对传统页面置换算法的分析与研究

摘要:随着虚拟存储技术在操作系统中的应用,大大提高了操作系统的性能,其中页面置换算法是虚拟存储管理的重要组成部分,页面置换算法的优劣将直接影响系统的整体性能。随着大量有着不同读写速度的外存设备共存于系统中,单一置换算法同样影响着系统的整体性能。

关键词:操作系统;虚拟存储;页面置换;算法

中图分类号:TP316.81 文献标识码:A文章编号:1007-9599 (2010) 10-0000-01

The Analysis and Research for Traditional Page Replacement Algorithm

Yang Ronggang

(Jinling College of Nanjing University,Nanjing210032,China)

Abstract:With the virtual storage technology applications in the operating system,greatly improved the performance of the operating system.And virtual memory page replacement algorithm is an important part of management.Page replacement algorithm will directly affect the merits of the overall system performance.With the large number of read and write speeds with different external memory devices co-exist in the system,a single replacement algorithm also affects the overall system performance.

Keywords:Operating system;Virtual storage;Page replacement;Algorithm

一、虚拟存储器的基本原理

虚拟存储器的实现是建立在离散分配存储管理方式的基础上的,一般采用分页请求系统或分段请求系统来实现。分页(段)请求系统是在分页(段)系统的基础上,增加了请求调页(段)功能、页面(分段)置换功能所形成的页(段)式虚拟存储器系统。它允许只装入若干页面(分段)的用户程序和数据(而非全部程序和数据),便可以启动运行。以后,再通过调页(段)功能及页面(分段)置换功能,把所需要的页面(分段)调入内存,同时把暂时不运行的页面(分段)换出到外存上,置换时以页面(分段)为单位。

在请求分页式系统中,每当所要访问的页面不在内存时,便要产生一缺页中断,请求操作系统将所缺之页面调入内存。若内存已无空间时,为了保证该进程能正常运行,系统必须从内存中调出一个页面,但应该将哪个页面调出,则必须根据一定的算法来确定。通常,把选择换出页面的算法称为页面置换算法。

二、传统的页面置换算法

传统的页面置换算法主要有最佳置换算法(Optimal)、FIFO(First In First Out,先进先出)、LRU( Least Recently Used,最近最久未使用)和LFU(Least Frequently Used,最近最少使用)等算法。

最佳置换算法,其所选择的被淘汰页面将是永远不使用的,或者是在最长时间内不再被访问的页面。但由于无法预知一个进程在内存的若干个页面中,哪一个页面是未来最长时间不再被访问的,因而该算法也是无法实现的。

FIFO总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。而页面调入的先后并不能反映页面的使用情况,故此算法性能一般较差。

LRU是根据页面调入内存后的使用情况来决定淘汰哪个页面。由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”,LRU页面置换算法选择最近最久未使用的页面予以淘汰。但是页面的过去和未来的走向之间并无必然的联系。

LFU页面置换算法假定在一段时间内访问频率较高的页面与那些访问频率较低的页面相比,更有可能在不远的将来被访问,因而选择在一段时间内访问频率较低的页面予以淘汰,即将最近时期使用最少的页面作为淘汰页。

三、传统的页面置换算法存在的不足

大量研究表明,大多数程序在运行时其页面访问序列呈现出一定的规律,这些规律与程序本身的内在特性有关:科学计算类程序在运行时其页面访问模式为循环型;数据库处理类程序在运行时其页面访问模式为概率型;Unix系统类程序在运行时其页面访问模式为顺序型或时间聚类型;多媒体处理类程序在运行时其页面访问模式为顺序型或循环型。

传统页面置换算法存在的最大不足,在于它们对于不同类型的程序采用相同的页面置换策略,而忽视了程序在运行时具有不同的页面访问模式这样一个事实。对于某个特定的页面访问模式最好能选用一个使系统缺页次数最少的最佳的页面置换策略,这样系统缺页率能降至最低,整个系统的性能会有所提高。

随着硬件技术的发展,各式各样的大容量存储设备相继出现,一台计算机上可能存在多种外存储设备。不同存储设备有着不同的读写速度,同一种设备的读写速度有可能也会相差很大。因此在多种具有不同读写速度的外存储设备的环境下,选择一种合适的页面淘汰算法,对整个系统的性能会有很大的提高。

目前大多数操作系统在页面置换时往往只采用某一种特定的页面置换算法,没能做到先探测当前运行程序的页面访问模式,然后针对不同的页面访问模式,选用不同的页面置换算法,这是一个很大的缺陷。同时,某一特定的页面置换算法既不能够考虑到不同外存储设备之间读写速度的差异,也不能够考虑到干净页面与脏页面淘汰代价的不同。

本文介绍两种已经被大量研究过的页面置算法:基于探测的自适应页面置换算法和ELRUK页面置换算法。

四、基于探测的自适应页面置换算法

基于探测的自适应页面置换算法的基本思想是系统在不需要任何人工干预的情况下,动态地探测每个运行程序的页面访问模式,然后针对不同的页面访问模式选用一个合适的页面置换算法,这样可以降低系统的缺页率,避免“抖动”现象的发生,提高系统的整体性能。本算法通过将程序运行过程中被访问页面的相关属性与这些页面的前向距离联系起来的方法来确定运行程序的页面访问模式,在本文中我们用到的页面相关属性主要有后向距离和访问频率。

探测工作由一个被周期性唤醒的监控进程来完成。当该进程在第i次被唤醒时,监控进程计算出所有在时间mi-1和mi之间被访问过的页面的前向距离,这些前向距离通过两个排序的链表与页面的相关属性联系起来,其中一个链表与后向距离有关,另一个链表与访问频率有关。将每个排序的链表分为若干个长度相同的子链表,通过分析每个子链表的相关属性值与该子链表中的所有页面的平均前向距离之间的关系,可以确定当前运行程序的页面访问模式。

五、结束语

本文首先对虚拟存储器存在的基本原理进行了分析,知道分页系统存在的可能性。然后又对传统页面置换算法进行了分析,得出其存在的不足。在分析传统页面置换算法存在不足的基础上,介绍了两种能够弥补传统页面置换算法存在不足的基于探测的自适应页面置换算法和ELRUK页面置换算法。通过这两种置换算法的结合,对操作系统的整体性能的提高具有重要意义。

参考文献:

[1]殷联甫,汪承焱.基于探测的自适应页面置换算法研究[J].计算机应用于软件,2005,22

[2]沈仕敏,陈闳中,方钰.一种量化的页面淘汰算法[J].计算机工程与科学,2008,30

作者简介:杨荣刚(1987-),男,江苏泰州人,南京大学金陵学院,计算机科学与技术,本科学生