操作系统 Operating System

第4章 存储管理 §4.1 存储管理的原理 §4.2 连续分配存储管理 §4.3 离散分配存储管理 §4.4 内核主存管理 §4.1 存储管理的原理 §4.2 连续分配存储管理 §4.3 离散分配存储管理 §4.4 内核主存管理 §4.5 虚拟存储技术 §4.6 虚拟页式存储管理 §4.7 虚拟段式存储管理 §4.8 存储管理实例

§4.5 虚拟存储技术 §4.5.1 程序局部性原理 §4.5.2 虚拟存储的实现 §4.5 虚拟存储技术 虚拟内存技术(Virtual Memory)诞生于1961年。 广泛使用是从上个世纪70年代初以后，今天几乎所有的操作系统都采用虚拟内存技术来管理内存。 这是一种利用虚拟存储器来逻辑扩充物理内存的技术。其基本思想是用软硬件技术把内存与外存这两级存储器当成一级存储器来用，从而给用户提供了一个比内存也比任何应用程序大得多的虚拟存储器，使得用户编程时再也不用考虑内存大小的限制了，给用户编程带来极大的方便。 虚拟内存技术的实现也利用了自动覆盖和交换技术。 §4.5.1 程序局部性原理 §4.5.2 虚拟存储的实现

§4.5.1 程序局部性原理 1.局部性原理(principle of locality)： 2.局部性主要表现： 指程序在执行过程中的一个较短时期内，所执行的指令地址和指令的操作数地址，分别局限于一定区域。 2.局部性主要表现： 时间局部性：是指一段指令在某一时间段内会被反复执行。即程序某一部分的数据或指令被重复性地访问，它们对应于程序结构中的循环、子程序、常用到的变量及数据等 ； 空间局部性：是指一旦某一个存储单元被访问，那么它附近的单元也将很快被访问。这对应于程序结构中的顺序执行的指令、线性数据结构以及在相邻位置存放的数据或变量等。而程序中的分支和调用子程序只是将程序的访问空间从一处移到另外一处，仍具有局部性。

排他性：程序运行不但体现在时间、空间的局部性，还体现在某些程序段执行的排他性。 即程序设计者编程时要考虑程序执行时所能遇到的各种情况，但具体到一次程序的执行，并不会发生所有的状况。因而某些程序段在进程整个运行期间，可能根本不使用，如出错处理、分支语句等。因而，没有用到的程序段就不必调入内存。另外，有些程序段仅执行一次，以后就再也不会用到，这样的程序段也没有必要一直占用内存空间。 综上所述：程序只要装入内存一部分就可以运行，当用到不在内存的部分时，再将其装入内存。换句话就是说程序全部装入内存并不是程序运行的必要条件。

§4.5.2 虚拟存储的实现 1.虚拟存储技术 2.虚拟技术实现的关键 如果把程序部分装入内存，其余大部分放在外存，而程序又能运行，这样我们就拥有了一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间。即用大容量的外存来模拟内存，这种存储模式就称之为虚拟存储技术。 2.虚拟技术实现的关键 (1)怎样才能发现欲执行的指令或数据不在内存? 简单有效方法就是进行标识 (2)怎样将不在内存的部分调入进来。 通常系统采用中断技术完成调入工作。 (3)在内存中的作业如何组织？ 一个进程可被分为多次调入内存，这样很难保证进程在内存中占据一个连续的空间，实际上进程在内存中是离散存储的。

虚拟技术进一步说明 因而系统要提供必要的硬件支持，如虚拟页式存储中的页表机制、缺页中断机构以及相应的地址变换机构。 虚拟存储技术是将内存与外存有机地结合在一起，从而得到一个容量很大的虚拟空间。使用户感到有一个很大的内存，不用再考虑内存的容量限制。 虚存虽然比内存要大得多，但不可能无限大，其大小要受到外存空间的限制以及CPU地址所能表示范围的限制。

3.引入虚拟存储技术的好处 大程序：可在较小的可用内存中执行较大的用户程序； 大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(real memory) 并发：可在内存中容纳更多程序并发执行； 易于开发：与覆盖技术比较，不必影响编程时的程序结构 总容量不超过物理内存和外存交换区容量之和。其运行速度接近于内存，每位的成本又接近于外存，是一种性能非常优越的存储管理技术

