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

1.

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

1.

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

提交后備執(zhí)行完成SPOOLing作業(yè)調(diào)度SPOOLing進(jìn)程調(diào)度和交通控制作業(yè)調(diào)度：又稱宏觀調(diào)度或高級調(diào)度。把外存上處于后備隊列中的作2

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

進(jìn)程調(diào)度：微觀調(diào)度或低級調(diào)度。按照某種策略和方法選取一個處3

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

交換調(diào)度：中級調(diào)度。按照某種策略，將處于外存交換區(qū)中的重又4

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

5非搶占方式(Nonpreemptivemode)

一旦把CPU分配給某一進(jìn)程后,便讓它一直運行下去，直到進(jìn)程完成或發(fā)生某事件而阻塞時，才將CPU分給其它進(jìn)程。主要優(yōu)點是簡單、系統(tǒng)開銷小，但是一個進(jìn)程的運行往往可能導(dǎo)致多數(shù)進(jìn)程長期得不到服務(wù)。通常用在批處理系統(tǒng)中。搶占方式(Preemptivemode)允許調(diào)度程序基于某種策略（優(yōu)先級策略、時間片策略、短作業(yè)優(yōu)先等）剝奪現(xiàn)行進(jìn)程的CPU給其它進(jìn)程。通常用在分時系統(tǒng)和實時系統(tǒng)中，以便及時響應(yīng)各進(jìn)程的請求。

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

2）調(diào)度的時機(jī)——進(jìn)程并發(fā)執(zhí)行過程中何時實現(xiàn)CPU的切換 7 3）調(diào)度的策略——選擇進(jìn)程運行的依據(jù)。調(diào)度算法選擇多從處理器利用率、吞吐量、等待時間和響應(yīng)時間考慮。

了解：平均周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務(wù)的時間TS之比，即W=T/TS，稱為帶權(quán)周轉(zhuǎn)時間，而平均帶權(quán)周轉(zhuǎn)時間則可表示為: 3）調(diào)度的策略——選擇進(jìn)程運行的依據(jù)。了解：平均周轉(zhuǎn)時間作8 ◆先來先服務(wù)（FCFS）：按進(jìn)程進(jìn)入就緒隊列的先后來調(diào)度。特點：有利于長作業(yè)，不利于短作業(yè)；有利于CPU繁忙型，不利于I/O繁忙型； ◆短作業(yè)（進(jìn)程）優(yōu)先算法—SJ(P)F:每次調(diào)度時，從就緒隊列中找出下一個估計CPU執(zhí)行期最短的作業(yè)（進(jìn)程）優(yōu)先調(diào)度；特點：不利于長作業(yè)，有利于短作業(yè)；進(jìn)程的執(zhí)行時間預(yù)測困難；沒有考慮進(jìn)程實際的緊迫程度；

。

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

◆優(yōu)先級調(diào)度算法：每次調(diào)度時，從就緒隊列中找出優(yōu)先級最高的進(jìn)10

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

11

◆多級反饋隊列調(diào)度就緒進(jìn)程的種類：剛創(chuàng)建的進(jìn)程；已經(jīng)被調(diào)度執(zhí)行過，但還沒有執(zhí)行完，等待下一次調(diào)度；因請求I/O而阻塞，當(dāng)?shù)却蚪獬粏拘堰M(jìn)入就緒隊列。設(shè)置多個就緒隊列，第一級隊列的優(yōu)先級最高，但占用的時間片最短，各級隊列依次優(yōu)先級遞減，占用時間片遞增。 執(zhí)行進(jìn)程調(diào)度時，剛進(jìn)入就緒隊列的進(jìn)程先加入第一級隊列，獲得一個時間片，如時間片到而沒有完成，則將該進(jìn)程加入下一級。 分級調(diào)度可以使運行時間短進(jìn)程優(yōu)先得到調(diào)度，減少運行時間長進(jìn)程的調(diào)度次數(shù)。

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

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

打印機(jī)輸入機(jī)進(jìn)程1進(jìn)程2死鎖產(chǎn)生原因打印機(jī)輸入機(jī)進(jìn)程1進(jìn)程216競爭臨時性資源（進(jìn)程通信）

