缺页中断处理过程课件

1、存储器分类内存：CPU直接存取，存放正要执行的程序和数据，访问速度快，价格贵，容量小。外存：CPU不能直接访问，存放暂时不执行的程序和数据，访问速度慢，容量大。存储管理指内存管理理想中的存储器速度快容量大价格便宜目前无法同时满足三个条件多级存储器结构3.1.1 存储器的层次结构 寄存器和主存又叫“可执行存储器”计算机对所存信息访问机制访问所耗时间可执行存储器进程可在很少的时钟周期使用一条Load或store指令访问可执行存储器很少的时钟周期辅存通过I/O设备访问辅存远高于前者，一般相差3个数量级甚至更多（因访问中涉及到中断、设备驱动程序以及物理设备的运行）3.1.2 高速缓冲存储器的工作原理1

2、、高速缓冲存储器 CACHE是一个高速度、小容量的缓冲存储器，存储CPU最经常访问的指令或数据，一般用SRAM芯片构成，其全部功能由硬件实现，对程序员是透明的。 CACHE用于解决 CPU与主存间的速度匹配问题，其理论依据是程序访问的局部性原理。 为了使主存与cache之间映射，将主存与缓存都分在若干个块，每个块包含若干个字，并使块的大小相等。 将主存n位地址分为高m位和低b位，缓存地址也分成高c位和低b位。主存的块数M=2m远大于缓存的块数C=2c块。 由于缓存的块数远小于主存的块数，一个缓存块不能唯一、永久地对应一个主存块，每个缓存块需设一个标记，用来表示当前存放的是哪一个主存块，该标记的

3、内容相当于主存块的编号（即主存地址的高m位）。 CPU读信息时根据主存地址的低位部分，将主存地址的高位部分与缓存块的标记进行比较，以判断所读信息是否在缓存中。主存储器Cache 主存块号0122m-1：字块0字块1字块2字块M-1字块0字块1字块C-1012c-1标记M= 2m C = 2c（1）CACAHE命中：CPU访问的数据或指令已存在于CACHE中。（2）命中时间：在CACHE命中时的访存时间，它等于CACHE的访问时间。（3）失效时间：CACHE不命中时因访存而增加的访问时间，它等于对主存的访问时间和将主存中的数据调入CACHE的时间。3.1.3 存储管理的功能内存的分配和回收 当用

4、户提出内存申请时，操作系统按一定策略从表中选出符合申请者要求的空闲区进行分配，并修改表内有关项，这称为内存的分配；若某进程执行完毕，需归还内存空间时，操作系统负责及时收回相关存储空间，并修改表中有关项，这称为内存的回收。内存的保护和共享内存保护：就是确保多个进程都在各自分配到内存区域内操作，互不干扰，防止一个进程破坏其他进程的信息。 内存共享：内存允许同时有多个程序在运行多个进程，它们可能调用相同程序段或使用同一数据体，从而节省内存空间，减少内外存的数据交换，提高系统的效率 内存扩充内存“扩充”包含了存储器利用的提高和扩充两方面的内容。为用户提供比内存物理空间大得多的地址空间。比较典型的内存扩

5、充是虚拟存储器。 地址定位就是将进程的逻辑地址变换为内存中的物理地址。我们需要实现从逻辑地址到物理地址的变换，即实现从虚地址到实地址的变换。用户程序的四个处理阶段 编辑阶段 1.编辑阶段用户源程序翻译阶段目标程序代码其他代码库代码链接编辑阶段可执行程序代码装入阶段程序地址空间磁盘 用汇编语言或某高级语言编写程序，是产生用户程序的编辑阶段，该阶段的结果是得到“源程序”文件。 翻译阶段 2. 为了程序的运行，先应使用汇编程序或编译程序对源程序进行翻译处理，产生出称为“目标程序”的二进制程序代码，这属于翻译阶段。 链接编辑阶段 3. 把目标程序代码链接装配到一起，成为一个统一的程序整体。经过链接编辑

6、阶段，得到用户程序相对于“0”编址的一个完整的二进制目标程序代码。 装入阶段 4. 装入阶段的任务，是根据内存的使用情况，为进入内存的程序分配存储区，对程序中的地址进行调整。 3.2.1 地址重定位1.用户程序的两种地址和空间 . 内存单元的地址称为“绝对地址”或“物理地址”。从任何一个绝对地址开始的一段连续的内存空间，被称为“物理地址空间”，或“绝对地址空间”。 .用户程序的逻辑地址空间0k内存装入用户程序的物理地址空间aa+k逻辑地址物理地址 在多道程序设计环境下，用户无法事先指定要占用内存的哪个区域，也不知道自己的程序将会被放在内存的什么地方。 . 程序通过链接编辑，产生出相对于“0”计

