【操作系统】虚拟存储器--页面置换算法

╰+攻爆jí腚メ 2022-07-13 03:11 52阅读 0赞

页面置换算法是用来选择换出页面的算法。

页面置换算法的优劣直接影响到系统的效率，若选择不合适，可能会出现抖动（Thrashing）现象。

抖动：刚被淘汰出内存的页面，过后不久又要访问它，需要再次将其调入，而该页调入内存后不久又再次被淘汰出内存，然后又要访问它，如此反复，使得系统把大部分时间用在了页面的调进换出上，这种现象称为抖动。

# 最佳置换算法 OPT #

最佳置换算法 OPT

> 选择永远不再需要的页面或最长时间以后才需要访问的页面予以淘汰。

最佳置换算法是一种理想化的算法，性能最好，实际上这种算法无法实现，因为页面访问的未来顺序很难精确预测，但可用该算法评价其它算法的优劣。

例：假定系统为某进程分配了3个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时 3 个物理块均为空，计算采用最佳置换算法时的缺页率？

![图示][SouthEast]

简单解释一下：

由于开始物理块为空，所以最开始，1 2 3，都缺，当要将4调入时，由于3个物理块已满，所以需要换出，换出规则是**选择永远不再需要的页面或最长时间以后才需要访问的页面予以淘汰** 而1 2 将要用到，所以将3换出，一次类推。

# 先进先出置换算法 FIFO #

先进先出置换算法 FIFO

> 选择先进入内存的页面予以淘汰。

例：假定系统为某进程分配了3 个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时 3 个物理块均为空，计算采用先进先出置换算法时的缺页率？

![图示][SouthEast 1]

简单解释一下：

由于开始物理块为空，所以最开始，1 2 3，都缺，当要将4调入时，由于3个物理块已满，所以需要换出，换出规则是**选择先进入内存的页面予以淘汰** 而1为最先调入的，所以将1换出，一次类推。

例：假定系统为某进程分配了4 个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时 4 个物理块均为空，计算采用先进先出置换算法时的缺页率？

![图示][SouthEast 2]

例：假定系统为某进程分配了5 个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时 5 个物理块均为空，计算采用先进先出置换算法时的缺页率？

![图示][SouthEast 3]

先进先出置换算法的出发点是最早调入内存的页面，其不再被访问的可能性会大一些。  
被置换的页可能含有一个初始化程序段，用过后再也不会用到；但也可能含有一组全局变量，初始化时被调入内存，在整个程序运行过程中都将会用到。  
FIFO 算法易于理解与编程，但它的效率不高。

## Belady 异常现象 ##

先进先出算法存在一种异常现象，即在某些情况下会出现分配给进程的物理块数增多，缺页次数有时增加，有时减少的奇怪现象，这种现象称为 Belady 异常现象(Belady’s Anomaly) 。

## 例题 ##

温馨提示：以下为动图，注意观察

![图示][20161221180612935]

![图示][20161221180904999]

# 最近最久未使用算法（LRU） #

最近最久未使用算法 LRU

> 选择最近一段时间最长时间没有被访问过的页面予以淘汰。

算法的出发点：如果某个页面被访问了，则它可能马上还要访问。如果很长时间未被访问，则它在最近一段时间也不会被访问。

该算法的性能接近于最佳算法，但实现起来较困难。因为要找出最近最久未使用的页面，必须为每一页设置相关记录项，用于记录页面的访问情况，并且每访问一次页面都须更新该信息。这将使系统的开销加大，所以在实际系统中往往使用该算法的近似算法。

例：假定系统为某进程分配了3 个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时 3 个物理块均为空，计算采用最近最久未使用算法时的缺页率？

![图示][SouthEast 4]

简单解释一下：

由于开始物理块为空，所以最开始，1 2 3，都缺，当要将4调入时，由于3个物理块已满，所以需要选择换出，换出规则是**选择最近一段时间最长时间没有被访问过的页面予以淘汰** 而2 3刚刚访问过，所以将1换出，一次类推。

## 最近最久未使用算法的硬件支持 ##

