N计算机操作系统教程第四章(B)

1、 计算机操作系统教程计算机操作系统教程 -Linux实例分析 程骅程骅 信息科学与工程学院信息科学与工程学院 存储管理的功能存储管理的功能 1. 分区存储管理分区存储管理2. 页式存储管理页式存储管理3. 段式存储管理段式存储管理 4. 虚拟存储技术虚拟存储技术5. Linux内存管理内存管理 6. 第第 4 4 章章 存储器管理存储器管理 第一节第一节 存储管理的功能存储管理的功能 v存储器是计算机系统的重要资源之一，存储管存储器是计算机系统的重要资源之一，存储管 理直接影响系统性能。理直接影响系统性能。 v三级存储体系结构三级存储体系结构 一级缓存（一级缓存（cache）内存内存外存外存

2、v存储管理的基本功能存储管理的基本功能 空间分配空间分配/回收，地址转换，共享与保护，空回收，地址转换，共享与保护，空 间扩充间扩充 v目标：目标：提供足够的容量，快速的存取速度，提供足够的容量，快速的存取速度， 可靠的稳定性能可靠的稳定性能 v虚拟存储器虚拟存储器 4.1 存储管理的基本概念存储管理的基本概念 v重要性重要性 直接存取要求内存速度尽量快到与直接存取要求内存速度尽量快到与CPU 取指速度相匹配，大到能装下当前运行取指速度相匹配，大到能装下当前运行 的程序与数据，否则的程序与数据，否则CPU执行速度就会执行速度就会 受到内存速度和容量的影响而得不到充受到内存速度和容量的影响而得不

3、到充 分发挥分发挥 重要资源，重要资源，“瓶颈瓶颈” v帕金森定律帕金森定律 内存多大，程序多长内存多大，程序多长 v内存：内存：由存储单元（字节或字）组成的一维连续的地由存储单元（字节或字）组成的一维连续的地 址空间，简称内存空间。用来存放当前正在运行程序址空间，简称内存空间。用来存放当前正在运行程序 的代码及数据，是程序中指令本身地址所指的、亦即的代码及数据，是程序中指令本身地址所指的、亦即 程序计数器所指的存储器。程序计数器所指的存储器。 v分为：分为： 系统区：用于存放操作系统系统区：用于存放操作系统 用户区：用于装入并存放用户程序和数据用户区：用于装入并存放用户程序和数据 v存储管理

4、的目的：存储管理的目的： 充分利用内存，为多道程序并发执行提供存储基础充分利用内存，为多道程序并发执行提供存储基础 尽可能方便用户使用，如：自动装入用户程序，用尽可能方便用户使用，如：自动装入用户程序，用 户程序中不必考虑硬件细节户程序中不必考虑硬件细节 解决程序空间比实际内存空间大的问题解决程序空间比实际内存空间大的问题 存储系统的组织与四大功能存储系统的组织与四大功能 v高速缓存高速缓存Cache：少量的、非常快速、昂贵、少量的、非常快速、昂贵、易变易变 v内存内存RAM：若干兆字节、中等速度、中等价格、易变若干兆字节、中等速度、中等价格、易变 v磁盘：磁盘：数百兆或数千兆字节、低速、价廉

5、、数百兆或数千兆字节、低速、价廉、不易变不易变 v存储器的功能是保存数据，存储器的发展方向是高速、大容量和存储器的功能是保存数据，存储器的发展方向是高速、大容量和 小体积。小体积。 内存在访问速度方面的发展：内存在访问速度方面的发展： SRAM 、DRAM、SDRAM等；等； 硬盘技术在大容量方面的发展：接口标准、存储密度等；硬盘技术在大容量方面的发展：接口标准、存储密度等； v存储组织是指在存储技术和存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理寻址技术许可的范围内组织合理 的存储结构。的存储结构。 其依据是访问速度匹配关系、容量要求和价格。其依据是访问速度匹配关系、容量要求和价

6、格。 “寄存器寄存器-内存内存-外存外存”结构结构 “寄存器寄存器-缓存缓存-内存内存-外存外存”结构；结构； v微机中的存储层次组织：微机中的存储层次组织： 访问速度越慢，容量越大，价格越便宜；访问速度越慢，容量越大，价格越便宜； 最佳状态应是各层次的存储器都处于均衡的繁忙状态（如：缓最佳状态应是各层次的存储器都处于均衡的繁忙状态（如：缓 存命中率正好使主存读写保持繁忙）；存命中率正好使主存读写保持繁忙）； 存储管理的四大功能存储管理的四大功能 v（1）存储空间的管理、分配和回收）存储空间的管理、分配和回收 记录内存的使用情况记录内存的使用情况设置相应的内存分配表设置相应的内存分配表 （内存

7、分配回收的依据）（内存分配回收的依据） 静态存储分配；动态存储分配静态存储分配；动态存储分配 分配和回收算法及相应的数据结构。分配和回收算法及相应的数据结构。 v（2）地址再定位（地址变换、地址映射）地址再定位（地址变换、地址映射）： 可执行文件生成中的链接技术可执行文件生成中的链接技术 程序加载程序加载(装入装入)时的重定位技术时的重定位技术 进程运行时硬件和软件的地址变换技术和机构进程运行时硬件和软件的地址变换技术和机构 v（3）存储共享和保护）存储共享和保护：两个或多个进程共用内存中：两个或多个进程共用内存中 相同区域相同区域 代码和数据共享代码和数据共享 地址空间访问权限、基址地址空间

