操作系统第五章.ppt

《操作系统第五章.ppt》由会员分享，可在线阅读，更多相关《操作系统第五章.ppt（98页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第第第第5 5章章章章 存储管理存储管理存储管理存储管理相关概念：相关概念：内存和外存内存和外存 计计算算机机系系统统中中的的存存储储器器可可分分为为两两种种：内内存存储储器器（内内存存）和和辅辅助助存存储储器器（外外存存）。内内存存可可被被CPUCPU直直接接访访问问，而而后后者者不不能能，外外存存与与CPUCPU之之间间只只能能在在输输入入输输出出的的控控制系统的管理下，进行信息交换。制系统的管理下，进行信息交换。5.1 5.1 5.1 5.1 虚拟存储器虚拟存储器虚拟存储器虚拟存储器虚拟存储器的产生原因虚拟存储器的产生原因 在在早早期期的的计计算算机机存存储储管管理理方方案案中中要要求求

2、把把作作业业“一一次次全全部部装装入入”到到内内存存，这这就就带带来来了了一一个个很很大大的的问问题题；如如果果一一个个作作业业太太大大，以以至至于于内内存存都都容容纳纳不不下下，那那么么，这这个个作作业业就就无无法法投投入入运运行行。因因此此小小内内存存和和大大作作业业之之间间存存在在着着的的这这个个矛矛盾盾，在在多多道道程程序序设设计计时时，当当要要求求内内存存中中存存在在多多个个作作业业程程序序时时，就就更更显显得得突突出出了了。虚虚拟拟存存储储器的概念就在这样的背景下产生了。器的概念就在这样的背景下产生了。虚拟存储器的概念虚拟存储器的概念虚拟存储器的概念虚拟存储器的概念 虚虚拟拟存存储

3、储器器是是一一种种扩扩大大内内存存容容量量的的设设计计技技术术，她她把把辅辅助助存存储储器器作作为为计计算算机机内内存存存存储储器器的的后后援援。当当作作业业提提交交给给系系统统时时，首首先先进进入入辅辅存存，运运行行时时，只只将将其其中中有有关关部部分分装装入入内内存存，其其他他部部分分仍仍在在辅辅存存中中，当当运运行行过过程程中中需需要要用用到到不不存存在在内内存存的的信信息息时时，再再把把它它们们调调入入，以以保保证证程程序序的的正正常常运运行行。这这样样一一个个看看上上去去容容量量很很大大、但但实实际际上上不不存存在在的的大大存存储储器器，就就被被称称为为“虚拟存储器虚拟存储器”。地址

4、变换的问题地址变换的问题地址变换的问题地址变换的问题1 1、什么是内存物理地址？、什么是内存物理地址？内内存存是是由由一一个个个个存存储储单单元元组组成成，这这些些内内存存单单元元按按照照一一定定顺顺序序编编号号，称称为为该该单单元元的的地地址址。我我们们把把这这些些“单单元元地地址址”称称为为“绝绝对对地地址址”或或“物理地址物理地址”。2 2、什么是逻辑地址？、什么是逻辑地址？用用户户的的源源程程序序经经过过编编译译程程序序的的加加工工，产产生生出出相相对对于于“0”“0”编编址址的的目目标标程程序序，再再经经过过连连接接装装配配，产产生生出出一一个个”0”0”编编址址的的更更大大的的地地

5、址址空空间间。这这个个地地址址空空间间被被称称为为是是用用户户程程序序的的“相相对地址空间对地址空间”或或“逻辑地址空间逻辑地址空间”。3 3、地址是怎样变换的？、地址是怎样变换的？当当程程序序执执行行时时，需需要要装装入入内内存存中中，但但是是此此时时程程序序中中的的指指令令地地址址是是“相相对对地地址址”，要要使使程程序序正正常常运运行行，需需要要将将“相相对对地地址址”变变换换成成“绝绝对地址对地址”，如：，如：XXXXXCall 10001001KB2KB3KB3000 用户程序的虚地址空间(a)(b)20KB+100 20KB+30001000 20KB 23KB 22KB 操作系统

6、 XXXXXX Call 100 21KB内存 1000 20KB 23KB 22KB 操作系统 XXXXXX Call 20580 20KB+100 20KB+3000 21KB内存(c)25KB22KB24KB 操作系统 XXXXXX Call 22628 020KB22KB+10022KB+300023KB内存(d)图5-1 地址变换示意图 其中程序其中程序A A中的一条入口地址为中的一条入口地址为30003000的一条指令的一条指令为为“call 100”,call 100”,在装入内存之后，由于程序的启始地址不在装入内存之后，由于程序的启始地址不再为再为“0”“0”，故程序中的指令需

