《现代操作系统》-读书笔记-第三章-内存管理

《现代操作系统》-读书笔记-第三章-内存管理

内存(RAM)是计算机中一种需要认真管理的重要资源。

经过多年探索,人们提出了分层存储器体系(memory hierarchy)的概念,即在这个体系中,计算机有若干兆(MB)快速、昂贵且易失性的高速缓存(cache),数千兆(GB)速度与价格适中且同样易失性的内存,以及几兆兆(TB)低速、廉价、非易失性的磁盘存储,另外还有诸如 DVD 和 USB 等可移动存储装置。操作系统的工作是将这个存储体系抽象为一个有用的模型并管理这个抽象模型。

操作系统中管理分层存储器体系的部分称为存储管理器(memory manager)。它的任务是有效地管理内存,即记录哪些内存是正在使用的,哪些内存是空闲的;在进程需要时为其分配内存,在进程使用完后释放内存。

无存储器抽象

最简单的存储器抽象就是根本没有抽象。早期大型计算机(20 世纪 60 年代之前)、小型计算机(20 世纪 70 年代之前)和个人计算机(20 世纪 80 年代之前)都没有存储器抽象。每一个程序都直接访问物理内存。当一个程序执行如下指令:

MOV REGISTER1, 1000

计算机会将位置为 1000 的物理内存中的内容移到 REGISTER1 中。

在不使用存储器抽象的情况下运行多个程序

即使没有存储器抽象,同时运行多个程序也是可能的。操作系统只需要把当前内存中所有内容保存到磁盘文件中,然后把下一个程序读人到内存中再运行即可。只要在某一个时间内存中只有一个程序,那么就不会发生冲突。

一种存储器抽象:地址空间

把物理地址暴露给进程会带来下面几个严重问题。

第一,如果用户程序可以寻址内存的每个字节,它们就可以很容易地(故意地或偶然地)破坏操作系统,从而使系统慢慢地停止运行(除非使用特殊的硬件进行保护,如 IBM 360 的锁键模式)。即使在只有一个用户进程运行的情况下,这个问题也是存在的。

第二,使用这种模型,想要同时运行(如果只有一个 CPU 就轮流执行)多个程序是很困难的。在个人计算机上,同时打开几个程序是很常见的(一个文字处理器,一个邮件程序,一个网络浏览器),其中一个当前正在工作,其余的在按下鼠标的时候才会被激活。在系统中没有对物理内存的抽象的情况下,很难实现上述情景,因此,我们需要其他办法。

地址空间的概念

要使多个应用程序同时处于内存中并且不互相影响,需要解决两个问题:保护和重定位。

一个更好的办法是创造一个新的存储器抽象:地址空间。就像进程的概念创造了一类抽象的 CPU 以运行程序一样,地址空间为程序创造了一种抽象的内存。地址空间是一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的地址空间,并且这个地址空间独立于其他进程的地址空间(除了在一些特殊情况下进程需要共享它们的地址空间外)。

基址寄存器与界限寄存器

这个简单的解决办法是使用动态重定位,简单地把每个进程的地址空间映射到物理内存的不同部分。

使用基址寄存器和界限寄存器重定位的缺点是,每次访问内存都需要进行加法和比较运算。比较运算可以做得很快,但是加法运算由于进位传递时间的问题,在没有使用特殊电路的情况下会显得很慢。

交换技术

如果计算机物理内存足够大,可以保存所有进程,那么之前提及的所有方案都或多或少是可行的。但实际上,所有进程所需的 RAM 数量总和通常要远远超出存储器能够支持的范围。

有两种处理内存超载的通用方法。最简单的策略是交换(swapping)技术,即把一个进程完整调入内存,使该进程运行一段时间,然后把它存回磁盘。空闲进程主要存储在磁盘上,所以当它们不运行时就不会占用内存(尽管其中的一些进程会周期性地被唤醒以完成相关工作,然后就又进入睡眠状态)。另一种策略是虚拟内存(virtual memory),该策略甚至能使程序在只有一部分被调人内存的情况下运行。

交换系统的操作如图 3-4 所示。开始时内存中只有进程 A。之后创建进程 B 和 C 或者从磁盘将它们换入内存。图 3-4 d 显示 A 被交换到磁盘。然后 D 被调入,B 被调出,最后 A 再次被调入。由于 A 的位置发生变化,所以在它换人的时候通过软件或者在程序运行期间(多数是这种情况)通过硬件对其地址进行重定位。例如,基址寄存器和界限寄存器就适用于这种情况。

交换在内存中产生了多个空闲区(hole,也称为空洞),通过把所有的进程尽可能向下移动,有可能将这些小的空闲区合成-大块。该技术称为内存紧缩(memory compaction)。通常不进行这个操作,因为它要耗费大量的 CPU 时间。

有一个问题值得注意,即当进程被创建或换入时应该为它分配多大的内存。若进程创建时其大小是固定的并且不再改变,则分配很简单,操作系统准确地按其需要的大小进行分配,不多也不少。

但是如果进程的数据段可以增长,例如,很多程序设计语言都允许从堆中动态地分配内存,那么当进程空间试图增长时,就会出现问题。若进程与一个空闲区相邻,那么可把该空闲区分配给进程供其增大。另一方面,若进程相邻的是另一个进程,那么要么把需要增长的进程移到内存中一个足够大的区域中去,要么把一个或多个进程交换出去,以便生成一个足够大的空闲区。若一个进程在内存中不能增长,而且磁盘上的交换区也已满了,那么这个进程只有挂起直到一些空间空闲(或者可以结束该进程)。

如果大部分进程在运行时都要增长,为了减少因内存区域不够而引|起的进程交换和移动所产生的开销,一种可用的方法是,当换入或移动进程时为它分配一些额外的内存。然而,当进程被换出到磁盘上时,应该只交换进程实际上使用的内存中的内容,将额外的内存交换出去是一种浪费。

空闲内存管理

在动态分配内存时,操作系统必须对其进行管理。一般而言,有两种方法跟踪内存使用情况:位图和空闲区链表。

1、使用位图的存储管理

使用位图方法时,内存可能被划分成小到几个字或大到几千字节的分配单元。每个分配单元对应于位图中的一位,0 表示空闲,1 表示占用(或者相反)。一块内存区和其对应的位图如图 3-6 所示。

分配单元的大小是一个重要的设计因素。分配单元越小,位图越大。然而即使只有 4 个字节大小的 分配单元,32位的内存也只需要位图中的1位。32n位的内存需要n位的位图,所以位图只占用了1/32的内存。若选择比较大的分配单元,则位图更小。但若进程的大小不是分配单元的整数倍,那么在最后一个分配单元中就会有一定数量的内存被浪费了。

因为内存的大小和分配单元的大小决定了位图的大小,所以它提供了一种简单的利用一块固定大小的内存区就能对内存使用情况进行记录的方法。这种方法的主要问题是,在决定把一个占 k 个分配单元的进程调人内存时,存储管理器必须搜索位图,在位图中找出有 k 个连续 0 的串。查找位图中指定长度的连续 0 串是耗时的操作(因为在位图中该串可能跨越字的边界),这是位图的缺点

2、使用空闲链表

另一种记录内存使用情况的方法是,维护一个记录已分配内存段和空闲内存段的链表。其中链表中的一个结点或者包含一个进程,或者是两个进程间的一块空闲区。可用图 3-6 c 所示的段链表来表示图 3- 6 a 所示的内存布局。链表中的每一个结点都包含以下域:空闲区(H)或进程(P)的指示标志、起始地址、长度和指向下一结点的指针。