4. 虚拟存储技术的特征 不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续（数据段和栈段之间的空闲空间，共享段和动态链接库占用的空间） 部分交换：与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的； 大空间：通过物理内存和快速外存相结合，提供大范围的虚拟地址空间 虚拟存储技术的种类： 虚拟页式 虚拟段式 虚拟段页式

§4.6 虚拟页式存储管理 §4.6.1 虚拟页式存储的实现 §4.6.2 页面分配策略 §4.6.3 页面置换方法 §4.6 虚拟页式存储管理 §4.6.1 虚拟页式存储的实现 §4.6.2 页面分配策略 §4.6.3 页面置换方法 §4.6.4 虚拟页式存储的优缺点

§4.6.1 虚拟页式存储的实现 1.基本原理 系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小，在作业运行前，只把初始需要的一部分页面装入内存块里，运行中需要访问自己地址空间中的但当前不在内存的页面时产生缺页中断，由缺页中断服务程序将所需的页面调入内存，若此时内存中没有空闲物理块安置请求调入的新页面，则系统按预定的置换策略自动选择一个或一些在内存的页面，把它们换出到外存。 这里的请求调入和置换功能都是比实分页存储管理增加的内容，是实现虚拟存储的主要功能。 返回

页面的动态调度步骤： 1、找到被访问页面在外存的地址； 2、在内存中找一个空闲页面； （1）如果没有，按照淘汰算法选择一个内存页面； （2）将此内存页面写回外存，修改页表及页面分配表； 3、读入所需的页面，修改页表及页面分配表； 4、重新启动进程执行被中断的指令。

标记某页是否在内存，用于查询要访问的页在不在内存。页表如下： 2.页表机制 标记某页是否在内存，用于查询要访问的页在不在内存。页表如下： 页号 物理块号 状态位P 访问位A 修改位M 外存地址 其中： 外存地址指出该页在外存的地址，供调入该页时用； 状态为指示该页是否在内存，供程序访问时用，也是检查是否缺页的标志位，如置1表示在内存 ； 访问位或访问字段则是该页被访问过的标志或该页被访问过的次数； 修改位表示该页是否被修改过；存取控制字段则是用来限制页面被安全共享的。

3.动态地址变换 在虚拟页式存储中，应采用动态地址变换方式，因为某一欲执行的指令可能不在内存，只能在指令执行之前完成地址变换。任一作业都应在自己的虚拟地址空间中执行，所以要为用户作业设置一个虚拟地址指针VP，虚拟地址依然是由页号和页内偏移地址组成的。 系统总是执行VP虚指针所指向的指令，为了将虚拟地址VP变换为对应的实存地址，因此先要查找页表。若从页表中查出此页不在内存（状态位为0），则产生一个缺页中断。此时，进程暂停当前指令执行，CPU转去执行缺页中断处理程序。若该页已在内存，则指令的地址映射过程与页式存储是一样的。即将块号和页内地址相并接形成物理地址IP，处理器再从IP中取指令执行。

4.缺页中断

5.缺页率 虽然通过缺页中断将所需要的页调入内存，但缺页中断的频繁发生会严重影响程序执行的效率。为了标识缺页中断发生的频度，可以引入缺页率来表示。 设进程在其执行期间共进行了S次访页操作，其中成功访页次数为A（访问时该页在主存），不成功的访页次数为B（即发生了缺页中断），显然有：S=A+B， 则该进程的缺页率f定义为：f＝B/S。 显然缺页率越低越好。

§4.6.2 页面分配策略 虚拟存储管理在进行页面分配时，要考虑这样的问题：空闲页面如何管理；采用什么样的分配策略；为进程分配多少物理块比较合适；在什么时间进行页面分配等。

1.空闲页面管理 同页式存储管理相似，虚拟存储方式下的空闲页面的管理也可以采用位示图或空闲页面链的形式。 由于主存中所有进程的虚拟地址空间之和远大于主存空间，因此进程执行时常发生缺页中断，这样不断地调入新页，很快就使主存空间饱和。以后再发生缺页时，要先淘汰一页才能装入新页，这使得缺页处理时间过长，减缓了进程的执行速度，从而影响到系统的性能。 在实际的系统中，总是维持一定数量的空闲块，而不是耗尽所有的空闲块。即空闲块数可以在某一区间浮动，一旦空闲块数小于下限值，系统就进行页面置换，以释放出一些空闲块，使得总的空闲块数不超过系统规定的上限值即可。即系统设置专门的独立进程负责页面置换，以保证链表的适当规模。

