【文档说明】计算机操作系统教程_第四版_第5章课件.ppt，共(104)页，578.248 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-76770.html

以下为本文档部分文字说明：

计算机操作系统教程_第四版_第5章•存储器是计算机系统的重要资源之一。因为任何程序和数据以及各种控制用的数据结构都必须占用一定的存储空间，因此，存储管理直接影响系统性能。•存储器由内存(primarysrotage)和外

存(secondarystorage)组成。内存由顺序编址的块组成，每块包含相应的物理单元。CPU要通过启动相应的输入输出设备后才能使外存与内存交换信息。本章主要讨论内存管理问题。•主要包括：几种常用的内存管理方法、内存的分配和释放算法

、虚拟存储器的概念、控制主存和外存之间的数据流动方法、地址变换技术和内存数据保护与共享技术等。5.1.1虚拟存储器•虚拟存储器是存储管理的核心概念。•实验证明，在一个进程的执行过程中，其大部分程序和数据并不经常被访问。这样，存储管理系统把进

程中那些不经常被访问的程序段和数据放入外存中，待需要访问它们时再将它们调入内存。那么，对于那些一部分数据和程序段在内存而另一部分在外存的进程，怎样安排它们的地址呢？•通常由用户编写的源程序，首先要由编译程序编译成CP

U可执行的目标代码。然后，链接程序把一个进程的不同程序段链接起来以完成所要求的功能。显然，对于不同的程序段，应具有不同的地址。•将进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器(virtualstore或virtualmemory)。虚拟存储器不考虑物理存储器的大小和信息存放的实际

位置，只规定每个进程中互相关连信息的相对位置。与实际物理存储器数量有限，且被所有进程共享不一样，每个进程都拥有自己的虚拟存储器，且虚拟存储器的容量是由计算机的地址结构和寻址方式确定的。•直接寻址时，如果CPU的有效地址长度为16位，则

其寻址范围为0到64K。•图中，编译和链接主要是语言系统的设计问题，而虚拟存储器到物理存储器的变换是操作系统必须解决的问题。要实现这个变换，必须要有相应的硬件支持，并使这些硬件能够完成统一管理内存和外存之间数据和程序段自动交换的虚拟存储器功能。

即，由于每个进程都拥有自己的虚存，且每个虚存的大小不受实际物理存储器的限制，因此，系统不可能提供足够大的内存来存放所有进程的内容。内存中只能存放那些经常被访问的程序和数据段等。这就需要有相当大的外部存储器，以存储那些不经常

被访问或在某一段时间内不会被访问的信息。待到进程执行过程中需要这些信息时，再从外存中自动调入主存。图5.1地址变换与物理存储器5.1.2地址变换•内存地址的集合称为内存空间或物理地址空间。内存中，每一个存储单元都与相应的称为内存地址

的编号相对应。显然，内存空间是一维线性空间。•虚存的一维线性空间或多维线性空间变换到内存的唯一的一维物理线性空间所涉及的两个问题：•第一个问题是虚拟空间的划分问题。•虚拟空间的划分使得编译链接程序可以把不同的程序模块(它们可能是用

不同的高级语言编写的)，链接到一个统一的虚拟空间中去。虚拟空间的划分与计算机系统结构有关。•VAX-11型机中的虚拟空间就是划分为进程空间和系统空间两大部分，而进程空间又更进一步划分为程序区和控制区。VAX-11的虚拟空间容量为232单元，其中程序区占23

0单元，用来存放用户程序，程序段以零为基址动态地向高地址方向增长，最大可达230-1号单元。控制区也占230个单元，存放各种方式和状态下的堆栈结构及数据等，其虚拟地址由231-1号地址开始由高向低地址方向增长。系统空间占2

31个单元，用来存放操作系统程序。图5.2VAX-11机虚拟空间的划分•第二个问题是把虚拟空间中已链接和划分好的内容装入内存，并将虚拟地址映射为内存地址的问题，称之为地址重定位或地址映射。•地址映射就是要建立虚拟地址与内存地址的关系。实现地址重定位或地址映射的方法有两

种：静态地址重定位和动态地址重定位。•静态地址重定位(staticaddressrelocation)是在虚拟空间程序执行之前由装配程序完成地址映射工作。•对于虚拟空间内的指令或数据来说，静态地址重定位只完成一个首地址不同的连续地址变换。•它要求所有待执行的程序必须在执行

之前完成它们之间的链接，否则将无法得到正确的内存地址和内存空间。•优点是不需要硬件支持。•缺点1：使用静态重定位方法进行地址变换无法实现虚拟存储器。•缺点2：必须占用连续的内存空间，这就难以做到程序和数据的共享。•动

态地址重定位(dynamicaddressrelocation)是在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换成内存地址。动态重定位依靠硬件地址变换机构完成。地址重定位机构需要一个(或多个)

基地址寄存器BR和一个(或多个)程序虚拟地址寄存器VR。指令或数据的内存地址MA与虚拟地址的关系为：MA=(BR)+(VR)这里，(BR)与(VR)分别表示寄存器BR与VR中的内容。动态重定位过程可参看图5.3。图5.3动态地址重定

位•动态重定位的具体过程：•设置基地址寄存器BR，虚拟地址寄存器VR。•将程序段装入内存，且将其占用的内存区首地址送BR中。例如，在图5.3中，(BR)=1000。•在程序执行过程中，将所要访问的虚拟地址送入VR中，例如在图5.3中执行LOADA50

0语句时，将所要访问的虚拟地址500放入VR中。•地址变换机构把VR和BR的内容相加，得到实际访问的物理地址。•动态重定位的主要优点有：•可以对内存进行非连续分配。显然，对于同一进程的各分散程序段，只要把各程序段在内存中的首

地址统一存放在不同的BR中，则可以由地址变换机构变换得到正确的内存地址。•动态重定位提供了实现虚拟存储器的基础。因为动态重定位不要求在作业执行前为所有程序分配内存，也就是说，可以部分地、动态地分配内存。

从而，可以在动态重定位的基础上，在执行期间采用请求方式为那些不在内存中的程序段分配内存，以达到内存扩充的目的。•有利于程序段的共享。5.1.3内外存数据传输的控制要实现内存扩充，在程序执行过程中，内存和外存之间必须经常地交换数据。也就是说，把那些即将执行的程序和数据段调

入内存，而把那些处于等待状态的程序和数据段调出内存。那么，按什么样的方式来控制内存和外存之间的数据流动呢?最基本的控制办法有两种。一种是用户程序自己控制，另一种是操作系统控制。•用户程序自己控制内外存之间的数据交换的例子是覆盖(overla

y)。覆盖技术要求用户清楚地了解程序的结构，并指定各程序段调入内存的先后次序。覆盖是一种早期的主存扩充技术。使用覆盖技术，用户负担很大，且程序段的最大长度仍受内存容量限制。因此，覆盖技术不能实现虚拟存储器。•操作系统控制方式又可进一步分为两种。一种是交换(swapping)

方式，另一种是请求调入(ondemand)方式和预调入(onprefetch)方式。•交换方式由操作系统把那些在内存中处于等待状态的进程换出内存，而把那些等待事件已经发生、处于就绪态的进程换入内存。•请求调入方式是在程序执行时，如果所要访问的程序段或数据段不在内存中，则操作系统自动地从外存将有关

的程序段和数据段调入内存的一种操作系统控制方式。而预调入则是由操作系统预测在不远的将来会访问到的那些程序段和数据段部分，并在它们被访问之前系统选择适当的时机将它们调入内存的一种数据流控制方式。•由于交换方式一般不进行部分交换，即每次交换都交换那些除去常驻内

存部分后的整个进程，而且，即使能完成部分交换，也不是按照执行的需要而交换程序段，只是把受资源限制、暂时不能执行的程序段换出内存。因此，虽然交换方式也能完成内存扩充任务，但它仍未实现那种所谓自动覆盖、内存和外存统一管理、进程大小不受内存容量限制的虚拟存储器

。只有请求调入方式和预调入方式可以实现进程大小不受内存容量限制的虚拟存储器。5.1.4内存的分配与回收内存的分配与回收是内存管理的主要功能之一。无论采用哪一种管理和控制方式，能否把外存中的数据和程序调入内存，取决于能否在内存中为它们安排合适的位置。因此，存储管理模块要为每