競爭臨時性資源（進(jìn)程通信）172）進(jìn)程推進(jìn)順序（不安全區(qū)D）2）進(jìn)程推進(jìn)順序（不安全區(qū)D）183.2死鎖產(chǎn)生的必要條件

1)

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

部分分配條件（動態(tài)分配）在運行中按需分配資源 3)

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

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

3.2死鎖產(chǎn)生的必要條件193.3死鎖的預(yù)防和解除解決死鎖的方法：鴕鳥政策：不采取任何措施，出現(xiàn)死鎖后再解除。如UNIX。假如系統(tǒng)中不允許死鎖發(fā)生，通常有兩種解決辦法：靜態(tài)解決辦法:系統(tǒng)事先采取措施，對進(jìn)程申請資源的要求加以限制，即預(yù)防死鎖。動態(tài)解決辦法:在進(jìn)程運行過程中提出資源申請時，系統(tǒng)加以檢測，決定是否分配資源，即避免死鎖。假如系統(tǒng)中允許發(fā)生死鎖，則需檢測死鎖是否發(fā)生，并在死鎖發(fā)生時加以解除。只要破壞死鎖四個必要條件之一，就可以解除死鎖。如：殺死死鎖的某個進(jìn)程。3.3死鎖的預(yù)防和解除201）預(yù)防死鎖限制“互斥條件”：不易有解決方案。限制“動態(tài)分配”條件：采用靜態(tài)分配，效率低。限制“不可剝奪條件”：常見的做法。限制“請求與保持條件”：禁止已擁有資源的進(jìn)程再申請其它資源，蛻變?yōu)殪o態(tài)分配；或當(dāng)進(jìn)程提出新的資源申請時，暫時釋放當(dāng)前已經(jīng)占用的所有資源，只有當(dāng)新的資源申請成功時，才收回其原先占用的資源。約束多且效率低。尋求合理途徑來動態(tài)地分配資源……？？1）預(yù)防死鎖21資源有序分配法：將所有資源編號，對資源的請求只能按編號增加的原則進(jìn)行，這樣可以避免形成資源循環(huán)等待。缺點是可能資源編號的順序與需求順序不一致。如對哲學(xué)家吃面條問題，若對所有的筷子編號，可以避免死鎖。i<j×資源有序分配法：將所有資源編號，對資源的請求只能按編號增加的222）避免死鎖基本思想：

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

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

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

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

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

AllocationMaxNeed

例：Dijkstra的銀行家算法(安全序列檢測算法)24

M1M2M3M4A3011B0100C1110D1101E0000

M1M2M3M4A4111B0212C4210D1111E2110

M1M2M3M4A1100B0112C3100D0010E2110

未分配資源數(shù)= 系統(tǒng)資源數(shù) - 已分配資源數(shù)Available（1，0，2，0）= r（6，3，4，2）-S（5，3，2，2）已分配矩陣 =最大分配矩陣-剩余需求矩陣

M1M2M3M4A3011B0100C1110D110125

安全性算法： ①在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)不安全；

安全性算法：26

銀行家算法：

設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requesti［j］=K，表示進(jìn)程Pi需要K個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：(1)如果Requesti［j］≤Need［i,j］，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。(2)如果Requesti［j］≤Available［j］，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。

銀行家算法：27

