磁盘缓存算法对应用程序的性能影响及优化研究

2022-09-11

现代计算机及智能终端都安装了操作系统, 文件系统是操作系统的基本模块之一。为了解决CPU与磁盘I/O性能不匹配的问题, 大多采用了把一小部分内存作为磁盘数据块的高速缓存, 以提升应用程序对用户的响应时间, 从而达到提高整体性能的目的。

由于内存和磁盘容量的巨大差异, 无法做到对整个磁盘的缓存, 因此, 缓存的算法就显得非常重要。各种磁盘缓存算法, 都有其最适用的场景。因此, 根据应用来制定相应的缓存策略, 就显得尤其重要。

一、缓存算法综述

(1) LRU算法。LRU算法是基于访问时间的缓存算法。该算法用于维护缓存项队列, 队列中的缓存项按照每页的最后访问时间进行排序。当缓存空间已满时, 队列指针指向队尾, 然后删除最后访问时间距现在最久的缓存项, 将新的访问项放入队头。LRU算法的出发点是如果某页被访问则该页可能再被访问。或者反过来说, 如果某页很长时间未被访问, 则该页在最近一段时间也不会访问[1]。 (2) LFU算法。LFU算法从本质上是一种很据过去的访问规律去预测将来的访问规律的算法。它是一种基于使用频繁程度的副本替换策略, 其假定近期文件的引用次数越多, 则将来的引用次数越多。在缓存中, LFU算法会将每一个缓存项按照被访问的频率进行排序, 当缓存空间已满时, 就用新缓存块替换掉缓存队列中访问频率最低的一项。与LRU缺点类似, LFU算法无法区分它所依据的频繁率是早期频繁还是最近频繁。 (3) LRU-2算法。LRU-2算法可以说是对LRU算法的改进, 也有人将它称作最近最少使用twice。它会将被两次访问过的数据放入缓存, 当缓存空间已满时, 就会把倒数第二次访问时间距现在最久的缓存项替换出去。相比于LRU, LRU-2需要多维护一个队列, 这个队列用来记录所有缓存数据被访问的历史。当数据的访问次数达到2次的时候才将数据放入缓存, 而要淘汰数据的时候就会淘汰掉第二次访问时间距当前时间最大的数据。我们要知道数据从访问历史中到缓存队列时要按照新的访问时间重新排序, 淘汰数据时候就淘汰排在缓存队列中最末尾的数据, 也就是“淘汰倒数第K次访问离现在最久”的数据。 (4) 2Q算法。2Q算法类似于LRU-2, 不同点在于2Q将LRU-2算法中的访问历史队列改为一个FIFO (先进先出) 缓存队列, 也就是说, 2Q算法有两个缓存队列, 一个是FIFO队列, 一个是LRU队列。当数据第一次访问的时候, 该算法先将数据缓存在FIFO队列中, 若数据在FIFO中一直都未被再次访问就按照FIFO规则淘汰, 若数据在FIFO队列中被再次访问, 则将数据移到LRU队列中, 按照LRU算法规则替换数据。 (5) LIRS算法。LIRS算法是基于访问频率的缓存算法。它引入了IRR的概念, 指的是同一个缓存数据在两次访问间隔中, 访问过其他缓存数据的个数[2]。它将数据分成两部分:LIR和HIR。其中LIR中的数据是热点, 在较短的时间内被访问了至少两次, 也就是说访问频率比较高的数据。而HIR部分用于存储HIR界面。将所有最近被访问的界面放置于栈S, 所有常驻HIR界面放置于栈Q, 当栈S的一个界面被访问时就会被移到栈S的顶部, 同时要确保栈S的尾部是一个LIR块;而当栈Q的一个HIR页面被访问了, 该HIR页面就会转变为LIR界面, 相应的栈S的底部LIR界面会转变为HIR界面并移至栈Q的顶部;当栈S和栈Q中的界面都不命中的时候, 就会考虑常驻页面的替换, 首先被替换出去的是处于栈Q底部的常驻HIR界面。 (6) FBR算法。FBR算法是同时考虑时间和频率的算法, 将考察的时间延长, 记录一段时间内缓存的访问情况, 为所有的缓存块维护一个访问频率计数器。该算法将缓存空间分成old, middle, new三个区段, 只对middle和old区域的缓存块的访问频率进行更新, 替换缓存块时在old区选取访问频率最低的缓存块进行替换[3]。该算法将缓存空间进行分区, 并对缓存项的使用次数进行计数, 删除去计数值最小的一项。这体现了高频率数据在缓存空间存留时间长, 顾全了效率。另外, 在FBR算法中, 一个缓存项被命中了, 该缓存项就会被移到new区域的MRU端, 如果该项原本位于old或者middle区, 就进行计数加1, 若原本位于new区就计数值不变。很容易知道在new区域, 数据是按照访问时间进行排序的, 刚访问的数据放在对应的位置。在这方面又兼顾了访问时间的性质, 最近访问频率又高的数据在相比较之下再次被访问的几率也是极大的 (7) LFRU算法。LFRU算法融合了最近最少使用和最不频繁使用两种算法的基本思想, 他选择最近访问最少的而且最近又没有被访问的块作为替换对象。由于结合了这两种算法的优势, 一方面考察了过去一段时间的访问频率, 另一方面根据最近最少访问的原则判断了未来访问的可能性。 (8) MQ算法。MQ算法属于根据访问频率来管理缓存空间的算法。它根据访问频率将数据分成多个队列, 不同的队列具有不同的优先访问级, 其核心思想史优先缓存访问次数多的数据。该算法将缓存划分成多个LRU队列, 每一个队列对应不同的访问优先级, 而访问优先级又是根据访问次数计算出来的。对于每一个队列按照LRU规则管理数据, 当数据的访问次数达到一定次数需要提升优先级时, 就将该数据从当前队列删除, 加入到高一级队列的头部。鉴于MQ需要维护多个队列, 且需要维护每个数据的访问时间复杂度要比LRU要高, 但是所有队列之和受限于缓存容量的大小, 同LRU相比队列的扫描性能是相近的。并且该算法保证了优先级的访问, 对于一些高频数据的访问是及其有利的。

