《第四章ch44.5虚拟存储管理》由会员分享，可在线阅读，更多相关《第四章ch44.5虚拟存储管理（82页珍藏版）》请在金锄头文库上搜索。
1、4.5虚拟存储管理,4.5.1 虚拟存储管理的概念 4.5.2 请求分页虚拟存储管理 4.5.3 请求分段虚拟存储管理 4.5.4 请求段页式虚拟存储管理,4.5.1 虚拟存储管理的概念,为什么要引入虚拟存储器? 实现虚拟存储器的基本思路。 虚拟存储器的定义： 在具有层次结构存储器的计算机系统中，采用自动实现部分装入和部分对换功能，为用户提供一个比物理主存容量大得多的，可寻址的一种“主存储器”。,虚拟存储器的概念图,程序局部性原理(1),指程序在执行过程中的一个较短时间内，所执行的指令地址或操作数地址分别局限于一定的存储区域中。又可细分时间局部性和空间局部性。,程序局部性原理 (2),第一，程
2、序中只有少量分支和过程调用，大都是顺序执行的指令； 第二，程序含有若干循环结构，由少量代码组成，而被多次执行； 第三，过程调用的深度限制在小范围内，因而，指令引用通常被局限在少量过程中； 第四，涉及数组、记录之类的数据结构，对它们的连续引用是对位置相邻的数据项的操作； 第五，程序中有些部分彼此互斥，不是每次运行时都用到。,实现虚拟存储器须解决的问题,主存辅存统一管理问题、 逻辑地址到物理地址的转换问题、 部分装入和部分对换问题。,虚拟存储管理实现技术,请求分页虚拟存储管理 请求分段虚拟存储管理 请求段页式虚拟存储管理,4.5.2分页式虚拟存储系统,1 分页式虚拟存储系统的硬件支撑(1) 主存管
3、理单元MMU完成逻辑地址到物理地址的转换功能，它接受虚拟地址作为输入，物理地址作为输出，直接送到总线上，对主存单元进行寻址。,分页式虚拟存储系统的硬件支撑(2),MMU主要功能,(1)管理硬件页表基址寄存器。 (2)分解逻辑地址。 (3)管理快表TLB。 (4)访问页表。 (5)发出缺页中断或越界中断，并将控制权交给内核存储管理处理。 (6)设置和检查页表中各个特征位。,缺页中断处理的过程,步1 挂起请求缺页的进程； 步2 根据页号查外页表，找到该页存放的磁盘物理地址； 步3 查看主存是否有空闲页框，如有则找出一个，修改主存管理表和相应页表项内容，转步6；， 步4 如主存中无空闲页框，按替换算
4、法选择淘汰页面，检查它曾被写过或修改过吗？若未则转步6；若是则转步5； 步5 该淘汰页面被写过或修改过，则把它的内容写回磁盘原先位置； 步6 进行调页，把页面装入主存所分配的页框中，同时修改进程页表项； 步7 返回进程断点，重新启动被中断的指令。,2请求分页虚拟存储系统 的基本原理,分页式虚存不把作业信息(程序和数据)全部装入主存，仅装入立即使用的页面，在执行过程中访问到不在主存的页面时，产生缺页中断，再从磁盘动态地装入 。 怎样才能发现页面不在主存中呢?怎样处理这种情况呢? 采用的办法是：扩充页表的内容,增加驻留标志位等信息。,页式虚拟存储管理页表扩展,驻留标志位(又称中断位) 修改位（Mo
5、dified） 引用位（Renferenced）,页号 驻留标志 页框号 其它标志,外页表,页面与磁盘物理地址的对应表，由操作系统管理，进程启动运行前系统为其建立外页表，并把进程程序页面装入辅存。 该表按进程页号的顺序排列，为节省主存，外页表可存放在磁盘中，当发生缺页中断需要查用时才被调入。,请求分页虚存地址转换过程(1),请求分页虚存地址转换过程(2),请求页式虚拟存储系统优缺点,优点：作业的程序和数据可按页分散存放在主存中，减少移动开销，有效解决了碎片问题;既有利于改进主存利用率，又有利于多道程序运行。 缺点：要有硬件支持，要进行缺页中断处理，机器成本增加，系统开销加大。,3 页面装入策略
6、和页面清除策略,页面装入主存,有两种策略： 请页式调度 预调式调度 何时把一个修改过的页面写回辅存储器，有两种策略： 请页式清除 预清除。,4页面分配策略,系统为进程分配主存,需考虑因素: 分给进程的空间越小,同一时间处于主存的进程就越多，至少有一个进程处于就绪态的可能性就越大 如果进程只有小部分在主存里,即使局部性很好,缺页中断率还会相当高 因程序的局部性原理，分给进程的主存超过一定限度后，再增加主存空间,不会明显降低进程的缺页中断率。,页面分配策略：固定分配,进程保持页框数固定不变,称固定分配; 进程创建时,根据进程类型和程序员的要求决定页框数,只要有一个缺页中断产生,进程就会有一页被替换
7、。,页面分配策略：可变分配,进程分得的页框数可变, 称可变分配; 进程执行的某阶段缺页率较高,说明目前局部性较差，系统可多分些页框以降低缺页率，反之说明进程目前的局部性较好,可减少分给进程的页框数,页面替换策略：局部替换和全局替换,如果页面替换算法的作用范围是整个系统，称全局页面替换算法,它可以在运行进程间动态地分配页框。 如果页面替换算法的作用范围局限于本进程，称为局部页面替换算法,它实际上需要为每个进程分配固定的页框。,固定分配和局部替换策略配合使用(1),进程分得的页框数不变，发生缺页中断，只能从进程的页面中选页替换，保证进程的页框总数不变。 策略难点：应给每个进程分配多少页框?给少了,
8、缺页中断率高;给多了,使主存中能同时执行的进程数减少，进而造成处理器和其它设备空闲。,固定分配和局部替换策略配合使用(2),采用固定分配算法，系统把页 框分配给进程，采用： 平均分配， 按比例分配, 优先权分配。,可变分配和全局替换策略配合使用,先每个进程分配一定数目页框,os保留若干空闲页框,进程发生缺页中断时，从系统空闲页框中选一个给进程,这样产生缺页中断进程的主存空间会逐渐增大,有助于减少系统的缺页中断次数。 系统拥有的空闲页框耗尽时 ，会从主存中选择一页淘汰，该页可以是主存中任一进程的页面，这样又会使那个进程的页框数减少，缺页中断率上升。 SVR4,可变分配和局部替换配合使用,其实现要
9、点如下: (1)新进程装入主存时，根据应用类型、程序要求，分配给一定数目页框,可用请页式或预调式完成这个分配。 (2)产生缺页中断时,从该进程驻留集中选一个页面替换。 (3)不时重新评价进程的分配，增加或减少分配给进程的页框以改善系统性能。 (4)Windows NT,5 缺页中断率,页面替换 页面淘汰算法 “抖动”(Thrashing)现象,影响缺页中断率的因素(1),假定作业p共计n页，系统分配给它的主存块只有m块（mn）。如果作业p在运行中成功的访问次数为s， 不成功的访问次数为F，则总的访问次数为： A = S + F 又定义： f = F / A,影响缺页中断率的因素(2),称f为缺
10、页中断率。影响缺页中断率f的因素有： (1)主存页框数。 (2)页面大小。 (3)页面替换算法。 (4)程序特性。,程序局部性例子,程序将数组置为“0”，假定仅分得一个主存块，页面尺寸为128个字，数组元素按行存放，开始时第一页在主存。 int A128128; int A128128; for(int j=0;j128;j+) for(int i=0;i128;i+) for(int i=0;i128;i+) for(int j=0;j128;j+) Aij=0; Aij=0; 128128-1 128-1,6 全局页面替换策略 可以选择任何一个页面加以替换,1) 最佳页面替换算法OPT 2
11、) 先进先出页面替换算法FIFO 3) 最近最少用页面替换算法LRU 4) 第二次机会页面替换算法SCR 5) 时钟页面替换算法Clock,1)最佳替换算法,调入一页而必须淘汰一个旧页时，所淘汰的页应该是以后不再访问的页或距现在最长时间后再访问的页。 Belady算法（Optimal） ，可用来作为衡量各种具体算法的标准。,2)先进先出页面替换算法,基于程序总是按线性顺序来访问物理空间这一假设。 算法总是淘汰最先调入主存的那一页，或者说在主存中驻留时间最长的那一页（常驻的除外）。,3)最近最少用页面替换算法,算法淘汰的页面是在最近一段时间里较久未被访问的那页。 根据程序局部性原理，那些刚被使用
12、过的页面，可能马上还要被使用，而在较长时间里未被使用的页面，可能不会马上使用到。,LRU算法实现：页面淘汰队列(1),队列中存放当前在主存中的页号，每当访问一页时就调整一次，使队列尾总指向最近访问的页，队列头就是最近最少用的页。 发生缺页中断时总淘汰队列头所指示的页；执行一次页面访问后，需要从队列中把该页调整到队列尾。,LRU算法实现：页面淘汰队列(2),例子：给某作业分配了三块主存，该作业依次访问的页号为：4，3，0，4，1，1，2，3，2。当访问这些页时，页面淘汰序列变化情况如下,LRU算法实现：页面淘汰队列(3),访问页号 页面淘汰序列 被淘汰页面 4 4 3 4 3 0 4 3 0 4
13、 3 0 4 1 0 4 1 3 1 0 4 1 2 4 1 2 0 3 1 2 3 4 2 1 3 2,LRU算法实现：标志位法,每页设置一个引用标志位R，访问某页时，由硬件将页标志位R置1，隔一定时间t将所有页的标志R均清0。 发生缺页中断时，从标志位R为0的页中挑选一页淘汰。挑选到要淘汰的页后，也将所有页的标志位R清0。 NRU,LRU算法实现：多位计数器法,每个页面设置一个多位计数器，又叫最不常用页面替换算法LFU。每当访问一页时，就使它对应的计数器加。 当发生缺页中断时，可选择计数值最小的对应页面淘汰，并将所有计数器全部清。,LRU算法实现：多位计时器法,为每个页面设置一个多位计时器
14、，每当页面被访问时，系统的绝对时间记入计时器。 比较各页面的计时器的值，选最小值的未使用的页面淘汰，因为，它是最“老”的未使用的页面。,4)第二次机会页面替换算法,改进FIFO算法,把FIFO与页表中的”引用位”结合起来使用： 检查FIFO中的队首页面(最早进入主存的页面),如果它的”引用位”是0,这个页面既老又没有用，选择该页面淘汰; 如果”引用位”是1,说明它进入主存较早，但最近仍在使用。把它的”引用位”清0,并把这个页面移到队尾，把它看作是一个新调入的页。 算法含义：最先进入主存的页面，如果最近还在被使用的话,仍然有机会作为像一个新调入页面一样留在主存中。,5）时钟页面替换算法(1),算
15、法实现要点(1)： 一个页面首次装入主存，其“引用位”置0 。 主存中的任何页面被访问时, ”引用位”置1。 淘汰页面时,从指针当前指向的页面开始扫描循环队列，把迁到的”引用位”是1的页面的”引用位”清0,跳过这个页面; 把所迁到的”引用位”是0的页面淘汰掉,指针推进一步。,时钟页面替换算法(2),算法实现要点(2)： 扫描循环队列时，如果迁到的所有页面的”引用位”为1，指针就会绕整个循环队列一圈，把碰到的所有页面的”引用位”清0;指针停在起始位置，并淘汰掉这一页,然后，指针推进一步。,时钟页面替换算法的一个例子,时钟页面替换改进算法(1),把”引用位”和”修改位”结合起来使用，共组合成四种情
16、况： (1)最近没有被引用,没有被修改(r=0,m=0) (2)最近被引用,没有被修改(r=1,m=0) (3)最近没有被引用,但被修改(r=0,m=1) (4)最近被引用过,也被修改过(r=1,m=1),时钟页面替换改进算法(2),步1：选择最佳淘汰页面，从指针当前位置开始,扫描循环队列。扫描过程中不改变”引用位”，把迂到的第一个r=0,m=0的页面作为淘汰页面。 步2：如果步1失败，再次从原位置开始，查找r=0且m=1的页面，把把迂到的第一个这样的页面作为淘汰页面，而在扫描过程中把指针所扫过的页面的”引用位”r置0。,时钟页面替换改进算法(3),步3：如果步2失败，指针再次回到了起始位置，由于此时所有页面的”引用位”r均己为0，再
