第3章 存储管理

第3章存储管理要求学生了解存储管理的一般性概念;重点掌握分区式管理、分页式管理、分段式管理以及段页式管理的原理，在学习中要注意每种管理方式提出的背景和解决的问题，还要了解系统内部提供的软硬件支持。第3章存储管理3.1概述

3.2简单的存储管理

3.3

分页存储管理

3.4

请求分页存储管理

3.5

分段存储管理

3.6

段页式存储管理

3.6

小结计算机系统中存储器一般分为主存储器和辅助存储器两级。3.1.1存储管理的功能

1．主存分配

2．地址映射:把逻辑地址转换成物理地址的过程

3．主存扩充:借助虚拟存储器或自动覆盖技术来“扩充”主存容量

4．存储保护3.1概述3.1.2内存的分配与回收按分配时机的不同，内存分配可分为两种方式：

1．静态存储分配：装入内存前一次分配

2．动态存储分配：装入内存后在运行中分配

内存分配与回收时应考虑的几个问题：1)如何选择内存中空闲区;2)置换问题;3)回收问题3.1概述3.1.3地址重定位1．逻辑地址空间

地址空间是指程序用来访问信息所用的一系列地址单元的集合。逻辑地址又叫相对地址3.1概述符号指令数据说明I/O说明名空间目标程序作业X地址空间物理空间0B0AA+B512K作业X的源程序图3-1名空间、地址空间、物理空间3.1.3地址重定位2．物理空间

物理空间（也称存储空间）是指主存中物理单元的集合。这些单元的编号称为物理地址或绝对地址

3．地址重定位作业地址空间中使用的逻辑地址变换成主存中的物理地址的过程,也叫地址映射。

4．重定位的类型静态重定位和动态重定位3.1概述3.1.3地址重定位4．重定位的类型

1)静态重定位程序运行之前进行重定位,如图3-3（a）缺点：①它要求分配给程序的内存空间连续,且一旦程序装入后，不能在内存中移动或重分配②用户需要事先确定所需存储量③用户之间难以共享主存中同一程序副本3.1概述2）动态重定位程序执行过程中由硬件地址变换机构实现,如图3-3（b）

动态重定位的主要优点有：（1）用户作业不要求分配连续的存储空间。（2）用户作业在执行过程中，可以动态申请存储空间和在主存中移动。（3）有利于程序段的共享。

动态重定位的主要缺点有：（1）需要附加的硬件支持。（2）实现存储管理的软件算法比较复杂。3.1概述3.1概述50001000Load1,1006Add1,1008Store1,1010XY（a）静态重定位…Load1,5000…X……Load1,5000…X…100005000+011000150000存储空间地址空间(b)动态重定位图3-3重定位类型3.1.4虚拟存储器

虚拟存储技术的基本思想是:将有限的内存空间与大容量的外存进行统一管理，构成一个远大于实际内存的、虚拟的存储器。但实际上这样大容量的内存并不存在，而是虚拟的，因此把具有这种功能的存储管理技术称为虚拟存储管理。3.1概述3.2.1固定分区存储管理

基本思想是:在作业未进入内存之前，把内存可用空间划分成若干个固定大小的存储区，除操作系统占用一个区域外，其余区域为系统中多个用户共享。也称为静态分区

举例:假设某系统有256K内存，刚开始运行时，内存分区划分如图3-4（a）所示。

优点:是简单，要求的硬件支持少，软件算法也简单，

缺点:是容易产生内部碎片。3.2简单的存储管理3.2.1固定分区存储管理操作系统空闲分区作业Y碎片（2K）空闲分区作业X40K48K80K144K256K0K第一分区（8K）第二分区（32K）第三分区（64K）第四分区（112K）（a）内存分配示意图分区号起始地址分区大小状态140K8K0248K32K1380K64K04144K112K1图3-4固定分区存储管理(b)固定式分区说明3.2.2可变式分区存储管理

可变式分区:又叫动态分区是指在作业装入时，根据它对内存空间实际的需求量来划分主存的分区，因此，每个分区的尺寸与进入它的作业大小相同。它能有效解决固定式分区的内部碎片问题。

