腾讯设计师也在用的高效设计工具

时钟页面置换算法

最不常用算法：当发生缺页中断时，选择访问次数最少的那个页面去淘汰。该算法可以给每个页面设置一个计数器，被访问时，该页面的访问计数器+1，在需要淘汰时，选择计数器值最小的那个页面。

这里有个问题：一个页面如果在开始的时候访问次数很多，但之后就再也不用了，那它可能永远都不会淘汰，但它又确实需要被淘汰，怎么办呢?可以定期把减少各个页面计数器的值，常见的方法是定期将页面计数器右移一位。

tips：最不常用算法(LFU)和最近最久未使用算法(LRU)的区别：LRU考察的是最久未访问，时间越短越好，而LFU考察的是访问的次数或频度，访问次数越多越好。

工作集页面置换算法

介绍该算法时首先介绍下什么是工作集。

工作集是指一个进程当前正在使用的页面的集合，可以用二元函数W(t, s)表示：

t表示当前的执行时刻)s表示工作集窗口，表示一个固定的时间段

W(t, s)表示在当前时刻t之前的s时间段中所有访问页面所组成的集合

不同时间下的工作集会有所变化，如图：
 

缺页中断的处理过程如下：

1. 如果内存中有空闲的物理页面，则分配一物理页帧r，然后转第4步，否则转第2步;
2. 选择某种页面置换算法，选择一个将被替换的物理页帧r，它所对应的逻辑页为q，如果该页在内存期间被修改过，则需把它写回到外存;
3. 将q所对应的页表项进行修改，把驻留位置0;
4. 将需要访问的页p装入到物理页面r中;
5. 修改p所对应的页表项的内容，把驻留位置1，把物理页帧号置为x;
6. 重新运行被中断的指令。

07页面置换算法都有哪些?

当缺页中断发生时，需要调入新的页面到内存中，而内存已满时，选择内存中哪个物理页面被置换是个学问，由此引入了多种页面置换算法，致力于尽可能减少页面的换入换出次数(缺页中断次数)。尽量把未来不再使用的或短期内较少使用的页面换出，通常在程序局部性原理指导下依据过去的统计数据来进行预测。

最优页面置换算法：当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之前，还需等待多长时间，从中选择等待时间最长的那个，作为被置换的页面。注意这只是一种理想情况，在实际系统中是无法实现的，因为操作系统不可能预测未来，不知道每一个页面要等待多长时间以后才会再次被访问。该算法可用作其它算法的性能评价的依据(在一个模拟器上运行某个程序，并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法)。

先进先出算法：最先进入的页面最先被淘汰，这种算法很简单，就不过多介绍啦。

最近最久未使用算法：传说中的LUR算法，当发生缺页中断时，选择最近最久没有使用过的页面淘汰，该算法会给每个页面一个字段，用于记录自上次访问以来所经历的时间T，当需要淘汰一个页面时，选择已有页面中T值最大的页面进行淘汰。

第二次机会页面置换算法：先进先出算法的升级版，只是在先进先出算法的基础上做了一点点改动，因为先进先出算法可能会把经常使用的页面置换出去，该方法会给这些页面多一次机会，给页面设置一个修改位R，每次淘汰最老页面时，检查最老页面的R位，如果R位是0，那么代表这个页面又老又没有被二次使用过，直接淘汰，如果这个页面的R位是1，表示该页面被二次访问过，将R位置0，并且把该页面放到链表的尾端，像该页面是最新进来的一样，然后继续按这种方法淘汰最老的页面。

时钟页面置换算法：第二次机会页面算法的升级版，尽管二次机会页面算法是比较合理的算法，但它需要在链表中经常移动页面，效率比较低，时钟页面置换算法如图，该算法把所有的页面都保存在一个类似时钟的环形链表中，一个表针指向最老的页面，当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并且把新的页面插入这个位置，然后表针移动到下一个位置，如果R位是1就将R位置0并把表针移动到下一个位置，重复这个过程直到找到一个R位是0的页面然后淘汰。

 

（编辑：潍坊站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!