第6章--虚拟存储管理1PPT课件.ppt

第第6章章 虚拟存储管理虚拟存储管理_1 6.1虚拟存储器的引入虚拟存储器的引入前面介绍的存储管理方案要求进程全部前面介绍的存储管理方案要求进程全部装入内存才可运行。但这会出现两种情装入内存才可运行。但这会出现两种情况：况：有的进程因太大，内存装不下而无法有的进程因太大，内存装不下而无法运行。运行。系统中进程数太多，因系统容量有限系统中进程数太多，因系统容量有限只能让少数进程先运行。只能让少数进程先运行。2024/5/24 周五1968年年P.Denning 提出提出局部性原理（理论基础）：局部性原理（理论基础）：程序在执行时将呈现出局部性规律，即在一较短的程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应的，它所时间内，程序的执行仅局限于某个部分；相应的，它所访问的存储空间也局限于某个区域。访问的存储空间也局限于某个区域。程序执行时，大多数情况下是顺序执行的。程序执行时，大多数情况下是顺序执行的。过程调用会使程序的执行轨迹从一部分内存区域转至过程调用会使程序的执行轨迹从一部分内存区域转至另一部分区域，另一部分区域，但过程调用的深度不会超过但过程调用的深度不会超过5。程序中有许多循环语句，这些语句会重复多次执行。程序中有许多循环语句，这些语句会重复多次执行。程序中对数据结构的操作，往往局限在很小的范围内。程序中对数据结构的操作，往往局限在很小的范围内。局部性原理局部性原理局部性的表现局部性的表现 空间局部性空间局部性程序一旦访问某存储单元，不久后程序一旦访问某存储单元，不久后会访问其附近的存储单元。会访问其附近的存储单元。时间局部性时间局部性程序中的某条指令一旦执行，不久程序中的某条指令一旦执行，不久后会再次执行。后会再次执行。程序中的某个数据结构一旦被访问，程序中的某个数据结构一旦被访问，不久后会再次被访问不久后会再次被访问。虚拟存储器虚拟存储器 进程运行时，不全部装入内存，仅将当前要运进程运行时，不全部装入内存，仅将当前要运行的那部分装入内存。行的那部分装入内存。当进程访问不在内存的那部分程序和数据时，当进程访问不在内存的那部分程序和数据时，再将其装入内存。再将其装入内存。若此时内存已满，将暂时不用的部分程序和数若此时内存已满，将暂时不用的部分程序和数据换出，腾出空间。据换出，腾出空间。从用户的角度看，系统具有的内存容量比实际大得多，从用户的角度看，系统具有的内存容量比实际大得多，所以称为所以称为 虚拟存储器虚拟存储器。虚拟存储器的定义虚拟存储器的定义 虚拟存储器虚拟存储器是指具有请求调入功能和置换功能，是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系能从逻辑上对内存容量进行扩充的一种存储器系统。统。离散性离散性 （实现虚拟存储器的基础）（实现虚拟存储器的基础）进程不装入连续的存储空间，内存分配采用离散分配方式。进程不装入连续的存储空间，内存分配采用离散分配方式。多次性多次性一个进程被分割，多次调入内存。一个进程被分割，多次调入内存。对换性对换性进程在运行过程中允许将部分程序和数据换进、换出内存。进程在运行过程中允许将部分程序和数据换进、换出内存。虚拟性虚拟性 （实现虚拟存储器的重要目标）（实现虚拟存储器的重要目标）从逻辑上扩充了内存的容量。从逻辑上扩充了内存的容量。虚拟存储器的特征虚拟存储器的特征 状态位状态位P：记录该页是否在内存。记录该页是否在内存。P=1该页在内存；该页在内存；P=0该页该页不不在内存。在内存。访问字段访问字段A：记录该页多长时间没有被访问。记录该页多长时间没有被访问。修改位修改位M：记录该页在内存期间是否被修改过。记录该页在内存期间是否被修改过。M=1该页调入内存后被修改过该页调入内存后被修改过；M=0该页调入内存后该页调入内存后未未被修改过。被修改过。外存地址：外存地址：该页在外存的地址。该页在外存的地址。页表的扩充页表的扩充 6.2请求页式存储管理请求页式存储管理 在页式存储管理的基础上，进程的页根据需要请在页式存储管理的基础上，进程的页根据需要请求调入内存，称为求调入内存，称为请求页式存储管理请求页式存储管理。缺页中断机构缺页中断机构缺页中断是一种特殊的中断。主要表现在：缺页中断是一种特殊的中断。主要表现在：在指令执行期间产生和处理中断信号。在指令执行期间产生和处理中断信号。一条指令执行期间，可能产生多次缺页中断。一条指令执行期间，可能产生多次缺页中断。缺页中断缺页中断：当要访问的页不在内存，产生一个缺页中断，当要访问的页不在内存，产生一个缺页中断，请求操作系统将所缺的页调入内存。请求操作系统将所缺的页调入内存。地址变换机构地址变换机构在页式存储管理基在页式存储管理基础上增加的功能：础上增加的功能：产生和处理缺页产生和处理缺页中断中断 从内存换出一页从内存换出一页 从外存调入一页从外存调入一页请求页式存储管理驻留集管理请求页式存储管理驻留集管理驻留集管理包括以下内容：驻留集管理包括以下内容：分配给进程的物理块数分配给进程的物理块数 分配策略分配策略固定的？还是可变的？固定的？还是可变的？置换策略置换策略局部置换？还是全局置换？局部置换？还是全局置换？驻留集驻留集：在某段时间间隔内，进程要访问的页面集合。：在某段时间间隔内，进程要访问的页面集合。每个进程分配的物理块越少，则内存中进每个进程分配的物理块越少，则内存中进程数越多。程数越多。为每个进程分配的物理块数目的减少，则为每个进程分配的物理块数目的减少，则缺页率提高，降低进程的执行速度。缺页率提高，降低进程的执行速度。每个进程分配的物理块达一定数量后，再每个进程分配的物理块达一定数量后，再增加分配，缺页率不会有明显改善。增加分配，缺页率不会有明显改善。分配给进程的物理块数分配给进程的物理块数驻留集管理驻留集管理(分配策略和换出策略分配策略和换出策略)固定分配、局部置换固定分配、局部置换 为每个进程分配固定页数的内存空间、且运行过程中不变。为每个进程分配固定页数的内存空间、且运行过程中不变。当进程缺页时，只能从该进程在内存的几个页面中选出一页当进程缺页时，只能从该进程在内存的几个页面中选出一页换出，然后再调入一页，保证进程的页数不变。换出，然后再调入一页，保证进程的页数不变。可变分配、全局置换可变分配、全局置换 系统开始先为每个进程分配一定数目的物理块。整个系统有系统开始先为每个进程分配一定数目的物理块。整个系统有一空闲块队列，当某进程缺页时，系统从空闲块队列中选出一一空闲块队列，当某进程缺页时，系统从空闲块队列中选出一块分配给进程。块分配给进程。空闲块队列空时，从所有进程的页面中权衡选择一页换出。空闲块队列空时，从所有进程的页面中权衡选择一页换出。可变分配、局部置换可变分配、局部置换 进程缺页时，只能从该进程在内存的页面中选出一页换出。进程缺页时，只能从该进程在内存的页面中选出一页换出。若某进程频繁缺页，则再为其分配一些物理块。反之，若某若某进程频繁缺页，则再为其分配一些物理块。反之，若某进程缺页率特别低，则减少分配给它的物理块数进程缺页率特别低，则减少分配给它的物理块数请求页式存储管理的调入策略请求页式存储管理的调入策略 何时调入页面何时调入页面 请调：发生缺页时，调入内存。请调：发生缺页时，调入内存。预调：预计要访问的页，提前调入内存。预调：预计要访问的页，提前调入内存。从何处调入从何处调入 把外存分成两部分：把外存分成两部分：文件区文件区和和对换区对换区 进程的所有页面都放在进程的所有页面都放在对换区对换区。只将修改过的页面放在只将修改过的页面放在对换区对换区，未改的放在，未改的放在文件区文件区。首次从首次从文件区文件区调入，换出时放在调入，换出时放在对换区对换区，以后从以后从对换区对换区调入。调入。请求页式存储管理的页面置换算法请求页式存储管理的页面置换算法 最佳置换算法最佳置换算法OPT 先进先出置换算法先进先出置换算法FIFO 最近最久未使用置换算法最近最久未使用置换算法LRU 时钟置换算法时钟置换算法目标：把目标：把未来不再使用未来不再使用的或的或短时间内不再使用短时间内不再使用的页调出。的页调出。最佳置换算法最佳置换算法OPT进程访问总页面数为进程访问总页面数为20结果：缺页结果：缺页9次，页面换出次，页面换出6次。缺页率次。缺页率45。页面走向页面走向思想思想置换那些不再使用，或最长时间不使用的页。置换那些不再使用，或最长时间不使用的页。先进先出页面置换算法先进先出页面置换算法FIFO进程访问总页面数为进程访问总页面数为20OPT与与FIFO的比较结果：的比较结果：OPT：缺页：缺页9次，次，页面换出页面换出6次。缺页率次。缺页率45 FIFO：缺页：缺页15次，页面换出次，页面换出12次。缺页率次。缺页率75OPT页面走向页面走向FIFO页面走向页面走向思想思想新进入内存的页被先置换出去。新进入内存的页被先置换出去。最近最久未使用最近最久未使用LRU页面置换算法页面置换算法OPT页面走向页面走向LRU页面走向页面走向思想思想用用“过去过去”的行为预测将来，置换的行为预测将来，置换“最近最久未使用最近最久未使用”的页。的页。进程访问总页面数为进程访问总页面数为20OPT与与LRU的比较结果：的比较结果：OPT：缺页：缺页9次，次，页面换出页面换出6次。缺页率次。缺页率45 LRU：缺页：缺页12次，页面换出次，页面换出9次。缺页率次。缺页率60时钟页面置换算法时钟页面置换算法CLOCK LRU性能较好，但实现困难！性能较好，但实现困难！因此可用时钟（因此可用时钟（CLOCK）置换算法。）置换算法。为每页设一访问位，再将内存中的所有页面链接成一为每页设一访问位，再将内存中的所有页面链接成一个循环队列。个循环队列。当某页被访问时，其访问位置当某页被访问时，其访问位置1。置换算法在选择一页淘汰时，只需检查其访问位。置换算法在选择一页淘汰时，只需检查其访问位。如果是如果是0，就选择该页换出；，就选择该页换出；如果是如果是1，则重新将其置为，则重新将其置为0，暂不换出。，暂不换出。CLOCK页面置换算法页面置换算法 除了考虑页面的使用情况外，还要考虑该页是否除了考虑页面的使用情况外，还要考虑该页是否被修改被修改过。过。由由访问位访问位A和和修改位修改位M组合成下面四种情况的组合：组合成下面四种情况的组合：A=0，M=0该页既未被访问过、又未被修改过，是最佳淘汰页。该页既未被访问过、又未被修改过，是最佳淘汰页。A=0，M=1该页最近未被访问、但已被修改，可以被淘汰。该页最近未被访问、但已被修改，可以被淘汰。A=1，M=0最近已被访问，但未被修改，该页有可能再被访问。最近已被访问，但未被修改，该页有可能再被访问。A=1，M=1最近已被访问且被修改，该页可能再被访问。最近已被访问且被修改，该页可能再被访问。CLOCKCLOCK算法执行过程算法执行过程算法执行过程算法执行过程 从当前位置扫描循环队列，寻找从当前位置扫描循环队列，寻找类页面。类页面。若步骤若步骤失败，开始第二轮扫描，寻找失败，开始第二轮扫描，寻找类页面淘汰。并将类页面淘汰。并将所经过的页面的访问位置所经过的页面的访问位置0。若步骤若步骤也失败，重复步骤也失败，重复步骤1，若仍失败，再重复步骤，若仍失败，再重复步骤2。请求页式存储管理系统的性能请求页式存储管理系统的性能 正确选择驻留集窗口大小：正确选择驻留集窗口大小：窗口大小窗口大小选择得过小，频繁产生缺页中断。选择得过小，频繁产生缺页中断。窗口大小窗口大小选择得很大，失去了虚拟存储器的意义。选择得很大，失去了虚拟存储器的意义。驻留集驻留集：即在某段时间间即在某段时间间隔内，进程实际隔内，进程实际要访问的页面的要访问的页面的集合。集合。缺页率与物理块数的关系缺页率与物理块数的关系 为进程分配的物理块数应该取为进程分配的物理块数应该取该曲线的拐点附近或稍大些。该曲线的拐点附近或稍大些。CPU的利用率与多道程序数的关系的利用率与多道程序数的关系 抖动的产生抖动的产生 并不是并不是“多道程序的度越高，多道程序的度越高，系统吞吐量越大。系统吞吐量越大。”当当CPU的利用率达到某一的利用率达到某一峰值后，若继续增加多道程峰值后，若继续增加多道程度，将产生度，将产生抖动抖动。抖动预防方法抖动预防方法 加载控制加载控制 L=S准则准则（产生缺页的平均时间（产生缺页的平均时间L等于等于系统处理缺页的平均时间系统处理缺页的平均时间 S）采用局部置换采用局部置换 挂起若干进程挂起若干进程 抖动：抖动：进程的大部分时间都用于页进程的大部分时间都用于页面的换进面的换进/换出，而几乎不能完成任换出，而几乎不能完成任何有效工作何有效工作 P148/4 6 7 8作业