操作系统课件第四章1.ppt

1、Operating SystemOperating SystemPage 12022-5-24Operating SystemOperating Systemq重点重点v理解理解重定位的基本概念重定位的基本概念 v掌握掌握动态分区分配方式动态分区分配方式 v掌握理解掌握理解分页和分段存储管理方式分页和分段存储管理方式 v理解理解虚拟存储器的基本概念虚拟存储器的基本概念 v掌握掌握请求分页系统的基本原理请求分页系统的基本原理 q难点难点v动态分区分配动态分区分配算法算法 v分页和分段地址转换分页和分段地址转换v请求分页系统的地址转换及页面置换算法请求分页系统的地址转换及页面置换算法Page 22

2、022-5-24Operating SystemOperating Systemq知识点知识点v重定位的基本概念重定位的基本概念 v动态分区分配方式及分配算法、分区保护动态分区分配方式及分配算法、分区保护v分页存储管理及地址变换、分段存储管理及地分页存储管理及地址变换、分段存储管理及地址变换，信息共享和保护址变换，信息共享和保护v虚拟存储器的基本概念、特征，页面置换技术虚拟存储器的基本概念、特征，页面置换技术 v请求分页系统，页表机制、地址变换及页面置请求分页系统，页表机制、地址变换及页面置换算法换算法 Page 32022-5-24Operating SystemOperating Syst

3、emq存储器是计算机系统重要的组成部分存储器是计算机系统重要的组成部分q虽然存储器的容量不断扩大，但仍不能满虽然存储器的容量不断扩大，但仍不能满足要求，因此存储器管理是操作系统的重足要求，因此存储器管理是操作系统的重要工作要工作Page 42022-5-24Operating SystemOperating Systemq存储器包括内存（主存）和外存（磁盘）存储器包括内存（主存）和外存（磁盘）v存储器的功能是保存数据，存储器的发展方向存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。是高速、大容量和小体积。内存在访问速度方面的发展：内存在访问速度方面的发展：DRAM、SDRAM、

4、SRAM等；等；硬盘技术在大容量方面的发展：接口标准、硬盘技术在大容量方面的发展：接口标准、存储密度等；存储密度等；q主存储器管理技术分为两大类主存储器管理技术分为两大类v实存储器管理实存储器管理v虚拟存储器管理虚拟存储器管理Page 52022-5-24Operating SystemOperating Systemq存储器的物理组织、多级存储器存储器的物理组织、多级存储器v存储组织是指在存储技术和存储组织是指在存储技术和CPU寻址技术许可的寻址技术许可的范围内组织合理的存储结构。范围内组织合理的存储结构。其依据是访问速度匹配关系、容量要求和价其依据是访问速度匹配关系、容量要求和价格。格。“

5、寄存器寄存器-内存内存-外存外存”结构结构“寄存器寄存器-缓存缓存-内存内存-外存外存”结构；结构；v微机中的存储层次组织：微机中的存储层次组织：访问速度越慢，容量越大，价格越便宜；访问速度越慢，容量越大，价格越便宜；最佳状态应是各层次的存储器都处于均衡的最佳状态应是各层次的存储器都处于均衡的繁忙状态（如：缓存命中率正好使主存读写繁忙状态（如：缓存命中率正好使主存读写保持繁忙）；保持繁忙）；Page 62022-5-24Operating SystemOperating Systemq快速缓存：快速缓存：vData CachevTLB(Translation Lookaside Buffer)

6、q内存：内存：DRAM, SDRAM等；等；q外存：软盘、硬盘、光盘、磁带等；外存：软盘、硬盘、光盘、磁带等；外存(secondary storage)DOS核心命令处理程序内存(primary storage)快速缓存(cache)寄存器(register)Page 72022-5-24Operating SystemOperating Systemq主存储器管理功能主存储器管理功能v存储分配和回收存储分配和回收分配和回收算法及相应的数据结构分配和回收算法及相应的数据结构v地址变换和重定位地址变换和重定位可执行文件生成中的链接技术可执行文件生成中的链接技术程序加载程序加载(装入装入)时的重定

