缺页中断处理过程课件.ppt

1、LOGO1存储管理第三章正文3.1 存储管理综述n存储器分类n内存：内存：CPU直接存取，存放正要执行的程序和数据，访问速度快，价格贵，容量小。n外存：外存：CPU不能直接访问，存放暂时不执行的程序和数据，访问速度慢，容量大。n存储管理指内存管理LOGO2存储管理第三章正文3.1 存储管理综述 理想中的存储器 速度快 容量大 价格便宜 目前无法同时满足三个条件 多级存储器结构3.1.1 存储器的层次结构存储器的层次结构 LOGO3存储管理第三章正文3.1 存储管理综述寄存器和主存又叫“可执行存储器可执行存储器”计算机对所存信息访问机制访问所耗时间可执行存储器进程可在很少的时钟周期使用一条Loa

2、d或store指令访问可执行存储器很少的时钟周期辅存通过I/O设备访问辅存远高于前者，一般相差3个数量级甚至更多（因访问中涉及到中断、设备驱动程序以及物理设备的运行）LOGO4存储管理第三章正文3.1 存储管理综述3.1.2 高速缓冲存储器的工作原理高速缓冲存储器的工作原理1、高速缓冲存储器 CACHE是一个高速度、小容量的缓冲存储器，存储CPU最经常访问的指令或数据，一般用SRAM芯片构成，其全部功能由硬件实现，对程序员是透明的。CACHE用于解决 CPU与主存间的速度匹配问题，其理论依据是程序访问的局部性原理。LOGO5存储管理第三章正文3.1 存储管理综述 为了使主存与cache之间映射

3、，将主存与缓存都分在若干个块，每个块包含若干个字，并使块的大小相等。将主存n位地址分为高m位和低b位，缓存地址也分成高c位和低b位。主存的块数M=2m远大于缓存的块数C=2c块。由于缓存的块数远小于主存的块数，一个缓存块不能唯一、永久地对应一个主存块，每个缓存块需设一个标记，用来表示当前存放的是哪一个主存块，该标记的内容相当于主存块的编号（即主存地址的高m位）。CPU读信息时根据主存地址的低位部分，将主存地址的高位部分与缓存块的标记进行比较，以判断所读信息是否在缓存中。LOGO6存储管理第三章正文3.1 存储管理综述主存储器主存储器Cache 主存块号主存块号0122m-1：字块字块0字块字块

4、1字块字块2字块字块M-1字块字块0字块字块1字块字块C-1012c-1标记标记M=2m C=2c（1）CACAHE命中：CPU访问的数据或指令已存在于CACHE中。（2）命中时间：在CACHE命中时的访存时间，它等于CACHE的访问时间。（3）失效时间：CACHE不命中时因访存而增加的访问时间，它等于对主存的访问时间和将主存中的数据调入CACHE的时间。LOGO7存储管理第三章正文3.1 存储管理综述3.1.3 存储管理的功能存储管理的功能内存的分配和回收 当用户提出内存申请时，操作系统按一定策略从表中选出符合申请者要求的空闲区进行分配，并修改表内有关项，这称为内存的分配；若某进程执行完毕，

5、需归还内存空间时，操作系统负责及时收回相关存储空间，并修改表中有关项，这称为内存的回收。LOGO8存储管理第三章正文3.1 存储管理综述内存的保护和共享内存保护：就是确保多个进程都在各自分配到内存区域内操作，互不干扰，防止一个进程破坏其他进程的信息。内存共享：内存允许同时有多个程序在运行多个进程，它们可能调用相同程序段或使用同一数据体，从而节省内存空间，减少内外存的数据交换，提高系统的效率 LOGO9存储管理第三章正文3.1 存储管理综述内存扩充内存“扩充”包含了存储器利用的提高和扩充两方面的内容。为用户提供比内存物理空间大得多的地址空间。比较典型的内存扩充是虚拟存储器。地址定位就是将进程的逻

6、辑地址变换为内存中的物理地址。我们需要实现从逻辑地址到物理地址的变换，即实现从虚地址到实地址的变换。LOGO10存储管理第三章正文3.2 固定分区存储管理 用户程序的四个处理阶段用户程序的四个处理阶段 编辑阶段编辑阶段 1.编辑阶段用户源程序翻译阶段目标程序代码其他代码库代码链接编辑阶段可执行程序代码装入阶段程序地址空间磁盘 用汇编语言或某高级语言编写程序，是产生用户程序的编辑阶段，该阶段的结果是得到“源程序”文件。翻译阶段翻译阶段 2.为了程序的运行，先应使用汇编程序或编译程序对源程序进行翻译处理，产生出称为“目标程序”的二进制程序代码，这属于翻译阶段。链接编辑阶段链接编辑阶段 3.把目标程

