欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

06-页面替换算法

最编程 2024-07-02 08:49:27
...

页面置换算法目标

当发生缺页中断时,如果内存空间不足,需要对页面进行换入换出,如何减少换入换出的次数。

最优页面置换算法

发生缺页中断时,对内存中的每一个逻辑计算下一次访问的时间,将时间最长的那个页面置换出去。但是这个算法作为一种未来算法是无法实现的,只是作为一种其他算法的评价标准。

先入先出置换算法(FIFO)

当产生缺页中断时,将链表首节点置换出去。
性能很差,被调出的页面可能是要经常访问的页面
根据装入内存的时间,顺序是固定的

最近最久未使用算法(LRU)

该算法是基于程序的局部性原理,选择将最近最久未使用的页面置换出去,默认认为最近频繁访问的页面,未来很有可能会继续 访问。
根据页面访问时间会更改链表顺序
实现1:维护一个页面链表,将刚访问的页面作为首节点,当发生缺页中断时,淘汰出去尾节点

时钟置换算法(clock)

需要用到页表项的访问位,当加载到内存时记为0,修改之后记为1.让页表组织成一个环形链表,把指针指向最老的页面,当发生缺页中断的时候,考察指针指向的最老的页面,如果访问位为0立即淘汰。如果访问位为1,就将访问位修改为0然后指针移向下一位。直到找到淘汰的页面。

二次机会法

再clock算法基础上,使用dirty bit和user bit两个页项,当缺页中断时全为0就立即淘汰,一个为0一个为1置为0指针下移,全为一就两次机会,直到遇到全为零淘汰出去。

最不常用算法(LFU)

淘汰掉访问次数最少的那个,对每个页面都增加一个访问计数器,当访问后计数器+1,注意到这个算法新页很吃亏,我们尝试定期将计数器除以2,又是ADMI和式增加积式减少的手段。

Belady现象

再FIFO算法中,分配的页帧大小越大,缺页率反而提高的异常现象。
可通过LRU算法来解决

工作集模型

二元组的形式描述某个进程某段时间访问的页面(x,y)
将不在工作集中的页面替换出去

缺页率页面置换算法

缺页率: 缺页次数除以内存访问次数
基于缺页率来动态调整常驻集的大小
常驻集大小 当前实际驻内存的页面种类

抖动问题

随着驻留内存的进程数目不断增加,分配给每个进程的物理页面数不断减少,缺页率上升,造成频繁的替换,这就是抖动

量化抖动

缺页频度: 两次缺页的平均间隔时间,
工作集大小

推荐阅读