7、要做相应的转换。在上图，故程序中的指令需要做相应的转换。在上图中中 所所 示示 的的 情情 况况 中中，“call call 100”100”变变 成成 了了“call call 2KB+100”2KB+100”。因此在操作系统中，把用户程序指令中的相对地址变因此在操作系统中，把用户程序指令中的相对地址变换成所在绝对地址空间中的绝对地址的过程，称为换成所在绝对地址空间中的绝对地址的过程，称为“地地址址重重定定位位”。“地地址址的的重重定定位位”可可分分为为“静静态态地地址址重重定定位位”和和“动态地址重定位动态地址重定位”。静态地址重定位静态地址重定位静态地址重定位静态地址重定位 在在程序运行

8、之前程序运行之前，就为用户程序实行了地址重定位的工作，就为用户程序实行了地址重定位的工作，称这种地址重定位为称这种地址重定位为“静态重定位静态重定位”。该重定位方法有如下的特。该重定位方法有如下的特 点点:1)静态重定位是在程序运行之前完成地址重定位工作的。静态重定位是在程序运行之前完成地址重定位工作的。2)静态重定位由软件实现，无须硬件提供支持。静态重定位由软件实现，无须硬件提供支持。3)实行静态重定位时，地址重定位工作是在装入时被一次集实行静态重定位时，地址重定位工作是在装入时被一次集 中完成的。中完成的。4)只完成了一个只完成了一个首地址不同的连续地址转换首地址不同的连续地址转换，要求连

9、续的内存，要求连续的内存 空间空间 5)一次性装入不再移动，无法实现虚拟存储一次性装入不再移动，无法实现虚拟存储 动态地址重定位：（1）方法：在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址变成内存地址，动 态重定位依靠硬件地址变换机构完成。（2）动态地址重定位机构 基地址寄存器BR（始址）、虚地址寄存器 VR偏移）则：内存地址MA MA=（BR）+（VR）其中括号表示取寄存器值（3）址映射过程：）址映射过程：设置基地址寄存器设置基地址寄存器BR，虚地址寄存器，虚地址寄存器VR将程序段装入内存，将其占用的区域的首地址送将程序段装入内存，将其占用的区域的首地址送BR；在程序执行过

10、程中，将要访问的虚地址送入在程序执行过程中，将要访问的虚地址送入VR中；中；地址变换机构把地址变换机构把VR和和BR的内容相加，得访问的物的内容相加，得访问的物理地址理地址（4）动态重定位优点：）动态重定位优点：可以对内存进行可以对内存进行非连续分配（非连续分配（各个程序分段的首地址各个程序分段的首地址）动动态态重重定定位位提提供供了了实实现现虚虚拟拟存存贮贮器器的的基基础础（不不要要求求一一次次性性装装入入，不不要求连续空间，可运行时部分和动态的分配空间要求连续空间，可运行时部分和动态的分配空间）有利于程序段共享（有利于程序段共享（将可共享程序段，分配共享的存储空间将可共享程序段，分配共享的

11、存储空间）关于动态地址重定位可以如下图所示的过程说明：关于动态地址重定位可以如下图所示的过程说明：关于动态地址重定位可以如下图所示的过程说明：关于动态地址重定位可以如下图所示的过程说明：03456.LOADA200.0100200300.LOADA2003456110012001300200VR+1000BR现在将地址的静态重定位和动态重定位做一个综合比较：现在将地址的静态重定位和动态重定位做一个综合比较：（1）地址转换时刻：静态地址重定位在程序运行之前完成）地址转换时刻：静态地址重定位在程序运行之前完成 地址转换的；动态地址重定位却是将地址转换的时刻地址转换的；动态地址重定位却是将地址转换的

12、时刻 推迟到指令执行时进行推迟到指令执行时进行的。的。（2）谁来完成任务：静态地址重定位是由）谁来完成任务：静态地址重定位是由软件软件完成地址转完成地址转 换工作的；动态地址重定位则由一套硬件提供的地址换工作的；动态地址重定位则由一套硬件提供的地址 转换机构来完成。转换机构来完成。（3）完成的形式：静态地址重定位是在装入时一）完成的形式：静态地址重定位是在装入时一次集中地次集中地 把程序指令中所有要转换的地址全部加以转换把程序指令中所有要转换的地址全部加以转换；而动；而动 态地址重定位则是态地址重定位则是每执行一条指令时，对其地址加以每执行一条指令时，对其地址加以 转换转换。（4）完成的结果：

