第五章 存储管理(2)答案.ppt

1、第四章 存储管理,第一节 存储管理的功能 第二节 内存资源管理 第三节 存储管理方式 第四节 外存管理技术 第五节 虚拟存储系统,存储管理的目的及功能（1）,目的：方便用户，使用户减少甚至摆脱对存储器使用的管理；提高内存资源的利用率，关键是实现内存共享 功能： 内存分配：通过建表、查表、改表和回收登录内存使用情况，按选定分配算法确定分区等,存储管理的目的及功能（2）,功能： 存储共享：节省内存空间，实现进程通信 内存保护技术：防止地址越界，防止操作越权 内存的扩充技术：使用虛存或自动复盖技朮提供比实际内存更大的空间 地址映射,逻辑地址与物理地址,在具有地址变換机构的计算机中，允许程序中编排的地

2、址和信息实际存放在内存中的地址有所不同。前者叫逻辑（相对）地址，后者叫物理（绝对）地址。 地址映射：将程序所产生的逻辑地址转换为存储空间的物理地址。,内存资源管理,内存分区 内存分配 碎片处理,内存资源管理,静态不等长分区 静态等长分区 动态异长分区,静态不等长分区,分区：系统运行前，将逐村划分成大小不等的若干区域，每个分区的大小可以预先确定，但系统开启后就不能再改变了。,管理：每个注册的作业必须规定其最大存储量，不得超过最大分区的大小。,分配：系统设置一张分区表，标明每块分区的大小位置 和使用状态，分区表按照分区从小到大顺序排列。分配时， 从说明的第一项开始依次查看每个分区的转台状态及大小，

3、 当状态可用，且其大小超过作业大小时，便可分配。,静态等长分配（分页）,存储空间被静态地划分为若干个长度相等的区域，每个区域称为一页。 字位影像图 空闲页面表/空闲页面链,动态异长分区,存储空间被动态地划分为若干个长度不等的区域 分配算法 最先适应算法FF(First Fit) 最佳适应算法BF(Best Fit) 最坏适应算法WF(Worst Fit),碎片处理,碎片 紧凑 紧凑的开销 修改被移动进程的地址信息 复制进程空间 实验：开始/程序/附件/系统工具/磁盘碎片整理,内存资源管理实例1,有一个系统，其内存容量为1024KB，有8个作业同时到达，各作业的内存量及运行时间如下表所示，假定系

4、统初启时，将内存1024KB按作业的编号顺序分给各道作业，并假定是多CPU下，分配到内存的作业都可以立即运行，问： 1S后，内存空白区按FF和Bf算法的方式将如何链接? 2S后，内存空白区按上述两种算法的方式又将如何链接? 这时（ 2S后），有作业9要求进入内存，它需要12KB内存量，按上述方法，系统将哪一块空白区分给它？,内存资源管理实例2,某计算机系统的内存容量为128KB，对存储器采用可变分区管理办法，现有3个作业J1,J2,J3在内存，其存储区间的分配如图所示： 现有一个需要25KB存储空间的作业J4请求装入内存， (1)若采用FF分配算法，请给出装入J4后的内存分配表；(2)若采用B

5、F分配算法，请给出装入J4后的内存分配表；(3)在只有J1,J2,J3三个作业的情况下,J2运行结束后撤离，请给出J2撤离后的内存分配表,内存“扩充”技术,交换（swap)：由操作系统做，用户不知道。 复盖（overlay)：由用户控制，操作系统提供覆盖机制。,存储管理方式,界地址存储管理 页式存储管理 段式存储管理 段页式存储管理,界地址存储管理,内存空间：动态地划分为若干个长度不同的区域 进程空间：由一个连续的区间构成，0L-1 地址映射：设内存中的起始地址为b 内存分配表/空闲区域表 首址寄存器/限长寄存器 物理地址=逻辑地址+首址寄存器内容,双对界 交换技术swapping Roll-

6、in,Roll-out,页式存储管理实现原理,基于程序在运行时不需要一开始都装入内存，更不应该把最近较长一段时间内不用的程序装入内存。 内存空间：静态地划分为若干等长的页面 物理地址=物理页首址+页内地址 进程空间：静态地划分为若干等长的逻辑页 逻辑地址=逻辑页首址+页内地址 页表/进程表/总页表 页表首址寄存器/页表长度寄存器/快表 地址映射p66,图4-15,分页式管理应用实例1,一个由4个页号（页号03），每页由1024个字节组成的程序，把它装入一个由8个物理块（块号为07）组成的存储器中，装入情况如下表所示，已知下面的逻辑地址0，100，1，179，2，785，3，1010（第一个元素

7、为页号，第二个元素为页内地址），请按页表求出对应的物理地址,页式存储管理的优点,虛存量大，适合多道程序运行，用户不必担心内存不够的调度操作。 内存利用率高，不常用的页面尽量不留在内存； 不要求作业连续存放，有效地解决了“碎片”问题。与分区式比，不需移动作业；与多重分区比，无零星碎片产生.,页式存储管理的缺点,要处理页面中断、缺页中断处理等，系统开销较大； 有可能产生“抖动”; 地址变換机构复杂，为提高速度采用硬件实现，增加了机器成本,分段式存储管理,内存空间：动态地划分为若干不等长的物理段 物理地址=段首址+段内地址 进程空间：静态地划分为若干不等长的逻辑段 逻辑地址=段号+段内地址 段表/进

