[理工] [OS] 清大資工97 replacement algorithum

[Lautreamont (Maldoror is dead)]

http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/97/2002.pdf

第六題 大意是:
500次reference 這500次中包含6個pages
可用頁框數為4
(1)求最小page fault次數
(2)求最大page fault次數
(3)若是n個reference，求最大page fault次數(即以n表示)

以下是我的想法:
(1) 因為要包含六個pages，必然有6個compulsory miss
    所以最少6個page fault

(2) 用猜的...
    假設refernce順序是123456123456...
    觀察到除前面6個外，後面每5個refernce有2個miss
    所以我寫 6 + ((500-6) div 5) + ((500-6) mod 5)-3 = 203

(3) 承(2)也用猜的...

總覺得(2)(3)應該是錯的，但是想不出其他好方法

請問有寫過的各位大大，不吝賜教
謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.244.169
推 polomoss:想法沒錯，差在計算而已，不過我手邊也沒答案~
→ polomoss:3)比較難導
→ Lautreamont:(2)也是嗎? 我想說應該會有的更好的想法證明最大
推 lightergogo:500應該要扣掉6吧?
※ 編輯: Lautreamont     來自: 220.136.244.169      (03/10 23:13)
→ Lautreamont:對打的時候忘計扣了
推 assassin88:感覺(2)的應該更多
→ Lautreamont:我是對自己想法沒信心 在想哪種狀況會使OPT最大
推 assassin88:我覺得最多的情況應該是，一開始的6個reference後，每
→ assassin88:次皆為PF，所以共為500次。(ex:123456123456...)
→ assassin88:噢..我錯了= =  是OPT..
推 ohstar:一開始4個錯 接下來每4個錯2個(因為opt可以估到2個) 這樣?