进程表中表示终止进程的结点中通常含有指向对应于其段链表结点的指针,因此段链表使用双向链表可能要比图 3-6 c 所示的单向链表更方便。这样的结构更易于找到上一个结点,并检查是否可以合并。

当按照地址顺序在链表中存放进程和空闲区时,有几种算法可以用来为创建的进程(或从磁盘换人的已存在的进程)分配内存:

  • 首次适配(first fit)

  • 下次适配 (next fit)

  • 最佳适配(best fit)

  • 最差适配(worst fit)

如果为进程和空闲区维护各自独立的链表,那么这四个算法的速度都能得到提高。这样就能集中精力只检查空闲区而不是进程。但这种分配速度的提高的一个不可避免的代价就是增加复杂度和内存释放速度变慢,因为必须将一个回收的段从进程链表中删除并插入空闲链表。

如果进程和空闲区使用不同的链表,则可以按照大小对空闲区链表排序,以便提高最佳适配算法的速度。在使用最佳适配算法搜索由小到大排列的空闲区链表时,只要找到一个合适的空闲区,则这个空闲区就是能容纳这个作业的最小的空闲区,因此是最佳适配。因为空闲区链表以单链表形式组织,所以不需要进一步搜索。空闲区链表按大小排序时,首次适配算法与最佳适配算法一样快,而下次适配算法在这里则毫无意义。

  • 快速适配(quick fit)

快速适配算法寻找一个指定大小的空闲区是十分快速的,但它和所有将空闲区按大小排序的方案一样,都有一个共同的缺点,即在一个进程终止或被换出时,寻找它的相邻块并查看是否可以合并的过程是非常费时的。如果不进行合并,内存将会很快分裂出大量的进程无法利用的小空闲区。

虚拟内存

尽管基址寄存器和界限寄存器可以用于创建地址空间的抽象,还有另一个问题需要解决:管理软件的膨胀(bloatware)。虽然存储器容量增长快速,但是软件大小的增长更快。从而导致,需要运行的程序往往达到内存无法容纳。

虚拟内存(virtual memory)的基本思想是:每个程序拥有自己的地址空间,这个空间被分割成多个块,每一块称作一页或页面(page)。每一页有连续的地址范围。这些页被映射到物理内存,但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时,由硬件立刻执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时,由操作系统负责将缺失的部分装人物理内存并重新执行失败的指令。

从某个角度来讲,虚拟内存是对基址寄存器和界限寄存器的一种综合。虚拟内存很适合在多道程序设计系统中使用,许多程序的片段同时保存在内存中。当一个程序等待它的一部分读入内存时,可以把 CPU 交给另一个进程使用。

分页

大部分虚拟内存系统中都使用种称为分页(paging)的技术,我们现在就介绍这一技术。在任何一台计算机上,程序引用了一组内存地址。当程序执行指令

MOV REG, 1000 

时,它把地址为 1000 的内存单元的内容复制到 REG 中(或者相反,这取决于计算机的型号)。地址可以通过索引、基址寄存器、段寄存器或其他方式产生。

由程序产生的这些地址称为虚拟地址(virtual address),它们构成了一个虚拟地址空间(virtual address space)。在没有虚拟内存的计算机上,系统直接将虚拟地址送到内存总线上,读写操作使用具有同样地址的物理内存字,而在使用虚拟内存的情况下,虚拟地址不是被直接送到内存总线上,而是被送到内存管理单元(Memory Management Unit, MMU), MMU 把虚拟地址映射为物理内存地址,如图 3-8 所示。

图 3-9 所示的简单例子说明了这种映射是如何工作的。在这个例子中,有一台可以产生 16 位地址的计算机,地址范围从 0 到 64 K-1, 且这些地址是虚拟地址。然而,这台计算机只有 32 KB 的物理内存,因此,虽然可以编写 64 KB 的程序,但它们却不能被完全调入内存运行。在磁盘上必须有一个最多 64 KB 的程序核心映像的完整副本,以保证程序片段在需要时能被调人内存。

虚拟地址空间按照固定大小划分成被称为页面(page)的若干单元。在物理内存中对应的单元称为页框(page frame)。页面和页框的大小通常是一样的,在本例中是 4 KB,但实际系统中的页面大小从512字节到1GB。

在引用了虚拟页面时,MMU 注意到该页面没有被映射,于是使 CPU 陷人到操作系统,这个陷阱称为缺页中断缺页错误(page fault)。操作系统找到一个很少使用的页框且把它的内容写人磁盘(如果它不在磁盘上)。随后把需要访问的页面读到刚才回收的页框中,修改映射关系,然后重新启动引起陷阱的指令。

页表

作为一种最简单的实现,虚拟地址到物理地址的映射可以概括如下:虚拟地址被分成虚拟页号(高位部分)和偏移量(低位部分)两部分。例如,对于 16 位地址和 4 KB 的页面大小,高 4 位可以指定 16 个虚拟页面中的一页,而低 12 位接着确定了所选页面中的字节偏移量(0~4095)。但是使用 3 或者 5 或者其他位数拆分虚拟地址也是可行的。不同的划分对应不同的页面大小。

虚拟页号可用作页表的索引,以找到该虚拟页面对应的页表项。由页表项可以找到页框号(如果有的话)。然后把页框号拼接到偏移量的高位端,以替换掉虚拟页号,形成送往内存的物理地址。

页表的目的是把虚拟页面映射为页框。从数学角度说,页表是一个函数,它的参数是虚拟页号,结果是物理页框号。通过这个函数可以把虚拟地址中的虚拟页面域替换成页框域,从而形成物理地址。

虚拟内存本质上是用来创造一个新的抽象概念—地址空间,这个概念是对物理内存的抽象,类似于进程是对物理处理器(CPU)的抽象。虚拟内存的实现,是将虚拟地址空间分解成页,并将每一页映射到物理内存的某个页框或者(暂时)解除映射。

加速分页过程

在任何分页系统中,都需要考虑两个主要问题:

  • 虚拟地址到物理地址的映射必须非常快。
  • 如果虚拟地址空间很大,页表也会很大。

转换检测缓冲区

在加速分页的问题上,多年以来,计算机的设计者已经意识到了这个问题,并找到了一种解决方案。这种解决方案的建立基于这样一种观察:大多数程序总是对少量的页面进行多次的访问,而不是相反。因此,只有很少的页表项会被反复读取,而其他的页表项很少被访问。不 001

上面提到的解决方案是为计算机设置一个小型的硬件设备,将虚拟地址直接映射到物理地址,而不必再访问页表。这种设备称为转换检测缓冲区(Translation Lookaside Buffer, TLB),有时又称为相联存储器(associate memory)或快表,如图 3-12 所示。

软件TLB管理

许多现代的 RISC 机器,包括 SPARC、MIPS 以及(现在废弃的)HPPA,几乎所有的页面管理都是在软件中实现的。在这些机器上,TLB 表项被操作系统显式地装载。当发生 TLB 访问失效时,不再是由 MMU 到页表中查找并取出需要的页表项,而是生成一个 TLB 失效并将问题交给操作系统解决。系统必须先找到该页面,然后从 TLB 中删除一个项,接着装载一个新的项,最后再执行先前出错的指令。当然,所有这一切都必须在有限的几条指令中完成,因为 TLB 失效比缺页中断发生得更加频繁。

