處理機(jī)調(diào)度-課件3

1.

處理機(jī)調(diào)度的概念1）調(diào)度即按照一定的調(diào)度規(guī)則合理地分配與釋放資源，處理機(jī)調(diào)度即完成處理機(jī)的分配任務(wù)。一般認(rèn)為，有三級(jí)：作業(yè)調(diào)度、進(jìn)程調(diào)度和交換調(diào)度；2）原語(yǔ)：操作系統(tǒng)通過(guò)原語(yǔ)操作來(lái)實(shí)現(xiàn)調(diào)度控制。一般系統(tǒng)都有進(jìn)程創(chuàng)建、掛起、激活、阻塞、喚醒、撤消原語(yǔ)。注意在操作過(guò)程中用到就緒隊(duì)列、阻塞隊(duì)列和PCB。第三章處理機(jī)調(diào)度

作業(yè)調(diào)度：又稱(chēng)宏觀調(diào)度或高級(jí)調(diào)度。把外存上處于后備隊(duì)列中的作業(yè)調(diào)入內(nèi)存，并為之創(chuàng)建進(jìn)程、分配必要的資源，然后再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。用于批處理系統(tǒng)。在分時(shí)和實(shí)時(shí)系統(tǒng)，通常無(wú)須作業(yè)調(diào)度。

提交后備執(zhí)行完成SPOOLing作業(yè)調(diào)度SPOOLing進(jìn)程調(diào)度和交通控制

進(jìn)程調(diào)度：微觀調(diào)度或低級(jí)調(diào)度。按照某種策略和方法選取一個(gè)處于就緒狀態(tài)的進(jìn)程，將處理機(jī)分配給它。進(jìn)程調(diào)度程序：操作系統(tǒng)的真正核心，負(fù)責(zé)完成進(jìn)程從就緒到運(yùn)行轉(zhuǎn)變的工作。具體功能是記住所有進(jìn)程的狀態(tài)、優(yōu)先數(shù)和資源請(qǐng)求等，確定調(diào)度算法，分配處理機(jī)給進(jìn)程。進(jìn)程調(diào)度的基礎(chǔ)是進(jìn)程的組織，實(shí)際上是PCB的有效組織。

交換調(diào)度：中級(jí)調(diào)度。按照某種策略，將處于外存交換區(qū)中的重又具備運(yùn)行條件的就緒進(jìn)程調(diào)入內(nèi)存，或?qū)⑻幱趦?nèi)存就緒狀態(tài)或內(nèi)存阻塞狀態(tài)的進(jìn)程交換到外存交換區(qū)。它主要涉及內(nèi)存管理與擴(kuò)充。

2進(jìn)程調(diào)度的實(shí)現(xiàn)進(jìn)程的調(diào)度主要考慮三個(gè)方面：①調(diào)度的方式；②調(diào)度的時(shí)機(jī)；③調(diào)度的策略；1）調(diào)度的方式——如何來(lái)分配和回收CPU

非搶占方式和搶占方式。

非搶占方式(Nonpreemptivemode)

一旦把CPU分配給某一進(jìn)程后,便讓它一直運(yùn)行下去，直到進(jìn)程完成或發(fā)生某事件而阻塞時(shí)，才將CPU分給其它進(jìn)程。主要優(yōu)點(diǎn)是簡(jiǎn)單、系統(tǒng)開(kāi)銷(xiāo)小，但是一個(gè)進(jìn)程的運(yùn)行往往可能導(dǎo)致多數(shù)進(jìn)程長(zhǎng)期得不到服務(wù)。通常用在批處理系統(tǒng)中。搶占方式(Preemptivemode)

允許調(diào)度程序基于某種策略（優(yōu)先級(jí)策略、時(shí)間片策略、短作業(yè)優(yōu)先等）剝奪現(xiàn)行進(jìn)程的CPU給其它進(jìn)程。通常用在分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)中，以便及時(shí)響應(yīng)各進(jìn)程的請(qǐng)求。

2）調(diào)度的時(shí)機(jī)——進(jìn)程并發(fā)執(zhí)行過(guò)程中何時(shí)實(shí)現(xiàn)CPU的切換

①進(jìn)程運(yùn)行時(shí)，時(shí)間片用完被時(shí)鐘中斷；②請(qǐng)求I/O服務(wù)時(shí)，進(jìn)程需要暫時(shí)放棄CPU，以免出現(xiàn)CPU的“忙等待”；③某些原語(yǔ)操作，如P操作等；④進(jìn)程完成；⑤在可搶占方式調(diào)度中，新建進(jìn)程較當(dāng)前執(zhí)行進(jìn)程優(yōu)先級(jí)高。

