操作系统——存储管理

内存是计算机中需要认真管理的资源。每个程序员都梦想拥有这样的内存：私有、容量无限大、速度无限快，并且是永久存储器（掉电不丢失数据）。但目前的技术还不能帮助我们提供这样的内存，除此之外，还有哪些选择呢？人们提出了“分层存储器”概念，在这个体系中，计算机有若干兆（MB）快速、昂贵且易失性的高速缓存，数千兆速度与价格适中且同样易失性的内存，以及几TB低速廉价，非易失性的磁盘存储，另外还有诸如DVD和USB等可移动装置。

 

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

1.   无存储器抽象

最简单的存储器就是根本没有抽象，每一个程序都直接访问物理内存，给编程人员呈现出来的存储器模型就是简单的物理内存：0到某个上限的地址集合。

 

这种情况下是无法在内存中运行两个程序的。下面是三种存储模型的变体。a中操作系统位于RAM中底部，b中操作系统位于内存顶端的ROM中，这种情况比较经常用于嵌入式设备中；c中设备驱动程序位于ROM中，操作系统的其他部分位于RAM的底部，在ROM中的系统部分称为BIOS，常用于早期的操作系统中。

 

 

 

 

在没有内存抽象的系统中实现并行的一种方法是使用多线程来编程。虽然这个想法行得通，但是却并没有广泛使用，人们通常希望能够在同一时间运行没有关联的程序。

 

不使用内存抽象的情况下运行多道程序

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

2.   一种存储器抽象：地址空间

总之，将物理地址暴露给进程会导致下面几个严重问题。第一，如果用户程序可以寻址内存的每个字节，就可以很容易地破坏操作系统；第二，使用这种模型，想要同时运行多个程序是非常困难。

2.1          地址空间的概念

要保证多个应用程序同时处于内存中并且不存在影响，需要解决两个问题：保护和重定位。更好的办法便是创造一个新的内存抽象：地址空间。地址空间为程序创造了一种抽象的内存。地址空间是一个进程可用于寻址内存的一套地址集合。每个进程都有自己的地址空间。并且这个地址空间独立于其他进程的地址空间。

基址寄存器与界限寄存器

动态重定位可以简单地把每个进程的地址空间映射到物理内存的不同部分，经典方法便是给每个CPU配置两个特殊的硬件寄存器，通常叫做基址寄存器与界限寄存器，此时，程序装载到内存中连续的空闲位置且装载期间无须重定位。当一个程序运行时，程序的物理地址装载到基址寄存器中，程序的长度装载到界限寄存器中。

 

每次一个进程访问内存，取一条指令，CPU硬件会在把地址发送到内存总线前，自动把基址值加到进程发出的地址值上，同时检查程序提供的地址是否大于界限寄存器的值（产生错误并中止访问）。

 

使用基址寄存器与界限寄存器的唯一缺点便是每次访问内存都要进行加法和比较运算。

2.2          交换技术

如果计算机物理内存足够大，大到可以保存所有的进程，那么之前提及的所有方法是可行的。但是实际上所有进程所需的RAM数量总和通常要远远超出存储器支持的范围，把所有进程一直保存在内存中需要巨大的内存。

 

有两种处理内存超载的通用方法。最简单的是交换技术，把一个进程完整调入内存，使该进程运行一段时间，然后存回磁盘。另一种策略是虚拟内存，该策略甚至使程序在只有一部分调入内存的情况下运行。

 

操作系统中内存交换技术的使用如下所示，程序运行期间通过硬件对其地址进行重定位，这里就可能很好地使用基址寄存器和界限寄存器。

 

 

 

交换在内存中产生多个空闲区（空洞），通过将所有的进程向下移动，可能将这些小的空闲区合成一大块，该技术称为内存紧缩，比较耗费CPU时间。

 

当进程被创建或换入时应该给它分配多大的内存，如果进程创建时其大小是固定的并且不能改变，分配很简单；但如果进程的数据段可以增长（动态分配内存），那么当进程空间试图增长时，就会出现问题，与该进程使用的内存区域相邻的是否为空闲区域，如果不是，就可能考虑把一个或多个进程交换出去，若无法交换，该进程便只能挂起直到一些空间空闲。

2.3          空闲内存管理

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

位图存储管理

内存被划分成几个字或几千个字节的分配单元，每个分配单元对应位图中的一位，0表示空闲，1表示占用。

 

分配单元的大小是一个重要的因素。分配单元越小，位图就越大。如果进程的大小不是分配单元的整数倍，最后一个分配单元中就会有一定数量的内存被浪费了。

 