13、实行静态重定位，）完成的结果：实行静态重定位，原来的指令地址部分原来的指令地址部分 被修改被修改；实行动态地址重定位，只是按照所形成的地；实行动态地址重定位，只是按照所形成的地 址去执行这条指令，址去执行这条指令，并不对指令本身做任何修改并不对指令本身做任何修改。内外存数据传输的控制的问题内外存数据传输的控制的问题内外存数据传输的控制的问题内外存数据传输的控制的问题 内存大小总是有限的，而程序的大小是无内存大小总是有限的，而程序的大小是无 法限制的，所以我们需要对内存进行扩充。此法限制的，所以我们需要对内存进行扩充。此 时就提出了一个问题：按什么样的方式来控制时就提出了一个问题：按什么样的方式

14、来控制 内存和外存之间的数据流动呢？最基本的控制内存和外存之间的数据流动呢？最基本的控制 方法有两种：方法有两种：“用户程序控制用户程序控制”和和“操作系统控操作系统控 制制”。“用户程序控制用户程序控制”方法的例子是方法的例子是“覆盖覆盖”。“覆盖覆盖”技术的实质可以使用下例来说明：技术的实质可以使用下例来说明：用用户户程程序序的的调调用用结结构构如如图图(a)a)所所示示，通通过过连连接接装装配配的的处处理理，该该作作业业将将形形成成一一个个需需要要存存储储量量180180KBKB的的相相对对地地址址空空间间，如如图图(b)b)所所示示。由由于于程程序序中中的的若若干干子子程程序序不不可可

15、能能同同时时调调用用，所所以以我我们们可可以以按按照照图图(c)c)分分配配内内存存空空间间，此时将此时将5050KBKB和和4040KBKB的存储区称为覆盖区。的存储区称为覆盖区。继续继续MAIN(10KB)A(50KB)B(30KB)C(30KB)D(20KB)E(40KB)(a)180K0(b)连接装配连接装配MIAN(10KB)A(50KB)B(30KB)C(30KB)D(20KB)E(40KB)MAINA或或BC或或D或或E(c)50KB40KB10KB覆盖技术程序示例覆盖技术程序示例返回返回操作系统控制方式可以分为两种：操作系统控制方式可以分为两种：“交换交换”和和“请求调入和预调

16、入请求调入和预调入”方式。方式。“交换交换”方式的示意图入下所示，包括换进与换出，它是方式的示意图入下所示，包括换进与换出，它是指指由操作系统把那些在内存中处于等待状态的进程换出内由操作系统把那些在内存中处于等待状态的进程换出内存，以及把那些等待事件已经发生，处于就绪态的进程换存，以及把那些等待事件已经发生，处于就绪态的进程换入内存，以及那些即将执行的程序数据调入内存入内存，以及那些即将执行的程序数据调入内存辅助存储器辅助存储器作业作业1 1作业作业2 2作业作业3 3换出换出换入换入图图5-45-4内外存之间的交换示意图内外存之间的交换示意图操作系统操作系统用户区用户区内存内存请求调入方式请

17、求调入方式：在程序执行时，如访问的程序段或数据段不在内存在程序执行时，如访问的程序段或数据段不在内存中，则操作系统自动地从外存将有关程序、数据调入中，则操作系统自动地从外存将有关程序、数据调入内存。内存。预调入方式预调入方式：由由OS预测预测在不远的将来会访问到的那在不远的将来会访问到的那些程序、数据部分，并在他们被访问之前由系统选择些程序、数据部分，并在他们被访问之前由系统选择适当的时机将它们调入内存的方法适当的时机将它们调入内存的方法。评价：评价：交换技术只是将整个进程换入换出，无法实现自动覆盖、交换技术只是将整个进程换入换出，无法实现自动覆盖、内内外外存存统统一一管管理理，进进程程大大小

18、小也也受受内内存存容容量量限限制制。不不利利于于虚虚拟拟内内存存管理管理内存的分配与回收的问题内存的分配与回收的问题内存的分配与回收的问题内存的分配与回收的问题 内内存存的的分分配配与与回回收收使使内内存存管管理理的的主主要要功功能能之之一一，为为了了合合理理利利用用内内存存，设设计计内内存存的的分分配和回收方法时，必须考虑的因素：配和回收方法时，必须考虑的因素：一、分配结构一、分配结构 二、放置策略二、放置策略 三、交换策略三、交换策略 四、调入策略四、调入策略 五、回收策略五、回收策略内存信息的共享与保护的问题内存信息的共享与保护的问题内存信息的共享与保护的问题内存信息的共享与保护的问题

