第3章-1 進(jìn)程調(diào)度

第3章處理機(jī)調(diào)度與死鎖1

3.1處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)

3.2作業(yè)與作業(yè)調(diào)度

3.3進(jìn)程調(diào)度3.4實(shí)時(shí)調(diào)度

3.5死鎖概述3.6預(yù)防死鎖3.7避免死鎖3.8死鎖的檢測(cè)與解除處理機(jī)調(diào)度概述(p85)處理機(jī)調(diào)度的三個(gè)層次（類型）高級(jí)調(diào)度（作業(yè)調(diào)度，長(zhǎng)程調(diào)度）中級(jí)調(diào)度(交換調(diào)度，內(nèi)存調(diào)度)低級(jí)調(diào)度（進(jìn)程調(diào)度，短程調(diào)度）二級(jí)調(diào)度隊(duì)列模型處理器低級(jí)調(diào)度高級(jí)調(diào)度完成超時(shí)就緒隊(duì)列等待事件事件出現(xiàn)后備作業(yè)隊(duì)列處理機(jī)調(diào)度算法的目標(biāo)(p86)

調(diào)度實(shí)質(zhì)上是一個(gè)策略問(wèn)題，設(shè)定的目標(biāo)往往是相互沖突的，如何選擇取決于操作系統(tǒng)的類型和目標(biāo).面向用戶的準(zhǔn)則周轉(zhuǎn)時(shí)間短響應(yīng)時(shí)間快截止時(shí)間的保證面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高處理機(jī)利用率高

各類資源的平衡利用調(diào)度算法性能衡量

周轉(zhuǎn)時(shí)間如果進(jìn)程i進(jìn)入內(nèi)存的時(shí)刻是ts，完成時(shí)刻是tf，該進(jìn)程的周轉(zhuǎn)時(shí)間ti為：ti=tf-ts實(shí)際上，它是進(jìn)程的等待時(shí)間與運(yùn)行時(shí)間之和。平均周轉(zhuǎn)時(shí)間為了提高系統(tǒng)的性能，要讓若干個(gè)進(jìn)程的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間最小。平均周轉(zhuǎn)時(shí)間T=(Σti)/n帶權(quán)周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間如果進(jìn)程i的周轉(zhuǎn)時(shí)間為ti，所需運(yùn)行時(shí)間為tk，則稱

wi=ti/tk為該進(jìn)程的帶權(quán)周轉(zhuǎn)時(shí)間。ti是等待時(shí)間與運(yùn)行時(shí)間之和，故帶權(quán)周轉(zhuǎn)時(shí)間總大于1。平均帶權(quán)周轉(zhuǎn)時(shí)間W=(Σwi)/n作業(yè)調(diào)度(p88)作業(yè)調(diào)度的概念從作業(yè)后備隊(duì)列中選出若干作業(yè)裝入內(nèi)存，參與多道運(yùn)行高級(jí)調(diào)度內(nèi)容接納多少作業(yè)接納哪些作業(yè)

作業(yè)調(diào)度算法(p89)先來(lái)先服務(wù)（FCFS）短作業(yè)優(yōu)先（SJF）高響應(yīng)比優(yōu)先（HRRN）優(yōu)先級(jí)高優(yōu)先（PS）調(diào)度算法按照作業(yè)進(jìn)入后備作業(yè)隊(duì)列的先后次序來(lái)選擇。例優(yōu)點(diǎn)實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)算法只顧及作業(yè)等候時(shí)間，沒(méi)考慮作業(yè)要求服務(wù)時(shí)間的長(zhǎng)短，不利于短作業(yè)而優(yōu)待了長(zhǎng)作業(yè)。先來(lái)先服務(wù)調(diào)度算法算法以進(jìn)入系統(tǒng)的作業(yè)所要求的CPU時(shí)間為標(biāo)準(zhǔn)，總選取估計(jì)計(jì)算時(shí)間最短的作業(yè)投入運(yùn)行。例優(yōu)點(diǎn)算法易于實(shí)現(xiàn)。缺點(diǎn)忽視了作業(yè)等待時(shí)間；不利于長(zhǎng)作業(yè)，會(huì)出現(xiàn)饑餓現(xiàn)象。短作業(yè)優(yōu)先調(diào)度算法（SJF）SJF算法習(xí)題【例】四個(gè)作業(yè)同時(shí)到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：作業(yè)名所需CPU時(shí)間作業(yè)19

作業(yè)24

作業(yè)310

作業(yè)48

假設(shè)系統(tǒng)中沒(méi)有其他作業(yè)，現(xiàn)實(shí)施SJF調(diào)度算法，平均作業(yè)周轉(zhuǎn)時(shí)間為多少？(17)平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間為多少？(1.98)