7、算的地址空间，这个地址空间称为是用户程序的“相对地址空间”，或“逻辑地址空间”，其地址称为“相对地址”或“逻辑地址”。系统所接受的，就是这种相对于“0”编址的用户程序。 . 这样的程序是不可能直接投入运行的，因为程序中的地址没有能够反映出它所在存储区的真正存储位置。 2.地址的重定位 程序被装入到分配给它的内存储区时，必须对每条指令里所涉及到的逻辑地址进行修改，使它们能够正确地反映出所在的存储位置。这种把逻辑地址转换成物理地址的过程，称为地址的“重定位”。.用户程序A的相对地址空间xxxxxx01001KB2KB3KB3000call 100内存xxxxxx20KB20KB+10021KB22

8、KB23KB20KB+3000call 100操作系统0X内存xxxxxx20KB20KB+10021KB22KB23KB20KB+3000call 20580操作系统0内存xxxxxx22KB22KB+10023KB24KB25KB22KB+3000call 226280操作系统20KB(a)(b)(c)(d) 例如，假定用户程序A的相对地址空间为03KB（03071），在程序中地址为3000的地方，有一条调用子程序（其入口地址为100）的指令：“call 100”，如图（a）所示。. 对用户程序原封不动的装入，不能使它正确运行，因为在执行到位于绝对地址20KB+3000处的“call 10

9、0”指令时，它就会转到绝对地址100处去调用所需的子程序，而这个地址却是在操作系统里面，如图（b）所示。 .把指令“call 100”中的100变换成20580，就是地址重定位，如图（c）所示。 . 若把程序A装入到（22KB25KB）的绝对地址空间里，那么call指令中地址100所对应的绝对地址就是22KB+100=22628了。如图（d）所示。 即在程序装入内存之前，程序指令中的地址就已经是绝对地址，已经正确地反映了它将要进入的存储区位置。3.2.2. 地址的定位方式和静态重定位 .绝对定位方式 (1). 优点是程序中的逻辑地址与实际内存的物理地址相同，不再需要对指令中的地址进行任何重定位

10、，装入到指定的内存位置就可以运行了。缺点是编程人员要熟悉内存使用情况，要小心对待指令中的地址，不能出差错；程序在内存不能移动，只能固定在该存储区内；对程序所作的微小修改，都可能牵扯到程序整体的变动；不适用多道程序设计环境。 静态重定位方式 (2) 要有重定位装入程序，功能是：根据当前内存使用情况，为欲装入的二进制目标程序分配所需存储区；根据所分配的存储区，对程序中的指令地址进行重定位；将重定位后的二进制目标程序装入到指定的存储区中。 . 用户提供相对于“0”编址的二进制目标程序。通过重定位装入程序的加工，目标程序进到分配给它的物理地址空间，程序指令中的地址都被修改为正确反映该空间的情形。 .

11、由于地址重定位在程序执行前完成，因此称为“静态重定位”，或“静态地址绑定”。特点是：重定位由软件实现，无须硬件支持；在程序运行前完成地址重定位工作；地址重新计算和修改是在程序装入时集中完成；物理地址空间里的目标程序与原逻辑地址空间里的目标程序已不相同；位于物理地址空间里的用户程序不能在内存中移动，除非重新进行地址定位；适用于多道程序设计环境。 静态重定位在装入时一次性集中把程序指令中所有地址全部加以重定位；动态重定位则是每执行一条指令时，才其地址加以重定位。 静态重定位在程序运行之前完成地址转换；动态重定位则是将地址转换的时刻推迟到指令执行时进行。 若将地址定位的时间推迟到程序执行时进行，那么

12、称其为地址的“动态重定位”方式。 .动态重定位方式 (3). 对程序实行动态重定位需要硬件支持：一个地址转换机构。它由地址转换线路和一个“定位寄存器”（也称“基址寄存器”）组成。这时，用户程序不做任何修改地装入到分配给它的内存空间中。当调度到程序运行时，就把它所在物理空间的起始地址加载到定位寄存器中。CPU每执行一条指令，就把指令中的相对地址与定位寄存器中的值相“加”，得到绝对地址。然后按这绝对地址去执行指令，访问所需要的存储位置。 xxxxxx22KB22KB+10023KB24KB25KB22KB+3000call 1000操作系统20KB(b)用户程序A的相对地址空间xxxxxx0100

13、1KB2KB3KB3000call 100(a)22KB定位寄存器1002262822528内存.静态重定位和动态重定位的比较 (4). 静态重定位由软件完成地址转换；动态重定位由硬件地址转换机构完成。 . 静态重定位时原来的指令地址被修改了；实行动态重定位，不对指令本身做修改。 用户区分为“使用区”和“空闲区”两部分，如图（b）所示。使用区是用户作业程序真正占用的连续存储区域；空闲区是分配给了用户、但未被用户使用的区域，称为“内部碎片”。 1.单一分区存储管理 . 单一分区存储管理的系统，任何时刻只有一个用户程序驻留内存。因此内存为两个部分：供操作系统使用的系统区和供用户程序使用的用户区。