3）調(diào)度的策略——選擇進(jìn)程運(yùn)行的依據(jù)。調(diào)度算法選擇多從處理器利用率、吞吐量、等待時(shí)間和響應(yīng)時(shí)間考慮。

了解：平均周轉(zhuǎn)時(shí)間作業(yè)的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間TS之比，即W=T/TS，稱(chēng)為帶權(quán)周轉(zhuǎn)時(shí)間，而平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為: ◆先來(lái)先服務(wù)（FCFS）：按進(jìn)程進(jìn)入就緒隊(duì)列的先后來(lái)調(diào)度。特點(diǎn)：有利于長(zhǎng)作業(yè)，不利于短作業(yè)；有利于CPU繁忙型，不利于I/O繁忙型；

◆短作業(yè)（進(jìn)程）優(yōu)先算法—SJ(P)F:每次調(diào)度時(shí)，從就緒隊(duì)列中找出下一個(gè)估計(jì)CPU執(zhí)行期最短的作業(yè)（進(jìn)程）優(yōu)先調(diào)度；特點(diǎn)：不利于長(zhǎng)作業(yè)，有利于短作業(yè)；進(jìn)程的執(zhí)行時(shí)間預(yù)測(cè)困難；沒(méi)有考慮進(jìn)程實(shí)際的緊迫程度；

。

◆優(yōu)先級(jí)調(diào)度算法：每次調(diào)度時(shí)，從就緒隊(duì)列中找出優(yōu)先級(jí)最高的進(jìn)程優(yōu)先調(diào)度。靜態(tài)優(yōu)先級(jí)法：在進(jìn)程創(chuàng)建時(shí)就確定其優(yōu)先級(jí)，運(yùn)行過(guò)程中不再改變的方法。一般按進(jìn)程類(lèi)型、資源的要求、作業(yè)到達(dá)時(shí)間或用戶類(lèi)型確定。動(dòng)態(tài)優(yōu)先級(jí)法：在運(yùn)行過(guò)程中，不斷調(diào)整進(jìn)程的優(yōu)先級(jí)。思考：動(dòng)態(tài)優(yōu)先級(jí)怎么確定？

◆時(shí)間片輪轉(zhuǎn)法：有簡(jiǎn)單時(shí)間片輪轉(zhuǎn)、可變時(shí)間片輪轉(zhuǎn)、多隊(duì)列輪轉(zhuǎn)法。時(shí)間片的大小確定：①系統(tǒng)對(duì)響應(yīng)時(shí)間的要求；②就緒隊(duì)列中進(jìn)程的數(shù)目；（分時(shí)系統(tǒng)終端的數(shù)目）③系統(tǒng)處理能力：保證用戶鍵入的常用命令能夠在一個(gè)時(shí)間片內(nèi)完成