19、在在多多道道程程序序设设计计的的环环境境下下，内内存存中中的的许许多多用用户户或或系系统统程程序序可可以以提提供供不不同同的的用用户户进进程程共共享享。为为了了防防止止用用户户程程序序与与用用户户程程序序之之间间，以以及及用用户户程程序序与与系系统统程程序序之之间间的的干干扰扰和和破破坏坏，我我们们必必须须对对内内存存内内进进行行保保护护。常常见见的的内内存存保保护护法法是是“上上下下界界存存储储保保护护法法”。即即在在CPUCPU中中设设置置一一对对专专用用的的寄寄存存器器上上界界寄寄存存器器和和下下界界寄寄存存器器，如如下下图图所所示：示：0 0a ab bc cd d第第1 1分区分区第

20、第2 2分区分区第第3 3分区分区 a a b b上界寄存器上界寄存器下界寄存器下界寄存器操作系统操作系统作业作业1 1作业作业2 2作业作业3 3 上下界寄存器保护法示意图上下界寄存器保护法示意图 当系统调度到哪一个作业进程运行时，就把该作业在内存当系统调度到哪一个作业进程运行时，就把该作业在内存中的中的低端地址装入下界寄存器低端地址装入下界寄存器，把，把高端地址装入上界寄存器高端地址装入上界寄存器，在运行作业在运行作业1 1时，硬件自动检测指令中的地址，时，硬件自动检测指令中的地址，若超出若超出a a或或b,b,则会产生出错中断则会产生出错中断。适合静态地址定位，连续空间适合静态地址定位，

21、连续空间保护键法保护键法：方法：为每一个被保护存贮块分配一个单独的方法：为每一个被保护存贮块分配一个单独的保护键。保护键。在程序状态字中设置相应的保护键开关字在程序状态字中设置相应的保护键开关字段，对不同进程赋予不同的开关代码，与保护的段，对不同进程赋予不同的开关代码，与保护的存贮块中的保护键匹配，保护键可设置成对存贮块中的保护键匹配，保护键可设置成对RW同时进行保护或只对同时进行保护或只对R、W进行单独保护的。如进行单独保护的。如果果开关字与保护键匹配开关字与保护键匹配或或存贮块未受到保护存贮块未受到保护，则，则访问该存贮块是允许的，否则产生访问出错中断访问该存贮块是允许的，否则产生访问出错

22、中断例子见例子见P1143、界限寄存器与界限寄存器与CPU的用户态或核态工作方式相结合的用户态或核态工作方式相结合的保护方式的保护方式在这种方式下，用户态进程只能访问那些在这种方式下，用户态进程只能访问那些在界限寄存在界限寄存器所规定范围内器所规定范围内的内存部分，而核心态进程则可以访的内存部分，而核心态进程则可以访问整个内存区域。问整个内存区域。5.2 5.2 5.2 5.2 分区存储管理分区存储管理分区存储管理分区存储管理基本原理：基本原理：操作系统为操作系统为每一个进程每一个进程划分一块适当大小的存划分一块适当大小的存储储区区，用用来来连连续续存存放放进进程程的的程程序序和和数数据据（但

23、但作作业业和和程程序序可可能能是是分分段段的的），使使各各进进程程能能并并发发执执行行。分分区区管管理理可可以以分分为为“固固定定分分区区”和和“动态分区动态分区”两种方法。两种方法。固定分区法固定分区法固定分区法固定分区法思想：思想：操操作作系系统统将将内内存存区区划划分分成成大大小小不不等等的的若若干干连连续续分分区区，每每个个分分区区尺尺寸寸在在划划分分后后保保持持不不变变。系系统统对对内内存存的的管管理理通通过过数数据据结结构构：分分区区说说明明表表实实现现。分分区区说说明明表表说说明明：各各个个分分区区区区号，分区大小，起始地址，状态号，分区大小，起始地址，状态。继续继续 需要的数据

24、结构：需要的数据结构：操作系统设置一张操作系统设置一张“分区说明表分区说明表”，用来记录各分区的信息及当前，用来记录各分区的信息及当前 的使用情况。如表所示：的使用情况。如表所示：分区号分区号 起始地址起始地址 长度长度 使用标志使用标志 1 1 20 20KBKB 8 8KBKB 作业作业1 1 2 2 28 28KBKB 32 32KBKB 作业作业6 6 3 3 60 60KBKB 64 64KBKB 0 0 4 4 124 124KBKB 132 132KBKB 作业作业2 2当需要装一个作业入内存时，系统的步骤为：当需要装一个作业入内存时，系统的步骤为：扫描分区分配表，找到标志为扫描

25、分区分配表，找到标志为“0”“0”的分区。的分区。比较作业尺寸与该分区的长度，若能容纳该比较作业尺寸与该分区的长度，若能容纳该 作业，则分配给该作业。作业，则分配给该作业。修改分区分配表中该分区的标志为修改分区分配表中该分区的标志为“非非0”0”。分区的分配与释放分区的分配与释放分区的分配与释放分区的分配与释放 分区的分配：分区的分配：若若采采用用的的是是一一个个队队列列的的管管理理方方案案，则则当当一一个个分分区区空空间间被被释释放放时，需要在时，需要在队列中选出一个作业运行队列中选出一个作业运行，可以有以下几种方案：，可以有以下几种方案：（1 1）选选出出第第一一个个可可容容纳纳的的作作业

