第四章_存储管理

1、操作系统 Operating System教学目的教学目的&通过对本章的讲解使学生理解并掌握存通过对本章的讲解使学生理解并掌握存储管理功能，各种内存分配方式，如连储管理功能，各种内存分配方式，如连续分配方式，离散分配方式以及虚拟存续分配方式，离散分配方式以及虚拟存储的基本理论。储的基本理论。本章重点：本章重点：&程序的装入方式程序的装入方式&连续分配方式的管理连续分配方式的管理&离散分配方式的管理离散分配方式的管理&虚拟存储的基本理论虚拟存储的基本理论本章难点：本章难点：&地址变换的实现地址变换的实现&虚拟存储的理解虚拟存储的理解&页面置换算法的实现页面置换算法的实现第第4 4章章 存储管理存

2、储管理4.1 4.1 存储管理的原理存储管理的原理 4.2 4.2 连续分配存储管理连续分配存储管理 4.3 4.3 离散分配存储管理离散分配存储管理4.4 4.4 内核主存管理内核主存管理4.5 4.5 虚拟存储技术虚拟存储技术4.6 4.6 虚拟页式存储管理虚拟页式存储管理 4.7 4.7 虚拟段式存储管理虚拟段式存储管理4.8 4.8 存储管理实例存储管理实例本章学习目标本章学习目标 &本章首先介绍了存储管理的研究对象和目的，明确本章首先介绍了存储管理的研究对象和目的，明确了存储管理的基本功能和原理；然后从连续、离散了存储管理的基本功能和原理；然后从连续、离散（实存、虚存）两个角度，分别

3、介绍了常用的几种（实存、虚存）两个角度，分别介绍了常用的几种存储管理方案；最后介绍了当前主流操作系统中存存储管理方案；最后介绍了当前主流操作系统中存储管理实例。储管理实例。 存储管理方式一览表存储管理方式一览表存储方式存储方式连续存储方式（实存）连续存储方式（实存）离散离散单连续区单连续区固定分区固定分区可变分区可变分区内核存储管理内核存储管理实存实存虚存虚存分页分页分段分段段页式段页式虚拟页式虚拟页式虚拟段式虚拟段式虚拟段页式虚拟段页式4.1 4.1 存储管理的原理存储管理的原理4.1.1 4.1.1 存储器存储器4.1.2 4.1.2 存储管理的原理存储管理的原理4.1.3 4.1.3 链

