第6章 虚拟存储管理课件

第6章虚拟存储管理本章要点●虚拟存储器的引入

●请求页式存储管理

●请求段式存储管理

●6.1虚拟存储器的引入前面介绍的存储管理方案要求作业全部装入内存才可运行。但这会出现两种情况：●有的作业因太大，内存装不下而无法运行。●系统中作业数太多，因系统容量有限只能让少数作业先运行。问题：能否不把作业的全部信息同时装入主存储器，而让作业开始执行？如果这个问题能够解决的话，当主存空间小于作业需求量时，作业也能执行，这就使得主存空间能被充分地利用，进而用户编制程序时可以不必考虑主存储器的实际容量，允许用户的逻辑地址空间大于主存储器的绝对地址空间，对用户来说，好像计算机系统具有一个容量很大的主存储器，称为虚拟存储器。虚拟存储器的容量由计算机的地址结构和辅助存储器（如磁盘）的容量决定，与实际主存储器的容量无关。所以，虚拟存储器实际上是为扩大主存容量而采用的一种管理技巧。工作原理：以大容量的辅助存储器（如磁盘）做后盾。把作业信息保留在磁盘上，当要求装入时，只将其中一部分先装入主存储器，另一部分暂时存放在磁盘上，作业执行过程中要用到那些不在主存储器中的信息时，再把它们装到主存储器中。问题：在作业信息不全部装入主存的情况下能否保证作业的正确执行?局部性原理（理论基础）1968年P.Denning提出●程序执行时，大多数情况下是顺序执行的。●过程调用会使程序的执行轨迹从一部分内存区域转至另一部分区域，但过程调用的深度不会超过5。●程序中有许多循环语句，这些语句会重复多次执行。●程序中对数据结构的操作，往往局限在很小的范围内。局部性原理局限性的表现●时间局限性程序中的的某条指令一旦执行，不久后会再次执行。●空间局限性程序一旦访问某存储单元，不久后会访问其附近的存储单元。虚拟存储器的定义所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。●离散性作业不装入连续的存储空间，内存分配采用离散分配方式。●多次性一个作业被分割，被多次调入内存。●对换性作业在运行过程中换进、换出内存。●虚拟性从逻辑上扩充了内存的容量。虚拟存储器的特征实现虚拟存储管理必须解决三个关键问题：怎样知道当前哪些信息已在主存储器中，哪些信息尚未装入主存储器中？如果作业要访问的信息不在主存储器中，怎样去找到这些信息且把它们装入到主存储器中？在把欲访问的信息装入主存储器时，发现主存储器中已无空闲区域，又该怎么办？●6.2请求页式存储管理对采用页式管理的存储器来说，能被方便地改造成虚拟存储器。改造的方法很简单，只需将作业的全部信息作为副本存放在磁盘上，作业调度选中一个作业时，至少把作业的第一页信息装入主存储器，在作业执行过程中欲访问不在主存储器中的页时，再把它们装入。为此需要对页表进行改造。首先应在页表中指出哪些页已在主存储器中，哪些页还没装入主存储器，并且指出每一页副本在磁盘上的位置。●状态位P：记录该页是否在内存。P=1该页在内存； P=0该页不在内存。●访问字段A：记录该页在一段时间内被访问的次数。●修改位M：记录该页在内存期间是否被修改过。 M=1该页调入内存后被修改过；M=0该页调入内存后未被修改过。●外存地址：该页在外存的地址。页表的扩充●6.2请求页式存储管理缺页中断机构主要表现在：●在指令执行期间产生和处理中断信号。而普通中断是在每条指令结束后去检查是否有中断到达。●一条指令执行期间，可能产生多次缺页中断。一条双操作数的指令在执行时，指令本身和操作数可能都不在内存。缺页中断是一种特殊的中断movax,[2500]…………incax地址变换机构页面调度如果欲调入一页时，主存储器中已没有空闲块，怎么办？则必须先调出已在主存储器中的某一页，再将当前所需的页调入，同时对页表作相应的修改。采用某种算法选择一页暂时调出，把它存放到磁盘上去，让出主存空间，用来存放当前要使用的页面，这一过程称为页面调度。若被页面调度选中调出的页又要被访问，则可用类似的方法调出另一些页面而将其调入。页面调度算法的选择是很重要的。如果选用了一个不合适的调度算法就会出现这样的现象：刚被调出的页又立即要用，因而又要把它调入；而调入不久又被调出；调出不久又再次被调入。如此反复，使调度非常频繁，以至于使大部分时间都花费在来回调度上，这种现象称为抖动，又称颠簸。因而应该选择一种好的调度算法，以减少和避免抖动现象。

请求页式存储管理的页面置换算法

