操作系统-页面置换算法课件.pptx

《操作系统-页面置换算法课件.pptx》由会员分享，可在线阅读，更多相关《操作系统-页面置换算法课件.pptx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 1第一章 操作系统引论5.3 页面置换算法在进程运行过程中，若其所要访问的页面不在内存，而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page-Replacement Algorithms)。置换算法的好坏将直接影响到系统的性能。2 2第一章 操作系统引论5.3.1 最佳置换算法和先进先出置换算法1.最佳(Optimal)置换算法最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用

2、的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。但由于人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。3 3第一章 操作系统引论图5-3利用最佳页面置换算法时的置换图4 4第一章 操作系统引论2.先进先出(FIFO)页面置换算法FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的

3、页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。5 5第一章 操作系统引论图5-4 利用FIFO置换算法时的置换图6 6第一章 操作系统引论5.3.2 最近最久未使用和最少使用置换算法1.LRU(Least Recently Used)置换算法的描述FIFO置换算法的性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法是根据页面调入内存后的使用情况做出决策的。7 7第一章 操作系统引论图5-5

4、LRU页面置换算法8 8第一章 操作系统引论2.LRU置换算法的硬件支持1)寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3 R2R1R09 9第一章 操作系统引论当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(例如100 ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。10 10第一章 操作系统引论图5-6 某进程具有8个页面时的LRU访问情况11 11第一章 操作系统引论2)栈可利用一个特殊的栈保存

5、当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。假定现有一进程，它分有五个物理块，所访问的页面的页面号序列为：4，7，0，7，1，0，1，2，1，2，612 12第一章 操作系统引论图5-7用栈保存当前使用页面时栈的变化情况13 13第一章 操作系统引论3.最少使用(Least Frequently Used，LFU)置换算法在采用LFU算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。14 14

6、第一章 操作系统引论5.3.3 Clock置换算法1.简单的Clock置换算法当利用简单Clock算法时，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。15 15第一章 操作系统引论图5-8简单Clock置换算法的流程和示例16 16第一章 操作系统引论2.改进型Clock置换算法在将一个页面换出时，如果该页已被修改过，便须将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。换而言之，对于修改过的页面，在换出时所付出的开销比未修改过的页面大，或者说，置换代价大。在改进型Clock算法中，除须考虑页面的使用情况外，还须再增加一个因素置换代价。17

7、17第一章 操作系统引论5.3.4 页面缓冲算法(Page Buffering Algorithm，PBA)1.影响页面换进换出效率的若干因素(1)页面置换算法。(2)写回磁盘的频率。(3)读入内存的频率。18 18第一章 操作系统引论2.页面缓冲算法PBAPBA算法的主要特点是：显著地降低了页面换进、换出的频率，使磁盘I/O的操作次数大为减少，因而减少了页面换进、换出的开销；正是由于换入换出的开销大幅度减小，才能使其采用一种较简单的置换策略，如先进先出(FIFO)算法，它不需要特殊硬件的支持，实现起来非常简单。1)空闲页面链表2)修改页面链表19 19第一章 操作系统引论5.3.5 访问内存的有效时间与基本分页存储管理方式不同，在请求分页管理方式中，内存有效访问时间不仅要考虑访问页表和访问实际物理地址数据的时间，还必须要考虑到缺页中断的处理时间。