2 分配策略（内存） 可变分配：是指一个进程所拥有的物理块数是不定的，这种分配方式称之为可变分配。 固定分配是指为每个进程分配一固定页数的内存空间，在整个运行期间都不再改变。 ⑴ 平均分配算法，是将系统中所有可供分配的物理块，平均分配给每一个进程。例如，当系统中有80个空闲块，4个进程时，每个进程可分得20个物理块。这种平均分配方式因其未考虑各进程本身的大小，会造成事实上的不公平。如有一个进程其大小为100页，只分配给它20个块，这样它必将会有很高的缺页率；而另一个进程只有10页，却有10个块在闲置未用。所以在平均的思想下，还要考虑进程的大小。

⑵ 按比例分配算法，根据进程的大小按比例分配空闲块。设系统中现有m个进程、n个空闲块，每个进程拥有的页数为Si，则系统中所有进程页数之和为： S = S1 + S2 + S3 + … + Sm 则为每个进程分配的物理块数为： Bi = （Si / S）× n ，Bi应向下取整。 ⑶ 优先权分配算法，为优先权高的作业分配较多的内存空间，这样可以使重要或紧迫的任务尽快完成。这时可以将内存中的空闲块分成两部分：一部分按比例分配给各进程，另一部分则根据各进程的优先权，适当地为其增加相应份额。

一个进程在运行之前，将其页面全部装入外存。当某一外存页面被调入内存时，并不释放所占用的外存页面。 2 分配策略（外存） 1、静态分配 一个进程在运行之前，将其页面全部装入外存。当某一外存页面被调入内存时，并不释放所占用的外存页面。 2、动态分配 一个进程在运行之前，仅将未装入内存的那部分页面装入外存。当某一外存页面被调入内存时，释放所占用的外存页面。

3.工作集 (1)为保证进程能正常运行最少需要多少物理块。 从理论上讲，进程只要获得一个物理块就可以运行。但是进程正常运行所需的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。由于分页是系统的行为，可能会出现下面的情景： 涉及6次缺页中断的指令 1 2 3 4 5 6 由此可见，系统应保证任一条指令执行时，其所涉及的虚拟地址所在的页都应在内存中。这个页数就是进程所需要的最小块数，若系统为进程所分配的物理块数少于此值时，进程将无法运行。 指令copy A to B 数据A： 数据B：

(2)为使进程能有效地工作，应为它分配多少物理块合适 随着为每个进程所分配物理块数目的减少，将使进程执行中的缺页率提高，导致非生产性开销过大，从而降低了进程的执行速度，严重时导致进程不能向前推进。最少物理块数只能保证程序能执行下去，而不是最合适的块数。 !!在1968年，Denning提出了工作集理论。所谓工作集就是进程在某段时间里实际上要访问的页的集合。依据程序执行时的局部特性，可以利用程序过去的行为来估计它未来的行为。故定义运行进程在t－w到t这个时间间隔内所访问的页的集合为该进程在时间t的工作集，记为W（t，w）。并把变量w称之为“工作集窗口尺寸”，工作集中所包含的页面数称为“工作集尺寸”，记为|W(t,w)|。

例如: 访问页面：２３３３２３２５５８５ 访问页面： T w t-w t W(t,w)={2,3,5,8} ２３３３２３２５５８５５８５３９８９５８７８ T w w t1 t2 W(t1,w)={2,3,5,8} W(t2,w)={3,5,7,8,9}

(3)工作集的应用 工作集W（t，w）是二元函数，随t、w的值而改变。首先工作集与时间有关，即不同时间的工作集其所包含的页面可能不同，其所包含的页面个数也可能不同；其次工作集也是工作集窗口尺寸w的函数，体现在工作集尺寸|W(t,w)|随w的增加而变大，即满足|W(t,w)|≤|W(t,w+a)|，a>0。 工作集窗口尺寸与缺页率关系密切，若w增大，工作集尺寸|W|随之增加（即所含的页面数增多），缺页率就会下降。倘若w含盖了整个作业虚拟空间，缺页率降为0，也就失去了虚存意义；反之若w选取过小，将引起频繁缺页，导致系统性能下降。二者之间的关系可以如图所示。

虚存中并不是要取消缺页率，而是要使缺页率维持在一个较低的水平上。因此可以取拐点所对应的工作集尺寸作为分给进程的物理块数，实验分析表明，这个数应是进程总页面数的一半。即一个进程应获得其所需页数一半的空间时，再进入内存执行。

