2.虚拟内存管理

基本概念

注意

• 虚拟内存的最大容量是由计算机的地址结构（CPU寻址范围）确定的。如：某计算机地址结构为32位，按字节编址，则虚拟内存的最大容量为$2^{32}$字节
• 虚拟内存的实际容量= min（内存和外存容量之和，CPU寻址范围）^[1]

定义和特征

1. 多次性,指无须在作业运行时一次性地全部装入内存,而允许被分成多次调入内存运行,即只需将当前要运行的那部分程序和数据装入内存即可开始运行。以后每当要运行到尚末调入的那部分程序时,再将它调入。多次性是虚拟存储器最重要的特征。
2. 对换性。是指无须在作业运行时一直常驻内存,在进程运行期间,允许将那些暂不使用的程序和数据从内存调至外存的对换区 (换出),待以后需要时再将它们从外存调至内存(换进)。正是由于对换性,才使得虛拟存储器得以正常运行。
3. 虚拟性。是指从逻辑上扩充内存的容量,使用户所看到的内存容量远大于实际的内存容量。这是虛拟存储器所表现出的最重要特征,也是实现虛拟存储器的最重要目标。

虚拟内存技术的实现

不管哪种方式,都需要有一定的硬件支持,一般需要的支持有以下几个方面:

• 一定容量的内存和外存。
• 页表机制(或段表机制),作为主要的数据结构。
• 中断机构,当用户程序要访问的部分尚未调入内存时,则产生中断。
• 地址变换机构,逻辑地址到物理地址的变换。

请求分页管理方式

只要求将当前需要的一部分页面装入内存,除了需要一定容量的内存及外存的计算机系统,还需要有页表机制、缺页中断机构和地址变换机构。

页表机制

页号	物理块号	状态位P	访问字段A	修改位M	外存地址

• 状态位 P。用于指示该页是否己调入内存,供程序访问时参考。
• 访问宇段A。用于记录本页在一段时问内被访问的次数,或记录本页最近已有多长时间未被访问,供置换算法换出页面时参考。
• 修改位M。标识该页在调入内存后是否被修改过,以确定页面置换时是否写回外存。
• 外存地址。用于指出该页在外存上的地址,通常是物理块号,供调入该页时参考

缺页中断机构

缺页中断作为中断,同样要经历诸如保护 CPU 环境、分析中断原因、转入缺页中断处理程序、恢复 CPU 环境等几个步骤。但与一般的中断相比,它有以下两个明显的区别:

1. 在指令执行期间而非一条指令执行完后产生和处理中断信号,属于内部异常。
2. 一条指令在执行期间,可能产生多次缺页中断。

请求分页中的地址变换过程

image.png

页框分配

驻留集大小

给一个进程分配的物理页框的集合就是这个进程的驻留集

内存分配策略

固定分配局部置换

• 发生缺页,则只能从分配给该进程在内存的页面中选出一页换出
• 保证分配给该进程的内存空间不变

可变分配全局置换

先为每个进程分配一定数目的物理块,在进程运行期间可根据情况适当地增加或减少。所谓全局置换,是指如果进程在运行中发生缺页,系统从空闲物理块队列中取出一块分配给该进程, 并将所缺页调入。

可变分配局部置换

为每个进程分配一定数目的物理块,当某进程发生缺页时,只允许从该进程在内存的页面中选出一页换出,因此不会影响其他进程的运行。

1. 若进程在运行中频繁地发生缺页中断,则系统再为该进程分配若干物理块,直至该进程的缺页率趋于适当程度
2. 反之,若进程在运行中的缺页率特别低,则可适当减少分配给该进程的物理块,但不能引起其缺页率的明显增加

物理块调入算法

采用固定分配策略时：

1. 平均分配算法
2. 按比例分配算法
3. 优先权分配算法

调入页面的时机

1. 预调页策略。主要用于进程的首次调入,由程序员指出;应先调入哪些页
2. 请求调页策略。

预调入实际上就是运行前的调入,请求调页实际上就是运行期间调入

从何处调入页面

请求分页系统中的外存分为两部分:

1. 用于存放文件的文件区，用离散分配方式
2. 用于存放对换页面的对换区，采用连续分配方式

当发生缺页请求时,系统从何处将缺页调入内存就分为三种情况：

1. 系统拥有足够的对换区空间,可以全部从对换区调入所需页面,以提高调页速度。为此, 在进程运行前,需将与该进程有关的文件从文件区复制到对换区。
2. 系统缺少足够的对换区空间,凡是不会被修改的文件都直接从文件区调入;而当换出这些页面时,由于它们未被修改而不必再将它们换出。
3. UNIX 方式,与进程有关的文件都放在文件区,因此未运行过的页面都应从文件区调入。
   曾经运行过但又被换出的页面,由于是放在对换区,因此在下次调入时应从对换区调入。
   进程请求的共享页面若被其他进程调入内存,则无须再从对换区调入

