三种页面置换算法

一、算法描述 1.先进先出（FIFO）置换算法 （1）描述：FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。 （2）优点：该算法实现简单，只需要把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。 （3）缺点：该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如：含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。 2.最佳（Optimal）置换算法 （1）描述：最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰的页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。 （2）优点：采用最佳置换算法通常可以保证获得最低的缺页率。 （3）缺点：人们目前通常还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因此，该算法是无法实现的，但可以利用该算法去评价其他算法。 3.LRU(Least Recently Used)置换算法 （1）描述:最近最久未使用（LUR）的页面置换算法是根据页面调入内存后使用情况做出决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”做“最近的将来”的近似，因此，LUR置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，及最近最久未使用的页面予以淘汰。 （2）优点：考虑程序访问的时间局部性，一般能有较好的性能，实际应用多。 （3）缺点：实现会需要较多的硬件支持，会增加硬件成本。 4、CLCOK算法又称为最近未使用算法（NUR） 每页设置一个访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列；当某个页面被访问时，其访问位置1。淘汰时，检查其访问位，如果是0，就换出；若为1，则重新将它置0；再按FIFO算法检查下一个页面，到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首再去检查第一个页面。

二、代码实现