[理工] [OS] Optimal repalcement & Second-Chance replacement

[bigrat2 (MrEric)]

[95淡江]
Suppose that there are four frames allocated for process in a virtual memory
system.Consider the following page-reference string for this process:
1,2,3,4,2,1,3,5,6,3,2,1,2,3,4,7,6,3,2,1,7,4,5,1,2
How many page fault would occur for the following replacement algo?
(1)Optimal
解答

1 2 3 4 2 1 3 5 6 3 2 1 2 3 4 7 6 3 2 1 7 4 5 1 2
-----------------------------------------------
1 1 1 1       1 1           1 1 1 1     1   1
  2 2 2       2 2           2 2 2 2     2   2
    3 3       3 3           3 7 6 3     7   5
      4       5 6           4 4 4 4     4   4
-------------------------------------------------上述為洪逸解答
                            #
                            4 7       7   7 5
      前面步驟相同          2 2       2   2 2
                            3 3       3   4 4
                            6 6       1   1 1


我的問題是,上述為洪逸的解答,paga fault 共12次
但是我覺得在#號開始的步驟如果這樣做的話page fault只剩下11次
請問我的想法有錯誤嘛？還是答案錯了呢？
謝謝各位

問題二

(2) Second-Chance replacement
題目相同
答案如下
1 2 3 4 2 1 3 5 6 3 2 1 2 3 4 7 6 3 2 1 7 4 5 1 2
--------------------------------------------------
1 1 1 1       5
  2 2 2       2     <------為什麼置換掉1？
    3 3       3
      4       4

上述步驟我不懂的是為什麼不置換掉4?
1不是上個步驟才被使用到reference bit 應該為1?2也有被使用到也是1
但是4沒有被使用到應該是0,所以為什麼不是置換掉4呢？
（second-chance我找了講義跟金寶典都沒有講的很清楚 :(
拜託各位了



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.33.6.216
推 assassin88:我做法也跟你一樣..這時候就差在定義了
→ assassin88:看Optimal定義為最近將會最少使用，還是往後最少使用。
→ taitin:應該是答案錯
→ bigrat2:但是答案把6置換掉,下個進字串就是6了這樣不會很奇怪嘛？
→ bigrat2:所以是答案錯嘛？我找鼎茂也沒有出五版的勘誤表
→ bigrat2:發現五版真的錯誤很多 :(
→ bigrat2:如果是看往後最少使用的話3也只會用到一次怎麼不選3呢？
※ 編輯: bigrat2         來自: 114.33.6.216         (01/17 23:57)
推 howar31:最近最少使用的不是LRU嗎？囧 Optimal好像是以後最慢用到?
→ ru03jo6m4:所以Optimal退化時應該是FIFO還是LRU?