7、序代码链接装配到一起，成为一个统一的程序整体。经过链接编辑阶段，得到用户程序相对于“0”编址的一个完整的二进制目标程序代码。装入阶段装入阶段 4.装入阶段的任务，是根据内存的使用情况，为进入内存的程序分配存储区，对程序中的地址进行调整。LOGO11存储管理第三章正文3.2 固定分区存储管理3.2.1 地址重定位地址重定位1.用户程序的两种地址和空间用户程序的两种地址和空间.内存单元的地址称为“绝对地址”或“物理地址”。从任何一个绝对地址开始的一段连续的内存空间，被称为“物理地址空间”，或“绝对地址空间”。.用户程序的逻辑地址空间0k内存装入用户程序的物理地址空间aa+k逻辑地址物理地址 在多道

8、程序设计环境下，用户无法事先指定要占用内存的哪个区域，也不知道自己的程序将会被放在内存的什么地方。.程序通过链接编辑，产生出相对于“0”计算的地址空间，这个地址空间称为是用户程序的“相对地址空间”，或“逻辑地址空间”，其地址称为“相对地址”或“逻辑地址”。系统所接受的，就是这种相对于“0”编址的用户程序。.这样的程序是不可能直接投入运行的，因为程序中的地址没有能够反映出它所在存储区的真正存储位置。2.地址的重定位地址的重定位 程序被装入到分配给它的内存储区时，必须对每条指令里所涉及到的逻辑地址进行修改，使它们能够正确地反映出所在的存储位置。这种把逻辑地址转换成物理地址的过程，称为地址的“重定位

9、”。.LOGO12存储管理第三章正文3.2 固定分区存储管理.用户程序A的相对地址空间xxxxxx01001KB2KB3KB3000call 100内存xxxxxx20KB20KB+10021KB22KB23KB20KB+3000call 100操作系统0X内存xxxxxx20KB20KB+10021KB22KB23KB20KB+3000 call 20580操作系统0内存xxxxxx22KB22KB+10023KB24KB25KB22KB+3000 call 226280操作系统20KB(a)(b)(c)(d)例如，假定用户程序A的相对地址空间为03KB（03071），在程序中地址为3000

10、的地方，有一条调用子程序（其入口地址为100）的指令：“call 100”，如图（a）所示。.对用户程序原封不动的装入，不能使它正确运行，因为在执行到位于绝对地址20KB+3000处的“call 100”指令时，它就会转到绝对地址100处去调用所需的子程序，而这个地址却是在操作系统里面，如图（b）所示。.把指令“call 100”中的100变换成20580，就是地址重定位，如图（c）所示。.若把程序A装入到（22KB25KB）的绝对地址空间里，那么call指令中地址100所对应的绝对地址就是22KB+100=22628了。如图（d）所示。LOGO13存储管理第三章正文3.2 固定分区存储管理

11、即在程序装入内存之前，程序指令中的地址就已经是绝对地址，已经正确地反映了它将要进入的存储区位置。3.2.2.地址的定位方式和静态重定位地址的定位方式和静态重定位.绝对定位方式(1).优点是程序中的逻辑地址与实际内存的物理地址相同，不再需要对指令中的地址进行任何重定位，装入到指定的内存位置就可以运行了。缺点是编程人员要熟悉内存使用情况，要小心对待指令中的地址，不能出差错；程序在内存不能移动，只能固定在该存储区内；对程序所作的微小修改，都可能牵扯到程序整体的变动；不适用多道程序设计环境。静态重定位方式(2)要有重定位装入程序，功能是：根据当前内存使用情况，为欲装入的二进制目标程序分配所需存储区；根

12、据所分配的存储区，对程序中的指令地址进行重定位；将重定位后的二进制目标程序装入到指定的存储区中。.用户提供相对于“0”编址的二进制目标程序。通过重定位装入程序的加工，目标程序进到分配给它的物理地址空间，程序指令中的地址都被修改为正确反映该空间的情形。.由于地址重定位在程序执行前完成，因此称为“静态重定位”，或“静态地址绑定”。特点是：重定位由软件实现，无须硬件支持；在程序运行前完成地址重定位工作；地址重新计算和修改是在程序装入时集中完成；物理地址空间里的目标程序与原逻辑地址空间里的目标程序已不相同；位于物理地址空间里的用户程序不能在内存中移动，除非重新进行地址定位；适用于多道程序设计环境。LO

