假設說，因為最近忙於寫報告，需要用到一些參考資料，所以要到圖書館去借書
這時候問題來了，我要參考的書籍有10本，但是圖書館限制說學生總共只能借4本書，而且借書、還書每一次只能1本
所以有6本書我"暫時"沒辦法借到，等到日後要用再來借，這時候我會希望說想出一個辦法，能夠跑最少次圖書館（因為圖書館很遠），而把我要參考的書都借到 手，完成我的報告。根據這個作為出發點，可以想出幾個方法：
例如我需要用到的書單編號是（分頁要求的順序）：1、2、3、4、2、1、5、6、7、5、4、3
不管怎麼做，都有一個基本原則：先察看自己身上有沒有該參考書，沒有的話代表說要跑圖書館去借了（類似置換的動作）。
FIFO 先進先出：最簡單的方法
我的借書單（分頁表），一開始雙手空空，順序是 1、2、3、4、2、1、5、6、7、5、 4、3
| 位置 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 4 | 4 | 4 | 1 |
| 順序 | 1 | 2 | 3 | 4 | 2 | 1 | 5 | 6 | 7 | 5 | 4 | 3 |
| 格子(Frame)1 | 1 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 |
| 格子(Frame)2 | 2 | 2 | 2 | 2 | 2 | 2 | 6 | 6 | 6 | 6 | 6 | |
| 格子(Frame)3 | 3 | 3 | 3 | 3 | 3 | 3 | 7 | 7 | 7 | 7 | ||
| 格子(Frame)4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 3 | |||
| 總計 | 1 | 2 | 3 | 4 | 4 | 4 | 5 | 6 | 7 | 7 | 7 | 8 |
| 註解 | ||||||||||||
也就是說，我要跑8次圖書館才能借齊所要用到書
以上廢話，可略
======================================================================================================================
Second Chance + FIFO Ver1 ： 最簡單的版本
原則：
1.當分頁被載入的時候，參考位元設成1， 表示多了一次機會，如果需求的分頁在分頁表中，參考位元也設為1
2.當要存取的分頁不在分頁表中，從 頭到尾掃瞄參考位元，遇 到1 設為0， 遇到0則替換調這一頁， 掃完了再從頭到尾掃一次
3.替換上來的那一頁，參考位元設為1
例子：1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6
| 1 | 2 | 3 | 4 | 2 | 1 | 5 | 6 | 2 | 1 | 2 | 3 | 7 | 6 | 3 | 2 | 1 | 2 | 3 | 6 | |
| 分 頁 表 | 1 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | 1 | 6 |
| 2 | 2 | 2 | 2 | 2 | 2 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 3 | 3 | ||
| 3 | 3 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | |||
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | ||||
| 參 考 位 元 | 1 | 1 | 1 | 1 | 1 | 1(0) | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1(0) | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | ||
| 1 | 1 | 1 | 1(0) | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | |||
| 1 | 1 | 1(0) | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | ||||
| 總 計 | 1 | 2 | 3 | 4 | 4 | 4 | 5 | 6 | 7 | 8 | 8 | 9 | 10 | 10 | 10 | 11 | 12 | 12 | 13 | 14 |
| 註 | A | B | C |
A.當要載入第5頁的時候，第5頁不在分頁表中，因為前面一欄的參考位元是1111(藍色部分)，掃瞄過一次之後就變成0000(刮號的部分)，
再重新掃瞄發現第一個0，就把它替換出去，接著把第5頁換進來，參考位元設為1，所以變成1000(紫色部分)
B.當要載入第6頁，第6頁不在分頁表中，前面的參考位元是1000(紫色部分)，掃瞄過一次，把第一個參考位元設成0，發現第二個參考位元為0，把它置 換出去，其他的參考位元不動，把第6頁換進來，參考位元設為1，所以變成0100(黃色部分)
C.當要載入第2頁，第2頁不在分頁表中，前面的參考位元是0100(黃色部分)，掃瞄過一次，第一個參考位元是0，把它置換出去，
其他的參考位元不動，把第2頁換進來，參考位元設為1，所以變成1100(橙色部分)
其他以此類推，所以總共會有14次分頁錯誤
Second Chance + FIFO Ver2 ：多了指標，13次分頁錯誤
原則上，比第一個版本多了一個指標，記錄上一次被替換掉的參考位元的位置
如果要求的分頁不在分頁表中，並不是從頭掃到尾，而是從指標所指定
原則：
1.當分頁被載入的時候，參考位元設成1， 表示多了一次機會
如果需求的分頁在分頁表中，參考位元也設為1
2.當要存取的分頁不在分頁表中，從指標所指定的位置開始掃瞄參考位元，遇 到1 設為0， 遇到0則替換調這一頁， 掃完了再從頭到尾掃一次
3.替換上來的那一頁，參考位元設為1
| 1 | 2 | 3 | 4 | 2 | 1 | 5 | 6 | 2 | 1 | 2 | 3 | 7 | 6 | 3 | 2 | 1 | 2 | 3 | 6 | |
| 分 頁 表 | 1 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 2 | 2 | 2 | 6 | 6 | 6 | 6 | 6 | 7 | 7 | 7 | 7 | 7 | 7 | 3 | 3 | ||
| 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | |||
| 4 | 4 | 4 | 4 | 4 | 4 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | ||||
| 指 標(1) | 2 | 3 | 4 | 1 | 1 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 4 | 4 | 1 | 2 | 2 | 3 | 3 |
| 參 考 位 元 | 1 | 1 | 1 | 1 | 1 | 1(0) | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1(0) | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | ||
| 1 | 1 | 1 | 1(0) | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | |||
| 1 | 1 | 1(0) | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | ||||
| 總 計 | 1 | 2 | 3 | 4 | 4 | 4 | 5 | 6 | 7 | 8 | 8 | 9 | 10 | 10 | 10 | 11 | 12 | 12 | 13 | 13 |
指標指的是下一個要被替換的分頁位置，初始值為1
Second Chance + LRU 改良版：這個有點複雜，不要太深入研究，錯誤率也不是最少的XD
| 1 | 2 | 3 | 4 | 2 | 1 | 5 | 6 | 2 | 1 | 2 | 3 | 7 | 6 | 3 | 2 | 1 | 2 | 3 | 6 | |
| 分 頁 表 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | ||
| 3 | 3 | 3 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | |||
| 4 | 4 | 4 | 4 | 6 | 6 | 6 | 6 | 6 | 7 | 7 | 7 | 7 | 7 | 2 | 2 | 2 | ||||
| 載 入 時 間 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | 5 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 | 1 | 2 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 0 | 0 | 1 | 2 | 3 | ||
| 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |||
| 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | ||||
| 參 考 位 元 | 1 | 1 | 1 | 1 | 1 | 1(0) | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1(0) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | ||
| 1 | 1 | 1 | 1(0) | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | |||
| 1 | 1 | 1(0) | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | ||||
| 總 計 | 1 | 2 | 3 | 4 | 4 | 4 | 5 | 6 | 6 | 6 | 6 | 7 | 8 | 9 | 9 | 9 | 10 | 11 | 11 | 11 |
沒有留言:
張貼留言