(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ù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。

(3)系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面283)死鎖的檢測在允許發(fā)生死鎖的系統(tǒng)中，必須有對死鎖進(jìn)行檢測的方法。死鎖的檢測通常是定時進(jìn)行的，時間間隔的選擇很重要。選擇的間隔小，死鎖檢測程序的執(zhí)行會增加系統(tǒng)開銷，間隔大，又不能及時檢測出死鎖。資源分配圖資源分配圖中有圓形及方框兩類節(jié)點，分別表示進(jìn)程和資源。從資源到進(jìn)程的有向邊表示該資源已被進(jìn)程占用，從進(jìn)程到資源的有向邊表示進(jìn)程申請該資源。3)死鎖的檢測資源分配圖29死鎖定理一種資源分配狀態(tài)為死鎖狀態(tài)的充要條件是：當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的。(a)(b)P1(c)P1P2P1P2P2死鎖定理(a)(b)P1(c)P1P2P1P2P2304）死鎖的解除在允許發(fā)生死鎖的系統(tǒng)中，當(dāng)檢測到死鎖時，應(yīng)設(shè)法解除死鎖。解除死鎖的一種方案是從其它進(jìn)程剝奪資源給死鎖進(jìn)程，直至死鎖解除。當(dāng)然，系統(tǒng)必須付出一定代價。另一種方案是撤消進(jìn)程。撤消進(jìn)程時，可選擇撤消部分進(jìn)程的方案，也可以將全部死鎖進(jìn)程撤消，這種方案會使系統(tǒng)付出很大代價。如：Windows任務(wù)管理器下撤銷進(jìn)程4）死鎖的解除311.

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

1.

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

提交后備執(zhí)行完成SPOOLing作業(yè)調(diào)度SPOOLing進(jìn)程調(diào)度和交通控制作業(yè)調(diào)度：又稱宏觀調(diào)度或高級調(diào)度。把外存上處于后備隊列中的作33

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

進(jìn)程調(diào)度：微觀調(diào)度或低級調(diào)度。按照某種策略和方法選取一個處34

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

交換調(diào)度：中級調(diào)度。按照某種策略，將處于外存交換區(qū)中的重又35

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

36非搶占方式(Nonpreemptivemode)

一旦把CPU分配給某一進(jìn)程后,便讓它一直運行下去，直到進(jìn)程完成或發(fā)生某事件而阻塞時，才將CPU分給其它進(jìn)程。主要優(yōu)點是簡單、系統(tǒng)開銷小，但是一個進(jìn)程的運行往往可能導(dǎo)致多數(shù)進(jìn)程長期得不到服務(wù)。通常用在批處理系統(tǒng)中。搶占方式(Preemptivemode)允許調(diào)度程序基于某種策略（優(yōu)先級策略、時間片策略、短作業(yè)優(yōu)先等）剝奪現(xiàn)行進(jìn)程的CPU給其它進(jìn)程。通常用在分時系統(tǒng)和實時系統(tǒng)中，以便及時響應(yīng)各進(jìn)程的請求。

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

2）調(diào)度的時機(jī)——進(jìn)程并發(fā)執(zhí)行過程中何時實現(xiàn)CPU的切換 38 3）調(diào)度的策略——選擇進(jìn)程運行的依據(jù)。調(diào)度算法選擇多從處理器利用率、吞吐量、等待時間和響應(yīng)時間考慮。

了解：平均周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務(wù)的時間TS之比，即W=T/TS，稱為帶權(quán)周轉(zhuǎn)時間，而平均帶權(quán)周轉(zhuǎn)時間則可表示為: 3）調(diào)度的策略——選擇進(jìn)程運行的依據(jù)。了解：平均周轉(zhuǎn)時間作39 ◆先來先服務(wù)（FCFS）：按進(jìn)程進(jìn)入就緒隊列的先后來調(diào)度。特點：有利于長作業(yè)，不利于短作業(yè)；有利于CPU繁忙型，不利于I/O繁忙型； ◆短作業(yè)（進(jìn)程）優(yōu)先算法—SJ(P)F:每次調(diào)度時，從就緒隊列中找出下一個估計CPU執(zhí)行期最短的作業(yè)（進(jìn)程）優(yōu)先調(diào)度；特點：不利于長作業(yè)，有利于短作業(yè)；進(jìn)程的執(zhí)行時間預(yù)測困難；沒有考慮進(jìn)程實際的緊迫程度；

。

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

◆優(yōu)先級調(diào)度算法：每次調(diào)度時，從就緒隊列中找出優(yōu)先級最高的進(jìn)41

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

42