4、接链接4.1.4 4.1.4 存储管理的机制和策略存储管理的机制和策略4.1.1 4.1.1 存储器存储器1.1.存储器存储器主存(内部存储器，磁芯存储器）辅存辅存（外存）磁盘、磁带、软盘）（外存）磁盘、磁带、软盘）高速缓冲存储器高速缓冲存储器CacheCache 通常将用户的作业放在通常将用户的作业放在主主存存中执行；中执行；而把那些不而把那些不立即使用的程序、数据立即使用的程序、数据放在外存中，用到时再放在外存中，用到时再将它们调入内存中；将它们调入内存中；在在程序运行时，为了提高程序运行时，为了提高对数据的存取速度，会对数据的存取速度，会将一些常用的表格，变将一些常用的表格，变量，临时数

5、据等放入到量，临时数据等放入到高速缓存高速缓存中。中。图4.1 存储层次 主存 系统区（存放OS程序和数据） 用户区（存放用户程序、数据）由于系统开工期间，由于系统开工期间，OSOS程序与其他程序一起共享主存，程序与其他程序一起共享主存，为安全起见，多道程序系统常由为安全起见，多道程序系统常由OSOS把内存初始化为：把内存初始化为：程序的指令和数据只有放在内存中，程序的指令和数据只有放在内存中，CPUCPU才能对其进行才能对其进行直接存取，或者说该程序才能被执行。直接存取，或者说该程序才能被执行。可见内存资可见内存资源是进程执行时不可或缺的条件之一。源是进程执行时不可或缺的条件之一。2.2.主

6、存（内存）主存（内存）存储管理常指对用户区进行管理存储管理常指对用户区进行管理系统区用户区图4.2内存示意图4.1.2 4.1.2 存储管理的原理存储管理的原理 1.1.存储管理的原理存储管理的原理(1)(1)程序执行过程程序执行过程 首先首先CPU通过程序计数器中的值从内存中取得相应的指通过程序计数器中的值从内存中取得相应的指令，指令被译码后根据要求可能会从存储器中再取得操作数。令，指令被译码后根据要求可能会从存储器中再取得操作数。对操作数处理完成后，操作结果又会存储到存储器中；对操作数处理完成后，操作结果又会存储到存储器中；进程进程在运行过程中依据任务的要求也会请求内存空间，如在运行过程中

7、依据任务的要求也会请求内存空间，如I/OI/O需要需要缓冲区、存放临时数据等，这涉及到内存的分配与回收问题。缓冲区、存放临时数据等，这涉及到内存的分配与回收问题。(2)(2)存储管理的主要工作存储管理的主要工作 就是负责内存空间的使用管理，就是负责内存空间的使用管理，即为进程分配与回收空即为进程分配与回收空间，将程序装入指定内存区域；间，将程序装入指定内存区域；再从指定的存储单元中读写再从指定的存储单元中读写数据，而内存单元的读写操作是由主存硬件完成的，所以对数据，而内存单元的读写操作是由主存硬件完成的，所以对主存发出的读写请求主存发出的读写请求只要指定主存单元只要指定主存单元就行。就行。 2

8、.2.存储单元与物理地址空间存储单元与物理地址空间(1)(1)物理地址（绝对地址）物理地址（绝对地址）内存是由若干个存储单元组成的，每个存储单元有一个编号，这内存是由若干个存储单元组成的，每个存储单元有一个编号，这种种编号可唯一标识一个存储单元，称为内存地址编号可唯一标识一个存储单元，称为内存地址（或物理地（或物理地址）。址）。(2)(2)物理地址空间物理地址空间是是指物理地址的集合指物理地址的集合，也叫绝对地址空间或实空间或存储空间，也叫绝对地址空间或实空间或存储空间，亦即内存空间。存储空间中的单元一般都是按字节从亦即内存空间。存储空间中的单元一般都是按字节从0 0开始连开始连续编址的，续编

9、址的，内存空间的最大容量由地址总线决定。内存空间的最大容量由地址总线决定。如地址总线如地址总线有有2424根，则其地址范围是根，则其地址范围是0 016M-1(216M-1(22424-1)-1)，最大容量为，最大容量为16M16M。(3)(3)存储单元的访问存储单元的访问存储器只能通过物理地址访问内存单元。存储器只能通过物理地址访问内存单元。即给出欲访问的存储单即给出欲访问的存储单元绝对地址，存储器即可对其进行读写操作。元绝对地址，存储器即可对其进行读写操作。3.3.作业的装入作业的装入 (1) (1)作业的处理过程作业的处理过程用户的作业总是由一个或若干个源程序文件组成，编译或汇用户的作业

10、总是由一个或若干个源程序文件组成，编译或汇编程序可编程序可对源程序文件进行编译或汇编形成相应的目标模块，对源程序文件进行编译或汇编形成相应的目标模块，再再由连接程序将这些目标模块和库函数连接成一个完整的装入模块，由连接程序将这些目标模块和库函数连接成一个完整的装入模块，最后将其装入内存执行。最后将其装入内存执行。 (2) (2)名字空间名字空间用汇编语言或高级语言编写程序时，总是通过符号名来访问用汇编语言或高级语言编写程序时，总是通过符号名来访问某一单元。我们把程序中某一单元。我们把程序中由符号名组成的空间称为名空间。由符号名组成的空间称为名空间。 (3) (3)逻辑地址空间逻辑地址空间源程序

11、经过汇编或编译并再经过链接程序所装配形成的程序，源程序经过汇编或编译并再经过链接程序所装配形成的程序，通常通常是以是以0 0为基址进行顺序编址，为基址进行顺序编址，或者是分成若干个部分，每个或者是分成若干个部分，每个部分以部分以0 0为基址，这样的地址表示形式称为相对地址为基址，这样的地址表示形式称为相对地址, ,也叫做逻辑也叫做逻辑地址或虚地址，地址或虚地址，把该程序逻辑地址组成的集合叫做程序的逻辑地把该程序逻辑地址组成的集合叫做程序的逻辑地址空间址空间( (简称地址空间，也叫简称地址空间，也叫相对地址空间相对地址空间或或虚空间虚空间 ) ) 。图图4.34.3装入示意图装入示意图Goto

12、L1L1：源程序编译Goto 2目标代码0123名空间地址空间装入Goto a2内存(运行程序)aa1存储空间a2 【作业的名空间、逻辑地址空间和物理空间作业的名空间、逻辑地址空间和物理空间】图4.4名空间逻辑物理空间示意图4.4.地址重定位地址重定位(1)(1)地址变换地址变换作业运行时不能按其相对地址访问内存单元，而应按相应的物作业运行时不能按其相对地址访问内存单元，而应按相应的物理地址访问。因此理地址访问。因此将一个逻辑地址空间的程序装入到物理地将一个逻辑地址空间的程序装入到物理地址空间时，由于两个空间不一致，需要进行址空间时，由于两个空间不一致，需要进行相对地址到物理相对地址到物理地址

13、的转换地址的转换，即地址的重定位。，即地址的重定位。也就是说也就是说将虚地址映射为内将虚地址映射为内存地址，这种作法叫做地址重定位或地址变换或存地址，这种作法叫做地址重定位或地址变换或地址映射地址映射。地址重定位有两种方式：静态重定位和动态重定位。地址重定位有两种方式：静态重定位和动态重定位。(2)(2)静态地址重定位静态地址重定位静态地址重定位是在程序执行之前由操作系统的重定位装入程静态地址重定位是在程序执行之前由操作系统的重定位装入程序完成的。序完成的。在装入一个作业时，把作业中的指令地址全部转在装入一个作业时，把作业中的指令地址全部转换为绝对地址换为绝对地址（地址转换工作是在作业执行前集

14、中一次完成（地址转换工作是在作业执行前集中一次完成的）在作业执行过程中就无须再进行地址转换工作。的）在作业执行过程中就无须再进行地址转换工作。 Load ah,781078 3651000Load ah,10781001相对地址装入装入模块内存绝对地址1078 365静态地址重定位的静态地址重定位的优点优点是容易实现，无需硬件是容易实现，无需硬件支持，支持，它只要求程序本它只要求程序本身是可重定位的，即对身是可重定位的，即对那些要修改的地址部分那些要修改的地址部分具有某种标识，地址重具有某种标识，地址重定位由专门设计的程序定位由专门设计的程序来完成。在早期的操作来完成。在早期的操作系统中大多数

15、都采用这系统中大多数都采用这种方法。种方法。其主要缺点是其主要缺点是程序经地址重定位后就程序经地址重定位后就不能移动了，因而不能不能移动了，因而不能重新分配内存，不利于重新分配内存，不利于内存的有效利用。内存的有效利用。静态地址重定位示例静态地址重定位示例图4.5静态重定位示意图(3)动态地址重定位动态地址重定位 动态地址重定位是在程序执行期间进行的动态地址重定位是在程序执行期间进行的。在在CPUCPU访问内存之前访问内存之前, ,将要访问的程序或数据地址转换成内将要访问的程序或数据地址转换成内存地址。存地址。 通过基地址寄存器、变址寄存器计算出指令的有通过基地址寄存器、变址寄存器计算出指令的

16、有效地址，再利用硬件机构实现地址映射，这样的硬效地址，再利用硬件机构实现地址映射，这样的硬件设备称为件设备称为存储管理单元存储管理单元MMU(Memory-Management MMU(Memory-Management Unit)Unit)。 通常采用的办法是通常采用的办法是利用一个重定位寄存器，对利用一个重定位寄存器，对每一个有效地址都要加上重定位寄存器中的内容，每一个有效地址都要加上重定位寄存器中的内容，以形成绝对地址。以形成绝对地址。 动态地址重定位的动态地址重定位的优点是程序在内存中的搬移不会对程序的优点是程序在内存中的搬移不会对程序的正确执行造成影响，使内存得以被充分利用，正确执行

17、造成影响，使内存得以被充分利用，其缺点是需要附加其缺点是需要附加的硬件支持，实现存储管理的软件算法比较复杂。的硬件支持，实现存储管理的软件算法比较复杂。图4.6 动态重定位及存储保护示意图4.1.3 4.1.3 链接链接&链接是指多个目标模块在执行时的地址空间分配和相互引用。链接方法一、链接方法一、链接方法、静态链接（、静态链接（static-linking）静态链接是在生成可执行文件时进行的。在目标模块中记录符号地址(symbolic address)，而在可执行文件中改写为指令直接使用的数字地址。Module AModule Acall function10L-1Module BModul

18、e B0M-1function1().function1FModule AModule Acall L+F0L-1Module BModule BLL+M-1function1().function1L+F图4.7 静态链接示意图2. 2. 动态链接动态链接(dynamic-linking)(dynamic-linking)在装入或运行装入或运行时进行链接。通常被链接的共享代码称为动态链接库(DLL, Dynamic-Link Library)或共享库(shared library)。F共享共享：多个进程可以共用一个：多个进程可以共用一个DLLDLL，节省内存，减少文件，节省内存，减少文件交换

19、。交换。F部分装入部分装入：一个进程可以将多种操作分散在不同的：一个进程可以将多种操作分散在不同的DLLDLL中中实现，而只将当前操作相应的实现，而只将当前操作相应的DLLDLL装入内存。装入内存。F便于局部代码修改便于局部代码修改：即便于代码升级和代码重用；只要函：即便于代码升级和代码重用；只要函数的接口参数（输入和输出）不变，则修改函数及其数的接口参数（输入和输出）不变，则修改函数及其DLLDLL，无需对可执行文件重新编译或链接。无需对可执行文件重新编译或链接。F便于运行环境适应便于运行环境适应：调用不同的：调用不同的DLLDLL，就可以适应多种使，就可以适应多种使用环境和提供不同功能。如

20、：不同的显示卡只需厂商为其用环境和提供不同功能。如：不同的显示卡只需厂商为其提供特定的提供特定的DLLDLL，而，而OSOS和应用程序不必修改。和应用程序不必修改。&缺点：缺点：F链接开销链接开销：增加了程序执行时的链接开销；：增加了程序执行时的链接开销；F管理开销管理开销：程序由多个文件组成，增加管理复杂度。：程序由多个文件组成，增加管理复杂度。&以以Multics系统为例，给出动态链接的一系统为例，给出动态链接的一种实现方法。种实现方法。& 操作系统需要为每一个进程保持一个用于操作系统需要为每一个进程保持一个用于记录当前已连接段的表目，该表称作段名记录当前已连接段的表目，该表称作段名-段号

21、对照表，见下表：段号对照表，见下表：段名段名段号段号namenumb&此外，为了将一个外段中的符号名转换为对此外，为了将一个外段中的符号名转换为对应的段内地址，每个段在编译时，需要生成应的段内地址，每个段在编译时，需要生成符号表，放在一个段的前面，作为段的一个符号表，放在一个段的前面，作为段的一个组成部分。见下表：组成部分。见下表：符号名符号名段内地址段内地址S1A1SKAK这样，一个段由符号表和目标程序两部分构成。例如：例如：&设有两个段，段名分别为设有两个段，段名分别为W和和X，见下述，见下述过程过程：load 1, x| W W段段 1234 X X段段 编译前编译前 段首地址 段号0

22、1 2段表 W段 （段号=2）load *1, 2|100“7X|”601001 2 160160段名段号MAIN0A1W2 段名-段号对照表 Y 200 12456 X段段 （尚未连接）（尚未连接）200 编译后连接前编译后连接前 段首地址 段号0 1 2 3 段表 60W段段 （段号（段号=2）load *1, 2|100“7X|”1001600 3 200 Y 200 12456 X段段 （已经连接）（已经连接）200段名段号MAIN0A1W2X3 连接后连接后 段名-段号对照表4.1.44.1.4存储管理的机制和策略存储管理的机制和策略&在多道环境下，存储管理不但要为进程提供内存资在多

23、道环境下，存储管理不但要为进程提供内存资源，还要为源，还要为内存的使用提供安全保障机制内存的使用提供安全保障机制，如防止，如防止进程非法访问不属于自已的空间。进程非法访问不属于自已的空间。&为了提高内存资源的利用率，存储管理还要为了提高内存资源的利用率，存储管理还要提供共提供共享机制，享机制，也就是当若干个进程调用同一段代码或数也就是当若干个进程调用同一段代码或数据时，系统应为共享的代码或数据保留一个副本而据时，系统应为共享的代码或数据保留一个副本而不是多个。不是多个。&这是从节省资源使用出发，但是作为有限的内存资这是从节省资源使用出发，但是作为有限的内存资源，经常有不够用的时候。随着主存元器

24、件成本的源，经常有不够用的时候。随着主存元器件成本的下降，主存的容量在不断地增长，但是在主存中运下降，主存的容量在不断地增长，但是在主存中运行的作业数也在增加，同时用户作业的规模也在不行的作业数也在增加，同时用户作业的规模也在不断地加大，因而内存容量总是很紧张。所以存储管断地加大，因而内存容量总是很紧张。所以存储管理为了能运行大作业或尽可能多地执行任务，理为了能运行大作业或尽可能多地执行任务，就要就要提供内存扩充技术。提供内存扩充技术。综上所述，存储管理的功能如综上所述，存储管理的功能如下所示：下所示： 【存储管理的功能】 1.1.内存的分配与回收内存的分配与回收&每一个进程运行时都需要内存资

25、源，每一个进程运行时都需要内存资源， 因此内因此内存空间的分配和回收是存储管理的基本功能。存空间的分配和回收是存储管理的基本功能。在在进程创建时按照一定的存储策略为其分配内存空进程创建时按照一定的存储策略为其分配内存空间，进程运行结束时，再将其所占用的内存空间间，进程运行结束时，再将其所占用的内存空间收回。收回。&为了记录内存的使用情况，为了记录内存的使用情况，存储管理会依据存储管理会依据存储策略采用相应的数据结构，存储策略采用相应的数据结构，标识哪些区域尚标识哪些区域尚未分配，哪些区域已经分配以及分配给哪些进程未分配，哪些区域已经分配以及分配给哪些进程等。每一个进程运行时都需要内存资源，等。

26、每一个进程运行时都需要内存资源， 因此因此内存空间的分配和回收是存储管理的基本功能。内存空间的分配和回收是存储管理的基本功能。系统通过所采用的数据结构来管理内存空间。系统通过所采用的数据结构来管理内存空间。【存储管理的功能】&内存分配按分配时机的不同，可分为两种方式。内存分配按分配时机的不同，可分为两种方式。&（1 1）静态存储分配：）静态存储分配：指内存分配是在作业运行之前各目标模指内存分配是在作业运行之前各目标模块连接后，把整个作业一次性全部装入内存，并在作业的整个块连接后，把整个作业一次性全部装入内存，并在作业的整个运行过程中，不允许作业再申请其他内存，或在内存中移动位运行过程中，不允许

27、作业再申请其他内存，或在内存中移动位置。也就是说，内存分配是在作业运行前一次性完成的。置。也就是说，内存分配是在作业运行前一次性完成的。&（2 2）动态存储分配：）动态存储分配：作业要求的基本内存空间是在目标模块作业要求的基本内存空间是在目标模块装入内存时分配的，但在作业运行过程中，允许作业申请附加装入内存时分配的，但在作业运行过程中，允许作业申请附加的内存空间，或是在内存中移动，即分配工作可以在作业运行的内存空间，或是在内存中移动，即分配工作可以在作业运行前及运行过程中逐步完成。前及运行过程中逐步完成。【存储管理的功能】&2.2.地址地址映射与存储保护映射与存储保护&在多任务环境下，为防止内

28、存中各程序相互干扰，必在多任务环境下，为防止内存中各程序相互干扰，必须对内存中的程序和数据进行保护。须对内存中的程序和数据进行保护。规定每一个进程只规定每一个进程只能在自己的存储区内活动，能在自己的存储区内活动，否则产生越界中断。否则产生越界中断。&存储保护一般以硬件保护机制为主，软件为辅。存储保护一般以硬件保护机制为主，软件为辅。因为因为完全用软件实现系统开销太大，速度成倍降低。故采用完全用软件实现系统开销太大，速度成倍降低。故采用软、硬件相结合的方式，一旦发生越界或非法操作时，软、硬件相结合的方式，一旦发生越界或非法操作时，硬件保护机制产生中断，进入操作系统处理。硬件保护机制产生中断，进入

29、操作系统处理。&存储保护机制应设置在主存操作之前，存储保护机制应设置在主存操作之前，也就是存储保也就是存储保护机制对每一个欲访问的主存地址都要进行检查。护机制对每一个欲访问的主存地址都要进行检查。若为若为合法访问，就可以去相应的内存单元中存取数据；否则合法访问，就可以去相应的内存单元中存取数据；否则就产生一个错误中断交由操作系统处理，即该次访问内就产生一个错误中断交由操作系统处理，即该次访问内存操作被终止。存操作被终止。【存储管理的功能】&常用的存储保护方法有：常用的存储保护方法有：&（1 1）上、下界存储保护：）上、下界存储保护：上、下界保护是一种简单的上、下界保护是一种简单的存储保护技术。

30、存储保护技术。系统可设置一对上、下界寄存器，分别用系统可设置一对上、下界寄存器，分别用来存放当前运行进程在内存空间的上、下边界地址，来存放当前运行进程在内存空间的上、下边界地址，用它用它们来限制用户程序的活动范围。们来限制用户程序的活动范围。 &（2 2）基址）基址限长存储保护：限长存储保护：上、下界保护的一个变种上、下界保护的一个变种是采用基址是采用基址限长存储保护。限长存储保护。在限长寄存器中存放作业的在限长寄存器中存放作业的长度，地址转换前进行测试，若逻辑地址的值大于限长值，长度，地址转换前进行测试，若逻辑地址的值大于限长值，就属于非法访问，产生一个越界中断，就属于非法访问，产生一个越界

31、中断，交由操作系统处理；交由操作系统处理；若逻辑地址的值小于限长值，则表示地址合法，可以对其若逻辑地址的值小于限长值，则表示地址合法，可以对其进行存取。只有这样内存中的进程才不会相互干扰，才能进行存取。只有这样内存中的进程才不会相互干扰，才能相对独立。相对独立。【界限寄存器的两种存储保护方式界限寄存器的两种存储保护方式】图4.8存储保护示意图【存储管理的功能】 存储保护还涉及对所访问区域的权限检查。存储保护还涉及对所访问区域的权限检查。应对每个访问共享区域的进程设置访问权限。应对每个访问共享区域的进程设置访问权限。进程对共享区域的操作不能超出自己的权限范进程对共享区域的操作不能超出自己的权限范

32、围，围，即对公共区域的访问要加以检查以防越权。即对公共区域的访问要加以检查以防越权。&权限的设置通常可以采用如下原则：权限的设置通常可以采用如下原则： 对属于自己区域的信息，可读可写。对属于自己区域的信息，可读可写。 对公共区域中允许共享的信息或获得授权对公共区域中允许共享的信息或获得授权可使用的信息，可读而不可修改。可使用的信息，可读而不可修改。 对未获授权使用的信息，不可读、不可写。对未获授权使用的信息，不可读、不可写。【存储管理的功能】3.3.内存共享与扩充内存共享与扩充&内存空间共享有两方面的含义：一是指内存被多个并发进内存空间共享有两方面的含义：一是指内存被多个并发进程所共用，即每一

33、个进程占据内存的一段相对独立的区域；程所共用，即每一个进程占据内存的一段相对独立的区域；二是指内存中某一区域的信息可被多个进程共享。很显然，二是指内存中某一区域的信息可被多个进程共享。很显然，共享将极大地提高内存空间的利用率。共享将极大地提高内存空间的利用率。&可被共享的内容既可以是程序代码，也可以是数据。如果可被共享的内容既可以是程序代码，也可以是数据。如果是代码共享，则共享的代码必须是纯代码，或称是代码共享，则共享的代码必须是纯代码，或称“可再入程可再入程序序”。即它在运行过程中不修改自身，可再入程序所使用的。即它在运行过程中不修改自身，可再入程序所使用的工作区由调用它的进程提供。信息共享

34、可以节省内存空间，工作区由调用它的进程提供。信息共享可以节省内存空间，还可以实现进程间通信。还可以实现进程间通信。&内存扩充技术主要有：内存扩充技术主要有：(1)(1)覆盖技术，节约内存使用；覆盖技术，节约内存使用； (2)(2)交换技术，轮流使用内存；交换技术，轮流使用内存；(3)(3)虚拟存储管理技术，用外存补充内存的不足。虚拟存储管理技术，用外存补充内存的不足。4.2 4.2 连续分配存储管理连续分配存储管理4.2.1 4.2.1 单连续存储管理单连续存储管理4.2.2 4.2.2 固定分区存储管理固定分区存储管理4.2.3 4.2.3 可变分区存储管理可变分区存储管理* * *4.2.

35、4 4.2.4 连续分配中内存扩充技术连续分配中内存扩充技术 连续分配是指每一进程占据连续的空间，可分连续分配是指每一进程占据连续的空间，可分为单连续、固定分区及可变分区三种形式。为单连续、固定分区及可变分区三种形式。1.1.内存分配与回收内存分配与回收一道用户程序独占用户区，如图所示。一道用户程序独占用户区，如图所示。 4.2.1 4.2.1 单连续存储管理单连续存储管理单一连续分配是一种简单的存储分配方案，主单一连续分配是一种简单的存储分配方案，主要用于单用户单任务操作系统。要用于单用户单任务操作系统。注意：本章所述的内存分配与回收都指用户区注意：本章所述的内存分配与回收都指用户区的分配与

36、回收，除非特别说明。的分配与回收，除非特别说明。通常内存被划分为通常内存被划分为系统区和用户区。系统区和用户区。系统区系统区是操作系统专用区，不允是操作系统专用区，不允许用户程序直接访问，一般在内许用户程序直接访问，一般在内存低地址部分，剩余的其它内存存低地址部分，剩余的其它内存区域为区域为用户区。用户区。图4.9 单连续分区管理示意图3.3.内存保护内存保护通过通过基址寄存器基址寄存器保证用户程序不会从系统区开始；另保证用户程序不会从系统区开始；另外系统需要一个外系统需要一个界限寄存器界限寄存器，里边存储程序逻辑地址，里边存储程序逻辑地址范围，若需要进行映射的逻辑地址超过了界限寄存器范围，若

37、需要进行映射的逻辑地址超过了界限寄存器中的值，则产生一个越界中断信号送中的值，则产生一个越界中断信号送CPUCPU。 2.2.地址映射地址映射物理地址物理地址= =用户区基地址用户区基地址+ +逻辑地址。逻辑地址。4.4.单一连续分配方案的优缺点单一连续分配方案的优缺点优点：方法简单，易于实现；优点：方法简单，易于实现；缺点：它仅适用于单道程序，因而不能使处理机和缺点：它仅适用于单道程序，因而不能使处理机和内存得到充分利用。内存得到充分利用。4.2.2 4.2.2 固定分区存储管理固定分区存储管理&分区存储管理是把主存储器中的用户区分成若干个连续区进行管理，每个连续区中可装入一个作业。&多道程

38、序系统一般都采用多个分区的存储管理，具体可分为固定分区和可变分区两种方式。 1.1.分区划分方法分区划分方法OS 把主存中可分配的用户区域预先划分成若干个连续的分把主存中可分配的用户区域预先划分成若干个连续的分区，每个连续区的大小可以相同，也可以不同。区，每个连续区的大小可以相同，也可以不同。 但是，但是，一旦划分好分区之后，主存中分区的个数就固定一旦划分好分区之后，主存中分区的个数就固定了，且每个分区的大小也固定不变。了，且每个分区的大小也固定不变。这是一种静态分区法。这是一种静态分区法。 分区大小相等分区大小相等: :分区大小不等：分区大小不等：分区划分分区划分适合于对象所需空间相等的情况

39、；适合于对象所需空间相等的情况；缺乏灵活性，易造成内存空间缺乏灵活性，易造成内存空间的浪费。的浪费。是对分区大小相等方式的改进，是对分区大小相等方式的改进，可更好地适应程序的大小。可更好地适应程序的大小。2.2.主存分配表主存分配表区号区号分区长度分区长度起始地起始地址址状态状态1l1Ka02l2Kbjob23l3Kc0空空 job2由于主存中有多个分区，为了管理主存空间的使用，由于主存中有多个分区，为了管理主存空间的使用，必须设置一张必须设置一张“主存分配表主存分配表”，以说明各分区的分，以说明各分区的分配情况。配情况。表表-1-1主存分配表主存分配表空空 OS0abcd图4.10内存分配示

40、意图3.3.主存空间的分配与释放主存空间的分配与释放 &主存分配表中应指出各分区的起始地址和长度，并为主存分配表中应指出各分区的起始地址和长度，并为每个分区设一个标志位。当标志位为每个分区设一个标志位。当标志位为“0”时，表示对时，表示对应的分区是空闲分区，当标志位为非应的分区是空闲分区，当标志位为非“0”时，表示对时，表示对应的分区已被某作业占用。空闲分区可以用来装作业。应的分区已被某作业占用。空闲分区可以用来装作业。区号区号 分区大小分区大小 起始地址起始地址 标志位标志位0 32k 0k 11 8k 32k 12 16k 40k 03 32k 56k 1 4 64k 88k 0OS作业作

41、业A(6k)A(6k)作业B(28k)0 32k 40k56k 88k表4-2主存分配表图4.11内存分配示意图&等待进入主存的作业排成一个作业队列。当主存中有空闲的分区时，依次从作业队列中选择一个能装入该分区的作业。当所有的分区都已装有作业，则其他的作业暂时不能再装入，绝对不允许在同一分区中同时装入两个或两个以上的作业。已经装入主存的作业在获得处理机运行时，要限定它只能在所占的分区中执行。 当作业队列中有作业要装入主存时，存储管理可采用“顺序分配算法”进行主存空间的分配。 &顺序查看主存分配表，顺序查看主存分配表，找到一个标志为“0”的并且长度大于或等于欲装入作业的地址空间长度的分区，则把此

42、分区分配给该作业，相应表目的标志位改成作业名的标识；若找不到一个这样的空闲分区，则该作业暂时不能装入主存。 &主存空间的释放很简单主存空间的释放很简单, ,某作业执行结束后必须归还所占的分区，这时存储管理根据作业名查看主存分配表，找到相应的表目后，把其中的标志位重新置成“0”即可。 图图.12.124.4.地址转换地址转换 &固定分区管理方式下作业的地址转换常采用静态重固定分区管理方式下作业的地址转换常采用静态重定位技术。定位技术。 &物理地址物理地址= =分区始址分区始址+ +逻辑地址逻辑地址5.5.存储保护存储保护 固定分区管理方式下只考虑判断其物理地址即可。常采用“界限寄存器对”法。If

43、 下限地址下限地址=物理地址物理地址=上限地址上限地址Then 继续继续 Else 产生产生“越界中断越界中断” ” ，转越界中断的处理子程序，转越界中断的处理子程序 6. 6.固定分区的缺点固定分区的缺点碎片大，存在小作业占用大分区的情况。碎片大，存在小作业占用大分区的情况。不利于提高内存资不利于提高内存资源的利用率源的利用率 。可调入的作业大小受分区大小的严格限制。可调入的作业大小受分区大小的严格限制。 解决办法：解决办法：采用可变分区存储管理采用可变分区存储管理分区1 100 KB分区2 150 KB分区3 250 KB分区4 250 KB分区5 250 KB程序4 100 KB程序5

44、50 KB程序1 20 KB程序2 30 KB程序3 50 KB 图4.13内存分配示意图4.2.3 4.2.3 可变分区存储管理可变分区存储管理&为了改善固定分区分配给系统带来的内存碎片太大、空间为了改善固定分区分配给系统带来的内存碎片太大、空间浪费严重的缺陷，提出了动态分区分配，也叫做可变式分浪费严重的缺陷，提出了动态分区分配，也叫做可变式分区分配的策略，区分配的策略，&根据进程的实际需求动态地划分内存的分区方法。根据进程的实际需求动态地划分内存的分区方法。它是在它是在进程装入和处理过程中建立分区，并要进程装入和处理过程中建立分区，并要使分区的容量能正使分区的容量能正好适应进程的大小好适应

45、进程的大小。而。而整个内存分区数目随着进程数目的整个内存分区数目随着进程数目的变化而动态改变变化而动态改变，各个分区的大小随着各个进程的大小各，各个分区的大小随着各个进程的大小各有不同，所以称之为动态分区分配。有不同，所以称之为动态分区分配。&动态分区又称之为可变分区，动态分区又称之为可变分区，或变长分区模式，主要克服或变长分区模式，主要克服固定分区管理的固定分区管理的“内碎片内碎片”问题。问题。 OSP1P3OSP1P3OSP4例子：一计算机系统有例子：一计算机系统有2560KB内存，采用可变分区模式管内存，采用可变分区模式管理，理，OS占低地址的占低地址的400KB空间，用户内存为空间，用

46、户内存为2160KB。P1OSP1P2OSP1P2P3P2和固定分区相似，和固定分区相似，动态分区也可以采用表格的形式来管理动态分区也可以采用表格的形式来管理内存空间。内存空间。可用一张可用一张已分区表已分区表来表示被分配出去的分区，来表示被分配出去的分区，用一张用一张空闲分区（未分区）表空闲分区（未分区）表来表示空闲分区。在这种方来表示空闲分区。在这种方式下，由于分区个数不定，因而式下，由于分区个数不定，因而已分区表或空闲分区表应已分区表或空闲分区表应该有一定的冗余，该有一定的冗余，此时占用标志位表示已分区表中的表项此时占用标志位表示已分区表中的表项是否被使用，置是否被使用，置1 1表示被使

47、用，置表示被使用，置0 0表示空闲。表示空闲。 1.1.动态分区中的数据结构动态分区中的数据结构 为了节省内存空间，系统中的空闲分区也可为了节省内存空间，系统中的空闲分区也可采用空闲区链表采用空闲区链表的方法来管理。的方法来管理。利用空闲分区的前几个字节，记录此分区的利用空闲分区的前几个字节，记录此分区的长度、起始地址和下一个分区的起始地址（即链指针）。从长度、起始地址和下一个分区的起始地址（即链指针）。从而将所有的空闲区链接起来，即将所有的空闲区链接成一个而将所有的空闲区链接起来，即将所有的空闲区链接成一个链。链。空闲区链表不占用额外的存储空间，空闲区链表不占用额外的存储空间，因此采用这种方

48、法，因此采用这种方法，可以避免考虑空闲分区表的冗余问题。可以避免考虑空闲分区表的冗余问题。00 00 20k 20k 28k 30k 30k 45k 45k 60k 60k 80k 80k 140k 140k 图4.14 可变分区分配示意图 操操作作系系统统 分分区区1 1 作作业业A A长长度度为为1 10 0k k 分分区区2 2 作作业业B B长长度度为为1 15 5k k 分分区区3 3 作作业业C C长长度度为为1 15 5k k 分分区区4 4 作作业业D D长长度度为为2 20 0k k 分分区区5 5 空空闲闲 长长度度为为6 60 0k k 操操作作系系统统 分分区区1 1

49、作作业业E E长长度度为为8 8k k 分分区区2 2 作作业业B B长长度度为为1 15 5k k 分分区区3 3 空空闲闲 长长度度为为1 15 5k k 分分区区4 4 作作业业D D长长度度为为2 20 0k k 分分区区5 5 空空闲闲 长长度度为为6 60 0k k Freelist 图 4.15 可变存储中空闲区链表 28k 2k 45k 15k 80k 60k NULL 表 4-3 可变分区存储中已分区表 表 4-4 可变分区存储中空闲分区表 分区号 起始地址 长度 占用标志位 1 20k 8k 1 2 30k 15k 1 3 60k 20k 1 4 0 5 0 分区号 起始地

50、址 长度 占用标志位 1 28k 2k 1 2 45k 15k 1 3 80k 60k 1 4 0 5 0 图4.16 动态分区流程图空闲分区大于程序大小 ?查找空闲分区链空闲分区程序大小规定剩余大小?该空闲区分给申请程序从该分区划分出申请空间找完?YYNN无法分配Y修改分区说明表、空闲链返回N1) 1) 首次适应算法（首次适应算法（FF, First FitFF, First Fit） 空闲分区链或空闲分区表以地址递增的顺序链接空闲分区链或空闲分区表以地址递增的顺序链接，分配时从链首开始查找，找到第一个大小可以满足的分区为止，找到第一个大小可以满足的分区为止，从其中划分出所需空间分配给申请的