8、访问权限、基址限长存储保护限长存储保护 上、下界存储保护上、下界存储保护 保护过程保护过程-防止地址越界、防止操作越权防止地址越界、防止操作越权 v（4）存储器扩充：）存储器扩充：存储器的逻辑组织和物存储器的逻辑组织和物 理组织，虚拟存储；理组织，虚拟存储； 由应用程序控制：覆盖；由应用程序控制：覆盖； 由由OS控制控制 交换（整个进程空间）交换（整个进程空间） 虚拟存储的请求调入和预调入（部分进虚拟存储的请求调入和预调入（部分进 程空间）程空间） 从源程序到程序执行从源程序到程序执行 v编译：编译程序编译：编译程序 由编译程序（由编译程序（Compiler）将用户源代码编译）将用户源代码编译

9、 成若干个目标模块。成若干个目标模块。 v链接：链接程序链接：链接程序 由链接程序（由链接程序（Linker）将编译后形成的一组）将编译后形成的一组 目标模块，以及它们所需要的库函数链接在目标模块，以及它们所需要的库函数链接在 一起，形成装入模块。一起，形成装入模块。 v装入：装入程序装入：装入程序 由装入程序（由装入程序（Loader）将装入模块复制到内）将装入模块复制到内 存中。存中。 库 汇编 编译 主 子1 子2 目标模块 链接程序 装入模块 库 主 子1 子2 装入程序 内存 库 主 子1 子2 地址空间的概念地址空间的概念 v物理（绝对）地址物理（绝对）地址程序执行程序执行 每个内

10、存单元的固定顺序地址（编号）。每个内存单元的固定顺序地址（编号）。 v逻辑（相对）地址逻辑（相对）地址装入（汇编编译）装入（汇编编译） 被链接装配（或汇编、编译）后的目标模块被链接装配（或汇编、编译）后的目标模块 所限定的地址的集合；所限定的地址的集合； 相对于某个基准量（通常为：相对于某个基准量（通常为：0）的编址。）的编址。 物理地址 内存 00000 00001 00002 . . . 01000 01FFF 主 子1 子2 主 子1 子2 逻辑地址 装入模块 000 . . . FFF 主 子1 子2 相对地址 源程序/单个目标模块 000 5FF 000 3FF 000 3FF 重定

11、位的概念重定位的概念 v重定位重定位 概念：把程序装入内存时，修改程序中所有概念：把程序装入内存时，修改程序中所有 与地址有关的项。与地址有关的项。 逻辑地址变换为物理地址。逻辑地址变换为物理地址。 v重定位的类型重定位的类型 静态重定位：程序执行前，一次性，链接静态重定位：程序执行前，一次性，链接 装入程序。装入程序。 动态重定位：处理机每次访问主存时，有动态重定位：处理机每次访问主存时，有 动态地址变换机构（硬件）自动执行。动态地址变换机构（硬件）自动执行。 作业地址空间 内存空间 装入 365 LOAD 1,2500 5000 2500 1000 365 LOAD 1,2500 1500

12、0 12500 10000 11000 365 LOAD1,12500 15000 12500 10000 11000 地址再定位地址再定位 v名空间：名空间：程序中由符号名组成的空间。程序中由符号名组成的空间。 v物理地址（绝对地址，实地址）物理地址（绝对地址，实地址）：内存中存储单元的：内存中存储单元的 地址。物理地址可直接寻址。地址。物理地址可直接寻址。 v逻辑地址（相对地址，虚地址）逻辑地址（相对地址，虚地址）：用户的程序经过汇：用户的程序经过汇 编或编译后形成目标代码，目标代码通常采用相对地编或编译后形成目标代码，目标代码通常采用相对地 址的形式。是指相对于某个基准量址的形式。是指相

13、对于某个基准量(通常用通常用0)编址时所编址时所 使用的地址。使用的地址。 其首地址为其首地址为0，其余指令中的地址都相对于首地址，其余指令中的地址都相对于首地址 来编址。来编址。 不能用逻辑地址在内存中读取信息。不能用逻辑地址在内存中读取信息。 v逻辑地址空间通过逻辑地址空间通过地址再定位地址再定位机构转换到绝对地址空机构转换到绝对地址空 间间。 Address: mov Ax,1 Obj 目标地址目标地址 名空间名空间 编译编译 地址空间地址空间 EXE文件装入文件装入 存贮空间存贮空间 mov Ax,(500) 12.3 0 100 500 1000 1100 1500 mov Ax,(

14、500) 12.3 装入主存装入主存 出错出错 解决方法：重定位解决方法：重定位 地址映射地址映射 BA=1000 Load A 200 3456 。 。 。 1200 物理地址空间物理地址空间 Load A data1 data1 3456 源程序源程序 Load A 200 3456 0 100 200 编译连接编译连接 逻辑地址空间逻辑地址空间 逻辑地址、物理地址和地址映射逻辑地址、物理地址和地址映射 地址的再定位方法地址的再定位方法 v将逻辑地址空间的程序装入到物理地址空间时，由于将逻辑地址空间的程序装入到物理地址空间时，由于 两个空间不一致，需要进行地址变换，所引起的对有两个空间不一

15、致，需要进行地址变换，所引起的对有 关地址部分的调整过程称为关地址部分的调整过程称为地址再定位地址再定位。 v程序在成为进程前的准备工作程序在成为进程前的准备工作 编辑：形成源文件（符号地址）编辑：形成源文件（符号地址） 编译：形成目标模块（模块内符号地址解析）编译：形成目标模块（模块内符号地址解析） 链接：由多个目标模块或程序库生成可执行文件（链接：由多个目标模块或程序库生成可执行文件（ 模块间符号地址解析）模块间符号地址解析） 装入：构造装入：构造PCB，形成进程（使用物理地址），形成进程（使用物理地址） v再定位方法再定位方法 静态再定位静态再定位 动态再定位动态再定位 静态地址再定位静

