作者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