【正文】 時鐘單位中斷。 ? 修改頁表的另一種有用功能：修改的頁可以成族地寫回磁盤，大大減少 I/O操作的數(shù)目。以上面的觀點為基礎(chǔ)，最小計數(shù)的頁也許剛剛被換入 ,并且尚未使用 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts PageBuffering Algorithm ? Replaced page is added to one of two lists ?free page list if page has not been modified ?modified page list if page has been modified， 這些頁在被替換時可以暫時不寫入磁盤，而是在磁盤空閑時，將一批頁一起被寫出去 ? Note: all replaced paged are still keeping in memory. ?如果進程需要訪問該頁，可以迅速返回活動頁中。 ? 最小數(shù)的頁（不一定唯一）被置換 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts SecondChance Algorithm 二次機會算法 ? A FIFO replacement algorithm ? Need reference bit.（ 需要訪問位） ? Clock replacement.（ 時鐘置換） ? Algorithm： ? reference bit = 1 after the page is first referenced ? If reference bit = 0 replace that page ? Else if a page to be replaced (in clock order) has reference bit = 1, then（ 如果將要 以順時針 交換的訪問位是 1，則） : 1. set the reference bit of this page to 0（ 把訪問位設(shè)位 0） . 2. leave the page in memory（ 把該頁保留在內(nèi)存中） . 3. replace next page [reference bit =0] (in clock order), subject to same rules（ 以同樣的規(guī)則，按順時針方向去替換下一個頁） . Silberschatz, Galvin and Gagne ?2022 Operating System Concepts SecondChance (clock) PageReplacement Algorithm Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Enhanced SecondChance Algorithm ? Use an order pair: Reference bit and Modify bit ? 4 possible classes: ? (0,0) neither recently used nor modified—best page to replace ? (0,1) not recently used but modified—not quite as good. The page will be written out before replacement ? (1,0) recently used but clean—it probably will be used again soon ? (1,1) recently used and modified– it probably will be used again soon, and the page will be need to be written out to disk before it can be replaced ? Replace the first page encountered in the lowest nonempty class ? Compared clock algorithm, this algorithm give preference to those pages that have been modified to reduce the number of I/Os required Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Counting Algorithms ? Keep a counter of the number of references that have been made to each page. 用一個計數(shù)器記錄對每一個頁的訪問次數(shù)。然而我們并不知道頁的使用順序，只知道那些頁被使用過（ reference bit=1）， 哪些被沒有使用過（ reference bit =0） ?根據(jù)這些信息，可以設(shè)計出許多與 LRU相類似的算法 . Silberschatz, Galvin and Gagne ?2022 Operating System Concepts AdditionalReferenceBits Algorithm ? 每一頁的頁表中都保持一個 8位字節(jié)，初始時為 0 ? 設(shè)定一個定時器（例如，每 100ms/次）。） 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。更新頁和頁框表 4. Restart the process. 重啟進程 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Page Replacement Silberschatz, Galvin and Gagne ?2022 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 p