页面置换算法ppt课件.ppt

4.3.4页面置换算法,1最优算法（OPT算法）2先进先出算法（FIFO算法）3最久未使用页面置换算法（LRU算法）4LRU近似算法,下一页,1,1最优算法（Optimal算法）,它是一种理想化的算法，性能最好，但在实际上难于实现。即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。但是要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法。例：假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。如下图所示，进程运行时先将7，0，1三个页面装入内存。当进程访问页面2时，产生缺页中断，此时OS根据最佳置换算法，页面7将在第18次才被访问，是三页中将最久不被访问的页面，所以被淘汰。接着访问页面0时，发现已在内存中，而不会产生缺页中断，以此类推。从图可以看出，采用最佳置换算法，只发生了6次页面置换。,下一页,2,3,2先进先出算法（FIFO算法）,这种算法的基本思想是：总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。,下一页,4,图4.20先进先出算法存储分块表构造,下一页,5,3最久未使用页面置换算法（LRULeastRecentlyUsed算法）,这种算法的基本思想是，如果某一页被访问了，那么它很可能马上又被访问；反之，如果某一页很长时间没有被访问，那么最近也不太可能会被访问。这种算法考虑了程序设计的局部性原理。其实质是，当需要置换一页时，选择在最近一段时间最久未使用的页面予以淘汰。实现这种算法可通过周期性地对“引用位”进行检查，并利用它来记录一页面自上次被访问以来所经历的时间t，淘汰时选择t最大的页面。,下一页,6,4LRU近似算法,这种算法，只要在存储分块表（或页表）中设一个“引用位”，当存储分块表中的某一页被访问时，该位由硬件自动置1，并由页面管理软件周期性把所有引用位置0。这样，在一个时间周期T内，某些被访问过的页面其引用位为1，而未被访问过的页面其引用位为0。因此，可根据引用位的状态来判别各页面最近的使用情况。当需要置换一页面时，选择其引用位为0的页，如图4.21所示的算法。图4.22是这种近似算法的一个例子。,下一页,7,图4.21LRU近似算法,下一页,8,图4.22LRU近似算法举例,返回本节,9,4.3.5请求式分页存储管理性能分析举例,1程序设计的质量2页面的大小3分配的内存块数4页面置换算法性能,下一页,10,【例1】主存块数m=3，置换算法采用FIFO算法，缺页中断次数及缺页率如图4.23所示。在图4.23中，P行表示页面走向，M行表示在主存中的页面号，其中带有+的表示新调入页面，在M行的各列按调入的顺序排列，带有圆圈的数字表示下一时刻将被淘汰页面，F行表示是否引起缺页中断，带号的表示引起缺页中断。从图4.23可以看出，缺页中断页数为9次，缺页率f=9/12=75%。,下一页,11,图4.23FIFO算法性能分析（m=3）,下一页,12,【例2】设m=4，仍采用FIFO算法，缺页中断次数及缺页率如图4.24所示。可以算出，在分配给该作业的内存块数增加到4时，缺页中断由图4.23的9次反而增加到了10次，缺页率由75%增加到10/12=83%，这就是FIFO算法的一种异常现象。随着分配的主存块数的增加，缺页中断次数不但没有降低，反而增加了。这与该算法定全不考虑程序的动态特征有关。,下一页,13,图4.24FIFO算法性能分析（m=4）,下一页,14,【例3】设m=3，采用LRU算法，缺页中断次数及缺页率如图4.25所示。,图4.25LRU算