13、GO14存储管理第三章正文3.2 固定分区存储管理 静态重定位在装入时一次性集中把程序指令中所有地址全部加以重定位；动态重定位则是每执行一条指令时，才其地址加以重定位。静态重定位在程序运行之前完成地址转换；动态重定位则是将地址转换的时刻推迟到指令执行时进行。若将地址定位的时间推迟到程序执行时进行，那么称其为地址的“动态重定位”方式。.动态重定位方式(3).对程序实行动态重定位需要硬件支持：一个地址转换机构。它由地址转换线路和一个“定位寄存器”（也称“基址寄存器”）组成。这时，用户程序不做任何修改地装入到分配给它的内存空间中。当调度到程序运行时，就把它所在物理空间的起始地址加载到定位寄存器中。C

14、PU每执行一条指令，就把指令中的相对地址与定位寄存器中的值相“加”，得到绝对地址。然后按这绝对地址去执行指令，访问所需要的存储位置。xxxxxx22KB22KB+10023KB24KB25KB22KB+3000call 1000操作系统20KB(b)用户程序A的相对地址空间xxxxxx01001KB2KB3KB3000call 100(a)22KB定位寄存器1002262822528内存.静态重定位和动态重定位的比较(4).静态重定位由软件完成地址转换；动态重定位由硬件地址转换机构完成。.静态重定位时原来的指令地址被修改了；实行动态重定位，不对指令本身做修改。LOGO15存储管理第三章正文3.

15、2 固定分区存储管理 用户区分为“使用区”和“空闲区”两部分，如图（b）所示。使用区是用户作业程序真正占用的连续存储区域；空闲区是分配给了用户、但未被用户使用的区域，称为“内部碎片”。1.单一分区存储管理单一分区存储管理.单一分区存储管理的系统，任何时刻只有一个用户程序驻留内存。因此内存为两个部分：供操作系统使用的系统区和供用户程序使用的用户区。作业3 作业2 作业1内存0ab操作系统用户区内存0ab操作系统使用区空闲区用户区c(a)(b).单一分区存储管理系统的特点：(1)总是把一个连续的用户区分配给一个用户使用，如图（a）中的ab区域。(2)(3)这种系统只适用于单用户的情况。(4)进入内

16、存的作业，独享系统中的所有资源，包括内存中的整个用户区。(5)由于整个用户区都分配给了一个用户，因此作业程序进入用户区后，没有移动的必要。所以采用这种存储管理策略，对用户程序实行静态重定位。3.2.3 单一连续分区存储管理单一连续分区存储管理LOGO16存储管理第三章正文3.2 固定分区存储管理 每次只能有一个作业进入内存，故不适用于多道程序设计，整个系统的工作效率不高，资源利用率低下；内存0ab操作系统使用区空闲区ca界限寄存器.实行静态重定位，不能阻止用户有意无意地通过不恰当的指令闯入操作系统所占用的存储区域。.在单一分区存储管理中，为有效阻止用户程序指令中的地址闯入操作系统所占用的区域，

17、在CPU中会设置一个用于存储保护的专用寄存器“界限寄存器”，如图所示。.界限寄存器中，总是存放内存用户区的起始地址。CPU在核心态下工作时，允许访问内存中的任何地址；CPU在用户态下工作时，对内存的每一次访问，都要在硬件的控制下，与界限寄存器中的内容进行比较。一旦发现所访问的地址小于界限寄存器中的地址，产生“地址越界”中断，阻止这次访问的进行，从而将作业限制在规定的存储区域内运行，确保操作系统中的信息不受外来的破坏。单一分区存储管理的缺点.(1)(2)只要作业比用户区小，那么在用户区里就会形成碎片，如果用户作业很小，那么这种浪费是巨大的；(3)若用户作业的相对地址空间比用户区大，那么该作业就无

18、法投入运行，因为大作业无法在小内存上运行。LOGO17存储管理第三章正文3.2 固定分区存储管理 “覆盖”是早期提供的扩充内存的技术，它允许一个作业的若干个程序段使用同一存储区，被共用的存储区称为“覆盖区”。程序段存放在磁盘上，需要时由操作系统完成对它们的调入或调出。覆盖技术覆盖技术 2.MAIN 10KBA 50KBB 30KBC 30KBD 20KBE 40KB链接编辑MAIN 10KBA 50KBB 30KBC 30KBD 20KBE 40KB0180KB(a)(b)(c)10KB50KB40KBMAINA或BC或D或E.比如，用户作业程序的调用结构如图（a）所示。.通过连接装配的处理，

19、该作业将形成一个需要存储量180KB的相对地址空间，如图（b）所示。.程序中的子程序A和B不可能同时调用，子程序C、D和E也不能同时出现。除主程序必须用内存中的10KB外，A和B可共用存储量为50KB的存储区，C、D和E可共用存储量为40KB的存储区，如图（c）所示。LOGO18存储管理第三章正文3.2 固定分区存储管理对换技术对换技术 “对换”的思想是：将作业信息都存放在辅助存储器上，根据单一分区存储管理的分配策略，每次只让其中的一个进入内存投入运行。当运行中提出输入/输出请求或分配给的时间片用完时，就把它从内存“换出”到辅存，把辅存里的另一个作业“换入”内存运行，产生出“多道”的效果。3.