14、作业3作业2作业1内存0ab操作系统用户区内存0ab操作系统使用区空闲区用户区c(a)(b).单一分区存储管理系统的特点： (1)总是把一个连续的用户区分配给一个用户使用，如图（a）中的ab区域。 (2)(3) 这种系统只适用于单用户的情况。 (4) 进入内存的作业，独享系统中的所有资源 ，包括内存中的整个用户区。 (5) 由于整个用户区都分配给了一个用户，因此作业程序进入用户区后，没有移动的必要。所以采用这种存储管理策略，对用户程序实行静态重定位。 3.2.3 单一连续分区存储管理 每次只能有一个作业进入内存，故不适用于多道程序设计，整个系统的工作效率不高，资源利用率低下； 内存0ab操作系

15、统使用区空闲区ca界限寄存器. 实行静态重定位，不能阻止用户有意无意地通过不恰当的指令闯入操作系统所占用的存储区域。 . 在单一分区存储管理中，为有效阻止用户程序指令中的地址闯入操作系统所占用的区域，在CPU中会设置一个用于存储保护的专用寄存器“界限寄存器”，如图所示。 . 界限寄存器中，总是存放内存用户区的起始地址。CPU在核心态下工作时，允许访问内存中的任何地址；CPU在用户态下工作时，对内存的每一次访问，都要在硬件的控制下，与界限寄存器中的内容进行比较。一旦发现所访问的地址小于界限寄存器中的地址，产生“地址越界”中断，阻止这次访问的进行，从而将作业限制在规定的存储区域内运行，确保操作系统

16、中的信息不受外来的破坏。 单一分区存储管理的缺点 .(1)(2) 只要作业比用户区小，那么在用户区里就会形成碎片，如果用户作业很小，那么这种浪费是巨大的； (3) 若用户作业的相对地址空间比用户区大，那么该作业就无法投入运行，因为大作业无法在小内存上运行。 “覆盖”是早期提供的扩充内存的技术，它允许一个作业的若干个程序段使用同一存储区，被共用的存储区称为“覆盖区”。程序段存放在磁盘上，需要时由操作系统完成对它们的调入或调出。 覆盖技术 2.MAIN 10KBA 50KBB 30KBC 30KBD 20KBE 40KB链接编辑MAIN 10KBA 50KBB 30KBC 30KBD 20KBE

17、40KB0180KB(a)(b)(c)10KB50KB40KBMAINA或BC或D或E.比如，用户作业程序的调用结构如图（a）所示。 . 通过连接装配的处理，该作业将形成一个需要存储量180KB的相对地址空间，如图（b）所示。 . 程序中的子程序A和B不可能同时调用，子程序C、D和E也不能同时出现。除主程序必须用内存中的10KB外，A和B可共用存储量为50KB的存储区，C、D和E可共用存储量为40KB的存储区，如图（c）所示。 对换技术 “对换”的思想是：将作业信息都存放在辅助存储器上，根据单一分区存储管理的分配策略，每次只让其中的一个进入内存投入运行。当运行中提出输入/ 输出请求或分配给的时

18、间片用完时，就把它从内存“换出”到辅存，把辅存里的另一个作业“换入”内存运行，产生出“多道”的效果。 。 3.作业1作业2作业3辅助存储器内存储器操作系统用户区换出换入3.2.4 固定分区存储管理1.基本思想 所谓“固定分区”存储管理，是指预先把内存的用户区划分成若干个连续的分区，它们的尺寸可以相同，也可以不同。划分后，内存中分区的个数以及每个分区的尺寸保持不变。每个分区里只允许装入一个作业运行。 2.对作业的组织操作系统0100KB200KB400KB700KB800KB第1分区第2分区第3分区第4分区多个队列操作系统第1分区第2分区第3分区第4分区单个队列(a)(b) 系统可以为每个分区设

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

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

21、.作业程序一次性全部装入分配给它的连续分区。 .实行的是静态重定位。 .会产生内部碎片，引起内存资源的浪费。 3.3.1可变分区存储管理的基本思想 可变分区存储管理的基本思想是：作业要求装入内存时，若内存有足够的连续存储空间供使用，那就依作业相对地址空间的大小，划分出一个分区分配给它。 .作业C10KB作业B20KB作业A15KB内存操作系统空闲区(a)内存操作系统空闲区作业A15KB内存操作系统空闲区作业A15KB作业B20KB内存操作系统空闲区作业A15KB作业B20KB作业C10KB(b)(c)(d)(e) 图（a）表明后备作业队列里，作业A需要内存15KB，作业B需要20KB，作业C需

22、要10KB，等等。 . 图（b）表示系统初启时的情形，整个系统里没有作业运行，用户区空闲。 . 图（c）表示作业A装入内存时，为它划分了尺寸为15KB的分区。用户区被分成两个分区，一个是已分配的，一个是空闲区。 . 图（d）表示作业B装入内存时，为它划分了尺寸为20KB的分区，此时的用户区被分成了三个分区； . 图（e）表示作业C装入内存时，为它划分了一个尺寸为10KB的分区，此时的用户区被分成了四个分区。 随着作业对存储区域的不断申请与释放，发展趋势是：分区的数目会逐渐增加，有的分区尺寸在逐渐减小，甚至有可能出现内存里有空闲区、但每个都满足不了作业程序的要求而无法分配出去的情形。在存储管理中