一个并发执行的进程分配内存空间。另外，当进程执行结束之后，存储管理模块又要及时回收该进程所占用的内存资源，以便给其他进程分配空间。为了有效合理地利用内存，设计内存的分配和回收方法时，必须考虑和确定以下几

种策略和数据结构：(1)分配结构：登记内存使用情况，供分配程序使用的表格与链表。例如内存空闲区表、空闲区队列等。(2)放置策略：确定调入内存的程序和数据在内存中的位置。这是一种选择内存空闲区的策略。(3)交换策略：在需要将某个程序段和数据调入内存时，如果内存中没有足

够的空闲区，由交换策略来确定把内存中的哪些程序段和数据段调出内存，以便腾出足够的空间。(4)调入策略：外存中的程序段和数据段什么时间按什么样的控制方式进入内存。调入策略与5.1.3节中所述内外存数据流动控制方式有关。(5)回收策略：回

收策略包括二点，一是回收的时机，二是对所回收的内存空闲区和已存在的内存空闲区的调整。5.1.5内存信息的共享与保护内存信息的共享与保护也是内存管理的重要功能之一。在多道程序设计环境下，内存中的许多用户或系统程序和数据段

可供不同的用户进程共享。这种资源共享将会提高内存的利用率。但是，反过来说，除了被允许共享的部分之外，又要限制各进程只在自己的存储区活动，各进程不能对别的进程的程序和数据段产生干扰和破坏，因此须对内存中的程序和数据段采取保护措施。

常用的内存信息保护方法有硬件法、软件法和软硬件结合三种：(1)上下界保护法是一种常用的硬件保护法。上下界存储保护技术要求为每个进程设置一对上下界寄存器。上下界寄存器中装有被保护程序和数据段的起始地址和终止地址。在程序执

行过程中，在对内存进行访问操作时首先进行访址合法性检查，即检查经过重定位后的内存地址是否在上、下界寄存器所规定的范围之内。若在规定的范围之内，则访问是合法的；否则是非法的，并产生访址越界中断。图5.4上、下界寄存器保护法(2)保护键法也是一种常用的存储保护法。保护键法为每一个被保护存储块

分配一个单独的保护键。在程序状态字中则设置相应的保护键开关字段，对不同的进程赋予不同的开关代码和与被保护的存储块中的保护键匹配。保护键可设置成对读写同时保护的或只对读，写进行单项保护的。例如，图5.5中的保护键0，就是对2K到4K的存储区进行读

写同时保护的，而保护键2则只对4K到6K的存储区进行写保护。如果开关字与保护键匹配或存储块未受到保护，则访问该存储块是允许的，否则将产生访问出错中断。图5.5保护键保护法(3)界限寄存器与CPU的用户态或核心态工作方式相结合的保护方式。在这种保护模式下，用户

态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空间。UNIX系统就是采用的这种内存保护方式。5.2分区存储管理分区管理是把内存划分成若干个大小不等的区域，除操作系统占用一个区域之外，其余由多道环境下的各并发进程共享。分区

管理是满足多道程序设计的一种最简单的存储管理方法。5.2.1分区管理基本原理分区管理的基本原理是给每一个内存中的进程划分一块适当大小的存储区，以连续存储各进程的程序和数据，使各进程得以并发执行。按分区的时机，分区管理可以分为固定分区和动态分区两种方法。1.固定分区法固定

分区法就是把内存区固定地划分为若干个大小不等的区域。分区划分的原则由一般系统操作员或操作系统决定。例如可划分为长作业分区和短作业分区。分区一旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变。系统对内存的管理和控制通过数据结

构——分区说明表进行，分区说明表说明各分区号、分区大小、起始地址和是否是空闲区(分区状态)。内存的分配释放、存储保护以及地址变换等都通过分区说明表进行。图5.6给出了固定分区时分区说明表和对应内存状态的例子。图5.6固定分区法图中，操作系统占用低地址部分的20K，其余空间被划分为4个

分区，其中1，2，3号分区已分配，4号分区未分配。2.动态分区法•与固定分区法相比，动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的，且其大小可随作业或进程对内存的要求而改变。这就改变了固定分区法中那种即使是小作业也要占据大分区的浪费现

象，从而提高了内存的利用率。•采用动态分区法，在系统初启时，除了操作系统中常驻内存部分之外，只有一个空闲分区。随后，分配程序将该区依次划分给调度选中的作业或进程。图5.7给出了FIFO调度方式时的内存初始分配情况。图5.7内存初始分配情况

•随着进程的执行，会出现一系列的分配和释放。如在某一时刻，进程C执行结束并释放内存之后，管理程序又要为另两个进程E(设需内存50K)和F(设需内存16K)分配内存。如果分配的空闲区比所要求的大，则管理程序将该空闲区分成两个部分

，其中一部分成为已分配区而另一部分成为一个新的小空闲区。图5.8给出了采用最先适应算法(firstfit)分配内存时进程E和进程F得到内存以及进程B和进程D释放内存的内存分配变化过程。如图5.8所示，在

管理程序回收内存时，如果被回收分区有和它邻接的空闲分区存在，则要进行合并。图5.8内存分配变化过程•与固定分区法时相同，动态分区法也要使用分区说明表等数据结构对内存进行管理。除了分区说明表之外，动态分区法还把内存中的可用分区单独构

成可用分区表或可用分区自由链，以描述系统内的内存资源。与此相对应，请求内存资源的作业或进程也构成一个内存资源请求表。图5.9给出了可用表，自由链和请求表的例子。图5.9动态分区说明表、自由链及请求表•动态分区说明表的每个表目记录一

个空闲区，主要参数包括区号、长度和起始地址。采用表格结构，管理过程比较简单，但表的大小难以确定，可用表要占用一部分内存。•自由链则是利用每个内存空闲区的头几个单元存放本空闲区的大小及下个空闲区的起始地址，从而把所有的空闲区链接起来。然后

，系统再设置一自由链首指针让其指向第一个空闲区，这样，管理程序可通过链首指针查到所有的空闲区。采用自由链法管理空闲区，查找时要比可用表困难，但由于自由链指针是利用的空闲区自身的单元，所以不必占用额外的内存区。•请求表的每个表目描述请求内存资源

的作业或进程号以及所请求的内存大小。•无论是采用可用表方式还是自由链方式，可用表或自由链中的各个项都要按照一定的规则排列以利查找和回收。5.2.2分区的分配与回收1.固定分区时的分配与回收固定分区法时的内存分配与回收较为简单，当用户程序要装入

执行时，通过请求表提出内存分配要求和所要求的内存空间大小。存储管理程序根据请求表查询分区说明表，从中找出一个满足要求的空闲分区，并将其分配给申请者。固定分区时的分配算法如图5.10。固定分区的回收更加简单。当进程执行完

毕，不再需要内存资源时，管理程序将对应的分区状态置为未使用即可。图5.10固定分区分配算法2.动态分区时的分配与回收•动态分区时的分配与回收主要解决三个问题：•对于请求表中的要求内存长度，从可用表或自由链中寻找出合适的空闲区分配程序。•分配空闲区之后

，更新可用表或自由链。•进程或作业释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自由链。•动态分区时的分配方法从可用表或自由链中寻找空闲区的常用方法有三种：•最先适应法(firstfitalgorithm)•最佳适应法(bestfitalgorithm)•最坏适应

法(worstfitalgorithm)•最先适应法(firstfitalgorithm)：要求可用表或自由链按起始地址递增的次序排列。该算法的最大特点是一旦找到大于或等于所要求内存长度的分区，则结束探索。然后，该算法从所找到的

分区中划出所要求的内存长度分配给用户，并把余下的部分进行合并(如果有相邻空闲区存在)后留在可用表中，但要修改其相应的表项。最先适应算法如图5.11所示。图5.11最先适应算法•最佳适应算法(bestfitalgorithm):要求从小到大的次序组成空闲区可用表或

自由链。当用户作业或进程申请一个空闲区时，存储管理程序从表头开始查找，当找到第一个满足要求的空闲区时，停止查找。如果该空闲区大于请求表中的请求长度，则与最先适应法时相同，将减去请求长度后的剩余空闲区部分留在可用表中

