本文為清華大學開放式課程上課心得整理。
此處所要介紹的 scheduling 是指電腦程序的最小單位，使用 CPU 的排序問題，最小單位是 thread 或 process 端看作業系統設計而定。
Basic Concepts
scheduling 出現的原因在於發展出了 multiple 的技術，因此需要排程讓 CPU 有效地執行每個程序。
程序只有計算與 I/O 兩種行為，程式的執行就是在 CPU burst 與 I/O burst 之間交換的過程，因此作業系統必須知道程式目前是在 CPU bound 還是 I/O bound，才能決定要如何優化執行緒。
Preemptive vs Non-Preemptive
rescheduling 的時機點大致上可分為四個：
・switches from running to waiting state：CPU 原本在執行的程式從 CPU burst 切換到 I/O burst
・switches from running to ready state：Time sharing 導致程式狀態轉換
・switches from waiting to ready state：程式的 I/O 結束，回到 ready queue 中等待執行
・Terminates：程式執行終止
Non-Preemptive scheduling 指的是當正在執行的程式仍在 CPU burst 時，就讓它繼續執行不去打斷，因此只會在上述第一、第四種狀況下做 rescheduling；Preemptive scheduling 則相反，只要發生會影響排序判斷的事件，就重新做 scheduling，所以上述四種狀況都會出現。
由於 Preemptive 是動態做排程，在效能上比較好，但是也因為可能在程式執行到一半時中斷，而產生同步的問題，而且是連作業系統的程式都有可能被打斷。不過因為 Preemptive 可以更有效使用資源，大部分的作業系統還是採用此種方式。在 Unix 系統中，當正在執行的程式屬於 kernel 時，系統會直接禁用 interrupt，用暫時將 scheduling 變成 Non-Preemptive 的方式，確保 kernel 能正確執行。
Dispatcher
scheduler 選擇了要執行的程式之後，便會將訊息傳給 dispatcher，再由 dispatcher 執行交換。前面提過的 switch context、page table pointer 更換等等，都是在 dispatcher 執行。
dispatcher 在執行時也會禁用 interrupt。
Scheduling Algorithm
通常我們會用幾種方式去衡量 Scheduling 的品質：
・CPU utilization：CPU 使用率，通常系統的 CPU 使用率會介於 40 到 90 之間。
・Throughput：每單位時間內完成的工作量（process），這是計算系統常用的衡量標準。
・Turnaround time：單一 process 從開始到結束的執行時間。
・Waiting time：process 在 ready queue 裡的等待時間，計算公式為 completion time − arrival time − run time（burst time）。
・Response time：submission 到第一個 response 產生所經過的時間。
其中，3、4、5 三項與 CPU scheduling 直接相關，也會影響 1、2 的結果。
常見的排序演算法如下：
FCFS Scheduling
顧名思義，就是先到者先處理。系統會拿到一串在 ready queue 中的程序，並得知程序預計的執行循環數，以下方為例：
P1(24), P2(3), P3(3)系統會按照 P1 > P2 > P3 的順序執行（Non-Preemptive 與 Preemptive 皆同），各程序的等待時間如下：
P1 = 0
P2 = 24
P3 = 27平均等待時間：（0+24+27）/ 3 = 17
這是第一輪的算法，若還有下一輪，那 wait time 就要扣掉程式執行 I/O burst 的時間。
就平均等待時間來說，FCFS Scheduling 的表現會取決於進入程式的執行循環數大小，如果一開始的程式循環數較小，表現就會比較好，反之則不然；運氣成份比較大，因此不算是比較好的解法。
Shortest-Job-First（SJF）Scheduling
從上方論述可以得知，如果只是單純要減少平均等待時間，只要將比較短的工作排在前面執行即可，因此就發展出 SJF 演算法。
SJF 是找最短的程式先執行，因此在 Non-Preemptive 與 Preemptive 狀況下得到的結果就會不同。以下用一個例子模擬 SJF 在 Non-Preemptive 與 Preemptive 狀況下的行為：
Process Arrival Time Burst Time
P1 0 7
P2 2 4
P3 4 1
P4 5 4一開始只有 P1 進入 ready queue，因此雙方皆從 P1 開始，執行順序如下：
Non-Preemptive P1(7) > P3(1) > P2(4) > P4(4)
Wait time：((7-0-7) + (8-4-1) + (12-2-4) + (16-5-4))/4 = 4
Response time：P1：0, P2：6, P3：3, P4：7Preemptive P1(7) > P2(4) > P3(1) > P2(2) > P4(4) > P1(5)
Wait time：((16-0-7) + (7-2-4) + (5-4-1) + (11-5-4))/4 = 3
Response time：P1：0, P2：0, P3：0, P4：2
SJF 只在意最短平均等待時間，所以有可能會犧牲 Response time 等要素，在某些情況下不見得是最好的解法。
Approximate Shortest-Job-First
SJF 實現的困難點在於無法得知下一個 CPU burst time，因此通常會搭配使用過去的紀錄，來預測下一個 burst time。
Priority Scheduling
先賦予每個程式權重，如果有需要也可以在程式執行的過程中動態增減權重。Scheduling 會以當下的權重決定程式的執行順序。
Priority Scheduling 是比較常見的一種排程方式，SJF 也可以算是 Priority Scheduling 的一種。Priority Scheduling 的問題在於如果有個程式權重很低，就有可能永遠輪不到它執行（starvation），解決的方式為每隔一段時間若該程式沒有被執行，便增加它的權重（aging）。