举例:如图3-5所示，假设某系统采用可变式分区存储管理3.2简单的存储管理3.2.2可变式分区存储管理256K256K操作系统空闲分区操作系统作业一(48K)作业二(24K)作业三(38K)作业四(40K)空闲(50K)操作系统空闲1(48K)作业二(24K)空闲2(38K)作业四(40K)空闲3(50K)206K166K128K104K56K0K0K206K166K128K104K56K0K（a）可变式分区运行开始(b)作业1.2.3.4进入（c）作业1.3释放后图3-5可变式分区内存使用情况示意图3.2.2可变式分区存储管理

1．空闲分区的组织形式常把空闲区组成空闲分区表或空闲分区链表的形式2．内存的分配与回收

当作业请求存储空间时,检索空闲区,分配相应的空间

当作业完成并释放所占分区时，系统应进行回收。若回收区与内存中前后空闲区相邻，则合并成一个较大的空闲区，并修改相应的链表指针;若不相邻，应将空闲区插入到空闲区链表的适当位置。3.2简单的存储管理3.2.2可变式分区存储管理

3．常用的算法常用的分配算法有以下三种：

（1）首次适应算法：选择第一个满足要求的空闲分区分配；优点是查找速度快

（2）最佳适应算法：找到满足要求的最接近作业大小的空闲分区（由小到大存储）

（3）最差适应算法：把空闲区按大小递减，总是检查空闲区链表的第一个空闲区是否满足要求。优点是查询简单3.2简单的存储管理3.2.2可变式分区存储管理4．分区管理的地址重定位和存储器保护（1）地址重定位固定分区采用静态重定位；可变式分区采用动态重定位。实现方法是设置基址（或重定位）寄存器

（2）存储器保护

实现方法是：系统可以增设一个限长寄存器，用来存放运行程序的大小。若地址在范围内，正常运行；若不在，产生地址越界中断，终止程序运行3.2简单的存储管理3.2.2可变式分区存储管理5．分区管理的优缺点主要优点有：1）实现了多道程序共享主存。2）系统设计相对简单，不需要更多的软、硬件开销。3）存储保护的手段比较简单。主要缺点有：1）主存利用不够充分。2）没有实现主存的扩充。3.2简单的存储管理3.2.3覆盖与交换技术1．覆盖（Overlay）

覆盖:是指同一主存区可以被不同的程序段重复使用。

覆盖段:可以相互覆盖的程序段覆盖区:可共享的主存区覆盖段与覆盖区一一对应。覆盖的基本原理可用图3-6所示例子说明

作用:解决了小主存运行大进程的矛盾，在逻辑上扩充了主存，3.2简单的存储管理3.2简单的存储管理主程序（60K）子程序1（25K）子程序2（35K）子程序11(20K)子程序21（25K）子程序22

（15K）主程序（60K）覆盖区1（35K）覆盖区2（25K）常驻段覆盖段0覆盖段1（a）程序内部结构（b）内存图3-6用户程序的覆盖结构3.2.3覆盖与交换技术2．交换（Swapping）

交换:就是系统根据需要把主存中暂时不运行的某个（或某些）进程中的部分或全部信息移到外存，而把外存中的某个（或某些）进程移到相应的主存区，并使其投入运行。

交换通常在以下情况下发生：1）进程用完分配的时间片或等待输入／输出时；2）进程要求扩充其占用的存储区却得不到满足时。

3.2简单的存储管理3.3.1分页存储管理的基本思想

分页存储管理的基本思想是:把内存空间分成大小相等、位置固定的若干个小分区，每个小分区称为一个存储块，简称块，并依次编号为0,1,2,3…n块，每个存储块的大小由不同的系统决定，一般是2的n次幂，如1K，2K，4K等，通常不超过4K。而把用户的逻辑地址空间分成与存储块大小相等的若干页，依次为0，1，2，3，…m页。作业按存储块大小划分为若干页

3.3分页存储管理3.3.1分页存储管理的基本思想

简单分页存储管理:作业一次全部装入内存

请求式分页存储管理:根据作业运行时的实际要求装入

