计算机四级操作系统-5-内存管理

第5章内存管理

计算机系统中的存储器可以分成两类：内存储器（简称内存）和外存储器（简称外存）。处理器可以直接访问内存，但不能直接访问外存。CPU要通过启动相应的输入/输出设备后才能使外存与内存交换信息。

与早期的数字电子计算机相比较，目前计算机的内存容量已经是非常大了，但是程序大小的增长速度与内存容量的增长几乎一样快。正如帕金森定律所说的那样存储器有多大，程序就会有多大”。使用计算机的人们总在抱怨机器的内存太小，总是不够用。

内存管理是操作系统的重要功能之一，对内存管理的好坏直接影响计算机系统工作性能的高低。本章叙述存储管理的基本思想。

5.1基本概念

本节给出涉及内存管理的几个重要的概念。首先强调第2章介绍的存储体系概念在内存管理中的地位，然后提出内存管理的基本任务，最后重点介绍内存管理中的一个非常重要的概念——地址转换，又称地址重定位、地址映射等。

5.1.1存储体系

在计算机系统中，存储器是处理器处理的信息的来源与归宿，占据着重要地位。到目前为止,最先进的计算机科学技术能够提供的存储设备的速度仍然明显慢于同级别的中央处理器的速度。而且由于成本等方面的原因，任何一种存储设备都无法在速度与容量两个方面同时满足用户的需求，在本书第2章有关容量、速度和成本这三个目标的分析中已经说明。为解决这些矛盾，采用如图5-1所示的存储体系。

在上述存储体系中包含：少量的、非常快速、昂贵、内容易变的高速缓存器（Cache),通常是百KB的数量级;若干兆字节、中等速度、中等价格、内容易变的内存（RAM)，通常是千MB的数量级；低速、价廉、内容不易变的外存（磁盘），通常是百至千GB的数量级;如果配有光盘或者磁带机，外存的容量可以增大至千GB甚至更大。

快速存储设备和大容量存储设备必须构成为统一的整体，由操作系统协调这些存储器的使用。对于内存速度和容量的要求是，内存的直接存取速度尽量快到与CPU取指速度相匹配，其容量大到能装下当前运行的程序与数据，否则CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥。各种速度和容量的存储器硬件在操作系统协调之下，形成了一种存储器层次结构，或称存储体系。

5.1.2存储管理的任务

任何程序和数据以及各种控制用的数据结构都必须占用一定的存储空间，因此，存储管理直接影响系统性能。存储器由内存和外存组成。所谓内存空间，是由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。内存空间用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的亦即程序计数器所指的存储空间。

内存空间一般分为两部分:一部分是系统区，用以存放操作系统常驻内存部分，用户不能占用这部分空间；另一部分是用户区，分配给用户使用，用于装入并存放用户程序和数据，这部分的信息随时都在发生变化。存储管理实质上就是管理供用户使用的那部分空间。

由于技术的进步，内存的制造成本大幅度下降，内存的容量大幅度上升，系统具有上千兆的内存容量是常见的了。但是，随着计算机应用领域的不断扩大与深化，现代程序的规模更大，更复杂，在基础科学和人工智能等许多新的应用领域，将对内存容量提出更高的要求。因此，如何管理好内存资源，仍然是操作系统的一个重要课题。内存管理问题主要包括：内存管理方法、内存的分配和释放算法、虚拟存储器的管理、控制内存和外存之间的数据流动方法、地址变换技术和内存数据保护与共享技术等。

为了对内存进行有效的管理，一般把内存分成若干个区域。即使在最简单的单道、单用户系统中，至少也要把它分成两个区域:在一个区域内存放系统软件，如操作系统本身；而另外一个区域则用于安置用户程序。显然，在多道、多用户系统中，为了提高系统的利用率，需要将内存划分成更多的区域，以便支持多道程序。用户对内存管理提出了许多要求：

（1）充分利用内存，为多道程序并发执行提供存储基础。

（2）尽可能方便用户使用：

●操作系统自动装入用户程序；

●用户程序中不必考虑硬件细节。

（1）系统能够解决程序空间比实际内存空间大的问题。

（2）程序的长度在执行时可以动态伸缩。

（3）内存存取速度快。

（4）存储保护与安全。

（5）共享与通信。

（6）及时了解有关资源的使用状况。

（7）实现的性能和代价合理。

这些要求往往引起了存储器分配以及随之而产生的一系列问题。通过对用户需求的分析，得到在操作系统中存储管理的主要任务。

1.内存的分配和回收

一个有效的存储分配机制，应对用户提出的需求予以快速响应，为之分配相应的存储空间；在用户程序不再需要它时及时回收，以供其他用户使用。为此，应该具有以下功能：

（1）记住每个存储区域的状态。内存空间哪些是分配了的，哪些是空闲的？这就需要设置相应的分配表格，记录内存空间使用状态。

（2）实施分配。当用户提出申请时，按需要进行分配，并修改相应的分配表格。分配方式有静态分配和动态分配两种。

（3）回收。接受用户释放的区域，并修改相应的分配表格。

为实现上述功能，必须引人分配表格，通称为内存分配表，其组织方式包括：

●位示图表示法：用一位（Bit)表示一个空闲页面（0表示空闲，1表示占用）。

●空闲页面表•.包括首页面号和空闲页面个数，连续若干页面作为一组登记在表中。

●空闲块表：空闲块首址和空闲块长度，没有记录的区域即为进程所占用。

内存分配有两种方式：

（1）静态分配。程序要求的内存空间是在目标模块连接装入内存时确定并分配的，并且在程序运行过程中不允许再申请或在内存中“搬家”，即分配工作是在程序运行前一次性完成。

（2）动态分配。程序要求的基本内存空间是在目标模块装入时确定并分配的。但是在程序运行过程中，允许申请附加的内存空间或在内存中“搬家”，即分配工作可以在程序运行前及运行过程中逐步完成。

显然，动态存储分配具有较大的灵活性，它不需要一个程序的全部信息进入内存后才可以运行，而是在程序运行中需要时系统自动将其调入内存。程序当前暂不使用的信息可以不进入内存，这对提高内存的利用率大有好处。动态存储分配反映了程序的动态性，较之静态存储分配更为合理。

2.存储共享

所谓存储共享是指两个或多个进程共用内存中的相同区域，这样不仅能使多道程序动态地共享内存，提高内存利用率，而且还能共享内存中某个区域的信息。共享的内容包括:代码共享和数据共享，特别是代码共享要求代码必须是纯代码。

存储共享的一个目的是通过代码共享节省内存空间，提高内存利用率;另一个目的是通过数据共享实现进程通信。

3.存储保护

在多道程序系统中，内存中既有操作系统，也有许多用户程序。为使系统正常运行，避免内存中各程序相互干扰，必须对内存中的程序和数据进行保护。

存储保护的目的在于为多个程序共享内存提供保障，使在内存中的各程序只能访问其自己的区域，避免各程序间相互干扰。特别是当某一程序发生错误时，不至于影响其他程序的运行，更要防止破坏系统程序。存储保护通常需要有硬件支持，并由软件配合实现。

存储保护的内容包括:保护系统程序区不被用户有意或无意的侵犯；不允许用户程序读写不属于自己地址空间的数据，如系统区地址空间、其他用户程序的地址空间。

1)地址越界保护

每个进程都具有其相对独立的进程空间，如果进程在运行时所产生的地址超出其地址空间，则发生地址越界。地址越界可能侵犯其他进程的空间，影响其他进程的正常运行;也可能侵犯操作系统空间，导致系统混乱。因此，对进程所产生的地址必须加以检查，发生越界时产生中断，由操作系统进行相应处理。

2)权限保护

对于允许多个进程共享的公共区域，每个进程都有自己的访问权限。例如，有些进程可以执行写操作，而其他进程只能执行读操作等。因此，必须对公共区域的访问加以限制和检查。

●对属于自己区域的信息，可读可写。

●对公共区域中允许共享的信息或获得授权可使用的信息，可读而不可修改。

●对未获授权使用的信息，不可读、不可写。

存储保护一般以硬件保护机制为主，软件为辅，因为完全用软件实现系统开销太大，速度显著降低。所以，当发生地址越界或非法操作时，由硬件产生中断，进入操作系统处理。

4.“扩充”内存容量

用户在编制程序时，不应该受内存容量限制，所以要采用一定的技术来“扩充”内存的容量，使用户得到比实际内存容量大得多的内存空间。

具体实现是在硬件支持下，软件、硬件相互协作，将内存和外存结合起来统一使用。通过这种方法扩充内存，使用户在编制程序时茶受内存限制。借助虚拟存储技术或其他交换技术，达到在逻辑上扩充内存容量，亦即为用户提供比内存物理空间大得多的地址空间，使得用户感觉他的程序是在这样一*个大的存储器中运行。

5.1.3地址转换

一般而言，存储器以字节（每个字节为8个二进制位）为编址单位，每个字节都有一个地址|与其对应。假定存储器的容量为〃字节，其地址编号顺序为0，1，2，…，n-1。这些地址称为内存的“绝对地址”，与绝对地址对应的内存空间称为“物理地址空间”。

