批處理系統中采用的調度算法

重要指標（吞吐量，周轉時間，CPU利用率，公平平衡）

非搶占式的先來先服務算法（FCFS）：按照進程就緒的先后順序使用CPU

特點：公平，實現簡單，但是長進程后面的短進程需要等待很長時間，不利于用戶體驗。

非搶占式的最短作業優先（SJF）：具有最短完成時間的進程優先執行

最短剩余時間優先（SRTN）：SJF搶占式版本，即當一個新就緒的進程比當前運行進程具有更短完成時間時，系統搶占當前進程，選擇新就緒的進程執行。

短作業優先調度算法特點：改善短作業的周轉時間，但如果源源不斷有短任務到來，可能使長的任務長時間得不到運行，產生饑餓現象。

最高相應比優先算法（HRRN）：是一個綜合算法，調度時，首先計算每個進程的響應比R，之后總是選擇R最高的進程執行。

響應比R=（等待時間+處理時間）/處理時間

交互系統中采用的調度算法

重要指標（響應時間，公平平衡）

時間片輪轉調度算法： 每個進程被分配一個時間片，允許該進程在該時間段運行，如果在時間片結束時該進程還在運行，則剝奪CPU并分配給另一個進程，如果該進程在時間片結束前阻塞或結束，則CPU立即進行切換。

當時間片選擇太長，其降級為先來先服務算法，引起對短的交互請求響應時間長

當時間片選擇太短，會導致頻繁的進程切換，浪費CPU時間。

通常選擇為20ms~50ms.

對進程表中不同進程的大小差異較大的有利，而對進程都是相同大小的不利。

虛擬輪轉法：主要基于時間片輪轉法進行改進，解決在CPU調度中對于I/O密集型進程的不友好。其設置了一個輔助隊列，對于I/O型進程執行完一個時間片之后，則進入輔助隊列，CPU調度時總是先檢查輔助隊列是否為空，如果不為空總是優先調度輔助隊列里的進程，直到為空，才調度就緒隊列的進程。

最高優先級調度算法：選擇優先級最高的進程優先執行。

優先級可以靜態不變，也可以動態調整

優先數決定優先級

就緒隊列可以按照優先級組織

實現簡單，但不公平，可能導致優先級低的進程產生饑餓現象。

可能產生優先級反轉問題（基于優先級的搶占式算法），即一個低優先級進程持有一個高優先級進程所需要的資源，使得高優先級進程等待低優先級進程運行。

多級反饋隊列調度算法：

設置多個就緒隊列，并為各個隊列賦予不同的優先級。第一個隊列的優先級最高，依次遞減優先級。

對于各個隊列進程執行時間片的大小也不同，優先級越高的隊列，分配到的時間片越少。

當第一級隊列為空時，再第二級隊列進行調度，依次類推，各級隊列按照時間片輪轉方式進行調度。

當一個新進程創建后，首先把它放入第一隊列的末尾。按照FCFS原則排隊等待調度。當輪到該進程執行時，如它在該時間片完成，便可準備撤離系統，如果它在一個時間片結束時尚未完成，則調度程序便將該進程轉入第二隊列的末尾，再同樣地按照FCFS原則等待調度執行。依次類推。

各種調度算法比較：