26、业。该该方方案案虽虽然然实实现现简简单单，选选择择率率高高，但但是是可可能能会会因因为为一一个个小小作作业业进进入入而而浪浪费费掉掉该该分分区区的的大大部部分分存储空间存储空间，存储利用率不高。，存储利用率不高。（2 2）在在队队列列中中找找出出该该分分区区能能容容纳纳的的最最大大的的作作业业。由由于于每每个个分分配配出出的的分分区区产产生生出出的的内内部部碎碎片片小小，因因此此，此此方方案案存存储储空空间间的的利利用用率高；缺点是率高；缺点是对小作业不公平对小作业不公平。分区的释放：分区的释放：当作业运行结束时，在分区分配表中找到它使用的当作业运行结束时，在分区分配表中找到它使用的表目，将该

27、表目的标志置为表目，将该表目的标志置为“0”“0”。地址重定位与存储保护地址重定位与存储保护:在固定分区方案中，每个分区只能装入一个作业，在固定分区方案中，每个分区只能装入一个作业，故应该对程序实行故应该对程序实行静态重定位静态重定位。即操作系统将一个分。即操作系统将一个分区分配给某个作业时，装入程序就把该作业程序指令区分配给某个作业时，装入程序就把该作业程序指令中的相对地址与分区的起始地址相加，得到绝对地址。中的相对地址与分区的起始地址相加，得到绝对地址。该该分分区区管管理理方方法法的的存存储储保保护护使使用用“上上下下界界存存储储保保护护法法”。动态分区法动态分区法 思想：思想：动动态态分

28、分区区在在作作业业执执行行前前不不建建立立分分区区，分分区区的的建建立立是是在在作作业业的的处处理理过过程程中中进进行行的的。内内存存分分区区的的建建立立是是在在作作业业的的处处理理过过程程中中进进行行的的，大大小小可可随随作作业业的的大大小小变变化化，这这就就改改变变了了固固定定分分区区中中小小作作业业也也要占据大内存的现象要占据大内存的现象，从而提高了内存的利用率。，从而提高了内存的利用率。动态分区的工作过程可用以下示意图说明动态分区的工作过程可用以下示意图说明:(a)a)操作系统操作系统内存内存0 02020KBKB空闲区空闲区(236(236KB)KB)256256KBKB 作业作业A

29、 A(16KB)(16KB)作业作业B B(100KB)(100KB)作业作业C C(70KB)(70KB)作业作业D D(75KB)(75KB)空闲区空闲区(220(220KB)KB)作业作业A A(16(16KB)KB)操作系统操作系统内存内存0 02020KBKB256256KBKB 作业作业B B(100KB)(100KB)作业作业C C(70KB)(70KB)作业作业D D(75KB)(75KB)36KB36KB(b)b)继续继续 作业作业C C(70KB)(70KB)作业作业D D(75KB)(75KB)操作系统操作系统内存内存0 02020KBKB256256KBKB 作业作业A

30、 A(16KB)(16KB)36KB36KB(c)c)作业作业B B(100KB)(100KB)空闲区空闲区(120KB)(120KB)136KB136KB 作业作业D D(75KB)(75KB)操作系统操作系统内存内存0 02020KBKB256256KBKB 作业作业A A(16KB)(16KB)36KB36KB(d)d)作业作业B B(100KB)(100KB)空闲区空闲区(50KB)(50KB)136KB136KB 作业作业C C(70KB)(70KB)206KB206KB继续 作业作业D D(75KB)(75KB)操作系统操作系统内存内存0 02020KBKB256256KBKB 作

31、业作业A A(16KB)(16KB)36KB36KB(e)e)空闲区空闲区(100KB)(100KB)空闲区空闲区(50KB)(50KB)136KB136KB 作业作业C C(70KB)(70KB)206KB206KB 操作系统操作系统内存内存0 02020KBKB256256KBKB 作业作业A A(16KB)(16KB)36KB36KB(e)e)空闲区空闲区(100KB)(100KB)空闲区空闲区(50KB)(50KB)136KB136KB 作业作业C C(70KB)(70KB)206KB206KB(f)f)操作系统操作系统内存内存0 02020KBKB256256KBKB 作业作业A A

