前言

什么是調度算法

在操作系統中調度是指一種資源分配的過程，因而調度算法是指：根據系統的資源分配策略所規定的資源分配算法。對于不同的的系統和系統目標，通常采用不同的調度算法

為什么需要調度算法

計算機系統中的CPU資源非常寶貴，為了充分利用其資源，讓多線程或者多進程系統能夠多快好省地完成我們讓它做的各種任務，就需要指定一定的規則去使用CPU。為此，可在內存中可存放數目遠大于計算機系統內CPU個數的進程，讓這些進程在操作系統的進程調度器的調度下，能夠讓進程高效（高的吞吐量–throughput）、及時（低延遲–latency）、公平（fairness）地使用CPU。為此調度器可設計不同的調度算法來選擇進程，這體現了進程調度的策略，同時還需并進一步通過進程的上下文切換（context switch）來完成進程切換，這體現了進程調度的機制。

我們需要何時調度（調度的時機）、是否能夠在內核執行的任意位置進行調度（調度的方式）、如果完成進程切換（上下文切換）、如果選擇“合適”的進程執行（調度策略/調度算法）、如果評價選擇的合理性（進程調度的指標）。

調度算法要達成的目標

周轉時間短：從作業提交給系統開始，到作業完成為止的這段時間的間隔要盡量小。

響應時間快：從用戶提交一個請求開始直至系統首次產生響應時間為止的一段時間要盡量小。

截止時間的保證：某個任務必須開始執行的最遲時間，或必須完成的最遲時間。截止時間是評價實時系統的重要指標。

系統吞吐量高：單位時間內完成的作業數量。系統的吞吐量是評價系統性能的重要標準之一。調度算法影響系統的吞吐量

CPU利用率高：CPU 是計算機系統中影響時間性能的最重要的硬件資源。在多任務系統，進程調度算法對 CPU 的利用率有很大影響。因此，在選擇和設計進程調度算法時應該考慮使 CPU 利用率盡可能高。

調度算法的類別

主要分為以下幾類：

• 先來先服務調度算法
• 短進程優先調度算法
• 優先權調度算法
• 時間片輪轉調度算法
• 多級隊列調度**、**多級反饋隊列調度

進程調度的原理

這里需要注意，存在兩種進程搶占處理器的調度方式：

• 可搶占式（可剝奪式，preemptive)：就緒隊列中一旦有某進程的優先級高于當前正在執行的進程的優先級時，操作系統便立即進行進程調度，完成進程切換。

• 不可搶占式（不可剝奪式non_preemptive）：即使在就緒隊列存在有某進程優先級高于當前正在執行的進程的優先級時，當前進程仍將占用處理機執行，直到該進程自己進入阻塞狀態，或時間片用完，或在執行完系統調用后準備返回用戶進程前的時刻，才重新發生調度讓出處理機。

常見的調度算法

FCFS 先來先服務優先調度算法（FCFS, First Come First Serve）

先來先服務（FCFS）調度算法是一種最簡單的調度算法，該算法既可用于作業調度，
也可用于進程調度。FCFS算法比較有利于長作業（進程），而不利于短作業（進程）。由此可知，本算法適合于CPU繁忙型作業，
而不利于I/O繁忙型的作業（進程）。這里和python的全局解釋器進程鎖的用法一樣，適合I/O密集型。

短作業（進程）優先調度算法（SJF, Shortest Job First）

短作業（進程）優先調度算法是指對短作業或短進程優先調度的算法，該算法既可用于作業調度，
也可用于進程調度。但其對長作業不利；不能保證緊迫性作業（進程）被及時處理；作業的長短只是被估算出來的。

最高優先權調度算法（Priority Scheduling）

為了照顧緊迫性作業，使之進入系統后便獲得優先處理，引入了最高優先權優先（FPF）調度算法。
此算法常被用在批處理系統中，作為作業調度算法，也作為多種操作系統中的進程調度，還可以用于實時系統中。當其用于作業調度，
將后備隊列中若干個優先權最高的作業裝入內存。當其用于進程調度時，把處理機分配給就緒隊列中優先權最高的進程，此時， 又可以進一步把該算法分成以下兩種：
(1)非搶占式優先權算法;
(2)搶占式優先權調度算法（高性能計算機操作系統）;

對于最高優先權優先調度算法，其核心在于：它是使用靜態優先權還是動態優先權， 以及如何確定進程的優先權。
動態優先權：高響應比優先調度算法為了彌補短作業優先算法的不足，我們引入動態優先權，使作業的優先等級隨著等待時間的增加而以速率a提高。
該優先權變化規律可描述為：優先權=（等待時間+要求服務時間）/要求服務時間；即 =（響應時間）/要求服務時間。

時間片輪轉法（RR, Round Robin）

時間片輪轉法一般用于進程調度，每次調度，把CPU分配隊首進程，并令其執行一個時間片。
當執行的時間片用完時，由一個記時器發出一個時鐘中斷請求，該進程被停止，并被送往就緒隊列末尾；依次循環。

多級反饋隊列調度算法(multilevel feedback queue scheduling)

多級反饋隊列調度算法，不必事先知道各種進程所需要執行的時間，它是目前被公認的一種較好的進程調度算法。 其實施過程如下：

設置多個就緒隊列，并為各個隊列賦予不同的優先級。在優先權越高的隊列中， 為每個進程所規定的執行時間片就越小。

當一個新進程進入內存后，首先放入第一隊列的末尾，按FCFS原則排隊等候調度。
如果他能在一個時間片中完成，便可撤離；如果未完成，就轉入第二隊列的末尾，再同樣等待調度……
如此下去，當一個長作業（進程）從第一隊列依次將到第n隊列（最后隊列）后，便按第n隊列時間片輪轉運行。

僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第1到第（ i-1 ）隊列空時，
才會調度第i隊列中的進程運行，并執行相應的時間片輪轉。

如果處理機正在處理第i隊列中某進程，又有新進程進入優先權較高的隊列，
則此新隊列搶占正在運行的處理機，并把正在運行的進程放在第i隊列的隊尾。

總結

以上是生活随笔為你收集整理的操作系统CPU调度算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。