7、位技术时的重定位技术进程运行时硬件和软件的地址变换技术和机构进程运行时硬件和软件的地址变换技术和机构v存储共享和保护存储共享和保护代码和数据共享代码和数据共享地址空间访问权限（读、写、执行）地址空间访问权限（读、写、执行）v存储器扩充：存储器的逻辑组织和物理组织；存储器扩充：存储器的逻辑组织和物理组织；由应用程序控制：覆盖；由应用程序控制：覆盖；由由OS控制：交换（整个进程空间），虚拟存储的请求调入和控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）预调入（部分进程空间）Page 82022-5-24Operating SystemOperating Systemq程序的装

8、入和链接程序的装入和链接 q连续分配方式连续分配方式 q基本分页存储管理基本分页存储管理 q基本分段存储管理基本分段存储管理q虚拟存储器的基本概念虚拟存储器的基本概念q请求分页存储管理方式请求分页存储管理方式q页面置换算法页面置换算法q请求分段存储管理方式请求分段存储管理方式Page 92022-5-24Operating SystemOperating Systemq程序的装入程序的装入q程序的链接程序的链接Page 102022-5-24Operating SystemOperating Systemq多道程序环境下，程序要运行必须为之创建进程，多道程序环境下，程序要运行必须为之创建进程，

9、而创建进程的第一件事就是分配内存而创建进程的第一件事就是分配内存q源程序要运行通常经过源程序要运行通常经过编译（编译（compile）链接链接(link)装入装入(load)等几个步骤等几个步骤库库链接链接程序程序装入模块装入模块装入装入程序程序编译程序产生编译程序产生的目标模块的目标模块第一步第一步第二步第二步第三步第三步内存内存Page 112022-5-24Operating SystemOperating System4.1 程序的装入和链接程序的装入和链接 图 4-1 对用户程序的处理步骤 库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存Page 122022-

10、5-24Operating SystemOperating System4.1.1 程序的装入程序的装入1. 绝对装入方式绝对装入方式(Absolute Loading Mode) 2. 可重定位装入方式可重定位装入方式(Relocation Loading Mode) 3. 动态运行时装入方式动态运行时装入方式(Dynamic Run-time Loading) Page 132022-5-24Operating SystemOperating Systemq绝对装入方式绝对装入方式(Absolute Loading Mode) v事先事先确定确定了程序将了程序将驻留在内存驻留在内存的什么的

11、什么位置位置，即，即在内存中的在内存中的绝对地址绝对地址v装入模块被装入内存后，由于程序中的逻辑地装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，故不需对程序和址与实际内存地址完全相同，故不需对程序和数据的地址进行修改数据的地址进行修改v绝对地址的产生绝对地址的产生程序员直接赋予。不仅要求程序员熟悉内存程序员直接赋予。不仅要求程序员熟悉内存使用情况，而且一旦程序或数据被修改后，使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。通常在程序可能要改变程序中的所有地址。通常在程序中采用符号地址，在编译或汇编时，再将符中采用符号地址，在编译或汇编时，再将符号地址转换为

12、绝对地址。号地址转换为绝对地址。编译或汇编时产生编译或汇编时产生Page 142022-5-24Operating SystemOperating Systemq可重定位装入方式可重定位装入方式(Relocation Loading Mode) v绝对装入方式只能将目标模块装入到内存中事绝对装入方式只能将目标模块装入到内存中事先指定的位置先指定的位置v在多道程序环境下，不可能预知目标模块放在在多道程序环境下，不可能预知目标模块放在内存中的地址，因此绝对装入方式不适合在多内存中的地址，因此绝对装入方式不适合在多道环境下使用道环境下使用v程序中程序中目标模块的地址通常从目标模块的地址通常从0开始开