51、进程，剩余部分仍旧作为一个分区保留在空闲分区链中，否则给出无法分配的提示。 采用这种方法时，每次分配都需要从链首也就是低地址开始查找，所以低地址由于被划分的可能性比较大，容易形成多低地址由于被划分的可能性比较大，容易形成多个过小分区而难以利用，成为外部碎片个过小分区而难以利用，成为外部碎片（前面所描述的在每个分区内的“碎片”相应称为内部碎片）。同时这些小分区增加了查寻时的判断时间，降低了效率。2 2动态分区分配算动态分区分配算法法2) 循环首次适应算法循环首次适应算法 为了改变首次适应算法每次从链首开始查寻造成的缺陷，可以增加一个起始查寻指针，指向下一次开始查寻时的起始分区，在查寻过程中，该指

52、针向后移动，当移动到最后一个当移动到最后一个空闲分区后，重新回到链首。空闲分区后，重新回到链首。找到适当分区后，按首次适应算法的划分分区方式进行。这种方法可以使内存区分配比较平均，减少查寻次数，但又造成了缺少大空闲分区，使得大进程无法进入。 首次适应首次适应算法算法实现比较简单直接，易于释放时实现比较简单直接，易于释放时合并相邻空间分区。合并相邻空间分区。比较容易的满足大作业的需要。比较容易的满足大作业的需要。完成一次分配平均需要的搜索次数较大，影响了工完成一次分配平均需要的搜索次数较大，影响了工作效率。作效率。3) 最佳适应算法最佳适应算法评价：尽可能的保留了较大的空间。尽可能的保留了较大的