。•最坏适应算法(worstfitalgorithm):要求空闲区按其大小递减的顺序组成空闲区可用表或自由链。当用户作业或进程申请一个空闲区时，先检查空闲区可用表或自由链的第一个空闲可用区的大小是否大于或等于所要求的内存长度，若可用表或自由链的第一个项长度小于所要求的，则分配失

败，否则从空闲区可用表或自由链中分配相应的存储空间给用户，然后修改和调整空闲区可用表或自由链。3.动态分区时的回收与拼接•当用户作业或进程执行结束时，存储管理程序要收回已使用完毕的空闲区，并将其插入空闲区可用表或自由链。这里，在将回收的空闲区插入可用表或自由链时，和分配空闲区时一样，也

要碰到剩余空闲区拼接问题。如果不对空闲区进行拼接，则由于每个作业或进程所要求的内存长度不一样而出现大量分散，较小的空闲区。这就造成大量的内存浪费。解决这个问题的办法之一就是在空闲区回收时或在内存分配时进

行空闲区拼接，以把不连续的零散空闲区集中起来。•在将一个新可用区插入可用表或队列时，该空闲区和上下相邻区的关系是下述4种关系之一：•该空闲区的上下两相邻分区都是空闲区；•该空闲区的上相邻区是空闲区；•该空闲区的下相邻区是空闲区；•两相邻

区都不是空闲区。图5.12空闲区的合并•对于上述4种情况，如果释放区与上下两空闲区相邻，则将三个空闲区合并为一个空闲区。新空闲区的起始地址为上空闲区的起始地址，大小为三个空闲区之和。空闲区合并后，取消可用表或自由链中下空闲区的表目项或链指针，修改上空闲区的对

应项。•如果释放区只与上空闲区相邻，则将释放区与上空闲区合并为一个空闲区，其起始地址为上空闲区的起始地址，大小为上空闲区与释放区之和。合并后，修改上空闲区对应的可用表的表目项或自由链指针。•如果释放区与下空

闲区相邻，则将释放区与下空闲区合并，并将释放区的起始地址作为合并区的起始地址。合并区的长度为释放区与下空闲区之和。同理，合并后修改可用表或自由链中相应的表目项或链指针。•如果释放区不与任何空闲区相邻，则释放区作为一个新可用区插入可

用表或自由链。读者可以自行写出动态分区时的回收算法。4.几种分配算法的比较由于回收后的空闲区要插入可用表或自由链中，而且可用表或自由链是按照一定顺序排列的，所以，除了搜索查找速度与所找到的空闲区是否最佳，释放空闲区的速度也对系统开销产生影响。•搜索速度：最先适应算法最佳。尽管

最佳适应算法或最坏适应算法看上去能很快找到一个最适合的或最大的空闲区，但后两种算法都要求首先把不同大小的空闲区按其大小进行排队，这实际上是对所有空闲区进行一次搜索。•回收过程：最先适应算法最佳。因为使用最先适应算法回收某一空闲区时，无论被释

放区是否与空闲区相邻，都不用改变该区在可用表或自由链中的位置，只需修改其大小或起始地址。而最佳适应算法和最坏适应算法都必须重新调整该区的位置。•最先适应算法尽可能地利用低地址空间，从而保证高地址有较大的空闲区来放置要求内存较多的进程或作业。•最佳适应法找到的空闲区最佳，用

最佳适应法找到的空闲区或者是正好等于用户请求的大小或者是能满足用户要求的最小空闲区。尽管最佳适应法能选出最适合用户要求的可用空闲区，但这样做在某些情况下并不一定能提高内存的利用率。•最坏适应算法正是基于不留下碎片空闲区这一出发点的。它选择最大的空闲区来满足用户要求，以期分配后的

剩余部分仍能进行再分配。5.2.3有关分区管理其他问题的讨论1.关于虚存的实现利用分区式管理，也同样存在有每个用户可以自由编程的虚拟空间。但是，分区式管理方式无法实现那种用户进程所需内存容量只受内存和外存容量之和限制的虚拟存储器。事实上，如果不采用内存扩充技术，每个

用户进程所需内存容量是受到分区大小限制的，这一点从上面的讨论中可以看出。2.关于内存扩充由于分区式管理时各用户进程或作业所要求的内存容量受到分区大小的限制，如果不采用内存扩充技术，将会极大地限制分区式管理技术的使用。在分区式管理中，可以使用覆盖或交换技术来扩充内存。3.关于地址变换和内存保护

静态地址重定位和动态地址重定位技术，都可用来完成分区式内存管理的地址变换。显然，动态分区时分区大小不固定，而空闲区的拼接会移动内存中的程序和数据，因此，使用静态地址重定位的方法来完成动态分区时的地址变换是不妥当的。在进行动态地址重定位时，每个分区需要一对硬件寄存器

的支持，即基址寄存器和限长寄存器，分别用来存放作业或进程在内存分区的起始地址和长度。这一对硬件寄存器除了完成动态地址重定位的功能之外，还具有保护内存中数据和程序的功能。这由硬件检查CPU执行指令所要访问的虚拟地址完成。即

设CPU指令所要访问的虚拟地址为D，若D>VR(VR是限长寄存器中的限长值)，则说明地址越界，所要访问的内存地址超出了该作业或进程所占用的内存空间。这时将产生保护中断。系统转去进行出错处理。若D<=VR，则该地址是合法

的，由硬件完成对该虚拟地址的动态重定位。4.分区存储管理的主要优缺点•分区存储管理的主要优点•实现了多个作业或进程对内存的共享，有助于多道程序设计，从而提高了系统的资源利用率。•该方法要求的硬件支持少，

管理算法简单，因而实现容易。•主要缺点有•内存利用率仍然不高。和单一连续分配算法一样，存储器中可能含有从未用过的信息。而且，还存在着严重的碎小空闲区(碎片)不能利用的问题，这更进一步影响了内存的利用率。•作业或进程的大小受分区大小控制，除非配合采用覆盖和交换技术。•无法

实现各分区间的信息共享。5.3覆盖与交换技术5.3.1覆盖技术覆盖技术的基本思想：一个程序并不需要一开始就把它的全部指令和数据都装入内存后再执行。单CPU系统中，每一时刻事实上只能执行一条指令。可以把程序划分为若干个功能上相对独立的程序段，按照程序的逻

辑结构让那些不会同时执行的程序段共享同一块内存区。通常，这些程序段都被保存在外存中，当有关程序段的先头程序段已经执行结束后，再把后续程序段调入内存覆盖前面的程序段。这使得用户看来，好像内存扩大了，从而达到了内存扩充的目的。

•覆盖技术要求程序员提供一个清楚的覆盖结构。即程序员必须完成把一个程序划分成不同的程序段，并规定好它们的执行和覆盖顺序的工作。•一般来说，一个程序究竟可以划分为多少段，以及让其中的哪些程序共享哪一内存区只有程序员清楚。这要求程序员既要清楚地了解程序所属进程的虚拟空间及各程序段所在虚拟空间的位

置，又要求程序员懂得系统和内存的内部结构与地址划分，因此，程序员负担较重。•例如，设某进程的程序正文段由A，B，C，D，E和F等6个程序段组成。它们之间的调用关系如图5.13(a)所示，程序段A调用程序段B和C

，程序段B又调用程序段F，程序段C调用程序段D和E。•由图5.13(a)可以看出，程序段B不会调用C，程序段C也不会调用B。因此，程序段B和C无需同时驻留在内存，它们可以共享同一内存区。同理，程序段D、E、F也可共享同一内存区。其覆盖结构如图5.13(b)所示。图5.13覆盖示例•在图5.13(

b)中，整个程序正文段被分为两个部分。一个是常驻内存部分，该部分与所有的被调用程序段有关，因而不能被覆盖。这一部分称为根程序。图5.13(b)中，程序段A是根程序。另一部分是覆盖部分，图中被分为两个覆盖区。其中，一个

覆盖区由程序段B，C共享。其大小为B，C中所要求容量大者。另一个覆盖区为程序段F，D，E共享。两个覆盖区的大小分别为50K与40K。这样，虽然该进程正文段所要求的内存空间是A(20K)+B(50K)+F(3

0K)+C(30K)+D(20K)+E(40K)=190K，但由于采用了覆盖技术，只需110K的内存空间即可开始执行。5.3.2交换技术多道程序环境或分时系统中，同时执行好几个作业或进程。但是，这些同

