OS.StudyLog.Ch6.Page replacement algorithm.頁面置換算法
- 全局頁面置換算法
-
- 工作集和常駐集
- 工作集頁置換算法
- 缺頁率頁面置換算法
- 抖動問題
局部頁面置換算法都針對一個程式/程序來進行操作的，然而OS可以同時執行多個程式，如果每一個程式都采取一個固定的局部頁面置換算法會帶來一些問題，是以我們引入全局頁面置換算法。
程式的通路特征是可變的，可能一開始需要的記憶體比較多，中間可能需要的很少，結束時又很多，也就說對實體記憶體的需求是可變的。而前面的局部頁面置換算法都有一個大前提：配置設定的實體頁幀是固定的。
由于OS可以同時跑多個程式，那麼這時候如果給每一個程式配置設定一個固定的實體頁幀，就限制了程式的靈活性。我們想要根據程式進行的不同階段，動态配置設定給其不同的實體記憶體大小。這就是我們全局頁面置換算法要考慮到的。
接下來要介紹的所有算法，都基于一個大前提。
如果一個算法要有效，那麼我們需要這個程式具有局部性。程式局部性原理越好，LRU/clock算法就會産生更少的缺頁次數。是以我們想要表現和分析局部性——工作集
一個程序一個時間段内的邏輯頁面的集合。t是目前時刻，△是t時刻開始後的一段時間。
W
（
t
,
△
）
W（t,△）
W（t,△）是t時刻開始△時間段内的所有通路到的頁面集合。t是一直變的，在這種情況下工作集視窗一直在滑動，通路頁的集合也會不斷變化。
∣
|W（t,△）|
∣W（t,△）∣是這個集合的大小。
注意：工作集視窗不包含目前時刻所對應的頁面
起始時間是t1,△是從過去到現在一固定長度。表示了程式在不同運作階段對記憶體通路特點的展現，t2的工作集的局部性就很好，t1相對于t2的局部性稍差，但是仍然具有一定的局部性。
下圖便于了解：
工作集在執行過程中會随着程式執行的特點而變化。可能一開始通路的頁不具有局部性，但是到通路到一定區域他的工作集大小也會比較穩定。
常駐是常駐記憶體的意思，常駐集是目前時刻正在運作的程式駐留在記憶體中的頁面集合。如果說工作集展現了運作中程式在運作過程中在對頁面通路的屬性，是程式本身的固有屬性；常駐集是OS和計算機系統給應用程式配置設定的實體頁-空間的大小，以及采取的頁面置換算法來決定到底将哪些頁面放入記憶體。工作集表示要通路的頁面有哪些，這些頁面有可能不在記憶體中，這是和常駐集的最大不同。我們希望工作集的頁都在常駐集裡，一旦工作集中某些頁不在常駐集，就會産生缺頁中斷，是以我們希望這兩個集合盡量是重疊的，這樣會使得缺頁率較小。OS在程式運作時可以配置設定的常駐集大小是不定的，配置設定的實體頁不是越多越好，可能當實體頁多到一定程度時，意義不大了，此時我們想将多餘的頁配置設定給其他程式，動态調整實體頁大小使得整體的缺頁率較低。隻要整體缺頁次數少，則整體系統性能就會高。
工作集視窗裡的頁代表目前這段時間内被通路的頁，如果其中的頁需要替換時，需要替換不在工作集中的頁；随着程式執行，視窗在挪動，評議過程中某個頁不再在國工作集視窗内，則這個頁也需要丢掉，并不是一定要等到缺頁時再置換出去。
看一個例子：【個人感覺用連結清單了解更加容易】
工作集視窗τ=4
| 階段 | 工作集視窗内容 |
|---|---|
| | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| 10 | |
它和前面的局部頁面替換算法相比，最大的變化是取決于工作集視窗。是以超出視窗的老頁被換出，保證實體記憶體中始終有足夠多的頁存在，給其他運作的程式提供更多的記憶體，進而減少頁面置換次數。從整個系統的層面上減少缺頁率。
| 過程 | |
|---|---|
| 預設階段下，工作集空間内包含ade三個頁面 | |
| 缺頁發生，以為沒有上一次缺頁是以忽略。加入新頁c。 | |
| 2~3 | t c − t l ≤ T t_c-t_l\leq T tc−tl≤T且沒有缺頁，工作集不變 |
| ≥ t_c-t_l\geq T tc−tl≥T，清除在該段時間内未被通路的所有頁，在1~3階段通路了c和d，是以保留cd且因為缺頁加入b，則此時工作集内的頁為bcd | |
| 同2~3階段 | |
| tc−tl≤T且缺頁，加入需要的頁e。此時工作集視窗内的頁是bcde | |
| 7~8 | 同5 |
| 保留與上次缺頁（階段6）之間通路過的是頁ce，且加入目前需要通路的頁a | |
| tc−tl≤T且缺頁，加入需要的頁d。此時工作集視窗内的頁是aced |