无论是用硬件还是用软件来处理 TLB 失效,常见方法都是找到页表并执行索引操作以定位将要访问的页面。用软件做这样的搜索的问题是,页表可能不在 TLB 中,这就会导致处理过程中的额外的 TLB 失效。可以通过在内存中的固定位置维护一个大的(如 4 KB) TLB 表项的软件高速缓存(该高速缓存的页面一直保存在 TLB 中)来减少 TLB 失效。通过首先检查软件高速缓存,操作系统能够实质性地减少 TLB 失效。

当使用软件 TLB 管理时,一个基本要求是要理解两种不同的 TLB 失效的区别在哪里。当一个页面访问在内存中而不在 TLB 中时,将产生软失效(soft miss)。那么此时所要做的就是更新一下 TLB,不需要 产生磁盘I/O。典型的处理需要10~20个机器指令并花费几纳秒完成操作。相反,当页面本身不在内存中(当然也不在 TLB 中)时,将产生硬失效。此刻需要一次磁盘存取以装入该页面,这个过程大概需要几毫秒。硬失效的处理时间往往是软失效的百万倍。在页表结构中查找相应的映射被称为页表遍历。

针对大内存的页表

在原有的内存页表的方案之上,引入 TLB 可以加快虚拟地址到物理地址的转换。不过这不是唯一需要解决的问题。另一个问题是怎样处理巨大的虚拟地址空间。下面将讨论两种解决方法。

多级页表

第一种方法是采用多级页表。一个简单的例子如图 3-13 所示。在图 3-13 a 中,32 位的虚拟地址被划分为 10 位的 PT1 域、10 位的 PT2 域和 12 位的 Offset(偏移量)域。

引入多级页表的原因是避免把全部页表一直保存在内存中。特别是那些从不需要的页表就不应该保留。比如一个需要 12 MB 内存的进程,其最底端是 4 MB 的程序正文段,后面是 4 MB 的数据段,顶端是 4 MB 的堆栈段,在数据段上方和堆栈段下方之间是大量根本没有使用的空闲区。

图 3-13 所示的二级页表可扩充为三级、四级或更多级。级数越多,灵活性就越大。

高性能奔腾处理器推出了另一种寻址实现形式:页目录指针表。此外,它每一级的页表项由 32 位扩展到了 64 位,这样处理器就能寻址到 4 GB 以外的地址空间。

倒排页表

针对页式调度层级不断增长的另一种解决方案是倒排页表(inverted page table),首先采用这种解决方案的处理器有 PowerPC、UltraSPARC 和 Itanium(有时也被称作 Itanic,这款处理器并没有达到 Intel 所期望的目标)。在这种设计中,实际内存中的每个页框对应一个表项,而不是每个虚拟页面对应一个表项。例如,对于 64 位虚拟地址,4 KB 的页,4 GB 的 RAM,一个倒排页表仅需要 1048 576 个表项。表项记录了哪一个(进程,虚拟页面)对定位于该页框。

虽然倒排页表节省了大量的空间(至少当虚拟地址空间比物理内存大得多的时候是这样的),但它也有严重的不足:从虚拟地址到物理地址的转换会变得很困难。当进程 n 访问虚拟页面 p 时,硬件不再能通过把 p 当作指向页表的一个索引来查找物理页框。取而代之的是,它必须搜索整个倒排页表来查找某一个表项(n, p)。此外,该搜索必须对每一个内存访问操作都要执行一~次,而不仅仅是在发生缺页中断时执行。每次内存访问操作都要查找一个 256 K 的表不是一种使机器快速运行的方法。

走出这种两难局面的办法是使用 TLB。如果 TLB 能够记录所有频繁使用的页面,地址转换就可能变得像通常的页表一样快。但是,当发生 TLB 失效时,需要用软件搜索整个倒排页表。实现该搜索的一个可行的方法是建立一张散列表,用虚拟地址来散列。当前所有在内存中的具有相同散列值的虚拟页面被链接在一起,如图 3- 14 所示。如果散列表中的槽数与机器中物理页面数-样多,那么散列表的冲突链的平均长度将会是 1 个表项的长度,这将会大大提高映射速度。一旦页框号被找到,新的(虚拟页号,物理页框号)对就会被装载到 TLB 中。

页面置换算法

当发生缺页中断时,操作系统必须在内存中选择一个页面将其换出内存,以便为即将调入的页面腾出空间。如果要换出的页面在内存驻留期间已经被修改过,就必须把它写回磁盘以更新该页面在磁盘上的副本;如果该页面没有被修改过(如一个包含程序正文的页面),那么它在磁盘上的副本已经是最新的,不需要回写。直接用调入的页面覆盖被淘汰的页面就可以了。

当发生缺页中断时,虽然可以随机地选择一个页面来置换,但是如果每次都选择不常使用的页面会提升系统的性能。如果一个被频繁使用的页面被置换出内存,很可能它在很短时间内又要被调入内存,这会带来不必要的开销。人们已经从理论和实践两个方面对页面置换算法进行了深人的研究。下面我们将介绍几个最重要的算法。

最优页面置换算法

很容易就可以描述出最好的页面置换算法,虽然此算法不可能实现。该算法是这样工作的:在缺页中断发生时,有些页面在内存中,其中有一个页面(包含紧接着的下一条指令的那个页面)将很快被访问,其他页面则可能要到 10、100 或 1000 条指令后才会被访问,每个页面都可以用在该页面首次被访问前所要执行的指令数作为标记。

最优页面置换算法规定应该置换标记最大的页面。如果一个页面在 800 万条指令内不会被使用,另外一个页面在 600 万条指令内不会被使用,则置换前一个页面,从而把因需要调入这个页面而发生的缺页中断推迟到将来,越久越好。计算机也像人一样,希望把不愉快的事情尽可能地往后拖延。

这个算法唯一的问题就是它是无法实现的。当缺页中断发生时,操作系统无法知道各个页面下一次将在什么时候被访问。(在最短作业优先调度算法中,我们曾遇到同样的情况,即系统如何知道哪个作业是最短的呢?)当然,通过首先在仿真程序上运行程序,跟踪所有页面的访问情况,然后在第一次运行时利用第一次运行时收集的信息是可以实现最优页面置换算法的。

用这种方式,可以通过最优页面置换算法对其他可实现算法的性能进行比较。如果操作系统达到的页面置换性能只比最优算法差 1%,那么即使花费大量的精力来寻找更好的算法最多也只能换来 1%的性能提高。

最近未使用页面置换算法

NRU (Not Recently Used,最近未使用)算法随机地从类编号最小的非空类中挑选一个页面淘汰。这个算法隐含的意思是,在最近一个时钟滴答中(典型的时间是大约 20 ms)淘汰一个没有被访问的已修改页面要比淘汰一个被频繁使用的“千净”页面好。NRU 的主要优点是易于理解和能够有效地被实现,虽然它的性能不是最好的,但是已经够用了。

先进先出页面置换算法

另一种开销较小的页面置换算法是 FIFO (First-In First-Out,先进先出)算法。由操作系统维护一个所有当前在内存中的页面的链表,最新进入的页面放在表尾,最早进入的页面放在表头。当发生缺页中断时,淘汰表头的页面并把新调人的页面加到表尾。当 FIFO 用在超市时,可能会淘汰剃须膏,但也可能淘汰面粉、盐或黄油这一类常用商品。因此,当它应用在计算机上时也会引起同样的问题,由于这一原因,很少使用纯粹的 FIFO 算法。