20、作业1作业2作业3辅助存储器内存储器操作系统用户区换出换入LOGO19存储管理第三章正文3.2 固定分区存储管理3.2.4 固定分区存储管理固定分区存储管理1.基本思想基本思想 所谓“固定分区固定分区”存储管理，是指预先把内存的用户区划分成若干个连续的分区，它们的尺寸可以相同，也可以不同。划分后，内存中分区的个数以及每个分区的尺寸保持不变。每个分区里只允许装入一个作业运行。2.对作业的组织对作业的组织LOGO20存储管理第三章正文3.2 固定分区存储管理操作系统0100KB200KB400KB700KB800KB第1分区第2分区第3分区第4分区多个队列操作系统第1分区第2分区第3分区第4分区单

21、个队列(a)(b)系统可以为每个分区设置一个后备作业队列，形成多队列的管理方式，如图（a）所示；也可采用多个分区只设置一个后备作业队列的办法，如图（b）所示。.为管理内存中的各分区，操作系统设置一张名为“分区分配表”的表格，它随时记录各分区的信息及当前的使用情况。.分区分配表中至少应该有每个分区的起始地址、长度，以及一个使用标志。当某分区的使用标志为“0”时，表示该分区当前是空闲的，可以分配；当某分区的使用标志不为“0”时，表示该分区已经分配给了一个作业使用，里面存放的是这个作业的名称。LOGO21存储管理第三章正文3.2 固定分区存储管理作业尺寸比任何一个分区的长度都大时，就无法运行。.3.

22、分区的分配与释放分区的分配与释放.分区空闲时，若它的队列非空，就把该分区分配给队列的第一个作业使用；作业运行完毕，收回该分区，进行下一次分配。每个分区设置一个后备作业队列 多个分区只设置一个后备作业队列 在任何一个分区释放时，就根据分配方案从该队列里挑选一个作业装入运行。4.地址重定位与存储保护地址重定位与存储保护 在固定分区存储管理中，实行静态重定位实行静态重定位。.在固定分区存储管理中，要防止用户程序对操作系统的侵扰，也要防止用户程序间的侵扰。因此设置一对专用寄存器：“低界限寄存器低界限寄存器”和和“高界高界限寄存器限寄存器”，用于存储保护。地址重定位存储保护0abcdab作业1作业2作业

23、3第1分区第2分区第3分区操作系统低界限寄存器高界限寄存器CPU5.固定分区存储管理的特点与缺点固定分区存储管理的特点与缺点.是最简单的、具有“多道”色彩的存储管理方案。.作业程序一次性全部装入分配给它的连续分区。.实行的是静态重定位。.会产生内部碎片，引起内存资源的浪费。LOGO22存储管理第三章正文3.3 可变分区存储管理 3.3.1可变分区存储管理的基本思想可变分区存储管理的基本思想 可变分区存储管理的基本思想是：作业要求装入内存时，若内存有足够的连续存储空间供使用，那就依作业相对地址空间的大小，划分出一个分区分配给它。.作业C10KB作业B20KB作业A15KB内存操作系统空闲区(a)

24、内存操作系统空闲区作业A15KB内存操作系统空闲区作业A15KB作业B20KB内存操作系统空闲区作业A15KB作业B20KB作业C10KB(b)(c)(d)(e)图（a）表明后备作业队列里，作业A需要内存15KB，作业B需要20KB，作业C需要10KB，等等。.图（b）表示系统初启时的情形，整个系统里没有作业运行，用户区空闲。.图（c）表示作业A装入内存时，为它划分了尺寸为15KB的分区。用户区被分成两个分区，一个是已分配的，一个是空闲区。.图（d）表示作业B装入内存时，为它划分了尺寸为20KB的分区，此时的用户区被分成了三个分区；.图（e）表示作业C装入内存时，为它划分了一个尺寸为10KB的

25、分区，此时的用户区被分成了四个分区。LOGO23存储管理第三章正文3.3 可变分区存储管理 随着作业对存储区域的不断申请与释放，发展趋势是：分区的数目会逐渐增加，有的分区尺寸在逐渐减小，甚至有可能出现内存里有空闲区、但每个都满足不了作业程序的要求而无法分配出去的情形。在存储管理中，把那些无法满足作业存储请求的空闲区称为“外部碎片”。.可变分区存储管理模式引发了许多新的问题。只有解决这些问题，可变分区存储管理才能付之以实现。内存操作系统空闲区236(a)020256内存操作系统空闲区220(b)020256作业A16作业B100内存操作系统空闲区120(c)020作业A16256作业C70361