◆多級(jí)反饋隊(duì)列調(diào)度就緒進(jìn)程的種類(lèi)：剛創(chuàng)建的進(jìn)程；已經(jīng)被調(diào)度執(zhí)行過(guò)，但還沒(méi)有執(zhí)行完，等待下一次調(diào)度；因請(qǐng)求I/O而阻塞，當(dāng)?shù)却蚪獬粏拘堰M(jìn)入就緒隊(duì)列。設(shè)置多個(gè)就緒隊(duì)列，第一級(jí)隊(duì)列的優(yōu)先級(jí)最高，但占用的時(shí)間片最短，各級(jí)隊(duì)列依次優(yōu)先級(jí)遞減，占用時(shí)間片遞增。 執(zhí)行進(jìn)程調(diào)度時(shí)，剛進(jìn)入就緒隊(duì)列的進(jìn)程先加入第一級(jí)隊(duì)列，獲得一個(gè)時(shí)間片，如時(shí)間片到而沒(méi)有完成，則將該進(jìn)程加入下一級(jí)。 分級(jí)調(diào)度可以使運(yùn)行時(shí)間短進(jìn)程優(yōu)先得到調(diào)度，減少運(yùn)行時(shí)間長(zhǎng)進(jìn)程的調(diào)度次數(shù)。就緒隊(duì)列1就緒隊(duì)列2就緒隊(duì)列3就緒隊(duì)列ns1s2s3sn至CPU至CPU至CPU至CPU（時(shí)間片：s1<s2<s3)特點(diǎn)：1）各個(gè)隊(duì)列賦予不同的優(yōu)先權(quán)，第一個(gè)隊(duì)列的優(yōu)先權(quán)最高，其余隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。2）各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也不相同。3）剛創(chuàng)建的進(jìn)程和因請(qǐng)求I/O未用完時(shí)間片的進(jìn)程排在最高優(yōu)先級(jí)隊(duì)列，在這個(gè)隊(duì)列中運(yùn)行1個(gè)時(shí)間片未完成的進(jìn)程排到下一個(gè)較低優(yōu)先級(jí)隊(duì)列。4）先調(diào)度優(yōu)先級(jí)高的隊(duì)列。僅當(dāng)該隊(duì)列空時(shí)，才調(diào)度次高優(yōu)先級(jí)隊(duì)列，以此類(lèi)推，第n個(gè)隊(duì)列進(jìn)程被調(diào)度時(shí)，必須是前n-1個(gè)隊(duì)列為空。5）既能使分時(shí)用戶作業(yè)得到滿意的響應(yīng)時(shí)間，又能使批處理用戶的作業(yè)獲得較合理的周轉(zhuǎn)時(shí)間。3死鎖3.1死鎖的概念 各并發(fā)進(jìn)程彼此互相等待對(duì)方所擁有的資源卻又在自身推進(jìn)之前不會(huì)釋放已有的資源，從而使各進(jìn)程都不能推進(jìn)的狀態(tài)即死鎖。死鎖的起因源于并發(fā)進(jìn)程的資源竟?fàn)?。產(chǎn)生死鎖的根本原因在于系統(tǒng)提供的資源個(gè)數(shù)少于并發(fā)進(jìn)程所要求的該類(lèi)資源數(shù)。顯然，由于資源的有限性，不可能為所有要求資源的進(jìn)程無(wú)限制地提供資源。

死鎖產(chǎn)生原因1）競(jìng)爭(zhēng)資源資源的類(lèi)型可剝奪資源：剝奪時(shí)僅終止占用進(jìn)程推進(jìn)。如主存、CPU。不可剝奪資源：一旦分配，不能強(qiáng)收回，只能由其自動(dòng)釋放。如打印機(jī)、磁帶機(jī)。競(jìng)爭(zhēng)不可剝奪資源

打印機(jī)輸入機(jī)進(jìn)程1進(jìn)程2競(jìng)爭(zhēng)臨時(shí)性資源（進(jìn)程通信）

2）進(jìn)程推進(jìn)順序（不安全區(qū)D）3.2死鎖產(chǎn)生的必要條件

1)

互斥條件系統(tǒng)使用臨界資源，各進(jìn)程不能同時(shí)使用

2)

部分分配條件（動(dòng)態(tài)分配）在運(yùn)行中按需分配資源

3)

保持和等待條件（循環(huán)等待）各進(jìn)程對(duì)資源的需求形成循環(huán)等待

4)

不可剝奪條件既不能強(qiáng)行剝奪其他進(jìn)程的資源

3.3死鎖的預(yù)防和解除解決死鎖的方法：鴕鳥(niǎo)政策：不采取任何措施，出現(xiàn)死鎖后再解除。如UNIX。假如系統(tǒng)中不允許死鎖發(fā)生，通常有兩種解決辦法：靜態(tài)解決辦法:系統(tǒng)事先采取措施，對(duì)進(jìn)程申請(qǐng)資源的要求加以限制，即預(yù)防死鎖。動(dòng)態(tài)解決辦法:在進(jìn)程運(yùn)行過(guò)程中提出資源申請(qǐng)時(shí)，系統(tǒng)加以檢測(cè)，決定是否分配資源，即避免死鎖。假如系統(tǒng)中允許發(fā)生死鎖，則需檢測(cè)死鎖是否發(fā)生，并在死鎖發(fā)生時(shí)加以解除。只要破壞死鎖四個(gè)必要條件之一，就可以解除死鎖。如：殺死死鎖的某個(gè)進(jìn)程。

