了解操作系统中的页面置换算法

淩亂°似流年 2022-06-10 03:28 466阅读 0赞

# 说明 #

本文通过参考《计算机操作系统》（第四版）进行总结

# 正文 #

在进程运行过程中，若要访问的页面不在内存，且内存已无空闲时间时，为了保证该进程能正常进行，系统必须从内存中调出一页程序或数据送到磁盘的对换去中。但应将哪个页面调出，须根据一定的算法确定。

### 最佳( Optimal）置换算法 ###

特点：性能最好 可操作性差  
其所选择的被淘汰页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面

采用书上的例子进行说明  
ex：假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：  
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

![这里写图片描述][SouthEast]

### 先进先出（FIFIO）页面置换算法 ###

特点：简单 性能较差  
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。  
该算法实现时，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面  
![这里写图片描述][SouthEast 1]  
利用FIOFO算法时，进行了12次页面置换，比最佳置换算法正好多一倍

### LRU（Least Recently Used）置换算法 ###

最近最久未使用使用算法时选择最近最久未使用的页面予以淘汰

与最佳置换算法比较，最佳置换算法是从“向后看”的观点出发的，即它是依据以后各页的使用情况进行判断；而LRU算法则是“向前看”的，即根据各页以前的使用情况来判断，而页面过去和未来的走向之间并无必然联系。

![这里写图片描述][SouthEast 2]

### 最少使用（Least Frequently Used, LFU）置换算法 ###

该置换算法选择在近期时期使用最少的页面作为淘汰页  
在采用LFU算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。

### Clock置换算法 ###

是一种LRU近似算法  
**简单的Clock置换算法**  
当利用简单Clock算法时，只需为每页设置一个访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，给予该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回队首去检查第一个页面。  
又把该算法称为**最近未使用**或**NRU（Not Recently Used）算法**

### 页面缓冲算法（Page Buffering Algorithm, PBA） ###

主要特点：

*  显著降低了页面换进、换出的频率，使磁盘I/O的操作次数大大减少，因而减少了页面的换进、换出的开销
 *  正是由于换入换出的开销大幅度减小，才能使其采用一种较简单的置换策略，如先进先出(FIFO)算法，它不需要特殊硬件的支持，实现起来十分简单

[SouthEast]: /images/20220610/dd322b43058c4cd8a7e1e71253e23832.png
[SouthEast 1]: /images/20220610/9899f42586224e488ca59ae7481f89f3.png
[SouthEast 2]: /images/20220610/5fb3f5fc4a16415a8efa1270f849b412.png