32、(16KB)(16KB)36KB36KB空闲区空闲区(25KB)(25KB)空闲区空闲区(50KB)(50KB)136KB136KB 作业作业C C(70KB)(70KB)206KB206KB 作业作业D D(75KB)(75KB)111KB111KB图图 动态分区存储管理的工作过程动态分区存储管理的工作过程作业作业B完成完成 可可以以看看出出,随随着着作作业业对对内内存存的的的的不不断断申申请请与与释释放放,分分区区的的数数目目不不断断增增加加,每每个个分分区区的的尺尺寸寸在在不不断断减减小小,这这种种情情况况持持续续下下去去,就就会会导导致致存存在在很很多多尺尺寸寸极极小小的的分分区区,这

33、这些些分分区区分分配配不不出出去去,就就形形成成了了”外外部部碎碎片片”。解决这个问题的方法就是解决这个问题的方法就是“空闲区的合并空闲区的合并”。当当内内存存中中的的一一个个分分区区被被释释放放时时，与与它它前前后后相相邻邻接接的的分分区区可可能能会会有有四种关系出现。如下图：四种关系出现。如下图：/上空闲区上空闲区释放区释放区下空闲区下空闲区/上空闲区上空闲区释放区释放区/释放区释放区下空闲区下空闲区/释放区释放区/(a)a)(b)b)(c)c)(d)d)（1 1）图图(a)a)表表示示释释放放区区的的前前后后都都是是空空闲闲区区，因因此此合合并并后后的的空空闲闲区区的的首首地地址址就就是

34、是上上空空闲闲区区的的起起始始地地址址，长长度度为为三三个个分分区区的的长长度度总总和。和。（2 2）图图(b)b)表表示示释释放放区区的的前前面面是是空空闲闲区区，合合并并后后的的空空闲闲区区的的首首地址就是上空闲区的起始地址，长度为两个个分区的长度总和。地址就是上空闲区的起始地址，长度为两个个分区的长度总和。（3 3）图图(c)c)中中表表示示释释放放区区的的后后面面是是空空闲闲区区，合合并并后后的的空空闲闲区区的的首地址就是该释放区的起始地址，长度为两个分区的长度总和。首地址就是该释放区的起始地址，长度为两个分区的长度总和。（4 4）图）图(d)d)中表示释放区的前后都不是空闲区，无合并

35、情况。中表示释放区的前后都不是空闲区，无合并情况。动态分区的管理与组织用到的数据结构动态分区的管理与组织用到的数据结构动态分区的管理与组织用到的数据结构动态分区的管理与组织用到的数据结构动态分区的管理与组织常用的两种方法为：动态分区的管理与组织常用的两种方法为：表格法、链表法表格法、链表法.表格法：表格法：在表格法中需要用到的数据结构为：在表格法中需要用到的数据结构为：可用表可用表和和请求表请求表区号区号分区长度分区长度起始地址起始地址1 11616K K4040K K2 22424K K7878K K3 39 9K K100100K K进程号进程号请求大小请求大小P1P11313K KP2P

36、22020K K可用表可用表请求表请求表分区并非分区并非紧密相连紧密相连 分区的分配与回收分区的分配与回收 （1 1）扫描请求表，读出表中的请求空间的某个进程。扫描请求表，读出表中的请求空间的某个进程。（2 2）将进程的请求长度与可用表中的每个可用分区大将进程的请求长度与可用表中的每个可用分区大 小进行比较，找到合适的空闲区，分配给该进程。小进行比较，找到合适的空闲区，分配给该进程。（3 3）更新可用表更新可用表（分区起始地址和长度更改）（分区起始地址和长度更改）和请求表。和请求表。（4 4）进程释放空间时，将相邻的空闲区进行联结合并，进程释放空间时，将相邻的空闲区进行联结合并，更新可用表。更

37、新可用表。链表法链表法 链链表表法法是是利利用用每每个个内内存存空空闲闲区区的的头头几几个个单单元元存存放放本本空空闲闲区区的的大大小小及及下下一一个个空空闲闲区区的的起起始始地地址址，从从而而将将所所有有的的空空闲闲区区链链接接起起来来。空闲区的示意图如空闲区的示意图如(a)a)所示，链表如图所示，链表如图(b)b)所示。所示。空闲区 size next(a)(b)8KB 60KB 32KB 212KB 300KB NULL20KB链首指针空闲分区组成的链表分区的分配与回收分区的分配与回收 （1 1）扫描请求表，读出表中的请求空间的某个进程。）扫描请求表，读出表中的请求空间的某个进程。（2