4.页面调入时机 即何时将一个页面由外存调入内存。 ⑴ 预调页策略 也称先行调度，即一页面被访问前就已经预先置入内存，以减少今后的缺页率。 主要适于进程的许多页存放在外存的连续区域中的情况。有的系统结合请求调入使用，即每次缺页时装入多个页面。 优点：提高调页的I/O效率。 缺点：基于预测，若调入的页在以后很少被访问，则效率低。预调页的成功率仅约50%，常用于程序装入时的调页。

⑵ 请求调页策略 当发生页面故障时进行调度，即当进程访问不在内存的页面引发缺页中断时，由系统根据这种访问请求把所缺页面装入内存。 优点：由请求调入策略装入的页一定会被访问，再加之比较容易实现，故在目前的虚拟存储器中，大多采用此策略。 缺点：每次仅调入一页，增加了磁盘I/O的启动频率。

5.从何处调入页面 在请求分页系统中，常把外存分为两部分：一部分是文件区，用于存放文件；另一部分是对换区，用于存放对换页面。通常，对换区的磁盘输入输出速度比文件区的高，这是因为对换区所规定的盘块要比文件区的大得多。 ⑴ 从交换区调入 若系统拥有足够的对换区空间，可在进程运行前，将与该进程有关的文件拷贝到对换区。以后就从对换区调入所需页面，以提高调页速度。

⑵ 从交换区及文件区调入 若系统缺少足够的对换区空间，则在交换区中只保存被修改过的页面。因为未被修改的页面在文件区中有副本。因此凡是没被修改的页，均从文件区调入；而已修改过的页面则从交换区调入。 ⑶ UNIX方式 与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过而又被换出的页面，总是存放在对换区中。因此在下次调入时，应从对换区调入。由于在UNIX系统中允许页面共享，因此，某进程所请求的页面有可能已由其它进程调入内存，此时也就无须再从对换区调入。

§4.6.3 页面置换方法 1.页面置换方式 当内存空间已没有空闲页面而又要调入新页时，必须采用一定的算法在内存中选择某一页面淘汰，所采用的算法称之为页面置换算法。 如果被淘汰的页面在内存期间曾被修改过，还要将此页重新写回到外存，以便保留最新的副本。然后再换进新的页面。 (1)页面置换方式 页面淘汰可以在整个内存空间范围内进行，称之为全局置换。也可以只在一个进程空间范围内考虑，称之为局部置换。即当某一进程请求新页时，而该进程又没有空闲块，则只能淘汰自己的一个页面而不能淘汰其它进程的页面。

为进程分配的物理块数在其运行期间是可变的，则称为可变分配。进程在运行中，系统可调整为该进程分配的物理块，直至进程的缺页率达到适当程度。 (2) 空闲块分配方式 若为进程分配固定的物理块数，在其执行期间再也不改变，则称为固定分配。初始进程块数的多少难以确定。若太少，则缺页频繁，系统开销大；若太多，则并发进程数目少，造成CPU空闲或其它资源空闲的情况。 为进程分配的物理块数在其运行期间是可变的，则称为可变分配。进程在运行中，系统可调整为该进程分配的物理块，直至进程的缺页率达到适当程度。 (3) 内存管理策略 在页面置换算法讨论中，为了比较各种方法的优劣，总是限定为固定分配局部置换。 固定分配局部置换： 固定分配全局置换： 可变分配局部置换 可变分配全局置换 不可能

2.页面置换算法 (1)最佳淘汰算法——OPT(Optimal) 这是Belady于1966年提出的一种理论上的算法。该算法每次都淘汰以后永不使用的，或者过最长的时间后才会被访问的页面。 显然，采用这种算法会保证最低的缺页率，但它是无法实现的，因为它必须知道页面“将来”的访问情况。不过，该算法仍有一定意义，可作为衡量其他算法优劣的一个标准。

假定系统为某个进程分配了三个物理块，进程的访问顺序为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2 OPT置换算法示例： 假定系统为某个进程分配了三个物理块，进程的访问顺序为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2 7，0，1， 2，0，3，0，4，2， 3，0 ，3， 2，1， 2 7 * 7 0 * 7 0 1 * 2 0 1 * 2 0 1 2 0 3 * 2 0 3 2 4 3 * 2 4 3 2 4 3 2 0 3 * 2 0 3 2 0 3 2 1 3 * 2 1 3 缺页次数8，成功访问次数7次， 缺页率f=8/15=53.33%