在多道程序设计的系统中，内存中同时存放了多个用户程序。操作系统根据内存的使用情|况为用户分配内存空间。因此，每个用户不能预先知道他的程序将被存放到内存的什么位置。|这样，用户程序中就不能使用内存的绝对地址。为了方便用户，每个用户都可认为自己的程序和|数据存放在一组从“0”地址开始的连续空间中。用户程序中使用的地址称为“逻辑地址”，与逻|辑地址对应的存储空间称为“逻辑地址空间”。

1.地址重定位

当用户程序进入计算机系统请求执行时，存储管理要为它分配合适的内存空间，这个分配到|的内存空间可能是从某单元开始的一组连续的地址空间。该地址空间的起始地址是不固定的，|而且逻辑地址与分到的内存空间的绝对地址经常不一致。因此，每个逻辑地址在内存中也没有一个固定的绝对地址与之对应。例如，某程序被装到内存中单元A开始的区域中，当程序中指定访问单元k时，实际应访问内存的单元A+k。如果程序被装入到内存中单元B开始的区域，那么，程序中指定访问的单元k在内存中的实际位置应该是单元可见，程序执行时不能按照其逻辑地址到内存中存取信息，处理器必须按照实际地址去访问内存才能保证程序的正确执行。

为了保证程序的正确执行，必须根据分配给程序的内存区域对程序中指令和数据的存放地址进行重定位，即要把逻辑地址转换成绝对地址。

把逻辑地址转换成绝对地址的工作称为“地址重定位”或“地址转换”，又称“地址映射”。重定位的方式有“静态重定位”和“动态重定位”两种，下面分别介绍。

2.静态重定位

在装人一个程序时，把程序中的指令地址和数据地址全部转换成绝对地址。由于地址转换工作是在程序开始执行前集中完成的，所以在程序执行过程中就无须再进行地址转换工作，这种地址转换方式称为“静态重定位”。

假定用户程序的逻辑地址空间从“0”到“168”，其中第18号单元处有一条“加法”指令，该指令要求从第066号单元处取出操作数1234，然后进行加法操作。如果存储管理为该程序分配的内存区域是从第800号单元开始，那么，逻辑地址第18号单元在内存中的对应位置是第818号单元，第066号单元在内存中的对应位置应该是第866号单元。

如果不修改上述“加法”指令中的操作数地址，则处理器执行该指令时将从内存的第066号单元中去取操作数，这显然是错误的，参见图5-2。

图5-2静态重定位

3.动态重定位

在装人程序时，不进行地址转换，而是直接把程序装入到分配的内存区域中。在程序执行过程中，每当执行一条指令时都由硬件的地址转换机构将指令中的逻辑地址转换成绝对地址。这种方式的地址转换是在程序执行时动态完成的，故称为“动态重定位”。图5-3指出了动态重定位的过程。

动态重定位由软件和硬件相互配合来实现。硬件要有一个地址转换机构，该机构可由一个基址寄存器和一个地址转换线路组成。存储管理为程序分配内存区域后，装入程序把程序直接装到所分配的区域中，并把该内存区域的起始地址存人相应程序进程的进程控制块中。当程序进程被调度占用处理器时，随同现场信息的恢复，程序所占的内存区域的起始地址也被存放到“基址寄存器”中。程序执行时，处理器每执行一条指令都会把指令中的逻辑地址与基址寄存器中的值相加得到绝对地址，然后按绝对地址访问内存。

图5-3动态重定位

在图5-3中，基址寄存器BR中存放了程序所在内存区域的起始地址1000。当处理器从第100号单元取出指令后，该指令中的逻辑地址是500，把基址寄存器中的值1000与逻辑地址500相加得到绝对地址1500，处理器便可从第1500号单元中取出正确的操作数。

采用动态重定位时，由于装人内存的程序仍保持原来的逻辑地址，所以必要时可改变程序在内存中的存放区域。程序在内存中被移动位置后，只要把新区域的起始地址代替原来在基址寄存器中的值，这样，在程序执行时，硬件的地址转换机构将按新区域的起始地址与逻辑地址相加，转换成新区域中的绝对地址，程序仍可正确执行。

若程序执行时被改变了存放区域仍能正确执行，则称程序是可浮动的。采用动态重定位的系统支持“程序浮动”。而采用静态重定位时，由于被装入内存的程序信息都已经用绝对地址指示，程序执行过程中不再进行地址转换，故程序执行过程中是不能改变存放位置的。可见，采用静态重定位的系统不支持“程序浮动”。

5.2分区存储管理方案

分区存储管理是能满足多道程序运行的最简单的存储管理方案。其基本思想是把内存划分成若干个连续区域，称为分区，每个分区装入一个运行程序。分区的方式可以归纳成固定分区和可变分区两类。

5.2.1固定分区

1.基本思想

固定分区是指系统先把内存划分成若干个大小固定的分区，一旦划分好，在系统运行期间便不再重新划分。为了满足不同程序的存储要求，各分区的大小可以不同。由于每一分区的大小是固定的，就对可容纳程序的大小有所限制了。因此，程序运行时必须提供对内存资源的最大申请量。

2.内存分配表与分区的分配、回收

用于固定分区管理的内存分配表是一张分区说明表，按顺序每个分区在分区说明表中对应一个表目。表目内容包括分区序号、分区大小、分区起始地址以及使用状态（空闲或占用）。一个程序在运行时，先要根据其对内存的需求量，按一定的分配策略在分区说明表中查找空闲分区。若找到合乎需要的分区，就将该分区分配给程序，并将该分区置为占用状态。当程序完成时释放这块分区内存，由系统回收，并在分区说明表中将回收的分区重新置为空闲状态。图5-4是固定分区的示例。

图5-4固定分区示例

在图5-4中，通过分区说明表可以看到，区号为1的分区大小为8KB，起始地址为16K，状态为占用，实际是被作业A占用；区号为2的分区大小为16KB，起始地址为24K，状态为空闲；区号为3的分区大小为32KB，起始地址为40K，状态为占用，实际是被作业B占用；如此等等。

固定分区方案虽然可以使多个程序共存于内存中，但不管采用哪种分配策略，都不能充分利用内存。因为一个程序的大小不可能刚好等于某个分区的大小，所以很难避免内存空间的浪费。另外，固定分区方案灵活性差，可接纳程序的大小受到了分区大小的严格限制。

5.2.2可变分区

1.基本思想

可变分区是指系统不预先划分固定分区，而是在装人程序时划分内存分区，使为程序分配的分区的大小正好等于该程序的需求量，且分区的个数是可变的。显然，可变分区有较大的灵活性，较之固定分区能获得更好的内存利用率。

系统初启后，在内存中除操作系统区之外，其余空间为一个完整的大空闲区。当有程序要求装入内存运行时，系统从该空闲区中划分出一块与程序大小相同的区域进行分配。当系统运行一段时间后，随着一系列的内存分配和回收，原来的一整块大空闲区形成了若干占用区和空闲区相间的布局。若有上下相邻的两块空闲区，系统应将它们合并成为一块连续的大空闲区。

图5-5是一个可变分区分配和回收的示例。图5-5(a)是某一时刻内存空间的布局情况，此时内存装入了A、B、C三个作业，一块空闲区大小为10KB，另一块空闲区大小为94KB₀此时，又有作业D和作业E请求装入，作业D大小为70KB;图5-5(b)中系统为作业D分配一块内存分区，此时内存中剩下了两块较小的空闲区，一块空闲区大小为10KB，另一块空闲区大小为24KB₀作业E大小为40KB，比这两块空闲区大，作业E的需要不能满足。图5-5(c)表示作业A(大小为16KB)和作业C(大小为30KB)已完成，系统回收了它们的占用区。从作业A回收了16KB与原有的10KB的空闲区合并，形成一个26KB的空闲区；从作业C回收了30KB，形成一个30KB的空闲区。这样，在内存中形成了三块空闲区，大小分别是26KB、30KB和24KB，它们的总容量虽然远大于作业E(大小为40KB)的需求量，但每块空闲区的单独容量均小于程序E的容量，故系统仍不能为作业E实施分配。

2.移动技术

从上面的例子可见，内存经过一段时间的分配回收后，会存在很多很小的空闲块。它们每一块都不足以满足程序进一步分配内存的要求，但其总和却可以满足程序的分配要求，这些空闲块被称为碎片。在可变分区管理方案中，随着分配和回收次数的增加，必然导致碎片的出现。

解决碎片问题的办法是在适当时刻进行碎片整理，通过移动内存中的程序，把所有空闲碎片合并成一个连续的大空闲区且放在内存的一端，而把所有程序占用区放在内存的另一端，参见图5-6。这一技术称为“移动技术”或“紧凑技术”或“紧缩技术”。

