1?全局頁面置換算法

以上頁面置換算法都是針對單一的應用程序的頁面置換算法, 且有一個前提, 就是給單一應用程序分配的物理頁幀數量是一定的. 現實中, 給一個應用程序分配的物理頁幀數, 該程序產生的缺頁中斷也就越少, 而且程序運行過程中, 可能某些階段對于內存的讀寫操作很多, 某些階段很少, 所以給一個應用程序分配固定數量的物理頁幀是不合理的. 這樣就需要一個全局頁面置換算法, 可以動態對某個應用程序的物理頁幀數進行調整.?

2 工作集模型

前文介紹的各種頁面置換算法, 都是基于一個前提, 即程序的局部性原理. 但是此原理是否成立?

• 如果局部性原理不成立, 那么各種頁面置換算法就沒有什么分別, 也沒有什么意義. 例如: 假設進程對邏輯頁面的訪問順序是1 2 3 4 5 6 7 8 9 ..., 即單調遞增, 那么在物理頁面數有限的前提下, 不管采用何種置換算法, 每次的頁面訪問都必然導致缺頁中斷.
• 如果局部性原理是成立的, 那么如何來證明它的存在, 如何來對它進行定量地分析? 這就是工作集模型.

2.1 工作集

工作集: 一個進程當前正在使用的邏輯頁面集合.

可以用一個二元函數來表示:

• 是當前的執行時刻.
• 稱為工作集窗口(working set window), 即一個定長的頁面訪問的時間窗口.??可以表示在時刻前長度的時間范圍, 代表著一段時間.
• = 在當前時刻之前的時間窗口當中的所有頁面所組成的集合(隨著的變化, 該集合也在不斷的變化).
• 指工作集的大小, 即頁面數目.

2.2?常駐集

常駐集:?指在當前時刻, 進程實際駐留在內存當中的頁面集合.

• 工作集是進程在運行過程中固有的性質, 而常駐集取決于系統分配給進程的物理頁面數目, 以及所采用的頁面置換算法.
• 如果一個進程的整個工作集都在內存中, 即常駐集包含工作集, 那么進程將很順利地運行, 而不會造成太多的缺頁中斷(知道工作集發生劇烈變動, 從而過渡到另一個狀態).
• 當今成常駐集的大小達到某個數目之后, 再給它分配更多的物理頁面, 缺頁率也不會明顯下降.

3 兩個全局置換算法:

3.1 工作集頁面置換算法

3.1.1 原理

追蹤之前個的引用.

• 在之前個內存訪問的頁引用是工作集,?被稱為窗口大小.
• 實現原理: 獲取某時刻的時間窗口為的工作集, 如果此時應用程序所占用的物理頁不在工作集中, 就把他直接換出去(也就是說根據工作集實時調整常駐集, 保證常駐集是該時刻之前時間段內一直被使用的物理頁).

3.1.2 舉例

1. 假設有一個應用程序, 操作系統給其分配了五個物理頁幀A, B, C, D, E, 該應用程序對于邏輯頁的訪問序列是e d a c c d b c e c e a d, 時間窗口的長度是4, 如圖:

2. 當e d a c邏輯頁面訪問請求過來之后, 會產生四次中斷:

?

?3. 當請求4進來之后, 此時的工作集應為e d a c, c在工作集中, 也就是不會產生中斷, 重新確認此時的工作集, 變成了d a c, 也就是e應該被踢出工作集, 其占用的物理頁幀也會被釋放出來:

?4. 當請求5過來之后, 此時工作集是d a c, d在工作集中, 不會產生缺頁中斷, 重新確定工作集, 還是d a c:

?5. 當請求6過來之后, 此時工作集是d a c, b不在工作集中, 會產生缺頁中斷, 重新確定工作集, 變成了 c d b, a又被踢出工作集, 其占用的物理頁幀也被釋放了出來:

6. 當請求7過來之后, 此時工作集是c d b, c在工作集中, 不會產生缺頁中斷, 重新確定工作集, 還是c d b:

7. 當請求8過來之后, 此時工作集是c d b, e不在工作集中, 會產生缺頁中斷, 重新確定工作集, 為d b c e, 添加了e, 沒有需要被踢出工作集的頁面:

