[访谈记录] 操作系统 VIII

本文已参与「新人创作礼」活动，一起开启掘金创作之路。

页面置换算法

页面的换入、换出需要磁盘I/O，因为涉及外存到内存互调，会有较大的开销，因此，优秀的页面置换算法应该是追求：更少的缺页率

最佳置换算法（OPT）

每次选择：以后永不使用，或者在最长时间内不再被访问的页面，进行淘汰，这样可以保证最低的缺页率。

由于需要预知未来，所以最佳置换算法是无法实现的。

整个过程：缺页中断发生了9次，页面置换发生了6次，缺页时未必发生页面置换，若有空闲内存块，就不用进行页面置换。

先进先出置换算法（FIFO）

每次选择：最早进入内存的页面进行淘汰（或者说在内存中待的时间最长的页面进行淘汰）

Belady异常（为进程分配的物理块数增大时，缺页次数不减反增的异常现象）

只有FIFO算法会产生Belady异常！！！ 并且FIFO性能并不好

最近最久未使用置换算法（LRU：Least Recently Used）

每次淘汰：最近最久未被使用的页面（参考过去的经验）

实现方法：给每个页面对应的页表项中，用访问字段记录该页面自上次被访问后所经历的时间t，当需要淘汰页面时，选择页面中t值最大的进行淘汰。

算法性能好（最接近OPT），但算法的实现需要专门的硬件支持，实现困难，开销大

时钟置换算法（Clock）（或：最近未用算法：NRU，Not Recently Used）

此算法是一种性能与开销都较均衡的算法，算法开销较小，性能也不错。

简单的时钟置换算法，实现方法：为每个页面设置一个访问位，将内存中的页面都链接成循环队列。 当某个页面被访问时，其访问位置为1。

当需要淘汰页面时，只需要检查页面的访问位，如果是0就选择该页换出；如果是1，则将它置0，暂不换出，继续检查下一个页面，若第一轮扫描所有的页面都是1，则将所有页面的访问位都置0(在扫描过程中已经置0了)，并开始第二轮扫描（这样第二轮扫描中一定会有访问位=0的页面。

简单的时钟置换算法选择一个页面进行淘汰时，最多会经过两轮扫描！！

由于扫描的过程类似于时钟，所以叫做时钟置换算法。

LRU和CLOCK算法的区别：

LRU：选择最近最久未被使用的页面进行淘汰，淘汰标准是：时间

CLOCK：选择最近最少使用的页面进行淘汰，淘汰标准是：使用频率

改进型的时钟置换算法

在简单算法的基础上，还要考虑页面是否修改过，在其他条件都相同时，优先淘汰没有修改过的页面，避免I/O操作。

用(访问位，修改位)的形式表示各个页面状态：如(1,1)表示一个页面近期被访问过且被修改过。

注意，只有第二轮需要将扫描过的访问位置0，其它几轮扫描不需要修改标志位。

先考虑最近未使用且未被修改（第一优先级）的，没找到就考虑最近未使用但被修改的（第二优先级），如果还没找到，就把所有访问位置0，再重新扫描找最近未使用且未被修改的（第三优先级），没找到就考虑最近未使用且被修改的（第四优先级）。

页面分配、置换策略

驻留集：请求分页存储管理中给进程分配的物理块的集合。（驻留集一般小于进程的总大小，肯定不可能整个内存都分配给该进程）

就是系统给进程分配的物理块个数

驻留集太小，会导致缺页频繁，系统要花费大量时间来处理缺页。

驻留集太大，会导致多道程序并发度下降，资源利用率降低。

固定分配： os为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。（即：驻留集大小不变）

可变分配： 先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。（即：驻留集大小可变）

局部置换： 发生缺页时，只能选进程自己的物理块进行置换。

全局置换： 可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存(就是把该物理块中的页面置换到外存，这个物理块就空了，可以分配给缺页的进程)，再分配给缺页进程。

分配和置换策略两两组合，构成三种策略（固定分配 + 全局置换，不能实现，因为全局置换中进程的物理块数肯定会改变，而固定分配又要求每个进程的物理块数固定）

1、固定分配 + 局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，只能从该进程在内存中的页面中选出一页进行置换。

缺点：很难在刚开始就确定为每个进程分配多少个物理块才算合理。

2、可变分配 + 全局置换：os刚开始为每个进程分配一定数量的物理块。os会保持一个空闲物理块队列，当某进程发生缺页时，从空闲物理块中取出一块分配给该进程。若无空闲的物理块，则选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。

采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。(被选择调出的页可能是系统中任何一个进程中的页)

3、可变分配 + 局部置换：给进程分配的物理块有可能变化，发生缺页时，只能选择进程自己的物理块进行置换。频繁缺页的进程，多分配一些物理块；缺页率很低的进程，回收一些物理块，直至缺页率合适。