《计算机操作系统教程（第三版）》课件第4章 存储管理

第4章

存储管理

本章学习目标

4.1存储管理的功能

4.2实存管理

4.3虚拟存储器管理

4.4碎片与抖动问题

开始本章学习目标

本章首先介绍了存储管理的研究对象和目的，明确了存储管理的基本功能和有关的基本概念；然后从实存和虚存两个角度，分别介绍了常用的几种存储管理方案；最后对各种存储管理方案存在的问题，主要是碎片和抖动问题进行了总结。

返回本章首页本章的主要内容如下：(1)存储管理的目的和四大基本功能。

(2)实存管理中讲述了固定分区存储管理、可变式分区存储管理、纯分页存储管理三种存储管理方案的实现原理(3)虚存管理以请求式分页存储管理为重点

(4)总结各种存储管理方案中存在的碎片和抖动问题及解决方法下一页图4.1多级存储器体系示意图4.1存储管理的功能4.1.1内存的分配与回收

4.1.2地址重定位4.1.3存储保护

4.1.4虚拟存储器

返回本章首页4.1.1内存的分配与回收内存分配按分配时机的不同，可分为两种方式。（1）静态存储分配：指内存分配是在作业运行之前各目标模块连接后，把整个作业一次性全部装入内存，并在作业的整个运行过程中，不允许作业再申请其他内存，或在内存中移动位置。也就是说，内存分配是在作业运行前一次性完成的。（2）动态存储分配：作业要求的基本内存空间是在目标模块装入内存时分配的，但在作业运行过程中，允许作业申请附加的内存空间，或是在内存中移动，即分配工作可以在作业运行前及运行过程中逐步完成。返回本节4.1.2地址重定位1．内存空间（或物理空间）2．逻辑空间3．地址重定位返回本节1．内存空间（或物理空间）内存是由若干个存储单元组成的，每个存储单元有一个编号，这种编号可唯一标识一个存储单元，称为内存地址（或物理地址）。下一页2．逻辑空间源程序经过汇编或编译后，形成目标程序，每个目标程序都是以0为基址顺序进行编址的，原来用符号名访问的单元用具体的数据——单元号取代。这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。下一页图4.2作业的名空间、逻辑地址空间和装入后的物理空间下一页3．地址重定位(1)静态地址重定位静态地址重定位是在程序执行之前由操作系统的重定位装入程序完成的。(2)动态地址重定位

动态地址重定位是在程序执行期间进行的。

下一页（b）采用动态重定位时内存空间及地址重定位示意图

（a）采用静态重定位后的内存空间图4.3静态地址重定位和动态地址重定位示意图返回本节4.1.3存储保护（1）上、下界存储保护：上、下界保护是一种简单的存储保护技术。系统可为每个作业设置一对上、下界寄存器，分别用来存放当前运行作业在内存空间的上、下边界地址，用它们来限制用户程序的活动范围。

（2）基址—限长存储保护：上、下界保护的一个变种是采用基址—限长存储保护。

返回本节图4.4界限寄存器的两种存储保护方式返回本节4.1.4虚拟存储器对内存进行逻辑上的扩充，现在普遍采用虚拟存储管理技术。

虚拟存储技术的基本思想是把有限的内存空间与大容量的外存统一管理起来，构成一个远大于实际内存的、虚拟的存储器。此时，外存是作为内存的直接延伸，用户并不会感觉到内、外存的区别，即把两级存储器当作一级存储器来看待。一个作业运行时，其全部信息装入虚存，实际上可能只有当前运行的必需一部分信息存入内存，其他则存于外存，当所访问的信息不在内存时，系统自动将其从外存调入内存。

返回本节4.2实存管理4.2.1固定分区存储管理

4.2.2可变式分区存储管理4.2.3纯分页存储管理4.2.4纯分段存储管理返回本章首页4.2.1固定分区存储管理固定分区存储管理是实现多道程序设计的最简单的一种存储管理技术。其基本思想是，在作业未进入内存之前，就由操作员或操作系统把内存可用空间划分成若干个固定大小的存储区，除操作系统占用一个区域外，其余区域为系统中多个用户共享，因为在系统运行期间，分区大小、数目都不变，所以固定式分区也称为静态分区。返回本节图4.5固定式分区内存分配示意图（a）和（b）固定式分区说明表返回本节4.2.2可变式分区存储管理1．空闲分区的组织形式

