Re: [理工] [OS]page-replacement

[mqazz1 (無法顯示)]

※ 引述《jim055006 (jim)》之銘言：
: Assume a page reference string for a process with m frames(initially
: all empty). The page reference string has lenth p with n distinct
: page numbers occurring in it. For any page-replacement algorithm,
: (1)What is a lower bound on the number of page faults?
: (2)What is a upper bound on the number of page faults?
: 答案是
: (1)n
: (2)p
: 有人可以解釋一下為什麼嗎?
: 鋼溫!!

(1) page fault至少會發生n次

因為m個frame一開始都是空的 而page reference string有n個不同的page number

所以page fault至少會發生n次

(2) 因為page refernce string的長度是p 所以worse case下 會發生p次page fault


我覺得多想一下應該就可以了

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.118.110.186
推 jim055006:我最主要是被stirng has length p with n distinct page
→ jim055006:numbers這句話困住了
→ jim055006:感謝M大....我在想想看....
page reference string的length是p

worse case下 每次都發生page fault 所以發生p次

n個不同的page number 我再想想該怎麼表達會比較好@@

推 jim055006:我在想這個答案應該是在P>N的情況下吧?
p應該會大於等於n 因為p不可能比n小

→ jim055006:真的很感謝M大這麼熱心跟我討論....
※ 編輯: mqazz1          來自: 140.118.110.186      (10/25 23:17)
→ jim055006:所以我在想這麼題目是不是應該多加p>n這個條件會比較貼
→ jim055006:切一點...還是說p>n算是已知的條件..??
應該算是trivial..XD

因為我覺得p>n應該是非常直觀的

※ 編輯: mqazz1          來自: 140.118.110.186      (10/25 23:24)
→ jim055006:哈哈哈....好的...既然都trivial了...那我懂了
我舉例子好了@@

page reference string: 58 59 16 48 13 46

長度是6 有6個不同的page number

page reference string: 58 58 16 48 13 46

長度是6 有5個不同的page number

※ 編輯: mqazz1          來自: 140.118.110.186      (10/25 23:29)
→ jim055006:給mqazzl大一個讚!!
→ jim055006:對了M大我還有兩題OS的問題...方便的話你幫我看看..
→ mqazz1:那兩題不太會耶@@
推 jim055006:喔喔~~我懂了....例子舉得太好了....鋼溫!!!
推 jim055006:NO MIND...還是謝謝你~~
→ sneak: 對了M大我還有兩題OS https://daxiv.com