计算机操作系统第5章

1、1计算机操作系统计算机操作系统第第5章章 内存管理内存管理2目目 录录l5.1 概述概述l5.2 地址重定位地址重定位l5.3 分区存储管理分区存储管理l5.4 页式存储管理页式存储管理 l5.5 段式与段页式存储管理段式与段页式存储管理l5.6 内存扩充技术内存扩充技术 l5.7 虚拟存储管理虚拟存储管理3学习目标l了解存储管理的目的与功能，熟悉各种存储器管理的方式及其实现方法。l了解重定位、虚拟存储器的概念以及其技术。l掌握分区、页式、段式与段页式存储管理的实现原理和实现方法。 l掌握虚拟存储器中的页面置换算法及请求分页系统性能分析。45.1.1 存储层次结构l第一层次是高速、昂贵而容量很

2、小的高速缓冲存高速缓冲存储器（储器（Cache）和寄存器）和寄存器；l第二层次是速度快、价格高而数据易丢失的内存内存和磁盘缓存和磁盘缓存；l第三层次是速度较低、价格低廉、容量极大而存储内容不易丢失的外存和可移动磁盘介质外存和可移动磁盘介质，如硬盘、光盘、U盘等。5图 5.1 存储层次结构5.1.1 存储层次结构65.1.1 存储层次结构1内存内存 主存储器简称内存或主存内存或主存，是计算机系统中的主要部件，用于保存进程运行时的程序和数据，也称可执行存储器。2寄存器寄存器 寄存器具有与处理机相同的速度，故对寄存器的访问寄存器的访问速度最快速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容

3、量不可能做得很大。 75.1.1 存储层次结构3高速缓冲存储器高速缓冲存储器高速缓存是现代计算机结构中的一个重要部件，它是介于寄存器和存储器之间的存储器介于寄存器和存储器之间的存储器，主要用于备份主存中较常用的数据，以备份主存中较常用的数据，以减少处理机对主减少处理机对主存储器的访问次数存储器的访问次数，这样可大幅度地提高程序执，这样可大幅度地提高程序执行速度行速度。高速缓存容量远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器。 85.1.1 存储层次结构4磁盘缓存磁盘缓存由于目前磁盘的I/O速度远低于对主存的访问速度，为了缓和两者之间在速度上的不匹配，而

4、设置了磁盘缓存，磁盘缓存，主要用于暂时存放频繁使用的一部分磁盘数据和信息主要用于暂时存放频繁使用的一部分磁盘数据和信息，以以减少访问磁盘的次数减少访问磁盘的次数。但磁盘缓存与高速缓存不同，它本身并不是一种实际存在的存储器，而是利用主存中的部分存储空间暂时存放从磁盘中读出(或写入)的信息。主存也可以看作是辅存的高速缓存，因为，辅存中的数据必须复制到主存方能使用，反之，数据也必须先存在主存中，才能输出到辅存。95.1.2 存储管理目的和任务 l操作系统的存储管理机构必须尽可能方便用户和提高内存的使用效率，使内存在成本、速度和规模之间获得较好的权衡1内存分配内存分配 2地址映射地址映射 3内存共享与

5、保护内存共享与保护 4内存扩充内存扩充 105.1.2 存储管理目的和任务 1内存分配内存分配 l各个作业装入内存时，必须按照规定的方式向操作系统提出申请，由存储管理进行统一分配。l存储管理设置一张表格记录存储空间的分配情况，根据申请的要求按一定的策略分析存储空间的使用情况，找出足够的空闲区域进行分配。l当内存中某个作业撤离或主动归还内存资源时，存储管理要收回它所占用的全部或部分存储空间，使它们成为空闲区域，同时还要修改表格的相关项。l收回存储区域的工作也称释放存储空间。115.1.2 存储管理目的和任务 2地址映射地址映射 l内存中往往同时存放多个作业程序，而这些程序在内存中的位置是不能预先

6、知道的，所以用户在编写程序时不能使用绝对地址。l计算机的指令中地址部分所指示的地址通常是逻辑地址，用户按逻辑地址编写程序。当要把程序装入运行时，操作系统要为其分配一个合适的内存空间，必须把逻辑地址转换成物理地址才能得到信息的真实存放处。把逻辑地址转换成物理地址的工作称为地址转换地址转换。125.1.2 存储管理目的和任务 3内存共享与保护内存共享与保护l所谓内存空间共享，一方面是指采用多道程序设计技术使若干个程序同时进入内存，各自占用一定数量的存储空间，即共享内存资源，共同使用一个内存共享内存资源，共同使用一个内存；l另一方面是指若干个作业有共同的程序段或数据段时，可将这些共同的程序段或数据段