26、36作业B100内存操作系统空闲区50(d)020作业A1625636136作业C70空闲区100内存操作系统空闲区50(e)020作业A1625636136作业C70空闲区25内存操作系统空闲区50(f)020作业A1625636136作业D7520620620611136.实行可变分区存储管理必须解决的问题：(1)(2)(3)采用地址动态重定位技术，使程序能在内存中移动，为空闲区的合并提供保证。记住各个分区的使用情况，当一个分区被释放时，能方便地判定它的前、后分区是否为空闲区。若是空闲区，就进行合并，形成一个大的空闲区。给出分区分配算法。LOGO24存储管理第三章正文3.3 可变分区存储管

27、理 静态重定位是在程序运行之前完成地址转换的；动态重定位却是将地址转换的时刻推迟到指令执行时进行。实行静态重定位，原来的指令地址部分被修改了；实行动态重定位，只是按照所形成的地址去执行这条指令，并不对指令本身做任何修改。静态重定位是在装入时一次集中地把程序指令中所有要转换的地址全部加以转换；而动态重定位则是每执行一条指令时，对其地址加以转换。静态重定位是由软件完成地址转换工作的；动态重定位则由一套硬件提供的地址转换机构来完成。1.基本思想2.地址静态和动态重定位的比较 3.3.2 地址的动态重定位地址的动态重定位 把相对地址空间中的用户作业程序“原封不动”地装入到分配给它的绝对地址空间中去。执

28、行某条指令时，才根据当前程序所在区域，对指令中的地址进行重定位。即指令中地址的转换是在程序执行时动态完成的，故称为地址的“动态重定位动态重定位”。0用户作业A的相对地址空间XXXXXX1001KB2KB3000call 1003KB0XXXXXX22KB+10023KB24KB22KB+3000call 10025KB20KB22KB22KB定位寄存器2262822528操作系统内存.LOGO25存储管理第三章正文3.3 可变分区存储管理 一是调度到某作业时，若系统的每个空闲区尺寸都小于它的需要，但空闲区总存储量大于它的存储请求，于是进行空闲区合并，得到一个大的空闲区，满足该作业的需要；一是只

29、要有作业运行完归还所占用的存储区，系统就进行空闲区的合并。释放区的前、后邻接分区都是空闲区。因此，释放区应该和前、后两个邻接的空闲区合并成一个新的空闲区。释放区的前邻接分区是已分配区，后邻接分区是空闲区。因此，释放分区应该和后邻接的空闲区合并成一个新的空闲区。释放分区的前邻接分区是空闲区，后邻接分区是已分配区。释放区应该和前邻接的空闲区合并成一个新的空闲区。释放分区的前、后邻接分区都是已分配区，没有合并的问题存在。3.3.3 空闲区的合并空闲区的合并1.前后相邻接分区的四种关系2.空闲分区合并的时机已分配区空闲区释放分区空闲区已分配区释放分区空闲区空闲区释放分区已分配区已分配区释放分区.LOG

30、O26存储管理第三章正文3.3 可变分区存储管理 若有作业运行结束，则根据作业名到已分配表里找到它的表目项，将该项的“状态”改为“空”，随之在空闲区表里寻找一个状态为“空”的表目项，把释放分区的信息填入，并将表目项状态改为“空闲”。作业提出存储需求时，查空闲区表里状态为“空闲”的表目项。若该项的尺寸能满足所求，就将它一分为二：分配出去的那部分在已分配表里找一个状态为“空”的表目项进行登记，剩下的部分仍在空闲区表里占据一个表目项。3.3.4 分区的管理与组织方式分区的管理与组织方式1.表格法表格法 设置两张表：“已分配表”和“空闲区表”。其中“序号”是表目项的顺序号，“起始地址”、“尺寸”、“状

31、态”都是该分区的相应属性。由于系统中分区的数目是变化的，因此每张表格中的表目项数要足够的多，暂时不用的表目项的状态被设为“空”。内存操作系统空闲区(8KB)作业B(32KB)空闲区(32KB)作业D(120KB)空闲区(300KB)序号起始地址尺寸状态12345020KB28KB60KB92KB212KB512KB28KB32KB作业B空空空92KB120KB作业D序号起始地址尺寸状态1234560KB32KB作业B空闲空空作业D20KB8KB212KB300KB已分配表空闲区表.LOGO27存储管理第三章正文3.3 可变分区存储管理 把内存中的每个空闲分区视为一个整体，在它的里面开辟出两个单