第二次机会页面置换算法

FIFO 算法可能会把经常使用的页面置换出去,为了避免这一问题,对该算法做一个简单的修改:检查最老页面的 R 位。如果 R 位是 0,那么这个页面既老又没有被使用,可以立刻置换掉,如果是 1,就将 R 位清 0,并把该页面放到链表的尾端,修改它的装入时间使它就像刚装人的一样,然后继续搜索。

这一算法称为第二次机会(second chance)算法。

第二次机会算法就是寻找一个在最近的时钟间隔内没有被访问过的页面。如果所有的页面都被访问过了,该算法就简化为纯粹的 FIFO 算法。

时钟页面置换算法

很有必要。一个更好的办法是把所有的页面都保存在一个类似钟面的环形链表中,一个表针指向最老的页面。

当发生缺页中断时,算法首先检查表针指向的页面,如果它的 R 位是 0 就淘汰该页面,并把新的页面插人这个位置,然后把表针前移个位置;如果 R 位是 1 就清除 R 位并把表针前移一个位置。重复这个过程直到找到了一个 R 位为 0 的页面为止。了解了这个算法的工作方式,就明白为什么它被称为时钟(clock)算法了。

最近最少使用页面置换算法

对最优算法的一个很好的近似是基于这样的观察:在前面几条指令中频繁使用的页面很可能在后面的几条指令中被使用。反过来说,已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。这个思想提示了一个可实现的算法:在缺页中断发生时,置换未使用时间最长的页面。这个策略称为 LRU (Least Recently Used,最近最少使用)页面置换算法。

虽然 LRU 在理论上是可以实现的,但代价很高。为了完全实现 LRU,需要在内存中维护一个所有页面的链表,最近最多使用的页面在表头,最近最少使用的页面在表尾。困难的是在每次访问内存时都必须要更新整个链表。在链表中找到一个页面,删除它,然后把它移动到表头是一个非常费时的操作,即使使用硬件实现也一样费时(假设有这样的硬件)。

然而,还是有一些使用特殊硬件实现 LRU 的方法。首先考虑一个最简单的方法,这个方法要求硬件有一个 64 位计数器 C,它在每条指令执行完后自动加 1,每个页表项必须有一个足够容纳这个计数器值的域。在每次访问内存后,将当前的 C 值保存到被访问页面的页表项中。一旦发生缺页中断,操作系统就检查所有页表项中计数器的值,找到值最小的一个页面,这个页面就是最近最少使用的页面。

用软件模拟LRU

前面一种 LRU 算法虽然在理论上是可以实现的,但只有非常少的计算机拥有这种硬件。因此,需要一个能用软件实现的解决方案。一种可能的方案称为 NFU (Not Frequently Used,最不常用)算法。该算法将每个页面与一个软件计数器相关联,计数器的初值为 0。每次时钟中断时,由操作系统扫描内存中所有的页面,将每个页面的 R 位(它的值是 0 或 1) 加到它的计数器上。这个计数器大体上跟踪了各个页面被访问的频繁程度。发生缺页中断时,则置换计数器值最小的页面。

NFU 的主要问题是它从来不忘记任何事情。比如,在一个多次(扫描)编译器中,在第一次扫描中被频繁使用的页面在程序进入第二:次扫描时,其计数器的值可能仍然很高。实际上,如果第一次扫描的执行时间恰好是各次扫描中最长的,含有以后各次扫描代码的页面的计数器可能总是比含有第一次扫描代码的页面的计数器小,结果是操作系统将置换有用的页面而不是不再使用的页面。

幸运的是,只需对 NFU 做一个小小的修改就能使它很好地模拟 LRU。其修改分为两部分:首先,在 R 位被加进之前先将计数器右移一位;其次,将 R 位加到计数器最左端的位而不是最右端的位。

修改以后的算法称为老化(aging)算法,图 3-17 解释了它是如何工作的。假设在第一个时钟滴答后,页面 0 ~ 5 的 R 位值分别是 1、0、1、0、1、1(页面 0 为 1,页面 1 为 0,页面 2 为 1,以此类推)。换句话说,在时钟滴答 0 到时钟滴答 1 期间,访问了页 0、2、4、5,它们的 R 位设置为 1,而其他页面的 R 位仍然是 0。对应的 6 个计数器在经过移位并把 R 位插入其左端后的值如图 3-17 a 所示。图中后面的 4 列是在下 4 个时钟滴答后的 6 个计数器的值。

工作集页面置换算法

在单纯的分页系统里,刚启动进程时,在内存中并没有页面。在 CPU 试图取第一条指令时就会产生一次缺页中断,使操作系统装人含有第一条指令的页面。其他由访问全局数据和堆栈弓|起的缺页中断通常会紧接着发生。一段时间以后,进程需要的大部分页面都已经在内存了,进程开始在较少缺页中断的情况下运行。这个策略称为请求调页(demand paging),因为页面是在需要时被调入的,而不是预先装人。

一个进程当前正在使用的页面的集合称为它的工作集(Denning, 1968 a; Denning, 1980)。如果整个工作集都被装人到了内存中,那么进程在运行到下一运行阶段(例如,编译器的下一遍扫描)之前,不会产生很多缺页中断。若内存太小而无法容纳下整个工作集,那么进程的运行过程中会产生大量的缺页中断,导致运行速度也会变得很缓慢,因为通常只需要几个纳秒就能执行完一条指令,而通常需要十毫秒才能从磁盘上读入一个页面。如果一个程序每 10 ms 只能执行一到两条指令,那么它将会需要很长时间才能运行完。若每执行几条指令程序就发生一次缺页中断,那么就称这个程序发生了颠簸(Denning, 1968 b)。

所以不少分页系统都会设法跟踪进程的工作集,以确保在让进程运行以前,它的工作集就已在内存中了。该方法称为工作集模型(Denning, 1970),其目的在于大大减少缺页中断率。在进程运行前预先装入其工作集页面也称为预先调页(prepaging)。请注意工作集是随着时间变化的。

工作集时钟页面置换算法

当缺页中断发生后,需要扫描整个页表才能确定被淘汰的页面,因此基本工作集算法是比较费时的。有一种改进的算法,它基于时钟算法,并且使用了工作集信息,称为 WSClock(工作集时钟)算法(Carr 和 Hennessey, 1981)。由于它实现简单,性能较好,所以在实际工作中得到了广泛应用。

与时钟算法一样,所需的数据结构是一个以页框为元素的循环表。最初,该表是空的。当装入第一个页面后,把它加到该表中。随着更多的页面的加入,它们形成一个环。每个表项包含来自基本工作集算法的上次使用时间,以及 R 位(已标明)和 M 位(未标明)。

页面置换算法小结

我们已经考察了多种页面置换算法,本节将对这些算法进行总结。已经讨论过的算法在图 3-21 中列出。最优算法在当前页面中置换最后要访问到的页面。不幸的是,没有办法来判定哪个页面是最后一个要访问的,因此实际上该算法不能使用。然而,它可以作为衡量其他算法的基准。

NRU 算法根据 R 位和 M 位的状态把页面分为四类。从编号最小的类中随机选择一个页面置换。该算法易于实现,但是性能不是很好,还存在更好的算法。

