页面调度算法_nru页面调度算法

当发生缺页中断时，操作系统必须在内存中选择一个页面将其换出内存，以便为即将调入的页面腾出空间。如果要患处的页面在内存驻留期间已经被修改过，那么它在磁盘上的副本已经是最新的，不需要诙谐，直接用调入的页面覆盖被淘汰的页面就可以了。

• 最优页面置换算法

在缺页中断发生时，有些页面在内存中，其中有一个页面很快被访问，其他页面可能要在10，100，1000条指令后才会被访问，每个页面都可以用在该页面首次被访问钱索要执行的指令作为标记。

这个算法的唯一缺点是无法是实现，当却也中断发生时，操作系统无法知道各个页面下一次将在什么时候被访问。

• 最近未使用页面置换算法

为使操作系统能够收集有用的统计信息，在大部分具有虚拟内存的计算机中，系统为每一页面设置两个状态位，当页面被访问时置为R，当页面被写入时置为M

当启动一个进程时，它的所有页面的两个位置由操作系统设置位0，R位被定期地清零，以区别最近没有被访问地页面和被访问地页面。

当发生缺页中断时，操作系统检查所有地页面并根据他们当前地R位和M位地值，把他们分为4类：

第0类：没有被访问，没有被修改
第1类：没有被访问，已被修改
第2类：已被访问，没有被修改
第3类：已被访问，已被修改

NRU算法随机地从类编号最小的非空类中挑选一个页面淘汰

• 先进先出页面置换算法

由操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在标为，最早进入的页面放在表头。当发生缺页中断时，淘汰标头的页面并把新调入的页面放在标为。

• 第二次机会页面置换算法

FIFO算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做了一个简单的修改，检查最老页面的R位，如果R位位-，那么这个页面即老又没有被使用，可以立即之换掉；如果时1，就将R位清零，并将该页面放在表尾。

• 时钟页面置换算法

尽管第二次机会算法是一个比较合理的算法，但是它经常要在链表中移动页面，既降低了效率又不是很有必要。一个更好的办法是把所有的页面都放在一个类似钟面的环形链表中，一个表指指向最老的页面。

• 最近最少使用页面算法

虽然LRU在理论上是可以实现的，但代价很高。为了完全首先LRU，需要在内存中维护一个所有页面的来年表，最近最多使用的页面在表头，最近最少使用的页面在表位。困难的是在每次访问内存时都必须要更新整个链表。在来年表中找到一个页面，删除它，然后把它移动到表头十一i按非常费时的操作。

• 工作集页面置换算法

在单纯的分页系统里，刚启动进程时，在内存中并没有页面。在CPU试图去第一条指令时就会产生一次缺页中断，使操作系统装入内有第一条指令的页面。

• 工作集时钟页面置换算法

当缺页中断发生后，需要扫描整个页表才能确定被淘汰的页面，因此基本工作及算法是比较费事的。

工作集时钟是基于时钟算法，并且使用了工作集信息。