53、空间。 产生大量的不易被使用的很小的空闲区。产生大量的不易被使用的很小的空闲区。 该算法不一定是最佳的。该算法不一定是最佳的。空闲分区链按照分区容量递增的方式形成，分配时从链首开始查找，这样找到的第一个大小可以满足的分区肯定是与进程申请空间大小最接近，甚至是完全吻合的分区，而且平均查找次数为分区数的一半，也就是说它是“最佳适应”的。先使用小的空闲区，将大的空闲区留给大作业，所以它总是试图找出最接近实际需要的空闲区。 4) 最差适应算法目标：总是搜索整个链表以找到够用的最大的空闲区，使分目标：总是搜索整个链表以找到够用的最大的空闲区，使分裂出来的小空闲区比较大，因而可以继续使用。因此裂出来的小空

54、闲区比较大，因而可以继续使用。因此空闲分区链按照分区容量递减的方式形成，分配时从链首开始，若链首分区大小不满足，则可以肯定不存在能够满足要求的分区；否则对链首分区进行划分，剩余空间成为“碎片”的可能性肯定是最小的。评价：最差适应算法具有查找速度快，分区碎片少评价：最差适应算法具有查找速度快，分区碎片少，分割后产分割后产生的空闲区一般仍可以供以后分配使用。生的空闲区一般仍可以供以后分配使用。 工作一段时间后，不能满足大作业对空闲区的请求。工作一段时间后，不能满足大作业对空闲区的请求。 在这几种分配算法中，一般情况下，首次适应算法是最简单，而且是最快和最好的算法。循环首次适应算法比首次适应算法稍差