1）預(yù)防死鎖限制“互斥條件”：不易有解決方案。限制“動(dòng)態(tài)分配”條件：采用靜態(tài)分配，效率低。限制“不可剝奪條件”：常見(jiàn)的做法。限制“請(qǐng)求與保持條件”：禁止已擁有資源的進(jìn)程再申請(qǐng)其它資源，蛻變?yōu)殪o態(tài)分配；或當(dāng)進(jìn)程提出新的資源申請(qǐng)時(shí)，暫時(shí)釋放當(dāng)前已經(jīng)占用的所有資源，只有當(dāng)新的資源申請(qǐng)成功時(shí)，才收回其原先占用的資源。約束多且效率低。尋求合理途徑來(lái)動(dòng)態(tài)地分配資源……？？資源有序分配法：將所有資源編號(hào)，對(duì)資源的請(qǐng)求只能按編號(hào)增加的原則進(jìn)行，這樣可以避免形成資源循環(huán)等待。缺點(diǎn)是可能資源編號(hào)的順序與需求順序不一致。如對(duì)哲學(xué)家吃面條問(wèn)題，若對(duì)所有的筷子編號(hào)，可以避免死鎖。i<j×2）避免死鎖基本思想：

允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，一次申請(qǐng)一部分資源。系統(tǒng)在進(jìn)行資源分配之前，先計(jì)算資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，便將資源分配給進(jìn)程；否則，進(jìn)程等待。安全狀態(tài)：指系統(tǒng)能按某種順序，如p1,p2,…,pn(安全序列)，來(lái)為每個(gè)進(jìn)程分配其所需資源，直至最大需求，使每個(gè)進(jìn)程都可順序完成。

如果系統(tǒng)無(wú)法找到這樣一個(gè)安全序列，則稱(chēng)系統(tǒng)處于不安全狀態(tài)。例：Dijkstra的銀行家算法(安全序列檢測(cè)算法)Dijkstra把系統(tǒng)比作一個(gè)占有有限資源的銀行家，雖然不能滿足所有借款人的最大需求總和，但可以滿足部分人的借款需求，待其還款后，又可以滿足其他人的需求。

①安全序列：即可以達(dá)到全部順利滿足各進(jìn)程資源要求的資源分配順序

②安全狀態(tài)：至少存在一個(gè)安全序列的狀態(tài)

③資源分配圖（資源分配矩陣）設(shè)有A～E五個(gè)進(jìn)程，系統(tǒng)資源為m1～m4，各進(jìn)程對(duì)各種資源的需求和分配情況可以用矩陣表示如下： 已分配矩陣 =最大分配矩陣-剩余需求矩陣

AllocationMaxNeed

M1M2M3M4A3011B0100C1110D1101E0000

M1M2M3M4A4111B0212C4210D1111E2110

M1M2M3M4A1100B0112C3100D0010E2110

未分配資源數(shù)= 系統(tǒng)資源數(shù) - 已分配資源數(shù)

Available（1，0，2，0）= r（6，3，4，2）-S（5，3，2，2）已分配矩陣 =最大分配矩陣-剩余需求矩陣

安全性算法： ①在Need中找一未標(biāo)記行，滿足每一元素小于等于Available，找不到轉(zhuǎn)④；②標(biāo)記找到的行，并將相應(yīng)進(jìn)程已占有的資源（Allocation中的相應(yīng)行）加到Available中； ③重復(fù)轉(zhuǎn)①；④如果所有行都已標(biāo)記，則系統(tǒng)是安全的，否則系統(tǒng)不安全；

銀行家算法：

設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Requesti［j］=K，表示進(jìn)程Pi需要K個(gè)Rj類(lèi)型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：

(1)如果Requesti［j］≤Need［i,j］，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。

(2)如果Requesti［j］≤Available［j］，便轉(zhuǎn)向步驟(3)；否則，表示尚無(wú)足夠資源，Pi須等待。

(3)系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：

Available［j］∶=Available［j］-Requesti［j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。

3)死鎖的檢測(cè)在允許發(fā)生死鎖的系統(tǒng)中，必須有對(duì)死鎖進(jìn)行檢測(cè)的方法。死鎖的檢測(cè)通常是定時(shí)進(jìn)行的，時(shí)間間隔的選擇很重要。選擇的間隔小，死鎖檢測(cè)程序的執(zhí)行會(huì)增加系統(tǒng)開(kāi)銷(xiāo)，間隔大，又不能及時(shí)檢測(cè)出死鎖。資源分配圖資源分配圖中有圓形及方框兩類(lèi)節(jié)點(diǎn)，分別表示進(jìn)程和資源。從資源到進(jìn)程的有向邊表示該資源已被進(jìn)程占用，從進(jìn)程到資源的有向邊表示進(jìn)程申請(qǐng)?jiān)?/p>