57、可能是最全的页⾯置换算法总结了
1、最佳置换法(OPT)
最佳置换算法(OPT，Optimal) ：每次选择淘汰的页⾯将是以后永不使⽤，或者在最长时间内不再被访问的页⾯，这样可以保证最低的缺页率。
最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执⾏的过程中才能知道接下来会访问到的是哪个页⾯。操作系统⽆法提前预判页⾯访问序列。因此，最佳置换算法是⽆法实现的
2、先进先出置换算法(FIFO)
先进先出置换算法(FIFO) ：每次选择淘汰的页⾯是最早进⼊内存的页⾯
实现⽅法：把调⼊内存的页⾯根据调⼊的先后顺序排成⼀个队列，需要换出页⾯时选择队头页⾯队列的最⼤长度取决于系统为进程分配了多少个内存块。
只有FIFO算法会产⽣Belady异常，⽽LRU和OPT算法永远不会出现Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运⾏时的规律不适应，因为先进⼊的页⾯也有可能最经常被访问。因此，算法性能差。access被淘汰了吗
FIFO的性能较差，因为较早调⼊的页往往是经常被访问的页，这些页在FIFO算法下被反复调⼊和调出，并且有Belady现象。所谓Belady现象是指：采⽤FIFO算法时，如果对—个进程未分配它所要求的全部页⾯，有时就会出现分配的页⾯数增多但缺页率反⽽提⾼的异常现象。
3、最近最久未使⽤置换算法(LRU)
最近最久未使⽤置换算法(LRU，least recently used) ：每次淘汰的页⾯是最近最久未使⽤的页⾯
实现⽅法：赋予每个页⾯对应的页表项中，⽤访问字段记录该页⾯⾃.上次被访问以来所经历的时间t(该算法的实现需要专门的硬件⽀持，虽然算法性能好，但是实现困难，开销⼤)。当需要淘汰⼀个页⾯时，选择现有页⾯中t值最⼤的，即最近最久未使⽤的页⾯。
LRU性能较好，但需要寄存器和栈的硬件⽀持。LRU是堆栈类算法，理论上可以证明，堆栈类算法不可能出现Belady异常。
在⼿动做题时，若需要淘汰页⾯，可以逆向检查此时在内存中的⼏个页⾯号。在逆向扫描过程中最后⼀个出现的页号就是要淘汰的页⾯。
4、时钟置换算法(CLOCK)
最佳置换算法性OPT能最好，但⽆法实现；先进先出置换算法实现简单，但算法性能差；最近最久未使⽤置换算法性能好，是最接近OPT 算法性能的，但是实现起来需要专门的硬件⽀持，算法开销⼤。
所以操作系统的设计者尝试了很多算法，试图⽤⽐较⼩的开销接近LRU的性能，这类算法都是CLOCK 算法的变体，因为算法要循环扫描缓冲区像时钟⼀样转动。所以叫clock算法。
时钟置换算法是⼀种性能和开销较均衡的算法，⼜称CLOCK算法，或最近未⽤算法(NRU，Not Recently Used)
简单的CLOCK算法实现⽅法：为每个页⾯设置⼀个访问位，再将内存中的页⾯都通过链接指针链接成⼀个循环队列。当某页被访问时，其访问位置为1。当需要淘汰-⼀个页⾯时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下⼀个页⾯，若第- - ~轮扫描中所有页⾯都是1，则将这些页⾯的访问位依次置为0后，再进⾏第⼆轮扫描(第⼆轮扫描中⼀定会有访问位为0的页⾯，因此简单的CLOCK算法选择–个淘汰页⾯最多会经过两轮扫描)
5、改进型的时钟置换算法
简单的时钟置换算法仅考虑到⼀个页⾯最近是否被访问过。事实上，如果被淘汰的页⾯没有被修改过，就不需要执⾏I/O操作写回外存。只有被淘汰的页⾯被修改过时，才需要写回外存。
因此，除了考虑⼀个页⾯最近有没有被访问过之外，操作系统还应考虑页⾯有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页⾯，避免I/O操作。这就是改进型的时钟置换算法的思想。修改位=0，表⽰页⾯没有被修改过; 修改位=1，表⽰页⾯被修改过。
为⽅便讨论，⽤(访问位，修改位)的形式表⽰各页⾯状态。如(1, 1)表⽰⼀个页⾯近期被访问过，且被修改过。
改进型的Clock算法需要综合考虑某⼀内存页⾯的访问位和修改位来判断是否置换该页⾯。在实际编写算法过程中，同样可以⽤⼀个等长的整型数组来标识每个内存块的修改状态。访问位A和修改位M可以组成⼀下四种类型的页⾯。
算法规则：将所有可能被置换的页⾯排成–个循环队列
由于第⼆轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描⼀定会有⼀个帧被选中，因此改进型CLOCK置换算法选择- -个淘汰页⾯最多会进⾏四轮扫描

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。