55、一些，而最佳适应算法虽然名字中有“最佳”，但实际上是性能最差的。但在某些应用情况下，上述比较结果会有所变化。起始地址 长度 标志位A L1 J1C L2 J2E L3 J3起始地址 长度 标志位B H1 1D H2 1C L2 1已分区表已分区表未分区表未分区表回收回收J2J2进进程程OSJ1J1J3J3J2J2ABCDEFL1H2H1L2L33.3.动态分区的回收动态分区的回收M1回收区M2回收M1空白区M2(a)M1回收区M2回收M1M2(b)M1回收区M2回收M1M2(c)M1回收区M2回收M1(d)(a) M1(a) M1、M2M2都非空都非空(b) M1(b) M1为空、为空、M2M

56、2非空非空(c) M1(c) M1为非空、为非空、M2M2空空(d) M1(d) M1、M2M2都为空都为空&回收内存空间，关键是修改两个表。回收内存空间，关键是修改两个表。图4.17 可变分区方式内存回收流程图在动态分区分配中，在动态分区分配中，消除消除了固定分区管理造成的了固定分区管理造成的“内碎片内碎片”，但是不可避但是不可避免的在内存空间造成免的在内存空间造成“外外碎片碎片”。多个无法利用的多个无法利用的小分区所形成的小分区所形成的“碎片碎片”是一种很大的资源浪费。是一种很大的资源浪费。如图（如图（a）所示，）所示，空闲分区空闲分区之和为之和为10 KB，但是无法，但是无法装入一个装入

