第4章 内存管理

1、1北华大学北华大学.计算机科学技术学院计算机科学技术学院操作系统原理操作系统原理 课程课程 管管 理理 第第 4 章章操作系统原理操作系统原理 课程 第2张今天虽然主存价格已相当便宜，但主存容量仍然是计今天虽然主存价格已相当便宜，但主存容量仍然是计算机四大硬件资源中最关键而又最紧张的算机四大硬件资源中最关键而又最紧张的“瓶颈瓶颈”资源。资源。因此对主存的管理和有效使用仍然是今天操作系统十分重因此对主存的管理和有效使用仍然是今天操作系统十分重要的内容。要的内容。许多操作系统之间最明显的区别特征之一往往是所使许多操作系统之间最明显的区别特征之一往往是所使用的存储管理方法不同。如用的存储管理方法不同

2、。如OS/360-MFTOS/360-MFT采用采用固定分区固定分区存储存储管理技术，管理技术，OS/360-MTVOS/360-MTV是采用是采用可变分区可变分区存储管理技术，存储管理技术，OS/2OS/2，WindowsNT, WindowsNT, 是采用是采用虚拟存储虚拟存储管理技术。管理技术。主存储器管理技术可分为两大类：主存储器管理技术可分为两大类： 实存储器实存储器管理和管理和虚拟存储器虚拟存储器管理。管理。操作系统原理操作系统原理 课程 第3张本章目标本章目标熟悉三级存储器结构：熟悉三级存储器结构：CPU寄存器、内存、外存。寄存器、内存、外存。记住用户程序的主要处理阶段：编辑、编

3、译、链接、装入、记住用户程序的主要处理阶段：编辑、编译、链接、装入、运行。运行。理解存储器管理的功能（内存分配与回收、地址映射、内存理解存储器管理的功能（内存分配与回收、地址映射、内存保护与共享、虚拟存储）和虚拟存储器的基本特征（离散分保护与共享、虚拟存储）和虚拟存储器的基本特征（离散分配、多次性、对换性、虚拟性）。配、多次性、对换性、虚拟性）。牢固掌握概念：逻辑地址、物理地址、重定位、碎片、虚拟牢固掌握概念：逻辑地址、物理地址、重定位、碎片、虚拟存储器、抖动、程序局部性原理等。存储器、抖动、程序局部性原理等。掌握分区、分页、分段存储管理技术的实现思想，如何实现掌握分区、分页、分段存储管理技术

4、的实现思想，如何实现从逻辑地址到物理地址的转换。从逻辑地址到物理地址的转换。掌握虚拟页式存储中的页面置换算法：先进先出法掌握虚拟页式存储中的页面置换算法：先进先出法（FIFO）、最佳置换法（）、最佳置换法（OPT）、最近最少使用法（）、最近最少使用法（LRU） 操作系统原理操作系统原理 课程 第4张存存储储器器管管理理 本章结构本章结构基础知识、程序的装入和链接基础知识、程序的装入和链接连续分配方式连续分配方式分页存储管理方式分页存储管理方式分段存储管理方式分段存储管理方式段页式存储管理方式段页式存储管理方式固定分区固定分区动态分区动态分区基本页式基本页式虚拟页式虚拟页式基本段式基本段式虚拟段

5、式虚拟段式操作系统原理操作系统原理 课程 第5张4.1 存储器管理的基础知识存储器管理的基础知识 一一. .存储器的层次结构：存储器的层次结构：（ 过去常见为三级结构划分，教材中为较细的划分过去常见为三级结构划分，教材中为较细的划分） CPU寄存器寄存器 用户程序在运行时应存放在用户程序在运行时应存放在中，以便处理机访问。但是由中，以便处理机访问。但是由于主存容量有限。所以把那些不马上使用的程序、数据放在外部于主存容量有限。所以把那些不马上使用的程序、数据放在外部存储器中，当用到时再把它们读入主存。存储器中，当用到时再把它们读入主存。如如IBM的缓存最大传输速度为的缓存最大传输速度为每双字每双

6、字120225毫微秒毫微秒，主存的传输速度，主存的传输速度每字每字1微秒微秒。操作系统原理操作系统原理 课程 第6张1.CPU寄存器寄存器： 访问速度最快，可与访问速度最快，可与CPU协调工作、少量的、昂贵，用于加快协调工作、少量的、昂贵，用于加快存储器的访问速度，如存放操作数或作为地址寄存器。存储器的访问速度，如存放操作数或作为地址寄存器。 2.主主（内内）存存RAM： 处理机能直接访问的存储器处理机能直接访问的存储器。用来存放系统和用户的程序和数。用来存放系统和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。失。

7、 3.辅存辅存（磁盘磁盘）： 处理机不能直接访问的存储器。用来存放用户的各种信息，存处理机不能直接访问的存储器。用来存放用户的各种信息，存取速度相对内存而言要慢得多，但它可用来长期保存用户信息。取速度相对内存而言要慢得多，但它可用来长期保存用户信息。4.1 存储器管理的基础知识存储器管理的基础知识 操作系统原理操作系统原理 课程 第7张. .教材中的教材中的多级多级层次结构：层次结构：寄存器寄存器高速缓存高速缓存主主 存存磁盘缓存磁盘缓存磁磁 盘盘 可移动存储介质可移动存储介质4.1 存储器管理的基础知识存储器管理的基础知识 操作系统原理操作系统原理 课程 第8张1： 物理地址是主存的真实地址

