CH4存储器管理解析.ppt

4.7 页面置换算法 页面替换算法又称页面调度算法、淘汰算法或置换算法。 当主存空间已装满而又要装入新页时，必须按一定算法把主存的一些页面调出去，这项工作称页面替换。 如果算法不适当，刚被换出的页很快被访问，需重新调入，因此需再选一页调出，而此时被换出的页很快又要被访问，因而又需要将它调入，如此频繁更换页面，以致花费大量时间，称这种现象为“抖动”。 这是Belady于1966年提出的一种理论上的算法。该算法每次都淘汰以后永不使用的，或者过最长的时间后才会被访问的页面。 显然，采用这种算法会保证最低的缺页率，但它是无法实现的，因为它必须知道页面“将来”的访问情况。不过，该算法仍有一定意义，可作为衡量其他算法优劣的一个标准。 （1）最佳淘汰算法——OPT(Optimal) 假定系统为某个进程分配了三个物理块，进程的访问顺序为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2 采用OPT淘汰算法： 7 7 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 4 4 4 0 0 0 0 0 1 1 1 3 3 3 3 3 3 3 3 1 1 命中 * * * * * * * 7，0，1，2，0，3，0，4，2，3，0 ，3，2，1，2 缺页8次，命中7次 （2）先进先出淘汰算法——FIFO 这是最早出现的淘汰算法。 总是淘汰最先进入内存的页面。它实现简单，只需把进程中已调入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存中最老的页面。 缺点：效率不高，因为它与进程实际的运行规律不相适应，比如常用的全局变量所在的页面或者循环体所在页面都可能被它选为淘汰对象。出现bleady现象。 采用FIFO淘汰算法（三个物理块）： 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 1 0 0 0 3 3 3 3 3 2 * * * 命中 7，0，1，2，0，3，0，4，2，3，0 ，3，2，1，2 缺页12次，命中3次 采用FIFO淘汰算法(4个物理块)： 0 1 2 2 3 3 4 4 4 0 0 0 1 2 7 0 1 1 2 2 3 3 3 4 4 4 0 1 7 0 0 1 1 2 2 2 3 3 3 4 0 7 7 0 0 1 1 1 2 2 2 3 4 * * * * * * 命中 7，0，1，2，0，3，0，4，2，3，0 ，3，2，1，2 缺页9次，命中6次 Belady现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。 Belady现象的描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S, N)时而增大，时而减小。 Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。 Belady现象 （3）最近最久未使用算法（LRU） 根据页面调入内存后的使用情况，选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。 OPT算法使用页面将要被访问的时间，LRU算法使用页面最后一次被访问的时间。二者唯一的差别是：OPT是向前看的，而LRU是向后看的。 下面给出LRU的两个实现算法： 计时法：对于每一页面增设一个访问时间