（2）先进先出淘汰算法——FIFO 这是最早出现的淘汰算法。 总是淘汰最先进入内存的页面。它实现简单，只需把进程中已调入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存中最老的页面。 缺点：效率不高，因为它与进程实际的运行规律不相适应，比如常用的全局变量所在的页面或者循环体所在页面都可能被它选为淘汰对象。出现belady现象。

Belady现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。 Belady现象的描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S, N)时而增大，时而减小。 Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。

3块内存时，缺页率f=12/15=80%；4块f=8/15=53.33% FIFO淘汰算法示例： 7，0，1， 2，0，3，0，4， 2， 3，0 ，3， 2，1， 2 7 * 7 0 * 7 0 1 * 2 0 1 * 2 0 1 2 3 1 * 2 3 0 * 4 3 0 * 4 2 0 * 4 2 3 * 0 2 3 * 0 2 3 0 2 3 0 1 3 * 0 1 2 * 7，0，1， 2，0，3，0，4， 2， 3，0 ，3， 2，1， 2 7 * 7 0 * 7 0 1 * 7 0 1 2 * 7 0 1 2 3 0 1 2 * 3 0 1 2 3 4 1 2 * 3 4 1 2 3 4 1 2 3 4 0 2 * 3 4 0 2 3 4 0 2 3 4 0 1 * 2 4 0 1 * 3块内存时，缺页率f=12/15=80%；4块f=8/15=53.33%

练习: 对如下的页面访问序列: 1 2 3 4 1 2 5 1 2 3 4 5 设进程开始运行时所有页面均在外存,采用FIFO淘汰算法, 计算进程所分的物理块分别为3和4时,缺页率各是多少?