在图5-6中，作业E需要40KB的空间。在存储器中有三块空闲的碎片，大小分别是26KB、30KB和24KB，它们的总容量80KB虽然远大于作业E(大小为40KB)的需求量，但每块空闲区的单独容量均小于作业E的容量，故系统仍不能为作业E实施分配，参见图5-6(a)。采用移动技术之后，在内存中的作业B和作业D被移动到内存的一端，三块碎片被拼接为一个大的空闲区，其容量为80KB，参见图⁵_6(b)。移动技术为作业E的运行创造了条件，作业E被分配了⁴0KB空间，还剩下一块40KB的空闲区。

移动技术可以集中分散的空闲区，提高内存的利用率，便于作业动态扩充内存。采用移动技术要注意以下问题：

（1）移动技术会增加系统的开销。采用移动技术，需要大量地在内存中进行数据块移动的操作，还要修改内存分配表和进程控制块，这些工作既增加了系统程序的规模，也增大了系统运行时间。

（2）移动是有条件的。不是任何在内存中的作业都能随时移动。比如，若某个进程正在与外部设备交换信息，与该进程有关的数据块就不能移动，只能在与外部设备的信息交换结束之后,再考虑移动。

所以，在采用移动技术时应该尽可能减少需要移动的作业数和信息量。这里以图5-7中的例子说明。

在图5-7中，为了要给作业E寻找⁴0KB的空闲空间，按图⁵_6(b)的做法拼出一个80KB的空闲区，当然是可以的，但是不符合尽可能减少需要移动的作业数和信息量的要求。为了能在尽可能减少需要移动的作业数和信息量的要求的前提下得到⁴0KB的空闲空间，可以只移动有24KB空间的空闲区，与有30KB空间的空闲区一起拼出一个54KB空间的空闲区，如图5-7(b)所示。也可以只移动那块有30KB空间的空闲区，与有24KB空间的空闲区一起拼出一个54KB空间的空闲区，如图5-7(c)所示。从移动的信息量考虑，图5-7(b)所示的方案需要移动24KB的信息量，而图5-7(c)所示的方案需要移动30KB的信息量，图5-7(b)方案好于图4-7(c)方案，少移动了6KB的信息量。

3.可变分区的实现

采用可变分区方式管理时，要有硬件的地址转换机构作支持。硬件设置两个专用的控制寄存器:基址寄存器和限长寄存器。基址寄存器用来存放程序所占分区的起始地址，限长寄存器用来存放程序所占分区的长度。

当程序被装到所分配的分区后，把分区的起始地址和长度作为现场信息存入该作业进程的进程控制块中。进程调度选中某程序进程占用处理器时，作为现场信息的分区起始地址和长度被送人基址寄存器和限长寄存器中。程序执行过程中，处理器每执行一条指令都要取出该指令中的逻辑地址。当逻辑地址小于限长寄存器中的限长值时，逻辑地址加基址寄存器值就可得到绝对地址。当逻辑地址大于限长寄存器中的限长值时，表示欲访问的内存地址超出了所分配的分区范围。这时就不允许访问，而形成一个“地址越界”的程序性中断事件。图5-8是地址转换的示意图。

图5-8可变分区地址转换

为了实现可变分区的管理，必须设置某种数据结构用以记录内存分配的情况，确定某种分配策略并且实施内存的分配与回收。

内存分配表由两张表格组成。一个是已分配区表，记录已装入的程序在内存中占用分区的起始地址和长度，用标志位指出占用分区的程序名。另~^个是空闲区表，记录内存中可供分配的空闲区的起始地址和长度，用标志位指出该分区是未分配的空闲区。由于已占分区和空闲区的个数不定，因此，两张表格中都应设置适当的空栏目，分别用以登记新内存分配表，如图5-9所示。

已分配区表                                       空闲区表

图5-9已分配区表和空闲区

4.空闲分区的分配策略

这里介绍操作系统查找和分配空闲区的四种分配算法。

1）最先适应算法

最先适应算法,又称顺序分配算法。在这种分配算法中，当接到内存申请时，顺序查找分区说明表，找到第一个满足申请长度的空闲区，将其分割并分配。此算法简单，可以快速怍出分配决定。

图5-10给出了该算法的具体流程。

2）最优适应算法

当接到内存申请时，查找分区说明表，找到第一个能满足申请长度的最小空闲区，将其分割并分配。此算法最节约空间，因为它尽量不分割大的空闲区；其缺点是可能会形成很多很小的空闲区域，称作碎片。

3）最坏适应算法

当接到内存申请时，查找分区说明表，找到能满足申请要求的最大的空闲区。

该算法的基本思想是：在大空闲区中装入信息后，分割剩下的空闲区相对也很大，还能用于装人其他程序。

该算法的优点是可以避免形成碎片，而缺点是分割了大的空闲区后，如果再遇到较大的程序申请内存时，无法满足要求的可能性较大。

4）下次适应算法

当接到内存申请时，查找分区说明表，从上一次分配的位置开始扫描内存，选择下一个大小足够的可用块。

5.分区的回收

当用户程序执行结束后，系统要回收已使用完毕的分区，将其记录在空闲区表中。在收回空间时，应首先检查是否有与回收区相邻的空闲区，即检查相邻的空闲区表中标志为“未分配”的栏目，以确定是否有相邻空闲区，若有，则应合并成一个空闲区登记。

一个归还区可以有上邻空闲区，也可以有下邻空闲区，或既有上邻空闲区又有下邻空闲区，或既无上邻空闲区又无下邻空闲区。假定作业归还的分区起始地址为^长度为一般情况下应考虑如下四种可能性。

（1）回收分区的上邻分区是空闲的，需要将两个空闲区合并成一个更大的空闲区，然后修改空闲区表。

具体计算方法如下：

如果空闲区表中第i个登记栏中的“起始地址+长度”正好等于^则表明回收区有一个上邻空闲区。这时要修改第纟栏登记项的内容:起始地址不变，长度为原长度加上L即

长度=原长度+L

于是，回收区便与上邻空闲区合并在一起了。

在图5-11中，空闲区表中第i个登记栏中的起始地址为1000，长度为1000，而回收区的起始地址S为2000，长度L为1000。空闲区表中第^•个登记栏中“起始地址+长度=2000”，正好等于5。于是要修改第i栏登记项的内容，其起始地址不变，长度为原长度加上I即1000+1000=2000。实现了回收区与上邻空闲区的合并。

（2）回收分区的下邻分区是空闲的，需要将两个空闲区合并成一个更大的空闲区，然后修改空闲区表。

具体计算方法如下：

如果S+L正好等于空闲区表中某个登记的栏目（假定为第；栏）所示分区的起始地址，则表明回收区有一个下邻空闲区。这时只要修改第i栏登记项的内容：

起始地址=S

长度=原长度+L

则第i栏指示的空闲区是回收区与下邻空闲区合并后的一个大空闲区。

（3）回收分区的上邻分区和下邻分区都是空闲的，需要将三个空闲区合并成一个更大的空闲区，然后修改空闲区表。

如果             S=第i栏起始地址+长度

S+L=第k栏起始地址

则表明回收区既有上邻空闲区，又有下邻空闲区。此时，必须把这三个区合并成一个空闲区登记入空闲区表中，只需使用一个登记栏目。具体修改方法如下：

第i栏起始地址不变；

第i栏长度为“i栏中原长度+k栏中长度+L”；

第k栏的标志应修改成“空”状态。

于是,第t栏中登记的空闲区就是合并后的空闲区，而第k栏成为空表目了。

（4）回收分区的上邻分区和下邻分区都不是空闲的，则直接将空闲分区记录在空闲区表中。

这时，应找一个标志为“空”的登记栏，把回收区的起始地址和长度登记入表，且把该栏目中的标志位修改成“未分配”，表示该登记栏中指示了一个空闲区。

6.分区的保护

有两种存储分区的保护方法。

一种是系统设置界限寄存器，界限寄存器可以是上、下界寄存器或基址、限长寄存器，在本书的第2章已介绍有关存储保护机构的基本知识。

通常，系统设置一对界限寄存器，用来存放现行进程的存储界限。在进程的PCB中保存界限值，当轮到该进程执行时，将界限值作为进程现场的一部分恢复。在进程执行过程产生的每一个访问内存的地址，硬件都自动将其与界限寄存器中的值进行比较，若发生地址越界，便产生保护性地址越界中断，参见图5-12。

在图5-12中，程序A自60K开始存放，到124K为止。如果采用上、下界寄存器的方法，程序A的下界寄存器中的内容为60K，上界寄存器中的内容为124K，如图5-12(a)所示。如果釆用基址寄存器与限长寄存器的方法，则基址寄存器中的内容为60K，限长寄存器中的内容为64K，如图5-12(b)所示。

另一种是保护键方法，即为每个分区分配一个保护键，相当于一把锁。同时为每个进程分配一个相皮的保护键，相当于一把钥匙，存放在程序状态字中。每当访问内存时，都要检查钥匙和锁是否匹配，若不匹配，将发出保护性中断。

5.2.3分区管理方案的优缺点