16、态地址再定位 v在程序执行之前进行地址再定位，由装配程序完成。在程序执行之前进行地址再定位，由装配程序完成。 在可执行文件中，列出各个需要重定位的地址单元在可执行文件中，列出各个需要重定位的地址单元 和相对地址值。当用户程序被装入内存时，一次性和相对地址值。当用户程序被装入内存时，一次性 实现逻辑地址到物理地址的转换，以后不再转换（实现逻辑地址到物理地址的转换，以后不再转换（ 一般在装入内存时由软件完成）。即：装入时根据一般在装入内存时由软件完成）。即：装入时根据 所定位的内存地址去修改每个重定位地址项，添加所定位的内存地址去修改每个重定位地址项，添加 相应偏移量。相应偏移量。 v优点：优点：

17、不需硬件支持，可以装入有限多道程序。不需硬件支持，可以装入有限多道程序。 v缺点：缺点： 程序装入内存后不能移动程序装入内存后不能移动 一个程序通常需要占用连续的内存空间一个程序通常需要占用连续的内存空间 不易实现共享不易实现共享 jmp 150 100150 . Relocation Table 0 jmp 150 21002150 . 2000 可执行文件在内存中的重定位可执行文件在内存中的重定位 重定位修改：重定位表中的重定位修改：重定位表中的150-绝对地址绝对地址2150(=2000+150) 内容修改：内容内容修改：内容100变成变成2100(=100+2000)。 动态地址再定位

18、动态地址再定位 v在执行寻址时重定位在执行寻址时重定位在程序运行过程在程序运行过程 中要访问数据时再进行地址变换，即在逐中要访问数据时再进行地址变换，即在逐 条指令执行时完成地址映射。条指令执行时完成地址映射。 v一般为了提高效率，此工作由硬件地址映一般为了提高效率，此工作由硬件地址映 射机制来完成。硬件支持，软硬件结合完射机制来完成。硬件支持，软硬件结合完 成成 v硬件上需要一对寄存器的支持：基址寄存硬件上需要一对寄存器的支持：基址寄存 器、变址寄存器器、变址寄存器。 mov r1,500 123 0 100 500 599 作业地址空间作业地址空间 mov r1 , 500 123 0 1

19、000 256k-1 存储空间存储空间 1100 1500 1600 1000 500 逻辑地址逻辑地址 动态地址映射过程示意图动态地址映射过程示意图 动态地址映射的优缺点动态地址映射的优缺点 v优点：优点：程序占用的内存空间是动态可变的，程序占用的内存空间是动态可变的， 当程序从某个存储区移到另一个区域时，只当程序从某个存储区移到另一个区域时，只 需要修改相应的寄存器需要修改相应的寄存器BR的内容即可。的内容即可。 一个程序不一定要求占用一个连续的内存一个程序不一定要求占用一个连续的内存 空间。空间。 可以部分地装入程序运行。可以部分地装入程序运行。 便于多个进程共享同一个程序的代码。便于多

20、个进程共享同一个程序的代码。 v动态地址重定位的代价：动态地址重定位的代价： 需要硬件的支持。需要硬件的支持。 实现存储管理的软件算法较为复杂实现存储管理的软件算法较为复杂。 IBM. PC的情况的情况 源程序源程序.obj.EXE.com 编译编译link exezbin .com绝对地址：装入即可运行绝对地址：装入即可运行 .com文件文件64k(可以可以) 程序的链接程序的链接 v 链接：链接：把一个程序相关的一组目标模块和系把一个程序相关的一组目标模块和系 统调用模块（库函数）链接形成一个整体统调用模块（库函数）链接形成一个整体 装入模块的过程。装入模块的过程。 v 具体工作：具体工作

21、：对相对地址的修改；变换外部调对相对地址的修改；变换外部调 用符号。用符号。 v 链接方式：链接方式： 静态链接静态链接 装入时动态链接：便于修改和装入时动态链接：便于修改和 更新；便于共享。更新；便于共享。运行时动态链接：最运行时动态链接：最 小化快速装入，节省内存。小化快速装入，节省内存。 模块A Call B; Return; 0 L-1 模块B Call C; Return; 0 M-1 模块C ; Return; 0 N-1 链接 模块A Call B; Return; 0 L-1 模块B Call C; Return; L L+M-1 模块C ; Return; L+M L+M+N

22、-1 装入模块 程序的装入程序的装入 v就是把链接好的装入模块装入就是把链接好的装入模块装入“内存内存”。 v装入方式装入方式 绝对装入：单道（任务）；装入位置是绝对装入：单道（任务）；装入位置是 固定的。程序员直接编址或由汇编、编固定的。程序员直接编址或由汇编、编 译程序完成地址重定位。译程序完成地址重定位。 可重定位装入（静态重定位）可重定位装入（静态重定位） 动态运行时装入（动态重定位）动态运行时装入（动态重定位） v提示：通常链接、装入程序是一体的。提示：通常链接、装入程序是一体的。 第二节第二节 连续分配方式连续分配方式 为用户程序分配一个连续的内存空间。为用户程序分配一个连续的内存