第二次机会算法是对 FIFO 算法的改进,它在移出页面前先检查该页面是否正在被使用。如果该页面正在被使用,就保留该页面。这个改进大大提高了性能。时钟算法是第二次机会算法的另一种实现。它具有相同的性能特征,而且只需要更少的执行时间。

LRU 算法是一种非常优秀的算法,但是只能通过特定的硬件来实现。如果机器中没有该硬件,那么也无法使用该算法。NFU 是一种近似于 LRU 的算法,它的性能不是非常好,然而,老化算法更近似于 LRU 并且可以更有效地实现,是一个很好的选择。

最后两种算法都使用了工作集。工作集算法有合理的性能,但它的实现开销较大。工作集时钟算法是它的一种变体,不仅具有良好的性能,并且还能高效地实现。

总之,最好的两种算法是老化算法和工作集时钟算法,它们分别基于 LRU 和工作集。它们都具有良好的页面调度性能,可以有效地实现。也存在其他一-些算法,但在实际应用中,这两种算法可能是最重要的。

分页系统中的设计问题

局部分配策略与全局分配策略

局部算法可以有效地为每个进程分配固定的内存片段。全局算法在可运行进程之间动态地分配页框,因此分配给各个进程的页框数是随时间变化的。

全局算法在通常情况下工作得比局部算法好,当工作集的大小随进程运行时间发生变化时这种现象更加明显。若使用局部算法,即使有大量的空闲页框存在,工作集的增长也会导致颠簸。如果工作集缩小了,局部算法又会浪费内存。在使用全局算法时,系统必须不停地确定应该给每个进程分配多少页框。一种方法是监测工作集的大小,工作集大小由“老化”位指出,但这个方法并不能防止颠簸。因为工作集的大小可能在几微秒内就会发生改变,而老化位却要经历一定的时钟滴答数才会发生变化。

负载控制

即使是使用最优页面置换算法并对进程采用理想的全局页框分配,系统也可能会发生颠簸。事实上,一旦所有进程的组合工作集超出了内存容量,就可能发生颠簸。该现象的症状之一就是如 PFF 算法所指出的,一些进程需要更多的内存,但是没有进程需要更少的内存。在这种情况下,没有方法能够在不影响其他进程的情况下满足那些需要更多内存的进程的需要。唯一现实的解决方案就是暂时从内存中去掉一-些进程。

减少竞争内存的进程数的一个好方法是将一部分进程交换到磁盘,并释放他们所占有的所有页面。例如,一个进程可以被交换到磁盘,而它的页框可以被其他处于颠簸状态的进程分享。如果颠簸停止,系统就能够这样运行一-段时间。如果颠簸没有结束,需要继续将其他进程交换出去,直到颠簸结束。因此,即使是使用分页,交换也是需要的,只是现在交换是用来减少对内存潜在的需求,而不是收回它的页面。

将进程交换出去以减轻内存需求的压力是借用了两级调度的思想,在此过程中一些进程被放到磁盘,此时用一个短期的调度程序来调度剩余的进程。很明显,这两种思路可以被组合起来,将恰好足够的进程交换出去以获取可接受的缺页中断率。- 些进程被周期性地从磁盘调入,而其他一些则被周期性地交换到磁盘。

不过,另一个需要考虑的因素是多道程序设计的道数。当内存中的进程数过低的时候,CPU 可能在很长的时间内处于空闲状态。考虑到该因素,在决定交换出哪个进程时不光要考虑进程大小和分页率, 还要考虑它的特性(如它究竟是CPU密集型还是I/O密集型)以及其他进程的特性。

页面大小

页面大小是操作系统可以选择的一个参数。例如,即使硬件设计只支持 4096 字节的页面,操作系统也可以很容易通过总是为页面对 0 和 1、2 和 3、4 和 5 等分配两个连续的 8192 字节的页框,而将其作为 8 KB 的页面。

要确定最佳的页面大小需要在几个互相矛盾的因素之间进行权衡。从结果看,不存在全局最优。首先,有两个因素可以作为选择小页面的理由。随便选择一个正文段、数据段或堆栈段很可能不会恰好装满整数个页面,平均的情况下,最后一个页面中有一半是空的。多余的空间就被浪费掉了,这种浪费称为内部碎片 (internal fragmentation)。在内存中有n个段、页面大小为p字节时,会有np/2 字节被内部碎片浪费。从这方面考虑,使用小页面更好。

选择小页面还有一个明显的好处,考虑一个程序,它分成 8 个阶段顺序执行,每阶段需要 4 KB 内存。如果页面大小是 32 KB,那就必须始终给程序分配 32 KB 内存。如果页面大小是 16 KB,它就只需要 16 KB。如果页面大小是 4 KB 或更小,那么在任何时刻它只需要 4 KB 内存。总的来说,大尺寸页面比小尺寸页面浪费了更多内存。

另一方面,页面小意味着程序需要更多的页面,这又意味着需要更大的页表。一个 32 KB 的程序只需要 4 个 8 KB 的页面,却需要 64 个 512 字节的页面。内存与磁盘之间的传输般是一次一页,传输中的大部分时间都花在了寻道和旋转延迟上,所以传输一个小页面所用的时间和传输一个大页面基本上是相同的。装入 64 个 512 字节的页面可能需要 64 x 10 ms,而装入 4 个 8 K B 的页面可能只需要 4 x 12 ms。

此外,小页面能够更充分地利用 TLB 空间。假设程序使用的内存为 1 MB,工作单元为 64 KB。若使用 4 KB 的页,则程序将至少占用 TLB 中的 16 个表项;而使用 2 MB 的页时,1 个 TLB 表项就足够了(理论上,你还可以将数据和指令分离开来)。由于 TLB 表项相对稀缺,且对于性能而言至关重要,因此在条件允许的情况下使用大页面是值得的。为了进行必要的平衡,操作系统有时会为系统中的不同部分使用不同的页面大小。例如,内核使用大页面,而用户进程则使用小页面。

在某些机器上,每次 CPU 从一个进程切换到另一个进程时都必须把新进程的页表装人硬件寄存器中。这样,页面越小意味着装入页面寄存器花费的时间就会越长,而且页表占用的空间也会随着页面的减小而增大。

商用计算机使用的页面大小一般在 512 B 到 64 KB 之间,以前的典型值是 1 KB,而现在更常见的页面大小是 4 KB 或 8 KB。

分离的指令空间和数据空间

为指令(程序正文)和数据设置分离的地址空间,分别称为 1 空间和 D 空间。每个地址空间都从 0 开始到某个最大值,比较有代表性的是 216-1 或者 232-1。链接器必须知道何时使用分离的 I 空间和 D 空间,因为当使用它们时,数据被重定位到虚拟地址 0,而不是在程序之后开始。

在使用这种设计的计算机中,两种地址空间都可以进行分页,而且互相独立。它们分别有自己的页表,分别完成虚拟页面到物理页框的映射。当硬件进行取指令操作时,它知道要使用 I 空间和 I 空间页表。类似地,对数据的访问必须通过 D 空间页表。除了这一区别,拥有分离的 I 空间和 D 空间不会引入任何复杂的设计,而且它还能使可用的地址空间加倍。

尽管现在的地址空间已经很大,但其大小曾是一个很严重的问题。即便是在今天把地址空间划分成 I 和 D 层也很常见。现在的地址空间经常被划分到一级缓存里,而不再分给常规的地址空间。毕竟在一级缓存中,内存也是个稀缺品。