◆多級反饋隊列調(diào)度就緒進(jìn)程的種類：剛創(chuàng)建的進(jìn)程；已經(jīng)被調(diào)度執(zhí)行過，但還沒有執(zhí)行完，等待下一次調(diào)度；因請求I/O而阻塞，當(dāng)?shù)却蚪獬粏拘堰M(jìn)入就緒隊列。設(shè)置多個就緒隊列，第一級隊列的優(yōu)先級最高，但占用的時間片最短，各級隊列依次優(yōu)先級遞減，占用時間片遞增。 執(zhí)行進(jìn)程調(diào)度時，剛進(jìn)入就緒隊列的進(jìn)程先加入第一級隊列，獲得一個時間片，如時間片到而沒有完成，則將該進(jìn)程加入下一級。 分級調(diào)度可以使運行時間短進(jìn)程優(yōu)先得到調(diào)度，減少運行時間長進(jìn)程的調(diào)度次數(shù)。

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

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

打印機(jī)輸入機(jī)進(jìn)程1進(jìn)程2死鎖產(chǎn)生原因打印機(jī)輸入機(jī)進(jìn)程1進(jìn)程247競爭臨時性資源（進(jìn)程通信）

競爭臨時性資源（進(jìn)程通信）482）進(jìn)程推進(jìn)順序（不安全區(qū)D）2）進(jìn)程推進(jìn)順序（不安全區(qū)D）493.2死鎖產(chǎn)生的必要條件

1)

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

部分分配條件（動態(tài)分配）在運行中按需分配資源 3)

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

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

3.2死鎖產(chǎn)生的必要條件503.3死鎖的預(yù)防和解除解決死鎖的方法：鴕鳥政策：不采取任何措施，出現(xiàn)死鎖后再解除。如UNIX。假如系統(tǒng)中不允許死鎖發(fā)生，通常有兩種解決辦法：靜態(tài)解決辦法:系統(tǒng)事先采取措施，對進(jìn)程申請資源的要求加以限制，即預(yù)防死鎖。動態(tài)解決辦法:在進(jìn)程運行過程中提出資源申請時，系統(tǒng)加以檢測，決定是否分配資源，即避免死鎖。假如系統(tǒng)中允許發(fā)生死鎖，則需檢測死鎖是否發(fā)生，并在死鎖發(fā)生時加以解除。只要破壞死鎖四個必要條件之一，就可以解除死鎖。如：殺死死鎖的某個進(jìn)程。3.3死鎖的預(yù)防和解除511）預(yù)防死鎖限制“互斥條件”：不易有解決方案。限制“動態(tài)分配”條件：采用靜態(tài)分配，效率低。限制“不可剝奪條件”：常見的做法。限制“請求與保持條件”：禁止已擁有資源的進(jìn)程再申請其它資源，蛻變?yōu)殪o態(tài)分配；或當(dāng)進(jìn)程提出新的資源申請時，暫時釋放當(dāng)前已經(jīng)占用的所有資源，只有當(dāng)新的資源申請成功時，才收回其原先占用的資源。約束多且效率低。尋求合理途徑來動態(tài)地分配資源……？？1）預(yù)防死鎖52資源有序分配法：將所有資源編號，對資源的請求只能按編號增加的原則進(jìn)行，這樣可以避免形成資源循環(huán)等待。缺點是可能資源編號的順序與需求順序不一致。如對哲學(xué)家吃面條問題，若對所有的筷子編號，可以避免死鎖。i<j×資源有序分配法：將所有資源編號，對資源的請求只能按編號增加的532）避免死鎖基本思想：

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

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

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

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

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

AllocationMaxNeed

例：Dijkstra的銀行家算法(安全序列檢測算法)55

M1M2M3M4A3011B0100C1110D1101E0000

M1M2M3M4A4111B0212C4210D1111E2110

M1M2M3M4A1100B0112C3100D0010E2110

未分配資源數(shù)= 系統(tǒng)資源數(shù) - 已分配資源數(shù)Available（1，0，2，0）= r（6，3，4，2）-S（5，3，2，2）已分配矩陣 =最大分配矩陣-剩余需求矩陣

M1M2M3M4A3011B0100C1110D110156

安全性算法： ①在Need中找一未標(biāo)記行，滿足每一元素小于等于Available，找不到轉(zhuǎn)④