8、物理地址是主存的真实地址 ，是存储控制部件能够识别的主存，是存储控制部件能够识别的主存单元编号。把内存分成若干个大小相等的存储单元，每个单元给单元编号。把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为一个编号，这个编号称为内存地址内存地址（物理地址物理地址、绝对地址绝对地址、实地实地址址），存储单元占），存储单元占8位，称作字节（位，称作字节（byte）。）。2.： 物理地址的集合称为物理地址空间（主存地址空间），它是一物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。个一维的线性空间。 内存内存014.1 存储器管理的基础知识存储器管理的基础知识 操

9、作系统原理操作系统原理 课程 第9张1.： 用户编程序时所用的地址（或称用户编程序时所用的地址（或称逻辑地址逻辑地址 、相对地址相对地址、虚地址虚地址 ），），是指相对于某个基准量编址时所使用的地址，常用于程序编写和是指相对于某个基准量编址时所使用的地址，常用于程序编写和编译过程中。基本单位可与内存的基本单位相同，也可以不相同。编译过程中。基本单位可与内存的基本单位相同，也可以不相同。（用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的（用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为形式，其首地址为0 0，其余指令中的地址都相对于首地址而编址

10、。），其余指令中的地址都相对于首地址而编址。）2.（逻辑地址空间、虚地址空间）（逻辑地址空间、虚地址空间）： 用户的程序地址的集合称为逻辑地址空间，它的编址总是从用户的程序地址的集合称为逻辑地址空间，它的编址总是从0开开始的，可以是一维线性空间，也可以是多维空间。始的，可以是一维线性空间，也可以是多维空间。 4.1 存储器管理的基础知识存储器管理的基础知识 虚地址空间虚地址空间010124.2 程序的装入和链接程序的装入和链接 程序和数据程序和数据装入内存装入内存创建进程创建进程运行程序运行程序源程序源程序转换为可执行文件转换为可执行文件编译编译 将源代码编译成若干将源代码编译成若干obj模块

11、模块;链接链接 由链接程序将由链接程序将obj模块链接在一起模块链接在一起,形成装入模块形成装入模块;装入装入 装入程序将装入模块装入内存装入程序将装入模块装入内存如何将一个用户源程序变为一个可在内存中执行的程序？如何将一个用户源程序变为一个可在内存中执行的程序？源程序源程序目标模块目标模块装入程序装入程序装入模块装入模块编译编译链接链接装入装入4.2 程序的装入和链接程序的装入和链接 库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存操作系统原理操作系统原理 课程 第12张4.2.1 程序的装入程序的装入1. 绝对装入方式绝对装入方式(Absolute Loading M

12、ode) 程序中所使用的程序中所使用的绝对地址绝对地址，既可在编译或汇编时给出，既可在编译或汇编时给出， 也可由程序员直接赋予。也可由程序员直接赋予。 但在由程序员直接给出绝对地址时，但在由程序员直接给出绝对地址时， 不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。址转换为绝对地址。 由于程序中的逻辑地址

13、与实际内存地址完全相同，故不须对由于程序中的逻辑地址与实际内存地址完全相同，故不须对程序和数据地址进行修改。但这种情况很少，一般只适于程序和数据地址进行修改。但这种情况很少，一般只适于单道单道环境环境。操作系统原理操作系统原理 课程 第13张2. 可重定位装入方式可重定位装入方式4.2.1 程序的装入程序的装入 由装入程序由装入程序根据内存当时的实际使用情况根据内存当时的实际使用情况，将装入模块装，将装入模块装入到入到内存的适当地方内存的适当地方。由于编译程序不能预知所编译的目标。由于编译程序不能预知所编译的目标模块在内存的什么位置，因此，会使装入模块中的所有模块在内存的什么位置，因此，会使装

14、入模块中的所有逻辑逻辑地址与实际地址不同。地址与实际地址不同。 在装入时，将根据实际装入的起始位置，相应调整所有的相在装入时，将根据实际装入的起始位置，相应调整所有的相对地址。在装入时对目标程序中的指令和数据地址的修改过程对地址。在装入时对目标程序中的指令和数据地址的修改过程称为称为重定位重定位。又因为地址交换只是在装入时一次完成，以后不。又因为地址交换只是在装入时一次完成，以后不在改变，故称为在改变，故称为静态重定位静态重定位。 图图 4-2重定位方式重定位方式作业装入内存时的情况作业装入内存时的情况 LOAD 1,2500365LOAD 1,250036510000110001250015

15、0005000250010000作业地址空间内存空间操作系统原理操作系统原理 课程 第15张3. 动态运行时装入方式动态运行时装入方式 (Denamle Run-time Loading) 动态运行时的装入程序，在把装入模块装入内存后，并动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到种地址转换推迟到程序真正要执行时程序真正要执行时才进行。因此，才进行。因此， 装入内装入内存后的所有地址都仍是相对地址。存后的所有地址都仍是相对地址。 4.2.1 程序的装入程序的装入为使地址转

