Working Set
Introduction
我們說 thrashing 會發生是因為 process 得到的 frame 不夠裝 locality，working-set strategy 的想法是：OS 持續觀察每個 process 實際在用哪些 pages，然後動態分配剛好足夠的 frames 給它
如果記憶體還有多，就可以啟動新的 process；如果所有 process 的需求超過記憶體總量，就需要執行 Linux Out-Of-Memory (OOM) Killer 釋放記憶體
Strategy
Working-Set Window ()
我們定義 是在時間點 ，從當前 reference string 往前看 次 reference，我們記錄下來的最近曾經存取過的 pages 集合就是這個 process 目前的 working set
的大小
太小 working set 抓不到完整 locality；太大的話會把多個不同的 locality 混在一起，working set 就沒有意義了
定義 是第 個 process 在時間 的 working set size，把所有 process 的 加起來得到總需求 ：
則是系統實際具有的 frame 數量
如果 ，代表所有 process 需要的 frames 加起來超過記憶體所能供應的，thrashing 即將發生。OS 便會執行 OOM Killer 殺掉一個 process 釋放記憶體，讓 降到 以下
Comparison
D-OS-Ch10fdc-comparison-Working-Set_Strategy-PFF
Practice
Problem
理論上，working set 需要精確記錄「最近 次 reference 中存取過哪些 pages」，但這樣做的硬體成本太高
Resolution: Interval Timer + Reference Bits
假設 ，slide 把這個窗口切成兩半，每 5000 個時間單位設一個 timer interrupt。每個 page 在記憶體裡保存 2 個 bit，代表這兩個時間段內有沒有被存取過。
每次 timer interrupt 發生時，把每個 page 的 reference bit（硬體設的）複製到 in-memory 的其中一個 bit，然後把 reference bit 清零。這樣 2 個 in-memory bit 分別記錄了「前 5000 個時間單位有沒有用過」和「更前面 5000 個時間單位有沒有用過」。只要這 2 個 bit 中有任何一個是 1，就代表這個 page 在最近的 時間單位內有被存取過，屬於 working set
這個方法是近似，不是精確的，因為它無法區分「5000 個時間單位內第 1 次存取」和「第 4999 次存取」
上述的意思是在我們的 time interval 中 locality 有可能已經切換了，但還是會被算到目前的 working set 中，所以近似版本的 working set 會高估實際 working set