響應(yīng)比

R=（處理時(shí)間+等待時(shí)間）/處理時(shí)間

=周轉(zhuǎn)時(shí)間/處理時(shí)間

=1+（等待時(shí)間/處理時(shí)間）短作業(yè)容易得到較高響應(yīng)比；長(zhǎng)作業(yè)等待時(shí)間足夠長(zhǎng)后，也將獲得足夠高的響應(yīng)比；饑餓現(xiàn)象不會(huì)發(fā)生例優(yōu)點(diǎn)短作業(yè)、長(zhǎng)作業(yè)兼顧。缺點(diǎn)每次調(diào)度都要計(jì)算響應(yīng)比，增加系統(tǒng)開(kāi)銷。高響應(yīng)比優(yōu)先調(diào)度算法（HRRN)進(jìn)程調(diào)度概念(p91)又稱微觀調(diào)度、低級(jí)調(diào)度、短程調(diào)度、處理機(jī)調(diào)度?？刂茀f(xié)調(diào)進(jìn)程對(duì)CPU的競(jìng)爭(zhēng)，即按一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程，把CPU的使用權(quán)交給被選中的進(jìn)程。操作系統(tǒng)中實(shí)現(xiàn)進(jìn)程調(diào)度的程序稱為進(jìn)程(線程)調(diào)度程序，或分派程序(Dispatcher)，常駐內(nèi)存。進(jìn)程調(diào)度程序是操作系統(tǒng)最為核心的部分，進(jìn)程調(diào)度策略的優(yōu)劣直接影響到整個(gè)系統(tǒng)的性能。僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型處理器低級(jí)調(diào)度完成超時(shí)就緒隊(duì)列等待事件事件出現(xiàn)交互用戶進(jìn)程調(diào)度的任務(wù)保存處理機(jī)的現(xiàn)場(chǎng)信息按某種算法選擇進(jìn)程把處理機(jī)分配給進(jìn)程何時(shí)發(fā)生進(jìn)程調(diào)度呢?有四種情況都會(huì)發(fā)生進(jìn)程調(diào)度:當(dāng)一個(gè)進(jìn)程從運(yùn)行態(tài)切換成阻塞態(tài)時(shí)；當(dāng)一個(gè)進(jìn)程從運(yùn)行態(tài)切換成就緒態(tài)時(shí)；當(dāng)一個(gè)進(jìn)程中止時(shí)。