2．内存的分配与回收

3．常用的分配算法

4．可变式分区的地址重定位

返回本节图4.6可变式分区内存使用情况示意图下一页1．空闲分区的组织形式空闲分区链表的组织是这样的：在每个空闲分区的起始部分开辟出一个单元，存放一个链表指针和该分区的大小，链表指针指向下一个空闲分区。系统中用一个固定单元作为空闲分区链表的链表头指针，指向第一块空闲分区首地址，最后一块空闲分区的链表指针存放链尾标志。如图4.7（a）所示。下一页2．内存的分配与回收当某一个用户作业完成释放所占分区时，系统应进行回收。在可变式分区中，应该检查回收区与内存中前后空闲区是否相邻，若相邻，则应进行合并，形成一个较大的空闲区，并对相应的链表指针进行修改；若不相邻，应将空闲区插入到空闲区链表的适当位置。

下一页图4.7首次适应算法的空闲分区链表组织形式下一页3．常用的分配算法（1）首次适应算法

（2）最佳适应算法

（3）最差适应算法

下一页图4.8最佳适应算法的空闲分区链表组织形式下一页图4.9最差适应算法的空闲分区链表组织形式下一页图4.10内存使用情况下一页图4.11用三种适应算法处理同一作业序列下一页4．可变式分区的地址重定位可变式分区的地址重定位可采用静态重定位，也可采用动态重定位。如采用静态重定位，因用户作业进入内存后，程序的逻辑地址实现了重定位，不能在内存中再进行移动，经过一段时间的运行，内存中不能再分配利用的小碎片会越来越多。有时可能会出现这种情况，即当一个作业申请一定数量的内存时，虽然此时空闲区的总和大于新作业的内存要求，但却没有单个的空闲区足以装下该作业。采用动态重定位的可变式分区管理技术，在执行内存分配时，如无足够大空闲块，应考虑实现紧凑操作。其分配算法如图4.12所示

。

下一页图4.12采用动态重定位的可变式分区分配算法返回本节4.2.3纯分页存储管理1．纯分页存储管理中存储块的分配与回收

2．纯分页存储管理的地址重定位问题3．联想存储器

4．存储保护

返回本节1．纯分页存储管理中存储块的分配与回收通常有两种记录空闲存储块的方法：位图法和链表法。（a）存储块使用情况（b）存储块使用情况的位图表示图4-13存储块的位图管理法2．纯分页存储管理的地址重定位问题纯分页存储管理中的地址重定位是非常重要的，要使不连续的、分散的用户程序能正常运行，须采用动态地址重定位。此时，可采用重定位寄存器方式，如分页太多，则重定位寄存器用得太多。通常可在内存中为每个作业开辟一块特定区域，建立起作业的逻辑页与存储块之间的对应表格关系，这种表常称为页面映象表，简称页表。

下一页图4.14纯分页存储管理示意图下一页3．联想存储器从上面介绍的地址变换过程可以看出：如果把页表全部放在内存，那么存取一个数据时，至少要访问二次内存。一次是访问页表，形成实际内存地址；另一次是根据形成的内存地址存取数据。显然，这比通常执行指令的速度要慢得多，使计算机的运行速度几乎降低一半。应用联想存储器和页表相结合的方式，可有效地提高系统动态地址转换的速度，是一种行之有效的方法。下一页图4.15纯分页存储管理地址重定位实现过程下一页图4.16采用快表和页表相结合的分页地址变换过程示意图下一页4．存储保护四种保护方式：①禁止做任何操作，②只能执行，③只能读，④能读/写，当要访问某页时，先判断该页的存取控制和存储保护信息是否允许。添加了存取控制信息的页表表目如下图所示：

返回本节4.2.4纯分段存储管理1．分段管理的基本思想2．地址变换3．分段与分页的区别返回本节1．分段管理的基本思想