23、空间。 单一连续分配单一连续分配 固定分区分配固定分区分配 动态分区分配动态分区分配 可重定位分区分配可重定位分区分配 实存扩充技术实存扩充技术 单一连续分区单一连续分区 内存分为两个区域：系统区，用户区。应内存分为两个区域：系统区，用户区。应 用程序装入到用户区，可使用用户区全用程序装入到用户区，可使用用户区全 部空间。最简单，适用于单用户、单任部空间。最简单，适用于单用户、单任 务的务的OS。 优点：易于管理。优点：易于管理。 缺点：对要求内存空间少的程序，造成内缺点：对要求内存空间少的程序，造成内 存浪费；程序全部装入，很少使用的程存浪费；程序全部装入，很少使用的程 序部分也占用内存。序

24、部分也占用内存。 用户程序用户程序 位于位于RAM中的中的 操作系统操作系统 0 xFFF. 0 位于位于RAM中的中的 操作系统操作系统 用户程序用户程序 0 ROM中的中的 设备驱动程序设备驱动程序 用户程序用户程序 位于位于RAM中的中的 操作系统操作系统 0 单一连续区存储管理单一连续区存储管理 分区存储管理分区存储管理 v原理：原理：把内存分为一些大小相等或不等的分区，每个把内存分为一些大小相等或不等的分区，每个 应用进程占用一个或几个分区。操作系统占用其中一应用进程占用一个或几个分区。操作系统占用其中一 个分区。个分区。 v特点：特点：适用于多道程序系统和分时系统适用于多道程序系统

25、和分时系统 v问题：问题：内碎片：占用分区之内未被利用的空间内碎片：占用分区之内未被利用的空间; 外碎片：占用分区之间难以利用的空闲分区（外碎片：占用分区之间难以利用的空闲分区（ 通常是小空闲分区）。通常是小空闲分区）。 v分区方式：分区方式： 固定分区固定分区(fixed partitioning) 动态分区动态分区(dynamic partitioning) 分区分配算法分区分配算法 v分区的数据结构：分区表，或分区链表分区的数据结构：分区表，或分区链表 只记录空闲分区，或同时记录空闲和占用分区只记录空闲分区，或同时记录空闲和占用分区 v内存紧缩内存紧缩(compaction)：将各个占用

26、分区向内存一端：将各个占用分区向内存一端 移动。使各个空闲分区聚集在另一端，然后将各个空移动。使各个空闲分区聚集在另一端，然后将各个空 闲分区合并成为一个空闲分区。闲分区合并成为一个空闲分区。 对占用分区进行内存数据搬移占用对占用分区进行内存数据搬移占用CPU时间时间 如果对占用分区中的程序进行如果对占用分区中的程序进行浮动浮动，则其重定位，则其重定位 需要硬件支持。需要硬件支持。 紧缩时机：每个分区释放后，或内存分配找不到满紧缩时机：每个分区释放后，或内存分配找不到满 足条件的空闲分区时足条件的空闲分区时 固定分区固定分区(fixed partitioning) v把内存划分为若干个固定大小

27、的连续分区。把内存划分为若干个固定大小的连续分区。 分区大小相等：分区大小相等：只适合于多个相同程序的并发执行只适合于多个相同程序的并发执行 （处理多个类型相同的对象）。（处理多个类型相同的对象）。 分区大小不等：分区大小不等：多个小分区、适量的中等分区、少多个小分区、适量的中等分区、少 量的大分区。根据程序的大小，分配当前空闲的、量的大分区。根据程序的大小，分配当前空闲的、 适当大小的分区。适当大小的分区。 v优点：易于实现，开销小。优点：易于实现，开销小。 v缺点：内碎片造成浪费缺点：内碎片造成浪费;分区总数固定，限制了并发执分区总数固定，限制了并发执 行的程序数目。行的程序数目。 v采用

28、的数据结构：分区表记录分区的大小和使用采用的数据结构：分区表记录分区的大小和使用 情况情况 8 M 8 M 8 M 8 M 8 M Operating System Operating System 8 M 12 M 8 M 8 M 6 M 4 M 2 M 固定分区固定分区( (大小相同大小相同) )固定分区固定分区( (多种大小多种大小) ) o.s区区 20k 28k 60k 90k 128k 256k 0区区 1区区 2区区 3区区 4区区 区号区号 大小大小起址起址状态状态 1 2 3 4 20k 28k 60k 128k in using NuL 8k 32k 68k 128k in

29、 using NuL (存贮分块表存贮分块表MBT) 分区分区4 分区分区3 分区分区2 分区分区1 操作系统操作系统 多个输入队列多个输入队列 单个输入队列单个输入队列 分区分区4 分区分区3 分区分区2 分区分区1 操作系统操作系统 700K 400K 100K 0 区号/键大小位置状态 18 K512K正使用 232 K520K正使用 332 K552K未使用 4128 K584K未使用 5512 K712K正使用 系统区 分区分区 1 分区分区 4 分区分区 5 分区分区 2 分区分区 3 系统区 作业 3 分区 4 作业 2 作业 1 分区 3 v存储保护与重定位（地址转换）存储保护

30、与重定位（地址转换） 每个分区（一道程序）对应一对界地址寄存器每个分区（一道程序）对应一对界地址寄存器 ：上：上/下限寄存器。下限寄存器。 采用静态重定位方式，即由链接采用静态重定位方式，即由链接/装入程序完成装入程序完成 。 v优缺点优缺点 优点：简单，要求的硬件支持少（一对优点：简单，要求的硬件支持少（一对R）；）； 缺点：存在大的碎片，主存利用率低。缺点：存在大的碎片，主存利用率低。 动态分区分配动态分区分配 v动态创建分区：在装入程序时按其初始要求分动态创建分区：在装入程序时按其初始要求分 配，或在执行过程中通过系统调用进行分配或配，或在执行过程中通过系统调用进行分配或 改变分区大小。

