CPU scheduling

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執行期限,優先權越高

 

2014-01-11 23:46:53發表 0000-00-00 00:00:00修改   

數據分析
程式開發
計算機組織與結構
資料結構與演算法
Database and MySql
manage tool
windows
unix-like
linux service
network
network layer3
network layer2
network WAN
network service
作業系統

數位鑑識
資訊安全解決方案
資訊安全威脅
Cisco security
Cisco network
Cisco layer3
Cisco layer2



  登入      [牛的大腦] | [單字我朋友] Powered by systw.net