進程的狀態

進程的基本狀態

• 就緒：進程已獲得除處理機以外的所需資源，等待分配處理機資源
• 執行：進程正在占用處理機資源執行
• 阻塞：進程等待某種條件，在條件滿足之前無法執行。例如發起I/O系統調用，等待I/O中斷發生

掛起

掛起指將暫不執行的進程換出到外存，節省記憶體空間。
與阻塞相比都是進程暫停執行的狀態，但：

• 阻塞表示進程正在等待一個事件的發生，阻塞狀態下收到信號會切換為就緒狀態
• 掛起表示進程被換出到外存，掛起狀態下被激活會被載入到記憶體，切換為非掛起狀態

掛起狀態進程按照是否阻塞分為：

• 掛起就緒狀態：進程在外存中，但只要被載入記憶體就可執行
• 掛起阻塞狀態：進程在外存中等待一個事件，即使被載入記憶體(激活)也無法執行
  

睡眠

Linux將進程的阻塞狀態進一步細分為：

• 暫停：不需要等待資源
• 淺睡眠：需要等待資源且睡眠狀態能被信號喚醒
• 深睡眠：需要等待資源且睡眠狀態不能被信號喚醒
  

進程調度演算法

分類

• 按照CPU分配方式：非搶占式，搶占式
• 按照系統分時方式：批處理系統，交互系統，實時系統和多處理機調度

進程饑餓

• 指某個進程無限等待，無法被調度

批處理系統調度演算法

調度演算法的目標：

• 吞吐量(每小時最大作業數)
• 周轉時間(每作業從提交到完成時間的統計平均時間)
• CPU利用率(最好令CPU始終忙碌)

1.先來先服務演算法(FCFS)

• 依據進程進入就緒狀態的先後順序排列，非搶占式 不公平
• 優點：易於理解，便於實現，只需一個就緒隊列
• 缺點：平均等待時間波動大(例如短進程排在長進程後)；I/O與CPU資源利用率低(CPU密集型進程會導致I/O設備閑置時，I/O密集型進程也等待)

2.最短進程優先演算法(SPN或SJF)

• 預知就緒隊列中執行時間最短進程占用CPU進入運行狀態，非搶占式 不公平
• 優點：相對於FCFS提高了平均周轉時間
• 缺點：可能導致饑餓；對長作業不公平；需要預知未來(預估下一個CPU計算的持續時間：詢問用戶或用歷史的執行時間來預估未來的執行時間)

3.最短剩餘時間優先演算法(SRT或SRTN)

• 最短進程優先的搶占式版本，若新進程比正在執行的進程剩餘時間短，則它優先執行， 搶占式 不公平
• 優缺點同SPN

4.最高響應比優先演算法(HRRN)

• 響應比：作業等待時間/作業運行所需時間；響應比大的進程優先，非搶占式 不公平
• 優先：同時考慮了等待時間和執行時間，既優先考慮短作業(進程)，也防止長作業(進程)無限等待的饑餓

交互系統(分時系統)調度演算法

1.時間片輪轉演算法(RR)

• 將所有就緒進程排成一個隊列，按照時間片輪轉調度，用完時間片的進程排到隊列末尾，搶占式 公平
• 優點：沒有饑餓問題
• 缺點：當時間片太小時，產生大量的上下文切換，吞吐量低；當時間片太長時，等待時間過長，不能保證實時性，極限情況退化成FCFS

2.多級隊列調度演算法(MQ)

• 優先順序高的進程先運行，同優先順序的進程輪轉。當高優先順序隊列中沒有進程後，再調度下一級隊列。
• 將就緒隊列劃分為多個獨立的子隊列，且每個隊列擁有自己的調度策略(上述)；隊列間的調度採用固定的優先順序：先處理前臺隊列，後處理後臺隊列。每個隊列都得到一個確定的能夠調度其進程的CPU總時間
• 缺點：可能導致饑餓問題

3.多級反饋隊列演算法(MLFQ)

• 進程可在不同隊列間移動的多級隊列演算法(MQ)；優先順序高的隊列先執行，優先順序越高，時間片越短；若一個進程在當前隊列規定時間片內無法執行完畢，則移動到下一個隊列的隊尾
• 特征：CPU密集型進程的優先順序下降很快；I/O密集型進程停留在高優先順序
• 缺點：可能導致饑餓問題：不斷有新更高優先順序的進程加入

4.公平共用調度(FSS)

• 保證不重要的組無法壟斷資源：未使用的資源按比例分配；沒有達到資源使用率目標的組獲得更高的優先順序 公平

5.彩票法

• 向進程提供各種系統資源的彩票。調度時隨機抽取彩票，擁有該彩票的進程得到資源
• 可給重要進程更多的彩票；協作進程可能交換彩票

實時系統的調度演算法

目標：滿足任務的截止時間。即若有一個任務需要執行，實時系統會馬上執行該任務，不會有較長的延時。

1.速率單調調度演算法(RM)

• 通過周期安排優先順序，周期越短優先順序越高
• 執行周期最短的任務

2.最早截止時間優先演算法(EDF)

• 截止時間越早優先順序越高
• 執行截止時間最早的任務

多處理機的調度

特征：多個處理機組成一個多處理機系統；處理機間可負載共用

對稱多處理機(SMP)調度

• 截止時間越早優先順序越高，每個處理器運行自己的調度程式
• 調度程式對共用資源的訪問需要進行同步

分為靜態進程分配和動態進程分配(負載均衡)：

• 靜態進程分配：進程從開始到結束都被分配到一個固定的處理機上執行；每個處理機有自己的就緒隊列；優點：調度開銷小；缺點：但是各處理機可能忙閑不均
• 動態進程分配(負載均衡)：進程在執行中可分配到任意空閑處理機執行；所有處理機共用一個公共的就緒隊列；優點：各處理機的負載是均衡的；缺點：調度開銷大

優先順序反置

• 操作系統出現高優先順序進程長時間等待低優先順序進程所占用資源的現象
• 基於優先順序的可搶占調度演算法存在優先順序反置

解決方法：

1. 優先順序繼承：占用資源的低優先順序進程繼承申請資源的高優先順序進程的優先順序；

• 這種情況只在占有資源的低優先順序進程被阻塞時，才提高占有資源進程的優先順序

2. 優先順序天花板協議(PCP)：占用資源進程的優先順序和所有可能申請該資源的進程的最高優先順序相同；

• 不管是否發生等待，都提升占用資源進程的優先順序
• 優先順序高於系統中所有被鎖定的資源的優先順序上限，任務執行臨界區時就不會阻塞