16、换不影响指令的运行速度，需要为使地址转换不影响指令的运行速度，需要重定位寄存器重定位寄存器支持。支持。操作系统原理操作系统原理 课程 第16张4.2.2 程序的链接程序的链接 1. 静态链接方式静态链接方式(Static Linking) 模块 ACALL B；Return；0L1模块 BCALL C；Return；0M1模块 CReturn；0N10模块 AJSR“L”Return；L1模块 BJSR“LM”Return；LLM1LMLMN1模块 CReturn；(a) 目标模块(b) 装入模块操作系统原理操作系统原理 课程 第17张 在将这几个目标模块装配成一个装入模块时，须解在将这几个目

17、标模块装配成一个装入模块时，须解决以下两个问题：决以下两个问题： (1) 对相对地址进行修改对相对地址进行修改。 (2) 变换外部调用符号变换外部调用符号。 4.2.2 程序的链接程序的链接 操作系统原理操作系统原理 课程 第18张2. 装入时动态链接装入时动态链接(Loadtime Dynamic Linking) 装入时动态链接方式有以下优点：装入时动态链接方式有以下优点： （1） 便于修改和更新便于修改和更新。 （2）便于实现对目标模块的共享便于实现对目标模块的共享。 4.2.2 程序的链接程序的链接 在装入目标模块时，若在装入目标模块时，若发现一个外部模块调用事件发现一个外部模块调用事

18、件，由装入程序找出相应的模块。由装入程序找出相应的模块。 操作系统原理操作系统原理 课程 第19张 近几年流行起来的运行时动态链接方式，是对上述在近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这种链接方式是将装入时链接方式的一种改进。这种链接方式是将对某些模对某些模块的链接推迟到执行时才执行块的链接推迟到执行时才执行，亦即，在执行过程中，当，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由发现一个被调用模块尚未装入内存时，立即由OS去找到该去找到该模块并将之装入内存，模块并将之装入内存， 把它链接到调用者模块上。凡在执把它链接到调用者模块上。凡在执行过程

19、中未被用到的目标模块，都不会被调入内存和被链行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。可节省大量的内存空间。 4.2.2 程序的链接程序的链接 操作系统原理操作系统原理 课程 第20张1.地址映射地址映射将程序地址空间中使用的将程序地址空间中使用的逻辑地址逻辑地址变换成变换成主存中的地址主存中的地址的过程的过程称为称为地址映射地址映射。有时也称为。有时也称为地址重定位地址重定位 。补补：存储管理的功能存储管理的功能 2.主存分配与回收主存分配与回收按照一定的算法把某

20、一空闲的主存区分配给作业或进程。按照一定的算法把某一空闲的主存区分配给作业或进程。在多道程序设计的环境中，内存分配的功能包括：在多道程序设计的环境中，内存分配的功能包括：制定分配策略制定分配策略、构造分配用的数据结构构造分配用的数据结构、响应系统的内存分配响应系统的内存分配的请求的请求和和回收系统释放的内存区回收系统释放的内存区。操作系统原理操作系统原理 课程 第21张内存管理策略内存管理策略有三种有三种:1）放置策略放置策略 决定内存中放置信息的区域（或位置），即如何在若干个决定内存中放置信息的区域（或位置），即如何在若干个空闲区中选择一个或几个空闲区的原则；空闲区中选择一个或几个空闲区的原

21、则；2）调入策略调入策略 决定信息装入内存的时机，有两种：在用户请求时调入，称决定信息装入内存的时机，有两种：在用户请求时调入，称为为请调请调；根据某种算法，确定系统将要使用的信息，并在执行；根据某种算法，确定系统将要使用的信息，并在执行前预先调入内存，称为前预先调入内存，称为预调预调 ；3）淘汰策略淘汰策略 当内存不足时，决定将某些信息调出内存的策略当内存不足时，决定将某些信息调出内存的策略 。操作系统原理操作系统原理 课程 第22张3.存储保护与共享存储保护与共享保证用户程序保证用户程序(或进程映象或进程映象)在各自存储区域内操作，互不干扰。在各自存储区域内操作，互不干扰。补：补：存储管理

22、的功能存储管理的功能 常用的存储保护有两种常用的存储保护有两种:上下界保护上下界保护下界寄存器下界寄存器: 存放程序装入内存后的开始地址（首址）存放程序装入内存后的开始地址（首址）上界寄存器上界寄存器: 存放程序装入内存后的末地址存放程序装入内存后的末地址判别式：判别式： 下界寄存器下界寄存器 物理地址物理地址 上界寄存器上界寄存器基址、限长寄存器保护基址、限长寄存器保护基址寄存器基址寄存器: 存放程序装入内存后的开始地址（首址）存放程序装入内存后的开始地址（首址）限长寄存器限长寄存器: 存放限制访问的最大相对长度存放限制访问的最大相对长度判别式：判别式：基址寄存器基址寄存器 物理地址物理地址

