頁碼更算演算法

假設一個小型系統包含4個page frames,使用LRU、FIFO、

Optimal等page replacement策略,若reference string為

0 1 6 2 4 1 0 2 6 1 0 4 ,當page frames初始值皆為empty時,

會發生page fault的次數為何?

我先把我的想法key上去好了:

LRU:

0-0

1-01

6-016

2-0162

4-4162

1-分頁已有

0-4102 6很久沒用

2-分頁已有

6-4602 1很久沒用

1-1602 4很久沒用

0-分頁已有

4-1604 2很久沒用

故9次============>答案為8次

想請問我是錯在哪邊,或是有更好的解法能夠得知答案

另外FIFO與Optimal的演算法觀念還不是很清楚

希望有大大能夠提供詳細的解法,感謝!!

1 Answer

Rating
  • 1 decade ago
    Favorite Answer

    0-0    page fault

    1-01   page fault

    6-016  page fault

    2-0162 page fault

    4-4162 取代0  page fault

    1-4162 ok

    0-4102 取代6  page fault

    2-4102 ok

    6-6102 取代4  page fault 這行!

    1-6102 ok

    0-6102 ok

    4-6104 取代2  page fault

    共八次,沒錯呀!你在這行標記的地方,應該取代4,而你選擇取代1所以後面都算錯了!

Still have questions? Get your answers by asking now.