分区管理是实现多道程序设计的一种简单易行的存储管理技术。通过分区管理，内存真正成了共享资源，有效地利用了处理机和I/O设备，从而提高了系统的吞吐量和缩短了周转时间。分区存储管理算法比较简单，所采用的表格不多，实现起来比较容易，内存额外开销较少，存储保护措施也很简单。

在内存利用率方面，可变分区的内存利用率比固定分区高。

分区管理的主要缺点是，内存使用仍不充分，并且存在着较为严重的碎片问题。虽然可以解决碎片问题，但需要移动大量信息，浪费了处理机时间。此外，分区管理不能为用户提供“虚存”，即不能实现对内存的“扩充”，每一个用户程序的存储要求仍然受到物理存储器实际存储容量的限制。分区管理要求运行程序一次全部装入内存之后，才能开始运行。这样，内存中可能包含有一些实际不使用的信息_Q

5.3覆盖技术与交換技术

无论内存空间有多大，程序所需要的空间往往总是比可用的内存空间更大。

为了“扩充”内存，可以把进程地址空间中信息（指令和数据）的一部分放在外存上，而把那些当前需要的执行程序段和数据段放在内存中。这样，在内、外存之间就会出现信息交换的问题。本节所介绍的覆盖技术（Overlay）和交换技术（Swapping）就是用于控制这种交换的。覆盖技术同交换技术的主要区别是控制交换的方式不同，前者主要用在早期的系统中，而后者目前主要用于小型分时系统。

5.3.1覆盖技术

覆盖技术是指一个程序的若干程序段或几个程序的某些部分共享某一个存储空间。覆盖技术的实现是把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构使那些不会同时执行的程序段共享同一块内存区域。未执行的程序段先保存在磁盘上，当有关程序段的前一部分执行结束后，把后续程序段调入内存，覆盖前面的程序段。

覆盖技术不需要任何来自操作系统的特殊支持，可以完全由用户实现，即覆盖技术是用户程序自己附加的控制。覆盖技术要求程序员提供一个清楚的覆盖结构，即程序员要把一个程序划分成不同的程序段，并规定好它们的执行和覆盖的顺序。操作系统则根据程序员提供的覆盖结构，完成程序段之间的覆盖。

覆盖技术可以由编译程序提供支持。此时被覆盖的块是由程序员或编译程序预先（在执行前）确定的。总之，覆盖可以从用户级彻底解决内存小装不下程序的问题。

下面举一个例子说明覆盖技术的特点，参见图5-13。

假设作业1的程序正文由A、B、C、D、E、F6个程序段组成，它们之间的调用关系如图5-13(a)所示。其中，程序段A只调用程序段B和C，程序段B只调用程序段F,而程序段C只调用D和E。即B不会调用C，C也不会调用B。因此，程序段B和程序段C就无需同时在内存中。可按图5-13(b)分配程序段的调入。可见，虽然该程序正文段所需要的内存空间是：A(20KB)+B(50KB)+F(30KB)+C(30KB)+D(20KB)+E(40KB)=190KB，但是在采用了覆盖技术后只需要110KB内存空间就行了。

覆盖技术打破了需要将一个程序的全部信息装入内存后程序才能运行的限制。它利用相互独立的程序段之间在内存空间的相互覆盖，逻辑上扩充了内存空间，从而在某种程度上实现了在小容量内存上运行较大程序的目的。

覆盖技术是早期釆用的简单的扩充内存的技术，对用户不透明，增加了用户的负担，要求用户清楚地了解程序的结构，并指定各程序段调入内存的先后次序，以及内存中可以覆盖掉的程序段的位置等。而且程序段的最大长度仍受内存容量的限制。

通常，覆盖技术主要用于系统程序的内存管理上，因为系统软件设计者容易了解系统程序的覆盖结构。例如，MS-DOS把系统分成两部分，一部分是操作系统中经常要用到的基本部分，它们常驻内存且占用固定区域，另一部分是不太经常使用的部分，它们存放在磁盘上，当调用它们时才被调人内存覆盖区。

5.3.2交换技术

交换技术又称对换技术。在分时系统中，用户的进程比内存能容纳的数量要多，这就需要在磁盘上保存那些内存放不下的进程。在需要运行这些进程时，再将它们装人内存。

进程从内存移到磁盘并再移回内存称为交换。交换技术是进程在内存与外存之间的动态调度，是由操作系统控制的。系统可以将那些不在运行中的进程或其一部分调出内存，暂时存放在外存上的一个后备存储区（称为盘交换区SwappingArea）中，以腾出内存空间给现在需要内存空间的进程，后者可能需要从外存换人内存，以后再将换出的进程调入内存继续执行。

交换技术的目的是尽可能达到“足够快地交换进程，以使当CPU调度程序想重新调度CPU时，总有进程在内存中处于就绪（准备执行）状态”的理想状态，从而提高内存利用率。

交换技术多用于分时系统中。大多数现代操作系统都使用交换技术，交换技术有力地支持多道程序设计，同时交换技术也是下面将要介绍的虚拟页式存储技术的基础。

交换技术的原理并不复杂，但是在实际的操作系统中使用交换技术需要考虑很多相关的问题。主要有：

1）换出进程的选择

即系统需要将内存中的进程换出时，应该选择哪个进程？

在使用交换技术时，换出进程的选择是非常重要的问题，如果处理不当，将会造成整个系统效率低下。在分时系统中，一般情况下可以根据时间片轮转法或基于优先数的调度算法来选择要换出的进程。系统在选择换出进程时，希望换出的进程是短时间内不会立刻投入运行的。

2）交换时机的确定

什么时候需要系统进行内外存的交换？一般情况下可以在内存空间不够或有不够的危险时，换出内存中的部分进程到外存，以释放所需内存。也可以当系统发现一个进程长时间不运行时就将该进程换出。

3）交换空间的分配

在一些系统中，当进程在内存中时，不再为它分配磁盘空间。当它被换出时，必须为它分配磁盘交换空间。每次交换，进程都可能被换到磁盘的不同地方。这种管理交换区的方法与管理内存的方法相同。

在另外一些系统中，进程一旦创建，就分配给它磁盘上的交换空间。无论何时进程被换出，它都被换到已经为它分配的空间，而不是每次换到不同的空间。当进程结束时，交换空间被回收。

4）换入进程换回内存时位置的确定

换出后再换入内存的进程，位置是否一定要在换出前的原来位置上。受绝对地址产生时的限制，如果进程中引用的地址都是绝对地址，那么再次被换入内存的进程一定要在原来的位置上。如果进程中引用的地址是相对地址，在装入内存可再进行地址重定位，那么再次被换入内存的进程就可以不在原来的位置上。

交换技术的缺点是，由于交换时需要花费大量的CPU时间，这将影响对用户的响应时间，因此，减少交换的信息量是交换技术的关键问题。合理的做法是，在外存中保留每个程序的交换副本，换出时仅将执行时修改过的部分复制到外存。

同覆盖技术一样，交换技术也是利用外存来逻辑地扩充内存，它的主要特点是，打破了一个程序一旦进入内存便一直运行到结束的限制。

与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构，对用户而言是透明的。而且，交换可以发生在不同的进程或程序之间，而覆盖发生在同一进程或程序内部，而且只能覆盖那些与覆盖段无关的程序段。因此，交换技术比覆盖技术更加广泛地用于现代操作系统。

覆盖技术与交换技术的发展导致了虚拟存储技术的出现。

5.4页式存储管理方案

用分区方式管理内存时，每道程序都占用内存的一块或几块连续的存储空间。因此，当内存中无足够大的连续空间时，程序就无法装人，必须移动已在内存中的某些程序后才能再装入新的程序，这不仅不方便，而且系统开销也增大。

如果可以把一个逻辑地址连续的程序分散存放到几个不连续的内存区域中，并且保证程序的正确执行，则既可充分利用内存空间，又可减少移动所花费的开销。页式存储管理就是这样一种有效的管理方式。

5.4.1基本思想

页式存储管理思想首先由英国曼彻斯特大学提出，并在该校的Atlas计算机上使用。该技术已广泛用于微机系统中，支持页式存储管理的硬件部件通常称为“存储管理部件”(Memory Management Unit’MMU)。

存储管理部件首先把内存分成大小相等的许多区，把每个区称为“块”，块是进行主存空间分配的物理单位。同时，要求程序中的逻辑地址也进行分页，页的大小与块的大小一致。这样，就可把程序信息按页存放到块中。于是，页式存储器提供编程使用的逻辑地址由两部分组成：页号和页内地址。其格式为

页式存储的地址结构确定了内存分块的大小，也就决定了页面的大小。假定地址用m个二进制表示，其中页内地址部分占用n个二进制位，那么，每一个块的长度就是，也就是每一页有2ⁿ个字节。这时，页号部分占用了m-n位，所以，最大的程序可允许有2^（m-n）个页面。显然，