57、一个8 KB的程序。的程序。 4.4.动态重定位分区分配动态重定位分区分配系统区程序A5 KB程序B3 KB程序C2 KB紧凑系统区程序A程序B程序C10 KB(a)(b) 为了解决类似问题，可以采用一种称为为了解决类似问题，可以采用一种称为“紧凑紧凑”的方法，的方法，通过移动程序将原来分散的空闲小分区拼接为一个大的分通过移动程序将原来分散的空闲小分区拼接为一个大的分区，就可以使某些比较大的进程进入，区，就可以使某些比较大的进程进入，如图（如图（b b）所示。一）所示。一般情况下，当某进程因为没有足够大的分区，而所有般情况下，当某进程因为没有足够大的分区，而所有“碎碎片片”之和又大于进程大小时

58、将进行之和又大于进程大小时将进行“紧凑紧凑”。&经过紧缩后的进程在内存中的位置发生了变化，经过紧缩后的进程在内存中的位置发生了变化，若不对程序和若不对程序和数据的地址进行修改，该进程就无法运行。要使其运行，必须数据的地址进行修改，该进程就无法运行。要使其运行，必须采用采用“动态重定位动态重定位”进行地址变换，于是称这种方案为动态重进行地址变换，于是称这种方案为动态重定位分区分配。定位分区分配。紧缩的时机：紧缩的时机： （1）一旦有归还的分区便进行紧缩，系统开销大。）一旦有归还的分区便进行紧缩，系统开销大。 （2）当发现内存不够用时）当发现内存不够用时.移动是有条件的移动是有条件的 图4.18在