二、应用性能分析

前面我们用很大篇幅介绍了多种缓存算法, 他们各有优劣, 所适用的场景也就不同。我们在日常使用电脑过程中会发现有些应用程序响应速度快, 而使用有些程序却反应似蜗牛。

对磁盘和内存的占用方式不同, 所使用的缓存算法不同, 对于性能的影响也就不同。下面我们以浏览器和office办公软件应用程序为例进行说明。

(1) 浏览器。电脑的主要功能之一就是通过浏览器上网。浏览网页时有以下几个特点:

一是很多网页我们仅仅浏览过一次, 而这些数据被存放到缓存空间开始到后面被替换出去就再也没被访问过;二是存在一些网页或者网站我们会重复使用, 比如校内网站、常用观影网站, 鉴于我们使用周期性, 这些网页请求的数据将会被再次请求读取。

应用程序浏览器内存管理是一块已分配的内存上再组织内存的使用方式, 它不会涉及操作系统的内存管理。系统在启动时, 内存大小已经固定浏览器在运行过程中, 所有的页面和浏览器本身都同在一个进程中, 共享同一块内存空间, 当内存不够时, 可以关闭界面来释放内存。

在这个过程中, 会产生一些内存碎片在页面关闭时不能被彻底释放, 在我们重复的打开、关闭操作之后, 内存资源可能就会被浏览器侵占而导致资源不足。

关于文件碎片, 顾名思义就是文件被分散保存到整个磁盘的各个地方, 磁盘上的文件碎片越多, 系统读取和新建文件速度也就非常的慢。当应用程序所需的物理内存不足时, 操作系统就会在硬盘中产生临时交换文件, 用该文件所占用的硬盘空间虚拟成内存。

而浏览器在浏览信息时生成的临时文件或临时文件目录就会造成系统中形成大量碎片。

浏览器提供了很多便民的功能比如历史记录、书签、收藏夹等等。当用户觉得有再次访问的必要时就会将某网页保存为书签、或者收藏, 而历史记录是浏览器对用户浏览记录的保存, 以便用户有需要可以直接点击访问。

浏览器本身是安装在我们的电脑的程序, 它为我们历史记录信息、书签信息等等自然都是保存在我们系统内存中, 这将是对我们内存的大量占用。基于前面所阐述的关于浏览器内存占用的特点, 最适合的缓存算法是将时间访问和频率访问相结合的算法, 比如FBR、LFRU算法。一方面我们在使用浏览器浏览网页时的访问目的变化性大, 或许在较长时间内才会有重复的可能性, 如果是仅仅按照访问时间来管理缓存, 那么缓存空间中存放大部分临时访问网页信息的可能性很大, 而有价值的可能再次访问的数据却很少。其次网页请求数量很大, 频繁进行缓存写入、删除、替换会产生大量磁盘碎片, 侵占内存。另一方面, 现实生活中人们存在固定访问某一网站或者网页的行为, 比如每天上新浪微博、或者基于工作要求间断性访问某一网站, 这就涉及到访问频率的问题。鉴于此, FBR或者LFRU算法可以用于浏览器应用程序的缓存管理。 (2) Office办公软件。Office办公软件包含word、excel、ppt等不同的应用程序, 实际上它是一种数据处理软件, 相应的包括对文字的处理、表格的处理以及多媒体的处理, 而任何处理一般都包括三个过程:输入、处理、输出。在这个过程中, 又会如何组织数据呢[4]?首先我们都知道程序在运行中磁盘的读写操作。

一般在运行一个程序时, 磁盘驱动器的磁头所做的工作就是先搜索改程序运行必需的文件, 然后读取数据, 最后做读后处理即将数据传送至磁盘高速缓存和内存中。

而在office办公软件使用常常是具有周期性或者说有规律的, 也就是说, 用户在打开这类应用程序时, 现在以及将来一段时间内都将会持续使用, 原因就在数据处理在短时间内无法完成并且并非时刻都有数据需要处理。相比与浏览器, 它的使用频率就少了[5]。

我们在使用office软件过程中, 除了第一次创建需要写入文件名、文件大小等信息以外, 在接下来往往都是通过当初我们命的文件名来进行访问操作。也就是说我们可以在缓存空间设定缓存项, 缓存项的内容就是这些文件名, 再由这些文件名链接到相应的数据区进行读取数据。

对于文件名缓存项的管理可以通过访问时间来存放。根据一般人的行为特性, 在对一个文本文件操作全部结束后, 在之后的很长一段时间内都将不会再访问, 若是这类文件的数据信息一直存放在缓存中毫无用处只会减少命中率。对于office办公软件的内存占用特性, 我更倾向于适用2Q算法。