7、存放在某个存储区域内，各作业执行时都可访问它们，即共享内存的某些区域共享内存的某些区域。l内存共享使得内存中不仅有系统程序，而且还有若干道用户程序。为了避免内存中的多道程序相互干扰，必须对内存中的程序和数据进行保护程序和数据进行保护。135.1.2 存储管理目的和任务 3内存共享与保护内存共享与保护l最基本的保护措施是规定各道程序只能访问属于自己的那些存储区域内的信息，对公共区域的访问可以加以限制，一般地说，一个程序执行时可能有以下三种情况：对属于自己的内存区域内的数据既可读又可写；对公共区域中允许共享的信息或可使用的别的用户的信息可读而不可写；对未获得授权的信息，既不可读又不可写。145.1

8、.2 存储管理目的和任务 4内存扩充内存扩充 l为方便用户编写程序，使用户编写程序时不受内存实际容量的限制，可以采用一定的技术扩充内存容量，得到比实际容量更大的内存空间。l这里的扩充不是对物理内存容量的扩充，而是指利用存储管理技术为程序的运行提供一个比实际内存更大的逻辑存逻辑存储空间储空间，即所谓的虚拟存储管理技术虚拟存储管理技术。l当一个大型的程序要装入内存时，可先把其中的一部分装入内存，其余部分存放在磁盘上，如果程序执行中需要用到不在内存中的信息时，则由操作系统采用覆盖技术将其调入内存。155.2 地址重定位一个逻辑地址空间的程序装入到物理地址空间时，由于两个空间不一致，需要进行地址变换，

9、称为地址重定位地址重定位。此时，相对地址空间相对地址空间（也称为逻辑地址空间逻辑地址空间）通过地址重定位机构转换到绝对地址空间（也称为物理地址空间物理地址空间）。165.2 地址重定位地址空间是逻辑地址的集合，存储空间是物理地址的集合。名字空间、地址空间和存储空间的关系如图5.2所示图 5.2 名字空间、地址空间和存储空间程序的装入和链接程序的装入和链接 用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可以执行的程序，通常都要经过以下几个步骤：(1) 编译，由编译程序(Compiler)对用户源程序进行编译，形成若干个目标模块(Object Module)；(2) 链接，由链接

10、程序(Linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module)；(3) 装入，由装入程序(Loader)将装入模块装入内存。图a给出了这样的三步过程程序的装入和链接程序的装入和链接图a对用户程序的处理步骤程序的装入程序的装入1. 1. 绝对装入方式绝对装入方式(Absolute Loading Mode)(Absolute Loading Mode)编译时，若知道程序将驻留在内存的某位置，则编译程序将产生绝对地址的目标代码，绝对装入程序按照装入模块的地址，将程序和数据直接装入指定内存。该地址既可在编译和汇编时给出，也可以由程序员

11、直接赋予。程序程序员直接给出绝对地址，使得程序修改时很可能要修改所有员直接给出绝对地址，使得程序修改时很可能要修改所有地址。因此宁可在程序中采用符号地址，在编译时再去转地址。因此宁可在程序中采用符号地址，在编译时再去转换成绝对地址换成绝对地址。单道程序环境下，可用此种方式。 而在多道程序环境下，目标模块的起始地址通常从0开始，程序中的其他地址，都相对于起始地址计算。这样的模块称为相对装入模块。程序程序JUMP iLOAD jDATAJUMP 400LOAD 1200JUMP 1424LOAD 2224符号地址绝对地址相对地址ij10241424222404001200绝对和可重定位装入模块绝对

12、和可重定位装入模块（a）目标模块（b）绝对装入模块（c）相对装入模块程序的装入程序的装入2. 2. 可重定位装入方式可重定位装入方式(Relocation Loading Mode)(Relocation Loading Mode) 把在装入时对目标程序中的指令和数据地址的修改过程称为重定位重定位。 对于相对装入模块，应采用可重定位装入方式来把装入模块装入内存。 装入相对装入模块时，装入程序要将模块的起始地址与装入程序要将模块的起始地址与内存某位置的地址相加，才能将模块定位到正确的物理地址内存某位置的地址相加，才能将模块定位到正确的物理地址，同样，模块中的指令地址和数据地址都要相应修改。 因地