从地址结构来看，逻辑地址是连续的。逻辑地址从“0”开始（页号为“0”，页内地址也为“0”），当编址到2ⁿ-l时，第0页的页内地址的各位均为“1”，即占满了一个页面。下一个地址是2‘这时页号部分就为“1”，而页内地址部分又恢复到“0”，表示进入了第1页。再继续顺序编址，此时页内地址0~(2ⁿ-l)是属于第1页的。依此类推，一组顺序的逻辑地址结构将其自然地分页了。所以，用户编辑时无须考虑如何分页的问题，仍使用连续的逻辑地址即可。

5.4.2存储空间的分配与回收

页式存储管理分配内存空间以物理页面为单位，由于物理页面的大小是固定的，所以只要在内存分配表中具有可以指出哪些块已经分配、哪些块尚未分配以及当前剩余的空闲块数等三种不同的标识即可。

简单的内存分配表可以用一张“位示图”构成。假设内存的可分配区域被分成256块，则可用字长为32位的8个字作为“位示图”。位示图中的每一位与一个内存块对应，每一位的值可以是0或1，0表示对应的内存块为空闲，1表示已占用。在位示图中再增加一个字节记录当前剩余的总空闲块数，如图5-14所示。初始化时系统在位示图中把操作系统占用块所对应的位置成1，其余位均置0，剩余空闲块数为可分配的空闲内存块总数。

在进行内存分配时，先查看空闲块数是否能满足程序要求。若不能满足，则不进行分配，程序就不能装入内存;若能满足，则根据需求从位示图中找出一些为0的位，把这些位置成1，并从空闲块数中减去本次分配的块数，然后按照找到的位计算出对应的块号。

当找到一个为0的位后，根据它所在的字号、位号，按如下公式就可计算出对应的块号：

块号=字号x字长+位号

把程序装入到这些内存块中，并为该程序建立页表。

当程序执行结束时，则应收回它所占用的内存块。根据归还的块号计算出该块在位示图中对应的位置，将占用标志修改成0，再把回收的块数加入到空闲块数中。

假定归还块的块号为〖，则在位示图中对应的位置为：

5.4.3地址转换与快表

页式存储管理要有硬件的地址转换机构作支持。同时，要为每个被装入内存的进程提供一张页表，该页表所在内存的起始地址和长度作为现场信息存放在该进程的进程控制块中。一旦进程被调度进入处理器执行，这些信息将被作为恢复现场信息送入系统的地址映射机制中的寄存器里。

1.页式存储管理的地址转换

为了实现页式存储管理，系统要提供一对硬件的页表控制寄存器，即页表起始地址寄存器和页表长度寄存器，另外还需要高速缓冲存储器的支持。页表起始地址寄存器用于保存正在运行进程的页表在内存的首地址，当进程被调度程序选中投入运行时，系统将其页表首地址从进程控制块中取出送入该寄存器。页表长度寄存器用于保存正在运行进程的页表的长度，当进程被选中运行时，系统将它从进程控制块中取出送人该寄存器。

页表指出该程序逻辑地址中的页号与所占用的内存块号之间的对应关系。页表的长度由程序拥有的页面数而定，故每个程序的页表长度可能是不同的。

页表又是硬件进行地址转换的依据，每执行一条指令时按逻辑地址中的页号查页表。若页表中无此页号，则产生一个“地址错”的程序性中断事件。若页表中有此页号，则可得到对应的内存块号，按计算公式可转换成访问的内存的物理地址。

物理地址的计算公式为：

物理地址=内存块号x块长+页内地址

根据二进制乘法运算的性质，一个二进制数乘以2ⁿ结果实际上是将该数左移n位。所以，实际上是把内存块号作为绝对地址的高位地址，而页内地址作为它的低地址部分。地址转换关系如图5-15所示。

2.页表

1）多级页表

大多数现代计算机系统都支持很大的地址空间，由此带来的结果是页表本身也变得很大。例如，当系统支持32位的逻辑地址空间时，若页面大小为4KB，则页表将包含1M个表项。假设每个表项由4字节组成，那么仅仅是为了存储页表就要为每个进程分配4MB的物理地址空间。假设用户地址空间为2GB，页面大小为4KB，则一个进程最多可以有2¹⁹页。若用4字节表示一页的物理页号，则页表本身就占用2MB，即需要512个页面存放。称存放页表的页面为页表页。一般来说，页表页可以不连续存放，因此需要对页表页的地址进行索引。一个简单的解决办法就是分级，例如采用两级页表，即页面大小为4KB的32位机器，逻辑地址可被划分为10位页目录、10位页表和12位的页内偏移。

在大多数操作系统中采用二级页表，即由页表页和页目录一起构成进程页表。图5-16表示了二级页表结构。

其中，第一级表示页目录，保存页表页的地址;第二级表示页表页，保存物理页面号（即内存块号）。

不同的操作系统对一级页表和二级页表的命名略有不同，但是其物理意义是相同的。例如，在Windows操作系统中，图5-16中页目录被称为页目录项（Page Directory Entry,PDE)，页表被称为页表项（Page Table Entry，PTE)。

2）散列页表

当地址空间大于32位时，一种常见的方法是使用以页号为散列值的散列页表。其中每个表项都包含一个链表，该链表中元素的散列值都指向同一个位置。这样，散列页表中的每个表项都包含三个字段：（a）虚拟页号，（b）所映射的页框号，（c）指向链表中下一个元素的指针。

使用的算法如下：由虚拟页号得到散列值来查找散列页表，并将此页号与链表中的第一个元素的字段（a）进行比较。如果匹配，则相应的页框号[字段（b）]就可用于形成物理地址。如果不匹配，则沿链表依次寻找相匹配的表项。

将上述方法稍作改变而得到的集群页表更适用于64位的地址空间。它与散列页表相似，不过其中每个表项代表了多个（例如16个）页面而不是一个。这样，一个页表项就存储了多个物理页框的映射信息。对于散布于整个地址空间的不连续内存访问来说，这种集群页表非常有效。

3）反置页表

通常，每个进程都有与之相关的页表，进程正在使用的每个页面在页表中都有一个表项，进程根据页面的虚拟地址对其进行访问，因此这种表示方法是很自然的。但是这种方法也有其缺点，即每个页表都含有上百万个表项，仅仅为了记录内存的使用情况就消耗了大量物理内存。

为了解决这个问题，可以使用反置页表。在反置页表中，每个物理页框对应一个表项，每个表项包含与该页框相对应的虚拟页面地址以及拥有该页面进程的信息。因此，整个系统中只存在一个页表，并且每个页框对应其中一个表项。由于一方面系统中只有一个页表，而另一方面系统中又存在着多个映射着物理内存的地址空间，因此需要在反置页表中存放地址空间标志符。这样就保证了一个特定进程的逻辑页面可以映射到相应的物理页框上。64位的UltraSPARC和PowerPC都是使用反置页表的实例。

尽管这种方法减少了为存放每个页表所使用的内存数量，但却增加了内存访问时的查表时间。由于反置页表是按照物理地址排序的，而在使用时却是按照虚拟地址查找，因此有可能为了寻找相匹配的表项而遍历全表。

3.快表

一般而言，页式存储管理中的页表是存放在内存中的。于是，当要按给定的逻辑地址进行读写时，必须访问两次内存。第一次按页号读出页表中对应的块号，第二次按计算出来的绝对地址进行读写。两次访问内存显然延长了指令的执行周期，降低了执行速度。

为了提高存取速度，有两种方法。一种是在地址映射机制中增加一组高速寄存器保存页表，这需要大量的硬件开销，在经济上不可行。另一种方法是在地址映射机制中增加一个小容量的联想寄存器（相联存储器），它由高速缓冲存储器组成。

利用高速缓冲存储器存放当前访问最频繁的少数活动页面的页号，这个高速缓冲器被称为“快表”，也称为转换检测缓冲器（Translation Lookaside Buffer，TLB)。

快表中登记了页表中的一部分页号与内存块号的对应关系。根据程序的存储访问局部性原理，在一段时间内总是经常访问少数几页，若这些页登记在快表中，显然可快速查找并提高指令执行速度。

有了快表后，地址转换过程如图5-17所示。

快表只存放当前进程最活跃的少数几页，随着进程的推进，快表的内容动态进行更新。

快表内容的更新原理如下：当某一用户程序需要存取数据时，根据该数据所在的逻辑页号在快表中找出对应的内存块号，然后拼接页内地址，以形成物理地址；如果在快表中没有相应的逻辑页号，则地址映射仍然通过内存中的页表进行;在得到内存块号后需将该块号填到快表的空闲单元中；若快表中没有空闲单元，则根据置换算法置换某一行，再填入新得到的页号和块号。

实际上，查找快表和查找内存页表是并行进行的，一旦发现快表中有与所查页号一致的逻辑页号就停止查找内存页表，而直接利用快表中的逻辑页号。

采用快表后，地址转换的时间大大下降。假定访问内存的时间为200ns,访问高速缓冲存储器的时间为40ns，高速缓冲存储器为16个单元时，查快表的命中率为90%。于是，按逻辑地址转换成绝对地址进行存取的平均访问时间为：

(200+40)x90%+(200+200)x10%=256(ns)

不使用快表需两次访问内存的时间为200x2=400ns。可见使用快表与不使用快表相比，访问时间下降了36%。