13、始，其他地，其他地址都是相对于址都是相对于0计算计算相对地址相对地址v把在装入时对目标程序中指令和数据的地址修把在装入时对目标程序中指令和数据的地址修改过程称为改过程称为重定位重定位，又因为，又因为地址变换通常是在地址变换通常是在装入时一次完成装入时一次完成的，以后不再改变，故称为的，以后不再改变，故称为静静态重定位态重定位Page 152022-5-24Operating SystemOperating SystemLOAD 1,2500365365100001100012500150005000250010000作业 地 址空间内 存空 间LOAD 1,12500作业装入内存时的情况作业装

14、入内存时的情况 缺点：不断的分配和回收，造成内存中小空闲块很多，总缺点：不断的分配和回收，造成内存中小空闲块很多，总空闲空间量够，但分配不了空闲空间量够，但分配不了办法：紧凑（移动），但该装入方法不支持办法：紧凑（移动），但该装入方法不支持Page 162022-5-24Operating SystemOperating SystemLOAD 1,25003655000250010000作业地址空间作业地址空间36510000110001250015000内存空间内存空间LOAD 1,1250036520000210002250025000内存空间内存空间LOAD 1,22500将程序加载到将

15、程序加载到10000？将程序移动到将程序移动到20000？Page 172022-5-24Operating SystemOperating Systemq动态运行时装入方式动态运行时装入方式(Denamic Run-time Loading) v可重定位方式不允许程序运行时可重定位方式不允许程序运行时在内存中移在内存中移动位置动位置v动态运行时的装入程序，是在把装入模块装动态运行时的装入程序，是在把装入模块装入内存后，并不立即把装入模块中的相对地入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种址转换为绝对地址，而是把这种地址转换推地址转换推迟到程序真正要迟到程序真正要执行执

16、行时才进行时才进行。因此，。因此，装入装入内存后的所有地址都内存后的所有地址都仍是相对地址仍是相对地址Page 182022-5-24Operating SystemOperating Systemq程序的装入程序的装入q程序的链接程序的链接Page 192022-5-24Operating SystemOperating System4.1 程序的装入和链接程序的装入和链接 图 4-1 对用户程序的处理步骤 库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存Page 202022-5-24Operating SystemOperating System4.1.2 程序的链

17、接程序的链接 1. 静态链接方式静态链接方式(Static Linking) 2. 装入时动态链接装入时动态链接(Load-time Dynamic Linking) 3. 运行时动态链接运行时动态链接(Run-time Dynamic Linking) Page 212022-5-24Operating SystemOperating Systemq静态链接方式静态链接方式(Static Linking) v在程序在程序运行前运行前，先将各目标模块及所需的库函，先将各目标模块及所需的库函数链接成一个完整的装配模块，以后不再拆开数链接成一个完整的装配模块，以后不再拆开v在将这几个目标模块装配成

18、一个装入模块时，在将这几个目标模块装配成一个装入模块时，须解决以下两个问题须解决以下两个问题 对相对地址进行修改对相对地址进行修改 变换外部调用符号变换外部调用符号Page 222022-5-24Operating SystemOperating System模块模块 ACALL B；Return；0L1模块模块 BCALL C；Return；0M1模块模块 CReturn；0N1(a) 目标模块目标模块( (外存外存) )装入前装入前链接修链接修改地址改地址0模块模块 AJSR“L”Return；L1模块模块 BJSR“LM”Return；LLM1LMLMN1模块模块 CReturn；(b)

19、 装入模块装入模块（外存）（外存）Page 232022-5-24Operating SystemOperating Systemq 装入时动态链接装入时动态链接(Loadtime Dynamic Linking) v将用户的源程序编译后所得的一组目标模将用户的源程序编译后所得的一组目标模块在装入内存时采用块在装入内存时采用边装入边链接边装入边链接的方式的方式便于修改和更新便于修改和更新 便于实现对目标模块的共享便于实现对目标模块的共享 Page 242022-5-24Operating SystemOperating System模块模块 ACALL B；Return；0L1模块模块 BCA

