簡介
為甚麼需要scheduling ? 為了實作multiprogram 去有效利用CPU資源
所有程式的執行狀態都可以歸納為CPU burst 與 I/O burst兩種情況
大部分程式只有短時間的CPU burst，與長時間的I/O burst
有四個情形需要CPU scheduling
- running => waiting (程式自己需要IO)
- running => ready (程式太久、其他情況需要被趕出去)
- wating => ready (程式結束IO)
- terminate (程式完成任務)
preemptive VS Non-preemptive
Non-preemptive => 不可插隊
比如只在1、4時scheduling
意思即為: 在程式結束之前都會一直佔著CPU
Preemptive=> 可以插隊，相對的概念
4種情況都scheduling
效能通常比較好，但是相對要注意process synchronization
Dispatcher
給被scheduler 選定的process使用CPU的權利
工作包含switching context , 修改Program counter
scheduling algorithm
throughput : 在一段時間內完成多少process
turnaround time : single job 執行的時間
waiting time : 在ready queue內等待的時間
response time : submision ~ 第一次執行的時間
First come First server (FCFS)
先到的process先執行
如下圖
注意: FCFS就算有preemptive，也不會使用
注意: 順序影響很大，如果今天順序變為 P2 P3 P1
則waiting time 變為 0+3+6 = 9
shortest job first (SJF)
- 是最短waiting time 的演算法
- 會受preemptive影響
- 要考慮job進來的時間
以下是Non-preemptive例子:
比如雖然P3最短，但在t=0時只能選P1
又因為無法打斷，waiting time == response time
以下是preemptive 例子:
注意response time 是進入~第一次被執行
重大困難點:無法事先確定process執行時間
Approximate SJF
使用moving average，以過去的執行時間，推測新process的執行時間
其中alpha表示對過去與現在的重視比例
使用例子:
priority scheduling
泛化的scheduling，為每個process綁定一個權重
權重越高，越快使用CPU
比如SJF，可以說是長度越短，權重越高
問題:可能有starving => 權重低的永遠執行不到
解法: aging，越久沒執行，權重會調越高
Round-Robin Scheduling
加入time quamtum的概念
實務上會設定10-100ms的TQ
當process執行超過TQ，就會被踢出並放到ready queue尾端 (必為preempted)
討論:
TQ large => 趨近FCFS
TQ small => context switch overhead 增加
直覺上可以理解， 通常RR會有比較高的完成所需時間，但會有較低的response time
Multilevel Queue Scheduling
用機率去選擇處理哪個queue
比如有50%的機率選擇system process queue
20% interactive queue …. 5% student process queue
選中queue就會執行裡面的程式
利用調整機率賦予權重，同時也避免starving
Multilevel Feedback Queue Scheduling
結合 RR 的TQ 與 multilevel queue的多queue概念
上下分層有意義，一定執行完上層，才往下執行
如果在該queue層未執行完，就會被推到下層(下層相較上層較晚執行、但執行時間可以更久)
aging: 當job卡在下層太久，會被往上拉
不像approximate SJF ，需要數學表達，實務上常採用