CPU scheduling
目地：最大化cpu使用率,以提高multi-program效率
主要由short-term scheduler負責
ps:
CPU-I/O burst cycle
process被執行時，會依CPU burst和I/O burst的循環到執行結束
dispatcher
將process交給cpus處理
工作括context switching ,switching to user mode,等…
當停止一個process而開始另一個process所需的時間稱為dispatch latency
context switching
動作：OS保存原process的執行狀態，並載入new process的狀態
使用時機：當cpu從一個process切換到另一個new process之前
該動為系統負擔,完成該動作的長短取決於硬體效能
scheduling使用時機
process state改變時,如下
running->waiting, 屬於nonpreemptive
running->ready
waiting->ready
running->terminate, 屬於nonpreemptive
ps:
nonpreemptive:不可插隊,若process不釋放CPU使用權,無法被強迫中斷
preemptive:可插隊,若process不釋放CPU使用權,可以被強迫中斷
scheduling可分兩類
Preemptive scheduling
一般而言，排班效能較佳(Avg. waiting time及Avg. turnaround time較低)
Context switching較多
Response time或turnaround time為不可預期的
Non-preemptive scheduling
Avg. waiting time可能較長(可能有Convoy effect)
Context switching較少
Response time或turnaround time為可預期
…………………………………………………
scheduling criteria
常見的有
cpu utilization：盡可能讓CPU持續工作
throughput：每單位時間內所完成的process的數量
turnaround time：從一個process開始到完成的時間
waiting time：每一個process在queue等待的時間總合
response time：從一個request被提出到開始要處理的時間
scheduling problem
常見的有
convoy effect(護衛效應):
許多process等待一個需花很多時間才能結束的process,使avg waiting time降低
stravation(飢餓),
low priority process可能永遠不會執行到
(可使用aging機制,當等待時越長,優先權會漸漸提昇)
常見scheduling
FCFS(first-come first-served)
process平均等待時間變動太大
會有convoy effect
SJF(shortest job first)
若能事先知道每個job的最小時間,則可使用該方法,此為最理想之方法
(但如何知道?常見的有系統預測和使用者定義)
preemptive SJF/shoartest remaining time first
當有new process進來時,就重新計算process需要的時間
然後先執行時間需求最少的process
priority scheduling
類似SJF
會發生stravation
RR(round robin)
假設指定時間為q,當process用完q後,會換到下一個process處理
屬於preemptive scheduling
process切換也會用掉cpu時間,q設太小會浪費很多時間一直在切換process
process的response time較快
process平均等待時間穩定
multilevel queue scheduling
根據不同類別的process給不同的queue scheduling
ex:80% to foreground in RR,20% to background in FCFS
multilevel feedback queue
當queue1 scheduling還無法處理完,則移到queue2 scheduling處理,以此類推
ex:Q0(RR with 4ms),q1(RR with 8ms),q2(FCFS)
假設有三個process,時間如下
p1(arrival time:0, burst time:10)
p2(arrival time:2, burst time:5)
p3(arrival time:4, burst time:8)
FCFS
運作如下
[p1,0-10][p2,10-15][p3,15:23]
計算如下
p1 waitting time=0,
p2 waitting time=10-2=8,
p3 waitting time=15-4=11,
waitting time=0+8+11=19
avg waitting time=19/3
RR(time slice=3)
運作如下
[p1,0-3(7)][p2,3-6(2)][p3,6-9(5)]
[p1,9-12(4)][p2,12-14(0)][p3,14-17(2)]
[p1,17-20(1)][p3,20-22(0)]
[p1,22-23(0)]
計算如下
p1 waitting time=0+(9-3)+(17-12)+(22-20)=13
p2 waitting time=(3+(12-6))-2=7
p3 waitting time=(6+(14-9)+(20-17))-4=10
waitting time=13+7+10=30
avg waitting time=10
……………..
multiple-processor scheduling
可以分為
asymmetric multiprocessing
只有一個processor負責分配
symmetric multiprocessing(SMP)
每個processor有自己的scheduling
processor affinity
讓process儘可能在同一個processor上處理
這可避免cache invalidating和repopulating
可分為
soft affinity:可讓process在processor之間轉移
hard affinity:可讓process不能在processor之間轉移
ps:
在windows下可用affinity指令控制process要在那個processor上處理
multiprocessor load balancing
主要有以下兩種
push migration:重的processor丟掉工作
pull migration輕的processor去接工作
…………………………..
real-time system scheduling
ps
real-time system
soft real-time system:讓有即性的process有較高優先權
hard real-time system:對完成時間有嚴格的要求
ps:
2種latency會影響real-time效能
interrupt latency
dispatch latency
ps:
一些processes有新的參數用在real-time system
period
processing time
deadline
Rate Monotonic Scheduling
period(執行週期)越短，優先權越高
Earliest Deadline First Scheduling
越接近process的deadline執行期限,優先權越高