LRU 置换算法虽然是一种比较好的算法，但实现开销很大，必须有硬件的支持。

### 1.寄存器 ###

为了记录某个进程在内存中各页的使用情况，为每个在内存中的页面配置一个移位寄存器，可表示为

![图示][SouthEast 5]

每当进程访问某页面时，将该页面对应寄存器的最高位(R n−1 ) 置 1，系统定期 (如 100ms) 将寄存器右移一位并将最高位补 0，如果把 n 位寄存器的数看作是一个整数，于是寄存器数值最小的页面是最久未使用的页面。

### 2.栈 ###

利用一特殊的栈保存当前使用的页号，每当进程访问某页面时，把被访问页面移到栈顶，于是栈底的页面就是最久未使用的页面。

![图示][SouthEast 6]

# 最近最少使用置换算法（LFU） #

最近最少使用置换算法 LFU

> 选择在最近时期使用最少的页面为淘汰页。

LFU 置换算法为在内存中的每个页面设置一个移位寄存器来记录该页面被访问的频率。

![图示][SouthEast 7]

## LRU 与 LFU 的区别 ##

LRU 是最近最久未使用页面置换算法 (Least Recently Used)，也就是首先淘汰最长时间未被使用的页面。

LFU 是最近最少使用置换算法 (Least Frequently Used)，也就是淘汰一定时期内被访问次数最少的页。

例如，进程分配了 3 个物理块，若所需页面走向为2 1 2 1 2 3 4（请求页面 4 时会发生缺页中断）

按 LRU 算法, 应换页面 1（1 页面最近最久未被使用） 。

但按 LFU 算法应换页面 3（页面 3 最近最少使用，最近只使用了一次） 。

LRU 是看时间长短，而 LFU 是看使用频率。

# Clock 置换算法 #

Clock 置换算法是 LRU 和 FIFO 的折衷（LRU 的近似算法，减少硬件消耗） 。也称为**最近未使用算法** (NotRecently Used，NRU)

该算法为每页设置一个访问位，并将内存中的所有页链接成一个循环队列。当某页被访问时，其访问位被置 1。

置换算法在选择一页淘汰时，只需检查页的访问位。如果是 0，就选择该页换出；若为 1，则重新将它置 0，暂不换出，而给该页第二次驻留内存的机会，再按照FIFO 算法检查下一个页面（循环，不是回到队首） 。

当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首去检查第一个页面。

![图示][SouthEast 8]

![图示][SouthEast 9]

假如某个页被频繁访问，那么它就不会被置换出去

![图示][SouthEast 10]

5位置有点绕，那就解释一下喽：

当调入5时，2,3,1访问位都为1，就按顺序，将2置0,3置0,1置0，然后再重头开始，2访问位，此时为0，则淘汰，将5调入，并将访问位置1。

![图示][SouthEast 11]

## 改进型 Clock 置换算法 ##

改进型 Clock 置换算法：除须考虑页面的使用情况外，还增加一个因素，即置换代价，这样选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。

由访问位 A 和修改位 M 可以组合成下面四种类型的页面：

![图示][SouthEast 12]

*  从指针所指示的当前位置开始扫描循环队列，寻找 A=0且 M=0 的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位 A。
 *  如果第一步失败，开始第二轮扫描，寻找 A=0 且 M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置 0。
 *  如果第二步也失败，则将指针返回到开始的位置，并将所有的访问位复 0。然后重复第一步，如果仍失败，必要时再重复第二步。

# 双指针 Clock 置换算法 #

双指针 Clock 置换算法：定时淘汰页面。前指针清除访问位，后指针淘汰页面。

![图示][SouthEast 13]

# 影响页面换入换出效率的若干因素 #

*  页面置换算法。
 *  回写磁盘的频率。已经被修改过的页面，换出时应当回写磁盘。如果建立一个已修改换出页面链表，可以暂不回写。当达到一定数目后，再将它们一起写入磁盘，这样能大大减少 I/O 操作的次数。
 *  读入内存的频率。已修改换出页面链表上的页面在回写前，如果需要被再次访问，就不需要从外存调入，直接从链表中获取。