20、LL C；Return；0M1模块模块 CReturn；0N1外存外存0模块模块 AJSR“L”Return；L1模块模块 BJSR“LM”Return；LLM1LMLMN1模块模块 CReturn；内存内存装入时装入时链接修链接修改地址改地址Page 252022-5-24Operating SystemOperating Systemq 运行时动态链接运行时动态链接(Run-time Dynamic Linking) v应用程序在每次运行的模块可能不相同应用程序在每次运行的模块可能不相同v运行时动态链接方式将对某些模块的运行时动态链接方式将对某些模块的链接链接推迟到推迟到执行执行时才进行时

21、才进行，即在执行过程中，即在执行过程中，当发现一个被调用模块当发现一个被调用模块尚未装入内存尚未装入内存时，时，立即由立即由OS去找到该模块并将之装入内存，去找到该模块并将之装入内存， 把它链接到调用者模块上把它链接到调用者模块上v凡在执行过程中未被用到的目标模块，都凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，不会被调入内存和被链接到装入模块上，这样不仅可这样不仅可加快程序的装入过程加快程序的装入过程，而且可，而且可节省大量的内存空间节省大量的内存空间Page 262022-5-24Operating SystemOperating System模块模块 ACALL

22、 B；Return；0L1模块模块 BCALL C；Return；0M1模块模块 CReturn；0N1外存外存0模块模块 AJSR“L”Return；L1内存内存执行时执行时链接修链接修改地址改地址Page 272022-5-24Operating SystemOperating Systemq程序的装入和链接程序的装入和链接 q连续分配方式连续分配方式 q基本分页存储管理基本分页存储管理 q基本分段存储管理基本分段存储管理q虚拟存储器的基本概念虚拟存储器的基本概念q请求分页存储管理方式请求分页存储管理方式q页面置换算法页面置换算法q请求分段存储管理方式请求分段存储管理方式Page 2820

23、22-5-24Operating SystemOperating Systemq单一连续分配单一连续分配q固定分区分配固定分区分配q动态分区分配动态分区分配q可重定位分区分配可重定位分区分配q对换（对换（SwappingSwapping）Page 292022-5-24Operating SystemOperating Systemq 连续分配方式为连续分配方式为一个用户一个用户程序分配一个连续的程序分配一个连续的内存空间内存空间q 单一连续分配单一连续分配是最简单的一种存储管理方式，是最简单的一种存储管理方式，但只能用于但只能用于单用户、单任务单用户、单任务的操作系统中的操作系统中q 把内存

24、分为把内存分为v系统区：系统区：OS使用，通常放在内存低址部分使用，通常放在内存低址部分v用户区：用户区：用户可使用的全部内存空间用户可使用的全部内存空间q 存储器保护机构不健全，易造成系统破坏存储器保护机构不健全，易造成系统破坏q 优点：易于管理优点：易于管理q 缺点：对要求内存空间少的程序，造成内存浪缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占费；程序全部装入，很少使用的程序部分也占用内存用内存Page 302022-5-24Operating SystemOperating System用户程序用户程序位于位于RAM中的中的操作系统操作系统0 xFFF

25、.0位于位于RAM中的中的操作系统操作系统用户程序用户程序0ROM中的中的设备驱动程序设备驱动程序用户程序用户程序位于位于RAM中的中的操作系统操作系统0单一连续区存储管理单一连续区存储管理Page 312022-5-24Operating SystemOperating Systemq单一连续分配单一连续分配q固定分区分配固定分区分配q动态分区分配动态分区分配q可重定位分区分配可重定位分区分配q对换（对换（SwappingSwapping）Page 322022-5-24Operating SystemOperating Systemq最简单的可运行最简单的可运行多道程序多道程序的存储管理方

26、式的存储管理方式q内存用户空间划分为若干个内存用户空间划分为若干个固定大小的区域固定大小的区域，每个分，每个分区中只装入区中只装入一道一道作业作业q划分分区的方法划分分区的方法 v分区大小相等分区大小相等：v即使所有的内存分区大小相等即使所有的内存分区大小相等太大：浪费太大：浪费太小：不够用太小：不够用 v分区大小不等分区大小不等：v划分为多个大、中、小搭配的分区划分为多个大、中、小搭配的分区根据程序大小决定所使用的分区根据程序大小决定所使用的分区 大班在大教室、小班在小教室大班在大教室、小班在小教室Page 332022-5-24Operating SystemOperating Syste