23、，把那些无法满足作业存储请求的空闲区称为“外部碎片”。 . 可变分区存储管理模式引发了许多新的问题。只有解决这些问题，可变分区存储管理才能付之以实现。 内存操作系统空闲区236(a)020256内存操作系统空闲区220(b)020256作业A16作业B100内存操作系统空闲区120(c)020作业A16256作业C7036136作业B100内存操作系统空闲区50(d)020作业A1625636136作业C70空闲区100内存操作系统空闲区50(e)020作业A1625636136作业C70空闲区25内存操作系统空闲区50(f)020作业A1625636136作业D752062062061113

24、6.实行可变分区存储管理必须解决的问题： (1)(2)(3)采用地址动态重定位技术，使程序能在内存中移动，为空闲区的合并提供保证。 记住各个分区的使用情况，当一个分区被释放时，能方便地判定它的前、后分区是否为空闲区。若是空闲区，就进行合并，形成一个大的空闲区。 给出分区分配算法 。 静态重定位是在程序运行之前完成地址转换的；动态重定位却是将地址转换的时刻推迟到指令执行时进行。 实行静态重定位，原来的指令地址部分被修改了；实行动态重定位，只是按照所形成的地址去执行这条指令，并不对指令本身做任何修改。 静态重定位是在装入时一次集中地把程序指令中所有要转换的地址全部加以转换；而动态重定位则是每执行一

25、条指令时，对其地址加以转换。 静态重定位是由软件完成地址转换工作的；动态重定位则由一套硬件提供的地址转换机构来完成。 1.基本思想2.地址静态和动态重定位的比较3.3.2 地址的动态重定位 把相对地址空间中的用户作业程序“原封不动” 地装入到分配给它的绝对地址空间中去。执行某条指令时，才根据当前程序所在区域，对指令中的地址进行重定位。即指令中地址的转换是在程序执行时动态完成的，故称为地址的“动态重定位”。 0用户作业A的相对地址空间XXXXXX1001KB2KB3000call 1003KB0XXXXXX22KB+10023KB24KB22KB+3000call 10025KB20KB22KB

26、22KB定位寄存器2262822528操作系统内存. 一是调度到某作业时，若系统的每个空闲区尺寸都小于它的需要，但空闲区总存储量大于它的存储请求，于是进行空闲区合并，得到一个大的空闲区，满足该作业的需要；一是只要有作业运行完归还所占用的存储区，系统就进行空闲区的合并。 释放区的前、后邻接分区都是空闲区。因此，释放区应该和前、后两个邻接的空闲区合并成一个新的空闲区。 释放区的前邻接分区是已分配区，后邻接分区是空闲区。因此，释放分区应该和后邻接的空闲区合并成一个新的空闲区。 释放分区的前邻接分区是空闲区，后邻接分区是已分配区。释放区应该和前邻接的空闲区合并成一个新的空闲区。 释放分区的前、后邻接分

27、区都是已分配区，没有合并的问题存在。 3.3.3 空闲区的合并1.前后相邻接分区的四种关系2.空闲分区合并的时机已分配区空闲区释放分区空闲区已分配区释放分区空闲区空闲区释放分区已分配区已分配区释放分区. 若有作业运行结束，则根据作业名到已分配表里找到它的表目项，将该项的 “状态”改为“空”，随之在空闲区表里寻找一个状态为“空”的表目项，把释放分区的信息填入，并将表目项状态改为“空闲”。 作业提出存储需求时，查空闲区表里状态为“空闲”的表目项。若该项的尺寸能满足所求，就将它一分为二：分配出去的那部分在已分配表里找一个状态为“空” 的表目项进行登记，剩下的部分仍在空闲区表里占据一个表目项。 3.3

28、.4 分区的管理与组织方式1.表格法 设置两张表：“已分配表”和“空闲区表”。其中“序号”是表目项的顺序号，“起始地址”、“尺寸”、“状态” 都是该分区的相应属性。由于系统中分区的数目是变化的，因此每张表格中的表目项数要足够的多，暂时不用的表目项的状态被设为“空”。 内存操作系统空闲区(8KB)作业B(32KB)空闲区(32KB)作业D(120KB)空闲区(300KB)序号起始地址尺寸状态12345020KB28KB60KB92KB212KB512KB28KB32KB作业B空空空92KB120KB作业D序号起始地址尺寸状态1234560KB32KB作业B空闲空空作业D20KB8KB212KB3

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

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

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

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

33、为分配的对象，尽可能地不把大的空闲区分割成小的分区，以保证大作业的需要。(3) “最坏适应”算法从当前所有空闲区中找出一个能满足存储需求的、最大的空闲分区作为分配的对象。这种方案的出发点是照顾中、小作业的需求。 2.可变分区存储管理的特点3.可变分区存储管理的缺点.作业一次性地全部装入到一个连续的存储分区中。 .分区是按照作业对存储的需求划分的，因此不会出现内部碎片这样的存储浪费。 .为确保作业能够在内存中移动，要由硬件支持实行指令地址的动态重定位。 .只要作业的存储需求大于系统提供的整个用户区，该作业就无法投入运行。 .有可能出现极小的分区暂时分配不出去的情形，产生外部碎片。 由于是通过移动