31、改变分区大小。 v数据结构的两种形式：数据结构的两种形式： 空闲分区表；空闲分区链空闲分区表；空闲分区链 v存储分配算法存储分配算法 最佳适应算法：大小最接近的，保证较小的碎最佳适应算法：大小最接近的，保证较小的碎 片；最先适应算法：最先找到的合适分区，短片；最先适应算法：最先找到的合适分区，短 的时间；最坏适应算法：找到最大的合适分区的时间；最坏适应算法：找到最大的合适分区 ，不适于固定分区管理。，不适于固定分区管理。 动态分区动态分区(dynamic partitioning) v优点：没有内碎片。缺点：有外碎片；如果大小优点：没有内碎片。缺点：有外碎片；如果大小 不是任意的，也可能出现内

32、碎片。不是任意的，也可能出现内碎片。 Operating System Process 1 320 K Process 2 Process 3 224 K 288 K 64 K Operating System Process 1 320 K Process 3 224 K 288 K 64 K Operating System Process 1 320 K Process 3288 K 64 K Process 4 128 K 96 K Operating System 320 K Process 3288 K 64 K Process 4 128 K 96 K Operating Sys

33、tem Process 3288 K 64 K Process 4 128 K 96 K Process 2224 k 96 K OS区 Job1 Job2 Job3 Job4 Job5 Job6 Job7 OS区 Job1 Job2 Job3 Job4 Job5 空闲分区链空闲分区链 头指针头指针 Job7 Job6 空闲分区的组织形式空闲分区的组织形式 序号序号大小大小起址起址状态状态 1 2 3 4 312k 320k 384k 已分已分 已分已分 8k 32k 120k 空表目空表目 已分已分 5 空表目空表目 大小大小起址起址状态状态 352k 504k 自由自由 空表目空表目 32

34、k 520k 自由自由 空表目空表目 空表目空表目 已分配分区表已分配分区表 UBT表表自由分区表自由分区表FBT 分区分配算法分区分配算法 v分区分配算法：分区分配算法：寻找某个空闲分区，其大小需大寻找某个空闲分区，其大小需大 于或等于程序的要求。若是大于要求，则将该分于或等于程序的要求。若是大于要求，则将该分 区分割成两个分区，其中一个分区为要求的大小区分割成两个分区，其中一个分区为要求的大小 并标记为并标记为“占用占用”，而另一个分区为余下部分并，而另一个分区为余下部分并 标记为标记为“空闲空闲”。分区的先后次序通常是从内存。分区的先后次序通常是从内存 低端到高端。低端到高端。 v分区释

35、放算法：分区释放算法：需要将相邻的空闲分区合并成一需要将相邻的空闲分区合并成一 个空闲分区。个空闲分区。(这时要解决的问题是：合并条件这时要解决的问题是：合并条件 的判断和合并时机的选择的判断和合并时机的选择) v分区分配操作（分配算法流程）分区分配操作（分配算法流程） 分配内存分配内存 分区大小与所需空间大小分区大小与所需空间大小“匹配匹配”： M.Size - U.Size Size （不再分割的小分区的尺寸（不再分割的小分区的尺寸 ） 剩余部分挂接到空闲分区链（表）上。剩余部分挂接到空闲分区链（表）上。 回收内存回收内存 回收区与插入点的前一个空闲分区相邻接；回收区与插入点的前一个空闲分

36、区相邻接； 回收区与插入点的后一个空闲分区相邻接；回收区与插入点的后一个空闲分区相邻接； 回收区与插入点的前后两个空闲分区相邻接；回收区与插入点的前后两个空闲分区相邻接； 回收区不与任何一个空闲分区相邻接；回收区不与任何一个空闲分区相邻接； v优缺点优缺点 管理复杂，总会有闲置的小分区管理复杂，总会有闲置的小分区“碎片碎片” 。 查找空闲分区链表第一项查找空闲分区链表第一项 检索完否？检索完否？ m.sizeu.size? m.size-u.sizesize? 划出划出u.size大小的分区大小的分区 修改有关的数据结构修改有关的数据结构 返回返回 将该分区从链表中移出将该分区从链表中移出 继

37、续检索下一个表项继续检索下一个表项 Y Y Y N N N OS区区 Job2 Job4 Job3 Job1 Job5 Job6 Job7 OS区 Job2 Job4 Job3 Job1 Job5 Job6 Job7 “零头” 碎片 OS区区 Job2 Job4 Job3 Job1 Job5 Job6 Job7 “零头” 碎片 v最先匹配法最先匹配法(first-fit)：按分区的先后次序，从头查找，找到符合按分区的先后次序，从头查找，找到符合 要求的第一个分区要求的第一个分区 该算法的分配和释放的时间性能较好，较大的空闲分区可以该算法的分配和释放的时间性能较好，较大的空闲分区可以 被保留在内

