當有多個進程時,cpu調度決定了哪一個進程運行
計算機中,CPU與I/O交替運行
但是一個進程往往需要大量的計算,卻有很少的I/O操作,并且I/O操作很費時間,于是乎,我們想讓這個cpu的執(zhí)行的時間更長一些,I/O更短一些,甚至可以同時把多個進程導入內存舍扰，使得一個進程在CPU中執(zhí)行I/O時，一個進程用來填補CPU的時間
進程狀態(tài)
在前面進程一章單獨講過進程狀態(tài),這里抽出三個比較主要的:
■ Running - process is running on CPU.
■ Ready - ready to run, but not actually running on the CPU.
■ Waiting - waiting for some event like IO
to happen
調度算法
?算法關注點
- cpu使用率:讓cpu盡可能高效
- 吞吐量：單位時間完成進程的數(shù)量
- 周轉時間：從進程提交到進程完成
- 等待時間：在就緒隊列等待的時間之和
- 響應時間：提交請求到第一次回復請求
不同的系統(tǒng)關注點不同:多道系統(tǒng)想要好的吞吐量和周轉時間,而交互系統(tǒng)則更看中響應時間
一. 批處理系統(tǒng)
?First-Come, First-Served (FCFS)
先到先服務,顧名思義,一個進只有被中斷或者執(zhí)行I/O才會放棄cpu資源,在其他情況下一直做個獨裁者
假設有三個進程:
P1 (takes 24 seconds)
P2 (takes3 seconds)
P3 (takes 3 seconds)
□ If arrive in order P1, P2, P3, what is
Waiting Time? (24+27) / 3 = 17
Turnaround Time? (24+27+30) / 3 = 27
Throughput? 30 / 3 = 10.
?Priority Scheduling
每個進程賦予一個優(yōu)先級,優(yōu)先級高的先運行,如果優(yōu)先級相同:考慮FCFS算法
饑餓問題:優(yōu)先級小的進程不容易運行,這里用老化解決:隨著時間增長,那些一直沒有運行的進程的優(yōu)先級會逐步增加
假定這里有五個進程:
P1(burst time 10, priority 3), P2 (burst
time 1, priority 1), P3 (burst time 2,
priority 3), P4 (burst time 1, priority
4), P5 (burst time 5, priority 2). Lower
numbers represent higher priorities.
執(zhí)行順序按照權重
下面介紹優(yōu)先調度算法的一個分支
Shortest-Job-First (SJF)
最小任務優(yōu)先可以減少等待和周轉時間,因為哪些時間長的任務放到了最后.前面提到,一個進程是由CPU區(qū)間和I/O區(qū)間交替組成的,而SJF是看哪個進程的CPU區(qū)間最短
- 搶占式：又稱最短剩余優(yōu)先希坚，當新進來的進程的CPU區(qū)間比當前執(zhí)行的進程所剩的CPU區(qū)間短妥粟，則搶占
- 非搶占：稱為下一個最短優(yōu)先，因為在就緒隊列中選擇最短CPU區(qū)間的進程放在隊頭
四個進程:
P1 (burst time 8)
P2(burst time 4)
P3 (burst time 9)
P4 (burst time 5)
that arrive one time unit apart in order P1, P2, P3, P4.
- 搶占的順序是:P2(time 4)P4(time 5)P1(time 8)P3(time9)
- 非搶戰(zhàn)的順序:P1(time 1)P2(time 4)P4(time 5)P1(time 7)P3(time 9)
SJF用于長期調度而不能用短期調度,因為進程是一個整體,CPU沒法知道進程中第一個CPU區(qū)間長度吏够。
SJF需要確定下一個CPU區(qū)間的時間長度,可以通過近似估算出下一個CPU區(qū)間的長度,比如tn+1=atn+(1-a)rn tn為最近最近一次的CPU時間勾给，rn為歷史記錄,a是給定的權重。
二.分時操作系統(tǒng)
?輪轉法/RR調度
在早期的時間片輪轉法中锅知，系統(tǒng)將所有的就緒進程按先來先服務的原則播急，排成一個隊列，每次調度時售睹，把CPU分配給隊首進程桩警，并令其執(zhí)行一個時間片。
時間片的大小從幾ms到幾百ms昌妹。當執(zhí)行的時間片用完時捶枢，由一個計時器發(fā)出時鐘中斷請求握截，調度程序便據(jù)此信號來停止該進程的執(zhí)行，并將它送往就緒隊列的末尾
然后烂叔，再把處理機分配給就緒隊列中新的隊首進程谨胞，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進程蒜鸡，在一給定的時間內胯努，均能獲得一時間片的處理機執(zhí)行時間。
如果在時間片結束時進程還在運行逢防，則CPU將被剝奪并分配給另一個進程叶沛。如果進程在時間片結束前阻塞或結束，則CPU當即進行切換忘朝。調度程序所要做的就是維護一張就緒進程列表灰署，當進程用完它的時間片后，它被移到隊列的末尾局嘁。
- 多級隊列方法：將系統(tǒng)中所有進程分成若干類氓侧，每類為一級
- 多級反饋隊列:多級反饋隊列方式是在系統(tǒng)中設置多個就緒隊列，并賦予各隊列以不同的優(yōu)先權---百度超詳細講解
假設Have 3 queues, numbered 0, 1, 2 with
corresponding priority.
■ So, for example, execute a task in queue
2 only when queues 0 and 1 are empty.
- 首先進程從就緒狀態(tài)到隊列0,然后讓他運行8ms
- 到達隊列1,讓他運行16ms
- 運行隊列2:如果是交互系統(tǒng),采用RR調度(給他充足的運行時間).如果是批處理操作系統(tǒng),采用FCFS算法
如果此時有其他進程準備就緒,則搶占隊列2,這個算法也就是說,后進的不一定最慢完成
?unix調度
作為分時操作系統(tǒng)最最典型的unix與linux,自然要介紹下讓他們:
每個進程給予相同的優(yōu)先級:60,由于系統(tǒng)時鐘每秒產生一個50到100次的中斷导狡，所以我們假設每秒鐘有60次中斷,當被中斷的進程運行時,時鐘中斷程序會在PCB上增加一個字段:cpu使用率
操作系統(tǒng)會運行優(yōu)先級最高的進程,如果相同,會選擇在就緒隊列時間較長的那一個
每一秒,都會從新計算優(yōu)先級和cpu使用率:
- cpu使用率=cpu使用率 / 2
- 優(yōu)先級=cpu 使用率 / 2 + 基礎優(yōu)先級(60)
所以,不難看出,如果一個進程最近沒有使用過cpu,那么他的優(yōu)先級就會增高,與IO和交互相關的進程優(yōu)先級往往很高，與CPU相關的進程優(yōu)先級往往很低（這是您想要的）
unix還為每個進程提供一個"nice"值,用來修正優(yōu)先級計算:
- 優(yōu)先級= CPU使用率 / 2 + 基礎優(yōu)先級 + nice value
數(shù)字越低,優(yōu)先級越高,并且您能通過nice值來減少一個進程的優(yōu)先級