如何调入页面

当进程所访问的页面不在内存中时(存在位为0),便向 CPU 发出缺页中断,中断响应后便转入缺页中断处理程序。该程序通过查找页表得到该页的物理块,此时如果内存未满,则启动磁盘 I/O,将所缺页调入内存,并修改页表。如果内存己满,则先按某种置换算法从内存中选出一页准备换出;如果该页未被修改过(修改位为0),则无须将该页写回磁盘;但是,如果该页己被修改(修改位为1),则必须将该页写回磁盘,然后将所缺页调入内存,并修改页表中的相应表项, 置其存在位为 1。调入完成后,进程就可利用修改后的页表形成所要访问数据的内存地址。

页面置换算法

最佳(OPT)置换算法

• 最佳置换算法选择的被淘汰页面是以后永不使用的页面,或是在最长时间内不再被访问的页面,以便保证获得最低的缺页率
• 该算法无法实现。但可利用该算法去评价其他算法

image.png

先进先出(FIFO)页面置换算法

优先淘汰最早进入内存的页面,即淘汰在内存中驻留时间最久的页面

image.png

Belady异常

• FIFO 算法还会产生所分配的物理块数增大而页故障数不减反增的异常现象,称为 Belady 异常。
• 只有FIFO 算法可能出现 Belady 异常,LRU 和 OPT 算法永远不会出现 Belady 异常

如图所示,页面访问顺序为3,2,1,0,3,2,4,3,2,1,0,4。若采用FIFO 置换算法,当分配的物理块为 了个时,缺页次数为9次:当分配的物理块为 4个时,缺页次数为 10 次。分配给进程的物理块增多,但缺页次数不减反增。

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

选择最近最长时间未访问过的页面子以淘汰,它认为过去一段时间内未访问过的页面,在最近的将来可能也不会被访问

image.png

LRU 算法的性能较好,但需要寄存器和栈的硬件支持。LRU 是堆栈类的算法。理论上可以证明,堆栈类算法不可能出现 Belady 异常。FIFO 算法基于队列实现,不是堆栈类算法。

时钟(CLOCK)置换箅法

简单的CLOCK 置换算法

该算法只有一位访问位,而置换时将未使用过的页面换出,故又称最近未用 (NRU)算法。

CLOCK 算法时的置换图

image.png

改进型CLOCK 置换算法

在选择页面换出时,优先考虑既未使用过又未修改过的页面

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

1. 1类4=0,M=0:最近未被访问且未被修改,是最佳淘汰页。
2. 2类A=0,M-1:最近未被访问,但己被修改,不是很好的淘汰页。
3. 3类4=1,M=0:最近已被访问,但未被修改,可能再被访问。
4. 4类A=1,M=1:最近已被访问且己被修改,可能再被访问。

在进行页面置换时,可采用与简单 CLOCK 算法类似的算法,差别在于该算法要同时检查访问位和修改位

改进型 CLOCK 算法优于简单 CLOCK 算法的地方在于,可减少磁盘的I/O 操作次数。但为了找到一个可置换的页,可能要经过几轮扫描,即实现算法本身的开销将有所增加。

提示

image.png

抖动和工作集

抖动

在页面置换过程中,一种最糟糕的情形是,刚刚换出的页面马上又要换入主存,刚刚换入的页面马上又要换出主存,这种频繁的页面调度行为称为抖动或颠簸。

根本原因是,系统中同时运行的进程太多,由此分配给每个进程的物理块太少,不能满足进程正常运行的基本要求,致使每个进程在运行时频繁地出现缺页,必须请求系统将所缺页面调入内存

警告

这会使得在系统中排队等待页面调入/调出的进程数目增加。显然,对磁盘的有效访问时间也随之急剧增加,造成每个进程的大部分时间都用于页面的换入/换出,而几乎不能再去做任何有效的工作,进而导致发生处理机的利用率急剧下降并趋于零的情况。

工作集

工作集是指在某段时问间隔内,进程要访问的页面集合

工作集$W$可由时间$y$和工作集窗口大小$\Delta$来确定

工作集示例

假设系统为该进程设定的工作集窗口大小$\Delta$为 5,则在$t_{1}$时刻,进程的工作集为2,3,5}, 在么时刻$t_{2}$进程的工作集为{1,2,3,4}。

对于局部性好的程序,工作集大小一般会比工作集窗口$\Delta$小很多

一般来说分配给进程的物理块数(即驻留集大小)要大于工作集大小。

工作集模型的原理

让操作系统跟踪每个进程的工作集,并为进程分配大于其工作集的物理块。落在工作集内的页面需要调入驻留集中,而落在工作集外的页面可从驻留集中换出。若还有空闲物理块,则可再调一个进程到内存。若所有进程的王作集之和超过了可用物理块总数,则操作系统会哲停一个进程,将其页面调出并将物理块分配给其他进程,防止出现抖动现象。