23、 基址寄存器基址寄存器+限长寄存器限长寄存器操作系统原理操作系统原理 课程 第23张1）常规存储器管理方式的特征常规存储器管理方式的特征 一次性。一次性。 (2) 驻留性。驻留性。 4.提供虚拟存储技术提供虚拟存储技术补：补：存储管理的功能存储管理的功能 早在早在1968年，年， Denning.P就曾指出：就曾指出： (1) 程序执行时，程序执行时， 除了少部分的转移和过程调用指令外，除了少部分的转移和过程调用指令外， 在大多数情况在大多数情况下仍是顺序执行的。下仍是顺序执行的。 (2) 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，过程调用将会使程序的执行轨迹由一部分区域转至另

24、一部分区域， 但经研究看出，过程调用的深度在大多数情况下都不超过但经研究看出，过程调用的深度在大多数情况下都不超过5。 (3) 程序中存在许多循环结构，程序中存在许多循环结构， 这些虽然只由少数指令构成，这些虽然只由少数指令构成， 但是它们但是它们将多次执行。将多次执行。 (4) 程序中还包括许多对数据结构的处理，程序中还包括许多对数据结构的处理， 如对数组进行操作，如对数组进行操作， 它们往它们往往都局限于很小的范围内。往都局限于很小的范围内。 2）局部性原理局部性原理 操作系统原理操作系统原理 课程 第24张 (1) 时间局限性时间局限性。如果程序中的某条指令一旦执行，。如果程序中的某条指

25、令一旦执行， 则不久以则不久以后该指令可能再次执行；如果某数据被访问过，后该指令可能再次执行；如果某数据被访问过， 则不久以后该则不久以后该数据可能再次被访问。产生时间局限性的典型原因，是由于在数据可能再次被访问。产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。程序中存在着大量的循环操作。 (2) 空间局限性空间局限性。一旦程序访问了某个存储单元，在不久之后，。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺地址，可能集中在一定

26、的范围之内，其典型情况便是程序的顺序执行。序执行。 局限性又表现在下述两个方面：局限性又表现在下述两个方面：操作系统原理操作系统原理 课程 第25张 使用户程序的大小和结构使用户程序的大小和结构不受主存容量和结构的限制不受主存容量和结构的限制，即使在，即使在用户程序比实际主存容量还要大的情况下，程序也能正确运行。用户程序比实际主存容量还要大的情况下，程序也能正确运行。问题的提出问题的提出物理存储器物理存储器的结构是个的结构是个一维一维的线性空间，容量是的线性空间，容量是有限有限的。的。用户程序用户程序结构：结构：一维空间一维空间： 一个用户程序就是一个程序，并且程序和数据是不分离的；一个用户程

27、序就是一个程序，并且程序和数据是不分离的；二维空间二维空间： 程序由主程序和若干个子程序（或函数）组成，并且程序程序由主程序和若干个子程序（或函数）组成，并且程序 与数据是分离的；与数据是分离的； n n维空间维空间： 即一个大型程序，由一个主模块和多个子模块组成，其中，即一个大型程序，由一个主模块和多个子模块组成，其中，各各 子模块又由主程序和子程序（或函数）组成。子模块又由主程序和子程序（或函数）组成。 用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。得多。 虚拟存储技术虚拟存储技术操作系统原理操作系统原

28、理 课程 第26张 虚拟存储概念虚拟存储概念 为用户提供一种不受物理存储器结构和容量限制的存储器的技术为用户提供一种不受物理存储器结构和容量限制的存储器的技术称为虚拟存储技术。称为虚拟存储技术。 所谓所谓虚拟存储器虚拟存储器，是指具有，是指具有请求调入请求调入功能和功能和置换置换功能，能从逻辑功能，能从逻辑上对内存容量加以扩充的一种存储器系统，其逻辑容量由内、外存上对内存容量加以扩充的一种存储器系统，其逻辑容量由内、外存容量之和来决定，其运行速度接近内存，成本接近外存。容量之和来决定，其运行速度接近内存，成本接近外存。 虚拟存储器的特征：虚拟存储器的特征： 多次性多次性对换性对换性虚拟性虚拟性

29、 0. 离散分配离散分配 虚拟存储技术虚拟存储技术操作系统原理操作系统原理 课程 第27张回顾：回顾：4.3 连续分配方式连续分配方式1.存储管理的基本功能：存储管理的基本功能：内存分配与回收内存分配与回收地址映射地址映射内存保护与共享内存保护与共享虚拟存储虚拟存储（内存扩充内存扩充）2.程序的虚拟地址空间（程序的虚拟地址空间（逻辑地址逻辑地址） 内存的物理地址空间（内存的物理地址空间（物理地址物理地址）操作系统原理操作系统原理 课程 第28张4.3 连续分配方式连续分配方式4.3.1 单一连续分配单一连续分配 分区存储管理分区存储管理 OS系统区系统区占用区占用区空闲区空闲区 用用 户户 区

30、区 低址低址高址高址用于用于单用户单用户、单任务单任务的的OSOS中中 操作系统原理操作系统原理 课程 第29张4.3.2 固定分区分配固定分区分配 2. 划分分区的方法划分分区的方法： 分区大小分区大小相等相等 4.3 连续分配方式连续分配方式1.原理原理：OS区用用户户区区OS区用用户户区区(2) 分区大小分区大小不等不等分区分区1分区分区2分区分区3分区分区4分区分区2分区分区1分区分区3分区分区4操作系统原理操作系统原理 课程 第30张3.3.涉及的数据结构涉及的数据结构分区说明表分区说明表（内存分配表）（内存分配表） 4.3.2 固定分区分配固定分区分配 4.3 连续分配方式连续分配