34、程序来达到分区合并的目的，势必增加系统在这方面的投入与开销。 伙伴系统 3.3.6. 伙伴系统是对固定分区和可变分区两种存储管理“扬长避短”后，提出的一种折中方案。 . 伙伴系统中，可用内存分区的大小为：2K，LKU其中：2L表示分配的最小分区的尺寸；2U表示分配的最大分区的尺寸。在实际操作系统中，最小分区尺寸一般为212。如果进程申请的存储空间大小为S ，且2U-1S2U，则将整个2U大小的分区分配给该进程；否则，该分区被分割成两个大小相等的伙伴分区，大小为2U-1；再判断S是否满足条件：2U-2S2U-1，若满足条件，则将两个伙伴中的任何一个分配给该进程。否则，将其中一个伙伴又分成两个大小

35、相等的伙伴分区；此过程一直继续进行，直到产生的分区满足条件U-JS并2U-J-1S2U-J，将2U-J大小的分区分配给该进程；当U-J-10，所以p=(2es)1/2给出的是作业最佳页面尺寸p与作业尺寸s间的关系，它使系统的额外开销为最小。 3.4.3 内存块的分配与回收1.对内存块的管理.存储分块表单链表操作系统作业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已分配1

36、3已分配14已分配15空闲空闲块总数：6 系统维持一张表格，表格表项与内存中的一块相对应， 记录该的块使用情况。只要表格中 “空闲块总数” 记录的数目大于请求的存储量，就可进行分配 ，并把分配出去的块的状态改为 “已分配” 。作业完成后归还存储块时，就把表中相应块的状态改为“空闲”。 单链表存储分块表 把空闲块链接成一个单链表加以管理，系统必须设置一个空闲块链表的起始地址指针，以便进行存储分配时能够找到空闲的内存块。无论是进行空闲块的分配还是作业完成后归还存储块，都要调整空闲块间的链表指针。 作业虽然不占据连续的存储区，但每次仍要求一次全部进入内存。因此，如果作业很大，其存储需求大于内存，那么

37、还是存在小内存不能运行大作业的问题。 用户作业的相对地址空间按照块的尺寸划分成页。这种划分是在系统内部进行的，用户感觉不到，即对用户是“透明”的。 2.分页式存储管理的特点.内存存储器事先被划分成相等尺寸的块，它是进行存储分配的单位。 . 相对地址空间中的页可以进入内存中的任何一个空闲块，并且分页式存储管理实行的是动态重定位，因此它打破了一个作业必须占据连续存储空间的限制，作业在不连续的存储区里，也能够得到正确的运行。 3.分页式存储管理的缺点.平均每一个作业要浪费半页大小的存储块。 .位图 用二进制位与内存块的使用建立起关系，为“0”，表示对应块空闲；为“1”，表示对应块已分配。 11110

38、10010011110空闲块总数：60123456701字节号位号位图引入从固定分区到可变分区，再到分页方式存储管理，是为了提高内存利用率。引入分段存储管理方式，是为了满足用户在编程和使用上多方面的要求。（1）方便编程（2）信息共享（3）信息保护（4）动态增长（5）动态链接1、分段进程地址空间被划分为若干段，每个段都有名字，如主程序段、子程序段、数据段、栈段等。可以用段号代替段名，每个段都是从0开始编址，并采用一段连续的地址空间。各段长度不等。整个进程地址空间分成多个段，所以进程地址空间是二维的，逻辑地址是由段号（段名）和段内地址组成。段号段内地址2、段表进程地址空间分成几个段，系统为每个段分

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

40、。于是，用户的逻辑地址空间是二维的。 分段式存储管理中的逻辑地址. 分段式存储管理中，逻辑地址用两个成分描述：段名和段内元素名。系统接受了用户的逻辑地址空间后，在内部就用段号s代替段名，用段内位移d代替段内元素名。 段号s段内位移d3116150. 在这种地址结构中，由于是各用16个2进制为表示段号s和段内位移d，因此允许用户逻辑地址空间最多有64K个段，每段的最大长度是64KB。 3.分段式存储管理中的内存分配. 在分段式存储管理中，作业逻辑地址空间的段原封不动离散地存放到内存的不同分区中。即系统为每个段分配一个连续的分区，而各段在内存中则不必连续。系统为每个作业进程设置一个段表，记录逻辑地

