第9章 存储管理

本章基本内容与要求 基本内容 存储器层次结构 存储管理任务 实存储管理 虚拟存储管理

本章基本内容与要求 要求 掌握存储管理任务 掌握存储管理、 实存储管理 了解存储器层次结构

9.1存储管理的概念与任务 一、存储器层次结构 二、存储管理任务

一、 存储器层次结构

二、存储管理任务 主存空间分配 地址映射 内存保护 内存“扩充”

1.主存空间分配 主存空间分配的任务是动态地为不断进进出出的作业分配主存空间，作业运行完成后，及时回收主存空间。操作系统在实现内存分配时，可采取以下两种方式： 1）静态分配方式 每个作业的主存空间是在作业装入时确定的；在作业装入后的整个运行期间，不允许再申请新的主存空间，也不允许作业在主存中“移动”。 2）动态分配方式 每个作业的主存空间是在作业装入时确定的；但在作业运行过程中，允许继续申请新的附加主存空间，以适应程序和数据的动态增长，也允许作业在主存中“移动”。 为了实现主存分配，在主存分配的机制中应具有以下结构和功能：1) 记住状态；2) 决定主存分配策略；3 )主存分配功能；4) 主存回收的技术和策略。

2.地址映射 通常，程序的起始地址都是从“0”开始的，程序中的其它地址都是相对于起始地址计算的，该地址被称为逻辑地址（或相对地址）。由这些地址所形成的地址范围称为（作业）地址空间。此外，主存单元的编号称为物理地址（或绝对地址），由主存中的一系列单元所限定的地址范围称为存储空间。

2.地址映射

3.内存保护 内存保护是为多个程序共享内存提供保障，使在内存中的各道程序只能访问自己的区域，避免各道程序间相互干扰，特别是当一道程序发生错误时, 不致影响其它程序的运行。通常由硬件完成保护功能，由软件辅助实现。实现方法有界限寄存器和存储保护键等方法。 1）界限寄存器 每个进程都有自己独立的进程空间，如果哪个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。一般提供一对寄存器，即基址寄存器/限长寄存器，分别存放起始地址和长度；或者是一对上界寄存器/下界寄存器。 2）存储保护键 给操作系统区和各个进程空间分别分配不同的整数作为键值，每个进程分别保存自己的键值，进行内存访问的时候匹配当前键值和被访问分区的键值，相等则同意，否则拒绝访问。

4.内存“扩充” 用户在编制程序时，不应该受内存容量限制，所以要采用一定技术从逻辑上来“扩充”内存的容量，使用户得到比实际内存容量大的多的内存空间，这就是内存“扩充”。具体实现方法是在硬件支持下，软硬件相互协作，将内存和外存结合起来统一使用。通过这种方法把内存扩充，使用户在编制程序时不受内存限制。通常的内存扩充技术有覆盖、交换和虚拟存储器。

9.2 实存储管理 单一连续分区 固定分区 动态分区

1.单一连续分区 在单道环境下，除了系统占用一部分主存外，剩下的主存区域全部归进程（作业）占用。 主存可以划分为三部分：系统区、用户区和空闲区。用户占用区是一个连续的存储区，主存除操作系统所用之外，全部给一个用户，故又称单一连续区存储管理。 2.0以下的DOS操作系统即采用单一连续区主存管理方法。 优点：该方法实现简单，便于操作。 缺点： 主存利用不充分，空白区不能利用 作业必须全部装入主存 处理机利用不充分，如作业等待I/O时，处理机空闲 主存不能扩充，当主存可用空间小于作业时，由用户将作业分割成几部分，一部分一部分地运行。

2.固定分区 预先把可分配的主存储器空间分割成若干个连续区域，称为分区。每个分区的大小可以相同也可以不同。 固定分区的优点是可以多道运行，比较简单，要求硬件支持少。缺点是存在内部碎片问题.

3.动态分区 动态分区的概念是主存不是预先划分好的，而是当作业装入时，根据作业的需求和主存空间的使用情况来动态决定是否分配。

3.动态分区 分区分配 空闲分区分配算法 分区的回收 可重定位的动态分区

3.动态分区 分区分配 为了实现动态分配，操作系统必须记录分区的使用情况，一般采用分区表（或者分区链表）来实现。为了便于管理，分区表可以分成两部分：空闲分区表和已分区分配表，分别表示空闲分区和已使用分区的信息

3.动态分区 分区分配

3.动态分区 空闲分区分配算法 1）首次适应算法（First Fit） 2）下次适应算法（Next Fit） 3）最坏适应算法（Worst Fit） 4）最佳适应算法（Best Fit）