38、存高端。被保留在内存高端。 但随着低端分区不断划分而产生较多小分区，每次分配时查但随着低端分区不断划分而产生较多小分区，每次分配时查 找时间开销会增大。找时间开销会增大。 v下次匹配法下次匹配法(next-fit)：按分区的先后次序，从上次分配的分区起按分区的先后次序，从上次分配的分区起 查找（到最后分区时再回到开头），找到符合要求的第一个分区查找（到最后分区时再回到开头），找到符合要求的第一个分区 该算法的分配和释放的时间性能较好，使空闲分区分布得更该算法的分配和释放的时间性能较好，使空闲分区分布得更 均匀，但较大的空闲分区不易保留。均匀，但较大的空闲分区不易保留。 v最佳匹配法最佳匹配法(

39、best-fit)：找到其大小与要求相差最小的空闲分区找到其大小与要求相差最小的空闲分区 从个别来看，外碎片较小，但从整体来看，会形成较多外碎从个别来看，外碎片较小，但从整体来看，会形成较多外碎 片。较大的空闲分区可以被保留。片。较大的空闲分区可以被保留。 v最坏匹配法最坏匹配法(worst-fit)：找到最大的空闲分区找到最大的空闲分区 基本不留下小空闲分区，但较大的空闲分区不被保留。基本不留下小空闲分区，但较大的空闲分区不被保留。 指针指针 10k60k90k20k 有四块空白区有四块空白区(从低地址从低地址高地址高地址)，来了，来了 一个作业需分配一个作业需分配19k内存内存。 (i)首

40、次适应算法首次适应算法(First Fit: FF) 指针指针 10k60k90k20k 41k 在高地址空白区中保持较大空白区在高地址空白区中保持较大空白区(每次从每次从 10k开始分配寻找开始分配寻找)。 FF特点：特点： (ii) 循环首次适应循环首次适应(Next fit: NF) 将空白区组成环状队列，按循环顺序寻找空将空白区组成环状队列，按循环顺序寻找空 白区。白区。(与与FF区别，头指针从低地址开始向高地区别，头指针从低地址开始向高地 址循环移动址循环移动) 12 指针移动指针移动 使得小空白区均匀分布，易于与其它空白使得小空白区均匀分布，易于与其它空白 区合并区合并。 NF特点

41、：特点： (iii) 最佳适应算法最佳适应算法(Best fit: BF) 将空白区按大小排成队列，寻找时总是以最小将空白区按大小排成队列，寻找时总是以最小 的空白区开始，找到第一个合适的分区的空白区开始，找到第一个合适的分区 指针指针 10k60k90k20k 来一个来一个19k的的作业作业 最佳地利用分区；最佳地利用分区； 开销比较大，并不是最好算法。开销比较大，并不是最好算法。 指针指针 10k20k60k90k 1k 特点：特点： (iv) 最坏适应算法最坏适应算法(Worst fit: WF) 将空白区排序将空白区排序(按从大到小按从大到小) 找最大空白区找最大空白区 如上例：如上例

42、： 指针指针 90k60k20k10k 71k 不会出现小的空白区。不会出现小的空白区。 特点：特点： ：设系统空白链表为设系统空白链表为 指针指针 7k3k10k8k20k5k abcdef 用户先后申请用户先后申请7.5k，4k试用四种算法，试试用四种算法，试 求出分配块。求出分配块。 FF: c,a 3k3k2.5k8k20k5k abcdef NF: c,d 7k3k2.5k4k20k5k abcdef 3k5k7k8k10k20k bfadce BF:首先从小到大排序首先从小到大排序 3k5k7k0.5k10k20k bfadce 3k5k7k0.5k10k20k bfadce 再排

43、序从小到大再排序从小到大 分配块为分配块为d, f 8.5k10k8k7k5k3k ecdafb WF: e,e 0.5k3k1k7k10k20k dbface (i) 原因：请求原因：请求释放释放使存区分割使存区分割 (ii) 碎片总和碎片总和nk，但不能装入但不能装入nk作业作业 碎片碎片(零头零头)问题问题 v存在于已分配的分区之间的一些不能充分利存在于已分配的分区之间的一些不能充分利 用的空白区用的空白区 解决的方法：解决的方法： (I) 将程序装入分散存区中将程序装入分散存区中 多重分区多重分区 Job1 Job2 Job3 RR 12 Job4部分部分2 Job4部分部分1 RR2

44、1 RR22 RR11 (II) 将碎片集中将碎片集中(紧凑或拼接紧凑或拼接) 可重定位分配可重定位分配 Job1 Job2 Job3 Job4 v移动内存已分配区的信息，使得所有分移动内存已分配区的信息，使得所有分 配区靠在一起使空白区连成一片，采用配区靠在一起使空白区连成一片，采用 浮动方法。浮动方法。 20k 28k 88k 132k 182k o.s 作业作业1(8k) (16k) 作业作业3(24k) (24k) 作业作业(20k) 作业作业4(50k) (74k) 64k 112k 256k (a)初始状态初始状态 20k 202k o.s 1 3 2 4 作业作业5(80k) (

45、54k) 122k (c)分配作业分配作业5之后之后 (b)移动之后移动之后(即浮动即浮动) 20k 28k 72k o.s 1(8k) 3(24k) 2(20k) 4(50k) (134k) 52k 122k 256k 作业作业5 80k 两大类分区分配类两大类分区分配类 单一连续区单一连续区 固定分区固定分区 可变分区可变分区 多重分区多重分区 可重定位分区可重定位分区 多用户多用户 解决零头解决零头 MS DOS中的分区存储管理中的分区存储管理 vDOS提供提供动态分区动态分区管理；管理； v通过通过DOS功能调用功能调用int 21h，支持分区的创，支持分区的创 建建(48h)、释放、