41、址空间中各段在内存中的基址，通过段表实现逻辑地址到内存物理地址的映射。段 0MAIN08KB段 1P05KB段 2D06KB段 3Q04KB逻辑地址空间段号 段长 基址 0 8KB 1 5KB 2 6KB 3 4KB 段表段MAIN段Q段D段P操作系统内存储器 比如，指令里给出一个逻辑地址s,d时，就用地址中的段号s去查段表，从那里得到该段在内存中的基址，由基址“加上”逻辑地址中的段内位移，就得到了所对应的物理地址。 . 改变某程序段的大小，就会影响其他无关程序段的起址；对某个程序段进行的修改，会影响到其他相关部分，就可能要对所有的程序重新进行链接编辑。 一维地址空间的组织方式，有如下缺点：

42、(1)(2)不利于按照程序段的性质，实施存储保护和共享。 . 所谓“分段式”存储管理，即要求用户将自己的作业程序以多个相互独立的称为“段”的地址空间提交给系统，每个段都是一个从“0”开始的一维地址空间，长度不一。操作系统按照段长为作业分配内存空间。 .分段式组织方式的优点：(1) 每个程序段是一个独立的地址空间，它们可独自增长或减小而不用顾及别的程序段，不会影响到其他程序段的地址空间。 (2) 每个程序段是一个独立的逻辑实体（比如一个过程、一个数组或一个堆栈），因此可以对它们进行不同类型的存储保护 。(3) 独立的地址空间有助于实施对过程和数据的共享，不必在每一个用户作业的地址空间里都必须有相

43、关的备份。 通过编译程序在编译过程中建立的各种表，说明页式及段式存储管理中，作业程序地址空间组织形式的不同。 例 ：解： 在编译过程中会建立很多表，其中主要有：供打印程序清单的源程序文档；由变量名及其属性组成的符号表；由程序中所有的整型、实型常量组成的常量表；包含程序语法分析结果的语法分析树；内部过程调用时使用的堆栈。.在分页式管理时，这5个表必须限定在一个一维的地址空间里，如图(a)所示。 使用使用使用使用使用空闲空闲空闲空闲堆栈语法分析树常量表源程序文档符号表(a)0KB4KB8KB12KB16KB20KB0KB4KB8KB12KB符号表段00KB源程序文档常量表段1段3段40KB4KB8

44、KB12KB16KB语法分析树0KB4KB8KB12KB堆栈段2(b). 在分段管理时，是把这些表视为一个个相互独立的地址空间，比如：段0、段1等，它们组成了整个用户的地址空间，如图(b)所示。 . 在分段式存储管理时，要指示存储空间里的一个地址，必须提供两部分内容：段号和段内位移。即逻辑地址应该是二维的：段号，段内位移。. 在图(a)所示的32位地址结构中，由于是各用16个二进制位表示段号s和段内位移d，因此表示用户的逻辑地址空间最多可以有216个段，每段最大长度是64KB。 3116 150sd段号段内位移ds段号段内位移03123 22(a)(b). 图(b) 所示的32位的地址结构中，

45、由于用9个二进制位表示段号s，用23个二进制位表示段内位移d，因此表示允许用户的逻辑地址空间中最多可以有29个段，每段的最大长度是223=8192KB。 用相对地址中的段内位移d与该段段长比较：如果大于段长，则表示该地址出错；否则，由段的基址和段内位移d拼装出所需的绝对地址，从而实现对内存的访问。 若段号大于段表长度，表示越界出错。否则以段号为索引查段表，得到该段在内存的基址。 从CPU给出的相对地址数对：段号s，段内位移d中提取段号s，用来进行地址转换。 3.4.2 分段式存储管理的地址转换过程 实施分段式存储管理时，系统为每个用户程序设置一个段表，用于记录各段在内存中的存放信息。逻辑空间中

46、有多少段，段表里就有多少个表项。每个表项包括的信息有段号、段长、该段的基址（即起始地址）等。. 为完成地址变换，需要一个段表控制寄存器。当作业调度时，把调度到的作业的段表起址和段表长度(即段表表项的数目)放入寄存器中，以期达到映射不同作业的目的。 段表起址段表长度段表控制寄存器段号s段内位移d相对地址越界中断段号 段长 基址 0 1 2 3 段表d内 存操作系统段 1段 3段 0段 2绝对地址.地址转换的具体步骤(1)(2)(3)段号(s)段内位移(d)相对地址段表段表基址寄存器段号长度基址基址段内位移物理地址段sd内存程序分段地址转换机制.分段地址转换机制图示：3.5.3 存储保护与共享1.

47、分页式存储中的存储保护与共享 . 在页式环境下，存储保护以页面为单位。在页表的每个表项里设置一个所谓的“保护位”，由该位的不同取值定义对应页是可读、可写或只可读等。. 被共享的程序文本不一定正好在一个或几个完整的页面中，有可能一个页面中既有允许共享的内容，又有不能共享的私有数据。因此，在分页环境下实现页面的共享比较困难，但也不是不可能。 3311. 若页面尺寸为50KB，文本编辑程序的代码是可重入的，需要3页，用户进程的数据段需要一页。那么每个用户进程的逻辑地址空间为4页。如图画出三个进程的逻辑地址空间和对应页表，它们的02页都划归给文本编辑程序使用(ed1，ed2，ed3)，页表中的02表项