共享页面

在大型多道程序设计系统中,几个不同的用户同时运行同一个程序是很常见的。显然,避免内存中一个页面的两个副本,共享页面效率更高。这里存在一个问题,即并不是所有的页面都适合共享。特别地,那些只读的页面(诸如程序文本)可以共享,但是数据页面则不能共享。

共享库

可以使用其他的粒度取代单个页面来实现共享。如果一个程序被启动两次,大多数操作系统会自动共享所有的代码页面,而在内存中只保留一份代码页面的副本。代码页面总是只读的,因此这样做不存在任何问题。依赖于不同的操作系统,每个进程都拥有一份数据页面的私有副本,或者这些数据页面被共享并且被标记为只读。如果任何一个进程对一个数据页面进行修改,系统就会为此进程复制这个数据页面的一个副本,并且这个副本是此进程私有的,也就是说会执行“写时复制”。

现代操作系统中,有很多大型库被众多进程使用,例如,处理浏览文件以便打开文件的对话框的库和多个图形库。把所有的这些库静态地与磁盘上的每一个可执行程序绑定在一起,将会使它们变得更加庞大。

一个更加通用的技术是使用共享库(在 Windows 中称作 DLL 或动态链接库)。为了清楚地表达共享库的思想,首先考虑一下传统的链接。当链接一个程序时,要在链接器的命令中指定一个或多个目标文件,可能还包括一些库文件。以下面的 UNIX 命令为例:

ld *.o -lc -lm

这个命令会链接当前目录下的所有的。0(目标)文件,并扫描两个库:/usr/lib/libc.a和/usr/lib/ibm.a。 任何在目标文件中被调用了但是没有被定义的函数(比如,printf),都被称作未定义外部函数(undefined externals)。链接器会在库中寻找这些未定义外部函数。如果找到了,则将它们加载到可执行=进制文件中。任何被这些未定义外部函数调用了但是不存在的函数也会成为未定义外部函数。例如,printf 需要 write,如果 write 还没有被加载进来,链接器就会查找 write 并在找到后把它加载进来。当链接器完成任务后,一个可执行二:进制文件被写到磁盘,其中包括了所需的全部函数。在库中定义但是没有被调用的函数则不会被加载进去。当程序被装入内存执行时,它需要的所有函数都已经谁备就绪了。

依赖于系统和配置信息,共享库或者和程序一起被装载,或者在其所包含函数第一次被调用时被装载。当然,如果其他程序已经装载了某个共享库,就没有必要再次装载它了一一这正是关键所在。值得注意的是,当一个共享库被装载和使用时,整个库并不是被一次性地读入内存。而是根据需要,以页面为单位装载的,因此没有被调用到的函数是不会被装载到内存中的。

除了可以使可执行文件更小、节省内存空间之外,共享库还有一个优点:如果共享库中的一个函数因为修正一个 bug 被更新了,那么并不需要重新编译调用了这个函数的程序。旧的二进制文件依然可以正常工作。这个特性对于商业软件来说尤为重要,因为商业软件的源码不会分发给客户。例如,如果微软发现并修复了某个标准 DLL 中的安全错误,Windows 更新会下载新的 DLL 来替换原有文件,所有使用这个 DLL 的程序在下次启动时会自动使用这个新版本的 DLL。

内存映射文件

一种更为通用的机制—内存映射文件(memory -mapped file)的一个特例。这种机制的思想是:进程可以通过发起一个系统调用,将一个文件映射到其虚拟地址空间的一部分。在多数实现中,在映射共享的页面时不会实际读人页面的内容,而是在访问页面时才会被每次一-页地读入,磁盘文件则被当作后备存储。当进程退出或显式地解除文件映射时,所有被改动的页面会被写回到磁盘文件中。

内存映射文件提供了一种I/O的可选模型。可以把一个文件当作一个内存中的大字符数组来访问,而不用通过读写操作来访问这个文件。在一些情况下,程序员发现这个模型更加便利。

如果两个或两个以上的进程同时映射了同一个文件,它们就可以通过共享内存来通信。一个进程在共享内存上完成了写操作,此刻当另一个进程在映射到这个文件的虚拟地址空间上执行读操作时,它就可以立刻看到上一个进程写操作的结果。因此,这个机制提供了一个进程之间的高带宽通道,而且这种应用很普遍(甚至扩展到用来映射无名的临时文件)。很显然,如果内存映射文件可用,共享库就可以使用这个机制。

清除策略

如果发生缺页中断时系统中有大量的空闲页框,此时分页系统工作在最佳状态。如果每个页框都被占用,而且被修改过的话,再换入一个新页面时,旧页面应首先被写回磁盘。为保证有足够的空闲页框,很多分页系统有一个称为分页守护进程(paging daemon)的后台进程,它在大多数时候睡眠,但定期被唤醒以检查内存的状态。如果空闲页框过少,分页守护进程通过预定的页面置换算法选择页面换出内存。如果这些页面装入内存后被修改过,则将它们写回磁盘。

在任何情况下,页面中原先的内容都被记录下来。当需要使用一个已被淘汰的页面时,如果该页框还没有被覆盖,将其从空闲页框缓冲池中移出即可恢复该页面。保存一定数目的页框供给比使用所有内存并在需要时搜索一个页框有更好的性能。分页守护进程至少保证了所有的空闲页框是“干净”的,所以空闲页框在被分配时不必再急着写回磁盘。

一种实现清除策略的方法就是使用一个双指针时钟。前指针由分页守护进程控制。当它指向一个脏页面时,就把该页面写回磁盘,前指针向前移动。当它指向一个干净页面时,仅仅指针向前移动。后指针用于页面置换,就像在标准时钟算法中一样。现在,由于分页守护进程的工作,后指针命中干净页面的概率会增加。

虚拟内存接口

到现在为止,所有的讨论都假定虚拟内存对进程和程序员来说是透明的,也就是说,它们都可以在一台只有较少物理内存的计算机上看到很大的虚拟地址空间。对于不少系统而言这样做是对的,但对于一些高级系统而言,程序员可以对内存映射进行控制,并可以通过非常规的方法来增强程序的行为。这一节将简短地讨论一下这些问题。

允许程序员对内存映射进行控制的一个原因就是为了允许两个或者多个进程共享同一部分内存。如果程序员可以对内存区域进行命名,那么就有可能实现共享内存:通过让一个进程把一片内存区域的名称通知另一个进程,而使得第二个进程可以把这片区域映射到它的虚拟地址空间中去。通过两个进程(或者更多)共享同一部分页面,高带宽的共享就成为可能一一个进程往共享内存中写内容而另一个从中读出内容。De Bruijn (2011) 描述了通信信道这种复杂例子。

页面共享也可以用来实现高性能的消息传递系统。一般地,传递消息的时候,数据被从一个地址空间复制到另一个地址空间,开销很大。如果进程可以控制它们的页面映射,就可以这样来发送一条消息:发送进程清除那些包含消息的页面的映射,而接收进程把它们映射进来。这里只需要复制页面的名字,而不需要复制所有数据。

另外一种高级存储管理技术是分布式共享内存(Feeley 等人,1995; Li, 1986; Li 和 Hudak,1989; Zekauskas 等人,| 1994)。该方法允许网络上的多个进程共享一个页面集合,这些页面可能(而不是必要的)作为单个的线性共享地址空间。当一个进程访问当前还没有映射进来的页面时,就会产生缺页中断。在内核空间或者用户空间中的缺页中断处理程序就会对拥有该页面的机器进行定位,并向它发送一条消息,请求它清除该页面的映射,并通过网络发送出来。当页面到达时,就把它映射进来,并重新开始运行引起缺页中断的指令。