46、释放(49h)和改变分区大小和改变分区大小(4Ah) v设置或查询分区的分配策略设置或查询分区的分配策略(58h)： 最先匹配法、最先匹配法、 最佳匹配法、最佳匹配法、 最后匹配法（最后匹配法（last-fit，从内存高端向低端，从内存高端向低端 查找）查找） 数据结构为单向链表。每个分区以一个数据结构为单向链表。每个分区以一个MCB(Memory Control Block)结构开始，结构开始，MCB占占16个字节，按段边界对齐（起始地址可个字节，按段边界对齐（起始地址可 被被16整除）整除） PSP(Program Segment Prefix)：起进程控制块的作用，其起始地：起进程控制块

47、的作用，其起始地 址可作为进程址可作为进程ID typedef struct BYTE type;/* M = in chain; Z = at end*/ WORD owner;/* PSP of the owner process, 0 = free */ WORD size;/* in 16-byte paragraphs */ BYTE unused3; BYTE dos48;/* program name(DOS 4.x) */ MCB; 可重定位分区分配可重定位分区分配 v动态重定位的引入动态重定位的引入 随着系统接收的作业的增加，内存中连续的大随着系统接收的作业的增加，内存中连续

48、的大 块分区不复存在，产生了大量的块分区不复存在，产生了大量的“碎片碎片”。 新的作业无法装入到每个新的作业无法装入到每个“碎片碎片”小分区上运小分区上运 行，但所有碎片的空间总和可能大于需求。行，但所有碎片的空间总和可能大于需求。 通过通过“拼接拼接”/“紧凑紧凑”/“紧缩紧缩”/“”澄清澄清“来实来实 现现”程序的浮动程序的浮动“/” 动态重定位动态重定位“。 v动态重定位的实现动态重定位的实现 必须由硬件地址变换机构支持实现必须由硬件地址变换机构支持实现重定位重定位 R 重定位寄存器：存放程序存放的起始地址。重定位寄存器：存放程序存放的起始地址。 处理机一侧 存储器一侧 作业J 内存 3

49、65 LOAD1,2500 5000 2500 1000 365 LOAD 1,12500 15000 12500 10000 11000 2500 相对地址 10000 重定位 寄存器 v 优缺点分析 优点：消除了“碎片”，提高了内存利用率，同时提高了系 统效率。 缺点：需要动态重定位“硬件”机构支持，增加了系统成本 ，并轻度降低了程序执行速度，“紧凑”处理增加了系统开 销。 可重定位分区分配算法 动态重定位分区分配算法流程 查找空闲分区链表第一项 找到可用分区？ 按动态分区方式 进行分配 修改有关的 数据结构 返回分区号 及首批 进行紧凑 形成连续空闲区 YY NN 请求分配 u.size

50、分区 找到可用分区？ 修改有关的 数据结构 无法分配 返回 交换技术交换技术(swapping) v引入：引入：多个程序并发执行，可以将暂时不能执行的程序多个程序并发执行，可以将暂时不能执行的程序 送到外存中，从而获得空闲内存空间来装入新程序。送到外存中，从而获得空闲内存空间来装入新程序。 v原理：原理：暂停执行内存中的进程，将整个进程的地址空间暂停执行内存中的进程，将整个进程的地址空间 保存到外存的交换区中（换出保存到外存的交换区中（换出swap out），而将外存），而将外存 中由阻塞变为就绪的进程的地址空间读入到内存中，并中由阻塞变为就绪的进程的地址空间读入到内存中，并 将该进程送到就绪

51、队列（换入将该进程送到就绪队列（换入swap in）。）。 交换单位为整个进程的地址空间。交换单位为整个进程的地址空间。 与分区存储管理配合使用与分区存储管理配合使用 又称作又称作对换对换或或滚进滚进/滚出滚出(roll-in/roll-out)； 交换技术实现中的几个问题交换技术实现中的几个问题 v选择原则：选择原则：将哪个进程换出内存？将哪个进程换出内存？ 例子：分时系统，时间片轮转法或基于优先数的调度算法，例子：分时系统，时间片轮转法或基于优先数的调度算法， 在选择换出进程时，换出要长时间等待的进程。在选择换出进程时，换出要长时间等待的进程。 v交换时机的确定：交换时机的确定：何时需发生

52、交换？何时需发生交换？ 只要不用就换出（或很少再用）只要不用就换出（或很少再用） 只在内存空间不够或有不够的危险时换出只在内存空间不够或有不够的危险时换出 v交换时需要做哪些工作？交换时需要做哪些工作？ 需要一个盘交换区：必须足够大以存放用户程序的内存映像需要一个盘交换区：必须足够大以存放用户程序的内存映像 的拷贝；必须对这些内存映像直接存取。的拷贝；必须对这些内存映像直接存取。 v换入回内存时位置的确定换入回内存时位置的确定 换出后再换入的内存位置一定要在换出前的原来位置上吗？换出后再换入的内存位置一定要在换出前的原来位置上吗？ 受地址映射技术的影响，即绝对地址产生时机的限制受地址映射技术的

53、影响，即绝对地址产生时机的限制 v优点：优点： 增加并发运行的程序数目，并且给用户增加并发运行的程序数目，并且给用户 提供适当的响应时间；提供适当的响应时间； 编写程序时不影响程序结构。编写程序时不影响程序结构。 v缺点：缺点： 对换入和换出的控制增加处理机开销；对换入和换出的控制增加处理机开销； 程序整个地址空间都进行传送，没有考程序整个地址空间都进行传送，没有考 虑执行过程中地址访问的统计特性。虑执行过程中地址访问的统计特性。 交换技术的特点交换技术的特点 简单覆盖应用示意图 输入模块 正常输出 计算模块 数据错误 结束退出 结果异常 分析与报告 输入模块 计算模块 结束退出 正常输出 数