27、mq内存分配内存分配 v分区的信息根据分区使用表管理分区的信息根据分区使用表管理2020v使用界地址寄存器使用界地址寄存器v采用静态重定位采用静态重定位问题：并发进程数受分区个数的制约！问题：并发进程数受分区个数的制约！出现：有内存却不能运行程序或大进程无法运行！出现：有内存却不能运行程序或大进程无法运行！Page 342022-5-24Operating SystemOperating Systemq单一连续分配单一连续分配q固定分区分配固定分区分配q动态分区分配动态分区分配q可重定位分区分配可重定位分区分配q对对换（换（SwappingSwapping）Page 352022-5-24Op

28、erating SystemOperating Systemq 根据进程的实际根据进程的实际需要，动态地为需要，动态地为之分配内存空间之分配内存空间q 分配中数据结构分配中数据结构 v空闲分区表空闲分区表 记录每个空闲记录每个空闲分区的情况分区的情况v空闲分区链空闲分区链 实现对空闲分实现对空闲分区的分配和链区的分配和链接接前前向向指指针针N20N个字节可用个字节可用后后向向指指针针N20Page 362022-5-24Operating SystemOperating Systemq 分区分配算法分区分配算法 v首次适应算法首次适应算法FF v循环首次适应算法循环首次适应算法v最佳适应算法最

29、佳适应算法v最差适应算法最差适应算法Page 372022-5-24Operating SystemOperating Systemq 分区分配算法分区分配算法 v首次适应算法首次适应算法FF 空闲分区链以空闲分区链以地址递增顺序地址递增顺序链接链接分配时从分配时从链首开始查找链首开始查找，找到一个大小可满足的，找到一个大小可满足的空闲分区，划出一块给请求者空闲分区，划出一块给请求者优点：简单；优先利用低地址空闲区，保留高地优点：简单；优先利用低地址空闲区，保留高地址大空闲区址大空闲区缺点：会造成在低地址部分很多难以利用的小空缺点：会造成在低地址部分很多难以利用的小空闲分区，查找效率低闲分区，

30、查找效率低v循环首次适应算法循环首次适应算法每次分配时每次分配时从上一次找到从上一次找到空闲分区的空闲分区的下一个空闲下一个空闲区开始查找区开始查找优点：减少查找空闲分区开销，空闲分区分布更优点：减少查找空闲分区开销，空闲分区分布更均匀均匀缺点：缺乏大的空闲区缺点：缺乏大的空闲区Page 382022-5-24Operating SystemOperating Systemv最佳适应算法最佳适应算法空闲区按容量由小到大排序空闲区按容量由小到大排序每次分配时，把能满足要求、又是每次分配时，把能满足要求、又是最小最小的分区分的分区分配给作业配给作业优点：不缺乏大的空闲区优点：不缺乏大的空闲区缺点：

31、会在存储器中留直许多难以利用的小分缺点：会在存储器中留直许多难以利用的小分区区“零头（或碎片）零头（或碎片）”；查找效率低；查找效率低v最差适应算法最差适应算法空闲区按容量由大到小排序空闲区按容量由大到小排序每次分配时，把能满足要求、又是每次分配时，把能满足要求、又是最大最大的分区分的分区分配给作业配给作业优点：剩余的空间最大化，不出现太小的优点：剩余的空间最大化，不出现太小的“零头零头”缺点：缺乏大的空闲区缺点：缺乏大的空闲区首次适应被认为最好、最快，其次是循环，最佳最差首次适应被认为最好、最快，其次是循环，最佳最差（每次分配后剩下小碎片，难再分，不得不经常压缩（每次分配后剩下小碎片，难再分