时存在于内存中的作业或进程，有的处于执行状态或就绪状态，而有的则处于等待状态。一般来说，等待时间比较长。例如从外存软磁盘读一块数据到内存有时要花0.1秒到1秒左右的时间。如果让这些等待中的进程继续驻留内存，

将会造成存储空间的浪费。因此，应该把处于等待状态的进程换出内存。实现上述目标的方法很多，其中比较常用的方法之一就是交换。广义地说，交换是指先将内存某部分的程序或数据写入外存交换区，再从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术。与覆盖

技术相比，交换不要求程序员给出程序段之间的覆盖结构。而且，交换主要是在进程或作业之间进行，而覆盖则主要在同一个作业或进程内进行。另外，覆盖只能覆盖那些与覆盖程序段无关的程序段。5.3.2交换技术交换进程由换出和换入两个

过程组成。其中换出(swapout)过程把内存中的数据和程序换到外存交换区，而换入(swapin)过程把外存交换区中的数据和程序换到内存分区中。换出过程和换入过程都要完成与外存设备管理进程通信的任务。由交换进程发送给设备进程的消息m

中应包含分区的分区号i、该分区的基址basei、长度sizei和方向及外存交换区中分区起始地址。交换进程和设备管理进程通过设备缓冲队列进行通信。交换技术大多用在小型机或微机系统中。这样的系统大部分采用固定的

或动态分区方式管理内存。•在换出过程SWAPOUT(i)中，除了前5行描述所需要的控制信息之外，backupstorbasei是用来记录被换出数据和程序的起始地址以便换入时使用的。而send指令则驱动设备做相应的数据读写操作。•与SWAPOUT过程相同，可以写出SWAPIN过程：5.4页

式管理5.4.1页式管理的基本原理分区式管理方式尽管实现方式较为简单，但存在着严重的碎片问题使得内存的利用率不高。再者，分区式管理时，由于各作业或进程对应于不同的分区以及在分区内各作业或进程连续存放，进程的大小仍受分区大小或内存可用空

间的限制。而且，分区式管理也不利于程序段和数据的共享。页式管理正是为了减少碎片以及为了只在内存存放那些反复执行或即将执行的程序段与数据部分，而把那些不经常执行的程序段和数据存放于外存待执行时调入，以提高内存利用率而提出来的。•页式管理的基本

原理如下：•首先，各进程的虚拟空间被划分成若干个长度相等的页(page)。页长的划分和内存外存之间数据传输速度以及内存大小等有关。一般每个页长大约为1-4K，经过页划分之后，进程的虚地址变为页号p与页内地址

w所组成。图5.14页的划分•如一个页长为1K，拥有1024页的虚拟空间地址结构如图5.14：•除了把进程的虚拟空间划分为大小相等的页之外，页式管理还把内存空间也按页的大小划分为片或页面(pageframe)。这些页面为系统中的任一进程所共享(除去操作系统区外)。从而，与分

区管理不一样，分页管理时，用户进程在内存空间内除了在每个页面内地址连续之外，每个页面之间不再连续。第一是实现了内存中碎片的减少，因为任一碎片都会小于一个页面。第二是实现了由连续存储到非连续存储这个飞跃，为在内存中局部地、动态地存储那些反复执行或

即将执行的程序和数据段打下了基础。页号P页内地址W191090•那么，怎样由页式虚拟地址变换为内存页面物理地址呢?页式管理把页式虚地址与内存页面物理地址建立一一对应页表，并用相应的硬件地址变换机构，来解决离散地址变换

问题。页表方式实质上是动态重定位技术的一种延伸。•再者，页式管理采用请求调页或预调页技术实现了内外存储器的统一管理。即内存内只存放那些经常被执行或即将被执行的页，而那些不常被执行以及在近期内不可能被执行的页，则存放于外存中待需要时再调入

。请求调页或预调页技术是基于工作区的局部性原理的。•由于使用了请求调页或预调页技术，页式管理时内存页面的分配与回收已和页面淘汰技术及缺页处理技术结合起来。不过，页面的换入换出仍是必要的，这只要把上节所述

的交换进程稍加修改就能用于页面的交换。•分页管理的重点在于页划分之后的地址变换以及页面的调入调出技术。5.4.2静态页面管理静态页面管理方法是在作业或进程开始执行之前，把该作业或进程的程序段和数据全部装

入内存的各个页面中，并通过页表(pagemappingtable)和硬件地址变换机构实现虚拟地址到内存物理地址的地址映射。1.内存页面分配与回收•静态分页管理的第一步是为要求内存的作业或进程分配足够的页面。系统依靠存储页面表、请求表以及页表来完成内存的分配工作。•页表：最简单的页表

由页号与页面号组成。图5.15基本页表示例页号页面号•页表在内存中占有一块固定的存储区。页表的大小由进程或作业的长度决定。例如，对于一个每页长1K，大小为20K的进程来说，如果一个内存单元存放一个页表项，则只要分配给该页表20个存储单元即可。显

然，页式管理时每个进程至少拥有一个页表。•请求表：用来确定作业或进程的虚拟空间的各页在内存中的实际对应位置。为了完成这个任务，系统必须知道每个作业或进程的页表起始地址和长度，以进行内存分配和地址变换。另外，请求表中还应包括每个作业或进程所要求的页

面数。•请求表整个系统一张，如图5.16所示。图5.16请求表示例请求页面数页表始址20102434104418107821……页表长度状态20已分配34已分配18已分配……已分配进程号1234…………………………•存储页面表：存储页面表也是整个系统一张，存储页面表指出内存各页面是否已

被分配出去，以及未分配页面的总数。存储页面表也有两种构成方法，一种是在内存中划分一块固定区域，每个单元的每个比特代表一个页面。如果该页面已被分配，则对应比特位置1，否则置0。这种方法称为位示图法。如图5.17所示。图5.17位示图…………190000………………18100017

01001600101510014011031110210111010101111•位示图要占据一部分内存容量，例如，一个划分为1024个页面的内存，如果内存单元长20比特，则位示图要占据1024/20=52个

内存单元。•存储页面表的另一种构成办法是采用空闲页面链的方法。在空闲页面链中，队首页面的第一个单元和第二个单元分别放入空闲页面总数与指向下一个空闲页面的指针。其他页面的第一个单元中则分别放入指向下一个页面的指针。空闲页面链的方法由于使用了空闲页面本身的单元存放指针，因此不占据额外

的内存空间。2.分配算法•利用上述三个表格和数据结构，给出一个页面分配算法。•首先，请求表给出进程或作业要求的页面数。然后，由存储页面表检查是否有足够的空闲页面，如果没有，则本次无法分配。如果有则首先分配设置页表，并填

写请求表中的相应表项后，按一定的查找算法、搜索出所要求的空闲页面，并将对应的页面号填入页表中。图5.18给出了上述页面分配算法的流程图。•静态页式管理的页面回收方法较为简单，当进程执行完毕时，拆除对应的页表，并把页表中的各页面插

入存储页面表即可。图5.18页面分配算法流图3.地址变换•是静态页式管理的另一个关键问题，即怎样由页号和页内相对地址变换到内存物理地址的问题。•由于静态重定位可以使CPU直接访问物理地址，而分区式管理中的动态重定位也只需把基址寄存器中的分区起始地址与待访问指令的虚地址相加即可得到所要访问的物理地址

。这两种重定位法都不需要访问内存就可得到待执行指令所要访问的物理地址。•页式管理时，地址变换的速度怎样呢?•由地址分配方式知道，在一个作业或进程的页表中，连续的页号对应于不连续的页面号。例如，设一个3页长的

进程具有页号0，1，2，但其对应的页面号则为2，3，8。如图5.19所示。图5.19页号与页面号页号面号021328•设每个页面长度为1K，指令LOAD1，2500的虚地址为100，怎样通过图5.19所示页表来找到该指令所对应的物理地址呢?下面使用该例子说明地址变换过程

。•首先，需要有一个装置页表始址和页表长度用的控制寄存器。系统把所调度执行的进程页表始址和长度从请求表中取出置入控制寄存器中。•然后，由控制寄存器的页表始址，可以找到页表所在位置。并由虚地址100可知，指令LOAD1，2500在第0页的第100单元之

