程序排程的兩種方式

• 非剝奪方式：處理機一旦配置設定給某個程序後就讓它一直執行，知道程序完成或發生某個事件而阻塞時，才把處理機配置設定給另一個程序。
• 剝奪方式：獲得處理機的某個程序在運作過程中，系統可以基于某種原則，剝奪它擁有的處理機并配置設定給其他程序。

排程算法的分類

不同的環境需要不同的排程算法。也就是說在不同的系統中，排程程式的優化是不同的。可以劃分出三種環境：

• 批處理系統
• 互動式系統
• 實時系統

常見的程序排程算法

批處理系統中排程

• 先來先服務算法FCFS：該算法總是把處理機配置設定給最先進入就緒隊列的程序。某個程序一旦得到處理機後便一直執行，知道該程序完成或發生某事件而阻塞時，才會把處理機配置設定給另一個程序。
• 最短作業優先算法：該算法總是把處理機配置設定給就緒隊列中占用處理機時間最短的那個程序。
• 最短剩餘時間優先：總是選擇剩餘運作時間最短的那個程序運作。

互動式系統中排程

• 輪轉排程：每個程序會依次被配置設定一個時間段，稱之為時間片（quantum），即允許程序在該時間片中運作。如何在時間片結束時程序還在運作，則剝奪CPU并配置設定給另一個程序。如果程序在時間片内阻塞或結束，則立即切換CPU。
• 優先級排程：總是選擇就緒隊列中優先級最高的程序運作。确定優先級的兩種方式：

1. 1. 靜态賦予：在程序建立是賦予，在整個運作期間不變。
   2. 動态賦予：在基于某種政策的情況下，程序的優先級随着時間可能發生變化。

• 多級隊列排程算法（CTSS）：系統中設定多個就緒隊列，每個隊列設定為不同的優先級。
• 最短作業優先：
• 保證排程：
• 彩票排程：
• 公平分享排程：