排程 (Scheduling)

CPU Scheduling Concept

當多個行程或執行緒在就緒佇列 (Ready Queues) 中等待進入CPU時，系統如何選擇適當的行程優先進入目前可執行的CPU中，這個作業即是CPU排程 (以下都簡稱為排程)。

排程是多工作業系統 (Multi programming) 的主要工作之一，目的在提高CPU的使用率 - 當CPU處於怠惰 (Idle) 時，立即安排其他就緒的行程進入CPU。

Type of Process

行程的執行會在兩個狀態間不停的切換:

- CPU Burst: 行程在CPU執行的期間。

- I/O Burst: 行程在等待I/O的期間。

CPU Bound: 此類行程大部分時間都在進行CPU計算上，通常由些一較長的CPU Burst組成。

I/O Bound: 此類行程花費大部分時間在I/O動作上 (ex. 播放DVD)，由許多小的CPU Burst組成。

Scheduler vs. Dispatcher

排程器 (Scheduler): 短程排程器 (Short - Term Scheduler 或稱 CPU Scheduler)，由就緒佇列中選出下一個可以執行的行程。

分配器 (Dispatcher): 當排程器選出下一個行程後，就把工作交給分派器執行下列動作

– 本文切換

– 將行程轉換至使用者模式 (排程是在核心模式進行)

– 重新回到使用者的程式，從適當位址開始執行

由分派器停止一個行程到開始執行另一個行程的這段時間稱為分派延遲 (Dispatch Latency)。

Preemptive vs. Non-Preemptive

行程進行排程的時機有兩種模式:

- 可搶先 (Preemptive): 當新的行程進入系統，或有其它行程進入就緒狀態 (ex. 中斷發生: Run → Ready/ 中斷喚醒: Wait → Ready)，能隨時進行搶佔CPU，讓目前執行中的行程暫停，再將CPU控制權交予優先權較高的行程。

*需注意同步的問題。

- 不可搶先 (Non-Preemptive): CPU配置給某行程後，此行程可一直擁有CPU控制權直到終止或是轉換到等待狀態 (ex. I/O發生: Run → Wait) 釋出CPU為止，其他行程無法搶佔。

Scheduling Algorithms

先到先執行 (First - Come -First Served, FCFS): 將就緒佇列內等待的各行程，依先到先執行的法則，排序進入CPU執行。

最短工作優先 (Shortest-Job-First, SJF): 根據下一次CPU Burst最短的行程可優先取得CPU的控制權。

優先權 (Priority): 行程的優先權高低來分配CPU 的使用順序，優先權愈高的行程可優先使用

CPU。但如果某行程的優先權很低，可能永遠無法進入CPU，即為饑餓 (Starvation) 現象，可用老化 (Aging) 來解決此問題 - 隨等待時間增長，機動提高該行程的優先權。

循環分時 (Round-Robin, RR): 將CPU時間等切割成數個時間分量 (Time slice/ Quantum)，時間分量代表每個行程每次取得CPU控制權的時間長短，因此當某個行程執行過程中超過一個時間分量時，便會被中斷 (Run → Ready)。

多層佇列 (Multilevel Queue): 將行程分類，相同類型的行程分在同一佇列，而每種佇列都有自己的排程方法，佇列之間還有優先權的關係，前景行程 (Foreground Process) 的優先權高於背景 (Background Process) 行程。

多層回饋佇列 (Multilevel Feedback-Queue): 允許行程在各個佇列間移動，避免飢餓的現象發生 (由低優先權的佇列移往較高優先權的佇列中等待)。

Multi-Processor Scheduling

同質性 (Homogeneous) CPU系統

佇列與CPU:

- 單一排程器 (Single Scheduler): 多個CPU共用一個佇列。

- 多重排程器 (Multiple Scheduler): 每個CPU都有專屬的佇列。

CPU與CPU (共用佇列):

- 對稱式 (SMP): 每個CPU的行為都是對等的，各自行進行排程，當CPU空閒時就到佇列中- 挑選一個行程來執行，但需克服同步的問題。

- 非對稱式 (NMP): 由某顆CPU來幫其他CPU進行排程。

Load Balancing vs. Processor Affinity (兩者為互斥關係)

負載平衡 (Load Balancing): 企圖保持工作均勻的分散在所有CPU，透過Push將過度負載的CPU裡行程分散到閒置CPU；用Pull動作將行程由忙碌CPU拉至閒置CPU。

處理器親和性 (Processor Affinity): 避免行程在不同間CPU轉移，當同一CPU上保持住同個行程，表示行程對該CPU有親和性。

Scheduling Criteria

1. CPU使用率 (Utilization): 0~100%。

2. 工作量 (Throughput): 單位時間內完成的行程數量。

3. 等待時間 (Waiting Time): 行程在就緒佇列裡等待的時間總和。

4. 回覆時間 (Turnaround Time): 完成一個行程所需的時間。

5. 反應時間 (Respond Time): 使用者發出要求後，收到第一個回應所需的時間。

(1)(2)計量越大越好；(3)(4)(5)越小越好。

Evaluation

定量模型 (Deterministic modeling )

佇列模式 (Queueing model)

模擬 (Simulation)

實作 (Implementation )

Other Issue:

Long - Term Scheduler/Job Scheduler vs Short - Term Scheduler/CPU Scheduler

Foreground Process vs Background Process

Soft affinity vs Hard affinity