3.动态分区 空闲分区分配算法 1）首次适应算法（First Fit） 为作业选择分区时总是按地址从低到高搜索，找到第一个可以容纳该作业的空白块，就把该空白块分割并分配给该作业。 为了提高查找速度，可以把空闲分区链表按照地址递增的次序排列。 该算法简单，快速分配 在低地址区，大的分区不易被保留，大的分区被保留在高地址区，并且时间一长，低地址区不断被分割，往往留下很多难以利用的、很小的空闲分区，这些分区存在于别的分区之外，是单独的分区，叫做“外部碎片”，而每次查找又从低地址开始查找，这又增加了查找开销。

3.动态分区 空闲分区分配算法 2）下次适应算法（Next Fit） 类似首次适应法，又叫做循环首次适应算法。 每次分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就把它划分后分配出去。 优点：解决了首次适应算法低地址区会产生很多碎片的问题，使内存中空闲分区分布比较均匀 缺点：大的空闲分区在内存中不易保留。

3.动态分区 空闲分区分配算法 3）最坏适应算法（Worst Fit） 在作业选择存储块时，总是寻找最大的空白区。为了提高查找速度，可以把空闲分区链表按照空闲块大小递减的次序排列。 优点：当分割后空闲块仍为较大空块 缺点：大的空闲区不易被保留，并且相对其它几种算法来说，主存利用率较低。 。

3.动态分区 空闲分区分配算法 4）最佳适应算法（Best Fit） 接到内存申请时，在空闲块表中找到一个不小于请求的最小空闲块进行分配。为了提高查找速度，可以将空白区按大小递增的顺序链在一起。 优点：比较容易保留大的空闲区 缺点：从整体来看，整个主存容易留下许多难以利用的小空闲区，即外部碎片。

3.动态分区 分区的回收 当进程结束或终止时，要进行内存回收。如果回收的分区与其它的分区相邻，则合并成一个较大的分区，修改空闲分区表，并检查是否满足阻塞在内存空间的等待进程的需求。 动态分区便于动态申请内存、共享内存和动态链接，但缺点是有碎片问题(外部碎片)。

3.动态分区 可重定位的动态分区 主要使用紧凑技术，即当空闲内存被分成很小的块时，即使全部的空间满足需求，也不能分配给请求进程，因为它们并不连续。 为了消除外部碎片，进一步提高主存的利用率，定时地（或者在主存空间紧张时）把主存中的作业“搬家”集中在主存的一端，使另一端产生一个大的空闲区，这种技术称为存储器的“紧凑”。 紧凑仅仅在动态重定位时才可以用，并且在运行时执行。

9.3 虚拟存储管理 1. 虚拟存储器的原理 2. 请求分页存储管理 3. 请求分段存储管理 4. 段页式存储管理

1. 虚拟存储器的原理 基于对大量程序运行特征的观察结果发现，程序在执行过程中一个较短的时期，所执行的指令地址和指令的操作数地址，分别局限于一定的区域，即程序对主存的访问是不均匀的，这种特性叫做程序的局部性原理(Principle of Locality)。 基于局部性原理，程序装入时，不必全部装入内存，而只需要将当前需要的执行的部分读入内存，就可以开始程序执行，在执行过程中，若需要的部分不在内存，由操作系统将其调入，如果没有多余的主存空间，则把暂时不用的部分调出。 27

2.请求分页存储管理 1) 分页管理的基本概念 2) 地址变换机构 3) 页面置换算法 4) 分页存储管理的优缺点 28

2.请求分页存储管理 1) 分页管理的基本概念 （1） 页面、页框 分页是把主存存储空间按大小一定的块划分，称为物理块，或页框；同时按同样的尺寸去划分作业的地址空间，形成一个个相等的页面，称为逻辑页或虚页。因此，作业可以按页为单位，零散地放在主存的不连续的页框中。 在主存中设一个页表，或叫页面映象表（Page map table）， 实现逻辑地址到物理地址的转换. 29

2.请求分页存储管理 1) 分页管理的基本概念 30

2.请求分页存储管理 1) 分页管理的基本概念 （2）地址结构 分页存储管理系统的地址结构与页的大小有关 页的尺寸太大，和可重定位分区分配没什么不同了 页的尺寸太小，页表就得加长，太碎，调度增加。 通常选择页的大小为2的幂。 分页系统中用户的逻辑地址是一个有序对（P，W），P是被访问项的页号，W是被访问项在页P内的位移量。 31