13、址变换只是在装入时一次完成，以后不再改变，故称为静态重定位静态重定位。LOAD 1,2500365 01000 2500 5000作业地址空间LOAD 1,1250036511000 1250015000内存空间作业装入内存时的情况10000程序的装入程序的装入3. 3. 动态运行时的装入方式动态运行时的装入方式(Dynamic Run-time Loading)(Dynamic Run-time Loading)多道程序环境下，程序在内存的位置可能要经常改变，如进程的换入换出，每次换入到内存的位置一般是不同的，这样，就应采用动态运行时的装入方式。 动态运行时的装入程序，把装入模块装入内存后，

14、把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是并不立即把装入模块中的相对地址转换为绝对地址，而是等到程序真正要执行时才进行地址转换等到程序真正要执行时才进行地址转换(转换时机的把握转换时机的把握)。因此，装入内存后的所有地址仍是相对地址。为使地址转换不影响指令的执行速度，这种方式需要一定的特殊硬件的支持。程序的链接程序的链接 实现链接的方法有三种：静态链接、装入时动态链接和运行时动态链接。1、静态链接：模块模块A CALL B:RETURN模块模块B CALL C:RETURN模块模块C RETURN模块模块A JSR “L”RETURN模块模块B JSR “L+M”

15、RETURN模块模块C RETURN0L-10M-10N-10L-1LL+M-1L+ML+M+N-1需要解决的需要解决的两个问题：两个问题：1、对相对地、对相对地址进行修改址进行修改2、变换外部、变换外部调用符号调用符号目标模块目标模块装入模块装入模块图b 程序链接示意图程序的链接程序的链接2. 2. 装入时动态链接装入时动态链接(Load-time Dynamic Linking)(Load-time Dynamic Linking)这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式在装入内存时，采用边装入边链接的链接方式。即在装入一个目标模块时，若发生一

16、个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要按照图b所示的方式修改目标模块中的相对地址。装入时动态链接方式有以下优点：(1) 便于修改和更新。(2) 便于实现对目标模块的共享。 程序的装入程序的装入3. 3. 运行时动态链接运行时动态链接(Run-time Dynamic Linking)(Run-time Dynamic Linking)这种链接方式，可将某些目标模块的链接，推迟到可将某些目标模块的链接，推迟到执行时才进行执行时才进行。即在执行过程中，若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存，并把它链接到调用者模块上。 275.

17、3 分区存储管理5.3.1 单一连续分区存储管理单一连续分区存储管理 这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。 在单道程序环境下，当时的存储器管理方式是把内存分为系统区和用户区两部分，系统区仅提供给OS使用，它通常是放在内存的低址部分。而在用户区内存中，仅装有一道用户程序，即整个内存的用户空间由该程序独占。这样的存储器分配方式被称为单一连续分配方式。285.3 分区存储管理5.3.2 固定分区管理固定分区管理l固定分区式分配是最简单的一种可运行多道程序的存储管理方式。这是将内存用户空间划分为若干个固定内存用户空间划分为若干个固定大小的区域大小的区域，在每个分区中只装

18、入一道作业在每个分区中只装入一道作业，这样，把用户空间划分为几个分区，便允许有几道作业并发运行。l当某一分区空闲时，便可以从外存的后备作业队列中选择一个适当大小的作业装入该分区，当该作业结束时，又可再从后备作业队列中找出另一作业调入该分区。295.3 分区存储管理5.3.2 固定分区管理固定分区管理 1. 划分分区的方法(1) 分区大小相等(指所有的内存分区大小相等)。(2) 分区大小不等。将内存划分出多个较小的分区，适量的中等分区和少量的大分区。 2. 内存分配为了便于内存分配，通常将分区按其大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)，

19、如图5.5所示。 305.3 分区存储管理图 5.5 固定分区分配315.3 分区存储管理5.3.3 可变分区管理（动态分区管理）可变分区管理（动态分区管理）l固定分区分配是最早的多道程序存储管理方式，由于每个分区的大小固定，必然会造成存储空间的浪费。l可变分区分配是指在系统运行的过程中根据作业对内存的实际需要，动态地为之分配内存空间的一种分区方法。l可变分区分配是在作业装入和处理过程中建立的分区，并使分区的大小与作业的大小相等。l分区的个数和大小不是固定不变的，而是根据装入的作业动态地划分。5.3.3 可变分区管理1. 可变分区分配中的数据结构 常用的数据结构有以下两种形式： 空闲分区表空闲