(3)最近最久未使用算法(LRU, Least Recently Used） 根据页面调入内存后的使用情况，选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。 OPT算法使用页面将要被访问的时间，LRU算法使用页面最后一次被访问的时间。二者唯一的差别是：OPT是向后看的，而LRU是向前看的。 10次，缺页率f=10/15=66.67% 7，0，1， 2，0，3，0，4， 2， 3，0 ，3， 2，1， 2 7 * 7 0 * 7 0 1 * 2 0 1 * 2 0 1 2 0 3 * 2 0 3 4 0 3 * 4 0 2 * 4 3 2 * 0 3 2 * 0 3 2 0 3 2 1 3 2 * 1 3 2

LRU的两个实现算法： ①计时法：对于每一页面增设一个访问时间计时器，每当一个页面被访问时，就将当时的绝对时钟拷贝到对应的访问时间计时器中，这样系统记录了内存中所有页面最后一次被访问的时间。淘汰时，选取访问时间计时器的值最小的页面。 ②堆栈法：每当进程访问某页面时，便将该页面的页号从栈中移出，将它压入栈顶。栈顶始终是最新被访问的页面的编号。栈底则是最近最久未被使用的页面的页面号。

假定现有一进程所访问的页面的页面号序列为：4，8，0，8，1，0，2，1，2，6 随着进程的访问，栈中页面号的变化情况： 4，8，0，8，1，0，1，2，1，2，6 2 1 2 6 1 0 1 1 2 1 2 0 8 8 1 0 0 0 0 1 8 8 0 0 8 8 8 8 8 0 4 4 4 4 4 4 4 4 4 4 8 LRU的开销是很大的，必须有硬件的支持，完全由软件实现其速度至少会减少10倍，因此LRU近似算法更实用些。

(4)二次机会淘汰算法—SC(Second Chance) 这是一种LRU的近似算法，是通过对FIFO算法进行简单改造，结合页表中的访问位而得来一种淘汰算法。 该算法首先检查位于FIFO链链首的页，如果它的访问位为0，则选择该页淘汰；如果它的访问位为1，则清除其访问位，将它移至FIFO链的链尾，重复此算法的查找过程，直至遇到新链首页是一个访问位为0的较早进入内存的页为止，把它选为被淘汰的页。

（5）时钟(Clock)淘汰算法 缺点：就是需要把访问位为1的处于链首的页移至链尾，这需要一定的开销。一种改进的方法就是把进程所访问的页面链成一个环形链表，再设一个指针指向最老的页面，于是形成了一种简单实用的LRU近似算法——时钟淘汰算法。 该算法首先检测指针所指的页面，如果它的访问位为0，则淘汰该页，新装入的页插入到此位置，然后指针前进一个位置；如果它的访问位为1，则清除为0，并将指针前进一个位置，继续检查访问位。重复此过程，直到找到访问位为0的页面为止。

算法流程参见书上第153页。

(6)最近未用淘汰算法—NUR(Not Used Recently) 它把FIFO算法的思想与页面的访问位和修改位结合起来确定一个接近LRU算法的淘汰对象。 该算法每次都尽量选择最近最久未被写过的页面淘汰，这种干净的页面可以不被写回到磁盘。在实现时，为每一个页面设置初始值为0的访问位和修改位。当对某页面执行写操作时，其修改位和访问位均由硬件置成1；当对某页面执行读操作时，只有其访问位被硬件置成1。

②访问位＝０，修改位＝１；淘汰之前写回外存； ③访问位＝１，修改位＝０；直接淘汰； ④访问位＝１，修改位＝１；淘汰之前写回外存； 按照下列次序选择被淘汰的页面： 最近未使用淘汰算法就是LRU的一种近似算法，它总是淘汰最近未使用的页，如果被淘汰的页在内存期间没有被修改过，该页可不必重新写入外存，将新页覆盖到被淘汰的页上即可。 访问位A＝0 表示该页未被访问过； 1 表示该页已被访问过； 修改位M＝ 0 表示该页未被修改过 1 表示该页已被修改过 ①访问位＝０，修改位＝０；直接淘汰； ②访问位＝０，修改位＝１；淘汰之前写回外存； ③访问位＝１，修改位＝０；直接淘汰； ④访问位＝１，修改位＝１；淘汰之前写回外存；

算法步骤：见书上第154页。

3.影响缺页中断率的因素 (1)分配给作业的内存块数 作业的缺页中断率与作业所占内存块数成反比。分配给作业的内存块数太少是导致抖动现象发生的最主要的原因，实验分析表明：对所有的程序来说，要使其有效地工作，它在内存中的页面数不应少于它的总页面数的一半。

(2)页面大小的选择 虽然缺页中断率与页面尺寸成反比，但页面尺寸却不能一味地求大，它一般在0.5KB~4KB之间，是个实验统计值。因为页面大时，页表较小，占空间少，查表速度快，缺页中断次数少，但页面调度时间长，页内碎片较大。页面小时，恰恰相反。 (3)用户程序编制的方法 作业的缺页中断率与程序的局部化（包括时间局部化和空间局部化）程度成反比。用户程序编制的方法不合适可能导致程序运行的时空复杂度高，缺页次数多。

例如：一个程序将128*128的数组置初值“0”，假定它仅分得一个主存块，页面尺寸为128个字，数组中的元素各行分别存放在一页中，开始时第一页在主存中，若程序如下两种方式编写： int A[128][128]; for(int i=0;i<128;i++) for(int j=0;j<128;j++) A[i][j]=0; 缺页中断（128-1）次 int A[128][128]; for(int j=0;j<128;j++) for(int i=0;i<128;i++) A[i][j]=0; 缺页中断(128*128-1)次

(4)页面调度算法 抖动又叫颠簸，是指一段时间里，页面在内存与外存之间频繁地调度或换入换出，以至于系统用于调度页面所需要的时间比进程实际运行所占用的时间还要多。 好的淘汰算法会维持一个较低的缺页率。若页面置换算法不好，会使系统出现抖动现象。 显然，抖动是由于缺页中断率很高而引起的一种坏现象，它将严重影响系统的效率，甚至可能使系统全面崩溃。

防止抖动现象的产生和扩展，具体方法: ⑴采取局部置换策略 这样，即使有某个进程发生了“抖动”，也不致引起其它进程也产生抖动，从而把抖动局限于较小的范围内。 这种方法并不很好，因为它不能从根本上防止抖动的发生；而且在某进程发生抖动后，还会长期地处于磁盘输入输出的等待队列中，这又会使其它进程缺页中断的处理时间增长，从而延长了等效的访问时间。 ⑵ L=S准则 Denning于1980年提出了“L=S准则”，用来调整多道程序度，以使产生缺页的平均时间L等于系统处理进程缺页的平均时间S。理论和实践表明，此时的CPU利用得最好。该准则也得到其它研究人员的证实。

防止抖动现象的产生和扩展，具体方法: ⑶挂起若干进程 当多道程序度偏高时，为了防止发生“抖动”，可用的一个简单易行的办法是挂起一些进程，以便腾出内存空间来分配给抖动的进程。被挂起的进程通常是选择优先权最低或较低的；当内存非常拥挤时，也可以选择一个并不很重要的、但确较大的进程挂起，以便能一次释放出较大的内存空间；或者是将具有最多剩余执行时间的进程挂起。

§4.6.4 虚拟页式存储的优缺点 1.优点 ⑴ 主存利用率比较高。平均每个用户作业只浪费一半的页空间，内存规范易于管理。 §4.6.4 虚拟页式存储的优缺点 1.优点 ⑴ 主存利用率比较高。平均每个用户作业只浪费一半的页空间，内存规范易于管理。 ⑵ 对磁盘管理比较容易。因为页的大小一般取磁盘物理块大小的整数倍。 ⑶ 地址映射和变换的速度比较快。在把用户程序装入到主存储器的过程中，只要建立用户程序的虚页号与主存储器的实页号之间的对应关系即可（拼接得到物理地址），不必使用整个主存的地址长度，也不必考虑每页的长度等。

2.缺点 ⑴ 程序的模块化性能不好。 由于用户程序是强制按照固定大小的页来划分的，而程序段的实际长度一般是不固定的。因此，虚拟页式存储器中一页通常不能表示一个完整的程序功能。一页可能只是一个程序段中的一部分，也可能在一页中包含了两个或两个以上程序段。 ⑵ 页表很长，需要占用很大的存储空间。 通常，虚拟存储器中的每一页在页表中都要占一个页表项。假设有一个虚拟页式存储器，它的虚拟存储空间大小为4GB，每一页的大小为1KB，则页表的容量为4M（个页表项）。如果每个页表项占用4个字节，则页表的存储容量为16MB。

§4.7 虚拟段式存储管理 §4.7.1 虚拟段式存储的实现 §4.7.2 段的共享和保护 §4.7.3虚拟段式存储管理的优缺点 §4.7 虚拟段式存储管理 §4.7.1 虚拟段式存储的实现 §4.7.2 段的共享和保护 §4.7.3虚拟段式存储管理的优缺点 §4.7.4 虚拟段页式存储管理

§4.7.1 虚拟段式存储的实现 1.虚拟段式存储原理 为了能实现虚拟存储，段式逻辑地址空间中的程序段在运行时并不全部装入内存，而是如同请求式分页存储管理，首先调入一个或若干个程序段运行，在运行过程中调用到哪段时，就根据该段长度在内存分配一个连续的分区给它使用。若内存中没有足够大的空闲分区，则考虑进行段的紧凑或将某段或某些段淘汰出去。相应于请求式分页存储管理，这种存储管理技术称为请求式分段存储管理。

2.段表 逻辑地址同前： 类似于请求式分页存储管理的页表，为了实现动态地址变换和存储保护，系统要为每一个作业建立一张段表。段表中的每一个表目对应着作业地址空间的一个程序段，其一般格式为： 段 号 存在 位P 访问 位A 修改 位M 存取 方式 增补 位 长度 段的 基址 外存 地址 存在位P表示该段是否在内存，如为0表示不在，为1表示在内存； 存取方式表示可对该段施加的操作，如只读、读写、还是执行。 增补位表示该段在运行期间是否可以扩展空间

3.请求式分段动态地址变换过程 图4.32 地址变换与中断处理流程

4.缺段中断 在虚拟段式存储系统中，采用的是请求调段策略。即每当进程所要访问的段尚未调入内存时，便由缺段中断机构产生一缺段中断信号，进入OS后由缺断中断处理程序将所需的段调入内存。 再调入新段时，也会有内存空间不够用的情况，也需要淘汰内存中的一个或多个段。如果此程序段从装入内存起一直没有被修改过，只要用新调入的程序段把它覆盖掉即可。若这个程序段被修改过，则必须先把该程序段全部写回到磁盘存储器中，才能占用被淘汰段原来存放的空间。 因为段要占用连续的空间，因此当内存中没有能够满足段长需要的空闲区时，系统还要合并空闲区，以便满足分段的需求。

§4.7.2 段的共享和保护 1.段的共享 在多道环境下，常常有许多子程序和应用程序是被多用户所使用的。最好的办法是在内存中只保留一个副本，供多个用户使用，称为共享。 段共享时，用户可以使用不相同的段名来共享同一个段。进程将共享段填写到自己的段表中，并置以适当的读写控制权，就可以做到共享一个逻辑上完整的内存段信息。 由于系统中有许多的共享段，而每一个共享段都可能被多个进程共享。因此系统需要对共享段进行统一的管理，设一张共享段表，每一个共享段都在表中占据一个表项。 共享段应该是可重入的。

图4.33 段式系统中共享内存副本示意图

共享段表 段名 段长 存在位 共享计数 内存基址 外存始址 共享该段的进程登记表 状态 进程名 进程号 段号 存取权限 … 其中存在位表示该共享段是否已被调入内存，共享计数是用来统计当前有多少个进程共享该段。系统可以为不同的进程使用该段设置不同的权限，以防止进程越权操作。 当进程请求共享段时，若该共享段未在内存，也是由缺段中断将其调入内存，同时为该段建立相应的共享段表项，共享计数设为1，将进程填写到共享段表项中，再将共享段填写到进程的段表中。若该共享段已在内存，只要将共享计数加1，再修改相应的表项即可。不用时做相反工作。

2.段的保护(两种保护方式) (1)地址越界保护法。主要是利用段表寄存器中的段表长及段表中的段长信息实现的。首先将逻辑地址空间的段号与段表长度进行比较;其次还要检查段内地址是否等于或大于段长。从而保证了每个进程只能在自己的地址空间内运行。 (2)存取方式控制保护法。是利用段表项中的“存取控制”字段实现的，存取控制字段规定了对该段的访问方式。通常的访问方式有： ⑴只读； ⑵只执行，只允许进程调用该段去执行，但不准读写该段； ⑶读/写，允许进程对该段进行读写访问。 对于共享段更应对不同的进程设置不同的存取权限控制。既要保证信息的安全，又要满足运行需要。

§4.7.3虚拟段式存储管理的优缺点 1.优点 ⑴ 程序的模块化性能好。由于各个程序段在功能上是相互独立的，因此，一个程序段的修改和增删等不会影响其它程序，从而可以缩短程序的编制和调试时间。 ⑵ 便于实现信息的保护。在一般情况下，一段程序是否需要保护是根据这个程序段的功能来决定的。因此，只要在段表中设置一个信息保护字段，就能根据需要很方便地实现对该程序段的保护。 ⑶ 便于程序和数据的共享。被共享的程序段只要在主存中装入一次即可，同时将该共享段填入调用进程的段表中。对于进程来讲其使用与普通段没有什么差别，即实现程序段的共享很容易。 ⑷ 程序的动态链接和调度比较容易。

2.缺点 ⑴ 地址变换所花费的时间比较长。 要使用主存全地址（段长和段基址），每次地址变换都要做加法运算。 ⑵ 主存储器的利用率往往比较低。 由于每个程序段的长度是不同的，一个程序段通常要装在一个连续的主存空间中，程序段在主存储器中不断地调入调出，有些程序段在执行过程中还要动态增加长度，从而使得主存储器中有很多的空隙存在。当然，也可以采用一些好的算法来减少空隙的数量，或者通过定时运行回收程序来合并这些空隙，但这无疑增加了系统开销。

§4.7.4 虚拟段页式存储管理 将虚拟段式和虚拟页式存储管理技术结合起来，就形成了虚拟段页式存储管理方式。虚拟段页式存储方式兼具虚拟段式和虚拟页式的优点，例如，用户程序可以模块化编写，程序段的共享和信息的保护都比较方便等。另一方面也具有虚拟页式存储的优点，例如，主存储器的利用率高，对磁盘存储器的管理比较容易等。

1.虚拟段页式存储原理 在虚拟段页式存储方式中，程序员仍然按照逻辑的程序段来编写程序，但每个程序段又被分成若干个固定大小的页，相似于段页式存储管理。系统将作业的部分页装入内存，执行时用到不在内存的段或页时再将其调入内存。 在虚拟段页式存储中，用户看到的逻辑地址仍然是二维的，即段号和段内地址。但系统对内存的管理则是采用了虚拟页式管理方式。

2.地址映射 在虚拟段页式管理中，用户作业仍是在自己的虚拟地址空间中运行，虚拟地址由三部分组成，即段号S、虚页号P和页内偏移地址D。在程序运行过程中，要把用户程序中的虚拟地址变换成主存实地址，必须分两步进行。首先查段表，若该段的存在位为0则产生一个缺段中断，读入该段的页表；其次再查找页表，看该页是否在内存，若不在内存则产生一个缺页中断，调入该页；最后把块号p与页内偏移地址d拼接起来就得到了主存的实地址。 虽然虚拟段页式存储方式兼具虚拟段式和虚拟页式的优点，但也有不足之处，功能的增强导致实现变得复杂及管理开销加大，需要更多的硬件支持。