59、分区分配方案中，地址映射都遵循“物理地址=分区始地址+逻辑地址”，固定分区分配与动态分区分配的分区始地址都来自于硬件“基址寄存器”，动态重定位分区分配的分区始地址来自于“重定位寄存器”。内存保护由“基址寄存器”和“限长寄存器”共同实现，也可以用一对下限寄存器和上限寄存器来实现，一旦超过限长，则发出越界中断信号。 分区分配方案的主要优点可归纳如下： 5.5.分区分配方案的评价分区分配方案的评价(1) 多道程序下的内存共享，改善了系统吞吐量，在内存利用率方面，从固定式分区到动态分区，再到动态重定位分区依次提高。 (2) 相对于后面介绍的存储管理方式，为实现分区分配所使用的数据结构占用的存储容量相对

60、较少，算法也相对简单。(3) 实现存储保护的措施也比较简单。 分区分配的主要缺点有：分区分配的主要缺点有： (1) 内存仍不能充分利用，除了动态重定位式分区内存仍不能充分利用，除了动态重定位式分区法外，都存在着严重的碎片问题。法外，都存在着严重的碎片问题。 (2) 不能实现对内存的扩充，因此进程的大小受到不能实现对内存的扩充，因此进程的大小受到内存可用空间的限制。内存可用空间的限制。 (3) 与单一连续分配一样，要求一个进程在执行之与单一连续分配一样，要求一个进程在执行之前必须全部装入内存，因此在内存中可能包含不会被使前必须全部装入内存，因此在内存中可能包含不会被使用的信息。用的信息。 (4)