20、分区表，在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目每个空闲分区占一个表目，表目中包括分区号、分区大小和分区始址等数据项中包括分区号、分区大小和分区始址等数据项。 空闲分区链空闲分区链。为了实现对空闲分区的分配和链接，在每个分区的起始部分设置一些用于控制分区分配的信息控制分区分配的信息，以及用于链接各分区所用的前向指针前向指针，在分区尾部则设置一后向指针后向指针。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链双向链。 5.3.3 可变分区管理2. 分区分配操作1) 分配内存系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的

21、分区大小为u.size，表中每个空闲分区的大小可表示为m.size。 内存分配流程size为内存中允许存在的最小内存空间尺寸5.3.3 可变分区管理2) 回收内存 当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一： (1) 回收区与插入点的前一个空闲分区F1相邻接。(2) 回收分区与插入点的后一空闲分区F2相邻接。(3) 回收区同时与插入点的前、后两个分区邻接。(4) 回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一个新表项单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。365.3.

22、4 分区分配算法可变分区分配常采用的几种分配算法：l1.首次适应算法首次适应算法l2.最优适应算法最优适应算法l3.最差适应算法最差适应算法l4.循环首次适应算法循环首次适应算法l5.快速适应算法快速适应算法371.首次适应算法 该算法要求分区链以地址递增的次序链接。内存分配内存分配时，从链首开始顺序查找，直至找到一个能满足其大小要时，从链首开始顺序查找，直至找到一个能满足其大小要求的空闲区为止求的空闲区为止。然后，再按照作业的大小，从该区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲链中。 该算法倾向于优先利用内存中低址部分的空闲区，倾向于优先利用内存中低址部分的空闲区，高址部分的很少

23、利用，从而保留了高址部分的大空闲区，高址部分的很少利用，从而保留了高址部分的大空闲区，为以后到达的大作业分配大的内存空间创造了条件为以后到达的大作业分配大的内存空间创造了条件。但低低址部分留下许多难以利用的很小的空闲区址部分留下许多难以利用的很小的空闲区 ，每次查找又每次查找又都从低址部分开始，这样，增加了查找开销都从低址部分开始，这样，增加了查找开销。382.循环首次适应算法 由首次适应算法演变而来，分配内存时，不再每次从不再每次从链首开始查找，而是从上次找到的空闲分区的下一个空闲链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足要求的空闲分区分区开始查找，

24、直到找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间。 为实现该算法，应设置一起始查询指针，并采用循环查找方式。该算法能使内存中的空闲分区分布得更均匀，减少查找空闲分区的开销，但这会缺乏大的空闲分区。393.最佳适应算法 “最佳”的含义是指每次为作业分配内存时，总是把既能满足要求又是最小的空闲分区分配给作业，避免“大材小用”。为加速查询，该算法要求将所有的空闲区按其该算法要求将所有的空闲区按其大小以递增的顺序链接成一空闲区链大小以递增的顺序链接成一空闲区链。这样，第一次找到的满足要求的空闲区，必然是最优的。 孤立地看，这似乎是最佳的，但从宏观上看却不一定。因为每次分配后所切

25、割下的剩余部分，总是最小的，在存储器中会留下许多难以利用的小空闲区。404.最差适应算法 由于最坏适应分配算法选择空闲分区的策略正好与最佳适应算法相反：它在扫描整个空闲分区表或链表时，总总是挑选一个最大的空闲区，从中分割一部分存储空间给作是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用业使用，以至于存储器中缺乏大的空闲分区，故把它称为是最坏适应算法。 该算法要求将所有空闲分区，按容量从大到小的顺该算法要求将所有空闲分区，按容量从大到小的顺序，形成一空闲分区链，查找时，只要看第一个分区能否序，形成一空闲分区链，查找时，只要看第一个分区能否满足作业要求即可。满足作业要求即可。l动态分区示例

26、：请使用下动态分区示例：请使用下面的算法再分配一个面的算法再分配一个16M的内存空间？的内存空间？1.首次适应（First fit）2.循环首次适应（Next fit）3.最佳适应（Best fit）4.最差适应（Worst fit）最佳适应最佳适应首次适应首次适应循环首次适应循环首次适应最差适应最差适应435.快速适应算法（基于索引） 该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表的表

27、头指针。 该算法在搜索空闲分区时分二步：第一步是根据进程长度从索引表中找到能容纳它的最小空闲区链表；第二步是从链表中取下第一块进行分配。445.快速适应算法 优点优点：查找效率高。另外在进行空闲分区分配时，不会对任何分区产生分割，能保留大的空闲分区，同时也不会产生内存碎片。 缺点缺点：在分区归还时算法比较复杂，系统开销较大。该算法在分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。空闲分区划分越细，浪费越严重，整体上会造成可观的存储空间浪费，这是典型的以空间换时间的作法。哈希算法哈希算法 哈希算法是利用哈希快速查找的优点，以及空闲分

