页面置换算法:当发送缺页中断(page fault)时,操作系统必须在内存中选择一个页面将其换出内存,以便为即将调入的页面腾出空间。
1. 最优页面置换算法
不可实现算法
算法描述:在缺页中断发生时,有些页面在内存中,其中有一个页面(包含紧接着的下一条指令的那个页面)将很快被访问,其他页面则可能要到10、100或1000条指令后才会被访问,每个页面都可以在给页面首次被访问前所要执行的指令数作为标记。最优页面置换算法规定应该置换标记最大的页面。
通俗描述:所有页面都有一个标记,该标记是该页面执行前所要执行的指令数,所置换的页面是标记最大的页面(也就是需要执行很多很多条指令后才会执行的页面)。
由于没法在页面执行前预知页面执行前需要执行多少条指令,所有本算法无法实现。
类似于短作业优先不可实现
2. 最近未使用页面置换算法
NRU(Not Recently Used 最近未使用算法)
操作系统为了能收集有用的统计信息,在大部分具有虚拟内存的计算机中,系统为每一页设置了两个状态位。
分别是访问位(Referenced)和修改位(Modified),其中访问位代表读或写。当启动一个进程时,该进程的所有页面会由操作系统将两个状态位都置为0,而R位会定期的(如每次时钟中断)清零,以区别最近被访问和没有被访问的页面。M位不会被定期清零,因为在决定一个页面是否需要写回磁盘时将用到M位的信息。
算法描述:当发生缺页中断时,操作系统会坚持所有的页面并根据他们当前的R位和M位的值,将页面分为4类:
- 第0类:没有被访问,没有被修改。
- 第1类:没有被访问,已被修改。
- 第2类:已被访问,没有被修改。
- 第3类:已被访问,已被修改。
第1类的页面是第3类页面在R位被清零时产生的。
NRU算法会随机的从类编号最小的非空类中挑选一个页面淘汰并置换新页面。
其中的类编号指的是上面的第0类、第1类等。
其中的隐含的意思是:在最近的一个时钟滴答中,淘汰一个没有被访问但已被修改(第1类)的页面比淘汰一个被频繁使用的干净(不被修改)的页面(第2类)要好。
3. 先进先出页面置换算法
FIFO(First-In First-Out)算法
算法描述:操作系统会维护一个所有当前在内存中页面的链表,最新进入的页面放在表尾,最早进入的页面放在表头。当发生缺页中断时,淘汰表头的页面(最早进入的页面、最老的页面)并把新页面放在表尾。
4. 第二次机会页面置换算法
第二次机会(Second Chance)算法的目的是为了解决FIFO算法可能把经常使用的页面置换出去的问题而设计。
算法描述:当发生缺页中断时,检查老页面(表头页面)的R位,若R位为0,则意味着该页面既老又没被使用,则立刻用新页面置换;若为1,则把R位清零,并将该页面放到链表的尾部,就像刚装入一样,然后继续搜索。
5. 时钟页面置换算法
时钟(Clock)页面置换算法是为了解决第二次机会算法中经常要在链表中移动页面而降低效率的问题而设计的。
算法描述:把所有页面都保存在循环链表中(类似钟表的环形链表),用一个指针(表针)指向最老的页面(最早页面)。当缺页中断时,首先检查表针指向的页面的R位,为0则淘汰该页面,并把新页面插入这个位置,然后表针向前移动一格;为1则清楚该R位并向前寻找。
6. 最近最少使用页面置换算法
LRU(Least Recently Used)最近最少使用页面置换算法是对最优算法的近似
该算法的实现基于对指令执行的观察:在前几条指令中频繁使用的页面在后几条指令也很可能用到,已经很久没使用的页面在后面很长一段时间也可能不会用到。
算法描述:当缺页中断时,置换长时间未使用的页面。
虽然该算法可以实现,但是实现代价十分高昂,一般需要特殊的硬件支持,需要在内存中维护一个所有页面的链表,并在每次发生内存访问的时候去更新整个链表(在链表中找到访问的页面删除并将其移到到表头或者表尾,意味此页面是最新访问过的),十分耗时间。
7. 最不常用置换算法
NFU(Not Frequently Used)算法,是一种软件模拟的LRU算法。此算法将每个页面与一个软件计数器相关联,计数器初始值为0。每一次时钟中断时,操作系统将扫描所有的页面,将每个页面的R位(访问位)加到该页面的计数器上,计数器大体反映了页面被访问的频繁程度。发生缺页中断时,置换计数器值最小(即访问次数最少)的页面。
NFU的主要问题:从来不忘记任何东西。在第一次扫描中被频繁使用的页面在第二次扫描时,其计数器仍然会很高。简单来说就是不会自动清零。
老化算法:将NFU经过简单修改:1.将R位加进计数器之前,将计数器右移一位;2.将R位加到计数器的最左端而不是最右端。这样做的好处时,当一个页面连续4次的时间中断都没有被访问过的话,该页面的计数器前面至少有4个连续的0,因此比在4个时间中断过程中有一次访问的页面计数器要小。
8. 工作集页面置换算法
请求调页(Demand paging):在页面被需要时被调入。
若每执行几条指令,程序就发生一次缺页中断,那么就称该程序发生了颠簸(thrashing)。缺页中断的时间代价是十分高昂的。
预先调页(Prepaging):在进程运行前预先装入工作集页面,能大大减少缺页中断发生概率。
工作集(Working Set):进程当前使用的页面称为它的工作集。
工作集模型(Working Set Model):分页系统设法跟踪进程的工作集,以确保在进程运行前,其工作集就已在内存中了。
在任意时刻t,都存在一个集合w(k,t),包含最近所有k次内存访问所访问过的页面。w(k,t)就是工作集。
工作集页面置换算法(The Working Set Page Replacement Algorithm):操作系统通过跟踪哪些页面在工作集中,当发生缺页中断时,淘汰一个不在工作集的页面。
实现:设想一个长度为k的移位寄存器,每次内存访问左移一位,并在右端插入刚刚访问过的页面号。移位寄存器的k个页面好即是工作集。当发生缺页中断时,读出移位寄存器并排序,然后删除重复页面,淘汰不在其中的页面即可。但维护移位寄存器并在缺页中断时处理它开销很大,这样的实现没有实际应用过。
工作集页面置换算法的一种可实现的近似做法是:考虑一段时间内的工作集,进程的工作集被定义为在过去的ɥ秒实际运行时间中进程所访问过的页面的集合。利用R位和上次访问时间统计出工作集,发生缺页中断时,淘汰在工作集以外的页面。
上图中每个表项包含:上次近似时间、R位
9. 工作集时钟页面置换算法
基本工作集算法的缺陷:当缺页中断发生后,需要扫描整个页表才能确定被淘汰的页面,十分费时间。
基于工作集页面置换算法改进,融合时钟算法,得到了工作集时钟页面置换(WSClock)算法。由于该算法实现简单,性能较好,在实际工作中应用广泛。
实现:发生缺页中断时,首先检查指针指向页面,检查其R位,若为1(最近被访问过),则置零后指向下一个页面;若为0,则继续检查其生存时间,若生存时间大于ɥ秒,该页面就不在工作集中,并会在磁盘上有有效副本,将申请将新页面放入此页框。若此页面被修改过(M位为1),则指向下一个(避免调度引起写磁盘操作)。
小结
最好的两种算法分别是老化算法和工作集时钟算法,分别基于LRU和工作集。
算法 | 注释 |
---|---|
最优算法 | 不可实现,但可作为基准 |
NRU(最近未使用)算法 | LRU的粗糙近似 |
FIFO算法 | 可能抛弃重要页面 |
第二次机会算法 | 比FIFO有较大改善 |
时钟算法 | 现实的 |
LRU(最近最少使用)算法 | 十分优秀,但难以实现 |
NFU(最不常用)算法 | LRU的相对粗糙近似 |
老化算法 | 非常近似LRU的有效算法 |
工作集算法 | 实现开销大 |
工作集时钟算法 | 好的、有效算法 |