●最佳置换算法OPT●先进先出置换算法FIFO●最近最久未使用置换算法LRU●CLOCK置换算法Optimal算法系统为某个进程分配了3个物理块，假设进程按照以下页号的顺序来访问页面;7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,170120120324320320170170120304230321201701共发生几次缺页中断？9次。页面换出6次，这是最理想的情况，置换的次数最少思想——置换那些不再使用，或最长时间不使用的页。仅仅是一个理论算法而已。因为在实际应用中，我们无法判断哪一页是以后不再访问的页或距离现在最长时间以后再访问的页770先进先出算法系统为某个进程分配了3个物理块，假设进程按照以下页号的顺序来访问页面;7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,170120123123043042042302301301271270270170120304230321201701思想——先进入内存的页被先置换出去。OPT与FIFO的比较结果： OPT页面换出6次，缺页9次。 FIFO页面换出12次，缺页15次。7701072103024032403240321232137107012030423031201701LRU算法3022301022021032021置换置换置换置换LRU页面换出9次，缺页12次。707思想——用“过去”的行为预测将来，置换哪些“最近最久未使用”的页。CLOCK页面置换算法●

LRU性能较好，但实现困难！因此可用CLOCK算法。

●为每页设一访问位，再将内存中的所有页面链接成一循环队列。●当某页被访问时，其访问位置1。●置换算法在选择一页淘汰时，只需检查其访问位。 如果是0，就选择该页换出； 如果是1，则重新将其置为0，暂不换出。CLOCK页面置换算法●除了考虑页面的使用情况外，还要考虑该页是否被修改过。●由访问位A和修改位M组合成下面四种情况的组合：●

<1>A=0，M=0该页既未被访问过、又未被修改过，是最佳淘汰页。●

<2>A=0，M=1该页最近未被访问、但已被修改，可以被淘汰。●

<3>A=1，M=0最近已被访问，但未被修改，该页有可能再被访问。●

<4>A=1，M=1最近已被访问且被修改，该页可能再被访问。CLOCK算法执行过程1>从当前位置扫描循环队列，寻找〈1〉类页面。2>若1>失败，开始第二轮扫描，寻找<2>类页面，并将所经过的页面的访问位置0。3>若2>也失败，返回到开始位置，将所有的访问位复0，goto1>。补充：UNIX的页面调度UNIX采用的措施：（1）正在与外设交换信息的页面或者正在被装入的页面是不能被替换的。（2）页面调度采用二次机会页面替换算法。实现要点如下：①把除了内核部分的所有物理页登录在一张总页面表中。②设置一个时钟指针，扫描总页面表。当时钟指针到达一个表项时，如果该物理页是空闲的或正在与外设交换信息，则继续扫描下一表项，否则找出占用该物理页的进程页表。③按物理页号从进程页表中找出对应的表项。若该页的有效位已经被置成了0，则对该页所占的物理页置上“空闲”标志。若该页有效位为1，则把有效位改置成0。④产生缺页中断后，可找一个有空闲标志的物理页，将该物理页中的信息调出到磁盘上，然后再来装入新页。⑤对有效位被置成0的页，页中的信息仍保留在所占的物理页中，只要这个物理页没有空闲标志，那么就不会被用来装入新页。这样，一旦进程又要访问该页时，只要把有效位重新置成1，使该页信息成为二次有效，进程就可立即访问该页信息。这样就减少了大量的输入/输出传送。（3）为了装入一个新页而要调出一页时，要检查被调出页的修改位标志。若该页被修改过，则调出时必须把该页的内容写回磁盘上，否则就不必写回磁盘，以减少I/O（4）系统中有一个2号进程，UNIX把它称为页面守护进程，它的作用是保证有足够的空闲物理页可供使用。一般它处于睡眠状态，每当有空闲标志的物理页总数量低于一个限值时被唤醒。其职责如下：①控制二次机会算法中的时钟指针，当时钟指针所指的某物理页可成为空闲页时，把空闲物理页数加1。②让时钟继续扫描，使空闲物理页不断增加。③当空闲物理页数达到限值后，让时钟指针停止扫描。时钟指针停止扫描时，页面守护进程就进入睡眠状态，直到被唤醒后再工作。缺页中断率

假定作业p共计n页，系统分配给它的物理块只有m块（１≤m≤n）。如果作业p在运行中成功的访问次数为s（访问的地址都在内存中），不成功的访问次数为F（访问的地址在外存），则总的访问次数Ａ为：A=S+F

则缺页中断率为：f=F/A请求页式存储管理系统的性能实现虚拟存储器时应尽可能降低缺页中断率。影响缺页中断率f的因素有：

(1)分配给作业的主存块数----块数n↑f↓(2)页面大小----页面大小↑f↓(3)程序的编制方法----局部化程度↑f↓(4)页面替换算法驻留集●正确选择驻留集窗口大小： ●窗口大小Δ选择得过小，频繁产生缺页中断。 ●窗口大小Δ选择得很大，失去了虚拟存储器的意义。●驻留集：即在某段时间间隔内，进程实际要访问的页面的集合。请求页式存储管理驻留集管理驻留集管理包括以下内容：●保证进程正常运行所需的最少物理块数是多少？●为每个进程分配物理块时，其数目是固定的、还是可变的？●如何为进程置换物理块，是局部置换？还是全局置换？缺页率与物理块数（窗口大小）的关系●当进程获得的物理块数达到临界值，继续增加块数，缺页率不能显著降低●进程获得的块数达到临界值，缺页率稳定在上下限之间临界值(窗口大小)块数过少，频繁缺页，降低了系统吞吐率块数太多，必然有些页面属于浪费。内存不能充分利用，失去了虚拟存储器的意义拐点●物理块越多越好！——虚拟？●随着为进程分配的物理块数目的减少，将使进程执行中的缺页率提高，从而降低进程的执行速度。●能保证进程正常运行所需的最小物理块数是多少？●这与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。最少物理块数进程正常运行需要多少物理块?能保证进程正常运行所需的最小物理块数是多少？这与计算机硬件结构有关，取决于指令格式、功能和寻址方式。例如：①对于某些简单机器，若是单地址指令且采用直接寻址方式，最小物理块数应为2。即，指令所在页和数据页。 incbyteptr[30H]

