页面置换算法

将逻辑地址转换为物理地址的过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。

当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法

。

最佳置换算法（OPT，理想置换算法）

从主存中移出永远不再需要的页面，如无这样的页面存在，则选择最长时间不需要访问的页面

。由于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。

先进先出置换算法（FIFO）

当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰

。其理由是：最早调入主存的页面不再被使用的可能性最大。

最近最久未使用算法（LRU）

当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰

。这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。

时钟置换算法(CLOCK)

LRU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。

CLOCK算法需要使用到访问位。把各个页面组织成环形链表（类似于时钟面）。把指针指向最老的页面。当发生一个缺页中断的时候。若它的访问位为0，则淘汰，页面插入该位置并把访问位置1，指针下移；若访问位为1，则把该位置0，指针下移。

实现一个LRU算法（LeetCode146）

实现LRU的基本方法有两种：

• 用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。
• 利用一个链表来实现。每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。

对于第一种方法，需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及查询数据时，时间复杂度都是O(n)。对于第二种方法，链表查询数据的时间复杂度为O(n)，插入数据和删除数据的时间复杂度是O(1)。

有没有办法既能够让其查询快，又能够快速进行增删操作？我们可以选择链表+hash表，hash表的查询可以达到O(1)时间复杂度，这样就完美的解决我们查询时间慢的问题了。

驻留集和工作集

驻留集指请求分页存储管理中给一个进程分配的物理块的集合,在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小

。

工作集指在某段时间间隔里，进程实际访问页面的集合

。

若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少；驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。

采用页面分配策略决定每个进程驻留集的大小。

页面分配策略

常见的页面分配策略分为三种：

固定分配局部置换

、

可变分配全局置换

、

可变分配局部置换

。

固定分配局部置换

系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选岀一页换岀，然后再调入需要的页面。

这种策略的缺点是：很难在刚开始就确定应为每个进程分配多少个物理块才算合理，采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给岀的参数来确定为一个进程分配的内存块数。

可变分配全局置换

刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取岀一块分配给该进程；若已无空闲物理块，则可选择个未锁定(系统会锁定一些页面，如：重要的内核数据）)的页面换出外存，再将该物理块分配给缺页的进程。

釆用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调岀。被选择调岀的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。

可变分配局部置换

刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。

抖动（颠簸）现象

刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动或颠簸

。

产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）。

为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率。因此，一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。