31、方式操作系统原理操作系统原理 课程 第31张3.3.内存分配内存分配4.3.2 固定分区分配固定分区分配 4.3 连续分配方式连续分配方式 由由内存分配程序内存分配程序对对分区说明表分区说明表进行检索，如果有一个空闲区符进行检索，如果有一个空闲区符合用户要求的大小合用户要求的大小, 则分配给进程。即则分配给进程。即将将写入写入PCB，并，并置该分区的状态为已分置该分区的状态为已分“1”。4.4.内存回收内存回收 将对应分区的状态设为空将对应分区的状态设为空闲，即闲，即“0”。操作系统原理操作系统原理 课程 第32张5.5.地址转换地址转换4.3.2 固定分区分配固定分区分配 4.3 连续分配方

32、式连续分配方式 系统采用系统采用“技术，将作业装入所分配的分区中，技术，将作业装入所分配的分区中，且在执行过程中不会被改变存放区域，由装入程序按如下计算得且在执行过程中不会被改变存放区域，由装入程序按如下计算得出物理地址。出物理地址。操作系统原理操作系统原理 课程 第33张6.6.存储保护存储保护4.3.2 固定分区分配固定分区分配 4.3 连续分配方式连续分配方式常采用常采用“基址、限长寄存器保护法基址、限长寄存器保护法”操作系统原理操作系统原理 课程 第34张4.3.3 动态分区分配动态分区分配 4.3 连续分配方式连续分配方式1）内存空间划分内存空间划分： 将内存空间除将内存空间除OS区

33、外，区外，。当一个作。当一个作业装入时，根据作业的需求和内存空间的使用情况来决定是否分业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。（若有足够的空间，则按需要配。（若有足够的空间，则按需要一部分分区给该进程；否一部分分区给该进程；否则令其等待主存空间）则令其等待主存空间）分区，分区，。1.原理原理：2）虚拟空间划分：虚拟空间划分：空间空间 3）分配原则：分配原则： 寻找一个满足大小的空闲区，按程序大小分割后，程序寻找一个满足大小的空闲区，按程序大小分割后，程序，。操作系统原理操作系统原理 课程 第35张4.3.3 动态分区分配动态分区分配 2. 分配中的数据结构分配中的数据结构

34、(1) 空闲分区表空闲分区表前向指针N20N个字节可用后向指针N20区号区号长度长度始址始址(2) 空闲分区链空闲分区链 (3) 资源请求表资源请求表 进程号进程号请求内存长度请求内存长度P113kP220k分区号分区号 分区大小分区大小 后继指针后继指针分区号分区号 分区大小分区大小 后继指针后继指针操作系统原理操作系统原理 课程 第36张3. 内存分配适应（配）算法内存分配适应（配）算法4.3.3 动态分区分配动态分区分配 适适应应法法适适应应法法适适应应法法适适应应法法适适应应法法操作系统原理操作系统原理 课程 第37张3. 内存分配适应（配）算法内存分配适应（配）算法(1) 首次适应算

35、法首次适应算法FF最先适配法最先适配法 4.3.3 动态分区分配动态分区分配 (2) 最佳适应算法最佳适应算法BF 当接到内存申请时，查空闲块表，找到当接到内存申请时，查空闲块表，找到起始地址最小起始地址最小的不小于请求的的不小于请求的空块，将其分割并分配。该算法要求空闲块空块，将其分割并分配。该算法要求空闲块按起始地址按起始地址递增递增排序排序。 评价评价：简单，倾向于优先利用内存简单，倾向于优先利用内存低址低址部分的空闲区，后期查找低速。部分的空闲区，后期查找低速。 当接到内存申请时，在空闲块表中找到一个不小于请求的当接到内存申请时，在空闲块表中找到一个不小于请求的最小空闲块最小空闲块进进

36、行行 分配。该算法要求空闲块分配。该算法要求空闲块按长度递增排序按长度递增排序。评价评价：用最小空间满足要求用最小空间满足要求 ，避免，避免“大材小用大材小用”，但会存在切割后无法，但会存在切割后无法再利用的再利用的“碎片碎片”。操作系统原理操作系统原理 课程 第38张3. 内存分配适应（配）算法内存分配适应（配）算法(3) 最差适应算法最差适应算法WF4.3.3 动态分区分配动态分区分配 (4) 循环首次适应算法循环首次适应算法NF 当接到内存申请时，在空闲块表中找到一个不小于请求的当接到内存申请时，在空闲块表中找到一个不小于请求的最大空闲块最大空闲块进进行分配。该算法要求空闲块行分配。该算