在分段存储管理中，作业的地址空间由若干个逻辑分段组成，每一分段是一组逻辑意义完整的信息集合，并有自己的名字（段名）。每一段都是以0开始的连续的一维地址空间，整个作业则构成了二维地址空间。因此所谓分段管理，就是管理由若干段组成的作业，并且按分段来进行存储分配，由于分段管理的作业地址空间是二维的，所以分段存储管理的关键在于如何把分段地址结构变成一维的地址结构。2．地址变换为了实现段的逻辑地址到物理地址的转换，系统为每个作业设置了一张段表SMT，每个表目至少有4个数据项：段号、段长、内存始址和存取控制。分段存储管理系统的地址变换过程如图4.17所示。图4.17分段存储管理的地址变换示意图【例】在一个分段存储管理系统中，其段表如表4.1所示。求表4.2中所示逻辑地址对应的物理地址。解：（1）由表4.1知，段号为0的段的内存起始地址为210，段长为500。由表4.2知，逻辑地址的段内位移为430。因为430<500，所以该逻辑地址是合法的。其对应的物理地址为：210+430=640（2）由表4.1知，段号为1的段的内存起始地址为2350，段长为20。由表4.2知，逻辑地址的段内位移为10。因为10<20，所以该逻辑地址是合法的。其对应的物理地址为：2350+10=2360（3）由表4.1知，段号为2的段的内存起始地址为100，段长为90。由表4.2知，逻辑地址的段内位移为500。因为500>90即逻辑地址的段内位移500已超过了段长90，所以该逻辑地址是非法的。3．分段与分页的区别（1）页是信息的物理单位。分页的目的是实现离散分配，减少内存的外零头，提高内存利用率。段是信息的逻辑单位。每一段在逻辑上是一组相对完整的信息。（2）分页存储管理的作业地址空间是一维的，而分段存储管理的作业地址空间是二维的。（3）页的大小固定且由系统确定，是等长的。而段的长度不定，它是由具有相对完整意义的信息长度确定。（4）分页的优点体现在内存空间的管理上，而分段的优点体现在地址空间的管理上。4.3虚拟存储器管理4.3.1虚拟存储器的概念4.3.2请求式分页存储管理4.3.3页面置换算法4.3.4请求式分页存储管理性能分析举例4.3.5请求式分段存储管理与动态地址重定位4.3.6段页式存储管理与动态地址重定位返回本章首页4.3.1虚拟存储器的概念（1）程序中往往会有一些彼此互斥的部分。（2）在一个完整的程序中，会有一些诸如出错处理这样的子程序，在作业正常运行情况下不会执行这些程序，没有必要把它们调入内存。基于程序局部性原理和上述情况，就没有必要把一个作业一次性全部装入内存再开始运行。而是可以把程序当前执行所涉及的信息放入内存中，其余部分可根据需要临时调入，由操作系统和硬件相配合来完成主存和辅存之间信息的动态调度。这样的计算机系统好像为用户提供了一个存储容量比实际主存大得多的存储器，就称为虚拟存储器。

返回本节4.3.2请求式分页存储管理1、动态地址重定位2、缺页中断处理机构3、页面分配策略返回本节1、动态地址重定位请求式分页存储管理与纯分页存储管理在内存块的分配与回收，存储保护某方面都十分相似，不同之处在于地址重定位问题。在请求式分页存储管理的地址重定位时，可能会出现所需页面不在主存的情况，此时，系统必须解决以下两个问题：（1）当程序要访问的某页不在内存时，如何发现这种缺页情况？发现后应如何处理？（2）当需要把外存上的某个页面调入内存时，此时内存中没有空闲块应怎么办？如图4.17所示是请求式分页存储管理的存储映像下一页为了帮助操作系统对要置换出内存的页面进行选择，在页表中还可以增加一个引用位，以反映该页最近的使用情况。一般来说，一个页表的表目通常可包括如下的数据内容：下一页请求式分页存储管理中的地址重定位和缺页中断处理过程如图4.18所示。返回本节2、缺页中断处理机构在请求分页系统中，每当进程所要访问的页面不在内存时，就会产生缺页中断，请求操作系统将所缺的页面调入内存。在任何情况下，缺页中断的处理时间主要包括三个部分：缺页中断处理、页面的调入和进程的重新启动。处理缺页中断应注意以下几点：1）缺页中断的发生和处理是在指令执行期间进行的。2）一条指令在执行期间可能产生多次缺页中断。3）发生缺页中断时应保存指令执行的中间结果。4）对新分配的物理块应上锁，防止同一物理块分配给多个进程。缺页中断处理是一个复杂的过程，几乎涉及到操作系统的各个部分：首先缺页中断要经中断机构处理，把控制权交给操作系统；调入页面，有的系统还要经过文件系统；信息传送要启动I/O，涉及设备管理；在等待页面传送时，CPU要分配给其他进程，涉及CPU调度；分配和页面置换应由存储管理系统来完成。3、页面分配策略在分页式虚拟存储管理中，不可能也不必要把一个进程的所有页面调入主存，那么，操作系统决定为某进程分配多大的主存空间，需要考虑以下因素：1）分配给一个进程的空间越小，同一时间处于主存的进程就越多，于是至少有一个进程处于就绪态的可能性就越大，从而，可减少进程对换的时间。2）如果进程只有一小部分在主存里，即使它的局部性很好，缺页中断率还会相当高。3）因为程序的局部性原理，分配给一个进程的主存超过一定限度后，再增加主存空间，也不会明显降低进程的缺页中断率。