28、区在可利用空闲分区表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关建立哈希函数，构造一张以空闲分区大小为关键字的哈希表键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。 进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。4546伙伴系统 该算法规定，无论已分配分区或空闲分区，其大小均为2的k次幂(k为整数，lkm)，其中2l表示分配的最小块的尺寸，2m表示分配的最大的块的尺寸。通常， 2m是可供分配的整个内存的大小。 （1）开始时，可用于分配的整个空间被看成是一个大小为2m的块； （2）如

29、果请求的大小s满足2m-1 s = 2m ，则分配整个空间；否则，该块被分成两个大小相等的伙伴，均为2m-1 ，如果有2m-2 s 2100段号S段长基址1K6K6004K5008K2009200段号0321+82928K82928692逻辑地址物理地址主存位移量段表寄存器越界795.5.1 段式存储管理 2.分页和分段的主要区别分页和分段的主要区别 分页和分段系统有许多相似之处，但在概念上二者完全不同： (1) 页是信息的物理单位，仅仅是出于系统管理的需要；段是信息的逻辑单位，其目的是满足用户的需要。(2) 页的大小固定且由系统确定，一个系统只能有一种大小的页面；段的长度不固定，决定于用户所

30、编写的程序； (3) 分页的作业地址空间是一维的；分段的作业地址空间是二维的。 (4) 通常分段的段内空间会比分页的页面空间大，因此段表会比页表短。805.5.2 段页式存储管理1) 基本原理 段页式系统的基本原理是分段和分页原理的结合，即即先将用户程序分成若干个段，再把每个段分成若干个页，先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名并为每一个段赋予一个段名。在段页式系统中，其地址结地址结构由段号构由段号、段内页号段内页号及页内地址页内地址三部分所组成，如下图所示。 为实现从逻辑地址到物理地址的变换，系统需同时配置段表和页表，段表的内容是页表始址和页表长度，这与分

31、段式系统不同。段号（S） 段内页号（P） 页内地址（W）图 5.14 利用段表和页表实现地址映射5.5.2 段页式存储管理825.5.2 段页式存储管理2) 地址变换过程 在段页式系统中，为了便于实现地址变换，需要配置一个段表寄存器，其中存放段表始址和段表长度。进行地址变换时按如下步骤进行：(1) 通过段表寄存器将段号与段表长度进行比较将段号与段表长度进行比较，如果未越界则查找段表在内存中的位置，否则越界中断；(2) 访问段表访问段表，将页表长度与页号进行比较，如果未越界则根据段号查找页表所在的位置；(3) 访问页表访问页表，根据页号查找该页所在的物理块号；(4) 将物理块号和地址结构中的页内

32、地址相加，形成内存单形成内存单元的物理地址元的物理地址。图 5.15 段页式地址变换过程5.5.2 段页式存储管理845.6 内存扩充技术 前面所介绍的各种存储管理方式都有一个共同的特点，那就是都要求将一个作业的全部装入内存后方能运行，于是，出现了这样两种情况：一是有的作业很大，其所要求的内存空间超过了内存空间的总容量，作业不能装入内存，导致其无法运行；二是有大量的作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存运行，其它大量作业留在外存等待。 出现这两种情况的原因，都是由于内存容量不够大。 一个明显的解决办法就是增加物理内存增加物理内存；另一种方法就是从逻辑上来扩充

33、内存容量逻辑上来扩充内存容量。855.6.1 覆盖技术 覆盖技术覆盖技术是指一个程序的若干程序段或几个程序的某些部分共享某一个存储空间。覆盖技术的实现是把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构使那些不会同时执行的程序段共享同一块内存区域。未执行的程序段先保存在未执行的程序段先保存在磁盘上，当有关程序段的前一部分执行结束后，再磁盘上，当有关程序段的前一部分执行结束后，再把后续程序段调入内存，覆盖前面的程序段把后续程序段调入内存，覆盖前面的程序段。865.6.1 覆盖技术 覆盖技术是早期采用的简单的扩充内存技术，对用户不透明，它要求用户清楚地了解程序的结构，并指定各程序段调入