内存映射文件

磁盐文件的全部或部分内容与进程虛拟地址空间的某个区域建立映射关系,便可以直接访问被映射的文件,而不必执行文件I/0操作,也无须对文件内容进行缓存处理。

当进程退出或显式地解除文件映射时,所有被改动的页面会被写回磁盘文件

共享内存是通过映射相同文件到通信进程的虚拟地址空间实现的

image.png

虛拟存储器性能影响因素

分配给进程的物理块数越多,缺页率就越低,但是当物理块超过某个数目时,再为进程增加一个物理块对缺页率的改善是不明显的

写回磁盘(见《计算机组成原理考研复习指导》)的频率。换出已修改过的页面时,应当写回磁盘,如果每当一个页面被换出时就将它写回磁盘,那么每换出一个页面就需要启动一次磁盘,效率极低。为此在系统中建立一个已修改换出页面的链表,对每个要被换出的页面(已修改),可以暂不将它们写回磁盘,而将它们挂在该链表上,仅当被换出页面数达到给定值时,才将它们一起写回磁盘,这样就可品著减少磁盘 I/O 的次数,即减少己修改页面换出的开销。此外,如果有进程在这批数据还未写回磁盘时需要再次访问这些页面,就不需从外存调入,而直接从己修改换出页面链表上获取,这样也可以减少页面从磁盘读入内存的频率,减少页面换进的开销。

地址翻译

设某系统满足以下条件：

• 有一个 TLB 与一个 data Cache
• 存储器以字节为编址单位
• 虚拟地址14位
• 物理地址12位
• 页面大小为 64B
• TLB 为四路组相联，共有16个条目
• data Cache 是物理寻址、直接映射的，行大小为4B，共有16组

写出访问地址为 0x0344, 0x00f1 和 Ox0229 的过程。

因为本系统以字节编址，页面大小为 64B，则:

• 页内偏移地址为$\log_{2}(64\mathrm{B}/1\mathrm{B})=6$位，
• 虚拟页号为$14-6=8$位
• 物理页号为$12-6=6$位

因为 TLB为四路组相联，共有16个条目，则

• TLB 共有$16/4= 4$ 组
• 虚拟页号中低$\log_{2}4=2$ 位就为组索引，高6位就为 TLB 标记

又因为 Cache 行大小为4B，因此物理地址中低$\log_{2} 4=2$ 位为块偏移

Cache 共有16 组，可知接下来$\log_{2}16=4$ 位为组索引，剩下高6位作为标记

地址结构如图所示

地址结构

TLB、页表、data Cache 内容如表 3.1、表3.2及表3.3所示

image.png

image.png

先把十六进制的虛拟地址 0x03d4,0x00f1 和0x0229 转化为二进制形式

image.png

得到每个地址的组索引和 TLB 标记,接下来就要找出每个地址的页面在不在主存中,若在主存中,则还要找出物理地址。

1. 对于 0x03d4,组索引为3,TLB 标记为 0x03,查TLB,第3组中正好有标记为 03的项,有效位为 1,可知页面在主存中,对应的物理页号为 0d (001101),再拼接页内地址 010100,可得物理地址为 0x354 (001101010100)
2. 对于 0x00f1,组索引为 3,TLB 标记为 0x00,查TLB,第3组中没有标记为 00的项,再去找页表,虛拟页号为 0x03,页表第3行的有效位为1,可知页面在主存中,物理页号为 02(000010), 再拼接页内地址 110001,可得物理地址为 0x0b1 (000010110001)
3. 对于 0x0229,组索引为0,TLB 标记为 0x02,查TLB,第0组中没有标记为 02 的项,再去找页表,虛拟页号为0x08,页表第8行的有效位为 0,页面不在主存中,产生缺页中断

找出在主存中的页面的物理地址后，就要通过物理地址访问数据，接下来要找该物理地址的
内容在不在 Cache 中，物理地址结构如表3.5 所示。

image.png

1. 对于 0x354, Cache 索引为 5,Cache 标记为 0x0d,对照Cache 中索引为5 的行,标记正好为0d,有效位为1,可知该块在Cache 中,偏移0,即块0,可得虛拟地址上 0x03d4 的内容为 36H。
2. 对于 0x0b1,Cache 索引为c,Cache 标记为 0x02,对照 Cache 中索引为c的行,有效位为0, 可知该块不在 Cache 中,要去主存中查找物理页号为2、偏移为 0x31 的内容。

以上例子基本覆盖了从虛拟地址到 Cache 查找内容的所有可能出现的情况,读者务必要掌握此节的内容,查找顺序是从 TLB到页表(TLB 不命中),再到 Cache 和主存,最后到外存。

---

1. 汤子瀛教材中的说法 ↩︎