页面置换算法

最佳置换算法opt：

每次选择淘汰页面将是以后永不使用，或者在最长时间内不再被访问的页面。

先进先出置换算法FIFO：

每次选择淘汰的页面是最早进入内存的页面

Bekad异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

最近最久未使用置换算法LRU：

每次淘汰的页面是最近最久未使用的页面

实现：

赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t，当需要淘汰一个页面时，选择现有的页面中t最大的，即最久未被使用的页面

算法性能好，但实现困难，开销大

时钟置换算法CLOCK

实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将他置为0，暂不换出，检查下一页面，如果第一轮扫描中所有页面都是1，则将这些页面依次访问后置为0后，再进行第二轮扫描。

改进：

在其他条件都相同时，优先淘汰没有修改过的页面，避免IO操作。

修改位==0，标识页面未被修改；修改位==1，被修改过。

页面分配策略

驻留集：指请求分页存储系统中给进程分配的物理块集合

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

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

可变分配：现为每个进程分配一定数目的物理块，在进程运行期间，可根据情况适当的增加和减少。

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

全局置换：可将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

分配置换策略：

何时调入页面：

1.预调页策略：程序员指出调入哪些部分，运行前调入

2.请求调页策略：发现缺页时调入内存，运行时调入

何处调入页面：

抖动现象：

刚换出的页面马上换入内存，刚换入的页面马上换出外存