當(dāng)一個(gè)進(jìn)程從阻塞態(tài)切換成就緒態(tài)時(shí)；進(jìn)程調(diào)度方式(p92)非搶占方式(Non-preemptive）某一進(jìn)程被調(diào)度運(yùn)行后，除非由于它自身的原因不能運(yùn)行，否則一直運(yùn)行下去。搶占方式(Preemptive）當(dāng)有比正在運(yùn)行的進(jìn)程優(yōu)先級(jí)更高的進(jìn)程就緒時(shí)，系統(tǒng)可強(qiáng)行剝奪正在運(yùn)行進(jìn)程的CPU，提供給具有更高優(yōu)先級(jí)的進(jìn)程使用。優(yōu)先權(quán)原則短進(jìn)程優(yōu)先原則時(shí)間片原則16進(jìn)程調(diào)度算法(p93)先來(lái)先服務(wù)算法（FCFS）短進(jìn)程優(yōu)先算法（SPF）高響應(yīng)比優(yōu)先調(diào)度算法（HRRN）優(yōu)先級(jí)調(diào)度算法（PSA）基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法（RR）17先來(lái)先服務(wù)調(diào)度算法FCFS調(diào)度算法按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序來(lái)選擇。調(diào)度方式采用非搶占方式。例18優(yōu)點(diǎn)實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)算法只顧及進(jìn)程的等候時(shí)間，沒(méi)考慮進(jìn)程要求服務(wù)時(shí)間的長(zhǎng)短；不利于短進(jìn)程而優(yōu)待了長(zhǎng)進(jìn)程；沒(méi)考慮進(jìn)程的優(yōu)先級(jí)。最短進(jìn)程優(yōu)先算法（SPF）算法以進(jìn)程所要求的CPU時(shí)間為標(biāo)準(zhǔn)，總選取估計(jì)運(yùn)行時(shí)間最短的進(jìn)程投入運(yùn)行。調(diào)度方式采用非搶占方式。例19優(yōu)點(diǎn)算法易于實(shí)現(xiàn)。缺點(diǎn)忽視了進(jìn)程等待時(shí)間；不利于長(zhǎng)進(jìn)程，會(huì)出現(xiàn)饑餓現(xiàn)象。20

響應(yīng)比

R=周轉(zhuǎn)時(shí)間/運(yùn)行時(shí)間

=（運(yùn)行時(shí)間+等待時(shí)間）/運(yùn)行時(shí)間

=1+（等待時(shí)間/運(yùn)行時(shí)間）短進(jìn)程容易得到較高響應(yīng)比；長(zhǎng)進(jìn)程等待時(shí)間足夠長(zhǎng)后，也將獲得足夠高的響應(yīng)比；饑餓現(xiàn)象不會(huì)發(fā)生例最高響應(yīng)比(HRRN)優(yōu)先調(diào)度算法高優(yōu)先權(quán)調(diào)度算法（1）(p94)算法思想從就緒隊(duì)列中選擇優(yōu)先權(quán)最高的進(jìn)程投入運(yùn)行。調(diào)度算法類型非搶占式搶占式優(yōu)先權(quán)類型靜態(tài)優(yōu)先數(shù)法:在進(jìn)程創(chuàng)建時(shí)指定優(yōu)先數(shù)，在進(jìn)程運(yùn)行期間優(yōu)先數(shù)不變。動(dòng)態(tài)優(yōu)先數(shù)法:在進(jìn)程創(chuàng)建時(shí)創(chuàng)立一個(gè)優(yōu)先數(shù)，但在其生命周期內(nèi)優(yōu)先數(shù)可以動(dòng)態(tài)變化。如等待時(shí)間長(zhǎng)優(yōu)先數(shù)可改變。2122優(yōu)先數(shù)越大，優(yōu)先權(quán)越高，非搶占式優(yōu)先數(shù)越小，優(yōu)先權(quán)越高，搶占式高優(yōu)先權(quán)調(diào)度算法示例時(shí)間片輪轉(zhuǎn)調(diào)度算法（RR）(p93)搶占方式調(diào)度?；舅枷?/p>

把CPU劃分成若干時(shí)間片,并且按順序賦給就緒隊(duì)列中的每一個(gè)進(jìn)程，進(jìn)程輪流占有CPU，當(dāng)時(shí)間片用完時(shí)，即使進(jìn)程未執(zhí)行完畢，系統(tǒng)也剝奪該進(jìn)程的CPU，將該進(jìn)程排在就緒隊(duì)列末尾。同時(shí)系統(tǒng)選擇另一個(gè)進(jìn)程運(yùn)行。23就緒隊(duì)列…時(shí)間片的選取時(shí)間片長(zhǎng)度的選擇輪轉(zhuǎn)法的性能取決于時(shí)間片（記為q）長(zhǎng)度的選擇，進(jìn)程間在CPU上的切換需要時(shí)間。q足夠大到每一進(jìn)程執(zhí)行完，F(xiàn)CFS(先到先服務(wù))q

適當(dāng)–––進(jìn)程均勻執(zhí)行q

太小–––開(kāi)銷太大，有切換時(shí)間，CPU利用率低。

例：切換t=5ms,q=20ms,則CPU利用率80％，有20％花費(fèi)在進(jìn)程調(diào)度程序。為了改善CPU的利用率，可以增大時(shí)間片，設(shè)q=500ms，此時(shí)CPU利用率達(dá)99％之多，但每一進(jìn)程的響應(yīng)時(shí)間也因之增大。若就緒隊(duì)列中共有10個(gè)進(jìn)程，則每一進(jìn)程需要等待5秒鐘，才能在CPU上服務(wù)一次。通常來(lái)說(shuō)，選擇時(shí)間片為10~100毫秒左右比較適宜，上下文切換時(shí)間少于10微妙。與時(shí)間片大小有關(guān)的因素系統(tǒng)響應(yīng)時(shí)間(進(jìn)程等待時(shí)間)就緒進(jìn)程個(gè)數(shù)（就緒隊(duì)列長(zhǎng)度）輪換時(shí)間(切換時(shí)間)24輪轉(zhuǎn)調(diào)度算法示例25進(jìn)程名

A

B

C

D

E

平均

到達(dá)時(shí)間

0

1

2

3

4

作業(yè)情況

時(shí)間片

服務(wù)時(shí)間

4

3

4

2

4

完成時(shí)間

12

10

16

11

17

周轉(zhuǎn)時(shí)間

12

9

14

8

13

11.2

RR

q＝1

帶權(quán)周轉(zhuǎn)時(shí)間

3

3

3.5

4

3.25

3.35

完成時(shí)間

4

7

11

13

17

周轉(zhuǎn)時(shí)間

4

6

9

10

13

8.4