2.请求分页存储管理 1) 分页管理的基本概念 （3）页表结构 页表负责从逻辑地址到物理地址的映射，请求分页存储系统中的页表结构一般如下图所示： 页号 存储块 号 中断位 辅存地 址 引用位 修改位 存取控 制 32

2.请求分页存储管理 2) 地址变换机构 采用一组硬件寄存器，可以按照内容并行查找，存放当前访问页的物理块号，此硬件寄存器即超高速缓存，称为“快表”（Translation Lookaside Buffers），又称为联想寄存器 33

2.请求分页存储管理 2) 地址变换机构 34

2.请求分页存储管理 3) 页面置换算法 (1)先进先出算法(FIFO) 3) 页面置换算法 (1)先进先出算法(FIFO) 先进先出算法是当需要淘汰一页时，选择在主存中驻留时间最长的那页被淘汰掉。 这一算法适用于按线性顺序访问地址的程序，否则效率不高。因为最先进入内存的页面可能是经常被使用的页面，这样会引起页面频繁的变换。 算法简单, 但性能较差，表现为: 内存利用率不高。原因：基于“cpu按线性顺序访问存储空间”假设，而事实并非如此，如循环语句； 存在Belady异常现象：内存块增加，缺页率增加。原因：该算法根本没有考虑程序执行的动态特性。 35

(1)先进先出算法(FIFO) 例：设有一用户程序共分为5页，其执行时页面变化的规律称为页面走向P，分配给该程序的页架数M为3，其页面淘汰过程如下图，其中F为“+”号表示页面有交换。 页面走向 2 3 4 + 1 P= M=3 F=

(1)先进先出算法(FIFO) 例：设有一用户程序共分为5页，其执行时页面变化的规律称为页面走向P，分配给该程序的页架数M为4，其页面淘汰过程如下图，其中F为“+”号表示页面有交换。 P= 3 2 1 4 M=4 F= +

2.请求分页存储管理 3) 页面置换算法 (2)最近最少使用算法(LRU) 3) 页面置换算法 (2)最近最少使用算法(LRU) 当需要淘汰一页时，选择在最近一段时间内最久未用的页淘汰掉。UNIX操作系统采用的就是这种算法。 LRU算法一般是设置记时器或利用堆栈实现，前者在页表的每个入口，设一个“访问时间”区域, 当一个页面被访问时，时钟寄存器里的内容被拷贝到这个区域。置换时替换最小时间值的页面。后者是当页面被访问时，将它从堆栈底部移到顶部。栈顶页面常常是最常用的页面，而底部的就是LRU页。 38

(2)最近最少使用算法(LRU) 例：设有一用户程序共分为5页，其执行时页面变化的规律称为页面走向P，分配给该程序的页架数M为3，其页面淘汰过程如下图，其中F为“+”号表示页面有交换。 页面走向 2 3 4 + 1 P= M=3 F=

2.请求分页存储管理 3) 页面置换算法 (3)最近未使用页面置换算法（NRU） 3) 页面置换算法 (3)最近未使用页面置换算法（NRU） 该算法是LRU算法的近似：将内存中的页面组成一循环链表，每一页面对应一访问位，当某页面被访问时，将其访问位自动置“1”。如果指针指向页面的访问位为“0”（代表最近没有被访问），则置换该页；否则，将访问位置为“0”，页面继续留在内存，按照相同规则替换下一页。如果一页经常被用到，则它永远不会被换出。 40

(3)最近未使用页面置换算法（NRU） 例：设有一用户程序共分为5页，其执行时页面变化的规律称为页面走向P，分配给该程序的页架数M为3，其页面淘汰过程如下图，其中F为“+”号表示页面有交换。 页面走向 2 3 4 + 1 P= M=3 F=

2.请求分页存储管理 3) 页面置换算法 (4)最佳页面置换算法(OPT) 3) 页面置换算法 (4)最佳页面置换算法(OPT) 该算法思想是从主存中移出永不再用的页面，至少是选择很远将来才用的页面淘汰之。其实，这是一个不实用的算法，因为页面走向是不可预知的。所以该算法常用做性能评价的依据。 OPT算法具有最低的缺页率。它和LRU算法一样，属于堆栈型算法，不会产生Belady现象。 42

(4)最佳页面置换算法(OPT) 例：设有一用户程序共分为5页，其执行时页面变化的规律称为页面走向P，分配给该程序的页架数M为3，其页面淘汰过程如下图，其中F为“+”号表示页面有交换。 页面走向 4 2 3 + 1 P= M=3 F=