37、法要求空闲块按长度按长度递减递减排序排序。评价评价：当分割后空闲块仍为较大空块，可再次利用；但同时会造成无大当分割后空闲块仍为较大空块，可再次利用；但同时会造成无大 的空闲区情况。的空闲区情况。 首次适应法的改进，区别在于搜索时不是每次都从链首开始，而是从上首次适应法的改进，区别在于搜索时不是每次都从链首开始，而是从上次找到的下一个空闲区开始查找。需设置一个寻查指针，用以指示下一次次找到的下一个空闲区开始查找。需设置一个寻查指针，用以指示下一次查询的分区。查询的分区。(5) 快速适应算法快速适应算法QF 将空闲分区按容量大小分类，相同容量空闲分区单独成一个链表，并设将空闲分区按容量大小分类，相

38、同容量空闲分区单独成一个链表，并设立管理索引表，索引表每一项对应一类链表，并记录每类空闲链的指针。立管理索引表，索引表每一项对应一类链表，并记录每类空闲链的指针。操作系统原理操作系统原理 课程 第39张3.内存分配分配过程内存分配分配过程 从头开始查表检索完否？m.size u.size?m.size u.sizesize?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN操作系统原理操作系统原理 课程 第40张F1回收区4.内存的回收内存的回收4.3.3 动态分区分配动态分区分配 视情况进行释放区与其前、后空闲空间

39、的视情况进行释放区与其前、后空闲空间的合并合并 a) 回收区回收区F的前一个区的前一个区F1也为空闲区。也为空闲区。F1回收区FF1b) 回收区回收区F的后一个区的后一个区F2也为空闲区。也为空闲区。F2回收区FF2回收区FF2“二合一二合一”不必新增空闲区表项，只修改不必新增空闲区表项，只修改F1即可。即可。 F1的大小为的大小为F1和和F之和之和 其余分量不变其余分量不变“二合一二合一”不必新增空闲区表项，只修改不必新增空闲区表项，只修改F2即可。即可。将将F的首地址作为新空闲区的首地址的首地址作为新空闲区的首地址新区的大小为新区的大小为F2和和F之和之和 其余分量不变其余分量不变操作系统

40、原理操作系统原理 课程 第41张4.内存的回收内存的回收4.3.3 动态分区分配动态分区分配 c) 回收区回收区F的前后两个区的前后两个区F1、F2都为空闲区。都为空闲区。b) 回收区回收区F的前后两个区都不是空闲区。的前后两个区都不是空闲区。回收区FF1回收区FF2F1回收区FF2F1回收区FF“三合一三合一”使用使用F1的表项，删除的表项，删除F2的表项。的表项。F1的大小为的大小为F1、F和和F2之和之和F1后继指针改为后继指针改为F2的后继指针的后继指针新增空闲区表项，新增空闲区表项，填写空闲区首地址和大小，填写空闲区首地址和大小，并插入到空闲链的适当位置并插入到空闲链的适当位置1.1

41、.空闲区个数变化？空闲区个数变化？2.2.碎片问题？碎片问题？操作系统原理操作系统原理 课程 第42张 通过在内存移动程序，将所有小的空闲区域合并为大的空通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域。（紧缩技术，紧致技术，浮动技术，搬家技术）闲区域。（紧缩技术，紧致技术，浮动技术，搬家技术） 碎片问题的解决碎片问题的解决紧凑技术紧凑技术碎片问题：碎片问题： 经过一段时间的分配回收后，内存中存在很多很小的空闲经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块

42、被称为分配要求。这些空闲块被称为碎片碎片（内内、外外）。）。 问题问题：开销大；移动时机：开销大；移动时机有关碎片有关碎片操作系统原理操作系统原理 课程 第43张4.3.6 可重定位分区分配可重定位分区分配 1. 动态重定位的引入动态重定位的引入 用户程序用户程序1用户程序用户程序6用户程序用户程序310KB30KB14KB用户程序用户程序926KBa)紧凑前紧凑前用户程序用户程序1用户程序用户程序6用户程序用户程序3用户程序用户程序980KBb)紧凑后紧凑后操作系统原理操作系统原理 课程 第44张2. 动态重定位的实现动态重定位的实现 “设置一个设置一个重定位寄存器重定位寄存器，存放内存的初

43、始地址，存放内存的初始地址 ” LOAD1,25003650100250050002500相对地址10000重定位寄存器LOAD1,250036510000101001250015000作业J处理机一侧 存储器一侧主存4.3.6 可重定位分区分配可重定位分区分配 操作系统原理操作系统原理 课程 第45张3. 动态重定位分区分配算法动态重定位分区分配算法 请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否4.3.6 可重定位分区分配

44、可重定位分区分配 操作系统原理操作系统原理 课程 第46张4.3.7 覆盖与对换技术覆盖与对换技术1. 覆盖技术覆盖技术 它是基于这样一种思想提出来的，即一个程序并不需要一开它是基于这样一种思想提出来的，即一个程序并不需要一开始就把它的全部指令和数据都装入内存后再执行。始就把它的全部指令和数据都装入内存后再执行。 覆盖是指一个作业的若干程序段，或几个作业的某些部分共覆盖是指一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间。享某一个存储空间。把程序划分为若干个功能上相对独立的程把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共序段，按照其自身的

