FCFS, SJF, RR 介紹，注意不同排程的優缺點；最近多處理器架構也越來越夯啦。
2015.1.15 初版
2017.8.20 二版
一、CPU 排程簡介
OS 用 multiprogramming 方法得到 CPU 最大使用率，一般 process 一開始都是 CPU Burst，交由 CPU 去處理該 process，接著是 I/O Burst，做 I/O 資料的傳送。在正常的狀況下，process 就在這兩個狀態間一直循環，最後會呼叫一個終止行程執行的 system call 作為行程的結束。
CPU scheduling 從在 ready queue 的 process 中挑選 process 進入 CPU 執行。CPU scheduling 選擇的 process 會在以下情況改變 :
- Switches from running to waiting state.
- Switches from running to ready state. e.g. time sharing 因為 time out 回到 ready
- Switches from waiting to ready.
- Terminates
[注意] Scheduling under only 1 and 4 is nonpreemptive
1. Preemptive vs Cooperative
Preemptive scheduling (當前主流)
- Higher responsiveness
- Hard to share resources race conditions
- Higher overheads
Cooperative scheduling
- Simpler in design
- Poor responsiveness
- Potential hazards
2. Dispatcher
dispatcher 負責將 CPU 控制權交給經由 Short-term scheduler 所挑選出的 process。
下列情況Dispatcher須執行：
- switching context
- switching to user mode
- jumping to the proper location in the user program to restart that program
[注意] Dispatch latency – time it takes for the dispatcher to stop one process and start another running ( Context-switch overhead )
3. Scheduling Criteria
- CPU utilization：CPU process exec. / CPU total time，CPU 使用的時間
- Throughput：單位時間內完成的工作數目
- Turnaround time：完成時間 (完成-到達)，進去process到出來花的時間
- Waiting time：waiting in the ready queue
- Response time：自使用者命令交付到系統產生第一個回應所需的時間 (time-sharing system, user-interactive App 特別重視)
[用心去感覺]
i. 綠色越大越好，紅色越小越好。
ii. throughput vs waiting time : 雖然一直小的效能好，但一直先做小的，大的會餓死。
二、排程演算法
1. FCFS (First-come,First-served) 排程
- 優點：很公平
- 缺點：低 CPU 利用度
很多 process 均在等待一個需要很長 CPU Time 來完成工作 process，造成平均等待時間大幅增加的不良現象。對 I/O-bound process 有極糟糕的影響，會造成低 I/O 利用度。
2. SJF (Shortest-Job-First) 排程
短任務先做，分可插隊與不可插隊。
- 優點：short waiting time.
- SJF (nonpreemptive) : optimal in terms of total waiting time if bursts all ready at 0
- SRTF (preemptive) : optimal in terms of total waiting time if jobs'arrival times are arbitrary
- 缺點：Not fair, starvation issue (low priority processes may never execute)
- Solution：Aging – as time progresses increase the priority of the process
It is hard to know the precise length of a CPU burst in advance.
- $t_n = $ 上一次預估的 CPU Burst Time
- $\tau_{n} = $ 上一次實際的 CPU Burst Time
- $\tau_{n+1} = $ 此次預估的 CPU Burst Time
- $\alpha = $ 分配比率，常用 $\alpha = \frac{1}{2}$
3. RR (Round Robin) 排程
知更鳥式循環排程法，分時系統所使用的排程法。
- 優點：
- No process waits more than (n-1)q time units.
- better response (Users feel that processes run "smoothly slow")
- Performance：
- q large：FIFO
- q small：q must be large with respect to context switch, otherwise overhead is too high
- Better response <— (小) Time quantum (大) —> better turnaround time
4. Multi-level queue
Ready queue is partitioned into separate queues. Each queue has its own scheduling algorithm. e.g.
- foreground (interactive) – RR
- background (batch) – FCFS
5. Multi-level feedback queue
A process can move between the various queues. Aging can be implemented this way.
e.g. Three queues :
- Q0 – RR with time quantum 8 milliseconds (If not finish, moved to next queue.)
- Q1 – RR time quantum 16 milliseconds
- Q2 – FCFS
[用心去感覺] I/O-bound and CPU-bound proces in m-queue
Why do we prefer I/O-bound processes?
- To improve I/O utilization (vs the convoy effect of FCFS)
- To improve the responsiveness (in favor of interactive processes)
Why CPU processes are given to larger time quantum?
- To improve the throughput / turnaround.
三、Multiple-Processor Scheduling (處理器之間)
Processor affinity : Processor affinity takes advantage of the fact that remnants of a process that was run on a given processor may remain in that processor's state (for example, data in the cache memory) after another process was run on that processor.
load balancing :
- Push migration – push a process away from a heavily loaded processor to an idle processor
- Pull migration – pull a waiting process from a heavily loaded processor into an idle processor
[感覺] The two issues conflict with each other!
References
Scheduling, Part 2: Scheduling Processes: Algorithms
http://cs241.cs.illinois.edu/scheduling-part-2-scheduling-processes-algorithms.html
Abraham Silberschatz, Peter B. Galvin, Greg Gagne - Operating System Concepts 8th Edition
https://www.amazon.com/Operating-System-Concepts-Abraham-Silberschatz/dp/0470128720
聯合大學陳士杰教授課程教材
http://web.nuu.edu.tw/~sjchen/
洪逸 - 作業系統金寶典
http://m.sanmin.com.tw/product/index/001601057
發表文章