32、元，一个存放该分区的长度（size），一个存放它下一个空闲分区的起址（next），操作系统开辟一个单元，存放第1个空闲分区的起址，这个单元称为“链首指针”。最后一个空闲分区的next里存放标志“NULL”。这样一来，系统里所有空闲分区被next连接成一个链表。从链首指针出发，顺着各个空闲分区的next往下走，就能到达每一个空闲分区。20KB8KB60KB2.单链表法单链表法.sizenext空闲区长度下一个空闲区起址空闲区8KB212KB32KBNULL300KB20KB60KB空闲区(8KB)32KB212KB空闲区(32KB)300KB NULL空闲区(300KB)作业B(32KB)作业D

33、(120KB)020KB28KB60KB92KB212KB512KB内存操作系统链首指针链首指针.基本思想 对提出的任何一个存储请求，从空闲区链表首指针开始查看一个个空闲区。若有满足要求的，按尺寸分配，调整next指针；若到达NULL未见满足要求，则分配失败。存储分配.存储释放作业完成任务后，将占用的存储区释放，链入空闲区链表（要调整指针和空闲区合并）。LOGO28存储管理第三章正文3.3 可变分区存储管理空闲区(300KB)sizenext.3.双链表法双链表法基本思想20KB空闲区长度下一个空闲区起址空闲区300KBNULL作业B(32KB)作业D(120KB)020KB28KB60KB9

34、2KB212KB512KB内存操作系统链首指针prior上一个空闲区起址空闲区(32KB)32KB212KB60KB20KB空闲区(8KB)8KB60KBNULL 在每个空闲分区里，即存放下一个空闲区起址next，也存放它的上一个空闲区起址（prior）的信息。这样，通过双向链表，就可以方便地由next找到一个空闲区的下一个空闲区，也可以由prior找到一个空闲区的上一个空闲区。.存储合并 把释放区链入空闲区双向链表时，若通过它的prior发现该释放区的前面一个空闲区的起址加上长度，等于释放区的起址，那么说明它前面的空闲区与它直接邻接，应该把这个释放区与原先的空闲区合并。若释放区起址加上长度正

35、好等于next所指的下一个空闲区的起址，那么说明它与后面的空闲区直接邻接，应该把这个释放区与原先的空闲区合并。.空闲区的两种组织形式 若将每个空闲分区按其起址由小到大排列在链表里，则把这种组织称为“地址法地址法”；若按每个空闲分区的长度由小到大排列在链表里，则把这种组织称为“尺寸法尺寸法”。LOGO29存储管理第三章正文3.3 可变分区存储管理3.3.5 空闲分区的分配算法空闲分区的分配算法1.三种分配算法三种分配算法 “最先适应”算法把最先找到的、满足存储需求的那个空闲分区作为分配的对象。它实现简单，查找时间少，但有可能把大的空闲分区分割成许多小的分区，因此对大作业不利。(1)(2)“最佳适

36、应”算法从当前所有空闲区中找出一个能满足存储需求的、最小的空闲分区作为分配的对象，尽可能地不把大的空闲区分割成小的分区，以保证大作业的需要。(3)“最坏适应”算法从当前所有空闲区中找出一个能满足存储需求的、最大的空闲分区作为分配的对象。这种方案的出发点是照顾中、小作业的需求。LOGO30存储管理第三章正文3.3 可变分区存储管理2.可变分区存储管理的特点可变分区存储管理的特点3.可变分区存储管理的缺点可变分区存储管理的缺点.作业一次性地全部装入到一个连续的存储分区中。.分区是按照作业对存储的需求划分的，因此不会出现内部碎片这样的存储浪费。.为确保作业能够在内存中移动，要由硬件支持实行指令地址的

37、动态重定位。.只要作业的存储需求大于系统提供的整个用户区，该作业就无法投入运行。.有可能出现极小的分区暂时分配不出去的情形，产生外部碎片。由于是通过移动程序来达到分区合并的目的，势必增加系统在这方面的投入与开销。LOGO31存储管理第三章正文3.3 可变分区存储管理伙伴系统伙伴系统 3.3.6.伙伴系统是对固定分区和可变分区两种存储管理“扬长避短”后，提出的一种折中方案。.伙伴系统中，可用内存分区的大小为：2K，LKU其中：2L表示分配的最小分区的尺寸；2U表示分配的最大分区的尺寸。在实际操作系统中，最小分区尺寸一般为212。如果进程申请的存储空间大小为S，且2U-1S2U，则将整个2U大小的

38、分区分配给该进程；否则，该分区被分割成两个大小相等的伙伴分区，大小为2U-1；再判断S是否满足条件：2U-2S2U-1，若满足条件，则将两个伙伴中的任何一个分配给该进程。否则，将其中一个伙伴又分成两个大小相等的伙伴分区；此过程一直继续进行，直到产生的分区满足条件U-JS并2U-J-1S2U-J，将2U-J大小的分区分配给该进程；当U-J-10，所以p=(2es)1/2给出的是作业最佳页面尺寸p与作业尺寸s间的关系，它使系统的额外开销为最小。LOGO42存储器管理第三章正文3.4 分页式存储管理 3.4.3 内存块的分配与回收内存块的分配与回收1.对内存块的管理对内存块的管理.存储分块表存储分块

