【文章內(nèi)容簡介】 2 Operating System Concepts Page Replacement ? Use modify bit (or dirty bit) to reduce overhead of page transfers – only modified pages are written to disk（ 通過設(shè)置 修改位 以減少頁面?zhèn)魉偷拇螖?shù) —只有被修改的頁面才寫入磁盤） . ? The bit is indicating that the page has been modified ? If the bit is set, the page must be written to disk ? If the bit is not set, the page has not been modified sine it was read into memory, so we can avoid writing the page to disk. ? In this way ,we can reduce the time required to service a page fault Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Page Replacement Algorithms ? Two major problems: ?Frameallocation algorithm ?How many frames to allocate to each process? ?Pagereplacement algorithm ?Which frames are to be replaced? ? There are many algorithms ? Goal: ?Lowest pagefault rate Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Page Replacement Algorithms ? Want lowest pagefault rate. （ 追求最小的缺頁率） ? Evaluate algorithm by running it on a particular string of memory references (reference string) and puting the number of page faults on that string. （ 通過運行一個內(nèi)存訪問的特殊序列（訪問序列），計算這個序列的缺頁次數(shù)） ? We only consider page number, rather than the entire address ? If we have a reference to a page p, then any immediately following references to page p will never cause a page fault ? In all our examples, the reference string is （ 在所有的例子中，訪問序列是） : (1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5) and ( 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 ) Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Graph of Page Faults Versus The Number of Frames Silberschatz, Galvin and Gagne ?2022 Operating System Concepts FIFO Page Replacement 缺頁次數(shù)： 15次 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts FIFO Algorithm Belady’s Anomaly ? 在 FIFO算法中，有時侯頁架數(shù)的增加反而會使缺頁次數(shù)增加，如下例： number of frames is 3 or 4 ? Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 ? 3 frames (3 pages can be in memory at a time per process) ? 4 frames ? FIFO Replacement – Belady’s Anomaly ? more frames ? less page faults 1 2 3 1 2 3 4 1 2 5 3 4 9 page faults 1 2 3 1 2 3 5 1 2 4 5 10 page faults 4 4 3 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts FIFO Illustrating Belady’s Anamoly Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Optimal Replacement ? Replace page that will not be used for longest period of time. （ 被置換的頁將是今后最長時間不被使用的頁） 缺頁次數(shù)： 9次 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Optimal Algorithm ? 4 frames example 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 ? How do you know this? ?情況與 SJF CPUscheduling算法相似 ? Used for measuring how well your algorithm performs. （ 用來衡量你的算法的效率） 1 2 3 4 6 page faults 4 5 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts LRU Page Replacement 缺頁次數(shù)： 12次 Least Recently Used (LRU) Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Least Recently Used (LRU) Algorithm ? Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 ? 實現(xiàn)方式： （ 1） Counter implementation （ 計數(shù)器的實現(xiàn)） ? Every page entry has a counter。 every time page is referenced through this entry, copy the clock into the counter. （ 每一個頁表項 有一個計數(shù)器，每次頁通過這個表項被訪問，把時間拷貝到計數(shù)器中） ? When a page needs to be changed, look at the counters to determine which are to change. （ 當一個頁需要替換時，查看計數(shù)器來決定改變哪一個頁。） 1 2 3 5 4 4 3 5 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts LRU Algorithm (Cont.) （ 2） Stack implementation – keep a stack of page numbers in a double link form : 棧實現(xiàn) —在一個雙鏈表中保留一個記錄頁數(shù)目的棧 ? Page referenced （ 被訪問的頁） : ?move it to the top when a page is referenced（ 移到棧頂） ?requires 6 pointers to be changed 需要改變 6個指針 ?No search for replacement 沒有為置換進行查找 ? The top of the stack is always the most recently used page ? The bottom is the LRU page Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Use Of A Stack to Record The Most Recent Page References Silberschatz, Galvin and Gagne ?2022 Operating System Concepts 置換算法舉例（ 1） 某程序在內(nèi)存中分配三個頁面，初始為空，頁面走 向為 4， 3， 2， 1， 4， 3， 5， 4， 3， 2， 1， 5。 OPT 4 3 2 1 4 3 5 4 3 2 1 5頁 1 4 3 2 1 1 1 5 5 5 2 1 1頁 2 4 3 3 3 3 3 3 3 5 5 5頁 3 4 4 4 4 4 4 4 4 4 4 x x x x 3 3 x 3 3 x x 3 共缺頁中斷 7 次Silberschatz, Galvin and Gagne ?2022 Operating System Concepts 置換算法舉例（ 2） LRU 4 3 2 1 4 3 5 4 3 2 1 5頁 1 4 3 2 1 4 3 5 4 3 2 1 5頁 2 4 3 2 1 4 3 5 4 3 2 1頁 3 4 3 2 1 4 3 5 4 3 2 x x x x x x x 3 3 x x x共缺頁中斷 10 次Silberschatz, Galvin and Gagne ?2022 Operating System Concepts 置換算法舉例（ 3） FIFO 4 3 2 1 4 3 5 4 3 2 1 5頁 1 4 3 2 1 4 3 5 5 5 2 1 1頁 2 4 3 2 1 4 3 3 3 5 2 2頁 3 4 3 2 1 4 4 4 3 5 5 x x x x x x x 3 3 x x 3共缺頁中斷 9 次Silberschatz, Galvin and Gagne ?2022 Operating System Concepts LRU Approximation Algorithms ? Reference bit（ 訪問位） ?With each page associate a bit, initially = 0 每個頁都與一個位相關(guān)聯(lián)，初始值位 0 ?When page is referenced bit set to 1 當頁被訪問位時，設(shè)位 1 ?Replace the one which is 0 (if one exists). We do not know the order, however. 如果存在的話，置換位為 0的頁。然而我們并不知道頁的使用順序，只知道那些頁被使用過（ reference bit=1）， 哪些被沒有使用過（ reference bit =0） ?根據(jù)這些信息，可以設(shè)計出許多與 LRU相類似的算法 . Silberschatz, Galvin and Gagne ?2022 Operating System Concepts AdditionalReferenceBits Algorithm ? 每一頁的頁表中都保持一個 8位字節(jié)，初始時為 0 ? 設(shè)定一個定時器（例如，每 100ms/次）。每次定時中斷時將每頁的 8位右移 1位，去掉最右位 ? 某頁被訪問時，最高位（最左位）置 1 ? 需要置換頁時，比