45、逻辑结构将那些不会同时执行的程序段共享同一块内存区域。享同一块内存区域。操作系统原理操作系统原理 课程 第47张4.3.7 覆盖与对换技术覆盖与对换技术1. 覆盖技术覆盖技术 程序段先保存在磁盘上，当有关程序段的先头部分执行结束，程序段先保存在磁盘上，当有关程序段的先头部分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存把后续程序段调入内存，覆盖前面的程序段（内存“扩大扩大”了）。了）。 一般要求作业各模块之间有明确的调用结构，程序员要向系一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由由操作系统完成自动覆盖。统指明覆盖结构，然后由由操作系统完成自动覆盖。 缺点

46、缺点：对用户不透明，增加了用户负担。：对用户不透明，增加了用户负担。操作系统原理操作系统原理 课程 第48张4.3.7 覆盖与对换技术覆盖与对换技术2. 对换对换 所谓所谓“对换对换”， 是指把是指把不能运行的进程或者不能运行的进程或者暂时不用的程序和数据，暂时不用的程序和数据，上，以便腾出足够的内上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和存空间，再把已具备运行条件的进程或进程所需要的程序和数据，数据，。对换是提高内存利用率的有效措施。对换是提高内存利用率的有效措施。 操作系统原理操作系统原理 课程 第49张 二者之比较二者之比较 与覆盖技术相比，交换技术不要求用

47、户给出程序段之间与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构。而且，交换发生在进程或作业之间，而的逻辑覆盖结构。而且，交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与覆盖段无关的程序段。与覆盖段无关的程序段。4.3.7 覆盖与对换技术覆盖与对换技术操作系统原理操作系统原理 课程 第50张4.7 请求分页存储管理请求分页存储管理 虚拟页式管理虚拟页式管理引入引入： 1. 常规存储器管理方式常规存储器管理方式(实模式实模式)的特征的特征 一次性。一次性。 (2) 驻留性。驻留性。 (1) 间局限性间

48、局限性(2) 间局限性间局限性2.局部性原理局部性原理操作系统原理操作系统原理 课程 第51张3. 虚拟存储器虚拟存储器 是指具有是指具有请求调入请求调入功能和功能和置换置换功能，功能， 能能从逻辑上对内存容量加以从逻辑上对内存容量加以扩充扩充的一种存储器系统。其逻辑容量由的一种存储器系统。其逻辑容量由内存容量和外存容量之和内存容量和外存容量之和所决所决定，其运行定，其运行速度接近于内存速度接近于内存速度，而每位的速度，而每位的成本却又接近于外存成本却又接近于外存。引入引入： 4.7 请求分页存储管理请求分页存储管理4. 实现页式虚拟存储的硬件支持实现页式虚拟存储的硬件支持 请求分页的页表机制

49、请求分页的页表机制：它是在纯分页的页表机制上：它是在纯分页的页表机制上而形成而形成的，作为请求分页的数据结构。的，作为请求分页的数据结构。 缺页中断机构缺页中断机构：即每当用户程序要访问的页面尚未调入内存时便产生：即每当用户程序要访问的页面尚未调入内存时便产生一缺页中断，以请求一缺页中断，以请求OS将所缺的页调入内存。将所缺的页调入内存。 地址变换机构地址变换机构： 它同样是在纯分页地址变换机构的基础上发展形成它同样是在纯分页地址变换机构的基础上发展形成的的操作系统原理操作系统原理 课程 第52张4.7.1 基本工作原理基本工作原理 在进程开始运行之前，在进程开始运行之前，不是装入全部页面不是

50、装入全部页面，而是装入一个，而是装入一个或零个页面，之后或零个页面，之后根据根据进程运行的进程运行的需要需要，动态装入动态装入其它其它页面页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰淘汰某个页面，以便装入新的页面。某个页面，以便装入新的页面。 根据页面调入的时机，又分为根据页面调入的时机，又分为请请求求调入调入页式管理和页式管理和预调入预调入页页式管理。式管理。4.7 请求分页存储管理请求分页存储管理操作系统原理操作系统原理 课程 第53张4.7.2 请求分页存储的硬件机制请求分页存储的硬件机制4.7 请求分页存储管理请

51、求分页存储管理状态位状态位P：（：（驻留位驻留位、中断位中断位）表示该页是在内存还是在外存）表示该页是在内存还是在外存访问位访问位A：记录本页在一段时间内被访问的次数，以便根据访问：记录本页在一段时间内被访问的次数，以便根据访问 位来决定淘汰哪页（由不同的算法决定）位来决定淘汰哪页（由不同的算法决定）修改位修改位M：查看此页是否在内存中被修改过：查看此页是否在内存中被修改过外存地址外存地址：用于指出该页在外存中的地址，供调入时参考：用于指出该页在外存中的地址，供调入时参考 1.页表机制扩充页表页表机制扩充页表操作系统原理操作系统原理 课程 第54张2.缺页中断机构缺页中断机构 在地址映射过程中

52、，在页表中发现所要访问的页在地址映射过程中，在页表中发现所要访问的页不在内存不在内存，则则产生缺页中断产生缺页中断。操作系统接到此中断信号后，就调出。操作系统接到此中断信号后，就调出缺页中缺页中断处理程序断处理程序，根据页表中给出的外存地址，将该页，根据页表中给出的外存地址，将该页调入内存调入内存，使作业继续运行下去。使作业继续运行下去。 如果内存中如果内存中有空闲块有空闲块，则分配一页，将新调入页，则分配一页，将新调入页装入装入内存，内存，并修改页表中相应页表项目的驻留位及相应的内存块号。并修改页表中相应页表项目的驻留位及相应的内存块号。 若此时内存中若此时内存中没有空闲块没有空闲块，则要，