8. 當請求9過來之后, 此時工作集是d b c e, c在工作集中, 不會產生缺頁中斷, 重新確定工作集, 為b c e, d需要被踢出工作集:?

9. 當請求10過來之后, 此時工作集是b c e, e在工作集中, 不會產生缺頁中斷, 重新確定工作集, 為c e, b需要被踢出工作集:?

?10. 當請求11過來之后, 此時工作集是c e, a不在工作集中, 會產生缺頁中斷, 重新確定工作集, 為c e a, 沒有需要被踢出工作集:?

11. 當請求12過來之后, 此時工作集是c e a, d不在工作集中, 會產生缺頁中斷, 重新確定工作集, 為c e a d, 沒有需要被踢出工作集:??

3.2 缺頁率頁面置換算法

3.2.1 原理

可變分配策略: 常駐集大小可變. 例如: 某個進程在剛開始運行的時候, 先根據程序大小給它分配一定數目的物理頁面, 然后在進程運行過程中, 動態調整常駐集大小.

• 可采用全局頁面置換的方式, 當發生一個缺頁中斷時, 被置換的頁面可以是在其它進程中, 各個并發進程競爭地使用物理頁面.
• 優缺點: 性能較好, 但增加了系統開銷
• 具體實現: 可以使用缺頁率算法(PFF, page fault frequency)來動態調整常駐集的大小.

缺頁率:

缺頁率表示"缺頁次數 / 內存訪問次數"(比率)或"缺頁的平均時間間隔的倒數". 影響缺頁率的因素:

• 頁面置換算法
• 分配給進程的物理頁面數目
• 頁面本身的大小
• 程序的編寫方法

缺頁率算法:

若運行的程序的缺頁率過高, 可通過增加工作集來分配更多的物理頁面. 若運行的程序的缺頁率過低, 則通過減少工作集來較少它的物理頁面數. 力圖使運行的每個程序的缺頁率保持在一個合理的范圍內.

3.2.2 算法實現

保持追蹤缺失發生概率:

當缺失發生時, 從上次頁缺失起計算這個時間差并記錄這個時間差,?是上次的頁缺失的時間.

如果發生頁缺失之間的時間差是"大"的, 之后減少工作集的時間窗口(也就是里面的): 如果?(是設置的一個閾值), 之后從內存中移除所有在時間內沒有被引用的頁.

如果發生頁缺失之間的時間差是"小"的, 之后增加工作集: 如果, 之后增加缺失頁到工作集中.

3.2.3 實例

• 如果, 從工作集中移除沒有在被引用的頁面.?
• 如果, 僅增加缺失頁到工作集中.

1. 假設有一個應用程序, 操作系統給其分配了五個物理頁幀A, B, C, D, E, 該應用程序對于邏輯頁的訪問序列是e d a c c d b c e c e a d, 時間差閾值為2, 如圖:

2. 前四次訪問, 都會產生中斷, 所以時間差都是1, 比閾值2小, 所有都會把頁面添加到工作集中:

?3. 訪問4和5, 因為c d都在工作集中, 所以不會產生中斷:

4. 當訪問6過來時, 此時b不在工作集中, 所以會產生中斷, 先把b放入工作集并找到物理頁面與其映射. 此時距離上次中斷的時間差為3, ?大于時間差閾值2, 所以就會把上次中斷到這次中斷之間工作集中未訪問的頁面踢出工作集(也就是a e被踢出, 其占用的常駐集中的A E也會被釋放出來):

5. 當訪問7過來時,??c在工作集中, 所以不會產生中斷:

6. 當訪問8過來時, e不在工作集, 會產生中斷, 此時中斷時間差為2, 不大于時間差閾值2, 所以直接把e添加進工作集:?

7. 當訪問9, 10過來時, c, e在工作集, 不會產生中斷:?

8. 當訪問11過來時, a不在工作集, 產生中斷, 此時距離上次中斷時間為3, 大于時間差閾值, 就會把工作集中在兩次中斷間未被引用的頁面清出:?

9. 當訪問12過來時, d不在工作集, 產生中斷, 此時距離上次中斷時間為1, 小于時間差閾值, 直接把d加入工作集:

總結

以上是生活随笔為你收集整理的操作系统中的全局页面置换算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。