38、2）搜索链表，找到合适的空闲区，分配给该进程。）搜索链表，找到合适的空闲区，分配给该进程。（3 3）更新链表。）更新链表。（4 4）进程释放空间时，将相邻的空闲区进行联结合并，）进程释放空间时，将相邻的空闲区进行联结合并，更新链表。更新链表。在上述分区分配过程中的步骤在上述分区分配过程中的步骤(2)(2)，寻找合适的分区常用，寻找合适的分区常用 的方法有以下三种：的方法有以下三种：（1 1）最先适应算法）最先适应算法 把把最最先先找找到到的的、满满足足存存储储需需要要的的空空闲闲分分区区作作为为分分配配的的 对对象象。优优点点：查查找找时时间间短短，实实现现简简单单；缺缺点点：容容易易将将大大

39、的的分分区区分分割割成成小小块块，对对大大作作业业不不利利。链链表表按按照照空空间间在在内内存存中中位位置置的的先先后后顺顺序序组织组织 （2 2）最佳适应算法）最佳适应算法 从从当当前前所所有有空空闲闲区区中中找找出出一一个个能能够够满满足足存存储储需需求求的的、最最小小的的空空闲闲区区作作为为分分配配的的对对象象。优优点点：保保证证了了大大作作业业的的需需求求。缺缺点点：容容易易形形成成小小的的碎碎片片空空闲闲区区，不不容容易易分分配配。链链表表按按照照空空间间大大小小（从从小小到大）组织到大）组织 （3 3）最坏适应算法）最坏适应算法 从从当当前前所所有有空空闲闲区区中中找找出出满满足足

40、需需求求的的、最最大大的的空空闲闲区区作作为为分分配配对对象象。优优点点：每每次次分分配配剩剩余余空空间间充充足足，不不留留下下碎碎片片空空闲闲区区。链链表按照空间大小（从大到小）组织表按照空间大小（从大到小）组织三种策略的评价和比较三种策略的评价和比较P119（1）查找速度）查找速度（2）释放速度）释放速度（3）空闲利用）空闲利用动态分区存储管理的特点：动态分区存储管理的特点：动态分区存储管理的特点：动态分区存储管理的特点：(1)(1)作业一次性全部装入到一个连续的存储分区中。作业一次性全部装入到一个连续的存储分区中。(2)(2)分区是按照作业对内存的需求来划分的，因此，不分区是按照作业对内

41、存的需求来划分的，因此，不 会会出出现现内内部部碎碎片片（内内部部碎碎片片就就是是已已经经被被分分配配出出去去（能能明明确确指指出出属属于于哪哪个个进进程程）却却不不能能被被利利用用的的内内存存空空间间）的问题。的问题。(3)(3)有硬件支持，实现指令地址的动态重定位。有硬件支持，实现指令地址的动态重定位。动态分区管理的缺点：动态分区管理的缺点：(1)(1)没没有有解解决决小小内内存存运运行行大大作作业业的的问问题题（仍仍然然是是仅仅依赖内存）仅仅依赖内存）。(2)(2)虽然避免了内部碎片，但是会引起极小的分虽然避免了内部碎片，但是会引起极小的分 区区难难以以得得到到利利用用，形形成成外外部部

42、碎碎片片（外外部部碎碎片片指指的的是是还还没没有有被被分分配配出出去去（不不属属于于任任何何进进程程），但但由由于于大大小小太太小小了了无无法法分分配配给给申申请请内内存存空空间的新进程的内存空闲区域）间的新进程的内存空闲区域）。分区管理的优点：分区管理的优点：(1)(1)现了多个作业对内存的共享，提高了系统的资源利用率。现了多个作业对内存的共享，提高了系统的资源利用率。(2)(2)要求硬件支持少，算法简单，易实现。要求硬件支持少，算法简单，易实现。缺点：缺点：(1)(1)内存利用率不高，内存中存在严重的碎片。内存利用率不高，内存中存在严重的碎片。(2)(2)作业受分区大小的限制。作业受分区大

43、小的限制。(3)(3)难以实现各分区的信息共享。难以实现各分区的信息共享。作业：作业：如如图图(a)a)所所示示，现现在在有有两两个个空空闲闲分分区区，是是111111KB-KB-161KB161KB，一一个个是是231231KB-256KBKB-256KB。作作业业D D到到达达，提提出出存存储储需需求求2020KBKB，问问：如如果果系系统统实实行行最最先先适适应应算算法法、最最佳佳适适应应算算法法、最最坏坏适适应应算算法法时时，分分别别应应该该把把哪哪一一个个空空闲闲区区分分配配给给它它？分分配配后后的的内内存存情情形形用用图图形形标标出出。(此此时时内内 0 0存存空空闲闲区区采采用用

44、链链表表法法管管理理，空空闲闲区区按按照照地地址址递递增增顺顺序序排排列列)。操作系统操作系统作业作业A A的分区（的分区（1616K K）作业作业B B的分区（的分区（7575K K）空闲区（空闲区（5050K K）作业作业C C的分区（的分区（7070K K）空闲区（空闲区（2525K K）0 02020K K3636K K111111K K161161K K231231K K256256K K(a)a)操作系统操作系统 作业作业A A的分区（的分区（1616K K）作业作业B B的分区（的分区（7575K K）空闲区（空闲区（3030K K）作业作业C C的分区（的分区（7070K K）

