页面淘汰算法下缺页次数的计算.docVIP

通常，操作系统在进行存储管理时，如果在地址映射过程中的页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址将该页调入内存，以使作业继续运行下去。如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号。如果此时内存中没有空闲块，则要淘汰某页；若该页在内存期间被修改过，则要将其写回外存。在进行页面淘汰时，如何选定要淘汰的页面？通常可以用算法有先进先出页面淘汰算法（FIFO）、最近最少使用页面淘汰算法（LRU）和最不经常使用页面淘汰算法（LFU）等。 页面淘汰算法概述 a.随机算法（Random Algorithm)（了解） 利用软件或硬件的随机数发生器来确定主存储器中被替换的页面。这中算法最简单，而且容易实现。但是，这种算法完全没有利用主存储器中页面调度情况的历史信息，吗也没有反应程序的局部性，所以命中率较低。 b.先进先出调度算法(FIFO) 先进先出调度算法根据页面进入内存的时间 先后选择页面，本算法实现时需要将页面按照进入的时间先后组成一个队列，每次调度队首页面（即最早进入的页面）予以淘汰。它的优点是比较容易实现，能够利用主存储器中页面调度情况的历史信息，但是它没有反映程序的局部性，因为最先调入主存的页面，很可能也是经常要使用的页面。 c.最近最少调度算法 （LFU） 先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内可能会经常访问它们，因此最近最少用调度在选择淘汰页面是会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现是需要为每个页面设置数据结构的记录页面自上次访问以来所经历的时间。 d.最近最不常用调度算法 （LRU） 由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一段时间内经常被访问的代码和数据将来可能也会经常被访问，，显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数开选择淘汰页面，每次淘汰访问次数最少的页面。算法实现是需要为每个页面设置计数器，记录访问次数。计数器有硬件或操作系统自动定时清零。 e.最优替换算法 OPT 前面介绍的集中页面调度算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内主存储器的页面调度情况是相同的。显然，这种假设不总是真确的，最好的算法应该是选择将来最久不被访问的页面最为被替换的页面，这种算法命中率一定是最高的。它就是最优替换算法，实现OPT算法，唯一的方法就是让程序先执行一边，记录下实际的页地址流情况，根据这个页地址流才能找出当前要被替换的页面，显然，这样做是不现实的，因此，OPT算法只是一种理想化的算法，然而，它也是一种很有用的算法，实际上，经常把这种算法用来作为评价其它页面调度算法好坏的标准，在其它条件相同的情况下，哪种页面调度算法的命中率与OPT想近，那么，它就是一种比较好的页面置换算法 缺页次数和缺页中断率，缺页置换率计算： Ⅰ.缺页中断次数是缺页是发出缺页中的次数（缺页中断就是要访问的页不在主存，需要操作系统将其调入主存后再进行访问）。 Ⅱ.缺页中断率=缺页中断次数/中的页面引用次数 缺页调度次数是调入新页时需要进行页面调度的次数缺页置换率=缺页调度次数/总的页面引用次数 典型例题