3.3分页存储管理3.3.2主存分配原则系统以存储块为单位把主存分给作业或进程,并且分给一个作业的各存储块，不一定是相邻和连续的。3.3.3页表和页表地址寄存器系统为每个装入主存的作业建立一张相应的页表，如图3-7所示。它的起始地址及大小保存在该作业中。一旦这个作业被调度执行，即把它的页表始址及大小装入特定页表寄存器中。

3.3分页存储管理页号块号存取控制021325图3-7页表3.3.4简单分页存储管理

1．主存的分配与回收页表:如图3-7所示。存储分块表：整个系统一张表2．分配算法首先分配设置页表，将分到的主存块号添入页表中

3．地址变换采用重定位寄存器方式

3.3分页存储管理3.3分页存储管理逻辑地址物理地址02132524525LOAD1,2500DATA页号块号45221485572内存图3-8分页动态地址变换下面从两个例子来说明地址变换过程。如图3-8、3-9和3-10所示3.3分页存储管理2K0K1K3K2K作业一0K0页1页0页1页2页作业二1K页号块号05180617210

空闲作业1（0页）作业2（0页）作业2（1页）作业1（1页）空闲作业2（2页）

空闲图3-9简单分页存储管理示意图3.3分页存储管理图3-10简单分页存储管理地址转换实现过程块内地址w块号p000010011100010000101001110001000172106页号p页内地址w026815块号页号W=1C4H09C4H29C4H

内存3.3.5联想存储器

从上面介绍的地址变换过程可以看出：如果把页表全部放在内存，那么存取一个数据时，至少要访问两次内存。一次是访问页表，形成实际内存地址；另一次是根据形成的内存地址存取数据。为了提高查表的速度，人们在分页地址变换机构中加入一组高速缓冲存储器，用来存放当前作业最常用的页号和与之相应的物理块号。通常称这样的寄存器组为快表或联想存储器。工作原理见图3-11

3.3分页存储管理3.3分页存储管理图3-11采用快表和页表相结合的分页地址变换过程示意图②物理地址①①③②a页表始地址寄存器pw页号块号pb页号块号pbbw逻辑地址联想寄存器页表1）利用快表查找2）利用页表查找3）利用页表中查找的页号、块号更新块表3.3.6存储保护1.在进行地址变换时，产生的页号应小于页表长度，否则视为越界访问，这类似于基址限长存储保护；2.在页表中增加存取控制和存储保护的信息，对每一个存储块，可允许四种保护方式：①禁止做任何操作，②只能执行，③只能读，④能读／写，当要访问某页时，先判断该页的存取控制和存储保护信息是否允许。

3.3分页存储管理页号块号存取控制信息3.3.7简单分页存储管理的优缺点

最大优点:是有效解决碎片问题，主存利用率高，内存分配与回收算法也比较简单

缺点:是采用动态地址变换机构增加了硬件成本，也降低了处理机速度。

3.3分页存储管理3.4.1请求分页存储管理的地址变换

解决两个问题:1.要访问的某页不在内存时，如何发现这种缺页情况？发现后应如何处理？

解决:增加一个状态位和当前页在辅存的地址。状态位用以表示当前页是否在内存中。

2．当需要把外存上的某个页面调入内存时，此时内存中没有空闲块应怎么办？

解决:页面置换

3.4请求分页存储管理图3-12是请求式分页存储管理的存储映像。

3.4请求分页存储管理0…1…2…3412……461010页号辅存地址状态位块号作业1其他作业MoveR1作业1图3-12请求式分页存储管理示意图页号内存块号状态位改变位引用位辅存地址存取控制其他页表的表目3.4.2页面置换算法1．最优算法（OPT算法）：如图(a)选择距下次被引用时间间隔最大的页来淘汰2．先进先出算法（FIFO算法）：如图(b)3．最久未使用页面置换算法（LRU算法）：如图(c)所示,把到目前为止最长时间没有被使用的页淘汰;近似的LRU算法：如图(d)所示4．时钟算法时钟算法是寻找一个从上次检查以来没有被访问过的页面3.4请求分页存储管理2321524532522222224442223333333333315

5555555FFF2222315522433331522443515

2443352FFFFFF2222315245333331524532515

2453252FFFFF22223152433333315243225152455552FFFFF（a）最佳算法（b）先进先出算法（c）最近最久未使用算法（d）近似的LRU算法图不同淘汰算法对同一页面请求序列的效果3.4.3请求页式存储管理的特点