45、空闲区（空闲区（2525K K）0 02020K K3636K K111111K K161161K K231231K K256256K K(b)b)作业作业D D的分区（的分区（2020K K）131131K K 操作系统操作系统 作业作业A A的分区（的分区（1616K K）作业作业B B的分区（的分区（7575K K）空闲区（空闲区（5050K K）作业作业C C的分区（的分区（7070K K）空闲区（空闲区（2525K K）0 02020K K3636K K111111K K161161K K231231K K256256K K(c)c)作业作业D D的分区（的分区（2020K K）25

46、1251K K 答：答：当当系系统统采采取取最最先先适适应应算算法法时时，两两个个空空闲闲区区都都能能满满足足作作业业D D的的需需求求，此此时时系系统统按按照照空空闲闲区区地地址址递递增增的的顺顺序序构构成成链链表表，则则最最先先搜搜索索到到的的空空闲闲区区应应该该是是大大小小为为5050KBKB的空闲区，此时分配后的内存的空闲区，此时分配后的内存如图如图(b)b)所示。所示。当当系系统统采采取取最最佳佳适适应应算算法法时时，空空闲闲区区链链表表应应当当按按照照空空闲闲区区的的大大小小顺顺序序重重新新排排列列，则则搜搜索索到到满满足足条条件件的的最最小小的的空空闲闲区区应应该该是是大大小小为

47、为2525KBKB的的空空闲闲区区，此此时时分分配配后后的的内内存存如如图图(c)c)所所示示。当当系系统统采采取取最最坏坏适适应应算算法法时时，则则搜搜索索到到满满足足条条件件的的最最大大的的空空闲闲区区应应该该是是大大小小为为5050KBKB的空闲区，此时分配后的内存的空闲区，此时分配后的内存如图如图(b)b)所示。所示。基本思想基本思想 分分区区管管理理存存在在着着严严重重的的外外部部碎碎片片问问题题，而而且且作作业业的的大大小小受受到到分分区区大大小小的的限限制制，而而分分页页管管理理可可以以很很好好的的解解决决这这些些问问题题。在在分分页页存存储储管管理理中中，系系统统将将内内存存划

48、划分分成成大大小小相相等等的的许许多多分分区区，称称为为“页页面面”。页页面面的的编编号号为为0,1,2,0,1,2,如如图图(a)a)所所示示。用用户户作作业业的的地地址址空空间间也也被被划划分分成成大大小小与与“页页面面”相相同同的的分分区区，称称为为“页页”，如如图图(b)b)所所示示。此此时时用用户户程程序序的的虚虚拟拟地地址址由由两两部部分分组组成成：页页号号与与页页内内地地址址，如如图图(c)c)所所示示。这个二维地址可以转换成一维的，具体转换公式为：这个二维地址可以转换成一维的，具体转换公式为：一维地址一维地址=页号页号*分页尺寸分页尺寸+叶内位移量叶内位移量 继续5.3 5.3

49、 页式存储管理页式存储管理 操作系统操作系统 作业作业A A（第第2 2页）页）作业作业A A（第第0 0页）页）作业作业A A（第第1 1页）页）2020K K2424K K2828K K3636K K4040K K256256K K0 03232K K (a)a)4444K K页面页面0404页面页面5 5页面页面6 6页面页面7 7页面页面8 8页面页面9 9页面页面1010内存内存用户作业的地址空间用户作业的地址空间0 0第第0 0页页4 4KBKB8 8KBKB1212KBKB第第1 1页页第第2 2页页(1,1092)(1,1092)5188518810921092(b)b)(c)

50、c)页号页号 页内地址页内地址0 09 910101919 只要内存中有足够多的空闲页面，用户作业中的某一页装入哪只要内存中有足够多的空闲页面，用户作业中的某一页装入哪一个页面都是可以的。上图中，作业装入了页面一个页面都是可以的。上图中，作业装入了页面6 6、页面、页面8 8和页面和页面1010这三个这三个不连续的存储块不连续的存储块中。因此解决了分区管理中作业必须连续存中。因此解决了分区管理中作业必须连续存放的缺陷。放的缺陷。返回返回 静态页面管理静态页面管理 静静态态页页面面管管理理在在作作业业或或进进程程执执行行之之前前，把把该该作作业业或或进进程程的的程程序序段段和和数数据据全全部部装