53、则要淘汰某页淘汰某页，若该页在内存，若该页在内存期间被修改过，则要将其写回外存期间被修改过，则要将其写回外存 。4.7 请求分页存储管理请求分页存储管理4.7.2 请求分页存储的硬件机制请求分页存储的硬件机制操作系统原理操作系统原理 课程 第55张涉涉及及6次次缺缺页页中中断断的的指指令令 页面B：A：654321指令copy ATO B操作系统原理操作系统原理 课程 第56张3.地地址址变变换换机机构构 缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU

54、检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是请求分页中的地址变换过程请求分页中的地址变换过程 操作系统原理操作系统原理 课程 第57张4.7.3 内存分配策略和分配算法内存分配策略和分配算法 1. 最小物理块数的确定最小物理块数的确定 是指能是指能保证进程正常运行所需的最小物理块数保证进程正常运行所需的最小物理块数。当系统为。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程分配的物理块数少于此值时，进程将无法运行。 进程应获得的最少物理块数与计算机的硬件结构有关，取决进程应获得的最

55、少物理块数与计算机的硬件结构有关，取决于指令的格式、于指令的格式、 功能和寻址方式。功能和寻址方式。4.7 请求分页存储管理请求分页存储管理操作系统原理操作系统原理 课程 第58张2. 物理块的分配策略物理块的分配策略 在请求分页系统中，可采取两种内存分配策略，即固定和可在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，变分配策略。在进行置换时， 也可采取两种策略，即全局置换也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。和局部置换。于是可组合出以下三种适用的策略。 1) 固定固定分配分配局部局部置换置换(Fixed Allocation,

56、Local Replacement) 2) 可变可变分配分配全局全局置换置换(Variable Allocation, Global Replacement) 3) 可变可变分配分配局部局部置换置换(Variable Allocation, Local Replacemen 4.7.3 内存分配策略和分配算法内存分配策略和分配算法 操作系统原理操作系统原理 课程 第59张3. 物理块分配算法物理块分配算法 1) 平均分配算法平均分配算法:这种方式貌似公平，但实际上是不公平的，因这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。为它未考虑到各进程本身的大小。4.7.3 内存分

57、配策略和分配算法内存分配策略和分配算法 2)按比例分配算法按比例分配算法:根据进程的大小按比例分配物理块。如果根据进程的大小按比例分配物理块。如果系统中共有系统中共有n个进程，每个进程的页面数为个进程，每个进程的页面数为Si，则系统中各进程页，则系统中各进程页面数的总和为：面数的总和为：又假定系统中可用的物理块总数为又假定系统中可用的物理块总数为m，则每个进程所能分到的物，则每个进程所能分到的物理块数为理块数为bi，将有：，将有：bi应该取整，它必须大于最小物理块数。应该取整，它必须大于最小物理块数。niiSS1mSSbii操作系统原理操作系统原理 课程 第60张 3) 考虑优先权的分配算法考

58、虑优先权的分配算法 在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，成， 应为它分配较多的内存空间。应为它分配较多的内存空间。通常采取的方法是把内存中通常采取的方法是把内存中可供分配的所有物理块分成两部分：可供分配的所有物理块分成两部分：一部分按比例一部分按比例地分配给各地分配给各进程；进程；另一部分则根据各进程的优先权另一部分则根据各进程的优先权，适当地增加其相应份，适当地增加其相应份额后，分配给各进程。额后，分配给各进程。 在有的系统中，如重要的实时控制系统，则可能是完全按优在有的系统中，如重要的实时控制系统，则可能是完全按优先权

59、来为各进程分配其物理块的。先权来为各进程分配其物理块的。 3. 物理块分配算法物理块分配算法 4.7.3 内存分配策略和分配算法内存分配策略和分配算法 操作系统原理操作系统原理 课程 第61张4.7.4 调页策略调页策略 1. 何时调入页面何时调入页面 预调预调页策略页策略 2) 请请求求调调页策略页策略 4.7 请求分页存储管理请求分页存储管理2. 从何处调入页面从何处调入页面 在请求分页系统中的外存分为两部分：用于存放文件的在请求分页系统中的外存分为两部分：用于存放文件的文件区文件区和用于存放对换页面的和用于存放对换页面的对换区对换区。通常，由于对换区是。通常，由于对换区是采用连续分配方式

60、，而事件是采用离散分配方式，故对换区采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘的磁盘I/O速度比文件区的高。速度比文件区的高。操作系统原理操作系统原理 课程 第62张 每当程序所要访问的页面未在内存时，便向每当程序所要访问的页面未在内存时，便向CPUCPU发出一缺页中断，发出一缺页中断，中断处理程序首先保留中断处理程序首先保留CPUCPU环境，分析中断原因后，环境，分析中断原因后， 转入缺页中断转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块后，处理程序。该程序通过查找页表，得到该页在外存的物理块后， 如果此时内存能容纳新页，则启动磁盘如果此时内存能容纳新页，则