5.5虚拟存储技术与虚拟页式存储管理方案的实现

虽然内存容量增长快速，但是各种软件的规模也在迅速膨胀。如何解决程序规模大于内存的问题？早期的解决方案如覆盖技术是由程序员指定，系统辅助完成的，对程序员的要求甚高，而且容易出错。所以根本的解决方法是将这类工作全部交给操作系统完成。这就产生了虚拟存储技术，本节介绍这一技术的基本思想，并重点介绍将虚拟存储技术与页式存储管理方案结合后的一种典型的、大多数操作系统采用的虚拟页式存储管理方案。

5.5.1虚拟存储技术

虚拟存储技术的基本思想是利用大容量的外存来扩充内存，产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间，简称虚存，以便能够有效地支持多道程序系统的实现和大型程序运行的需要，从而增强系统的处理能力。

虚拟存储管理是由操作系统在硬件支持下把两级存储器（内存和外存）统一实施管理，达到“扩充”内存的目的，呈现给用户的是一个远远大于内存容量的编程空间，即虚存。程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其他部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。虚拟存储管理支持多道程序设计技术。

虚拟存储器实际上是为扩大内存容量而采用的一种设计技巧。虚拟存储器的容量也是有限制的，主要是受外存容量所限。

实现虚拟存储器需要以下的硬件支持：

(1) 系统有容量足够大的外存。

(2) 系统有一定容量的内存。

(3) 最主要的是，硬件提供实现虚-实地址映射的机制。

虚拟存储器的工作原理如下：当进程开始运行时，先将一部分程序装入内存，另一部分暂时留在外存；当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存的工作；当没有足够的内存空间时，系统自动选择部分内存空间，将其中原有的内容交换到磁盘上，并释放这些内存空间供其他进程使用。这样做的结果是程序的运行丝毫不受影响，使程序在运行中感觉到拥有一个不受内存容量约束的、虚拟的、能够满足自己需求的存储器。

虚拟存储技术同交换技术在原理上是类似的，其区别在于在传统的交换技术中，交换到外存上的对象一般都是进程，也就是说交换技术是以进程为单位进行的，如果一个进程所需内存大于当前系统内存，那么该进程就不能在系统中运行。而虚拟存储一般是以页或段为单位，所以如果一个进程所需内存大于当前系统内存，那么该进程仍然可以在系统中正常运行，因为该进程的一部分可以被换出到外存上。下面介绍虚拟页式存储管理方案。

5.5.2虚拟页式存储管理

1.基本思想

在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其他页面；当内存空间已满，而又需要装人新的页面时，则根据某种算法置换出某个页面，以便装入新的页面。

在使用虚拟页式存储管理时需要在页表中增加以下的表项：

•页号——页面的编号。

•有效位——又称驻留位、存在位或中断位，表示该页是在内存还是在外存。

•页框号——页面在内存中时所对应的内存块号。

•访问位——又称引用位或参考位，表示该页在内存期间是否被访问过。

•修改位——表示该页在内存中是否被修改过。

•保护位——是否能读/写/执行。

•禁止缓存位——采用内存映射I/O的机器中需要的位。

等等。

其中，访问位和修改位可以用来决定置换哪个页面，具体由页面置换算法决定。

2.缺页中断

若在页表中发现所要访问的页面不在内存，则产生缺页中断。当发生缺页中断时，操作系统必须在内存中选择一个页面将其移出内存，以便为即将调人的页面让出空间。如果要移走的页面在内存期间已经被修改过，就必须把它写回磁盘以更新该页在磁盘上的副本。如果该页没有被修改过，那么它在磁盘上的副本仍然是最新的，则不需要写回，调入的页直接覆盖被置换的页。图5-18为缺页中断处理流程图。

整个缺页处理过程简单阐述如下：

(1) 根据当前执行指令中的逻辑地址查页表的驻留位，判断该页是否在内存。

(2) 该页标志为“0”，形成缺页中断。保留现场。中断装置通过交换PSW让操作系统的中断处理程序占用处理器。

(3) 操作系统处理缺页中断，寻找一个空闲的页面。

(4) 若有空闲页，则把磁盘上读出的信息装入该页面中。

(5) 修改页表及内存分配表，表示该页已在内存。

(6) 如果内存中无空闲页，则按某种算法选择一个已在内存的页面，把它暂时调出内存。若在执行中该页面已被修改过，则要把该页信息重新写回到磁盘上，否则不必重新写回磁盘。当一页被暂时调出内存后，让出的内存空间用来存放当前需要使用的页面。页面被调出或装入之后都要对页表及内存分配表作修改。

(7) 恢复现场，重新执行被中断的指令。当重新执行该指令时，由于要访问的页面已被装人内存，所以可正常执行下去。

3.页面调度策略

虚拟存储器系统通常定义三种策略来规定如何（或何时）进行页面调度：调入策略，置页策略和置换策略。

1) 调入策略

虚拟存储器的调入策略决定了什么时候将一个页由外存调入内存之中。在虚拟页式管理中有两种常用调入策略：

•请求调页（Demand Paging):只调入发生缺页时所需的页面。这种调入策略实现简单，但容易产生较多的缺页中断，造成对外存i/o次数多，时间开销过大，容易产生抖动现象。

•预调页（Prepaging):在发生缺页需要调入某页时，一次调入该页以及相邻的几个页。这种策略提高了调页的i/o效率，减少了I/O次数。但由于这是一种基于局部性原理的预测，若调入的页在以后很少被访问，则造成浪费。这种方式常在程序装入时使用。

通常对外存交换区的i/o效率比文件区的高。关于调人页面来源，通常有两种做法：

进程装入时，将其全部页面复制到交换区，以后总是从交换区调入。执行时调入速度快，要求交换区空间较大。

凡是未被修改的页面，都直接从文件区读入，而被置换时不需调出；已被修改的页面，被置换时需调出到交换区，以后从交换区调入。这种方式节省交换区空间，但也可能引发某些问题，如装入可执行文件a从而创建进程P，如果在P执行时，改写了可执行文件_a(如重新编译和链接，不包括用touch命令使文件的最后修改时间变得更晚），而此后P发生缺页需要从a中调入页面，则可能会因为各个页面内容无法配合而出错。

2) 置页策略

当线程产生缺页中断时，内存管理器还必须确定将调人的虚拟页放在物理内存的何处。用于确定最佳位置的一组规则称为“置页策略”。选择页框应使CPU内存高速缓存不必要的震荡最小。

3) 置换策略

如果缺页中断发生时物理内存已满，“置换策略”被用于确定哪个虚页面必须从内存中移出，为新的页面腾出空位。在虚拟页式存储管理方案中，可采用两种分配策略，即固定分配策略和可变分配策略。在进行置换时，也可以采用两种策略，即全局置换和局部置换。将它们组合起来，有如下三种策略：

•固定分配局部置换（Fixed Allocation,Local Replacement)。可基于进程的类型，为每一进程分配固定的页数的内存空间，在整个运行期间都不再改变。采用该策略时，如果进程在运行中出现缺页，则只能从该进程的W个页面中选出一个换出，然后再调入一页，以保证分配给该进程的内存空间不变。

•可变分配全局置换（Variable Allocation,Global Replacement)。采用这种策略时，先为系统中的每一进程分配一定数量的物理块，操作系统本身也保持一个空闲物理块队列。当某进程发生缺页时，由系统的空闲物理块队列中取出一物理块分配给该进程。但当空闲物理块队列中的物理块用完时，操作系统才从内存中选择一块调出。该块可能是系统中任意一个进程的页。

•可变分配局部置换（Variable Allocation,Local Replacement)。同样基于进程的类型，为每一进程分配一定数目的内存空间。但当某进程发生缺页时，只允许从该进程的页面中选出一页换出，这样就不影响其他进程的运行。如果进程在运行的过程中频繁地发生缺页中断，则系统再为该进程分配若干物理块，直到进程的缺页率降低到适当程度为止。

下面简单讨论一下置换时机问题。

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

4.页面置换算法

每次发生缺页时，当然可以随机选择一个页面置换。但是如果一个经常使用的页被置换出去，很有可能它很快又要被调人内存，带来不必要的额外开销。所以选择不常使用的页面会使系统性能好得多。

如果刚被调出的页面又立即要用，因而又要把它装入，而装入不久又被选中调出，调出不久又被装入，如此反复，使调度非常频繁。这种现象称为“抖动”或称“颠簸”。

页面置换算法的优劣将会影响虚拟存储系统的性能，进而影响整个系统的性能。下面将介绍几个主要的页面置换算法。

1）先进先出页面置换算法（First-In First-Out，FIFO)

为了解释它是怎样工作的，设想有一个超市，它的货架只能展示k种不同的商品。有一天，某家公司介绍了一种新的方便食品，这个产品非常好，所以容量有限的超市必须撤掉一种老商品以便能够展示该新产品。