32、，不得不经常压缩内存，反而浪费内存，反而浪费CPU）Page 392022-5-24Operating SystemOperating Systemq分区分配操作分区分配操作 v分配内存分配内存 从头开始查表从头开始查表检索完否？检索完否？m.sizeu.size?m.sizeu.sizesize?从该分区中划出从该分区中划出u.size大小的分区大小的分区将该分区分配给请求者修将该分区分配给请求者修改有关数据结构改有关数据结构返回返回返回返回继续检索下一个表项继续检索下一个表项将该分区从链中移出将该分区从链中移出YNNYYN解决碎解决碎片问题片问题Page 402022-5-24Operat

33、ing SystemOperating Systemq分区分配操作分区分配操作 v回收内存回收内存v进程运行结束释放内存时，系统根据回收区的进程运行结束释放内存时，系统根据回收区的首地址，把它插入到空闲链表中。根据回收区首地址，把它插入到空闲链表中。根据回收区的位置，有四种情况需处理：的位置，有四种情况需处理：回收区与插入点的回收区与插入点的前一个前一个空闲分区相邻接空闲分区相邻接回收区与插入点的回收区与插入点的后一个后一个空闲分区相邻接空闲分区相邻接 回收区同时与插入点的回收区同时与插入点的前、后前、后两个分区相邻两个分区相邻接接回收区不与任何空闲区邻接回收区不与任何空闲区邻接Page 41

34、2022-5-24Operating SystemOperating System空闲区空闲区回收区回收区回收区回收区空闲区空闲区空闲区空闲区回收区回收区空闲区空闲区回收区回收区情况情况1 1情况情况2 2情况情况3 3情况情况4 4Page 422022-5-24Operating SystemOperating System2) 回收内存 回收区F1F2回收区F2回收区F1回收区回收区Page 432022-5-24Operating SystemOperating Systemq分区式存储管理的优缺点分区式存储管理的优缺点 优点：优点： 便于动态申请内存便于动态申请内存 便于共享内存便于

35、共享内存 便于动态链接便于动态链接 缺点：缺点：碎片问题碎片问题( (外碎片外碎片) )，要求连续的内存空间，要求连续的内存空间，内存利用率不高，受实际内存容量限制内存利用率不高，受实际内存容量限制Page 442022-5-24Operating SystemOperating Systemq碎片问题碎片问题v经过一段时间的分配回收后，内存中存在很多经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空足分配要求；但其总和满足分配要求。这些空闲块被称为碎片闲块被称为碎片v造成存储资源的浪

36、费造成存储资源的浪费q碎片问题的解决碎片问题的解决v紧凑技术：通过在内存移动程序，将所有小的紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域空闲区域合并为大的空闲区域 （紧缩技术，紧致技术，浮动技术，搬家技术）（紧缩技术，紧致技术，浮动技术，搬家技术）v问题：开销大；移动时机问题：开销大；移动时机Page 452022-5-24Operating SystemOperating Systemq单一连续分配单一连续分配q固定分区分配固定分区分配q动态分区分配动态分区分配q可重定位分区分配可重定位分区分配q对换（对换（SwappingSwapping）Page 462022-5-

37、24Operating SystemOperating System4.2.4 可重定位分区分配可重定位分区分配 1. 动态重定位的引入动态重定位的引入 操作系统用户程序110kb用户程序330kb用户程序614kb用户程序926kb80kb用户程序9用户程序6用户程序3用户程序1操作系统Page 472022-5-24Operating SystemOperating Systemq动态重定位的引入动态重定位的引入v连续分配存在的连续分配存在的问题问题必须有足够大的必须有足够大的连续空间才能分连续空间才能分配配v解决方法解决方法：“拼拼接接”或或“紧凑紧凑”的引入的引入操作系统操作系统用户程

38、序用户程序1用户程序用户程序310 KB30 KB用户程序用户程序614 KB用户程序用户程序926 KB操作系统操作系统用户程序用户程序1用户程序用户程序3用户程序用户程序6用户程序用户程序980 KB(a) 紧凑前紧凑前(b) 紧凑后紧凑后Page 482022-5-24Operating SystemOperating Systemq动态重定位的实现动态重定位的实现v作业装入内存后的所有地址仍是作业装入内存后的所有地址仍是相对地址相对地址，将，将相相对地址对地址转换转换成成物理地址物理地址的工作的工作在指令执行时在指令执行时进行进行v需要有硬件地址变换机构的支持需要有硬件地址变换机构的支

