先來先服務(FCFS)調度演算法是一種最簡單的調度演算法，該演算法既可用於作業調度，也可用於進程調度。 當在作業調度中採用該演算法時，每次調度都是從後備作業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入記憶體，為它們分配資源、創建進程，然後放入就緒隊列 ...
一、進程調度的功能與時機
進程調度：進程調度的功能由操作系統的進程調度程式完成
具體任務：按照某種策略和演算法從就緒態進程中為當前空閑的CPU選擇在其上運行的新進程。
進程調度的時機：進程正常或異常結束、進程阻塞、有更高優先順序進程到來、時間⽚用完時都會導致進程調度。
二、進程調度演算法
什麼樣的演算法是好的演算法？
- 周轉時間短：作業從提交給系統開始，到作業完成，花費時間短
- 響應時間快：從用戶提交作業開始，到系統開始響應，花費時間短
- 截止時間的保證：保證作業在“開始截止時間”前開始，在“完成截止時間”前完成
- 系統吞吐量高：系統在單位時間內完成的作業量多
- 處理機利用率好：CPU的利用率儘可能高
進程調度演算法：
先來先服務調度演算法（FCFS） ：從就緒隊列的隊首選擇最先到達就緒隊列的進程，為該進程分配CPU
周轉時間=進程的周轉時間
系統平均周轉時間=所有進程的周轉時間之和，然後除以進程個數
帶全平均周轉時間w=每個進程的周轉時間除以該進程的服務時間，然後相加，最後除以進程個數
缺點：服務時間段的進程等待時間較長，整個周轉時間較長。
短進程優先調度演算法（SPF）：從就緒隊列中選擇估計運行時間最短的進程，為該進程分配CPU
優點 ：與FCFS演算法相比，短進程優先演算法能有效降低進程的平均等待時間，提高系統吞吐量
缺點： 對長進程不利；不能保證緊迫進程的處理；進程長短由用戶估計，不一定准確。
優先權調度演算法：統將CPU分配給就緒隊列中優先權最高的進程
- 非搶占式：運行期間，有更高優先權的進程到來，也不能剝奪CPU
- 搶占式：運行期間，有更高優先權的進程到來，就可以搶占CPU
優先權類型
- 靜態優先權：創建時確定，運行期間保持不變
- 動態優先權：創建時確定，隨著進程推進或等待時間增加而改變
該演算法存在的問題：無窮阻塞(饑餓問題)；解決的方案（老化技術）：增加等待時間很長的進程的優先權
時間片輪轉調度演算法（RR）：
系統將所有就緒進程按先來先服務的原則，排成一個隊列，每次調度時把CPU分給隊首進程，並令其執行一個時間片。當時間片用完時，調度程式終止當前進程的執行，並將它送到就緒隊列的隊尾。
1、時間片⼤小確定時
T=Nq T:系統響應時間 N:進程數量 q:時間片
- 系統對響應時間的要求：響應時間要求越短，時間片越小
- 就緒隊列中進程的數目：進程數量越多，時間片越小
- 系統的處理能力：處理能力越好，時間片越小
【例】進程A、B、C、D需要運行的時間分別為20ms、10 ms、15 ms、5 ms，均在0時刻到達。到達的先後次序為A、B、C、D。如果時間片分別為1 ms和5ms，計算各個進程的帶權周轉時間和平均帶權周轉時間。
多級隊列調度演算法：將就緒隊列分成多個獨⽴隊列，每個隊列有自己的調度演算法
優先順序高隊列 p1 、p2、 p3 、p4
優先順序低隊列 p5、 p6 、p7
多級反饋隊列調度演算法：建立多個優先權不同的就緒隊列，每個隊列有大小不同的時間片
隊列優先權越高，時間片越短
隊列優先權越低，時間片越長
三、實時系統中的調度
實現實時調度的基本條件：
1、提供必要的調度信息：就緒時間 、開始截止時間 、完成截止時間、處理時間、 資源要求 、優先順序
2、系統處理能力強：假定系統中有m個周期性的實時進程，它們的處理時間可表示為Ci，周期時間表示為Pi，則在單處理機情況下，必須滿足如下公式的限制條件：
3、採用搶占式調度機制(使用最廣泛的方式)
4、具有快速切換機制： 對外部中斷的快速響應能力 快速的進程切換能力
常用的實時調度演算法：
1、最早截止時間優先演算法EDF（淘寶&京東）：開始截止時間越早，進程優先順序越高，越優先獲得CPU
2、最低鬆弛度優先演算法LLF：根據實時進程的緊迫程度來進行調度的演算法
四、進程切換
進程切換的含義：當前正在執行的進程成為被替換進程，讓出其所使⽤的CPU，以運行被進程調度程式選中的新進程。
進程切換的步驟：
- 保存包括程式計數器和其他寄存器在內的CPU上下文環境
- 更新被替換進程的進程式控制制塊
- 修改進程狀態，把執行態改為就緒態或阻塞態
- 將被替換進程的進程式控制制塊移到就緒隊列或阻塞隊列
- 執行通過進程調度程式選擇的新進程，並更新該進程的進程式控制制塊
- 更新記憶體管理的數據結構
- 恢復被調度程式選中的進程的硬體上下文
五、 多處理器調度
1、多處理器系統的類型：
- 緊密耦合 共用主存儲器和I/O設備
- 鬆弛耦合 有各自的存儲器和I/O設備
- 對稱 處理單元功能和結構相同
- 非對稱 有多種類型的處理單元 一個主處理器，多個從處理器
2、多處理器系統的進程分配方式:
對稱系統分配方式:
靜態分配：就緒隊列的進程只能在與就緒隊列對應的處理器上運行。
動態分配：進程隨機地被分配到當時處於空閑狀態的某一處理器上執行。
⾮對稱系統分配方式：主-從式分配方式（大多採用）
3、進程（線程）的調度方式
⾃調度 最常用最簡單的方式：採⽤自調度的系統中設置有一個公共的就緒隊列，任何一個空閑的處理器都可以自行從該就緒隊列中選取一個進程或者一個線程運行。
成組調度
專⽤處理器分配
六、 死鎖
死鎖的定義：由於多個進程競爭共用資源而引起的進程不能向前推進的僵死狀態稱為死鎖
產生死鎖的原因：競爭共用資源且分配資源的順序不當
1、產生死鎖的必要條件
- 互斥條件：只有一個資源，要麼你用，要麼我用
- 請求和保持條件：必須保持自己的條件，不能相讓
- 不剝奪條件：不能搶占他人資源
- 環路等待條件：
2、處理死鎖的基本方法
- 死鎖的預防 通過破壞死鎖的產生條件來保證不發生死鎖
- 死鎖的檢測 檢測當前系統是否出現死鎖
- 死鎖的避免 通過演算法合理分配資源來保證不發生死鎖
- 死鎖的解除 檢測到系統有死鎖後進行解除
處理死鎖的基本方法有：預防死鎖、避免死鎖、檢測並解除死鎖和忽略死鎖問題
###############################處理死鎖的基本方法詳解###########################
1、死鎖的預防
2、死鎖的避免
例如：
銀行家演算法：一個進程提出資源請求後，系統先進行資源的試分配，分配後檢測系統是否安全。銀行家演算法的實質是避免系統進入不安全狀態。
例如：5個進程p0、p1、p2、p3、p4 3種類型的資源A、B、C
3、死鎖的檢測
何時調用檢測演算法
- 死鎖可能發生的頻率 ，發生頻率很高時需要檢測
- 死鎖發生時受影響的進程數量，受影響的進程數量較多
資源分配圖
系統初始化時分配給p1兩個資源，p1又主動請求一個資源
系統初始化時分配給p2兩個資源，p2又主動請求一個資源
死鎖定理
用於檢測系統所處的資源分配狀態是否為死鎖狀態
S為死鎖狀態的充分條件是當且僅當S狀態的資源分配圖是不可完全簡化的，即資源分配圖是不是可以把申請資源的線全部消掉。
4、死鎖的解除
解除途徑
- 進程終止 終止所有死鎖進程；一次只終止一個處於死鎖的進程，直到死鎖解除
- 資源搶占 逐步從進程中搶占資源給其他進程使用，直到死鎖被打破為止
