行程的狀態
行程的基本狀態
- 就緒：行程已獲得除處理機以外的所需資源，等待分配處理機資源
- 執行：行程正在占用處理機資源執行
- 阻塞：行程等待某種條件，在條件滿足之前無法執行，例如發起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)調度
- 截止時間越早優先級越高，每個處理器運行自己的調度程式
- 調度程式對共享資源的訪問需要進行同步
分為靜態行程分配和動態行程分配(負載均衡)：
- 靜態行程分配：行程從開始到結束都被分配到一個固定的處理機上執行；每個處理機有自己的就緒佇列；優點：調度開銷小；缺點：但是各處理機可能忙閑不均
- 動態行程分配(負載均衡)：行程在執行中可分配到任意空閑處理機執行；所有處理機共享一個公共的就緒佇列；優點：各處理機的負載是均衡的；缺點：調度開銷大
優先級反置
- 作業系統出現高優先級行程長時間等待低優先級行程所占用資源的現象
- 基于優先級的可搶占調度演算法存在優先級反置
解決方法：
- 優先級繼承：占用資源的低優先級行程繼承申請資源的高優先級行程的優先級；
- 這種情況只在占有資源的低優先級行程被阻塞時，才提高占有資源行程的優先級
- 優先級天花板協議(PCP)：占用資源行程的優先級和所有可能申請該資源的行程的最高優先級相同；
- 不管是否發生等待，都提升占用資源行程的優先級
- 優先級高于系統中所有被鎖定的資源的優先級上限，任務執行臨界區時就不會阻塞
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/523834.html
標籤：Linux
上一篇：復制鏈接，單擊一個按鈕-seleniumpython
下一篇：Docker