39、持LOAD1,25003650100250050002500相相 对对 地地 址址10000重重 定定 位位 寄寄 存存 器器LOAD1,250036510000101001250015000作作 业业 J处处 理理 机机 一一 侧侧存存 储储 器器 一一 侧侧主主 存存Page 492022-5-24Operating SystemOperating System3. 动态重定位分区分配算法动态重定位分区分配算法 动态重定位分区分配算法，与动态分区分配算法基本上相同； 差别仅在于：在这种分配算法中，增加了功能，通常是在找不到足够大的空闲分区来满足用户需求时，进行紧凑。图4-10示出了动态重定

40、位分区分配算法框图。Page 502022-5-24Operating SystemOperating System请请求求分分配配u.size分分区区检检索索空空闲闲分分区区链链( (表表) )找找到到大大于于u.size的的可可用用区区否否? ?按按动动态态分分区区方方式式进进行行分分配配修修改改有有关关的的数数据据结结构构返返回回分分区区号号及及首首批批空空闲闲分分区区总总和和u.size?进进行行紧紧凑凑形形成成连连续续空空闲闲区区修修改改有有关关的的数数据据结结构构否否是是无无法法分分配配返返回回否否q动态重定位分区分配算法动态重定位分区分配算法v在一个分区释放后立即移动在一个分区释

41、放后立即移动v当请求得不到满足时再移动当请求得不到满足时再移动Page 512022-5-24Operating SystemOperating Systemq 可重定位分区的优缺点可重定位分区的优缺点v优点优点: :解决了可变分区分配所引入的解决了可变分区分配所引入的“外零头外零头”问题。问题。消除内存碎片，提高内存利用率。消除内存碎片，提高内存利用率。v缺点缺点: :提高硬件成本，紧凑时花费时间。提高硬件成本，紧凑时花费时间。Page 522022-5-24Operating SystemOperating Systemq单一连续分配单一连续分配q固定分区分配固定分区分配q动态分区分配动态

42、分区分配q可重定位分区分配可重定位分区分配q对换（对换（SwappingSwapping）Page 532022-5-24Operating SystemOperating System4.2.5 对换对换(Swapping) 1. 对换的引入对换的引入 对换（也称交换）技术，最早用在单用户系统，在内存中仅驻留一道用户作业。所有其它作业都驻留在外存的后备队列上，只调入一个作业进入内存运行；此作业的时间片用完时，该作业调至外存，再将后备队列上的另一个作业调入内存；也让它运行一个时间片的时间，然后又将它调出，再调下一个作业进入内存。因为其效率太低，其CPU大约有一半的时间，都处于空闲状态。Page

43、 542022-5-24Operating SystemOperating Systemq对换的引入对换的引入 v所谓所谓“对换对换”，是指把内存中暂时不能运行，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是数据，调入内存。对换是提高内存利用率提高内存利用率的的有效措施有效措施v如果对换是以整个进程为单位，称为如果对换是以整个进程为单位，称为“整体整体对换对换”或或“进

44、程对换进程对换”v如果对换是以如果对换是以“页页”或或“段段”为单位进行的，为单位进行的，则称为则称为“页面对换页面对换”或或“分段对换分段对换”，又统，又统称为称为“部分对换部分对换”Page 552022-5-24Operating SystemOperating System4.2.5 对换对换(Swapping) 1. 对换的引入对换的引入 对换是以整个进程为单位，便称之为，解决内存紧张问题； 对换是以为单位，则分别称之为，又统称为 为了实现进程对换，系统必须能实现以下三方面的功能：（1）对换空间的管理；（2）进程的换出；（3）进程的换入。 Page 562022-5-24Operat

