操作系统习题Chapter_06-2

虚拟存储系统现代信息技术部张玉教学目标知识目标：（1）了解虚拟存储的含义；（2）理解虚拟页式存储系统的基本原理；（3）掌握虚拟页式存储系统的实现的具体步骤；（4）掌握置换算法和算法的程序实现；能力目标：（1）理解虚拟存储的基本原理和具体实现，加强学生对计算机存储系统的深入了解，设置虚拟内存；（2）通过对虚拟存储过程的分析和模拟，培养学生分析问题的能力；（3）通过置换算法程序的编写，培养学生的动手编程能力；什么是虚拟存储系统？冯.诺依曼原理——存储程序原则现有一个容量为200MB的作业需要运行，如果计算机只有128MB物理内存的话，如何来进行实现局部性原理1.常规存储器管理方式的特征（1）一次性。作业在运行前需一次性的全部装入内存。（2）驻留性。作业装入内存后，便一直驻留在内存中，直到作业运行结束。2.局部性原理1968年P.Denning指出：程序在执行时将呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分；相应地，它所访问的存储空间也局限于某个区域。虚拟存储系统概念:虚拟存储是一种借助于外存空间，从而允许一个进程在其运行过程中部分地装入内存的技术。分类虚拟页式存储系统虚拟段式存储系统虚拟段页式存储系统基本原理在虚拟页式存储管理的地址重定位时，可能会出现所需页面不在主存的情况，此时，系统必须解决以下问题：（1）当前页面在内存中，还是在外存，如何表示？（2）当程序要访问的某页不在内存时，如何发现这种情况？发现后应如何处理？（3）当需要把外存上的某个页面调入内存时，此时内存中没有空闲块应怎么办？为了帮助操作系统对要置换出内存的页面进行选择，对页表扩充：逻辑页号…p.........…......页架号内外标识外存块号访问权限修改标志f(0,1)p’{r,w,e}(0,1)......…......用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用用于指示当前页面是否已调入内存。若为1说明该页在内存中，为0说明在外存上表示该页在调入内存后是否被修改过具体步骤程序运行过程中，若所访问的页面不在内存中，发生“缺页中断”，由操作系统进行页面的调度：1.找到被访问页面在外存的地址2.在内存中找一个空闲页架a)如果没有，按照淘汰算法选择一个内存页架；b)将此内存页面写回外存，修改页表3.读入所需的页面，修改页表4.重新启动进程，执行被中断的指令虚拟内存不足的提示：置换算法1．最佳置换算法（OPT算法）2．先进先出置换算法（FIFO算法）3．最近最久未使用页面置换算法（LRU算法）1.最佳置换算法（OPT算法）算法思想：从内存中移出以后不再使用的页面；如无这样的页面，则选择以后最长时间内不需要访问的页面。2．先进先出算法（FIFO算法）基本思想：总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。实现过程页面走向：1，4，2，5，3，3，2，4，2，5；可用内存块数：3，用OPT算法求缺页次数和缺页率。1425332425114××142×542×342342×342342×342425缺页次数：6缺页率：6/10=3/52.先进先出置换算法（FIFO算法）算法思想：总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。页面走向：1，4，2，5，3，3，2，4，2，5；可用内存块数：3。用FIFO算法求缺页次数和缺页率。1425332425××××××××111444252532532534234254缺页次数：8缺页率：8/10=4/5532练习页面走向1,2,3,4,1,2,5,1,2,3,4,5可用内存块数：3；用FIFO算法求缺页次数页面走向1,2,3,4,1,2,5,1,2,3,4,5可用内存块数：4；用FIFO算法求缺页次数FIFO123412512345页0123412555344页112341222533页21234111255缺页xxxxxxx√√xX√FIFO123412512345页0123444512345页112333451234页21222345123页3111234512缺页xxxx√√xxxxxxBelady异常缺页次数：9缺页次数：10实验3．最近最少使用的先淘汰（LRU算法）基本思想：如果某一页被访问了，那么它很可能马上又被访问；反之，如果某一页很长时间没有被访问，那么最近也不太可能会被访问。其实质是，当需要置换一页时，选择在最近一段时间最久未使用的页面予以淘汰。1425332425页面走向：1，4，2，5，3，3，2，4，2，5；可用内存块数：3。用LRU算法求缺页次数和缺页率。2222221115444××××53×43×4345×缺页次数：7缺页率：7/10532532常用置换算法小结具体算法算法思想优点缺点OPT选择以后最长时间内不需要访问的页面淘汰(向→看)命中率较高，可作为衡量其他置换算法的标准不现实，只是一种理想算法FIFO先进入内存的页面先被淘汰实现简单，利用了主存的历史信息命中率不高，可能出现“Belady”异常LRU选择在最近一段时间最久未使用的页面淘汰(向←看)能正确反映程序的局部性原理，命中率较高实现较复杂4．最近未使用置换算法（NUR算法）——LRU近似算法淘汰最近一段时间未用到的。在实现时,为每一个页面增加两个硬件位,它们是:●引用位＝0,此页未被访问过;＝1,此页曾被访问过.●修改位＝0,此页未被修改过;＝1,此页曾被修改过.一个页面由外存调入内存时,其引用位和修改位均为0.当对某页面执行写操作时,其修改位和引用位由硬件置为1;当对某页面执行读操作时,其引用位由硬件置为1.每隔固定时间将所有引用位都清0.当要淘汰某一页面时,按照下面次序选择:(1)引用位＝0,修改位＝0:直接淘汰;(2)引用位＝0,修改位＝1:淘汰之前写回外存;(3)引用位＝1,修改位＝0:直接淘汰;(4)引用位＝1,修改位＝1:淘汰之前写回外存.图1NRU算法（LRU近似算法）淘汰使用次数最少的。依据:activelyusedpageshouldhavealargerreferencecount.Suffer:(1)前期使用多，但以后不用，难换出；(2)刚调入的页面，引用少，被换出可能大。实现：记数器，调入清0，访问增1，淘汰选取最小者。5.最不经常使用的先淘汰(LFU)6.最经常使用的先淘汰(MFU)淘汰使用次数最多的。依据:使用多的可能已经用完了。Suffer:程序有些成分是在整个程序运行中都使用的。6.5.1.6颠簸（抖动）在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象为颠簸。定义：颠簸又称抖动，是指页面在内存与外存之间频繁的调度，以至于系统用于调度页面所需要的时间比进程实际运行所占用的时间还要多。假设进程访问内存成功的次数为S，缺页的次数为F，则总访问次数A为A=S+F;缺页率f=F/A原因：分配给进程的物理页面数太少页面淘汰算法不合理程序结构防止抖动的原因(1)增加分给进程物理页架数，使得一个进程在一段时间内所需访问的那些页面在内存中有足够的物理块存放，都能调入内存，减小缺页率。(2)改进淘汰算法，首先考虑LRU算法，如开销过大或硬件支持不够，可选择NUR算法。总结程序运行的局部性原理——虚拟存储系统——由外存——页面不在内存——发生缺页中断——请求调入页面——内存页面已满——使用淘汰算辅助内存实现存储法淘汰一页