中。由于第0页与第2个页面相对应，因此，该指令在内存中的地址为2048+100=2148。•当CPU执行到第2148单元的指令时，CPU要从有效地址2500中取数据放入1号寄存器中。为了找出2500对应的实际物理地址，地址变换机构首先将2500转换为页号与页

内相对地址组成的地址形式。即p=2，w=452。•由页表，可知第2页所对应的页面号等于8。最后，将页面号8与页内相对地址w=452相连，得到待访问的物理内存地址8644。其变换过程由图5.20所示。图5.20地址变换•上述地址变换过程全部由硬件地址变换机构自动完成。•另外，由于页表是驻留在内

存的某个固定区域中，而取数据或指令又必须经过页表变换才能得到实际物理地址。因此，取一个数据或指令至少要访问内存两次以上。一次访问页表以确定所取数据或指令的物理地址，另一次是根据地址取数据或指令。这比通常执行指令的速度慢了一倍。有什么办法可以提高查找速度吗?一个最直观的办法就是把页表放在寄

存器中而不是内存中，但由于寄存器价格太贵，这样做是不可取的。另一种办法是在地址变换机构中加入一个高速联想存储器，构成一张快表。在快表中，存入那些当前执行进程中最常用的页号与所对应的页面号，从而以提高查找速度。•静态页式管理解决了分区管理时的碎片问

题。但是，由于静态页式管理要求进程或作业在执行前全部装入内存，如果可用页面数小于用户要求时，该作业或进程只好等待。而且，作业或进程的大小仍受内存可用页面数的限制。5.4.3动态页式管理•动态页式管理是在静态页式

管理的基础上发展起来的。它分为请求页式管理和预调入页式管理。•请求页式管理和预调入页式管理在作业或进程开始执行之前，都不把作业或进程的程序段和数据段一次性地全部装入内存，而只装入被认为是经常反复执行和调用的工作区部分。其他部分则在执行过程中动态装入。请求页式管理与预调

入页式管理的主要区别在它们的调入方式上。请求页式管理的调入方式是，当需要执行某条指令而又发现它不在内存时或当执行某条指令需要访问其他的数据或指令时，这些指令和数据不在内存中，从而发生缺页中断，系统将外存中相应的页面调入内

存。•预调入方式是，系统对那些在外存中的页进行调入顺序计算，估计出这些页中指令和数据的执行和被访问的顺序，并按此顺序将它们顺次调入和调出内存。除了在调入方式上请求页式管理和预调入管理有些区别之外，其他方面这两种方式基本相同。因此，下面主要介绍请求页式管

理。5.4.3动态页式管理•请求页式管理的地址变换过程与静态页式管理时的相同，也是通过页表查出相应的页面号之后，由页面号与页内相对地址相加而得到实际物理地址。•由于请求页式管理只让进程或作业的部分程序和数据驻留

在内存中，因此，在执行过程中，不可避免地会出现某些虚页不在内存中的问题。怎样发现这些不在内存中虚页以及怎样处理这种情况，是请求页式管理必须解决的两个基本问题。•第一个问题可以用扩充页表的方法解决。即与每个虚页号相对应，除了页面号之外，再增设该页是否在内存的中断位以及

该页在外存中的副本起始地址。扩充后的页表如图5.21。•第二个问题是有关缺页的调入和存放，在内存中没有空闲页面时，实际上是一个内存页面置换算法的问题。图5.21加入中断处理后的页表页面号中断位外存始址页号•由于虚页不在内存时的处理，涉及到两个问题。第一，采用何种方式把

所缺的页调入内存。第二，如果内存中没有空闲页面时，把调进来的页放在什么地方。也就是说，采用什么样的策略来淘汰已占据内存的页。还有，如果在内存中的某一页被淘汰，且该页曾因程序的执行而被修改，则显然该页是应该重新写到外存上加以保存的。而那些未被访问修改的页，因为外存已保留有相同的副

本，写回外存是没有必要的。因此，在页表中还应增加一项以记录该页是否曾被改变。增加改变位后的页表项如图5.22所示。图5.22加入改变位后的页表页面号中断位外存始址改变位页号•有关缺页的调入和存放，在内存中没有

空闲页面时，实际上是一个内存页面置换算法的问题。选择什么样的置换算法，将直接影响到内存利用率和系统效率。事实上，如果置换算法选择不当，有可能产生刚被调出内存的页又要马上被调回内存，调回内存不久又马上被调出内存，如此反复的局面。这使得整个系统的页面调度非常频繁，以致大部分时间都花费在主存和辅存

之间的来回调入调出上。这种现象被称为抖动(thrashing)现象。•动态页式管理的流程图如图5.23所示。•在图5.23中，有关地址变换部分是由硬件自动完成的。当硬件变换机构发现所要求的页不在内存时，产

生缺页中断信号，由中断处理程序做出相应的处理。中断处理程序是由软件实现的。除了在没有空闲页面时要按照置换算法选择出被淘汰页面之外，还要从外存读入所需要的虚页。这个过程要启动相应的外存和涉及到文件系统。因此，

请求页式管理是一个十分复杂的处理过程，内存利用率的提高是以牺牲系统开销的代价换来的。图5.23动态页式管理流图5.4.4请求页式管理中的置换算法•置换算法在内存中没有空闲页面时被调用。它的目的是选出一个被淘

汰的页面。如果内存中有足够的空闲页面存放所调入的页，则不必使用置换算法。把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中。因此，置换算法应该置换那些被访问概率最低的页，将它们移出内存。•几种常用的置换算法

：•随机淘汰算法(randomglongram)：在系统设计人员认为无法确定哪些页被访问的概率较低时，随机地选择某个用户的页面并将其换出将是一种明智的作法。•轮转法(roundrobin)：轮转法循回换出内存可用区内一个可以被换出的页，无论该页是刚被换进或已换进内存很长时间。•先进先出算

法(FIFO)：FIFO算法总是选择在内存驻留时间最长的一页将其淘汰。FIFO算法认为先调入内存的页不再被访问的可能性要比其他页大，因而选择最先调入内存的页换出。•最近最久未使用页面置换算法(leastrece

ntlyused)。•由实验和测试发现FIFO算法和RR算法的内存利用率不高。•FIFO算法的另一个缺点是它有一种陷阱现象。一般来说，对于任一作业或进程，如果给它分配的内存页面数越接近于它所要求的页面数，则发生缺页的次数会越少。在极限情况下，这个推论是成立的。因

为如果给一个进程分配了它所要求的全部页面，则不会发生缺页现象。但是，使用FIFO算法时，在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为Belady现象。图5.24FIFO算法的Belady现象•例：设进

程P共有8页，且已在内存中分配有3个页面，程序访问内存的顺序(访问串)为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。这里，这些自然数代表进程P所建的程序和数据的页号。内存中有关

进程P所建的程序和数据的各页面变化情况如图5.25所示。图5.25Belady现象示例(1)•由图5.25可以看出，进程在一个执行过程中，实际上发生了12次缺页。如果设缺页率为缺页次数与访问串的访问次

数之比，则该例中的缺页率为12/17=70.5%。77070170122010201342330232023101320123231023044302420002300121012•如果给进程P分配4个页面，则在其

执行过程中内存页面的变化情况如图5.26所示。图5.26Belady现象示例(2)•进程P在拥有4个内存页面时，共发生9次缺页，其缺页率为9/17=52.9%。770701701270107013341334023401

3402240330103014341234103400240124022222112222211•设进程P可分为5页，访问串为1，2，3，4，1，2，5，1，2，3，4，5。当进程P分得3个页面时，执行

过程中内存页面变化如图5.27所示。图5.27Belady现象示例(3)•由图5.27可知，进程P在执行过程中共缺页9次，其缺页率为9/12=75%。112123123442314133532553424125512151225124534•但是，如果为进程P分配4个内存页面，是否缺页率会变小呢?

进程P分得4个页面时，执行过程中内存页面的变化情况如图5.28。图5.28Belady现象示例(4)•由图5.28可知，当进程P分得4个页面时，在执行过程中的缺页次数为10次。即缺页率=10/12=83.3%。•先进先出算

