页面置换算法的实现

发表于 | 分类于 | 次

页面置换算法的实现

页面置换算法的实现

在进程运行过程中，若其所要访问的页面不在内存，而需把它们调入内存，但内存已无空闲空间时，但为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。但应将哪个页面调出。需根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。

一个好的页面置换算法应具有较低的页面置换频率。从理论上上讲，应将那些以后不再会访问的页面换出，或把那些在较长时间内不会再访问的页面换出。

常用算法介绍

  1. 最佳置换算法
    最佳置换算法是由Belady与1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的，或许是在最长时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。但由于人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的。因而该算法是无法实现的。
  2. 先进先出页面置换算法
    FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面按先后次序连接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量，常用函数，例程等的页面，FIFO算法并不能保证这些页面不被淘汰。
  3. 最近最久未使用算法
    最近最久未使用(LRU)的页面置换算法是根据页面调入内存后的使用情况作出决策的。由于无法预测各页面将来的使用情况，只能利用”最近的过去”作为”最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。当需淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

LRU置换算法的硬件支持

  1. 寄存器
    为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为：R=Rn-1Rn-2Rn-3·····R1R0
    当某进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(列如 100ms)将寄存器右移一位。如果我们把n位寄存器的数看做一个整数，那么，具有最小数值的寄存器所对应的页面，就是最久未使用的页面。
  2. 栈
    可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问页面时，便将该页面的页面号从栈中移除，将它压入栈顶。因此，栈顶始终是最新被访问的页面的编号，而栈底则是最近最久未使用页面的编号。

FIFO与LRU使用栈数据结构代码效果如下(源码可按F12查看)：