有关实现的问题

与分页有关的工作

操作系统要在下面的四段时间里做与分页相关的工作:进程创建时,进程执行时,缺页中断时和进程终止时。

缺页中断处理

缺页中断发生时的事件顺序如下:

1) 硬件陷人内核,在堆栈中保存程序计数器。大多数机器将当前指令的各种状态信息保存在特殊的 CPU 寄存器中。

2) 启动一个汇编代码例程保存通用寄存器和其他易失的信息,以免被操作系统破坏。这个例程将操作系统作为一个函数来调用。

3) 当操作系统发现一个缺页中断时,尝试发现需要哪个虚拟页面。通常一个硬件寄存器包含了这一信息,如果没有的话,操作系统必须检索程序计数器,取出这条指令,用软件分析这条指令,看看它在缺页中断时正在做什么。

4) 一旦知道了发生缺页中断的虚拟地址,操作系统检查这个地址是否有效,并检查存取与保护是否一致。如果不一致,向进程发出一个信号或杀掉该进程。如果地址有效且没有保护错误发生,系统则检查是否有空闲页框。如果没有空闲页框,执行页面置换算法寻找一个页面来淘汰。

5) 如果选择的页框“脏”了,安排该页写回磁盘,并发生一次上下文切换,挂起产生缺页中断的进程,让其他进程运行直至磁盘传输结束。无论如何,该页框被标记为忙,以免因为其他原因而被其他进程占用。

6) 一旦页框“干净”后(无论是立刻还是在写回磁盘后),操作系统查找所需页面在磁盘上的地址,通过磁盘操作将其装入。该页面正在被装入时,产生缺页中断的进程仍然被挂起,并且如果有其他可运行的用户进程,则选择另一个用户进程运行。

7) 当磁盘中断发生时,表明该页已经被装人,页表已经更新可以反映它的位置,页框也被标记为正常状态。

8) 恢复发生缺页中断指令以前的状态,程序计数器重新指向这条指令。

9) 调度引发缺页中断的进程,操作系统返回调用它的汇编语言例程。

10) 该例程恢复寄存器和其他状态信息,返回到用户空间继续执行,就好像缺页中断没有发生过一样。

指令备份

当程序访问不在内存中的页面时,引起缺页中断的指令会半途停止并引发操作系统的陷阱。在操作系统取出所需的页面后,它需要重新启动引起陷阱的指令。

在某些计算机上,CPU 的设计者们提供了一种解决方法,就是通过使用一个隐藏的内部寄存器。在每条指令执行之前,把程序计数器的内容复制到该寄存器。这些机器可能会有第二个寄存器,用来提供哪些寄存器已经自动增加或者自动减少以及增减的数量等信息。通过这些信息,操作系统可以消除引起缺页中断的指令所造成的所有影响,并使指令可以重新开始执行。如果该信息不可用,那么操作系统就要找出所发生的问题从而设法来修复它。看起来硬件设计者是不能解决这个问题了,于是他们就推给操作系统的设计者来解决这个问题。

锁定内存中的页面

如果分页算法是全局算法,包含I/O缓冲区的页面会有很小的机会(但不是没有)被选中换出内存。如果一个I/O设备正处在对该页面进行DMA传输的过程之中,将这个页面移出将会导致部分数据写人它 们所属的缓冲区中,而部分数据被写人到最新装人的页面中。一种解决方法是锁住正在做I/O操作的内 存中的页面以保证它不会被移出内存。锁住一个页面通常称为在内存中钉住(pinning)页面。另一种方法是在内核缓冲区中完成所有的 IO 操作,^然后再将数据复制到用户页面。

后备存储

在前面讨论过的页面置换算法中,我们已经知道了如何选择换出内存的页面。但是却没有讨论当页面被换出时会存放在磁盘上的哪个位置,现在我们讨论一下磁盘管理相关的问题。

在磁盘上分配页面空间的最简单的算法是在磁盘上设置特殊的交换分区,甚至从文件系统划分一块独立的磁盘(以平衡I/O负载)。大多数UNIX是这样处理的。在这个分区里没有普通的文件系统,这样就消除了将文件偏移转换成块地址的开销。取而代之的是,始终使用相应分区的起始块号。

当系统启动时,该交换分区为空,并在内存中以单独的项给出它的起始和大小。在最简单的情况下,当第一个进程启动时,留出与这个进程一样大的交换区块,剩余的为总空间减去这个交换分区。当新进程启动后,它们同样被分配与其核心映像同等大小的交换分区。进程结束后,会释放其磁盘上的交换区。交换分区以空闲块列表的形式组织。

与每个进程对应的是其交换区的磁盘地址,即进程映像所保存的地方。这一信息是记录在进程表里的。写回一个页面时,计算写回地址的过程很简单:将虚拟地址空间中页面的偏移量加到交换区的开始地址。但在进程启动前必须初始化交换区,一种方法是将整个进程映像复制到交换区,以便随时可将所需内容装人,另一种方法是将整个进程装入内存,并在需要时换出。

但这种简单模式有一个问题:进程在启动后可能增大,尽管程序正文通常是固定的,但数据有时会增长,堆栈也总是在随时增长。这样,最好为正文、数据和堆栈分别保留交换区,并且允许这些交换区在磁盘上多于一个块。

另一个极端的情况是事先什么也不分配,在页面换出时为其分配磁盘空间,并在换人时回收磁盘空间,这样内存中的进程不必固定于任何交换空间。其缺点是内存中每个页面都要记录相应的磁盘地址。换言之,每个进程都必须有一张表,记录每一个页面在磁盘上的位置。这两个方案如图 3-28 所示。

策略和机制分离

控制系统复杂度的一种重要方法就是把策略从机制中分离出来。通过使大多数存储管理器作为用户级进程运行,就可以把该原则应用到存储管理中。在 Mach (Young 等人,1987) 中首先应用了这种分离。下面的讨论是基于 Mach 的。
一个如何分离策略和机制的简单例子可以参见图 3-29。其中存储管理系统被分为三个部分:

1) 一个底层 MMU 处理程序。

2) 一个作为内核一部分的缺页中断处理程序。

3) 一个运行在用户空间中的外部页面调度程序。

这个实现方案没有给出放置页面置换算法的位置。把它放在外部页面调度程序中比较简单,但会有一些问题。这里有一条原则就是外部页面调度程序无权访问所有页面的 R 位和 M 位。这些二进制位在许多页面置换算法起重要作用。这样就需要有某种机制把该信息传递给外部页面调度程序,或者把页面置换算法放到内核中。在后一种情况下,缺页中断处理程序会告诉外部页面调度程序它所选择的要淘汰的页面并提供数据,方法是把数据映射到外部页面调度程序的地址空间中或者把它包含到一条消息中。两种方法中,外部页面调度程序都把数据写到磁盘上。

这种实现的主要优势是有更多的模块化代码和更好的适应性。主要缺点是由于多次交叉“用户一内核”边界引起的额外开销,以及系统模块间消息传递所造成的额外开销。现在看来,这一主题有很多争议,但是随着计算机越来越快,软件越来越复杂,从长远来看,对于大多数实现,为了获得更高的可靠性而牺牲- – 些性能也是可以接受的。