在请页式系统中，可采用两种策略分配页框给进程：固定分配和可变分配。如果进程生命周期中，保持页框数固定不变，称页面分配为固定分配。在进程创建时，根据进程类型和程序员的要求决定页框数，只要有一个缺页中断产生，进程就会有一页被替换。如果进程生命周期中，分得的页框数可变，称页面分配为可变分配。

在进行页面替换时，也可采用两种策略：局部替换和全局替换。如果页面替换算法的作用范围是整个系统，称为全局页面替换算法，它可以在可运行进程之间动态地分配页框。如果页面替换算法的作用范围局限于本进程，称为局部页面替换算法，它实际上需要为每个进程分配固定的页框。固定分配往往和局部替换策略配合使用，每个进程运行期间分得的页框数不再改变，如果发生缺页中断，只能从进程在主存的页面中选出一页替换，以保证进程的页框总数不变。可变分配往往和全局替换策略配合使用，这是采用得较多的一种分配和替换算法。4.3.3页面置换算法1．最优算法（OPT算法）2．先进先出算法（FIFO算法）3．最久未使用页面置换算法（LRU算法）4．时钟（clock）置换算法返回本节1．最优算法（OPT算法）最理想的页面置换算法是：从内存中移出以后不再使用的页面；如无这样的页面，则选择以后最长时间内不需要访问的页。这就是最优算法的思想。这种算法本身不是一种实际的方法，因为页面访问的顺序是很难预知的。但是，可把它作为一种评价标准，比较其他实用方法的优劣，所以，最优算法只具有理论上的意义。下一页设分配给进程使用的物理块数为3，其页面访问序列、缺页中断率的计算如表4.3所示。2．先进先出算法（FIFO算法）这种算法的基本思想是：总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。

下一页图4.20先进先出算法存储分块表构造下一页3．最久未使用页面置换算法（LRU算法）这种算法的基本思想是，如果某一页被访问了，那么它很可能马上又被访问；反之，如果某一页很长时间没有被访问，那么最近也不太可能会被访问。这种算法考虑了程序设计的局部性原理。其实质是，当需要置换一页时，选择在最近一段时间最久未使用的页面予以淘汰。实现这种算法可通过周期性地对“引用位”进行检查，并利用它来记录一页面自上次被访问以来所经历的时间t，淘汰时选择t最大的页面。

下一页4．时钟（clock）置换算法LRU算法能够比较普遍地适用于各种类型的程序，但是实现起来比较困难。因为要对以前的访问历史时时加以记录和更新，如果这种连续的修改完全由软件来做，则系统开销较大。如果由硬件完成会增加计算机成本。因此，在实际应用中得到推广的是一种简单而有效的时钟置换算法。下一页算法的基本思想是：1）一个页面首次装入主存时，其“引用位”置12）在主存中的任何一个页面被访问时，其“引用位”置1。3）淘汰页面时，存储管理从指针当前指向的页面开始扫描循环队列，把所遇到的“引用位”是1的页面的“引用位”清成0，并跳过这个页面；把所遇到的“引用位”是0的页面淘汰掉，指针推进一步。4）扫描循环队列时，如果遇到的所有页面的“引用位”为1，指针就会绕整个循环队列一圈，把碰到的所有页面的“引用位”清0；指针停在起始位置，并淘汰掉这一页，然后，指针推进一步。图4.21时钟置换算法流程

