操作系统几种主要的页面置换算法分别是用什么数据结构实现的?

一、操作系统几种主要的页面置换算法

算法通常只是描述解决问题的一个步骤，具体用什么数据结构实现则是视情况而定。LRU“实现起来比较困难，且开销大是因为LRU算法希望淘汰最后未使用的页面，而CLOCK算法则放低的要求，较久未使用即可，不一定是最久的。CLOCK算法恰好可以充分使用现有的为“请求分页存储管理“设计的硬件机构，所以也会更加高效，而LRU则难以使用现成的硬件机构来加速算法执行。

LRU又称最近最少使用，意为每次都淘汰最久未使用的页面。按照LRU的思想，一种实现思路如下三点：

下面来逐一分析这三点：

名列前茅点：这块内存空间不能太小，否则极易导致数据溢出，尤其是对于运行在server上OS来说，可能一开机就很久不关机，溢出的可能性更大。这段内存空间也不能太大，不然会造成空间浪费；

第二点：每执行一条指令必定带来至少一次访存，甚至更多，每次访存都要去维护这个时间开销无疑是很大的（CLOCK算法也要去维护一个bit，但是开销却小得多，原因后面再讨论），因为使用数组记录则需要线性的时间来维护，使用heap记录则需要对数时间来维护，而访存则是十分频繁的，这个代价是不能接受的；值得一提的是虽然看起来heap开销小一些，但是数据量很大的话heap相对无序array来说对缓存不友好，这也是一个问题，不过我不知道是否可以忽略；

第三点：选择出最久未使用的页面的开销也很大，使用无序array记录则需要线性的时间来查找，使用heap记录则需要对数时间来查找；

综合上述三点可知LRU具体实现起来确实很困难开销也很大。那么CLOCK算法和LRU相比优势在哪里？

未改进CLOCK算法需要维护一个bit，用来标志该页面是否被使用过；很自然地想到同样需要三点，即存储，维护和查找，但是前两点（存储和维护）的实现和开销相对LRU则简单很多。

延伸阅读：

二、全局页面置换算法

功能：

当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。

目标：

尽可能地减少页面的换进换出次数（既缺页中断的次数）。具体来说，把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测。

页面锁定（frame locking）：

用于描述必须常驻内存的操作系统的关键部分或时间关键（time-critical）的应用程序。实现的方法是L在页表中添加锁定标志位（lock bit）。使其不在页面置换算法范围之内，也就说不会被换入换出。

通常只需要考虑页号，因为偏移号一般不起作用。只保留页号。基于这个list来设计各种的页面替换算法。
通过模拟一个页面置换的行为并且记录产生页缺失数的数量。一般情况下，产生的缺页次数越少，性能就越高。