链表的存储管理

维护一个记录已分配内存段和空闲内存段的链表。其中链表中的一个节点或者包含一个进程，或者是两个进程间的一个空的空闲区。

 

当按照地址顺序在链表中存放进程和空闲区时，有几种算法可以用来为创建的进程（或从磁盘换入的进程）分配内存。

 

最简单的算法就是首次适配算法，沿着段链表进行搜索，直到找到一个足够大的空闲区，这是一种很快的算法，尽可能少地搜索链表节点。

 

对首次适配略微修改，就可以得到下次适配算法，不同点就是每次找到合适的空闲区时记录当时的位置，以便下次寻找空闲区时从上次结束的地方开始搜索，性能略低于首次适配算法。

 

最佳适配算法搜索整个链表，从开始到结束，找到能够容纳进程最小的空闲区，最好地区配请求和可用空闲区，可能会分裂出很多非常小的空闲区。

 

另一种分配算法是快速分配算法，为那些常用大小的空闲区维护单独的链表。例如有一个n项的表，第一项指向4KB的空闲区链表表头指针，第二项指向8KB的空闲区脸变表头指针，以此类推，这样寻找一个指定大小的空闲区是十分快速的，但它和所有将空闲区按照大小进行排序的方法一样都有着共同的缺点，在一个进程终止或被换出时，寻找其相邻块，查看是否合并的过程是非常耗时的。如果不进行合并内存将很快分裂出大量的进程无法利用的空闲区域。

3.   虚拟内存

虽然存储器容量增长迅速，但是软件大小的增长更快。需要运行的程序往往大到内存无法容纳，而且必然需要系统能够支持多个程序同时运行，此时交换技术并不是一个有吸引力的解决方案。

 

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

 

 

虚拟内存是对基址寄存器和界限寄存器的一种综合。虚拟内存很适合在多道程序中使用，许多程序的片段同时保存在内存中。当一个程序等待它的一部分换入内存时，可以把CPU交给另一个进程使用。

 

3.1          分页

大部分虚拟内存的实现都采用了分页的技术。程序引用了一组内存地址时，会将地址对应的内存单元内容复制到寄存器中，其中地址可以是通过索引、基址寄存器、段寄存器或其他方式产生。

 

由程序产生的这些地址成为虚拟地址，构成了一个虚拟地址空间，在没有虚拟内存的计算机上，系统直接将虚拟地址送到内存总线上，读写操作具有同样地址的物理内存字；而在使用虚拟内存的情况下，虚拟地址不是被直接送到内存总线上，而是被送到内存管理单元（MMU），MMU将虚拟地址转换为物理地址。

 

虚拟地址空间按照固定大小划分成称为页面的若干单元，在物理内存中对应的单元称为页框。页面和页框的大小通常是一样的，RAM和磁盘之间的交换总是以整个页面为单元进行的。

 

通过恰当地设置MMU，可以把多个虚拟页面映射到几个页框中的任何一个。在实际的硬件中，用一个“在/不在”记录页面在内存中的实际存在情况。当MMU注意到该页面没有被映射，于是CPU陷入到操作系统中，这个陷阱成为缺页中断。操作系统找到一个很少使用的页框且把它的内容写入磁盘，随后需要访问的页面读到刚才回收的页框中，修改映射关系，重启引起陷阱的指令。

3.2          页表

虚拟地址到物理地址的映射可以概括如下：虚拟地址被分成虚拟页号（高位部分）和偏移量（低位部分）两部分。不同的划分对应不同的页面大小，对于16位地址和4KB的页面大小，高4位可以指定16个虚拟页面中的一页，低12位确定了所选页面中的字节偏移量（0-4095）。

 

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

 

页表项的结构是与机器密切相关的，不同机器的页表项存储的信息都大致相同。32位是一个常用的大小，最重要的域是页框号，“在/不在”位标识该表项是否有效，该表项对应的虚拟页面是否在内存中，是否会出现缺页中断。保护位指出一个页允许什么类型的访问，先进的方法是使用三位，对应是否启用读，写，执行该页面。

 

 

 

为了记录页面的使用状况，引入修改和访问位，该位在操作系统重新分配页框时是非常有用的，如果一个页面已经被修改过，必须把它写回磁盘。

 

不论是读还是写，系统都会在该页面被访问时设置访问位。其值被用来帮助操作系统在发生缺页中断时选择被淘汰的页面，不再使用的页面要比正在使用的页面更适合淘汰。最后一位用于禁止该页面被高速缓存。

 