# 页面缓冲算法 PBA #

页面缓冲算法：用 FIFO 算法选择被置换页，选择换出的页面不是立即换出，而是放入两个链表之一，如果页面未被修改，就将其归入到空闲页面链表的末尾，否则将其归入已修改页面链表末尾。

这些空闲页面和已修改页面会在内存中停留一段时间。如果这些页面被再次访问，只需将其从相应链表中移出，就可以返回进程，从而减少一次 I/O 开销。

需调入新页，则将新页读入到空闲页面链表的第一个页面中，然后将其从该链表中移出。

当已修改的页面达到一定数目后，再将它们一起写入磁盘。这样能大大减少 I/O 操作的次数。

# 页面置换算法的比较 #

![图示][SouthEast 14]

# 访问内存的有效时间 EAT #

被访问页面在内存，且对应的页表项在快表中。设访问快表的时间为 λ，访问内存的时间为 t。

![图示][SouthEast 15]

被访问页面在内存，但对应的页表项不在快表中。这种情况不缺页，但需两次访问内存。一次读页表，并更新快表，一次读数据。

![图示][SouthEast 16]

更新快表 λ 与读数据t可并行。

被访问页面不在内存。缺页。设缺页中断处理时间为 ϵ。

![这里写图片描述][SouthEast 17]

上面的几种讨论没有考虑快表的命中率和缺页率等因素。

如果考虑快表的命中率 a和缺页率 f

![图示][SouthEast 18]

如果不考虑快表，仅考虑缺页率 f，即令上式中 λ = 0  
和 a = 0，

![图示][SouthEast 19]

![图示][SouthEast 20]

[SouthEast]: /images/20220713/5c8bd795fc2344aa84b9697ec892c7ef.png
[SouthEast 1]: /images/20220713/92569a32f02e4f41b74c9f0754b8784d.png
[SouthEast 2]: /images/20220713/76e721f6475f4ab39d111c8a1dcab611.png
[SouthEast 3]: /images/20220713/001a61cf30c844fb8b53eeecfb52c92d.png
[20161221180612935]: /images/20220713/86a8e756de924ebd8254b659572b29bd.png
[20161221180904999]: /images/20220713/b8898a2ec2b74c7a9caf8c76e62b947e.png
[SouthEast 4]: /images/20220713/285cb787e9794068b1dedb4788949666.png
[SouthEast 5]: /images/20220713/be00a9ffd8c7459faed190956200dd1a.png
[SouthEast 6]: /images/20220713/60772750c5cc4ccf93b6adda529a0c77.png
[SouthEast 7]: /images/20220713/89617cf5552a4fdab8712b87e1ec4ee4.png
[SouthEast 8]: /images/20220713/d5ff95e58531412d9ea58e573814223a.png
[SouthEast 9]: /images/20220713/0e32a0fa4a834e70977e7e794e8c823d.png
[SouthEast 10]: /images/20220713/1c036b597fb44b38b6263e5b371885d1.png
[SouthEast 11]: /images/20220713/5d7188841d1e4061b3bedf9b0a959e82.png
[SouthEast 12]: /images/20220713/d3817926903e41b8bddc84ad090e3181.png
[SouthEast 13]: /images/20220713/fc9390f30fff4049b66926a06066a63a.png
[SouthEast 14]: /images/20220713/8eff051b89a44c9ea695a58654adb176.png
[SouthEast 15]: /images/20220713/2800f1563565484d9be5e65c7899c7a7.png
[SouthEast 16]: /images/20220713/1817b44429eb49d0b77aac9517bd7c44.png
[SouthEast 17]: /images/20220713/3b9df305eed04f8ebd25f1a0e1989b08.png
[SouthEast 18]: /images/20220713/fb120b3585324cbcb0c7bb7e5351431b.png
[SouthEast 19]: /images/20220713/82f32be2dbc44eb4acaae49818b65475.png
[SouthEast 20]: /images/20220713/4ff0923e250f490ea71873017d00a3de.png