虚拟存储器—页面置换算法

一、最佳页面置换算法 OPT

目前是理想化的算法&＃xff0c;是无法实现的。

选择内存中被淘汰页面的条件&＃xff1a;

重点在于以后&＃xff0c;看物理块中哪一个页号在以后是最后才被访问使用的或者不使用的。

例题&＃xff1a;给出某进程所分配到的物理块数量&＃xff0c;以及接下来所要使用的页面号顺序&＃xff0c;让你使用该算法画出置换图。

发生第一次置换的详细分析&＃xff1a;

此时要访问页号2&＃xff0c;但是3个物理块已经满了&＃xff0c;所以发生缺页中断&＃xff0c;使用最佳页面置换算法把其中一个替换掉。

此时在未使用的页号顺序里面查看判断&＃xff0c;看物理块中的3个页号中&＃xff0c;哪一个是最后才访问使用的。

在这顺序里可以知道&＃xff0c;7是第18次页面访问时才使用&＃xff0c;0是第5次页面访问时使用&＃xff0c;1是第14次页面访问时使用。所以我们要淘汰最后一个才使用的页号7&＃xff0c;把页号2替换页号7&＃xff0c;物理块里面就变为了2 0 1。

二、先进先出置换算法 FIFO

选择内存中被淘汰页面的条件&＃xff1a;

看物理块中哪一个页号是第一个进来的&＃xff0c;即驻留时间最长&＃xff0c;就淘汰该页号。是根据页面调入内存的时间做决策的。

发生第一次置换的详细分析&＃xff1a;

上述例题中&＃xff0c;当要访问使用页号2时&＃xff0c;查看物理块中701中哪一个是第一个进来的就要最先淘汰出去&＃xff0c;所以叫作先进先出。

可以从页号顺序得知7是最先进入物理块的&＃xff0c;所以淘汰页号7。

此时物理块变为2 0 1 。

三、最近最久未使用置换算法&＃xff08;least recently used&＃xff0c;LRU&＃xff09;

选择内存中被淘汰页面的条件&＃xff1a;

是根据页面调入内存后的使用情况做决策的。

发生第一次置换的详细分析&＃xff1a;

四、最少使用置换算法

选择内存中被淘汰页面的条件&＃xff1a;

最近时期使用最少的页面作为淘汰页面&＃xff0c;即看以后的页面访问顺序中&＃xff0c;哪一个页面的访问次数最少就作为淘汰页面。

五、Clock置换算法

选择内存中被淘汰页面的条件&＃xff1a;

额外条件&＃xff1a;

每页设置一个访问位&＃xff0c;并将内存中的所有页面链接成一个循环队列。

当某一页被访问时&＃xff0c;访问位置为1。

未被访问时&＃xff0c;访问位置为0。

淘汰条件&＃xff1a;

只需要看访问位是否为0&＃xff0c;是0就表示该页最近都未被访问使用过&＃xff0c;就淘汰该页。

如果是1&＃xff0c;表示该页近期被访问使用过&＃xff0c;此时重新将访问位置为0。

改进型Clock置换算法&＃xff1a;

在Clock置换算法的基础上增加修改位。

使用访问位、修改位同时决定要被淘汰的页面。