虚拟内存本身就是用来创造一个新的抽象概念——地址空间，这个概念是对物理内存的抽象，类似于进程是对物理机器CPU的抽象。虚拟内存的实现，是将虚拟地址空间分解成页，并将每一页映射到物理内存的某个页框解除映射。

4.   页面置换算法

当发生缺页中断时，操作系统必须在内存中选择一个页面将其换出内存，以便为即将调入的页面腾出空间。如果要换出的页面在内存驻留期间已经被修改过，就必须把它写回磁盘以更新该页面在磁盘上的副本；如果未被修改过，不需要回写，直接调入即可。

 

最优页面置换算法

在缺页中断发生时，有些页面在内存中，其中有一个页面将很快被访问，其他页面则可能要到100，1000条指令后才能被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数作为标记。

 

最优页面置换算法规定应该置换标记最大的页面，把因需要调入这个页面而发生的缺页中断推迟越久越好。

 

这个算法唯一的问题就是根本无法实现，但可以对其他可实现算法的性能进行比较。

最近未使用页面置换算法

当启用一个进程时，将其所有的页面都标记为不在内存；一旦访问一个页面就会引发一次缺页中断，操作系统设置R位，设置为READ ONLY模式；如果随后对该页面的修改又引发一次缺页中断，则操作系统设置这个页面的M位并将其改为READ/WRITE模式。

 

最近未使用算法隐含的意思是，在最近的一个时钟周期淘汰一个没有被访问的已修改页面要比淘汰一个被频繁使用的干净页面要好。这种算法的主要优点是易于理解和能够有效地被实现，虽然性能不是最好。

 

先进先出页面置换算法

另一种开销小的页面置换算法是FIFO，先进先出算法。由操作系统维护一个所有当前在内存中的页面链表，最新进入的页面放在表尾，最久进入的页面放在表头。当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾。

 

第二次计算页面置换算法

FIFO算法可能会把经常使用的页面置换出去，为了避免这个问题，对该算法做一个简单的修改：检查最老页面的R位，如果R位是0，表示这个页面最老而且没有被使用，直接置换出去；如果R位是1，就将R位清零，并把该页面放到链表的尾端，然后继续搜索。

 

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

时钟页面置换算法

尽管第二次机会算法是一个比较合理的算法，但它经常要在链表中移动页面，既降低效率又不是很有必要。一个更好的办法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。

 

当发生缺页中断，算法首先检查表针指向的页面，如果R位是0就淘汰该页面，并把新的页面插入到这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到第一个R位为0的页面为止。

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

已经很久没有被使用的页面很有可能在未来较长一段时间内仍然不会被使用，这个思想提示了一个可实现的算法：在缺页中断发生时，置换未使用时间最长的页面，这个策略被称为LRU页面置换算法。

 

LRU在理论上是可以实现的，但代价很高，为了完全实现LRU，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾，困难的是在每次访问内存时都必须更新整个链表。

 

工作集页面置换算法

大多数程序都不是均匀地访问它们的地址空间的，访问往往是集中在一小部分页面。一个进程当前使用的页面集合称为它的工作集。如果整个工作集都被装入到内存中，那么进入在下一阶段之前不会产生过多中断。不少分页系统都会设法跟踪进程的工作集，以确保在让进程运行以前，该方法称为工作集模型，目的仅仅在于大大减少缺页中断率。

5.   分页系统中的设计问题

前面讨论了发生缺页中断时用来选择一个被置换页面的几个算法，怎样在相互竞争的可运行进程之间分配内存？

 

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

假设有3个进程构成了可运行进程的集合，当进程A发生缺页中断时，页面置换算法在寻找最近最少使用页面时是只考虑分配给A的页面呢？还是考虑所有在内存中的页面，这就涉及到局部分配策略与全局分配策略。局部分配策略可以有效地为每个进程分配固定的内存片段，全局算法在可运行进程之间动态地分配页框。

 

全局算法在通常情况下工作会比局部算法好，当工作集的大小随进程运行时间发生变化时这种现象更加明显。另一种途径是使用一个为进程分配页框的算法，定期确定进程运行的数目并分配相等的份额。使用全局算法，根据进程的大小按照比例为其分配页面也是可能的，但是分配必须在程序运行时动态更新，管理内存动态分配的一种方法是使用缺页中断率（PFF，Page Fault Frequency）算法，它指出了何时增加或减少分配给一个进程的页面。

 

一些页面置换算法既适用于局部置换算法，又适用于全局置换算法。比如FIFO能够将内存中最老的页面置换掉（全局算法），也可能将当前进程的页面最老的页面置换掉（局部算法）。

5.2          负载控制