48、都对应于块号3、4和6；各进程的数据页(即dataA、dataB、dataC)都位于自己空间的第3页，分别存放在内存的2、8和11块。进程A的逻辑地址空间进程B的逻辑地址空间进程C的逻辑地址空间ed10ed21ed32dataA3ed10ed21ed32dataB3ed10ed21ed32dataC3进程A的页表031426320314263203142632页号帧号进程B的页表页号帧号进程C的页表页号帧号操作系统0123456789101112dataAed1ed2ed3dataBdataC内存(a)2.分段式存储中的存储保护与共享 在分段环境下，段是有完整意义的逻辑信息单位，为实行存储保护

49、，只需在段表表项里增加权限位，指出每段是可读的、可写的或只执行的等。每次进行地址映射时，都将这次访问的类型与权限位比较，若不符合就产生出错中断。. 在段式存储管理中很容易实现段的共享，只需在作业的段表中都增加一个表项，让该段的基址指向共享段在内存中的起始地址即可。 比如进程A和B要对文本编辑程序进行共享，那么可把文本编辑程序作为它们地址空间中的段0，如图所示。若文本编辑程序存放在内存43062起始的连续分区里，那么在所对应的各段表中，段号为0的表项的基址都是43062，从而可共享该文本编辑程序。 .文本编辑程序段0程序段段1数据段段2进程A的逻辑地址空间文本编辑程序段0程序段段1数据段段2进程

50、B的逻辑地址空间堆栈段段30252861基址243062操作系统内存进程A的段表段号段长025286 1基址243062进程B的段表段号段长3A的数据段文本编辑程序B的数据段A的程序段B的堆栈段43062B的程序段(b)4.分段与分页的区别 (1) 页是信息的物理单位，段是信息的逻辑单位：系统根据帧的大小划分页，不考虑页中的信息是否完整。因此，一页对应的是信息的一个物理单位；段是基于用户程序结构提出的存储管理模式，用户知道自己的程序分多少段，每段在逻辑上都是相对完整的一组信息。所以，段是信息的逻辑单位。 (2)页的尺寸由系统确定，段的尺寸因段而异。分页式存储管理中的页的尺寸是由系统确定的，它与

51、内存块的大小相同。段的长度取决于用户编写的程序，不同的段有不同的长度。(3) 页式地址空间是一维的，段式地址空间是二维的 ：在分页式存储管理时，用户必须通过链接编辑程序，把各程序段链接成一个相对于0编址的一维线性空间，用户向系统提供的是一个一维的逻辑地址空间；在分段式存储管理时，用户不把各程序段连接成一个相对于0编址的一维线性空间，各程序段之间是通过段号，段内位移进行访问的。因此，用户向系统提供的是一个二维的逻辑地址空间。虚拟存储器的引入前面介绍的存储管理方案要求进程全部装入内存才可运行。但这会出现两种情况：有的作业因太大，内存装不下而无法运行。系统中作业数太多，因系统容量有限只能让少数作业先

52、运行。3.6.1 虚拟存储的概念1.程序执行的“局部性”原理 由于程序执行具有“局部性”，因此实际运行时，没有必要把全部信息都放在内存里。只要合理组织，调度恰当，在发现所需访问的信息不在内存时，能够找到它，能够把它调入内存，那么不仅可以保证作业的正确执行，而且还提高了系统的资源利用率，使得系统具有更高的运行效率。 程序执行的“局部性”原理，是指程序在执行的某一时刻，并不是均匀地访问它的整个地址空间，而往往是集中于某一小部分区域。 程序执行的局部性，具体表现在几个方面 ： 除分支和调用指令，程序的执行都是顺序的。分支和调用指令在所有程序指令中只占很少一部分。大多数情况下，要读取的下一条指令肯定都

53、是紧跟在已取到的上一条指令之后的。 (1)(2) 程序中很少会出现很长的、一个过程调用接着又一个过程调用的调用序列。在较短的时间内，指令的引用大多局限在很少几个过程中，不会一会儿是这个过程，一会儿是那个过程。 2.虚拟存储的概念(3) 大多数循环结构都由较少的几条指令重复若干次组成，循环过程中的计算，也多被限制在程序中的一个很小的相邻部分完成。 (4) 许多程序中的计算都涉及到对数组、文件记录之类数据的处理，而对这些数据的引用，其实都是对位置相邻的数据项进行操作。 程序执行的“局部性”原理给人们重要的启示是：其实程序并不是必须全部都在内存后才能运行，只要关键的那一小部分在内存就可以了。 . 有

54、了“局部性”原理的支撑，一个新程序运行时，只需把包含程序开始处的一个或几个块（页或段）从磁盘读入内存就行。运行过程中，若对存储器的访问在这些块里，那么通过页表或段表对逻辑地址的动态重定位，执行就可顺利进行。如果CPU需要访问一个不在内存中的逻辑地址，那就产生一个中断，告知CPU对内存的访问出现了故障。这时，操作系统就阻塞正在执行的进程，产生磁盘I/O请求，把包含引起访问故障的那个逻辑地址所在的块取到内存。这样，被阻塞进程就可重新成为就绪状态，继续运行下去。 . 作业提交给系统时，先进入辅存。运行时，只将部分信息装入内存，大部分仍保存在辅存中。运行过程中需要用到不在内存的信息时，再把它们调入，以