1.请求页式管理的优点

1）由于它不要求作业或进程的程序段和数据在主存中连续存放，从而有效地解决了碎片问题。

2）请求分页管理提供了虚拟存储器。提高了主存的利用率，有利于多道程序的运行和方便用户，特别是大作业用户。3.4请求分页存储管理3.4.3请求页式存储管理的特点

2．请求页式管理的缺点

1）必须有相应的硬件支持。

2）为处理缺页中断，增加了处理机时间的开销

3）可能因作业地址空间的过大或多道程序的道数过多，以及其他原因而造成系统抖动，

4）虽然消除了碎片，但每个作业或进程的最后一页内存总还有一部分空间得不到利用。3.4请求分页存储管理3.5.1分段管理的基本思想

基本思想:在分段存储管理中，作业的地址空间由若干个逻辑分段组成，每一分段是一组逻辑意义完整的信息集合，并有自己的名字（段名）。每一段都是以0开始的连续的一维地址空间,整个作业则构成了二维地址空间分段存储管理是以段为基本单位分配内存，且每一段必须在连续的内存空间中，但各段之间不要求连续。

分段存储管理的逻辑地址结构如下：3.5分段存储管理段号S段内位移W3.5.2地址变换为了实现段的逻辑地址到物理地址的转换，系统为每个作业设置了一张段表SMT。每个表目至少有4个数据项：段号、段长、内存始址和存取控制。分段存储管理系统的地址变换过程如图3-15所示。

3.5分段存储管理3.5分段存储管理段表起始地址段表长度段号段长hang1内存始址08001231K6502K60008000400010K24004400<<段号段内位移逻辑地址越界中断物理地址段表控制寄存器图3-15分段存储管理的地址变换示意图3.5.2地址变换例如：在一个分段存储管理系统中，其段表如表3-1所示。求表3-2中所示逻辑地址对应的物理地址。

3.5分段存储管理段号内存起始地址段长02105001235020210090表3-1段表段号段内位移04301102500表3-2逻辑地址分析：在由表3-1可知，段号为0的段的内存地址起始地址为210，段长为500。由表3-2知，逻辑地址的段内位移为430。因为400<500，所以该逻辑地址是合法的。其对应的物理地址为：210+430=640

3.5分段存储管理由表3-1知，段号为1的段的内存起始地址为2350，段长为20。由表3-2知，逻辑地址的段内位移为10。因为10<20，所以该逻辑地址是合法的。其对应的物理地址为：2350+10=2360。

由表3-1知，段号为2的段的内存起始地址为100，段长为90。由表3-2知，逻辑地址的段内位移为500。因为500>90即逻辑地址的段内位移500已经超过了段长90，所以该逻辑地址是非法的。

3.5.3段的共享与保护

1.段的共享:

用户使用相同的段名并置以适当的读写控制权,即可共享

2.分段存储管理系统的保护措施：

1）在段表中设置一个段长值。当存储访问时，将段地址的位移量与段长进行比较2）在段表的每个表目中建立存取控制3）采用存储保护键

3.5分段存储管理3.5.4分段与分页的区别（1）页是信息的物理单位。分页的目的是实现离散分配，减少内存的外零头，提高内存利用率。段是信息的逻辑单位。每一段在逻辑上是一组相对完整的信息。（2）分页存储管理的作业地址空间是一维的，而分段存储管理的作业地址空间是二维的。（3）页的大小固定且由系统确定，是等长的。而段的长度不定，它是由具有相对完整意义的信息长度确定。（4）分页的优点体现在内存空间的管理上，而分段的优点体现在地址空间的管理上。

3.5分段存储管理3.5.5段式存储管理的优缺点

1.段式管理的主要优点如下：

（1）便于程序模块化处理和便于处理变换的数据结构。（2）便于动态连接。（3）便于共享分段。（4）可以实现虚拟存储器，使作业的地址空间不受主存容量的限制。

3.5分段存储管理3.5.5段式存储管理的优缺点

2.段式管理的主要缺点如下：（1）和分页管理一样，处理机要为地址变换花费时间；要为表格提供附加的存