54、据错误 结果异常 分析与报告 实存扩充技术实存扩充技术 覆盖技术覆盖技术(overlay) v原理：原理：一个程序的几个代码段或数据段，按照时间先后一个程序的几个代码段或数据段，按照时间先后 来占用公共的内存空间。（并不是作业的每一部分都是来占用公共的内存空间。（并不是作业的每一部分都是 时时要用的）时时要用的） 把程序划分为若干个功能上相对独立的程序段，按把程序划分为若干个功能上相对独立的程序段，按 照其自身的逻辑结构将那些不会同时执行的程序段照其自身的逻辑结构将那些不会同时执行的程序段 共享同一块内存区域共享同一块内存区域 程序段先保存在磁盘上，当有关程序段的前一部分程序段先保存在磁盘上，

55、当有关程序段的前一部分 执行结束，把后续程序段调入内存，覆盖前面的程执行结束，把后续程序段调入内存，覆盖前面的程 序段（内存序段（内存“扩大扩大”了）了） 一般要求作业各模块之间有明确的调用结构，程序一般要求作业各模块之间有明确的调用结构，程序 员要向系统指明覆盖结构，然后由操作系统完成自员要向系统指明覆盖结构，然后由操作系统完成自 动覆盖动覆盖 A 8K E 4K F 10K C 10K B 8K D 12K 作业作业X的调用结构的调用结构 作业作业X X的常驻区的常驻区 A A（8K8K） 覆盖区覆盖区0 （10K） 覆盖区覆盖区1 （12K） BC C D E F 图图 示示 A 20K

56、 B 50K C 30K F 30K D 20K E 40K Resident 20K Overlay 0 50K Overlay 1 40K Total: 190KTotal: 110K 注：注：另一种覆盖方法：另一种覆盖方法：(100K) A(20K)占一个分区：占一个分区：20K； B(50K)、D(20K)和和E(40K)共用一个分区：共用一个分区：50K； F(30K)和和C(30K)共用一个分区：共用一个分区：30K； v缺点：缺点： 编程时必须划分程序模块和确定程序模块之间的覆编程时必须划分程序模块和确定程序模块之间的覆 盖关系，增加编程复杂度。盖关系，增加编程复杂度。 从外存装

57、入覆盖文件，以时间延长来换取空间节省从外存装入覆盖文件，以时间延长来换取空间节省 。 v实现：实现：函数库（操作系统对覆盖不得知），函数库（操作系统对覆盖不得知），或操作系或操作系 统支持统支持 v例子：例子：目前这一技术用于小型系统中的系统程序的内目前这一技术用于小型系统中的系统程序的内 存管理上，存管理上，MS-DOS的启动过程中，多次使用覆盖技的启动过程中，多次使用覆盖技 术；启动之后，用户程序区术；启动之后，用户程序区TPA的高端部分与的高端部分与 COMMAND.COM暂驻模块也是一种覆盖结构。暂驻模块也是一种覆盖结构。 覆盖技术分析覆盖技术分析 覆盖与交换的比较覆盖与交换的比较 v

58、共同点：共同点： 进程的程序和数据主要放在外存，当前需要进程的程序和数据主要放在外存，当前需要 执行的部分放在内存，内外存之间进行信息执行的部分放在内存，内外存之间进行信息 交换交换 v不同点：不同点： 交换发生在进程或作业之间，而覆盖发生在交换发生在进程或作业之间，而覆盖发生在 同一进程或作业内。同一进程或作业内。 与覆盖技术相比，交换技术不要求用户给出与覆盖技术相比，交换技术不要求用户给出 程序段之间的逻辑覆盖结构；程序段之间的逻辑覆盖结构； 基本分页存储管理方式基本分页存储管理方式 连续分配方式的不足，促使人们产生了分散连续分配方式的不足，促使人们产生了分散 分配的管理思想。从而引入了分

59、配的管理思想。从而引入了“分页分页”分配管分配管 理的管理方式。分为：基本分页（纯分页）和理的管理方式。分为：基本分页（纯分页）和 支持虚存管理的请求分页管理。支持虚存管理的请求分页管理。 页面与页表页面与页表 地址变换机构地址变换机构 两级和多级页表两级和多级页表 基本分页的特点基本分页的特点 分页存储管理的基本思想分页存储管理的基本思想 v主存分成多个固定大小的块主存分成多个固定大小的块 主存划分为大小相等的区域，称为块或内存块主存划分为大小相等的区域，称为块或内存块 （物理页面，页框）（物理页面，页框） v作业按照主存块大小分页作业按照主存块大小分页 把用户程序按逻辑页划分成大小相等的部

60、分，把用户程序按逻辑页划分成大小相等的部分， 称为页（称为页（page）。从）。从0开始编制页号，页内地开始编制页号，页内地 址是相对于址是相对于0编址编址 v连续的页存放在离散的块中连续的页存放在离散的块中 以页为单位进行分配，并按作业的页数多少来以页为单位进行分配，并按作业的页数多少来 分配。逻辑上相邻的页，物理上不一定相邻分配。逻辑上相邻的页，物理上不一定相邻 0 1 2 3 4 5 6 7 8 9 11 10 内存 第0页 第1页 第2页 第3页 第4页 第5页 第6页 用户作业 0 2K-1 第2页 （页长2K） 0 2K-1 4号页架 （页长2K） 页面与页表 v页面 页面和物理块