法产生Belady现象的原因在于它根本没有考虑程序执行的动态特征。112123123412311233512545221235523151325124412443344443•最近最久未使用页面置换算法(le

astrecentlyused)•基本思想：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间也

不会被访问。•要完全实现LRU算法是一件十分困难的事情。因为要找出最近最久未被使用的页面的话，就必须对每一个页面都设置有关的访问记录项，而且每一次访问都必须更新这些记录。这显然要花费巨大的系统开销。因此，在实际系统中往往使用LRU的近似算法。•比较常用的近似

算法有：•最不经常使用页面淘汰算法LFU(leastfrequentlyused)。该算法在需要淘汰某一页时，首先淘汰到当前时间为止，被访问次数最少的那一页。这只要在页表中给每一页增设一个访问计数器即可实现。每当该页被访问时，访

问计数器加1，而发生一次缺页中断时，则淘汰计数值最小的那一页，并将所有的计数器清零。•最近没有使用页面淘汰算法NUR。该算法在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。只要在页表

中增设一个访问位即可实现。当某页被访问时，访问位置1。否则，访问位置0。系统周期性地对所有引用位清零。当需淘汰一页时，从那些访问位为零的页中选一页进行淘汰。•理想型淘汰算法OPT(optimalreplacementalgorithm)•该算法淘汰在访问串中将来再也不出现的或是

在离当前最远的位置上出现的页。这样，淘汰掉该页将不会造成因需要访问该页又立即把它调入的现象。遗憾的是，这种算法无法实现，因为它要求必须预先知道每一个进程的访问串。5.4.5存储保护•·页式管理可以为内存提供两种方式的保护。一种是地址越界保护，另一种是通过页表控制对内存信息的存取操作方式以

提供保护。•地址越界保护可由地址变换机构中的控制寄存器的值——页表长度和所要访问的虚地址相比较来完成。•存取控制保护的实现则是在页表中增加相应的保护位即可。5.4.6页式管理的优缺点•优点：•由于它不要求作业或进程的程序段和数据在内存中连续存

放，从而有效地解决了碎片问题。•动态页式管理提供了内存和外存统一管理的虚存实现方式，使用户可以利用的存储空间大大增加。这既提高了主存的利用率，又有利于组织多道程序执行。•主要缺点：•要求有相应的硬件支持。例如地址变换机构，缺页中断的产生和选择淘汰页面等都要求有相应的硬件支持。这

增加了机器成本。•增加了系统开销，例如缺页中断处理等。•请求调页的算法如选择不当，有可能产生抖动现象。•虽然消除了碎片，但每个作业或进程的最后一页内总有一部分空间得不到利用。如果页面较大，则这一部分的损失仍然较大。5.5段式与段页式管理5.5.1段式管理的

基本思想•分区式管理和页式管理的不足：•分区式管理和页式管理的进程地址空间结构都是线性的，这要求对源程序进行编译、链接时，把源程序中的主程序、子程序、数据区等按线性空间的一维地址顺序排列起来。这使得不同作业或进程之间共享公用子程序和数据变得非常困难。•对于不同的用户进程来

说，它们访问这些公用子程序或数据块的权限是不同的。因此，如果系统不能把用户给定的程序名和数据块名与这些被共享程序和数据在某个进程中的虚页对应起来，则不可能共享这些存放在内存页面中的程序和数据。•由于在页式管理时，一个页面中可能装有两个不同子程序段的指令代码，因此，通过页面共

享来达到共享一个逻辑上完整的子程序或数据块是不可能的。•从链接的角度看，分区管理和页式管理只能采用静态链接。一个大的进程可能包含数百个甚至上千个程序模块。对它们进行链接要花费大量的CPU时间，而实际执行时则可能只用到其中的一个子集。因此，从减少CPU开销和存储空间浪费的角度来看，静态链接是不

合适的。•综上所述，段式存储管理是基于为用户提供一个方便灵活的程序设计环境而提出来的。段式管理的基本思想是：把程序按内容或过程(函数)关系分成段，每段有自己的名字。一个用户作业或进程所包含的段对应于一个二维线性虚拟空间，

也就是一个二维虚拟存储器。段式管理程序以段为单位分配内存，然后通过地址映射机构把段式虚拟地址转换成实际的内存物理地址。和页式管理时一样，段式管理也采用只把那些经常访问的段驻留内存，而把那些在将来一段时间内不被访问的段放入外存，待需要时自动调入的方法实现二维虚拟存

储器。5.5.2段式管理的实现原理1.段式虚存空间•段式管理把一个进程的虚地址空间设计成二维结构，即段号s与段内相对地址w。与页式管理时不一样的是，页式管理中，被划分的页号按顺序编号递增排列，属一维空间，而段式管理中的段号与段号之间无顺序关系。另外，段的划分也不像页的划

分那样具有相同的页长，段的长度是不固定的。每个段定义一组逻辑上完整的程序或数据。例如，一个进程中的程序和数据可被划分为主程序段、子程序段、数据段与工作区段。•每个段是一个首地址为零的、连续的一维线性空间

。根据需要，段长可动态增长。对段式虚地址空间的访问包括两个部分：段名和段内地址。2.段式管理的内存分配与释放•段式管理中以段为单位分配内存，每段分配一个连续的内存区。由于各段长度不等，所以这些存储区的大小不一。而且，同一进程所包含

的各段之间不要求连续。•段式管理的内存分配与释放在作业或进程的执行过程中动态进行。•首先，段式管理程序为一个进入内存准备执行的进程或作业分配部分内存，以作为该进程的工作区和放置即将执行的程序段。•随着进程的执行，进程根据需要随时申请

调入新段和释放老段。进程对内存区的申请和释放可分为两种情况。•一种是当进程要求调入某一段时，内存中有足够的空闲区满足该段的内存要求。•另一种是内存中没有足够的空闲区满足该段的内存要求。另一种内存空闲区的分配与回收方法是在内存中没有足够的空闲区满足调入段

的内存要求时使用的。这时，段式管理程序根据给定的置换算法淘汰内存中在今后一段时间内不再被CPU访问的段，也就是淘汰那些访问概率最低的段。•动态页式管理中的几种常用的淘汰算法都可以用来作为段式管理时的淘汰算法。例如FIFO置换算法、LRU算法及其近似算法等。但是，与页式管

理时每页具有相同的长度时不一样，需要调入的某段长度可能大于被淘汰的一段程序或数据的长度。这样，仅仅淘汰一段可能仍然满足不了需要调入段的内存要求。此时，就应再淘汰另外的段直到满足需调入段的内存要求时为止。•事实上，一次调入时所需淘汰的段数与段的大小有关。如果一个作业或进程的段数较多，且段长之间的差

别较大，则有可能出现调入某个大段时，需淘汰好几个小段的情况。不过，在段式管理时，任何一个段的段长都不允许超过内存可用区长度，否则将会造成内存分配出错。•除了初始分配之外，段的动态分配是在CPU所要访问的指令和数据不在内存时产生缺段中断的情况下发生的。因此，段的淘汰或

置换算法实际上是缺段中断处理过程的一部分。•缺段中断处理过程的全过程如图5.29所示。图5.29缺段中断处理过程•X代表所缺段段号。该处理程序是在CPU访问执行时，地址变换机构发现该段不在内存，而由硬件发出缺段中断信号后被调用的。3.段式管理的

地址变换•由于段式管理只存放部分用户信息副本在内存，而大部分信息在外存中，这必然引起CPU访内时发生所要访问的段不在内存的现象。那么，CPU如何感知到所要访问的段不在内存而启动中断处理程序呢?•还有，段式虚拟地址属于一个二维的虚拟空间。一个二维空间的虚拟地址怎

样变换为一个一维的线性物理地址呢?这些都由段式地址变换机构解决。•段表(segmentmappingtable)：和页式管理方案类似，段式管理程序在进行初始内存分配之前，首先根据用户要求的内存大小为一个作业或进程建立一个

段表，以实现动态地址变换和缺段中断处理及存储保护等。与页式管理时一样，段式管理也是通过段表来进行内存管理的。考虑了缺段处理和段式访问控制保护后的段表如图5.30所示。图5.30段表•图中段号与用户指定的段名一一对应，始址和长度分别表示该段在内存或