34、内存的先后次序，以及内存中可以覆盖掉的程序段的位置等，增加了用户的负担。而且程序段的最大长度仍受内存容量的限制。覆盖技术可以由编译程序提供支持，此时被覆盖的块是由程序员或编译程序预先确定的。875.6.2 交换技术交换的引入交换的引入 一方面一方面，在内存中的某些进程由于某事件尚未发生而被阻塞运行，但它却占用了大量的内存空间，甚至有时可能出现在内存中所有进程都被阻塞，而无可运行之进程，迫使CPU停止下来等待的情况；另一方面另一方面，却又有着许多作业，因内存空间不足，一直驻留在外存上，而不能进入内存运行。 所谓交换交换(对换对换)，是指把内存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外

35、存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需的程序和数据，换入内存。885.6.2 交换技术 交换技术的目的是尽可能快的实现进程在内、外存之间的交换，从而提高内存利用率。早期的交换技术多用于分时系统当中，大多数现代操作系统也都使用交换技术，交换技术有力地支持了多道程序设计，同时交换技术也是虚拟存储技术的基础。交换基础实施时需要考虑如下问题：换出进程的选择交换时机的确定交换空间的分配换入进程换回内存时位置的确定895.7 虚拟存储管理5.7.1 基本原理1. 常规存储器管理方式的特征常规存储器管理方式的特征 (1) 一次性。作业在运行前需要一次性的将其全部装入内存。但许多作业在

36、每次运行时，并非其全部程序和数据都使用到了，如果一次性的将其全部装入，实际上也是对内存空间的一种浪费。 (2) 驻留性。作业装入内存后，便一直驻留在内存中，直至作业运行结束。尽管运行中的进程会因各种事件而长期等待，或有些模块在运行过一次以后就不再需要了，但它们仍将继续占用宝贵的内存资源。905.7.1 基本原理2. 局部性原理局部性原理 程序运行时存在的局部性现象，很早就已被人发现，但直到1968年，P.Denning才真正指出：程序在执行时将呈程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存

37、储空间也局限于某限于某个部分，相应地，它所访问的存储空间也局限于某个区域个区域。 局限性又表现在下述两个方面：(1) 时间局限性。程序中的某条指令被执行，不久后会再次执行；某个数据被访问，不久后将再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环循环操作。(2) 空间局限性。 程序访问了某个存储单元，不久后，其附近的存储单元也将被访问。915.7.1 基本原理3. 虚拟存储虚拟存储 基于局部性原理可知，应用程序在运行之前没有必要将应用程序在运行之前没有必要将之全部装入内存之全部装入内存，而仅须将那些当前要运行的少数页面或段当前要运行的少数页面或段先装入内存便可运行先装入内存便可运行

38、，其余部分暂留在盘上。 局部性原理是实现虚拟存储管理的理论基础。 所谓虚拟存储器虚拟存储器是指仅把作业的一部分装入内存便可运行的存储器系统，是具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。虚拟存储器的逻辑容量由系统的寻址能力和外存容量之和所决定，与实际的内存容量无关。925.7.1 基本原理虚拟存储虚拟存储特征特征(1) 多次性多次性：是指一个作业被分成多次来调入内存，即作业运行时不需将其全部装入内存，只需将当前要运行的那部分程序和数据装入，以后运行到某些部分时再将其调入。 (2) 对换性对换性：是指允许作业中的程序和数据，在作业运行过程中换进、换出。 (3) 虚拟

39、性虚拟性：是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。 虚拟性以多次性和对换性为基础，多次性和对换性以离散分虚拟性以多次性和对换性为基础，多次性和对换性以离散分配为基础配为基础。935.7.2 请求分页存储管理 请求分页存储管理系统是在分页存储管理系统的基础上，增加了请求调页功能和页面置换功能后形成的页式虚拟存储页式虚拟存储管理系统管理系统。1. 请求分页原理请求分页原理 请求分页存储是建立在分页存储管理基础之上，从静态分页存储管理发展而来的。在作业或进程开始执行前，不把作业或进程的程序段和数据段一次性的全部装入内存，而只是装入被认为是经常使用的那一部分。其他部分则

40、在程序执行过程中动态的装入。 请求分页的地址变换过程与静态分页管理方式相同，都是通过页表查询出相应的块号之后，再由块号与页内地址相加得到实际的物理地址。945.7.2 请求分页存储管理请求页表机制请求页表机制 在请求分页系统中需要的主要数据结构是请求页表，其基本作用仍然是将用户地址空间中的逻辑地址映射为内存空将用户地址空间中的逻辑地址映射为内存空间中的物理地址间中的物理地址。为了满足页面换进换出的需要，在请求页表中又增加了四个字段。这样，在请求分页系统中的每个页表应含以下诸项：页号页号 物理块号物理块号 状态位状态位P P 访问字段访问字段A A 修改位修改位M M 外存地址外存地址又称存在位