45、ing SystemOperating Systemq对换空间的管理对换空间的管理v外存中对换区主要存放从内存中换出的进程，外存中对换区主要存放从内存中换出的进程，对换空间管理的对换空间管理的主要目标主要目标是是提高进程换入和换提高进程换入和换出的速度出的速度v对换区中空闲盘块的管理对换区中空闲盘块的管理：在系统中配置相应：在系统中配置相应的数据结构，记录外存的使用情况。形式与内的数据结构，记录外存的使用情况。形式与内存在动态分区分配方式中所用数据结构相似，存在动态分区分配方式中所用数据结构相似，即用即用空闲分区表或空闲分区链空闲分区表或空闲分区链。在空闲分区表。在空闲分区表中的每个表目中应包

46、含两项，中的每个表目中应包含两项， 即即对换区的首址对换区的首址及其及其大小大小，它们的单位是盘块号和盘块数，它们的单位是盘块号和盘块数v对换区的分配采用对换区的分配采用连续分配方式连续分配方式，分配算法可，分配算法可以是以是首次适应算法首次适应算法、循环首次适应算法循环首次适应算法或或最佳最佳适应算法适应算法Page 572022-5-24Operating SystemOperating System2. 对换空间的管理对换空间的管理 由于对对换区的分配，是采用连续分配方式，对换区 的回收操作也可分为下述四种情况，即：（1）回收区与插入点的前一分区F1相邻接；（2）回收区与插入点的后一分区

47、F2相邻接；（3）回收区还同时与F1和F2二个分区相邻接；（4）回收区的前、后没有与之相邻接的空闲分区。 对这几种情况的处理方法也与动态分区分配式的方法相同。回收区F1F2回收区F2回收区F1回收区回收区Page 582022-5-24Operating SystemOperating Systemq进程的换出与换入进程的换出与换入v进程的换出进程的换出系统先系统先选择选择处于处于“阻塞阻塞”状态状态且且优先级最低优先级最低的进程作为换出进程，然后启动盘块，将该的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的进程的程序和数据传送到磁盘的对换区对换区上。上。若传送未出现错误，便

48、回收其所占用的内存若传送未出现错误，便回收其所占用的内存空间，并对该进程的空间，并对该进程的进程控制块进程控制块做相应的修做相应的修改改v进程的换入进程的换入系统应定时地查看所有进程的状态，从中找系统应定时地查看所有进程的状态，从中找出出“就绪就绪”状态状态但已换出的进程，将其中但已换出的进程，将其中换换出时间出时间(换出到磁盘上换出到磁盘上)最久最久的进程作为换入的进程作为换入进程，将之换入，直至已无可换入的进程或进程，将之换入，直至已无可换入的进程或无可换出的进程为止无可换出的进程为止Page 592022-5-24Operating SystemOperating Systemq 可重定

49、位分区的优缺点可重定位分区的优缺点v优点优点: :解决了可变分区解决了可变分区分配所引入的分配所引入的“外零头外零头”问题。问题。消除内存碎片，消除内存碎片，提高内存利用率。提高内存利用率。v缺点缺点: :提高硬件成本，提高硬件成本，紧凑时花费时间。紧凑时花费时间。操作系统操作系统用户程序用户程序1用户程序用户程序310 KB30 KB用户程序用户程序614 KB用户程序用户程序926 KB操作系统操作系统用户程序用户程序1用户程序用户程序3用户程序用户程序6用户程序用户程序980 KB(a) 紧凑前紧凑前(b) 紧凑后紧凑后Page 602022-5-24Operating SystemOp

50、erating Systemq多重分区多重分区v即一个程序可以占据主存中不连续的多个分即一个程序可以占据主存中不连续的多个分区区可以解决碎片问题可以解决碎片问题v支持结构化程序设计，操作系统往往把一道支持结构化程序设计，操作系统往往把一道作业分成若干片段如子程序、主程序、数据作业分成若干片段如子程序、主程序、数据组等。组等。v需要硬件支持（多对界地址寄存器，需要硬件支持（多对界地址寄存器，重定位重定位寄存器寄存器）v管理复杂管理复杂Page 612022-5-24Operating SystemOperating Systemq多重分区多重分区 Page 622022-5-24Operatin