5.1 Basic Concepts
- CPU Burst: 使用 CPU 的時間
- I/O Burst: 使用 I/O 的時間
- I/O Bound process: I/O比計算時間多
- CPU Bound process: CPU比I/O時間多
Non-preemptive and Preemptive
- 不可奪取的: Non-preemptive Process，優先級極高使其他Process無法奪取CPU
- 進入 wait state 或結束時可交給其他 process
- 可奪取的: Preemptive Process，可被奪取
- ready queue 沒有其他 process時，中斷完成後依然有控制權
如果有 interrupt ， Non-preemptive Process 依然會轉交給 OS ， 完成後OS歸還控制權給原程式。
5.2 Scheduling Criteria
選擇的考量
- Maximum CPU Utilization: CPU 使用率
- Maximum Throughput: 吞吐量
- Minimize the Maximum Response Time: 最小的最差反應時間
- Minimize Turnaround Time: submit到完成的時間最小
- Minimize Average Waiting Time: ready queue wait time 最小
- Minimize Variance in the Response Time
- Minimize The Number of Interactive Users: 最多交談使用者
- Minimize System Overhead: 最小負擔
- Balance Resources Used: 平衡資源
- Be Fair: 使排程公平
5.3 Scheduling Scheme
FCFS (First Come First Served)
先進先服務，不可奪取，不適合使用者交談與分時系統
- Turnaround Time: 往返時間
Finish time - Arrival time - Waiting Time: 等待時間
Turnaround time - CPU Burst - Gantt chart: 甘特圖，將Process順序畫成甘特圖，用來求出往返與等待時間
- Arrival Time: 抵達時間
Shortest Job First
特性
- 最小平均等待時間
- 最佳演算法 Optimal Algorithm
- 難以實現: 無法預測CPU burst time
方法:
- CPU Burst time 最小的Process優先佔有CPU
- Burst time 相同者以 FCFS 處理
類型:
- Preemptive SJF:
- Shortest Remaining Time First: SRTF 最短剩餘時間優先
- 適合 Time Sharing 處理
- 最小 Burst 者優先，並且能夠搶奪當前的 Process
- Non-Preemptive SJF:
- 不適合 Time Sharing 處理
- 處理時如果更少花費的 Process 抵達，只能在 Queue 前等待
註:
- 可奪取時: 先比較與 CPU 執行的 Process 比較
- 不可奪取則直接在 Queue 比較
最高反應時間比率優先
透過反應時間作為優先等級
反應時間比率
Response Ratio = (Waiting time + CPU Burst Time) / CPU Burst Time
Priority 排程法
- 優先級最高者佔有CPU
- 優先級相同者以 FCFS 處理
- 依然能有可奪取與不可奪取
缺點
- Indefinite Blocking: 無限懸置，也稱為 Starvation
- 透過 Aging 機制解決:
- 隨時間降低或升高 Priority
- Dynamic Priority, Floating Priority: 類似最高反應時間比率的方式
- 透過 Aging 機制解決:
Round Robin 排程
- 為可搶奪: Time sharing
- 透過 Time Sharing 處理 FCFS
注: time Sharing 可作為 Processor sharing 的方式
Time Slice 選擇
- Time Slice 過大: 效果如同 FCFS
- Time Slice 過小: 系統效率差 (Context Switch 過多)
各種情況
- 考量不同 time Slice
- 不同的抵達時間
- I/O 處理
注意: 計算時如果process沒有處理完成，時間片段用完之後必須把 Process放回queue中
Multilevel Queue
用於實現 Priority 排程法的方法
- 多重 Queue ，並且由高到低優先等級
- 原則上採用 Round Robin，最低優先級可能採用 FCFS
注
- foreground Process: 可交互，需要高優先級，由 RR 排程法處理
- Background Process: 不需要交互的，如 Batch，低優先級，可以用FCFS
缺點
- 優先等級被固定，容易有 Indefinite Blocking
Multilevel Feedback Queue
加上 Aging 方法，來升降佇列等級
特性
- 可奪取
- 不會有 Indefinite Blocking
- 花費時間過多(如 CPU Bound Process )降級
- 等待時間過多(如 I/O Bound Process )升級
總結
- FCFS: 由先後次序作為優先級
- 可奪取 SJF 預估時間作為優先級
- 不可奪取 SJF 剩餘時間作為優先級
- 最高反應時間: 以反應時間比率作為優先級
- RR: 由 ready Queue 的次序作為優先級
5.4 系統效能評估
- 定量模式 (Deterministic Modeling): 收集現有環境中一段時間內的數據，對不同以演算法輸入數據
找出當中最好的算法。
- 收集資料花費許多成本
- 佇列模式 (Queuing Modeling): 透過Little’s formula 評估
n = lambda * omega- n: 佇列平均長度
- omega: Process 平均等待時間
- lambda: Process 平均出生率，透過統計計算，透過各種機率分佈下去計算
- 模擬法(Simulations): 透過亂數產生資料，並進行評估
- 定量模式法差在該方法透過隨機模擬數據
Operating System