作者bigrat2 (MrEric)
看板Grad-ProbAsk
標題[理工] [OS] Optimal repalcement & Second-Chance replacement
時間Sun Jan 17 22:43:31 2010
[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
1F：推 assassin88:我做法也跟你一樣..這時候就差在定義了 01/17 22:46
2F：→ assassin88:看Optimal定義為最近將會最少使用，還是往後最少使用。 01/17 22:47
3F：→ taitin:應該是答案錯 01/17 22:53
4F：→ bigrat2:但是答案把6置換掉,下個進字串就是6了這樣不會很奇怪嘛？ 01/17 23:40
5F：→ bigrat2:所以是答案錯嘛？我找鼎茂也沒有出五版的勘誤表 01/17 23:42
6F：→ bigrat2:發現五版真的錯誤很多 :( 01/17 23:42
7F：→ bigrat2:如果是看往後最少使用的話3也只會用到一次怎麼不選3呢？ 01/17 23:45
※ 編輯: bigrat2 來自: 114.33.6.216 (01/17 23:57)
8F：推 howar31:最近最少使用的不是LRU嗎？囧 Optimal好像是以後最慢用到? 02/28 21:07
9F：→ ru03jo6m4:所以Optimal退化時應該是FIFO還是LRU? 02/28 01:17