41、，用于指示该页是否已调入内存，供程序访问时参考。用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。指示该页在调入内存后是否被修改过。若未被修改，在置换该页时就不需将该页回写到外存，否则，就要回写到外存。用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。955.7.2 请求分页存储管理2. 缺页中断机构缺页中断机构 每当所要访问的页面不在内存时，便要产生一次缺页中缺页中断断，请求OS将所缺之页调入内存。缺页中断虽要经历与一般中断相同的几个步骤，但它是一种特殊的中断，与一般中断的区别主要是： (1) 在指令执行期间产生和处理中断信号在指

42、令执行期间产生和处理中断信号。通常CPU都是在一条指令执行完后去检查是否有中断请求到达。有则响应，无则继续执行下一条指令。而缺页中断是在指令执行期间，发现所要访问的指令和数据不在内存时产生和处理的。 (2) 一条指令在执行期间，可能产生多次缺页中断一条指令在执行期间，可能产生多次缺页中断。这时硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处，继续执行。96B:A:Copy ATo B例如：执行 COPY A TO B指令时，可能要产生6次缺页中断654321页面975.7.2 请求分页存储管理地址变换过程地址变换过程请求分页系统中的地址变换机构是在分页系统地址变换

43、机构的基础上，为实现虚拟存储器，再增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。图5.16示出了请求分页系统中的地址变换过程。98图 5.16 请求分页中的地址变换过程995.7.3 页面置换算法 缺页率假设一个进程的逻辑空间为n页，系统为其分配的内存物理块数为m(mn)。如果在进程的运行过程中，访问页面成功(即所访问页面在内存中)的次数为S，访问页面失败(即所访问页面不在内存中，需要从外存调入)的次数为F，则该进程总的页面访问次数为A=S+F，那么该进程在其运行过程中的缺页率即为 缺页率的影响因素: 1) 页面大小；2) 进程分配物理块的数目；3) 页面置换算

44、法；4) 程序固有特性。AFf 1005.7.3 页面置换算法 在请求分页存储管理中，进程或作业执行中产生缺页中断，需要从外存中调入对应的程序或数据到内存当中，此时，如果内存已经满了，那么应该调出哪一页以腾出内存空间就需要遵循一定的算法。通常把这类算法称为页面置换算法页面置换算法。 一个好的算法，应具有较低的页面更换频率。理论上讲，应将那些以后不再被访问的页面换出，或把那些在较长时间内不会再访问的页面调出。1011. 最佳置换算法最佳置换算法(Optimal replacement, OPT)最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的

45、，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。但由于人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1770701201203243203201701页面的编号系统为某进程分配的三个物理块（页框）进程运行时先后将7，0，1三个页面装入内存，此时内存已满，若进程要访问新的页面，则需淘汰三者之一进程访问页面2，此时产生缺页中断，将页面2调入内存，但调入之前须将内存中的某页换出。OS

46、根据最佳置换算法，将页面7淘汰，因页面0将在第5次被访问，页面1在第14次被访问，而页面7要在第18次时被访问才需调入。进程访问访问页面3，引起页面1被淘汰，因在内存中的1，2，0三个页面中，页面1将是以后最晚才被访问的，要在第14次才被访问。 采用最佳置换算法，只发生6次页面置换进程在运行过程中共发生9次缺页中断缺页中断和页面置换次数分别是多少？编号页面的引用顺序（页面走向）： 1 2 3 4 5 6 7 8 9 10 11121314 15161718 19201022. 先进先出置换算法先进先出置换算法(First in first out, FIFO) FIFO算法是最早出现的置换算法

47、。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1770701201231430023013702编号页面的引用顺序（页面走向）： 1 2 3 4 5 6 7 8 9 10 11121314 15161718

48、1920进程运行时已先后将7,0,1三个页面装入内存，此时内存已满。进程访问页面2，此时将产生缺页中断，将页面2调入内存，但调入之前会将7,0,1三个页面中的一个进行置换。OS根据FIFO置换算法，将页面7淘汰，因7,0,1三个页面中，页面7最先进入内存，其在内存中的驻留时间最长。230420423012712701进程访问访问页面3，引起页面0被淘汰，因在内存中的2，0，1三个页面中，页面0是最先进入内存，即在内存中驻留时间最长。总共发生15次缺页中断，12次页面置换。1033. 最近最久未使用算法最近最久未使用算法(Least recently used, LRU) FIFO依据的条件是页