外存的物理地址与实际长度。存取方式是用来对该段进行存取保护的。只有处理机状态字中的存取控制位与段表中存取方式一致时才能访问该段。内外栏是指出该段现在存储于外存还是内存中。如果该栏目指出所访问段在外存的话，则发生中断。而访问位则是根

据淘汰算法的需要而设的，这里假定淘汰算法淘汰那些访问位未被改变过的段(NUR算法)。始址长度存取方式内外段号访问位•动态地址变换：一般在内存中给出一块固定的区域放置段表。当某进程开始执行时，管理程序首先把该进程的段表始址放

入段表地址寄存器。通过访问段表寄存器，管理程序得到该进程的段表始址从而可开始访问段表。然后，由虚地址中的段号s为索引，查段表。若该段在内存，则判断其存取控制方式是否有错。如果存取控制方式正确，则从段表相应表目中查出该段在内存的起始地址，并将其和段内相对地址w相加，从而得到实际内存地址。如

果该段不在内存，则产生缺段中断将CPU控制权交给内存分配程序。内存分配程序首先检查空闲区链，以找到足够长度的空闲区来装入所需要的段。如果内存中的可用空闲区总数小于所要求的段长时，则检查段表中访问位，以淘汰那些访问概率低的段并将需要段调入。段式地址变换过程如图5.31所示。图5.31段式地址变换

过程•与页式管理时相同，段式管理时的地址变换过程也必须经过二次以上的内存访问。即首先访问段表以计算得到待访问指令或数据的物理地址，然后才是对物理地址进行取数据或存数据操作。为了提高访问速度，页式地址变换时使用的高速联想寄存器的方法也可以用在段式地址变换中。即高速联想寄存器中存放那些经常访问的段

号所对应的段表项，且高速联想寄存器中的段表和内存的段表可同时查找。如果在联想寄存器中找到了所需要的段，则可以大大加快地址变换速度。4.段的共享与保护•段式存储管理可以方便地实现内存信息共享和进行有效地内存保护。这是因为段是按逻辑意义来划分的，可以按段名访问的缘

故。•段的共享：•在多道环境下，常常有许多子程序和应用程序是被多个用户所使用的。特别是在多窗口系统、支持工具等广泛流行的今天，被共享的程序和数据的个数和体积都在急剧增加，有时往往超过用户程序长度的许多倍。这种情况下，

如果每个用户进程或作业都在内存保留它们共享程序和数据的副本，那就会极大地浪费内存空间。最好的办法是内存中只保留一个副本，供多个用户使用，称为共享。如图5.32所示。图5.32段式系统中共字内存副本•如果用户进程或作业需要共享内存中的某段程序或数据

，只要用户使用相同的段名，就可在新的段表中填入已存在于内存之中的段的起始地址，并置以适当的读写控制权，就可做到共享一个逻辑上完整的内存段信息。•另外，在多道环境下，由于进程的并发执行，一段程序为多个进程共享时，有可能出现多次同时重复执行该段程序的情况(即某个进程在未执行完该段程序之前，其他并发

进程又已开始执行该段程序)。这就要求它在执行过程中，该段程序的指令和数据不能被修改。还有，与一个进程中的其他程序段一样，共享段有时也要被换出内存。这时，就要在段表中设立相应的共享位来判别该段是否正被某个进程调用。显然一个正在被某个进程使

用或即将被某个进程使用的共享段是不应该调出内存的。•段的保护：与页式管理时相同，段式管理的保护主要有两种。一种是地址越界保护法，另一种是存取方式控制保护法。关于存取方式控制保护已在前面介绍，这里不再重复。而地址越界保护则是利用段表中的段长项与虚拟地址中的段内相对地址比较进行的。若段内相

对地址大于段长，系统就会产生保护中断。不过，在允许段动态增长的系统中，段内相对地址大于段长是允许的。为此，段表中设置相应的增补位以指示该段是否允许该段动态增长。5.5.3段式管理的优缺点•优点：•和动态页式管理一样，段式管理也提供了内外存统一管理

的虚存实现。与页式管理不同的是，段式虚存每次交换的是一段有意义的信息，而不是像页式虚存那样只交换固定大小的页从而需要多次缺页中断才能把所需信息完整地调入内存。•在段式管理中，段长可根据需要动态增长。这对那些需

要不断增加或吸收新数据的段来说，将是非常有好处的。•便于对具有完整逻辑功能的信息段进行共享。•便于实现动态链接。由于段式管理是按信息的逻辑意义来划分段，每段对应一个相应的程序模块。因此，可用段名加上段入口地址

等方法在执行过程中调入相应的段进行动态链接。当然，段的动态链接需要一定的硬件支持。5.5.3段式管理的优缺点•主要缺点：•段式管理比其他几种方式要求有更多的硬件支持。这就提高了机器成本。•由于在内存空闲区管理方式上与分

区式管理相同，在碎片问题以及为了消除碎片所进行的合并等问题上较分页式管理要差。•允许段的动态增长也会给系统管理带来一定的难度和开销。•段式管理的另一个缺点就是每个段的长度受内存可用区大小的限制。•和页式管理一样，段式管理系统在选择淘汰算法时也必须十

分慎重，否则也有可能产生抖动现象。5.5.4段页式管理的基本思想•以上几种存储管理方式各有特长。段式管理为用户提供了一个二维的虚地址空间，反映了程序的逻辑结构，有利于段的动态增长以及共享和内存保护等，这大大地方便了用户。而分页系统

则有效地克服了碎片，提高了存储器的利用率。从存储管理的目的来讲，主要是方便用户的程序设计和提高内存的利用率。那么，把段式管理和页式管理结合起来让其互相取长补短不是更好吗?于是，段页式管理方式便被提了出来。•不过，由于段式管理与页式管理

都需要较大的系统开销，可以预计到段页式管理的开销会更大。因此，段页式管理方式一般只用在大型机系统中。近年来由于硬件发展很快，段页式管理的开销在工作站等机型上已变得可以容忍了。例如UNIXSystemⅤ就采用了分区加请求页式的内存管理技术。5.5.5段页式管理的实现原

理1.虚地址的构成段页式管理时，一个进程仍然拥有一个自己的二维地址空间，这与段式管理时相同。首先，一个进程中所包含的具有独立逻辑功能的程序或数据仍被划分为段，并有各自的段号s。这反映和继承了段式管理的特征。其次，对于段s中的程序或数据，则按照一定的大小将其划分为不同的页。和

页式系统一样，最后不足一页的部分仍占一页。这反映了段页式管理中的页式特征。从而，段页式管理时的进程的虚拟地址空间中的虚拟地址由三部分组成：即段号s，页号p和页内相对地址d。对于这个由三部分组成的虚拟地址来说，程序员可见的仍是段号s和段内相对地址w。p和d是由地址变换机构把

w的高几位解释成页号p，以及把剩下的低位解释为页内地址d而得到的。由于虚拟空间的最小单位是页而不是段，从而内存可用区也就被划分成为若干个大小相等的页面，且每段所拥有的程序和数据在内存中可以分开存放。分段的大

小也不再受内存可用区的限制。2.段表和页表为了实现段页式管理，系统必须为每个作业或进程建立一张段表，管理内存分配与释放、缺段处理、存储保护和地址变换等。另外，由于一个段又被划分成了若干页，每个段又必须建立一张页表，把段中的虚页变换成内存中的实际页面。显然，与页式管理

时相同，页表中也要有实现缺页中断处理和页面保护等功能的表项。另外，由于在段页式管理中，页表不再是属于进程而是属于某个段，因此，段表中应有专项指出该段所对应页表的页表始址和页表长度。段页式管理中段表、页表以及内存的关系如图5.33所示。图中各表中其他栏可参考段式或

页式管理中的相应栏目。图5.33段页式管理中段表、页表与内存的关系3.动态地址变换过程在一般使用段页式存储管理的计算机系统中，都在内存中辟出一块固定的区域存放进程的段表和页表。因此，在段页式管理系统中，要对内存中

指令或数据进行一次存取的话，至少需要访问三次以上的内存。第一次是由段表地址寄存器得到段表始址去访问段表，由此取出对应段的页表地址。第二次则是访问页表得到所要访问的物理地址。只有在访问了段表和页表之后，第三次才能访问真正需要访问的物理单元。显然，这将使

