Re: Clock & Second Chance

[yanunix (臣知罪...)]

※ 引述《kewang (一段車禍的故事......orz)》之銘言：
: 這兩個都看不懂啦
: 什麼dirty bit & used bit
: 這什麼鳥啦~
: 用google找了一堆資料  結果都沒有流程圖  只有敘述而已
: 再度orz
: 不管了  看機率去~  滾拜

dirty bit 就是髒的位元嘛...也就是說是frame內容更新~
used bit 就是用過的位元嘛...也就是取用過的位元

這不是重點，重點是幹嘛用~

當frame被存取過時，dirty bit 設為 1，
┌────────┬─────────────────────────┐
│Time          0 │ 1    2    3    4    5    6    7    8    9    10  │
├────────┼─────────────────────────┤
│Requests        │ c    aw   d    bw   e    b    aw   b    c    d   │
└──────╥─┼─────────────────────────┤
  Page      0 ║a ║ a    a    a    a    a    a    a    a    a    a   │
  Frame     1 ║b ║ b    b    b    b    b    b    b    b    b    d   │
            2 ║c ║ c    c    c    c    e    e    e    e    e    e   │
            3 ║d ║ d    d    d    d    d    d    d    d    c    c   │
═══════╩═╩═════════════════════════╝
 Faults                                  *                   *    *
────────────────────────────────────
                ↑1               4↑  5↑   6↑   ↑7     9↑    ↑10
             ＠10 a             ＠11a  00a*  00a*  11a   ＠ 11a ＠00a*
     起始值    10 b               11b  00b*  10b*  10b*     10b*  10d
               10 c               10c  10e   10e   10e      10e   00e
               10 d               10d＠00d ＠00d ＠00d      10c   00c
────────────────────────────────────
↑+number=標示時間
＠表示指標所在位置

在 1 時，起始值相信沒問題吧~
在 4 時，因為在這 4 個時間裡，分別取 c、d，而寫入 a、b，所以這四個frame
         的used bit需設為 1，且 a、b 的dirty bit則需設為 1，因為 a、b 的
         資料都更新過，所以需要做寫入的動作，請注意，是需要做，不是已經做
         。
在 5 時，需要 e 這個資料，clock就是繞圈子嘛，這時候＠從 a 開始往下，遇到
         used bit為 1 者，則將其used bit設為 0 ，若 used bit原本就為 0 ，
         則將此frame取代，指標指向下一個，這裡的 a* 是第一個被檢查的，
         used bit設為 0 。
         繼續檢查，全部frame都檢查完了，used bit都設成 0 了，
         可看到 a 多了一個 *，此 * 代表此frame將被寫入儲存體，但尚未寫入，
         繼續向下檢查，b 也是多了 * ，再往下檢查，唷~ c 剛剛被清掉 used bit，
         所以 c 的used bit和dirty bit皆為 0 囉！便把 c 取代成 e。

以此類推，dirty bit就是在當frame被更新時，暫時不寫入儲存體，而多了個 * 標記，
表示這個frame被改過了，但還不必寫入儲存體，指標找不到frame可以取代時，再取代
它，基本上，這個frame只有兩次逃過取代命運的機會，所以叫 second chance。
可以避免浪費太多時間在寫入資料上。

--
┬  ┬╭─╮╭╮┬┬  ┬╭┐┬┬╭┐╮
╰┬╯├─┤││││  │││││┌┼┘
  ┴  ┴  ┴┴└╯╰─╯┴└╯┴╰└╯by yanunix

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.56.184.235
→ yanunix:打到快吐~自個兒推一個~
推 kewang:orz orz orz  我印出來了
推 kyong:哇~我還真的一點都看不懂…不過還是推…
推 kewang:大王m不m ??
推 JoeTsang:感覺這篇真的很不錯...m吧 花很多心血的
推 JoeTsang:計結小老師→yanunix  ^^
推 JoeTsang:我也要 Orz Orz Orz Orz Orz Orz Orz Orz
推 yanunix:no 考...
推 JoeTsang:殘念爹斯...
推 yanunix:push
推 yanunix:push