2.请求分页存储管理 4) 分页存储管理的优缺点 分页存储管理的优点是不需要移动就可解决碎片问题；提高主存的利用率；可提供大容量的多个虚拟存储器；提高了多道程序运行的程度；对大作业而言，更加方便用户。 但由于采用了动态地址变换机构，增加了计算机的成本，处理速度降低；对于请求分页系统，为处理页面中断增加了系统开销；而且在进程的最后一个页框中可能有内部碎片的存在。 44

3.请求分段存储管理 在分页存储系统中，出于系统管理的需求，作业的地址空间是一维线性的，这破坏了程序内部天然的逻辑结构，因为常常会把逻辑上相关的部分划到不同的页面，造成共享、保护的困难。加之，程序员常常用二维地址描述自己的程序，基于用户的需求，产生了分段的思想，即按程序自身的逻辑关系分配存储空间。 1) 分段存储管理的基本概念 2) 实现原理 3) 分段管理的优缺点 4) 分段与分页的区别 45

3.请求分段存储管理 1) 分段存储管理的基本概念 （1) 作业的逻辑地址空间 地址空间按照程序自身的逻辑关系分成若干段。 （1) 作业的逻辑地址空间　 地址空间按照程序自身的逻辑关系分成若干段。 每段有自己的段名（段名通常由程序员给出）。每段有内部段名，它是一个编号，称为段号。 每个段的地址空间都从“0”开始，并且编成连续性的线性地址。 （2） 程序的地址结构　 用段号和段内相对地址（S，W）来描述，通常规定每个作业的段号为从“0”开始的连续正整数。 （3) 主存分配　 段式管理的主存分配以段为单位，采用动态分区分配。每一段分配一块连续的主存分区，一个作业的各段分到的主存分区不要求是相邻连续的分区。 46

3.请求分段存储管理 2) 实现原理 （1）段表和段表地址寄存器　 （2）分段管理中的地址映射 47

3.请求分段存储管理 3) 分段管理的优缺点 优点： 便于模块化处理 消除内部碎片 动态链接方便 缺点： 提高硬件成本，需要更多的硬件支持，地址变换代价增加，使系统更加复杂。 在辅存中管理不定长度的分段困难很多，存储位置不易确定。 分段尺寸受主存大小限制，段太大就不 易在主存中找到合适的空白块 。 由于段长不固定，又会产生外部碎片。 48

3.请求分段存储管理 4) 分段与分页的区别 页不是完整的逻辑信息总体的结合，而段是信息的逻辑单位，它是有意义的一组信息。 页的大小一样，由系统决定。段的大小不一，决定于用户编写的程序。 逻辑地址表示不一样，分页是一维的，分段是两维的。 段是用户可见的，（分段可以在用户编程时确定，也可以在编译程序对源程序编译时根据信息的性质来划分），而页是用户看不见的，是操作系统分的。用户可感知段，但分页活动用户是看不见的，而仅仅用于主存管理。 49

4. 段页式存储管理 段号s 页号p 页内地址d 一、段页式管理的基本概念 1) 段页结构 段页式管理是分页和分段管理结合的结果。段页式管理中，作业的地址空间采用分段方式，而作业的每一段采用分页方式。整个主存分成大小相等的存储块，称为页架，主存以页架为单位分配给每个作业。 2) 段页管理的地址结构 段页式管理中的逻辑地址用三个参数表示，如下图 段号s 页号p 页内地址d 段页式管理地址结构

一、段页式管理的基本概念 3) 段表、页表、段地址寄存器 系统为每个作业建立一个段表，并为每个段建立一个页表，并设置一个段地址寄存器来指出当前运行作业段的段表起始地址和段表长度。

4. 段页式存储管理 二、段页式管理的地址转换 地址转换硬件将逻辑地址中的段号s与段地址寄存器中的段表起始地址b相加得到该访问段的表目。 从该段表目中得到该段页表的起始地址，并与逻辑地址中的页号p相加得到欲访问页在该段页表中的地址。 从该页表目中得到对应的页架号p’并与逻辑地址中的页内地址d相加得到绝对地址。

二、段页式管理的地址转换

4. 段页式存储管理 三、段页式管理的优缺点 优点: 段页式管理具有分页、分段管理的优点，是使用的最广泛、最灵活的一种存储管理技术。 缺点： 需要更多的硬件支持，增加了硬件的成本，同时也增加了软件的复杂性和管理开销。 许多大中型计算机，如IBM370/168、Multics等都采用这种段页式虚拟存储器。