分段

到目前为止讨论的虚拟内存都是一-维的,虚拟地址从 0 到最大地址,一个地址接着另一个地址。对许多问题来说,有两个或多个独立的地址空间可能比只有一个要好得多。

机器上提供多个互相独立的称为(segment)的地址空间。每个段由一个从 0 到最大的线性地址序列构成。各个段的长度可以是 0 到某个允许的最大值之间的任何一个值。不同的段的长度可以不同,并且通常情况下也都不相同。段的长度在运行期间可以动态改变,比如,堆栈段段长度在数据被压入时会增长,在数据被弹出时又会减小。

因为每个段都构成了一个独立的地址空间,所以它们可以独立地增长或减小而不会影响到其他的段。如果一个在某个段中的堆栈需要更多的空间,它就可以立刻得到所需要的空间,因为它的地址空间中没有任何其他东西阻挡它增长。段当然有可能会被装满,但通常情况下段都很大,因此这种情况发生的可能性很小。要在这种分段或二维的存储器中指示一个地址,程序必须提供两部分地址,一个段号和一个段内地址。

需要强调的是,段是一个逻辑实体,程序员知道这一点并把它作为一个逻辑实体来使用。一个段可能包括一个过程、一个数组、一个堆栈、一组数值变量,但一般它不会同时包含多种不同类型的内容。

除了能简化对长度经常变动的数据结构的管理之外,分段存储管理还有其他一些优点。如果每个过程都位于一个独立的段中并且起始地址是 0,那么把单独编译好的过程链接起来的操作就可以得到很大的简化。当组成一个程序的所有过程都被编译和链接好以后,一个对段 n 中过程的调用将使用由两个部分组成的地址(n, 0) 来寻址到字 0(人口点)。

分段也有助于在几个进程之间共享过程和数据。这方面一个常见的例子就是共享库(shared library)。

纯分段的实现

分段和分页的实现本质上是不同的:页面是定长的而段不是。。在系统运行一段时间后内存被划分为许多块,一些块包含着段,一些则成了空闲区,这种现象称为棋盘形碎片或外部碎片(external fragmentation)。空闲区的存在使内存被浪费了,而这可以通过内存紧缩来解决。

分段和分页结合:MULTICS

如果一个段比较大,把它整个保存在内存中可能很不方便甚至是不可能的,因此产生了对它进行分页的想法。这样,只有那些真正需要的页面才会被调入内存。有几个著名的系统实现了对段的分页支持,本节将介绍第一个实现了这种支持的系统 MULTICS。

MULTICS 是有史以来最具影响力的操作系统之一,对 UNIX 系统、x86 存储器体系结构、快表以及云计算均有过深刻的影响。MULTICS 始于麻省理工学院的一一个研究项目,并在 1969 年上线。最后一个 MULTICS 系统在运行了 31 年后于 2000 年关闭。几乎没有其他的操作系统能像 MULTICS一样几乎没有修改地持续运行了那么长时间。

分段和分页结合:Intel x86

x86 处理器的虚拟内存在许多方面都与 MULTICS 类似,其中包括既有分段机制又有分页机制。MULTICS 有 256 K 个独立的段,每个段最长可以有 64 K 个 36 位字。x86 处理器有 16 K 个独立的段,每个段最多可以容纳 10 亿个 32 位字。这里虽然段的数目较少,但是相比之下 x86 较大的段大小特征比更多的段个数要重要得多,因为几乎没有程序需要 1000 个以上的段,但是有很多程序需要大段。自从 x86-64 起,除了在“传统模式”下,分段机制已被认为是过时的且不再被支持。虽然在 x86-64 的本机模式下仍然有某些痕迹,但大多只是未了兼容,且它们不再具有起到同样的作业,也不再提供真正的分段。

有关内存管理的研究

传统的内存管理(尤其是单处理器 CPU 的页面算法)研究硕果累累,时至今日,仍有人坚守阵地继续研究(Moruz 等人,2012),或者在此基础上关注某些特殊需求的应用(Stoica 和 Ailamaki, 2013),例如在线事务处理。不过这个领域的研究已趋式微,大多数都已消失在历史长河中,至少对于通用系统来说正是如此。然而即使针对单处理器而言,SSD 而非硬盘的页面处理也带来了新的问题,并需要新的算法(Chen 等人,2012)。作为后起之秀的非易失性相变内存,由于性能(Lee 等人,2013)、延迟(Saito 和 Oikawa, 2012),以及使用频率过高容易损坏(Bheda 等人,2011, 2012) 等特性,其页面处理也需要重新考虑。

对页面处理的研究仍在继续,不过更普遍的是聚焦于新型系统。例如,关注内存管理中具有重启功能的虚拟机(Bugnion 等人,2012)。在同样的研究领域里,Jantz 等人(2013) 的工作可以让应用程序向系统提供决策,以指导取哪个物理页来支持虚拟页。在云服务器稳定性对页面处理的影响方面,每次虚拟机可以使用的物理内存总量都不同,这也需要新的算法(Peserico, 2013)。

多核操作系统的页面处理成为一个新热门研究领域(Boyd-Wickizer 等人,2008; Baumann 等人,2009)。其中一个研究点在于,多核系统的缓存更多,其共享方式更为复杂(Lopez -Oritiz 和 Salinger, 2012)。和多核研究相关的是 NUMA 系统的页面处理,其中,不同的内存片的访问次数不同(Dashti 等人,2013; Lankes 等人,2012)。

另外,手机和平板等电子设备也逐渐转型为小型电脑,也会进行从 RAM 到“磁盘”的页面置换,不过手机,上的磁盘是闪存,Joo 等人(2012) 最近做了一些相关研究。

最后,实时系统的内存管理研究仍在继续(Kato 等人,2011)。

小结

本章主要讲解内存管理。我们看到在最简单的系统中是根本没有任何交换或分页的。一旦程序装人内存,它将持续在内存中运行,直到结束。一些操作系统一次只允许一个进程在内存中运行,而另一些操作系统支持多道程序设计。这种模型在小型或嵌人式实时系统中仍有用武之地。

接下来是交换技术。通过交换技术,系统可以同时运行总内存占用超过实际物理内存大小的多个进程。如果一个进程没有内存空间可用,它将会被交换到磁盘上。内存和磁盘上的空闲空间可以使用位图或空闲区链表来记录。

现代计算机都有某种形式的虚拟内存。最简单的情况下,每一个进程的地址空间被划分为同等大小的块,称为页面,页面可以被放入内存中任何可用的页框内。有多种页面置换算法,其中两个比较好的算法是老化算法和工作集时钟算法。

为了使分页系统工作良好,仅选择算法是不够的,还要关注诸多问题,例如工作集的确定、内存分配策略以及所需页面大小等。

如果要处理在执行过程中大小有变化的数据结构,分段是一个有用的选择,它还能简化链接和共享。不仅如此,分段还有利于为不同的段提供不同的保护。有时,可以把分段和分页结合起来,以提供二维的虚拟内存。MULTICS 系统以及 32 位 Intel x86 即是如此,支持分段也支持分页。不过,几乎没有操作系统开发者会仔细考虑分段(因为他们更青睐其他的内存模型),这导致分段逐渐乏人问津。如今,即使 64 位版本的 x86 也不支持真正的分段。

说点什么

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
提醒