55、保证程序的正常运行。这样一个被用户认为有的、但实际上不存在的“大”存储器，就被称为“虚拟存储器”。. 虚拟存储器是一种扩大内存容量的设计技术，它把辅存作为计算机内存的后援。在虚拟存储意义下，用户作业的相对地址空间，就是系统提供给他的虚拟存储器。在多道程序设计环境下，每个用户都有自己的虚拟存储器。在提供虚拟存储管理的系统里，把用户作业的相对地址空间称为“虚拟地址空间”，里面的地址称为“虚拟地址”。. 有了“局部性”原理的支撑，有了操作系统新的工作模式，用户在程序设计时就完全不需要去顾忌内存的大小。这时给程序人员的感觉是，他面对的是一个巨大的“内存储器”，其大小只与磁盘存储器有关。虚拟存储要解决的

56、问题 3.(1)读取策略 所谓“预约式”，是利用磁盘I/O操作中所具有的寻道时间和旋转延迟特性，一次顺序读入后面的多个块，把可能需要的块提前读入供程序使用，这比需要哪块才去读哪块显得更加有效些。 .指在程序运行过程中，何时把所需要的块调入内存的策略。. 所谓“请求式”，指当访问需要某块里的信息、而这块当时又不在内存时，才把这块从辅存换入内存.放置策略 (2). 主要是针对请求页式管理的，当要把所需的页面信息从辅存调入内存时，内存必须要有空闲页。放置策略用来决定把所需要的页面存放到内存的哪个空闲页帧去。. 所谓“固定”的放置策略，就是静态放置策略，指为作业程序分配固定数目的帧，页面只能存放在这些

57、页帧里；所谓“可变”的放置策略，就是动态放置策略，是指分配给作业程序的页帧随需要不断变化。 (3)替换策略 . 如果放置时内存里没有空闲的区域，那么就必须先要把当前暂时不用的信息从内存替换出去，以便腾出位置进行放置，这是替换策略需要解决的问题。. 所谓“局部”替换策略，指只在分配给作业使用的帧里选择替换对象；所谓“全局”替换策略，指把整个内存页帧都作为替换的候选对象，不去管它们属于哪一个作业进程。 3.6.2 请求页式存储管理的基本思想最多可有2048页每页1KB第0页第1页第2页虚拟存储器第2045页第2046页第2047页第0块第1块第2块第29块第30块第31块内存储器1.与分页式相同处

58、 把内存划分成尺寸相同、位置固定的块。然后按照内存块的大小，把作业的虚拟地址空间（即以前的相对地址空间）划分成页。由于页的尺寸与块一样，因此虚拟地址空间中的一页，可以装入到内存中的任何一块中。 2.与分页式不同处 作业全部进入辅存。运行时，只装入要用的若干页，其他页仍在辅存。运行过程中，虚拟地址被转换成数对：(页号，页内位移)。由页号查页表，若该页在内存，运行就进行下去；若该页不在内存，表明“缺页”，运行无法继续。这时，就根据页号把该页从辅存调入内存。所谓“请求分页式”，即是当运行中需要某页时，再把它从辅存调入内存使用的意思。 3.6.3 缺页中断的处理1.缺页中断位页号块号缺页中断位辅存地址

59、在请求分页式存储管理中，是由页表表目项的“缺页中断位”来判断所需页是否在内存的。具体含义:缺页中断：该位为“1”，表示此页在内存；为“0”，表示不在内存，并发出“缺页”中断信号，以求得系统的处理，将所缺的页从磁盘调入内存。 页号：虚拟地址空间中的页号块号：该页占用的内存块号辅存地址：该页内容在辅助存储器上的存放地址。缺页时，缺页中断处理程序就会根据它的指点，把所需要的页调入内存。 当执行到作业2第0帧中的指令“call 8300”时，系统把虚拟地址8300转换成数对：（2，108）。 2.请求页式虚拟存储管理的实际运作过程 例 ：一个请求页式存储管理的整个运作过程。 346000已分配1已分配

60、2已分配3空闲4已分配5已分配6已分配7空闲8已分配9空闲帧号 状态存储分块表0操作系统0 1 21 1 42 0 5作业2第0页call 8300作业2第1页作业1第0页作业1第1页作业3第0页4KB8KB12KB16KB20KB24KB28KB32KB36KB40KB内存帧1帧0帧2帧3帧4帧5帧6帧7帧8帧9页面表信息长度 起址1 8KB 2 41602 12KB 3 46003 4KB 1 4820尺 寸作业号作业表页表控制寄存器0 1 51 1 6P I FP I F2 1 70 1 21 1 42 0 50 1 8P I F作业1的页表作业2的页表作业3的页表空闲帧空闲帧空闲帧(a