一种可能的解决方法就是找到超市中销售时间最长的商品并将其撤换掉（比如某个10年以前就开始卖的商品），理由是现在已经没有人喜欢它了。这实际上相当于超市有一个按照引进时间排列的所有商品的链表，新的商品加到链表的尾部，链表头上的商品被撤换掉。

同样的思想也可以应用在页面置换算法中。先进先出页面置换算法总是选择最先装入内存的一页调出，或者说是把驻留在内存中时间最长的一页调出。

FIFO算法简单，容易实现。把装人内存的那些页面的页号按进入的先后次序排好队列，每次总是调出队首的页，当装入一个新页后，把新页的页号排人队尾。由操作系统维护一个所有当前在内存中的页面的链表，最老的页面在表头，最新的页面在表尾。当发生缺页时，置换表头的页面并把新调人的页面加到表尾。

在具体实现时，可用指针K指示最早被装入内存的那页在队列中的位置，每次总是选择指在针K指示的页调出，在装入一个新页后，在指针指示的位置上填上新页页号，然后指针尺加1，指出下一次可调出的页。图5-19是先进先出调度算法的示例。

图5-21中，指针尺指示页面1，表示页面1是最早装入内存的页面。现在需要调入页面6，于是页面1被换成页面6，而指针K加1，指出下一次可调出的页，即页面3。

这里，指针K是循环指针。假定页号队列中有n个页号，每次调出一页后，执行

K：=(K+1) mod n

于是K指示的位置就是页号队列的队首，而新装人的那页所在的位置就成了队尾。

FIFO算法有一个问题，因为最先装入内存的一页，不等于说这一页是不常使用的。用在超市时，FIFO算法可能会置换羽毛球拍，但也可能会置换掉面包、牛奶或其他常用商品。由于这一原因，很少使用纯FIFO算法。

2）最近最少使用页面置换算法（Least Recently Used,LRU)

通常，在前面几条指令中使用频繁的页面很可能在后面的几条指令中也频繁使用。反过来说，已经很久没有使用的页面很有可能在未来较长的一段时间内不会被用到。这个思想提示了一个可以实现的算法：在缺页发生时，首先置换掉最长时间未被使用过的页面。这个策略称为LRU页面置换算法。

最近最少使用页面置换算法总是选择距离现在最长时间内没有被访问过的页面先调出。实现这种算法的一种方法是在页表中为每一页增加一个“计时”标志，记录该页面自上次被访问以来所经历的时间，每被访问一次都应从“0”开始重新计时。当要装入新页时，检查页表中各页的计时标志，从中选出计时值最大的那一页调出（即最近一段时间里最长时间没有被使用过的页），并且把各页的计时标志全置成“0”，重新计时。当再一次产生缺页中断时，又可找到最近最久未使用过的页，将其调出。这种实现方法必须对每一页的访问情况时时刻刻地加以记录和更新，实现起来比较麻烦且开销比较大。

3）最近最不常用页面置换算法（Least Frequently Used,LFU)

最近最不常用调度算法是根据在一段时间里页面被使用的次数选择可以调出的页，如果一个页面被访问的次数比较多，则是经常要使用的页面，就不应该把它调出。所以，这种算法总是选择被访问次数少的页面调出。

最近最不常用调度算法的一种简单的实现方法是为每一页设置一个计数器，每当访问一页时，就把该页对应的计数器加1。另外，操作系统还要确定一个周期在周期r的一段时间内，若没有发生缺页中断，则把所有的计数器清“0”，开始一个新的周期重新计数。若在周期r的时间内发生了缺页中断，则选择计数值最小的那页调出（它是最近一段时间内最不常用的页），同时把所有的计数器清“0”。这个算法的实现要花很大的开销，并且要确定一个合适的周期r也有一定的难度。

4）理想页面置换算法（OPT)

该算法置换以后不再需要的或者在最长时间以后才会用到的页面。这一算法一般不可能实现，但它可以作为衡量其他页面置换算法优劣的一个标准。

5）最近未使用页面置换算法（NRU)

为使操作系统能够收集有用的统计信息，在大部分支持虚存的计算机中，硬件为每一页面设置了两个状态位。当访问页面（读或写）时设置R位；当写人页面（即修改页面）时设置M位。这些位包含在页表项中。如果硬件没有这些位，则对其进行软件模拟。

用R位和M位可以构造一个简单的页面置换算法：当启动一个进程时，它的所有页面的两个位都由操作系统设置成0，定期将R位（比如在每次时钟中断时）清零，以区别最近没有被访问的页面和被访问的页面。

当发生缺页中断时，操作系统检查所有的页面并根据它们当前的R位和M位的值，把它们分为如下4类：

第0类：没有被访问，没有被修改。

第1类：没有被访问，已被修改_Q

第2类：巳被访问，没有被修改。

第3类：已被访问，已被修改。

尽管第1类初看起来似乎是不可能的，但是一个第3类的页面在它的R位被时钟中断清零后就成了第1类。时钟中断不会清除M位，因为在决定一个页面是否需要写回磁盘时将用到这个信息。清除R位而不清除M位产生了第1类页面。

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

6）第二次机会页面置换算法

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

这一算法称为第二次机会（SecondChance)算法，其基本思想是寻找一个最近的时钟间隔以来没有被访问过的页面。如果所有的页面都被访问过了，该算法就退化为FIFO算法。

7）时钟页面置换算法（Clock)

尽管第二次机会算法是一个比较合理的算法，但它经常要在链表中移动页面，既降低了效率又不是很有必要。一个更好的办法是把所有的页面都保存在一个类似时钟面的环形链表中，一个表针指向最老的页面。当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就置换该页面，并把新的页面插入这个位置，然后把表针前移一个位置;如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到一个R位为0的页面为止。由于这个算法的工作方式，就将它称为时钟（Clock)算法。

下面举例说明页面置换算法的应用。

例1  （a）某程序在内存中分配三个页面，初始为空，所需页面的走向为4，3，2，1，4，3，5，4，3,2,1,5，采用FIFO算法，请计算整个缺页次数。

下面用“时间长-页”表示在内存时间最长的页面，“时间中-页”其次，“时间短-页”表示在内存时间最短的页面。x表示缺页，√表示不缺页。

开始时，内存中三个页面初始为空，故产生第1个缺页中断，需要把页面4调入。同样产生第2个缺页中断，需要把页面3调入。产生第3个缺页中断，需要把页面2调入。

此时3个内存页面全满。在需要页面1时，发现页面4时间最长，故产生第4个缺页中断，把页面4换出，页面1调入。接着又需要页面4，于是产生第5个缺页中断，把页面3换出，页面4调入。后面又需要页面3，于是产生第6个缺页中断，把页面2换出，页面3调入。接着又需要页面5，于是产生第7个缺页中断，把页面1换出，页面5调入。

下面需要页面4，正好在内存。接着需要页面3，也正好在内存。后面需要页面2，于是产生第8个缺页中断，把页面4换出，页面2调入。接着需要页面1，于是产生第9个缺页中断，把页面3换出，页面1调入。最后需要页面5，正好在内存。整个操作结束，共产生缺页中断9次。

（b）在上述例子中采用LRU算法，请计算整个缺页次数。

同样，用“时间长-页”表示未使用时间最长的页面，“时间中-页”其次，“时间短-页”表示未使用时间最短的页面。

共缺页中断10次。

（c）在上述例子中采用OPT算法，请计算整个缺页次数。

最长时间以后才会用到的页面，用“时间长-页”表示，“时间中-页”其次，“时间短-页”表示最短时间会用到的页面。

共缺页中断7次。

例2某程序在内存中分配m页初始为空，页面走向为1，2，3，4，1，2，5，1，2，3，4，5。当m=3、m=4时，试用FIFO算法计算缺页中断分别为多少次？说明所出现的现象。

通过计算得到当w=3时缺页中断9次，m=4时缺页中断10次。

我们发现，当分配给进程的物理页面数增加时，缺页次数反而增加。这一现象称为贝莱迪异常（BeladyAnomaly)现象，FIFO页面置换算法会产生异常现象。

5.缺页中断率

假定一个程序共有〃页，系统分配给它的内存块是w块（爪、〃均为正整数，且^爪因此，该程序最多有m页可同时被装入内存。如果程序执行中访问页面的总次数为1其中有F次访问的页面尚未装入内存，故产生了F次缺页中断。现定义_：

f=F/A

把f称为“缺页中断率”。

显然，缺页中断率与缺页中断的次数有关。因此，影响缺页中断率的因素如下：

1）分配给程序的内存块数

分配给程序的内存块数多，则同时装人内存的页面数就多，故减少了缺页中断的次数，也就降低了缺页中断率。反之，缺页中断率就高。

从原理上说₇每个程序只要能得到一块内存空间就可以开始执行了。这样可增加同时执行的程序数，但实际上仍是低效的，因每个程序将频繁地发生缺页中断。如果为每个程序分配很多的内存块，则又减少了可同时执行的程序数，影响系统效率。根据试验分析，对一共有n页的程序来说，只要能分到〃/2块内存空间时才把它装入内存执行，那么，可使系统获得最高效率。

2）页面的大小