②若该机器允许间接寻址，则至少要3个物理块 MOVA,[B]③现代计算机，指令长度可能是两个或两个以上字节，至少要为进程分配6个物理块。因为指令本身可能跨越2个页，源地址和目标地址所涉及的区域也都可能跨两个页面

最小物理块数 …… jelabel ……label: incax ……if(序列号!=x){…}else{…}0000:…… ……2A00: 745A2A02: ………… ……2A5A: 1C…… ……5A…………74驻留集管理

●固定分配、局部置换●为每个进程分配固定页数的内存空间、且运行过程中不变。●当进程缺页时，只能从该进程在内存的几个页面中选出一页换出，然后再调入一页，保证进程的页数不变。●可变分配、全局置换●系统开始先为每个进程分配一定数目的物理块。整个系统有一空闲物理块链，当某进程缺页时，系统从空闲链中选出一块分配给进程。●空闲链为空时，OS从所有进程的页面中权衡选择一页换出。●可变分配、局部置换●分配同上，但进程缺页时，只能从该进程在内存的页面中选出一页换出。请求页式存储管理的调入策略

●何时调入页面●预调：预计进程要访问的页，提前调入内存。一次调入多页比调入一页更高效但预调页的成功率仅约50％。●请调：进程发生缺页中断时将所缺页面调入内存。实现简单每次仅调入一页，故须花费较大的系统开销，增加了磁盘I／O的启动频率●从何处调入 请求页式存储管理系统中，把外存分为两部分：文件区和对换区有以下三种实现方式：●进程的所有页面都放在对换区。●只将修改过的页面放在对换区，未改的放在文件区。●UNIX系统方式，首次从文件区调入，换出时放在对换区，以后从对换区调入。●结论：

①在多道程序环境下，并非“多道程序度越高，系统吞吐量越大。”

②当CPU利用率达到某峰值后，若继续增加道数，将产生抖动，使CPU利用率降低。●抖动预防方法①加载控制(只有驻留集足够大的进程才能执行。这限制了进程数目)②

L=S准则（调整道数，使产生缺页的平均时间L等于系统处理缺页的平均时间

S）③采用局部置换(某进程抖动，不影响其它进程)④当道数偏高，尽快挂起若干进程图6-6CPU利用率与多道程序道数的关系2抖动和加载控制抖动(颠簸)的含义：刚刚被调出的页面又立即要用，因而又要把它装入，而装入不久又被选中调出，调出不久又要装入使用，如此反复，使调度非常频繁。抖动的原因：置换算法不好；缺页严重缺页的原因：内存不足；道数多道数多

块数少

缺页严重

抖动

进程的时间浪费在换进换出，CPU利用率低【练习】在一个页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是：115,228,120,88,446,102,321,432,260,167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题：（1）按FIFO算法将产生_________次缺页中断，依次淘汰的页号为___________________.缺页中断率为__________.

0000044444411111133332222222210、1、2它依次要访问的字地址序列是：115,228,120,88,446,102,321,432,260,167（2）按LRU调度算法将产生___________次缺页中断，依次淘汰的页号为___________________.缺页中断率为_________.0121041342101210413420021041342、0、1、3●1请段式系统中段表的扩充

6.3请求段式存储管理除段号、段长和段始址这些段式系统已有的基本表项之外，增加了以下表项：●存取方式：用于标识本段的存取属性是只执行、只读，还是允许读/写●状态位：指示该段是否已进驻内存●访问字段：用于记录本段有多长时间没有被访问。置换算法在选择换出段时参考●修改位：表示该段调入内存后是否被修改过●增补位：这是请求段式存储管理系统中特有的字段，用于表示本段在运行过程中是否进行过动态增长●外存地址：用于指出该段在外存的地址，供调入该段时使用2请段式系统中的缺段中断

3请段式系统中的地址变换机构

4请段式系统中的内存管理

调入调出内存的单位是段。如果所需的段尚未调入内存，则产生缺段中断信号。缺段中断处理程序得到控制权侯，负责将所缺段调入内存。在段式系统的基础上形成。在进行地址变换时，如果发现所要访问的段不在内存，必须将所缺的段调入内存，并修改段表中的状态位。段的调入策略和置换算法与请求页式系统类似。物理内存的分配可以采取与可变分区管理相似的方案。不同的是分配的单位不是一个程序或进程，而是一个程序段或数据段。动态链接L