即使是使用最优页面置换算法并对进程采用理想的全局页框分配，系统也可能会出现颠簸。一旦所有进程的组合工作集超出内存容量，就可能发生。一些进程需要更多内存，没有进程会需要更少的内存，这种情况下，没有方法能够在不影响其他进程的情况下满足那些需要更多内存的进程的需要。

 

减少竞争内存的进程数的一个好方法是将一部分进程交换到磁盘，并释放其所占有的所有页面。不过，另一个需要考虑的因素是多道程序设计的道数，当内存中的进程数过低的时候，CPU可能在很长时间内处于空闲状态。

5.3          页面大小

页面大小是操作系统可以选择的一个参数，要确定页面的大小，需要在几个相互矛盾的因素中获得平衡，不存在全局最优。

 

随便一个正文段，数据段或堆栈很可能不会恰好装满数个页面，平均情况下，最后一个页面中有一半是空的，多余的空间称为内部碎片，从这方面考虑，小空间的页面大小更好；此外，页面小也意味着程序需要更多的页面，这也意味着需要更大的页表，内存和磁盘之间的传输一般都是一次一页，传输中的大部分时间都花在了寻道和旋转延迟上，所以传输一个小的页面和一个大的页面基本上时间相同

 

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

 

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

大多数计算机只有一个地址空间，既存放数据也存放程序，如果地址空间足够大，一切都好；如果不够大，就会使得程序员对地址空间的使用出现困难。

 

一种解决方案是，为指令和数据设置分离的地址空间，每个地址空间都是从0开始，链接器必须知道何时使用分离的I空间和D空间，使用时也需要对数据进行重新定位到虚拟地址0而不是程序之后。两种地址空间都可以分页，并且相互独立，分别有自己的页表，分别完成虚拟页面到物理页框的映射。

 

5.5          共享页面

大型多道程序设计系统中，几个不同的用户同时运行同一个程序是很常见的，为了避免在内存中有一个页面的两个副本，共享页面效率更高。但不是所有的页面都适合共享，那些只读的程序文本可以共享，但是数据页面不能共享。

 

如果系统支持分离的指令空间和数据空间，那么让多个进程共享程序就变得非常简单了，这些进程使用相同的指令空间和不同的数据空间。每个进程在其进程表中存在两个不同的指针，当调度程序选择一个进程运行时，它使用这些指针来定位合适的页表，并使用它们来设立MMU。

 

在两个或更多进程共享某些代码时，共享页面存在一些问题，一个进程的结束可能会导致撤销其所有页面，会造成另一个进程产生大量的缺页中断。

 

共享数据要比共享代码麻烦，但并不是不可能的，只要这两个进程共享的数据是只读的，不做修改就可以将这种情况保持下去，但只要有一个进程更新了数据，就会触发只读保护，并引发操作系统陷阱，然后会生成一个该页的副本，这样每个进程都有自己的专用副本，这两个复制都是可以读写的，这种方式叫做写时复制，通过减少复制而提高了性能。

5.6          共享库

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

 

现代操作系统中，很多大型库被众多进程使用，一个更加通用的技术是使用共享库（Windows中被称为DLL或动态链接库）。当一个程序和共享库链接时，链接器并没有加载被调用的函数，而是加载了一小段能够在运行时绑定被调用函数的存根例程。共享库和程序一起被加载，或者在其所包含函数的第一次被调用时被装载，如果其他程序已经装载了该共享库，就没有必须要再次装载了。值得注意的是，当一个共享库被装载或和使用时，整个库并不是被一次性读入内存，而是根据需要，以页面为单位装载的，没有被调用的函数是不会被装载的。

 

除了可以使可执行文件更小，节省内存空间以外，共享库还有一个优点，如果共享库的一个函数因为修正一个bug被更新了，并不需要重新编译调用了这个共享库的程序。

5.7          内存映射文件

共享库其实是一种更为通用的机制——内存映射文件的特例，这种机制的思想是：进程可以通过发起一个系统调用，将一个文件映射到其虚拟地址空间的一部分。在映射共享的页面时不会实际读入页面的内容，而是在访问页面时才会每次一页地读入，磁盘文件被当作后备存储。

 

内存映射文件提供了一种I/O的可选模型，把一个文件当作内存中的一个大型数组，而不是通过读写这个文件实现。如果两个或两个以上的进程同时映射了同一个文件，就可以通过共享内存来通信。

 

5.8          清除策略

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

 

保持一定数目的页框供给比使用所有内存并在需要时搜索一个页框有更好的性能，分页守护进程至少保证了所有空闲页框是干净的，被分配时不用急着写回磁盘。