页面替换算法有哪些?

在程序运行过程中,如果要访问的页面不在内存中,就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间,系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

包括以下算法:

最佳算法

所选择的被换出的页面将是最长时间内不再被访问,通常可以 保证获得最低的缺页率。这是一种理论上的算法,因为无法知道一个页面多长时间不再被访问。

先进先出

选择换出的页面是最先进入的页面。该算法将那些经常被访问的页面也被换出,从而使缺页率升高。

LRU

虽然无法知道将来要使用的页面情况,但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。为了实现 LRU,需要在内存中 维护一个所有页面的链表。当一个页面被访问时,将这个页面移到链表表 头。这样就能保证链表表尾的页面是最近最久未访问的。因为每次访问都 需要更新链表,因此这种方式实现的 LRU 代价很高。

时钟算法

时钟算法使用环形链表将页面连接起来,再使用一个指针指向最老的页面。它将整个环形链表的每一个页面做一个标记,如果标记是 0, 那么暂时就不会被替换,然后时钟算法遍历整个环,遇到标记为 1 的就替换,否则将标记为 0 的标记为 1。

回复

我来回复
  • 暂无回复内容

免费咨询
免费咨询
扫码关注
扫码关注
联系站长

站长Johngo!

大数据和算法重度研究者!

持续产出大数据、算法、LeetCode干货,以及业界好资源!

2022012703491714

微信来撩,免费咨询:xiaozhu_tec

分享本页
返回顶部