CPU的执行指令速度大大降低。为了提高地址转换速度，设置快速联想寄存器就显得比段式管理或页式管理时更加需要。在快速联想寄存器中，存放当前最常用的段号s、页号p和对应的内存页面与其他控制用栏目。当要访问内存空间某一单元时，可在通过段表、页表进行内存地址查找的同时，根据快速联想

寄存器查找其段号和页号。如果所要访问的段或页在快速联想寄存器中，则系统不再访问内存中的段表、页表而直接把快速联想寄存器中的值与页内相对地址d拼接起来得到物理地址。经验表明，一个在快速联想寄存器中装有1/10左右的段号、页号及页面的段页式管理系统，可以通过快速联想

寄存器找到90%以上的所要访问的内存地址。段页式管理的地址变换机构如图5.34所示。图5.34段页式地址变换•总之，因为段页式管理是段式管理的页式管理方案结合而成的，所以具有它们二者的优点。但反过来说，由于管理软件的增加，复杂性和开销也就随之增加了。另外，需

要的硬件以及占用的内存也有所增加。更重要的是，如果不采用联想寄存器的方式提高CPU的访内速度，将会使得执行速度大大下降。5.6局部性原理和抖动问题•动态页式管理，段式管理以及段页式管理都提供了一种将内存和外存统一管理，内存中只存放那些经常被调用和访问的程序段和数据，而进程

或作业的其他部分则存放于外存中待需要时再调入内存的虚拟存储器的实现方法。然而，由于上述实现方法实质上要在内存和外存之间交换信息，因此，就要不断地启动外部设备以及相应的处理过程。•段式、页式以及段页式虚存实现方法都要求在内存中存放一个不小

于最低限度的程序段或数据，而且它们必须是那些正在被调用，或那些即将被调用的部分。•由模拟实验知道，在几乎所有的程序的执行中，在一段时间内，CPU总是集中地访问程序中的某一个部分而不是随机地对程序所有部分具有平均访问概率。人们把这种现象称为局部性原理(principleoflocalit

y)。•但是，如果不能正确地将那些系统所需要的局部段放入内存的话，则显然系统的效率会大大降低，甚至无法有效地工作。•试验表明，任何程序在局部性放入时，都有一个临界值要求。当内存分配小于这个临界值时，内存和外存之间的交换频率将会急剧增加，而内存分配大于这个临

界值时，再增加内存分配也不能显著减少交换次数。这个内存要求的临界值被称为工作集。如图5.35所示。图5.35内存与交换次数的关系•一个进程执行过程中缺页(missingpage)的发生有两种可能。一种是并发进程所要求的工作集总和大于内存可提供的可用区。这时，系统将无法正常工作，因为缺乏足够的空间装

入所需要的程序和数据。另一种可能性是，虽然存储管理程序为每个并发进程分配了足够的工作集，但系统无法在开始执行前选择适当的程序段和数据进入内存。这种情况下，只能依靠执行过程中，当CPU发现所要访问的指令或数据不在内存时，由硬件中断后转入中断处理程序，将所需要的程序段和

数据调入。这是一种很自然的处理方法。•当给进程分配的内存小于所要求的工作集时，由于内存外存之间交换频繁，访问外存时间和输入/输出处理时间大大增加，反而造成CPU因等待数据空转，使得整个系统性能大大下降，这就造成了系统抖动。可以利用统计模型进一步分析

工作集与抖动之间的关系:•设r为CPU在内存中存取一个内存单元的时间，t为从外存中读出一页数据所需时间，p(s)为CPU访问内存时，所访问的页正好不在内存的概率，这里s是当前进程在内存中的工作集。•显

然，在虚存情况下存取一个内存单元的平均时间可描述为T=r+p(s)*t。•由程序模拟可知，p(s)=ae-bs。•这里，0<a<1<b，ae-bs<<r。•另外，假定内存中各并发进程具有相同的统计特性，而且对于一个并发进程来说，只有

发生缺页时才变成等待状态。这是为了简化讨论而忽略了外部设备和进程通信功能的存在。•由于访问外存一个页面的速度为t，且缺页发生的概率为p(s)，则在处理机访问一个内存单元的r时间内，平均每秒引起的内外存之间页传送率为p(s)/r。也就是每r/p(s)秒需要从外存向内存传送一页。从

而，对于一个在虚存范围内执行的进程，它可以处于三种可能的状态之中，即：•(1)t＜r/p(s)•(2)t＞r/p(s)•(3)t=r/p(s)•第一种情况，由于页传送速度大于访问外存页面的速度，因此，进程在执行过程中发生缺页的次数较少，并不经常从外存调页。•

在第二种情况时，由于内外存之间的页面传送速度已经小于访问外存页面速度，因此，进程在执行过程中发生缺页的次数已经多到外存供不应求的地步。事实上，这时的系统已处于抖动状态。•第三种情况是一种较理想的情况，即进程在执行过程中所

需要的页数正好等于从外存可以调入的页数。此时该进程在内存中占有最佳工作集。•根据以上讨论可知，一个进程在内存中占有最佳工作集的条件是：p(w)=r/t•这里，r是CPU访问内存单元所需平均时间，t是访问外存一个页面

所需平均时间。•因为p(w)可表示为p(w)=ae-bw•从而有，w=(1/b)ln(at/r)•即，与内存存取速度r相比，若外存传送速度越慢，所需工作集就越大。•当然，上面讨论是在作了许多近似的情况下得出的结论。事实上，由于各进程所包

含的程序段多少，选用的淘汰算法等不一样，工作集的选择也不一样。一般来说，选择工作集有静态和动态两种选择方法，这里不再进一步介绍。•另外，由以上讨论，我们可以找出解决抖动问题的几种关键办法。•抖动只有在t>r/p

(s)时才会发生。而p(s)等于ae-bs是一个与工作集s、参数a和b有关的概率值。p(s)是可以改变的。对于给定的系统来说，t和r则是一个很难改变的数字。显然，解决抖动问题的最关键办法是将p(s)减少到

使t=r/p(s)。这只需要：•增加s，也就是扩大工作集，或是•改变参数a和b，也就是选择不同的淘汰算法以解决抖动问题•即，与内存存取速度r相比，若外存传送速度越慢，所需工作集就越大。•在物理系统中，为了防止抖动的产生，在进行淘汰或置换时，一般总是把缺页进程锁住，不让其换出，而调入的页或段总是占据

那些暂时得不到执行的进程所占有的内存区域，从而扩大缺页进程的工作集。UNIXSystemⅤ中就是采用的这种方法。•比较几种存储管理方法所提供的功能和所需硬件支持习题5.1存储管理的主要功能是什么？5.2什么是虚拟存储器，其特点是什么？5.3实现地址重定位的方法有哪几类？形式化

地描述动态重定位过程。5.4常用的内存信息保护方法有哪几种？它们各自的特点是什么？5.5如果把DOS的执行模式改为保护模式，起码应作怎样的修改？5.6动态分区式管理的常用内存分配算法有哪几种？比较它们各自的优缺点。5.75.2节讨论的分区式管理可以实现虚存吗？如果不能，需怎样修改？试设

计一个分区式管理实现虚存的程序流程图。如果能，试说明理由。5.8简述什么是覆盖？什么是交换？覆盖和交换的区别是什么？5.9什么是页式管理？静态页式管理可以实现虚存吗？习题(续）5.10什么是请求页式管理？试设计和描述一个请求页式管理时的

内存页面分配和回收算法(包括缺页处理部分)。5.11请求页式管理中有哪几种常用的页面置换算法？试比较它们的优缺点。5.12什么是Belady现象？试找出一个Belady现象的例子。5.13描述一个包括页面分配与回收、页面置换和

存储保护的请求页式存储管理系统。5.14什么是段式管理？它与页式管理有何区别？5.15段式管理可以实现虚存吗？如果可以，简述实现方法。5.16为什么要提出段页式管理？它与段式管理及页式管理有何区别？习题（续）5.17为什么说段页式管理时的虚地址仍是二维的？5.18段页

式管理的主要缺点是什么？有什么改进办法？5.19什么是局部性原理？什么是抖动？你有什么办法减少系统的抖动现象？