目錄
一、緩存淘汰算法
1.LFU（Least Frequently Used）最近最不常用算法
2.LRU（Least Recently User）最近最少使用算法
3.FIFO（First in first out）先進先出算法
二、進程的狀態和轉換
1.最基本的三種狀態
2.三種狀態的切換（重點）
3.新增的進程狀態（五態）
?4.新增狀態（七態）
5.掛起進程具有的特征
一、緩存淘汰算法
緩存算法用于決定緩存系統中哪些數據應該被刪去。
1.LFU（Least Frequently Used）最近最不常用算法
主要思想：把使用頻率最小的數據置換出去。
主要步驟：
- 在緩存中查找需要的數據，如果緩存中有則將訪問的數據從隊列中取出，并將數據對應的頻率計數加1，然后將其放到頻率相同的數據隊列的頭部。
- 如果緩存中沒有將需要訪問的數據從磁盤中取出，加入到緩存隊列的尾部，記頻率為1。
- 如果緩存空間已滿，淘汰尾部使用頻率最低的數據。
舉例：
ABCD為數據，括號內是被使用的次數
初始狀態：
訪問D后（訪問次數加一，并排在相同次數最前）：
新增E后：
緩存滿時（淘汰次數最少的E）：
存在的問題：
對于A而言，可能他在最開始某段時間集中被頻繁地訪問。但可能之后不會再被訪問了，但由于他的次數遠遠大于其他數據，這使得它不會被輕易地淘汰。
對于E而言，可能他才剛剛被訪問了第一次，后面可能會被頻繁的訪問。但由于他的次數只有一次，每次緩存滿時都會先被淘汰。
2.LRU（Least Recently User）最近最少使用算法
主要思想：把最長時間未被訪問到的數據置換出去。
主要步驟：
- 在緩存中查找客戶端需要訪問的數據。如果緩存中有，則將訪問的數據從隊列中取出，重新加入到緩存隊列的頭部。
- 如果緩存中沒有，將需要訪問的數據從磁盤中取出，加入到緩存隊列的尾部；
- 如果此時緩存滿了，淘汰隊列尾部的數據，然后再在隊列頭部加入新數據。
?舉例：
初始狀態：
?訪問D后：
?新加E時緩存滿了：
?
存在的問題：
當客戶端需要大量訪問歷史數據時，這時歷史數據被提到隊頭，其他數據可能會因為緩存滿而舍棄。這時其他客戶端想要訪問其他數據時又會重新到磁盤訪問，效率大大降低。
3.FIFO（First in first out）先進先出算法
主要思想：最先進入的數據最先被淘汰
主要步驟：
- ?當緩存中有訪問的數據時，直接訪問不做任何處理。
- 緩存中沒有時，讀取磁盤將數據寫入隊列隊頭。
- 緩存滿時直接淘汰最早進入的數據。
舉例：
初始狀態：
?訪問C時（依然不做任何操作）：
?新加E時緩存滿：
?存在的問題：
可能最先進入的數據是經常被訪問的界面，這樣操作會降低效率。
二、進程的狀態和轉換
1.最基本的三種狀態
①運行態：進程當前占有CPU，并在CPU上運行。
②就緒態：一個進程已經具備運行條件，但沒有分配CPU，暫時不能運行。當調度給該進程CPU時，立即可以運行。
③等待態：當前進程因等待某事件的發生而暫時不能運行的狀態。即使這時CPU空閑也不能運行。
2.三種狀態的切換（重點）
就緒——>運行：在調度程序時，一旦調度到這個進程時，就發生這件事。
運行——>就緒：運行進程用完了CPU分給他的時間片（分時操作系統分配給每個運行的進程微觀上的一段時間）或CPU處理機被搶占。
運行——>等待：這個進程對資源的訪問得不到滿足 或者初始化I/O操作等待結果 或者等待某一進程提供輸入
等待——>就緒：等待的事情得到滿足時執行。
3.新增的進程狀態（五態）
新建態：因為就緒態也是需要一個過程才能達到這樣一個狀態，就緒態之前的狀態就為新建態。
終止態：最后對進程整個生命周期進行一個收尾。
?4.新增狀態（七態）
等待態→掛起等待態：操作系統根據當前資源狀況和性能要求，可以決定把等待態進程對換出去成為掛起等待態。
掛起等待態→掛起就緒態：引起進程等待的事件發生之后，相應的掛起等待態進程將轉換為掛起就緒態掛起就緒態→就緒態：當內存中沒有就緒態進程，或者掛起就緒態進程具有比就緒態進程更高的優先級，系統將把掛起就緒態進程轉換成就緒態。
就緒態→掛起就緒態：操作系統根據當前資源狀況和性能要求，也可以決定把就緒態進程對換出去成為掛起就緒態。
掛起等待態→等待態：當一個進程等待一個事件時，原則上不需要把它調入內存。但是在下面一種情況下，這一狀態變化是可能的。當一個進程退出后，主存已經有了一大塊自由空間,而某個掛起等待態進程具有較高的優先級并且操作系統已經得知導致它阻塞的事件即將結束，此時便發生了這一狀態變化。
運行態→掛起就緒態：當一個具有較高優先級的掛起等待態進程的等待事件結束后，它需要搶占 CPU，而此時主存空間不夠，從而可能導致正在運行的進程轉化為掛起就緒態。另外處于運行態的進程也可以自己掛起自己。
新建態→掛起就緒態：考慮到系統當前資源狀況和性能要求，可以決定新建的進程將被對換出去成為掛起就緒態。
掛起進程等同于不在內存中的進程，因此掛起進程將不參與低級調度直到它們被調換進內存。
5.掛起進程具有的特征
- 該進程不能立即被執行
- 掛起進程可能會等待一個事件，但所等待的事件是獨立于掛起條件的，事件結束并不能導致進程具備執行條件。 （等待事件結束后進程變為掛起就緒態）
- 進程進入掛起狀態是由于操作系統、父進程或進程本身阻止它的運行。
- 結束進程掛起狀態的命令只能通過操作系統或父進程發出。
)
