06第六章 存储管理2

6.4外存资源管理,外存空间划分静态等长，2i,称为一块(block)，块是外存分配的基本单位，也是IO传输的基本单位。外存空间分配空闲块链(慢)空闲块表(UNIX)字位映像图,Swap空间,File空间,输入井,输出井,进程与外存对应关系,界地址每进程占一组外存连续块；每进程占二组外存连续块（双对界）。页式内存一页，外存一块。段式每段占外存若干连续块。段页式内存一页，外存一块。,6.5虚拟存储系统,无虚拟问题不能运行比内存大的程序；进程全部装入内存，浪费空间(进程活动具有局部性)。单控制流的进程需要较少部分在内存；多控制流的进程需要较多部分在内存。虚拟存储进程部分装入内存，部分（或全部）装入外存，运行时访问在外存部分动态调入，内存不够淘汰。,6.5.1虚拟页式存储系统,基本原理进程运行前：全部装入外存，部分装入内存。进程运行时：访问页不在内存，发生缺页中断，中断处理程序：找到访问页在外存的地址；在内存找一空闲页面；如没有，按淘汰算法淘汰一个；如需要，将淘汰页面写回外存，修改页表和总页表；读入所需页面（切换进程）；重新启动中断指令。,6.5.1虚拟页式存储管理(Cont.),虚拟页式存储管理地址映射,指令给出逻辑地址(p,d),由p查快表得到f,查到,f、d合并得物理地址,0pl-1,越界中断,由b、p查找页表得f,该页在内存,缺页中断,保存现场,有空闲页框,选一页面淘汰,该页面修改过,写回外存,读入所需页面,更新页表和快表,恢复现场,F,F,F,T,T,T,(p,f)快表如快表满，淘汰一表项,硬件完成,软件完成,T,f、d合并得物理地址,对页表的改进：,对快表的改进：,.,逻辑页号页框号访问权限修改标志,pfr,w,e(0,1),.,6.5.1.2内存页框分配策略（静态策略）1.平均分配如内存128页，进程25个，每个进程5个页架2.按进程长度比例分配pi共si个页面；S=si；内存共m个页架ai=(si/S)m3.按进程优先级比例分配4.按进程长度和优先级别比例分配静态策略没有反映：(1)程序结构；(2)程序在不同时刻的行为特性。,6.5.1.3外存块的分配策略1.静态分配外存保持进程的全部页面：优点：速度快-淘汰时不必写回(未修改情况)缺点：外存浪费2.动态分配外存仅保持进程不在内存的页面：优点：节省外存缺点：速度慢-淘汰时必须写回,6.5.1.4页面调入时机1.请调(demandpaging)uponpagefault,发生缺页中断时调入。2.预调(prepaging)beforepagefault,将要访问时调入(根据程序顺序行为，不一定准）预调必须辅以请调。,用于：页淘汰、段淘汰、快表淘汰。Objective:lowestpage-faultrate.1.最佳淘汰算法(OPT-optimal)淘汰将来最长时间以后才用到的。效率最高，notfeasible。,6.5.1.5置换算法(replacementalgorithm),2.先进先出(FIFO)淘汰最先调入的。依据:先进入的可能已经使用完毕。实现：队列negativecase:有些代码和数据可能整个程序运行中用到。Belady异常:例子：1，2，3，4，1，2，5，1，2，3，4，5内存3个物理页面：页故障率=9/12内存4个物理页面：页故障率=10/12,FIFO淘汰算法(belady异常),页故障率=10/12,页故障率=9/12,访问序列:,访问序列:,内存页面:,内存页面:,3.使用过最久的先淘汰（LRU）淘汰最近一次访问距当前时间最长的。Replacepagethathasntbeenusedforthelongestperiodoftime.实现：stack当一页面被访问时，如在栈中，取出压到栈顶；否则直接压入栈顶，满时淘汰栈底。例子：referencestring:4,7,0,7,1,0,2,1,7,4（页框数=4）,LRU算法,4.最近不用的先淘汰(notusedrecently)淘汰最近一段时间未用到的。实现：每页增加一个访问标志，访问置1，定时清0，淘汰时取标志为0的。LRU算法的近似：Referencestring:2,3,5,6,4,2,5,6,7,5,6,8,标志清0,选择淘汰LRU：3NUR：2，3，4任意,5.最不经常使用的先淘汰(LFU)淘汰使用次数最少的。依据:活跃访问页面应有较大的访问次数.Suffer:(1)前期使用多，但以后不用，难换出；(2)刚调入的页面，引用少，被换出可能大。实现：记数器，调入清0，访问增1，淘汰选取最小者。6.最经常使用的先淘汰(MFU)淘汰使用次数最多的。依据:使用多的可能已经用完了。Suffer:程序有些成分是在整个程序运行中都使用的。,7.二次机会(secondchance),淘汰装入最久且最近未被访问的页面。实现时：采用拉链数据结构。,8.时钟算法(clockalgorithm),将页面组织成环形，有一个指针指向当前位置。每次需要淘汰页面时，从指针所指的页面开始检查。如果当前页面的访问位为0，即从上次检测到目前，该页没有访问过，则将该页替换。如果当前页面的访问位为1，则将其清0，并顺时针移动指针到下一个位置。重复上述步骤直至找到一个访问位为0的页面。可以看出，时钟算法与二次机会算法的淘汰效果是相同的，差别在于二者所采用的数据结构不同，二次机会使用的是链表，需要额外存储空间，且摘链入链速度很慢。而时钟算法可直接利用页表中的引用位(访问时置1)，外加一个指针，速度快且节省空间。,页6/r=1,页3/r=1,页4/r=0,页8/r=0,页10/r=1,页9/r=0,页0/r=0,页1/r=1,框12,框23,框51,框6,框81,框96,框60,框5,访问第18页,时钟算法,页6/r=0,页3/r=1,页4/r=0,页8/r=0,页10/r=1,页9/r=0,页0/r=0,页1/r=1,框12,框23,框51,框6,框81,框96,框60,框5,访问第18页,时钟算法,页6/r=0,页3/r=0,页4/r=0,页8/r=0,页10/r=1,页9/r=0,页0/r=0,页1/r=1,框12,框23,框51,框6,框81,框96,框60,框5,访问第18页,时钟算法,页6/r=0,页3/r=0,页18/r=1,页8/r=0,页10/r=1,页9/r=0,页0/r=0,页1/r=1,框12,框23,框51,框6,框81,框96,框60,框5,替换第4页,时钟算法,改进的时钟算法,考虑修改标志mr=0,m=0：最佳r=0,m=1：次佳，淘汰前回写r=1,m=0：再次r=1,m=1：最后，淘汰前写回,改进的时钟算法,步骤1：由指针当前位置开始扫描，选择最佳淘汰页面，不改变引用位，将第一个遇到的r=0且m=0的页面作为淘汰页面；步骤2：如步骤1失败，再次从原位置开始，找r=0且m=1的页面，将第一个满足上述要求的页面作为淘汰页面，同时将扫描过页面的r位清0；步骤3：若步骤2失败，指针再次回到原位置，重新执行步骤1。若还失败再次执行步骤2，此时定能找到。,页6/r=1m=1,页3/r=1m=1,页18/r=1m=0,页8/r=1m=0,页10/r=1m=0,页9/r=0m=1,页0/r=0m=1,页1/r=1m=0,框12,框23,框51,框6,框81,框96,框60,框5,访问第15页,改进的时钟算法,页6/r=1m=1,页3/r=1m=1,页18/r=1m=0,页8/r=1m=0,页10/r=1m=0,页9/r=0m=1,页0/r=0m=1,页1/r=1m=0,框12,框23,框51,框6,框81,框96,框60,框5,访问第15页,改进的时钟算法,页6/r=1m=1,页3/r=1m=1,页18/r=1m=0,页8/r=0m=0,页10/r=1m=0,页9/r=0m=1,页0/r=0m=1,页1/r=1m=0,框12,框23,框51,框6,框81,框96,框60,框5,访问第15页,改进的时钟算法,页6/r=1m=1,页3/r=1m=1,页18/r=1m=0,页8/r=0m=0,页10/r=0m=0,页9/r=0m=1,页0/r=0m=1,页1/r=1m=0,框12,框23,框51,框6,框81,框96,框60,框5,访问第15页,时钟算法,页6/r=1m=1,页3/r=1m=1,页18/r=1m=0,页8/r=0m=0,页10/r=0m=0,页15/r=1m=0,页0/r=0m=1,页1/r=1m=0,框12,框23,框51,框6,框81,框96,框60,框5,时钟算法,2010年考研试题,某虚拟页式系统，进程空间和内存空间都是64k，页长1K，某进程6个页，内存分配4个页框，采用局部置换，280时刻页表和Clock数据结构如下：,0页,2页,3页,5页,框5,框12,框8,框3,(顺时针),2010年考研试题,(1)280时刻访问13B7H，逻辑页号是多少？(2)采用FIFO置换算法，物理页框号是多少？物理地址是多少？(3)采用CLOCK置换算法，页框号是多少？物理地址是多少？,2010年考研试题,（1）逻辑地址13B7H化为二进制数为0001001110110111，其中后10位为页内地址，前6位为逻辑页号，即逻辑页号为4。（2）4号页不在内存，发生缺页中断，按FIFO置换算法，应置换第5页，所得页框号3，形成物理地址0000111110110111，划成16进制为0FB7H。（3）采用CLOCK置换算法，淘汰第0页，得页框5，形成物理地址为0001011110110111，划成16进制为17B7H。,6.5.1.6颠簸(thrashing)页面在内存与外存之间频繁换入换出。原因：(1)分给进程物理页架过少；(2)淘汰算法不合理；(3)程序结构不好。处理：(1)增加分给进程物理页架数；(2)改进淘汰算法；(3)改善程序结构。,思考题：在某些虚拟页式存储管理系统中，内存中总保持一个空闲的物理页架，这样做有什么好处？,关于程序结构对页故障的影响,inta10241024;清零操作：for(i=0;i1024;i+)for(j=0;j1024;j+)aij=0;for(i=0;i0acceptfinish_readdorcount:=rcount-1;endfinish_r