49、面进入内存的时间。LRU依据的条件是页面调入内存后的使用情况。LRU置换算法选择最近最久未使用的页面予以淘汰。 其作法是赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，需淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面予以淘汰。 仍以前面的页面引用串作例。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1770701201这时淘汰页面7，换入页面2。因页面7是最先进入内存且被使用，在这之后至今未使用，是最近最久未使用的页面进程访问页面2，但它不在内存，系统需将它调入。203403402432032132102107进程访问

50、页面3，但它不在内存，系统需将它调入。进程访问页面0，但其不在内存。淘汰页面4，换入页面0。这时页面1是最近最久未使用的页面，淘汰页面1，换入页面3。共发生12次缺页中断，9次页面置换1044. 第二次机会置换算法第二次机会置换算法(Second chance, SC) FIFO算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：检查最老页面的R位。如果R位是0，那么这个页面既老又没有被使用过，可以立刻置换掉；如果是1，就将R位清0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续搜索。图 5.17第二次机会置换算法1055. 时钟页面置换算

51、法时钟页面置换算法(Clock) 把所有的页面都保存在一个类似钟面的环形链表中，用一个表针指向最老的页面。 当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到了一个R位为0的页面为止。1066. 最近未使用页面置换算法最近未使用页面置换算法(Not recently used, NRU) 在大部分具有虚拟内存的计算机中，系统为每一页面设置了两个状态位。当页面被访问时设置R位；当页面被写入时设置M位。 可以用R位和M位来构造一个简单的页面置换算法：当启动一个

52、进程时，它的所有页面的两个位都由操作系统设置成0，R位被定期地清零，以区别最近没有被访问的页面和被访问的页面。1076. 最近未使用页面置换算法最近未使用页面置换算法(Not recently used, NRU) 当发生缺页中断时，操作系统检查所有的页面并根据它们当前的R位和M位的值，把它们分为4类：第0类：RM=00，没有被访问，没有被修改。第1类：RM=01，没有被访问，已被修改。第2类：RM=10，已被访问，没有被修改。第3类：RM=11，已被访问，已被修改。 NRU算法随机地从类编号最小的非空类中挑选一个页面淘汰之。这个算法隐含的意思是，在最近一个时钟周期淘汰一个没有被访问的已修改页

53、面要比淘汰一个被频繁使用的“干净”页面好。NRU主要优点是易于理解和能够有效地被实现，虽然它的性能不是最好的，但是已经够用了。1085.7.4 请求分页系统性能分析1. 缺页率对访问时间的影响缺页率对访问时间的影响 假设使用了“快表”以提高访问内存的速度，则CPU访问内存所花费的时间由以下3个部分组成：(1) 页面在“快表”时的存取时间，只需1个读写周期时间；(2) 页面不在“快表”而在页表时的存取时间，需要2个读写周期时间；(3) 页面既不在“快表”也不在页表时，发生缺页中断处理的时间。 缺页中断处理的时间又有3个部分组成：(1) 缺页中断服务时间；(2) 页面传送时间，包括：寻道时间、旋转

54、时间和数据传送时间。(3) 进程重新执行时间。1092. 抖动现象抖动现象 置换算法的好坏将直接影响系统的性能，不适当的算法可能导致进程发生“抖动” (Thrash-ing)。即刚被换出的页很快又被访问，需重新调入。为此，又需再选一页调出；而此刚被换出的页，很快又被访问，因而又需将它调入。如此频繁地更换页面，以至一个进程在运行中，将把大部分时间花在完成页面置换的工作上，我们称该进程发生了“抖动抖动”。 抖动现象分为局部抖动和全局抖动两种类型。5.7.4 请求分页系统性能分析1102. 抖动现象抖动现象 抖动现象如下两种类型： 1) 局部抖动：进程采用局部置换策略，产生缺页时，只能置换自身拥有的某个页面，而不能置换其它进程的页面 2) 全局抖动：由进程之间的相互作用引起的，若进程采用的是全局置换策略，当一个进程发生缺页中断时，需要从其它进程那里获取物理块，从而导致这些进程在运行中需要物理块，产生了缺页中断时，又需要从其它进程那里获取物理块。5.7.4 请求分页系统性能分析1113. 页面大小的选择页面大小的选择l页面大小的选择涉及到内部碎片、页表大小、页面失效率的高低等诸多问题l页面越小，内部碎片就越少，内存利用率就越高，但同时就会产生较大的页表，占用较大的内存空间；l页面过大，会导致页面在内外