页面的大小取决于内存分块的大小，块大则页面也大，每个页面大了则程序的页面数就少。装人程序时是按页存放在内存中的，因此，装入一页的信息量就大，就减少了缺页中断的次数，降低了缺页中断率。反之，若页面小则缺页中断率就高。

对不同的计算机系统，页的大小可以不相同。一般说来，页的大小在2⁹(512字节）至2¹⁴(16384字节）之间。有的系统还提供几种分页方式供选择。

3）程序编制方法

怎样编制程序也是值得探讨的，程序编制的方法不同，对缺页中断的次数有很大影响。

例如，有一个程序要把128x128的数组置初值“0”，数组中的每个元素为一个字。现假定页面的大小为每页128个字，数组中的每一行元素存放在一页中。能供这个程序使用的内存块只有一块，开始时把第一页装入了内存。若程序如下编制：

VARA：ARRAY[1..128,1..128]OFINTEGER；

FORj：=1TO128DO

FORi：=1TO128DOA[i,j]:=0；

则由于程序是按列把数组中的元素清“0”的，所以，每执行一次A[i，j]:=0就会产生一次缺页中断。因为开始时第一页已在内存了，故程序执行时就可对元素A[l，l]清“0”，但下一个元素A[2，l]不在该页中，就产生缺页中断。按程序上述的编制方法，每装入一页只对一个元素清

“0”后就要产生缺页中断，于是总共要产生（128x128-1)次缺页中断。

如果重新编制这个程序如下：

VARA：ARRAY[1..128,1..128]OFINTEGER；

FORi：=1TO128DO

FORj：=1TO128DOA[i,j]：=0；

那么，每装入一页后就对一行元素全部清“0”后才产生缺页中断，故总共产生（128-1)次缺页中断。

可见，缺页中断率与程序的局部化程度密切相关。一般说来，希望编制的程序能经常集中在几个页面上进行访问，以减少缺页中断率。

4）页面置换算法

页面置换算法对缺页中断率的影响也很大，调度不好就会出现“抖动”。理想的调度算法(OPT)能使缺页中断率最低。然而，因为谁也无法对程序执行中要使用的页面作出精确的断言，因此这种算法是无法实现的。不过，这个理论上的算法可作为衡量各种具体算法的标准。据估计，采用FIFO置换算法产生的缺页中断率约为最佳算法的三倍。

6.虚拟存储管理的性能问题

引人虚拟存储管理，把内存和外存统一管理，其真正目的，是把那些访问概率非常高的页放人内存，减少内外存交换的次数。

在虚存中，页面可能在内存与外存之间频繁地调度，有可能出现抖动或颠簸。当系统出现这一现象时，系统用于调度页面所需要的时间比进程实际运行所占用的时间还多，系统效率会急剧下降。

颠簸是由于缺页率高而引起的。例如，由于页面置换算法不合理，可能出现刚被置换出去的一页又要被访问，因而又要把它调入的情况，如此反复，使整个系统的页面调入调出非常频繁。

此外，一般进程在一段时间内集中访问一些页面，称为“活动”页面，这是与程序的局部性有关的。如果分配给一个进程的内存物理页面数太少，使得该进程所需要的“活动”页面不能全部装入内存，则进程在运行过程中可能会频繁地发生缺页中断，从而产生颠簸。

采用工作集模型，可以解决颠簸问题。

对于给定的进程访页序列，从时刻到时刻t之间所访问页面的集合，称为该进程的工作集。其中，d称为工作集窗口。

工作集是随时间而变化的，如图5-20所示。工作集大小与窗口尺寸密切相关。

?₁={1,2,5,6,7}

由模拟实验知道，任何程序对内存都有一个临界值要求，当分配给进程的物理页面数小于这个临界值时，缺页率上升；当分配给进程的物理页面数大于该临界值时，再增加物理页面数也不能显著减少缺页次数。因此，希望分配给进程的物理页面数与当•前工作集大小一致。

在实现时，操作系统为每一个进程保持一个工作集，并为该进程提供与工作集大小相等的物理页面数,这一过程可动态调整。统计工作集大小一般由硬件完成，系统开销较大。

5.5.3段式与段页式存储管理方案

1.段式存储管理方案

1）设计思想

系统将内存空间动态划分为若干个长度不同的区域，每个区域称作一个物理段。每个物理段在内存中有一个起始地址，称作段首址。将物理段中的所有单元从0开始依次编址，称为段内地址。

而用户程序则按逻辑上有完整意义的段来划分，称为逻辑段（简称段），例如主程序、子程序、数据等都可各成一段，每段对应于一个过程、一个程序模块或一个数据集合。将一个用户程序的所有逻辑段从0开始编号，称为段号。将一个逻辑段中的所有单元从0开始编址，称为段内地址。用户程序的逻辑地址由段号和段内地址两部分组成。

内存分配时，系统以段为单位进行内存分配，为每一个逻辑段分配一个连续的内存区（物理段）。逻辑上连续的段在内存中不一定连续存放。

操作系统为了实现段式管理，需要建立段表。当把程序装入内存后，系统为每个用户程序建立一张段表，用于记录用户程序的逻辑段与内存物理段之间的对应关系。段表包括逻辑段号、物理段起始地址（段首址）和物理段长度三项内容。用户程序有多少逻辑段，该段表里就登记多少行，且按逻辑段的顺序排列。段表存放在内存系统区里。

2）地址转换

与页式存储管理相同，为了实现段式管理，系统提供一对寄存器：段表起始地址寄存器和段表长度寄存器。其中，段表起始地址寄存器用于保存正在运行进程的段表在内存的首地址。当进程被调度程序选中投入运行时，系统将其段表首地址从进程控制块中取出送入该寄存器。而段表长度寄存器用于保存正在运行进程的段表的长度。当进程被选中运行时，系统将它从进程控制块中取出送入该寄存器。用户程序运行时，系统根据用户程序提供的逻辑地址和两个寄存器的内容，形成一个访问内存的物理地址。同样，为了加快地址映射，亦可以采用快表技术。为此，系统设置一组相联存储器，用于保存正在运行进程段表的活跃子表。有了这些支持，就可以完成地址映射。

3）与可变分区管理方案的比较

段式存储管理分配内存空间的方法与可变分区管理方案的分配方法相同，有相同结构的内存分配表，包括巳分配区表和空闲区表。与可变分区管理方案不同的是，段式存储管理是为程序的每一个分段分配一个连续的内存空间。空闲区的分配也可以采用首先适应算法、最佳适应算法、最坏适应算法。进行内存分配时，根据段长找出一个可容纳该段的一个空闲区，分割这个空闲区，一部分用来装人该段信息，另一部分仍为空闲区。当没有一个足够大的空闲区时，仍可采用拼接技术来合并分散的空闲区。程序执行结束时，要收回该程序各段所占用的内存区域，使其成为空闲区，回收存储空间的方法与可变分区管理方案相同。

2.段页式存储管理方案

段式存储管理为用户提供了一个二维地址空间，满足程序和信息的逻辑分段的要求^段式管理反映了程序的逻辑结构，有利于段的动态增长以及共享和内存保护等，这大大地方便了用户。而页式存储管理的特征是等分内存，有效地克服了碎片，提高了存储器的利用率。从存储管理的目的来讲，主要是方便用户的程序设计和提高内存的利用率。为了保持页式在存储管理上的优点和段式在逻辑上的优点，结合页式和段式两种存储管理方案，形成了段页式存储管理。

段页式存储管理的基本思想是:用页式方法来分配和管理内存空间，即把内存划分为若干大小相等的页面;用段式方法对用户程序按照其内在的逻辑关系划分成若干段;再按照划分内存页面的大小，把每一段划分成若干大小相等的页面。内存是以页为基本单位分配给每个用户程序的，逻辑上相邻的页面在物理内存中不一定相邻。

采用段页式存储管理方案时，一个进程仍然拥有一个自己的二维地址空间，这与段式管理时相同。首先，一个进程中所包含的具有独立逻辑功能的程序或数据仍被划分为段，并有各自的段号。这反映和继承了段式管理的特征。其次，对于段中的程序或数据，则按照一定的大小将其划分为不同的页。和页式系统一样，最后不足一页的部分仍占一页。这反映了段页式管理中的页式特征。

由于内存空间的最小单位是页而不是段，从而内存可用区也就被划分成为若干个大小相等的页面，且每段所拥有的程序和数据在内存中可以分开存放。分段的大小不再受内存可用区的限制。

为了实现段页式管理，需要增加段式管理和页式管理的成分：系统必须为每个程序建立一张段表；由于一个段又被划分成了若干页，系统又为每个段建立一张页表。段表中记录了该段对应页表的起始地址和长度；而页表则给出该段的各个逻辑页面与内存块号之间的对应关系。

当然，也需要采用位示图法建立内存分配表，用于记录并管理内存空闲块。

在进行动态地址转换时，硬件提供段表起始地址寄存器、段表长度寄存器等支持。

计算机四级操作系统-5-内存管理

原文：https://www.cnblogs.com/jtd666/p/12505402.html