如果把页表中的“引用位”和“修改位”结合起来使用可以改进时钟页面替换算法，它们一共组合成四种情况：1）最近没有被引用，没有被修改（r=0，m=0）2）最近被引用，没有被修改（r=1，m=0）3）最近没有被引用，但被修改（r=0，m=1）4）最近被引用过，也被修改过（r=1，m=1）内存中的所有页面必定属于这四类中的一类，在进行页面置换时，必须同时检查引用位和修改位，尽可能地选择置换代价小的页面淘汰。改进的时钟算法可如下执行：步1：选择最佳淘汰页面，从指针当前位置开始，扫描循环队列。扫描过程中不改变“引用位”，把遇到的第一个r=0，m=0的页面作为淘汰页面。步2：如果步1失败，再次从原位置开始，查找r=0且m=1的页面，把遇到的第一个这样的页面作为淘汰页面，而在扫描过程中把指针所扫过的页面的“引用位”r置0。步3：如果步2失败，指针再次回到了起始位置，由于此时所有页面的“引用位”r均己为0，再转向步1操作，必要时再做步2操作，这次一定可以挑出一个可淘汰的页面。4.3.4请求式分页存储管理性能分析举例1．程序设计的质量2．页面的大小3．分配的内存块数4．页面置换算法性能返回本节【例1】主存块数m=3，置换算法采用FIFO算法，缺页中断次数及缺页率如图4.23所示。在图4.23中，P行表示页面走向，M行表示在主存中的页面号，其中带有+的表示新调入页面，在M行的各列按调入的顺序排列，带有圆圈的数字表示下一时刻将被淘汰页面，F行表示是否引起缺页中断，带√号的表示引起缺页中断。从图4.23可以看出，缺页中断页数为9次，缺页率f=9/12=75%。下一页图4.23FIFO算法性能分析（m=3）下一页【例2】设m=4，仍采用FIFO算法，缺页中断次数及缺页率如图4.24所示。可以算出，在分配给该作业的内存块数增加到4时，缺页中断由图4.23的9次反而增加到了10次，缺页率由75%增加到10/12=83%，这就是FIFO算法的一种异常现象。随着分配的主存块数的增加，缺页中断次数不但没有降低，反而增加了。这与该算法定全不考虑程序的动态特征有关。下一页图4.24FIFO算法性能分析（m=4）下一页【例3】设m=3，采用LRU算法，缺页中断次数及缺页率如图4.25所示。图4.25LRU算法性能分析（m=3）下一页【例4】设m=4，其余同例3，则缺页中断次数及缺页率如图4.26所示。

图4.26LRU算法性能分析（m=4）返回本节4.3.5请求式分段存储管理与动态地址重定位为了能实现虚拟存储，段式逻辑地址空间中的程序段在运行时并不全部装入内存，而是如同请求式分页存储管理，首先调入一个或若干个程序段运行，在运行过程中调用到哪段时，就根据该段长度在内存分配一个连续的分区给它使用。若内存中没有足够大的空闲分区，则考虑进行段的紧凑或将某段或某些段淘汰出去。相应于请求式分页存储管理，这种存储管理技术称为请求式分段存储管理。返回本节图4.27分段的逻辑地址空间下一页请求式分段存储管理的地址变换1．程序的逻辑地址结构

2．段表

3．请求式分段动态地址变换过程

4．请求式分段存储管理的优、缺点

下一页1．程序的逻辑地址结构请求式分段存储管理的逻辑地址结构由段号s和段内位移量d组成，如下图所示。下一页2．段表类似于请求式分页存储管理的页表，为了实现动态地址变换和存储保护，系统要为每一个作业建立一张段表。段表中的每一个表目对应着作业地址空间的一个程序段，其一般格式为：

下一页3．请求式分段动态地址变换过程图4.28请求式分段动态地址下一页请求式分段存储管理的地址变换（1）可提供大容量的虚存

（2）允许动态增加段的长度

（3）便于段的动态链接

（4）便于实现程序段的共享

（5）便于实现存储保护

返回本节4.3.6

段页式存储管理与动态