39、表单链表单链表操作系统作业C第2页作业B第0页作业A第0页空闲块作业A第2页空闲块空闲块作业B第1页空闲块空闲块作业A第1页作业C第3页作业C第0页作业C第1页空闲块内存储器064K空闲块链表起址块号状态0已分配1已分配2已分配3已分配4空闲5已分配6空闲7空闲8已分配9空闲10空闲11已分配12已分配13已分配14已分配15空闲空闲块总数：6 系统维持一张表格，表格表项与内存中的一块相对应，记录该的块使用情况。只要表格中“空闲块总数”记录的数目大于请求的存储量，就可进行分配，并把分配出去的块的状态改为“已分配”。作业完成后归还存储块时，就把表中相应块的状态改为“空闲”。单链表存储分块表 把空

40、闲块链接成一个单链表加以管理，系统必须设置一个空闲块链表的起始地址指针，以便进行存储分配时能够找到空闲的内存块。无论是进行空闲块的分配还是作业完成后归还存储块，都要调整空闲块间的链表指针。LOGO43存储器管理第三章正文3.4 分页式存储管理 作业虽然不占据连续的存储区，但每次仍要求一次全部进入内存。因此，如果作业很大，其存储需求大于内存，那么还是存在小内存不能运行大作业的问题。用户作业的相对地址空间按照块的尺寸划分成页。这种划分是在系统内部进行的，用户感觉不到，即对用户是“透明”的。2.分页式存储管理的特点分页式存储管理的特点.内存存储器事先被划分成相等尺寸的块，它是进行存储分配的单位。.相

41、对地址空间中的页可以进入内存中的任何一个空闲块，并且分页式存储管理实行的是动态重定位，因此它打破了一个作业必须占据连续存储空间的限制，作业在不连续的存储区里，也能够得到正确的运行。3.分页式存储管理的缺点分页式存储管理的缺点.平均每一个作业要浪费半页大小的存储块。.位图位图 用二进制位与内存块的使用建立起关系，为“0”，表示对应块空闲；为“1”，表示对应块已分配。1111010010011110空闲块总数：60123456701字节号位号位图LOGO44存储管理第三章正文3.5 分段式存储管理 引入 从固定分区到可变分区，再到分页方式存储管理，是为了提高内存利用率。引入分段存储管理方式，是为了

42、满足用户在编程和使用上多方面的要求。（1）方便编程（2）信息共享（3）信息保护（4）动态增长（5）动态链接LOGO45存储管理第三章正文3.5 分段式存储管理1、分段u进程地址空间被划分为若干段，每个段都有名字，如主程序段、子程序段、数据段、栈段等。u可以用段号代替段名，每个段都是从0开始编址，并采用一段连续的地址空间。u各段长度不等。u整个进程地址空间分成多个段，所以进程地址空间是二维的，逻辑地址是由段号（段名）和段内地址组成。段号段号段内地址段内地址LOGO46存储管理第三章正文3.5 分段式存储管理2、段表u进程地址空间分成几个段，系统为每个段分配连续的分区，各个段可以离散的装入内存中的

43、不同分区中。u设置段表保存进程各个段在内存中的起始地址（基址）和段的长度。u段表可以保存在内存中。LOGO47存储管理第三章正文3.5 分段式存储管理 3.5.1分段及二维逻辑地址空间分段及二维逻辑地址空间 用户的程序结构不是一维的，多由主程序及一些子程序、过程、函数或模块构成，还包括各种数据结构，如堆栈、表格、变量等。即程序多由程序段和数据段组成。.1.2.用户程序的二维结构用户程序的二维结构段MAIN(0段)段P(1段)段D(2段)段Q(3段)call p,x0008KB8KB5KB6KB4KBx:x.分段支持用户二维观点的内存管理方案。作业的逻辑地址空间由一组段组成，每个段有自己的名称和

44、长度，用户通过数对：段名，段内元素名指定某段中的地址。于是，用户的逻辑地址空间是二维的。分段式存储管理中的逻辑地址分段式存储管理中的逻辑地址.分段式存储管理中，逻辑地址用两个成分描述：段名和段内元素名。系统接受了用户的逻辑地址空间后，在内部就用段号段号s代替段名，用段内位移段内位移d代替段内元素名。段号s段内位移d3116 150.在这种地址结构中，由于是各用16个2进制为表示段号s和段内位移d，因此允许用户逻辑地址空间最多有64K个段，每段的最大长度是64KB。LOGO48存储管理第三章正文3.5 分段式存储管理3.分段式存储管理中的内存分配分段式存储管理中的内存分配.在分段式存储管理中，作

