操作系统第七版第九章.ppt

Use Of A Stack to Record The Most Recent Page References 4,7,0,7,1,0,1,2,1,2,7,1,2 1 2 0 7 4 2 1 0 7 4 1 0 7 4 0 1 7 4 1 7 0 4 7 0 4 0 7 4 7 4 4 Use Of A Stack to Record The Most Recent Page References 4,7,0,7,1,0,1,2,1,2,7,1,2 2 1 0 7 4 1 2 0 7 4 2 1 0 7 4 1 0 7 4 0 1 7 4 1 7 0 4 7 0 4 0 7 4 7 4 4 Use Of A Stack to Record The Most Recent Page References 4,7,0,7,1,0,1,2,1,2,7,1,2 2 1 0 7 4 1 2 0 7 4 2 1 0 7 4 1 0 7 4 0 1 7 4 1 7 0 4 7 0 4 0 7 4 7 4 4 7 2 1 0 4 Use Of A Stack to Record The Most Recent Page References 4,7,0,7,1,0,1,2,1,2,7,1,2 2 1 0 7 4 1 2 0 7 4 2 1 0 7 4 1 0 7 4 0 1 7 4 1 7 0 4 7 0 4 0 7 4 7 4 4 7 2 1 0 4 1 7 2 0 4 Use Of A Stack to Record The Most Recent Page References 4,7,0,7,1,0,1,2,1,2,7,1,2 2 1 0 7 4 1 2 0 7 4 2 1 0 7 4 1 0 7 4 0 1 7 4 1 7 0 4 7 0 4 0 7 4 7 4 4 7 2 1 0 4 2 1 7 0 4 9.4.5 LRU Approximation Algorithms Additional-Reference-Bit Algorithm With each page associate a bit, initially = 0 When page is referenced, set bit to 1 Replace the one which is 0 (if one exists) Shift registers： keep an 8-bit byte for each page in a table in memory, say R=Rn-1Rn-2Rn-3 … R2R1R0 The operating system shifts the reference bit for each page into the high-order bit of its 8-bit byte, shifting the other bits right by 1 bit and discarding the low-order bit the page with the lowest number is the LRU page 9.4.5 LRU Approximation Algorithms Second chance Need reference bit Clock replacement If page to be replaced (in clock order) has reference bit = 1 then: set reference bit 0 leave page in memory replace next page (in clock order), subject to same rules Second chance Algorithm(Clock) FIFO算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改—二次机会算法 基于FIFO算法 当需要选择一页进行置换时，检查其引用位 若引用位为0，淘汰该页面（因为近期该页未被访问） 若引用位为1，则不置换该页（给予该页第二次机会），将该引用位置0，然后检查下一页（按FIFO顺序,顺时针） 一般地，将页面按照FIFO顺序建立一个循环队列； Second-Chance (clock) Replacement Algorithm 不淘汰该页 淘汰该页 Enhanced Second-chance Algorithm 在二次机会算法的基础上，再增加一个修改位 The reference bit and the modify bit as an order pair (reference bit , modif