當計算機中有多個process處於ready狀態，將CPU分配給哪個進程呢？操作系統中做出這個決策的組件就是調度器，決策的算法叫調度算法，決策過程就是進程調度的過程。
進程調度壹般發生在壹下幾種情況下：
在非搶占式調度中，進程開始執行以後，除非它主動放棄CPU或被block, 否則就能壹直執行。
搶占式調度中，如果在進程執行過程中來了壹個優先級更高的進程，CPU使用權就會被搶走，尤其在時間片調度中即使時間片沒用完也可以被搶占。但搶占也不是隨時可以發生的，如果設計不好可能會發生優先級逆轉或者死鎖問題。
在不同的場景下，為了實現不同的目標，評價調度算法的標準不盡相同。這裏我們介紹壹些常用的標準：
Fairness : 給每個進程公平的CPU使用機會
Balance : 讓系統的各個組件都能得到最大程度的利用率
Throughput 吞吐量 ：單位時間內完成的任務數量
Turnaround Time ：壹般在批處理系統中，壹個批任務從提交到結束的間隔時間
CPU Utilization ：CPU的利用率
Waiting Time ：進程在ready隊列裏等待的時間
Response Time ：壹般在交互式系統中，從用戶提交任務到第壹次得到響應（任務不壹定完成）的間隔時間
Meeting Deadline ：壹般在實時系統中及時處理數據，避免丟失或失效
接下來我們看看在三種不同類型系統中常用的調度算法。
1. FCFS : First Come, First Served
這是壹種非搶占式的先來先服務算法。ready process隊列只有壹個。如果進程執行中被block，進入block隊列，ready之後作為新的進程排到ready隊列的尾部。
優點：容易理解，容易實現
缺點：平均等待時間往往很長，不好平衡CPU密集和IO密集型進程
2. SJF: Shortest Job First
SJF也是非搶占式調度，每次都選擇最短的任務來執行。
3. Shortest Remaining Time Next
是SJF的搶占式版本，只要有新任務到達就重新調度選擇剩余時間最短的任務執行。
SJF和Shortest Remaining Time Next的問題在於壹般情況下很難判斷進程的剩余執行時間是多少。除非這是經常要執行的task，根據對歷史的統計分析能確定壹個執行時間的大致範圍。
1. Round-Robin Scheduling
輪詢調度。 給每個進程相同的時間片，輪流執行。壹般時間片選擇在20-50msec比較合適，太短會導致進程切換浪費時間，太長會導致響應時間延長。
優點：比SJF響應快
缺點：turnaround時間長
2. Priority Scheduling
優先級調度為每個進程分配優先級，高優先級先執行，這也是時間片調度算法。優先級可以靜態分配也可以動態分配，為了避免高優先級的進程壹直占用CPU不放，可以在依次執行結束後降低其優先級。相同優先級的進程之間可以使用其他的調度算法如round-robin，不同隊列可以使用不同的調度算法。
優點：引入了優先級
3. Multiple Queues
為了避免執行時間長的進程頻繁進程切換，可以在不同的優先級隊列之間分配不等長度的時間片。進程執行壹次之後被分配其他擁有更長執行時間的優先級。比如壹個進程需要100個quanta, 第壹次執行時分配1個，下壹次執行分配2個，再下次分配4，8，16，32，64. 比每次都只分配1的純輪詢算法減少了進程調度的次數。
4. Guaranteed Scheduling
前面提到的算法都不保證進程能夠得到的CPU時間，但有些情況下我們需要確保進程使用CPU的機會和時間，比如n個用戶同時登錄，壹般要保證每個用戶都能獲得1/n的CPU，或者我們購買VPN服務，根據不同的用戶級別需要獲得壹定的帶寬保證。這種算法就叫Guaranteed 調度。在實現中，需要追蹤給每個進程分配的CPU，與承諾分配量比較，比值最小的進程會獲得下壹次使用權。
5. Lottery Scheduling
彩票調度算法引入了隨機性，為每個進程發壹張彩票，調度時就像開獎，誰中獎誰獲得資源。優先級更高的進程可以獲得多張彩票以提高中獎機會。
彩票調度有趣的地方在於進程之間可以互贈彩票，比如process 1 pending在process 2上，它可以把自己的彩票都給process2提高它被調度的機會。process2結束以後再把彩票還給process1.
6. Fair-Share Scheduling
下面考慮壹種情況，所有進程並不屬於壹個用戶，這在Linux 系統中非常常見。如果user1有99個process，user2只有1個process，按照前面的算法可能user1能得到99%的CPU，而user2只有1%。為了實現用戶層面的公平性，調度時需要考慮進程屬於哪個user.
實時系統分兩種：
實時系統中，壹般任務時間都比較短，調度器需要使所有進程都在deadline前完成。對於周期性發生的事件，如果事件發生的周期為 , 事件處理時間(需要占用CPU的時間)為 , 只有 時，才是可調度的。
調度算法只能由操作系統實現嗎，關於使用哪種調度算法進程是否有話語權呢？答案是可以的。將機制與策略分離，由操作系統提供多種實現機制，並提供system call由process傳參數給OS指定具體使用哪壹種調度策略。
如果線程是在用戶態實現的，那麽需要兩級調度，OS負責調度process，process負責調度thread。如果線程是在內核態實現的，OS直接調度thread，而不關心它屬於哪個process。