45、业逻辑地址空间的段原封不动离散地存放到内存的不同分区中。即系统为每个段分配一个连续的分区，而各段在内存中则不必连续。系统为每个作业进程设置一个段表，记录逻辑地址空间中各段在内存中的基址，通过段表实现逻辑地址到内存物理地址的映射。段 0MAIN08KB段 1P05KB段 2D06KB段 3Q04KB逻辑地址空间段号 段长 基址 0 8KB 1 5KB 2 6KB 3 4KB 段表段段MAIN段段Q段段D段段P操作系统内存储器 比如，指令里给出一个逻辑地址s,d时，就用地址中的段号s去查段表，从那里得到该段在内存中的基址，由基址“加上”逻辑地址中的段内位移，就得到了所对应的物理地址。.LOGO49

46、存储管理第三章正文3.5 分段式存储管理 改变某程序段的大小，就会影响其他无关程序段的起址；对某个程序段进行的修改，会影响到其他相关部分，就可能要对所有的程序重新进行链接编辑。一维地址空间的组织方式，有如下缺点：(1)(2)不利于按照程序段的性质，实施存储保护和共享。.所谓“分段式”存储管理，即要求用户将自己的作业程序以多个相互独立的称为“段”的地址空间提交给系统，每个段都是一个从“0”开始的一维地址空间，长度不一。操作系统按照段长为作业分配内存空间。.分段式组织方式的优点：(1)每个程序段是一个独立的地址空间，它们可独自增长或减小而不用顾及别的程序段，不会影响到其他程序段的地址空间。(2)每

47、个程序段是一个独立的逻辑实体（比如一个过程、一个数组或一个堆栈），因此可以对它们进行不同类型的存储保护。(3)独立的地址空间有助于实施对过程和数据的共享，不必在每一个用户作业的地址空间里都必须有相关的备份。LOGO50存储管理第三章正文3.5 分段式存储管理 通过编译程序在编译过程中建立的各种表，说明页式及段式存储管理中，作业程序地址空间组织形式的不同。例例：解解：在编译过程中会建立很多表，其中主要有：供打印程序清单的源程序文档；由变量名及其属性组成的符号表；由程序中所有的整型、实型常量组成的常量表；包含程序语法分析结果的语法分析树；内部过程调用时使用的堆栈。.在分页式管理时，这5个表必须限定

48、在一个一维的地址空间里，如图(a)所示。使用使用使用使用使用空闲空闲空闲空闲堆栈语法分析树常量表源程序文档符号表(a)0KB4KB8KB12KB16KB20KB0KB4KB8KB12KB符号表段00KB源程序文档常量表段1段3段40KB4KB8KB12KB16KB语法分析树0KB4KB8KB12KB堆栈段2(b).在分段管理时，是把这些表视为一个个相互独立的地址空间，比如：段0、段1等，它们组成了整个用户的地址空间，如图(b)所示。LOGO51存储管理第三章正文3.5 分段式存储管理.在分段式存储管理时，要指示存储空间里的一个地址，必须提供两部分内容：段号和段内位移。即逻辑地址应该是二维的：段

49、号，段内位移。.在图(a)所示的32位地址结构中，由于是各用16个二进制位表示段号s和段内位移d，因此表示用户的逻辑地址空间最多可以有216个段，每段最大长度是64KB。3116 150sd段号段内位移ds段号段内位移03123 22(a)(b).图(b)所示的32位的地址结构中，由于用9个二进制位表示段号s，用23个二进制位表示段内位移d，因此表示允许用户的逻辑地址空间中最多可以有29个段，每段的最大长度是223=8192KB。LOGO52存储管理第三章正文3.5 分段式存储管理 用相对地址中的段内位移d与该段段长比较：如果大于段长，则表示该地址出错；否则，由段的基址和段内位移d拼装出所需的

50、绝对地址，从而实现对内存的访问。若段号大于段表长度，表示越界出错。否则以段号为索引查段表，得到该段在内存的基址。从CPU给出的相对地址数对：段号s，段内位移d中提取段号s，用来进行地址转换。3.4.2 分段式存储管理的地址转换过程分段式存储管理的地址转换过程 实施分段式存储管理时，系统为每个用户程序设置一个段表，用于记录各段在内存中的存放信息。逻辑空间中有多少段，段表里就有多少个表项。每个表项包括的信息有段号、段长、该段的基址（即起始地址）等。.为完成地址变换，需要一个段表控制寄存器。当作业调度时，把调度到的作业的段表起址和段表长度(即段表表项的数目)放入寄存器中，以期达到映射不同作业的目的。