摘要
程序排程
排程原則
排程演算法
作業系統-程序排程
執行緒排程
程序排程是指在程序之間選擇一個程序將其送上CPU執行，通常這個是由
作業系統中的排程程式執行
。
排程原則
如果執行的程式發生I/O事件請求，CPU使用率會降低，因為此時程序在等待硬碟資料的返回。所以為了提高CPU執行效率，在由於I/O導致CPU空閒時，排程程式需要從就緒佇列中選擇一個程序執行。
有的程式執行時間較長，一直佔有CPU，系統吞吐量（單位時間內CPU完成的程序數量）降低。所以為了提高系統吞吐量，排程程式需要權衡長任務和短任務的完成數量。
程序的週轉時間包含執行時間和阻塞等待時間。程序的週轉時間越小越好，排程程式需要保證週轉時間儘可能的小
排程程式需要讓就緒佇列中的等待時間儘可能的短
對於互動式比較強的應用，比如鍵盤、滑鼠，排程程式要考慮程式的響應時間儘可能快。
綜上所述，排程程式主要從以下幾個系統引數來考慮：
CPU利用率：排程程式儘可能的讓CPU繁忙，提高排程程式的利用率
系統吞吐量：吞吐量是單位時間內CPU完成的程序數，長作業會降低吞吐量，短作業提高吞吐量
週轉時間：週轉時間是執行時間和阻塞時間的總和，一個程序的排程時間越小越好
等待時間：程序在就緒佇列中等待時間儘可能的短
響應時間：在互動式較強的系統，排程演算法需要儘可能的降低響應時間
排程演算法
如果硬體提供某個頻率的時鐘中斷，根據如何處理時鐘中斷排程演算法大致分為兩類：
非搶佔式排程演算法：該演算法挑選一個程序，讓該程序執行直到被阻塞或者程序退出，才會呼叫另外一個程序，不會理會時鐘中斷
搶佔式排程演算法：該演算法挑選一個程序，讓該程序在某個時間段內執行，如果執行超出該時間段，則會把它掛起，接著排程程式從就緒佇列中挑選另一個程序執行。這種搶佔式排程需要在時間段結束時發生時鐘中斷，以便把CPU控制權返回給排程程式進行排程。這就是常說的
時間片機制。
先來先服務（FCFS）演算法
先來後到，每次從就緒佇列中選擇一個程序執行，直到程序阻塞或退出。FCFS適用於CPU繁忙性作業的系統，不適用於I/O繁忙性。
最短作業優先排程（SJF）演算法
優先選擇執行時間最短的程序來執行，有利於提高系統的吞吐量。
SJF演算法不利於長作業，如果就緒佇列中短作業過多，會導致長作業具有較高的延遲。
高響應比優先（HRRN）排程演算法
主要是權衡了短作業和長作業，每次進行排程時，先計算響應比，然後把響應比最高的程序執行。
響應比=（等待時間+要求服務時間）/ 要求服務時間
如果程序等待時間相同，要求服務時間越短，響應比越高，這樣短作業容易被執行
如果程序要求服務時間相同，等待時間越長，響應比越高，這樣長度作業在等待時間過長時也會被選中執行
時間片輪轉（RR）排程演算法
每一個程序被分給一個時間段，稱之為時間片，即允許該程序在該時間段中執行。
如果時間片用完，程序還在執行，程序會將CPU釋放，排程程式會把CPU分配給另一個程序執行
如果該程序在時間片結束之前阻塞或結束，CPU也會立即切換
在該演算法中，時間片的長度是一個比較關鍵的點：
如果設定的太短會導致過多的程序上下文切換，降低CPU的效率
如果設定的太長有可能會導致短作業的響應時間變長
一般來說，時間片的設定應為略大於一次互動的響應時間，20ms~50ms是一個折中的值。
最高優先順序（HPF）排程演算法
從就緒佇列中選擇最高優先順序的程序執行。
程序的優先順序分為
靜態優先順序
和
動態優先順序
：
靜態優先順序：建立程序的時候，就已經確定優先順序了，然後整個執行時間優先順序都不會變化
動態優先順序：根據程序的動態變化調整優先順序，如果程序執行時間增加，降低優先順序，如果程序等待時間增加，則升高優先順序
該演算法也有兩種處理高優先順序的方法，非搶佔式和搶佔式：
非搶佔式：當就緒佇列中出現優先順序高的程序，執行完當前程序，再選擇優先順序高的程序
搶佔式：當就緒佇列中出現優先順序高的程序，當前程序掛起，排程優先順序高的程序執行
優先順序低的程序可能一直無法執行
。
多級反饋佇列（MFQ）排程演算法
該演算法是時間片輪轉演算法和最高優先順序演算法的結合。
多級表示有多個佇列，每個佇列優先順序從高到低，同時優先順序越高佇列中時間片也越短
反饋表示如果有新的程序加入高優先順序佇列時，立刻停止當前正在執行的程序，轉而去執行優先順序高的程序
具體的工作流程如下：
設定多個佇列，每個佇列設定不同的優先順序，佇列的優先順序從高到低，且優先順序越高時間片越短
新的程序會被第一級佇列的末尾，按照先來先服務的原則等待被排程，如果在第一優先順序的規定的時間片程序沒有執行完成，則會將他轉入第二佇列的末尾，依次類推，直至完成
當較高優先順序的佇列為空時，才能排程較低優先順序佇列中的程序。如果程序在執行時，有新程序加入較高優先順序的佇列，則停止當前執行的程序並將其移入到原佇列末尾，接著讓較高優先順序的程序執行。
這種演算法對於短作業來說很可能就在第一級佇列就被處理完成，對於長作業來說，雖然有可能因為在第一級佇列無法執行完成而被被移入到第二級佇列執行（等待時間變長），但是獲得時間片也會變長（執行時間變長），所以該演算法很好的兼顧了長短作業，同時有較好的響應時間
。