8、程表/空闲表 段表首址寄存器/段表长度寄存器/快表 地址映射p70,图4-26,段,页式存储管理的对比表,段式 页式 由用户设计，有逻辑意义 分页用户不可见，由OS划分 段面是信息的逻辑单位 页面是信息的物理单位 便于段的共享和动态链接 页一般不能共享 段长不等，可动态增长 页面大小相同，不能增长 段具有二维地址空间 页具有一维地址空间 管理形式相似，但概念不同,段页式存储管理,内存空间：静态地划分为若干等长的物理页 物理地址=物理页首址+页内地址 进程空间：静态地划分为若干不等长的逻辑段，每段又静态地划分为若干等长的逻辑页 逻辑地址=段号+逻辑页号+页内地址 段表/页表/进程表/空闲表 段表

9、首址寄存器/段表长度寄存器/快表 地址映射p74,图4-37,分段式管理应用实例,给定下面段表，已知下列逻辑地址0，430，3，400，1，10，2，500，4，42，1，11（第一个元素为段号，第二个元素为段内地址），分别求其对应的物理地址,段式存储管理,段,页式存储管理的对比表 段式存储管理的优越性:段的共享与动态分配，一般由硬件设备的多种支持，特别是近代的优化编译巳进入CPU内部设计。段共享的先决条件是程序段可重入，即前面一段没有退出前，在不影响工作前提下，后面一段又可重新装入。而可重入程序的特点是执行程序中指令不变称纯代码（纯码）,而工作区和数据区由调用者自带。,段页式存储管理特点,每

10、一段分若干页，再按页式管理，页间不要求连续； 用分段方法分配管理作业，用分页方法分配管理内存； 兼有段式和页式管理的优点,系统复杂性和开销增大，一般在大型机器上才使用.,外存管理技术,外存区间划分：基本单位为块 外存空间分配：外存分配的基本单位是块，而内存的分配单位是单元 界地址存储管理外存空间分配 页式存储管理外存空间分配 段式存储管理外存空间分配 段页存储管理外存空间分配,虚拟存储管理,虚存是由操作系统调度，采用内外存的交换技术，各道程序在必需使用时调入内存，不用的调出内存，这样好象内存容量不受限制。,虚拟存储系统,虚拟存储是一种借助于外存 空间，从而允许一个进程在其运行过程中部分地装入内

11、存的技术 虚拟 页式存储系统 虚拟段式存储系统 虚拟段页式存储系统,虚存的特点,虚存容量不是无限的，极端情况受内存和外存可利用的总容量限制 虚存容量还受计算机总线地址结构限制 速度和容量的“时空”矛盾，虛存量的“扩大”是以牺牲CPU工作时间以及内外存交換时间为代价的，以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术,概述,程序局部性原理 时间局部性 一条指令被执行了，则在不久的将来它可能再被执行 空间局部性 若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用,虚拟页式存储管理,基本思想 在进程开始运行之前，不是装入全部页面，而是装入几个或零个页面，之后根

12、据进程运行的需要，动态装入其它页面； 当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面,页表表项,页号、内存块号、外存块号 、访问位、内外标志、修改标志 内外标志：表示该页是在内存还是在外存 修改位：查看此页是否在内存中被修改过,页表设计,页表内容举例 淘汰位/修改位/保护位/中断位/引用位/缺用位等 快表:因页面较多，页表在内存，取一次数要访问内存两次。,内存页面分配策略,平均分配 将内存中所有物理页等份分给进入系统的进程。 按进程长度比例分配 Ai=si/S*m 按进程优先级比例分配 按进程长度和优先级比例分配,外存块分配策略,静态分配 一个进程在运行前

13、，将其所有页面全部装入外存，当某外存页被调入内存时，所占用的外存 页面并不释放 动态分配 一个进程在运行前，仅将未装入内存的那部分页面装入外存，当某外存页被调入内存时，释放所占用的外存 页面,缺页中断（Page Fault）处理,在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，准备将该页调入内存 此时应将缺页的进程挂起（调页完成唤醒）,如果内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应页表项目的驻留位及相应的内存块号 若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被

14、修改过，则要将其写回外存）,思考,缺页中断同一般中断的区别？,缺页中断同一般中断都是中断，相同点是： 保护现场 中断处理 恢复现场 不同点： 一般中断是一条指令完成后中断，缺页中断是一条指令执行时中断 一条指令执行时可能产生多个缺页中断。如指令可能访问多个内存地址，这些地址在不同的页中。,页面调入方法,请调 页故障发生/缺页时，进行页面调度 预调 页故障发生/缺页前，进行页面调度,页面淘汰算法（1）,最优淘汰算法（OPT）（Optimal Replacement Algorithm） 淘汰以后不再需要的或最远的将来才会用到的页面 先进先出算法(FIFO） （First Input First

15、Output）,又称轮转法（RR） 选择在内存中驻留时间最长的页并淘汰之 最近最少使用页面先淘汰（LRU） （Least Recently Used） 选择最后一次访问时间距离当前时间最长的一页并淘汰之 即淘汰没有使用的时间最长的页,页面淘汰算法（2）,最近没有使用页面先淘汰（NUR） 最不经常使用的页面先淘汰（LFU）（Least Frequent Used） 最经常使用的页面先淘汰（MFU）（Most Frequent Used）,LRU的硬件解法： 系统为每页设置一个寄存器R，每当访问这一页时，将该页对应的寄存器R置1，以后每个时间间隔将所有的R左移一位，当淘汰一页时就选择R值最大的页。

16、也就是说R值越大，对应的页未被使用的时间越长。所以淘汰的是最久未使用的页。显然，R的位数越多越精确。但系统硬件成本也就越高。,LRU软件解法： 设置一个页号栈，当一个页面被访问时，就立即将它的页号压入页号栈，并检查页号栈中是否有与刚压入栈顶的相同的页号，若有，则从页号栈中抽出，以保证页号栈中无相同的页号。当系统要淘汰一节时，总是从页号栈底取出一个页号淘汰，即淘汰的页是最久未使用的。,LRU近似算法： 在页表中增加一访问位，每当访问一页时，将该页的访问位由硬件置1，软件周期（T）性地将所有访问位置0。在时间T内，访问过的页其访问位为1，反之为0，淘汰为0 的页。 缺点：T难定。太小，访问位为0的

17、页相当多，所选的不一定是最久未用的。太大，所有页的引用位可能都为1，找不到合适的淘汰页。,最不经常使用（LFU） 选择访问次数最少的页面淘汰之 与LRU的硬件解法类似。,某程序在内存中分配三个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按FIFO、 LRU、OPT算法分别计算缺页次数 假设开始时所有页均不在内存,例1,FIFO 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 4 3 5 5 5 2 1 1 页2 4 3 2 1 4 3 3 3 5 2 2 页3 4 3 2 1 4 4 4 3 5 5 x x x x x x x x x 共缺页中断9次

18、,FIFO,LRU 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 4 3 5 4 3 2 1 5 页2 4 3 2 1 4 3 5 4 3 2 1 页3 4 3 2 1 4 3 5 4 3 2 x x x x x x x x x x 共缺页中断10次,LRU,OPT 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 1 1 5 5 5 2 1 1 页2 4 3 3 3 3 3 3 3 5 5 5 页3 4 4 4 4 4 4 4 4 4 4 x x x x x x x 共缺页中断7次,OPT,练习,某程序在内存中分配四个块，访问页的走向为4，3，2，

19、1，4，3，5，4，3，2，1，5，按LRU、OPT算法分别计算缺页次数 假设开始时所有页均不在内存,LRU,4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 4 3 5 4 3 2 1 5 页2 4 3 2 1 4 3 5 4 3 2 1 页3 4 3 2 1 4 3 5 4 3 2 页4 4 3 2 1 1 1 5 4 3 x x x x x x x x 共缺页中断8次,OPT,4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 1 1 5 5 5 5 1 1 页2 4 3 2 2 2 2 2 2 2 5 5 页3 4 3 3 3 3 3 3 3 3

20、3 页4 4 4 4 4 4 4 4 4 4 x x x x x x 共缺页中断6次,有一虚拟存储系统，采用先进先出的页面淘汰算法。在内存中为每个进程分配3块。进程执行时使用页号的顺序为 4 3 2 1 4 3 5 4 3 2 1 5 (1)该进程运行时总共出现几次缺页。 (2)若每个进程在内存有4块，又将产生几次缺页。 (3)如何解释所出现的现象。,例2,FIFO 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 4 3 5 5 5 2 1 1 页2 4 3 2 1 4 3 3 3 5 2 2 页3 4 3 2 1 4 4 4 3 5 5 x x x x x x x x

21、x 共缺页中断9次,m=3,FIFO 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 1 1 5 4 3 2 1 5 页2 4 3 2 2 2 1 5 4 3 2 1 页3 4 3 3 3 2 1 5 4 3 2 页4 4 4 4 3 2 1 5 4 3 x x x x x x x x x x 共缺页中断10次,m=4,m=3时，缺页中断9次 m=4时，缺页中断10次 FIFO页面淘汰算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加,(1) 分配给进程的物理块数 (2) 页本身的大小 (3) 程序的编制方法 (4) 页淘汰算法,影响缺页次数的因素,在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动 原因： 分配给进程的物理页面数太少 页面淘汰算法不合理,颠簸（抖动）,工作集模型,工作集是进程活跃地访问页面的集合 工作集随时间而变化 工作集大小与窗口大小密切相关 工作集模型实现的难点在于 动态记录各个进程的工作集,页故障率反馈模型,系统可以利用页故障率的反馈信息来动态地调整页面的分配。 规定页故障率的上限和下限。,1、段表内容 增加： 特征位（