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

1、第三章 處理機(jī)調(diào)度與死鎖 【教學(xué)目的】了解處理機(jī)調(diào)度的基本概念、調(diào)度算法和類型及死鎖的概念、產(chǎn)生條件及檢測(cè)與解除。 【教學(xué)重點(diǎn)】1、處理機(jī)調(diào)度原理及算法。2、死鎖的產(chǎn)生原因及檢測(cè)與解除。 【分配課時(shí)】進(jìn)度計(jì)劃6學(xué)時(shí)第三章 處理機(jī)調(diào)度與死鎖3.1 處理機(jī)調(diào)度的基本概念3.2 進(jìn)程調(diào)度算法3.3 實(shí)時(shí)調(diào)度3.4 多處理機(jī)系統(tǒng)中的調(diào)度3.5 產(chǎn)生死鎖的原因和必要條件3.6 預(yù)防死鎖的方法和死鎖避免3.7 死鎖的檢測(cè)和解除第一節(jié)第一節(jié)調(diào)度的類型和模型調(diào)度的類型和模型一、 調(diào)度類型1、高級(jí)調(diào)度（High level Scheduling）（或作業(yè)/長(zhǎng)程/接納調(diào)度）（1）定義 把外存上處于后備隊(duì)列中的那些

2、作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后，再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。在批處理系統(tǒng)中，是先駐留在外存上的，因此需要有作業(yè)調(diào)度，以將它們分批裝入內(nèi)存。在分時(shí)系統(tǒng)中，為了能及時(shí)響應(yīng)，用戶通過鍵盤輸入的命令或數(shù)據(jù)等，都是直接送入內(nèi)存，因而無需配置作業(yè)調(diào)度。（2）決定作業(yè)調(diào)度的兩個(gè)因素 接納多少個(gè)作業(yè) 作業(yè)調(diào)度每次要接納多少個(gè)作業(yè)進(jìn)入內(nèi)存，取決于多道程序度（Degree of Multiprogramming）,即允許有多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。 接納哪些作業(yè) 應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存，將取決于所采用的調(diào)度算法。最簡(jiǎn)單的是先來先服務(wù)調(diào)度算法，較常用的一種是短作業(yè)優(yōu)先調(diào)度算

3、法，還有基于作業(yè)優(yōu)先權(quán)的調(diào)度算法、響應(yīng)比高者優(yōu)先的調(diào)度算法等。第一節(jié)第一節(jié)調(diào)度的類型和模型調(diào)度的類型和模型 2、低級(jí)調(diào)度（Low Level Scheduling） 低級(jí)調(diào)度通常又稱為進(jìn)程調(diào)度、短程調(diào)度（Short-Term Scheduling）在三種類型的OS中都必須配置這級(jí)調(diào)度。進(jìn)程調(diào)度可采取下述兩種方法： (1)非搶占方式（Non-Preemptive Mode） 采取調(diào)度方式時(shí)，一旦處理機(jī)分配某進(jìn)程后，便讓該進(jìn)程一直執(zhí)行，直至該進(jìn)程完成或發(fā)生某事件而被阻塞時(shí)，才再把處理機(jī)分配給其它進(jìn)程，決不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)。 這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單、系統(tǒng)開銷小，適用大于多數(shù)的

4、批處理系統(tǒng)環(huán)境。但它難于滿足緊急任務(wù)的要求。(2)搶占方式（Preemptive Mode） 這種調(diào)度方式，允許調(diào)度程序根據(jù)某種原則，去停止某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)，重新分陪另一進(jìn)程。第一節(jié)第一節(jié)調(diào)度的類型和模型調(diào)度的類型和模型 搶占的原則有： 時(shí)間片原則 各進(jìn)程按時(shí)間片運(yùn)行，當(dāng)一個(gè)時(shí)間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)姓調(diào)度。這種原則適用于分時(shí)系統(tǒng)、大多數(shù)實(shí)時(shí)系統(tǒng)，以及要求較高的批處理系統(tǒng)。 優(yōu)先權(quán)原則 通常是對(duì)一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。當(dāng)這種作業(yè)到達(dá)時(shí)，如果其優(yōu)先權(quán)比正在執(zhí)行進(jìn)程的優(yōu)先權(quán)高，便停止正在執(zhí)行的進(jìn)程，將處理機(jī)分配給優(yōu)先權(quán)高的進(jìn)程，使之執(zhí)行。短

5、作業(yè)（進(jìn)程）優(yōu)先原則 當(dāng)新到達(dá)的作業(yè)（進(jìn)程）比正在執(zhí)行的作業(yè)（進(jìn)程）明顯地短時(shí)，將剝奪長(zhǎng)作業(yè)（進(jìn)程）的執(zhí)行，將處理機(jī)分配給作業(yè)（進(jìn)程），使之優(yōu)先執(zhí)行。 第一節(jié)第一節(jié)調(diào)度的類型和模型調(diào)度的類型和模型 3、中級(jí)調(diào)度 又稱中程調(diào)度 (1)引入中級(jí)調(diào)度的目的 是為了提高內(nèi)存的利用率和系統(tǒng)吐量。(2)定義 應(yīng)使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存空間，而將它們調(diào)至外存上去等待，稱此時(shí)的進(jìn)程狀態(tài)為就緒駐外存狀態(tài)，或掛起狀態(tài)。當(dāng)這些進(jìn)程重又舉備運(yùn)行條件，且內(nèi)存又稍有空閑時(shí)，由中級(jí)調(diào)度決定，將外存上的那些重又具備運(yùn)動(dòng)條件的就緒進(jìn)程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒態(tài)，掛在就緒隊(duì)列上，等待進(jìn)程調(diào)度。 第一節(jié)第

6、一節(jié)調(diào)度的類型和模型調(diào)度的類型和模型 在上述三種調(diào)度中，進(jìn)程調(diào)度的運(yùn)行頻率最高，在分時(shí)系統(tǒng)中通常是10-100ms便進(jìn)行一次進(jìn)程調(diào)度，因而進(jìn)程調(diào)度算法不能太復(fù)雜，以免占用太多的CPU時(shí)間。作業(yè)調(diào)度往往是發(fā)生在一個(gè)（批）作業(yè)運(yùn)行完畢，退出系統(tǒng)又需要重新調(diào)入一個(gè)（批）作業(yè)進(jìn)入內(nèi)存時(shí)，故作業(yè)調(diào)度的周期校長(zhǎng)，大約幾分鐘一次。因而也允許作業(yè)調(diào)度算法花費(fèi)較多時(shí)間，中級(jí)調(diào)度的運(yùn)行頻率基本上介入于上述兩種調(diào)度之間。第一節(jié)第一節(jié)調(diào)度的類型和模型調(diào)度的類型和模型二、 調(diào)度隊(duì)列模型1、僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 在分時(shí)系統(tǒng)中通常僅設(shè)置了進(jìn)程調(diào)度。用戶鍵入的命令和數(shù)據(jù)，都直接送入內(nèi)存。對(duì)于命令，由OS為之建立一個(gè)進(jìn)程

7、，并將它排在就緒隊(duì)列的末尾，然后按時(shí)間片輪轉(zhuǎn)方式執(zhí)行。每個(gè)進(jìn)程執(zhí)行時(shí)，都可能出現(xiàn)這樣三種可能。（1）該任務(wù)在該時(shí)間片內(nèi)已經(jīng)完成，該進(jìn)程釋放處理機(jī)后進(jìn)入完成狀態(tài)；（2）任務(wù)在本其對(duì)應(yīng)的時(shí)間內(nèi)尚未完成，OS便將任務(wù)放在就緒隊(duì)列的后面；（3）在執(zhí)行期間，進(jìn)程因某事件而被阻塞后，OS將它們放入阻塞隊(duì)列。 1.進(jìn)程調(diào)度模型 1) 1)只有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型只有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型圖 3 - 1 僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型2、具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型（見P99圖4-2）（1）在OS中不僅引入了進(jìn)程調(diào)度，而且還進(jìn)入了作業(yè)調(diào)度。后者從外存的后備隊(duì)列中選擇一批作業(yè)調(diào)入內(nèi)存，為之創(chuàng)建進(jìn)程后，送入就

8、緒隊(duì)列；（2）在OS中設(shè)置多個(gè)阻塞隊(duì)列。當(dāng)系統(tǒng)中僅設(shè)置一個(gè)阻塞隊(duì)列時(shí)，可能會(huì)使該隊(duì)列很長(zhǎng)，尤其當(dāng)系統(tǒng)較大時(shí)，該隊(duì)列中可能數(shù)百個(gè)進(jìn)程。為了提高隊(duì)列的操作效率，通常都設(shè)置若干個(gè)（1，2,.,n）阻塞隊(duì)列，每個(gè)隊(duì)列對(duì)應(yīng)于一種引起進(jìn)程阻塞的事件。 2)具有高低級(jí)調(diào)度的調(diào)度隊(duì)列模型圖 3-2 具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型3、同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型 當(dāng)在OS中引入中級(jí)調(diào)度后，可把就緒態(tài)分為內(nèi)存就緒狀態(tài)、外存就緒狀態(tài)?？砂炎枞麪顟B(tài)進(jìn)一步分成內(nèi)存阻塞和外存阻塞兩種狀態(tài)。在調(diào)出操作的情況下，可使內(nèi)存就緒轉(zhuǎn)變?yōu)橥獯婢途w、內(nèi)存阻塞轉(zhuǎn)變?yōu)橥獯孀枞?；在中?jí)調(diào)度的作用下，外存就緒轉(zhuǎn)變?yōu)閮?nèi)存就緒。3)具有三級(jí)調(diào)

9、度的調(diào)度隊(duì)列模型圖 3-3 具有三級(jí)調(diào)度時(shí)的調(diào)度隊(duì)列模型三、選擇調(diào)度方式和算法的若干準(zhǔn)則 面向用戶的準(zhǔn)則：周轉(zhuǎn)時(shí)間短；響應(yīng)時(shí)間快；截止時(shí)間的保證；優(yōu)先權(quán)準(zhǔn)則 面向系統(tǒng)的準(zhǔn)則：系統(tǒng)吞吐量高；處理機(jī)利用率好；各類資源的平衡利用1、面向用戶的準(zhǔn)則（1）周轉(zhuǎn)時(shí)間短通常把周轉(zhuǎn)時(shí)間作為評(píng)價(jià)批處理系統(tǒng)的性能、選擇作業(yè)調(diào)度方法與算法的準(zhǔn)則。定義是指從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止這段時(shí)間間隔（稱為作業(yè)周轉(zhuǎn)時(shí)間）。它包括：作業(yè)在外存后備隊(duì)列上等待（作業(yè)）調(diào)度的時(shí)間；進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間；進(jìn)程在CPU上執(zhí)行的時(shí)間；等待I/O操作完成的時(shí)間。 其中，第（2）、（3）、（4）項(xiàng)在一個(gè)作業(yè)處理過程中，

10、可能發(fā)生多次。 對(duì)每個(gè)用戶而言，作業(yè)的周轉(zhuǎn)時(shí)間最短。但作為計(jì)算計(jì)系統(tǒng)的管理者，希望平均周轉(zhuǎn)時(shí)間最短；這不僅會(huì)有效地提高資源利用率，而且還可使大多數(shù)用戶滿意。平均周轉(zhuǎn)時(shí)間： T= 帶權(quán)周轉(zhuǎn)時(shí)間:作業(yè)周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供的實(shí)際服務(wù)時(shí)間Ts之比，即W=T/Ts稱為。而平均帶周轉(zhuǎn)時(shí)間可表示為：W= （2）響應(yīng)時(shí)間快響應(yīng)時(shí)間是從用戶通過鍵盤提交一個(gè)請(qǐng)求開始，直到在屏幕上顯示出結(jié)果為止的一段時(shí)間間隔。它包括：（1）從鍵盤輸入的要求信息傳送到處理機(jī)的時(shí)間；（2）處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間；（3）將所行成的響應(yīng)回送到終端顯示器的時(shí)間；（3）截止時(shí)間的保證它是用來評(píng)價(jià)實(shí)時(shí)系統(tǒng)性的重要指標(biāo)，因而是選擇實(shí)時(shí)

11、調(diào)度算法的重要準(zhǔn)則。定義 截止時(shí)間：指某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間，對(duì)于嚴(yán)格的實(shí)時(shí)系統(tǒng)，其調(diào)度方式和調(diào)度算法必須保證這點(diǎn)。否則將可能引起難以預(yù)料的后果。（4）優(yōu)先權(quán)準(zhǔn)則 讓緊急的作業(yè)，得到及時(shí)的處理。第二節(jié)第二節(jié)調(diào)度算法調(diào)度算法 調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法，對(duì)于不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法。調(diào)度算法 先進(jìn)先出(FIFO)算法 最短CPU運(yùn)行期優(yōu)先調(diào)度算法 最高優(yōu)先權(quán)優(yōu)先調(diào)度算法 輪轉(zhuǎn)法 多級(jí)反饋隊(duì)列 一、先來先服務(wù)調(diào)度算法一、先來先服務(wù)（FCFS）調(diào)度算法1、原理 當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度是從后備作業(yè)隊(duì)列中，選擇一

12、個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。 在進(jìn)程調(diào)度中，采用FCFS調(diào)度算法時(shí)，每次調(diào)度是從就緒隊(duì)列中，選擇一個(gè)最先進(jìn)入該進(jìn)程，把處理分配給它，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完或發(fā)生某事件阻塞后，才放棄處理機(jī)。2、優(yōu)缺點(diǎn)（1）FCFS算法比較有利于作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。 下表列出了A、B、C、D四個(gè)作業(yè)分別到達(dá)系統(tǒng)的時(shí)間、要求服務(wù)的時(shí)間、開始執(zhí)行的時(shí)間及各自的完成的時(shí)間，并計(jì)算出各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。從上表可以看出：其中短作業(yè)C的帶權(quán)周轉(zhuǎn)時(shí)間競(jìng)高達(dá)100，這是不能容忍的；而長(zhǎng)作業(yè)D的帶權(quán)周轉(zhuǎn)時(shí)間僅為1.99。據(jù)此可知：（

13、2）FCFS調(diào)度算法有利于CPU繁忙型的作業(yè)，而不利于I/O繁忙型的作業(yè)進(jìn)程。 CPU繁忙型作業(yè)：是指該類作業(yè)需要大量的CPU時(shí)間進(jìn)行計(jì)算，而很少請(qǐng)求I/O。通常的科學(xué)計(jì)算便屬于CPU繁忙行作業(yè)。I/O繁忙行作業(yè)：是指CPU進(jìn)行處理時(shí)，又需頻繁地請(qǐng)求I/O，而每次I/O的操作時(shí)間卻又很短。目前的大多數(shù)的事務(wù)處理，都屬于I/O繁忙行作業(yè)。1.先進(jìn)先出(FIFO)算法 該算法總是把處理機(jī)分配給最先進(jìn)入就緒隊(duì)列的進(jìn)程，一個(gè)進(jìn)程一旦分得處理機(jī)，便執(zhí)行下去，直到該進(jìn)程完成或阻塞時(shí)，才釋放處理機(jī)。 優(yōu)點(diǎn):實(shí)現(xiàn)簡(jiǎn)單. 缺點(diǎn):沒考慮進(jìn)程的優(yōu)先級(jí) 2.最短CPU運(yùn)行期優(yōu)先調(diào)度算法 該算法從就緒隊(duì)列中選出“下一個(gè)

14、CPU執(zhí)行期”最短的進(jìn)程，為之分配處理機(jī)。 該算法雖可獲得較好的調(diào)度性能，但難以準(zhǔn)確地知道下一個(gè)CPU執(zhí)行期，而只能根據(jù)每一個(gè)進(jìn)行的執(zhí)行歷史來預(yù)測(cè)。圖 3-4 FCFS和SJF調(diào)度算法的性能 3. FCFS和SJF的性能比較優(yōu)點(diǎn)（1）短作業(yè)（SJF）的調(diào)度算法可以照顧到實(shí)際上在所有作業(yè)中占很大比例的短作業(yè)，使它能比長(zhǎng)作業(yè)優(yōu)先執(zhí)行。 （2）SJF調(diào)度算法能有效地降低作業(yè)的平均等待時(shí)間和提高系統(tǒng)的吐量。缺點(diǎn)（1）該算法對(duì)長(zhǎng)作業(yè)非常不利 來的）短作業(yè)（進(jìn)程），將致使長(zhǎng)作業(yè)（進(jìn)程）得不到調(diào)度。（2）該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)（進(jìn)程），回得到及時(shí)處理；（3）由于作業(yè)（進(jìn)程）的

15、長(zhǎng)短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定，而用戶又可能會(huì)有意或無意地縮短其作業(yè)的估計(jì)執(zhí)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。一、優(yōu)先權(quán)調(diào)度算法的類型 （1）非搶占式優(yōu)先權(quán)算法 （2）搶占式優(yōu)先權(quán)調(diào)度算法 4.最高優(yōu)先權(quán)優(yōu)先調(diào)度算法二、優(yōu)先權(quán)的類型（1）靜態(tài)優(yōu)先權(quán) 靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，切規(guī)定它在進(jìn)程的整個(gè)運(yùn)行期間保持不便，。一般，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來表示。確定進(jìn)程優(yōu)先權(quán)的依據(jù)是： 進(jìn)程類型。 進(jìn)程對(duì)資源的需求。 如進(jìn)程的估計(jì)執(zhí)行時(shí)間及內(nèi)存需要量少的進(jìn)程，應(yīng)賦予較高的優(yōu)先權(quán)。 優(yōu)缺點(diǎn) 靜態(tài)優(yōu)先權(quán)法簡(jiǎn)單易行、系統(tǒng)開銷小。 但不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)（進(jìn)

16、程），長(zhǎng)期沒有調(diào)度的情況，因此，僅在要求不太高的系統(tǒng)中，才使用靜態(tài)優(yōu)先權(quán)。（2）動(dòng)態(tài)優(yōu)先權(quán) 動(dòng)態(tài)優(yōu)先權(quán)是指在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，可以隨進(jìn)程的推進(jìn)而改變，以變獲得更好的性能。 5.高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先權(quán)的變化規(guī)律可描述為： 由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為： 由上式可以看出：（1）如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)；（2）當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，因而實(shí)現(xiàn)了先來先服務(wù)；（3）對(duì)于長(zhǎng)作業(yè)，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先權(quán)便可升到很高，從而也可獲得

17、處理機(jī)。 該算法既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后順序，也不會(huì)使作業(yè)長(zhǎng)期得不到服務(wù)。因此，該算法實(shí)現(xiàn)了一種較好的折衷。當(dāng)然，再利用該算法時(shí)，每要進(jìn)行調(diào)度之前，都需先進(jìn)行響應(yīng)應(yīng)比的計(jì)算，這會(huì)增加系統(tǒng)的開銷3.2練習(xí)練習(xí)假如有四道作業(yè)，它們的進(jìn)入時(shí)間和運(yùn)行時(shí)間由下表給出，假如有四道作業(yè)，它們的進(jìn)入時(shí)間和運(yùn)行時(shí)間由下表給出，在單道程序環(huán)境下，分別填寫先來先服務(wù)、短作業(yè)優(yōu)先和高響在單道程序環(huán)境下，分別填寫先來先服務(wù)、短作業(yè)優(yōu)先和高響應(yīng)比優(yōu)先調(diào)度算法的完成時(shí)間和周轉(zhuǎn)時(shí)間，并求出平均周轉(zhuǎn)時(shí)應(yīng)比優(yōu)先調(diào)度算法的完成時(shí)間和周轉(zhuǎn)時(shí)間，并求出平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。間和平均帶權(quán)周轉(zhuǎn)時(shí)間。作業(yè)作業(yè)號(hào)號(hào)進(jìn)入

18、時(shí)間進(jìn)入時(shí)間(時(shí)時(shí))運(yùn)行時(shí)間運(yùn)行時(shí)間(小時(shí)小時(shí))FCFSSJF完成時(shí)完成時(shí)間間(時(shí)時(shí))周轉(zhuǎn)時(shí)周轉(zhuǎn)時(shí)間間(小時(shí)小時(shí))完成時(shí)完成時(shí)間間(時(shí)時(shí))周轉(zhuǎn)時(shí)周轉(zhuǎn)時(shí)間間(小時(shí)小時(shí))110:000.4210:101310:200.6410:300.26. 輪轉(zhuǎn)法 在通常的輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)原則，排成一個(gè)隊(duì)列，每次調(diào)度時(shí)把CPU分配給對(duì)手進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的大小幾ms到幾百ms。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，有一個(gè)計(jì)時(shí)器發(fā)出時(shí)中斷，調(diào)度程序便據(jù)此信號(hào)來停止該進(jìn)程的執(zhí)行并將它送就緒隊(duì)列的末尾，等待下一次執(zhí)行；然后，把處理機(jī)分配給就緒隊(duì)列中新的對(duì)手進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣

19、就可以保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間（人所能接受的等待時(shí)間）內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。時(shí)間片選擇問題時(shí)間片選擇問題： 固定時(shí)間片 可變時(shí)間片時(shí)間片大小的確定時(shí)間片大小的確定 在時(shí)間片輪轉(zhuǎn)算法中，時(shí)間片的大小對(duì)計(jì)算機(jī)性能有很大影響。如果時(shí)間片太大，大到每個(gè)進(jìn)程都能在該時(shí)間片內(nèi)執(zhí)行完畢，則時(shí)間片輪轉(zhuǎn)算法邊退出為FCFS算法，因而獲得令用戶滿意的響應(yīng)時(shí)間。（1）系統(tǒng)對(duì)響應(yīng)時(shí)間的要求 數(shù)目N和時(shí)間片q成比例，即T=Nq,因此在用戶（進(jìn)程）數(shù)一定時(shí)，時(shí)間作為分時(shí)系統(tǒng)首先就是必須滿足系統(tǒng)對(duì)響應(yīng)時(shí)間的要求。由于響應(yīng)時(shí)間T直接與用戶（進(jìn)程）片的長(zhǎng)短將正比于系統(tǒng)所要求的響應(yīng)時(shí)間。（2）就緒

20、隊(duì)列中進(jìn)程的數(shù)目（3）系統(tǒng)的處理能力：是必須保證用戶鍵入的常用命令能在一個(gè)時(shí)間片內(nèi)處理完畢，否則將無法保證得到滿意的響應(yīng)時(shí)間 1)簡(jiǎn)單輪轉(zhuǎn)法的調(diào)度模型2)多隊(duì)列反饋調(diào)度算法 將就緒隊(duì)列分為N級(jí)，每個(gè)就緒隊(duì)列分配給不同的時(shí)間片，隊(duì)列級(jí)別越高，時(shí)間越小，級(jí)別越小，時(shí)間片越大，最后一級(jí)采用時(shí)間片輪轉(zhuǎn)，其他隊(duì)列采用先進(jìn)先出； 系統(tǒng)從第一級(jí)調(diào)度，當(dāng)?shù)谝患?jí)為空時(shí)，系統(tǒng)轉(zhuǎn)向第二個(gè)隊(duì)列，.當(dāng)運(yùn)行進(jìn)程用完一個(gè)時(shí)間片，放棄CPU時(shí)，進(jìn)入下一級(jí)隊(duì)列；等待進(jìn)程被喚醒時(shí)，進(jìn)入原來的就緒隊(duì)列；當(dāng)進(jìn)程第一次就緒時(shí)，進(jìn)入第一級(jí)隊(duì)列 * 首先系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列* 每個(gè)就緒隊(duì)列分配給不同時(shí)間片，優(yōu)先級(jí)高的為第一級(jí)隊(duì)列，時(shí)間片

21、最小，隨著隊(duì)列級(jí)別的降低，時(shí)間片加大* 各個(gè)隊(duì)列按照先進(jìn)先出調(diào)度算法* 一個(gè)新進(jìn)程就緒后進(jìn)入第一級(jí)隊(duì)列* 進(jìn)程由于等待而放棄CPU后，進(jìn)入等待隊(duì)列，一旦等待的事件發(fā)生，則回到原來的就緒隊(duì)列* 當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒時(shí)，可以搶占CPU，被搶占進(jìn)程回到原來一級(jí)就緒隊(duì)列末尾* 當(dāng)?shù)谝患?jí)隊(duì)列空時(shí)，就去調(diào)度第二級(jí)隊(duì)列，如此類推* 當(dāng)時(shí)間片到后，進(jìn)程放棄CPU，回到下一級(jí)隊(duì)列 3)多隊(duì)列反饋調(diào)度算法8.進(jìn)程調(diào)度的時(shí)機(jī)當(dāng)一個(gè)進(jìn)程運(yùn)行完畢，或由于某種錯(cuò)誤而終止運(yùn)行當(dāng)一個(gè)進(jìn)程在運(yùn)行中處于等待狀態(tài)（等待I/O）分時(shí)系統(tǒng)中時(shí)間片到當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒（可搶占式） 例如：新創(chuàng)建一個(gè)進(jìn)程，一個(gè)等待進(jìn)程變成

22、就緒在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語(yǔ)操作（P操作，阻塞原語(yǔ)，喚醒原語(yǔ)）何時(shí)切換進(jìn)程 只要OS取得對(duì)CPU的控制，進(jìn)程切換就可能發(fā)生，如:超級(jí)用戶調(diào)用 來自程序的顯式請(qǐng)求來自程序的顯式請(qǐng)求 ( (如：打開文件如：打開文件) )，該，該進(jìn)程通常會(huì)被阻塞進(jìn)程通常會(huì)被阻塞陷阱 最末一條指令導(dǎo)致出錯(cuò)，會(huì)引起進(jìn)程移至退最末一條指令導(dǎo)致出錯(cuò)，會(huì)引起進(jìn)程移至退出狀態(tài)出狀態(tài)中斷 外部因素影響當(dāng)前指令的執(zhí)行，控制被轉(zhuǎn)移外部因素影響當(dāng)前指令的執(zhí)行，控制被轉(zhuǎn)移至至IHIH（中斷處理程序）（中斷處理程序）9.引起進(jìn)程調(diào)度的原因 正在執(zhí)行的進(jìn)程執(zhí)行完畢或因發(fā)生某事件而不能再繼續(xù)執(zhí)行； 執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求

23、而暫停執(zhí)行； 在進(jìn)程通信或同步過程中執(zhí)行了某種原語(yǔ)操作如P操作、阻塞、掛起原語(yǔ)等； 在可剝奪式調(diào)度中，有比當(dāng)前進(jìn)程優(yōu)先權(quán)更高的進(jìn)程進(jìn)入就緒隊(duì)列； 在時(shí)間片輪轉(zhuǎn)法中，時(shí)間片完。 通常系統(tǒng)是按先來先服務(wù)或優(yōu)先權(quán)形式來組織調(diào)度隊(duì)列。 10.進(jìn)程調(diào)度算法 其中，RQ為就緒隊(duì)列指針，EP為運(yùn)行隊(duì)列指針。3.3 3.3 實(shí)實(shí) 時(shí)時(shí) 調(diào)調(diào) 度度 1.實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件 提供必要的信息(就緒時(shí)間、截止時(shí)間、處理時(shí)間、資源優(yōu)先級(jí)) 系統(tǒng)處理能力強(qiáng) 采用搶占式調(diào)度機(jī)制 具有快速切換機(jī)制： 具有快速響應(yīng)外部中斷的能力； 快速的任務(wù)分派：2.實(shí)時(shí)調(diào)度算法的分類 1)非搶占式調(diào)度算法非搶占式調(diào)

24、度算法: 非搶占式輪轉(zhuǎn)調(diào)度算法 非搶占式優(yōu)先調(diào)度算法2)2)搶占式調(diào)度算法搶占式調(diào)度算法: : 基于時(shí)鐘中斷的搶占優(yōu)先調(diào)度算法 立即搶占優(yōu)先權(quán)調(diào)度算法。 圖 3-5 實(shí)時(shí)進(jìn)程調(diào)度 3.常用的幾種實(shí)時(shí)調(diào)度算法 1）最早截止時(shí)間優(yōu)先即）最早截止時(shí)間優(yōu)先即EDF(EarliestDeadlineFirst)算法算法圖 3-6 EDF算法用于非搶占調(diào)度方式 2）最低松弛度優(yōu)先(LLF)算法 該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級(jí)。該算法主要用于可搶占調(diào)度方式中。 假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)A和B，任務(wù)A要求每 20 ms執(zhí)行一次，執(zhí)行時(shí)間為 10 ms；任務(wù)B只要求每

25、50 ms執(zhí)行一次，執(zhí)行時(shí)間為 25 ms。 圖 3-7 A和B任務(wù)每次必須完成的時(shí)間 在剛開始時(shí)(t1=0)，A1必須在20ms時(shí)完成，而它本身運(yùn)行又需 10 ms，可算出A1的松弛度為10ms；B1必須在50ms時(shí)完成， 而它本身運(yùn)行就需25 ms，可算出B1的松弛度為25 ms，故調(diào)度程序應(yīng)先調(diào)度A1執(zhí)行。在t2=10 ms時(shí)，A2的松弛度可按下式算出： A2的松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間 =40 ms-10 ms-10 ms=20 ms 類似地，可算出B1的松弛度為15ms，調(diào)度程序應(yīng)選擇B2運(yùn)行。t3=30 ms時(shí)，A2的松弛度已減為0，B1的松弛度為15 ms，

26、于是調(diào)度程序應(yīng)搶占B1的處理機(jī)而調(diào)度A2運(yùn)行.圖 3-8 利用ELLF算法進(jìn)行調(diào)度的情況3.4 多處理機(jī)系統(tǒng)中的調(diào)度一、多處理機(jī)系統(tǒng)的類型1、引入原因（1）增加系統(tǒng)的吞吐量：?jiǎn)挝粫r(shí)間內(nèi)的工作總量。（2）節(jié)省投資：采用有N個(gè)處理機(jī)的系統(tǒng)，可以共用一個(gè)機(jī)箱，電源，和一部分資源（外設(shè)和內(nèi)存）。（3）提高系統(tǒng)的可靠性：當(dāng)一臺(tái)處理機(jī)發(fā)生故障時(shí)，系統(tǒng)能夠立即將該臺(tái)處理機(jī)上所處理的任務(wù)，遷移到其他一個(gè)或多個(gè)處理機(jī)上去，整個(gè)系統(tǒng)仍能正常運(yùn)行。只是系統(tǒng)的性能稍有降低。2、多處理機(jī)類型（1）緊密偶合MPS 通過高速總線或高速開關(guān)實(shí)現(xiàn)過個(gè)處理機(jī)之間的互連，共享存儲(chǔ)器、I/O設(shè)備、系統(tǒng)中的所有資源和進(jìn)程，都由OS實(shí)施

27、統(tǒng)一的管理和控制。（2）松散偶合型MPS 通過通道或通信線路實(shí)現(xiàn)多臺(tái)計(jì)算機(jī)之間的互連，每臺(tái)計(jì)算機(jī)都有自己的存儲(chǔ)器和I/O設(shè)備，并配置了OS來管理本地資源和在本地運(yùn)行的進(jìn)程。3、多處理機(jī)OS的類型（1）非對(duì)稱處理機(jī)模式 又稱為主-從模式，主處理機(jī)只有一個(gè)，配有OS，管理整個(gè)系統(tǒng)資源，并負(fù)責(zé)為各從處理機(jī)分配任務(wù)，從處理機(jī)有多個(gè)，執(zhí)行預(yù)先規(guī)定的任務(wù)及由主處理機(jī)分配的任務(wù)。（2）對(duì)稱處理機(jī)模式SMPS 所有處理機(jī)都是相同的，在每個(gè)處理機(jī)上運(yùn)行一個(gè)相同的OS拷貝。二、進(jìn)程分配方式1、對(duì)稱多處理機(jī)系統(tǒng)中的進(jìn)程分配方式（同構(gòu)型）（1）靜態(tài)分配（Static Assignment） 一個(gè)進(jìn)程從開始執(zhí)行直至完成

28、，都被固定地分配到一臺(tái)處理機(jī)上去執(zhí)行。每一臺(tái)處理機(jī)設(shè)備一專用的就緒進(jìn)程隊(duì)列，該隊(duì)列中的諸進(jìn)程都被先后分配到該臺(tái)處理機(jī)上執(zhí)行。缺點(diǎn)是會(huì)使各處理機(jī)的忙、閑不均。（2）動(dòng)態(tài)分配（Dynamic Assignment） 在系統(tǒng)中僅設(shè)置一個(gè)公共的就緒隊(duì)列，系統(tǒng)中的所有就緒進(jìn)程都被放在該隊(duì)列中。對(duì)一進(jìn)程，可分配到任意一臺(tái)處理機(jī)上。一個(gè)進(jìn)程的整個(gè)運(yùn)行過程而言，在每次被調(diào)度執(zhí)行時(shí)，都是隨機(jī)分配到一臺(tái)當(dāng)時(shí)是空閑的處理機(jī)上去執(zhí)行。動(dòng)態(tài)分配的優(yōu)點(diǎn)是消除了處理機(jī)忙閑不均的現(xiàn)象，但調(diào)度的開銷可能較大。(3)自調(diào)度(Self-Scheduling) 在系統(tǒng)中仍只設(shè)備一個(gè)公共就緒隊(duì)列，處理機(jī)自己去查看公共就緒隊(duì)列，選擇一個(gè)

29、進(jìn)程令其執(zhí)行。2.非對(duì)稱MPS中的進(jìn)程分配方式（異構(gòu)型） 即OS的核心部分駐留在主機(jī)上,而從機(jī)（Slave）只是執(zhí)行用戶程序，進(jìn)程調(diào)度主機(jī)執(zhí)行。每當(dāng)機(jī)空閑時(shí)，主機(jī)發(fā)送一要求進(jìn)程的信號(hào)這種主一從方式的進(jìn)成調(diào)度。（1）主/從式進(jìn)程分配的主要優(yōu)點(diǎn)： 系統(tǒng)處理比較簡(jiǎn)單，因?yàn)樗羞M(jìn)程分配都由一臺(tái)主機(jī)獨(dú)自處理，使進(jìn)程間的同步問題得以簡(jiǎn)化。切進(jìn)程調(diào)度程序也很容易從單處理機(jī)的進(jìn)程調(diào)度程序演化而來。（2）主/從式進(jìn)程分配的主要缺點(diǎn)： 可靠性不高：主機(jī)一旦出現(xiàn)故障，將會(huì)導(dǎo)致整個(gè)系統(tǒng)癱瘓，而且也很容易因主機(jī)太忙，來不及處理而形成系統(tǒng)瓶頸。三、進(jìn)程（線程）調(diào)度 在多處理機(jī)系統(tǒng)中，比較有代表性的進(jìn)（線）程調(diào)度方式有：自

30、調(diào)度方式，成組調(diào)度（Gang Scheduling），專用處理機(jī)分配方式。1、 自調(diào)度方式（1）自調(diào)度機(jī)制 在處理機(jī)系統(tǒng)中的自調(diào)度，它是直接由單處理機(jī)環(huán)境下的調(diào)度方式演變而來。在系統(tǒng)中設(shè)置有一個(gè)公共的進(jìn)程或線程的就緒隊(duì)列，所有的處理器在空閑時(shí)都可自己到該隊(duì)列中取得一進(jìn)程（線程）來運(yùn)行。（2）優(yōu)點(diǎn)只要系統(tǒng)中有工作可做，只要就緒隊(duì)列不空，就不會(huì)出現(xiàn)處理機(jī)空閑的情況。系統(tǒng)中沒有集中的調(diào)度機(jī)制，任何處理機(jī)都可利用OS的調(diào)度例程去選擇一線程。對(duì)就緒隊(duì)列可按單處理機(jī)所采用的各種方式加以組織，其調(diào)度算法也可沿用單處理所用的算法。如： FCFS算法 最小優(yōu)先數(shù)優(yōu)先算法 搶占式最小有限數(shù)法 （3）缺點(diǎn)由于FCF

31、S算法簡(jiǎn)單、開銷小，從而使它成為一種較好的自調(diào)度算法。自調(diào)度算法仍存在以下問題。瓶頸問題。 在整個(gè)系統(tǒng)中只設(shè)備一個(gè)就緒線程隊(duì)列，供多個(gè)處理機(jī)共享，這些處理機(jī)必須互斥地訪問該隊(duì)列，這就很容易形成系統(tǒng)的瓶頸。低效性。 當(dāng)線程阻塞后又重新就緒時(shí)，又進(jìn)入唯一的就緒隊(duì)列，可能要多次更換處理機(jī)，因而使高速緩存的使用效率很低。線程切換頻繁。 在一應(yīng)用程序中的若干個(gè)線程都屬于相互合作型的，但在采用自調(diào)度方式時(shí)，這些線程很難同時(shí)獲得處理機(jī)而同時(shí)運(yùn)行，這將會(huì)使某些線程位能獲得處理機(jī)運(yùn)行而阻塞。進(jìn)而被切換下來。2、成組調(diào)度所謂成組調(diào)度，是將一個(gè)進(jìn)程中的一組線程，分配到一組處理機(jī)上去執(zhí)行。這種調(diào)度方式至少有以下兩點(diǎn)好

32、處：（1）如果一組相互合作的線程或進(jìn)程，能并行執(zhí)行，則可有效地減少線程（進(jìn)程）的阻塞情況的發(fā)生。從而可以減少線程的切換，使系統(tǒng)性能得到改善。（2）因而每次調(diào)度都可以解決一組線程的處理機(jī)分配問題，因而可以顯著地減少調(diào)度頻率，從而也就減少了調(diào)度開銷。在成組調(diào)度時(shí)，如何為應(yīng)用程序分配處理機(jī)時(shí)間，可以考慮采用這樣兩種方式：面向所有應(yīng)用程序平均分配處理機(jī)時(shí)間 假設(shè)系統(tǒng)中有N個(gè)處理器和M個(gè)應(yīng)用程序。每個(gè)應(yīng)用程序中至多N個(gè)線程，則每個(gè)應(yīng)用程序可有1/M的時(shí)間占有N個(gè)處理機(jī)。面向所有的現(xiàn)成平均分配處理機(jī)時(shí)間 應(yīng)用程序A中有四個(gè)線程，應(yīng)用程序B中只有1個(gè)線程。因此，應(yīng)為應(yīng)用程序A分配4/5的時(shí)間，只為應(yīng)用程序B

33、分配1/5的時(shí)間。按線程數(shù)平均分配時(shí)間的方法更有效。3、專用處理機(jī)分配 專用處理機(jī)分配在一個(gè)應(yīng)用程序執(zhí)行期間，專門為該應(yīng)用程序分配一組處理機(jī)，每一個(gè)線程一個(gè)。這組處理機(jī)供該應(yīng)用程序?qū)Ｓ弥敝翍?yīng)用程序完成。這會(huì)造成處 理機(jī)的嚴(yán)重浪費(fèi)。但把這種調(diào)度方式用于并發(fā)程序相當(dāng)高的多處理機(jī)的環(huán)境。 3.5產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件3.5.1 死鎖的概念死鎖的概念1.1.死鎖例子死鎖例子: : 一個(gè)由于一個(gè)由于申請(qǐng)不同類型資源申請(qǐng)不同類型資源而產(chǎn)生死鎖而產(chǎn)生死鎖的例子的例子 設(shè)系統(tǒng)有一臺(tái)打印機(jī)設(shè)系統(tǒng)有一臺(tái)打印機(jī)(R1)(R1)一臺(tái)掃描儀一臺(tái)掃描儀(R2)(R2)，兩進(jìn)程共享這兩臺(tái)設(shè)備。，兩

34、進(jìn)程共享這兩臺(tái)設(shè)備。 用信號(hào)量用信號(hào)量S1S1表示表示R1R1是否可用，用信號(hào)量是否可用，用信號(hào)量S2S2表示表示R2R2是否可用，是否可用， S1S1、 S2S2初值為初值為1 1。 死鎖例子死鎖例子 這兩個(gè)進(jìn)程在并發(fā)執(zhí)行過程中，可這兩個(gè)進(jìn)程在并發(fā)執(zhí)行過程中，可能會(huì)發(fā)生死鎖。大家可以思考一下，如能會(huì)發(fā)生死鎖。大家可以思考一下，如何修改，進(jìn)程才不會(huì)發(fā)生死鎖。何修改，進(jìn)程才不會(huì)發(fā)生死鎖。2.死鎖概念 指多個(gè)進(jìn)程因競(jìng)爭(zhēng)共享資源而造成的指多個(gè)進(jìn)程因競(jìng)爭(zhēng)共享資源而造成的一種僵局，若無外力作用，這些進(jìn)程一種僵局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。都將永遠(yuǎn)不能再向前推進(jìn)。 即：一組進(jìn)程中，每個(gè)

35、進(jìn)程都無限等即：一組進(jìn)程中，每個(gè)進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到的資源，這種源，因而永遠(yuǎn)無法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。為死鎖進(jìn)程。 3.關(guān)于死鎖的一些結(jié)論關(guān)于死鎖的一些結(jié)論 參與死鎖的進(jìn)程最少是兩個(gè) 參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源 參與死鎖的所有進(jìn)程都在等待資源 參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集注：如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。 4.永久性資源和臨時(shí)性資源永久性資源：可以被多個(gè)進(jìn)程多次永久性資源：可以被多個(gè)進(jìn)程多次使用（可再用資源

36、）使用（可再用資源） 可搶占資源可搶占資源 不可搶占資源不可搶占資源臨時(shí)性資源：只可使用一次的資源；臨時(shí)性資源：只可使用一次的資源；如信號(hào)量如信號(hào)量, ,中斷信號(hào)，同步信號(hào)中斷信號(hào)，同步信號(hào)等（可消耗性資源）等（可消耗性資源）“申請(qǐng)申請(qǐng)-分配分配-使用使用-釋放釋放”模式模式3.5.2 產(chǎn)生死鎖的原因1.1.競(jìng)爭(zhēng)系統(tǒng)資源競(jìng)爭(zhēng)系統(tǒng)資源2.2.進(jìn)程的推進(jìn)順序不當(dāng)進(jìn)程的推進(jìn)順序不當(dāng) 1. 1. 競(jìng)爭(zhēng)系統(tǒng)資源 若系統(tǒng)中只有一臺(tái)打印機(jī)若系統(tǒng)中只有一臺(tái)打印機(jī)R1R1和一臺(tái)和一臺(tái)讀卡機(jī)讀卡機(jī)R2R2，可供進(jìn)程，可供進(jìn)程P1P1和和P2P2共享。若共享。若形形成環(huán)路成環(huán)路，這樣會(huì)產(chǎn)生死鎖，這樣會(huì)產(chǎn)生死鎖。 2

37、.2.進(jìn)程的推進(jìn)順序不當(dāng) 在進(jìn)程在進(jìn)程P1P1和和P2P2并發(fā)執(zhí)行時(shí)，按照左圖曲并發(fā)執(zhí)行時(shí)，按照左圖曲線線所示順序推進(jìn)時(shí)，兩進(jìn)程會(huì)順?biāo)卷樞蛲七M(jìn)時(shí)，兩進(jìn)程會(huì)順利完成，我們稱這種推進(jìn)順序是合法的。利完成，我們稱這種推進(jìn)順序是合法的。若按曲線若按曲線的順序推進(jìn)時(shí)，進(jìn)入不安全的順序推進(jìn)時(shí)，進(jìn)入不安全區(qū)區(qū)D D內(nèi)，兩進(jìn)程再推進(jìn)會(huì)產(chǎn)生死鎖。內(nèi)，兩進(jìn)程再推進(jìn)會(huì)產(chǎn)生死鎖。 3.5.3 產(chǎn)生死鎖的必要條件 互斥條件互斥條件（資源獨(dú)占）（資源獨(dú)占） 請(qǐng)求和保持條件請(qǐng)求和保持條件（部分分配，（部分分配，占有申請(qǐng)）占有申請(qǐng)） 不剝奪條件（不剝奪條件（不可強(qiáng)占）不可強(qiáng)占） 環(huán)路等待條件。環(huán)路等待條件。解決死鎖的基本辦

38、法 預(yù)防死鎖預(yù)防死鎖 避免死鎖避免死鎖 檢測(cè)死鎖檢測(cè)死鎖 解除死鎖解除死鎖 3.6 預(yù)防死鎖的方法和避免死鎖 1.預(yù)防死鎖的方法 在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個(gè)必要條件之一。 1)1)資源一次性分配；資源一次性分配；(破壞請(qǐng)求和保持條件) 2)2)可剝奪資源；可剝奪資源；即當(dāng)某進(jìn)程新的資源未滿足時(shí)，釋放已占有的資源(破壞不可剝奪條件) 3)3)資源有序分配法資源有序分配法；做法：系統(tǒng)給每類資源賦予一個(gè)編號(hào)，每一個(gè)進(jìn)程按編號(hào)遞增的順序請(qǐng)求資源，釋放則相反(破壞環(huán)路等待條件)2. 死鎖避免 死鎖避免定義死鎖避免定義:在系統(tǒng)運(yùn)行過程中，對(duì)進(jìn)程發(fā)出的每一個(gè)

39、系統(tǒng)能夠滿足的資源申請(qǐng)進(jìn)行動(dòng)態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。 預(yù)防死鎖的幾種策略，會(huì)嚴(yán)重地?fù)p害了系統(tǒng)性能。因此要施加較弱的限制，從而獲得較滿意得系統(tǒng)性能來避免死鎖。 由于在避免死鎖的策略中，允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源。因而，系統(tǒng)在進(jìn)行資源分配之前預(yù)先計(jì)算資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程；否則，進(jìn)程等待。其中最具有代表性的避免死鎖算法是銀行家算法。3. 安全狀態(tài)與不安全狀態(tài) 安全狀態(tài)指系統(tǒng)能按某種進(jìn)程安全狀態(tài)指系統(tǒng)能按某種進(jìn)程順序來為每個(gè)進(jìn)程分配其所需資順序來為每個(gè)進(jìn)程分配其所需資源，直至最大需求，

40、使每個(gè)進(jìn)程源，直至最大需求，使每個(gè)進(jìn)程都可順序完成。若系統(tǒng)不存在這都可順序完成。若系統(tǒng)不存在這樣一個(gè)序列，則稱系統(tǒng)處于不安樣一個(gè)序列，則稱系統(tǒng)處于不安全狀態(tài)。全狀態(tài)。 1)安全序列 一個(gè)進(jìn)程序列一個(gè)進(jìn)程序列PP1 1，P Pn n 是安是安全的，如果對(duì)于每一個(gè)進(jìn)程全的，如果對(duì)于每一個(gè)進(jìn)程P Pi i(1(1i in n），它以后尚需要的資源），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程進(jìn)程P Pj j (j i ) (j i )當(dāng)前占有資源量之和，當(dāng)前占有資源量之和，系統(tǒng)處于安全狀態(tài)。系統(tǒng)處于安全狀態(tài)。 ( (安全狀態(tài)一定是沒有死鎖發(fā)生的安全狀態(tài)一定

41、是沒有死鎖發(fā)生的) )2)安全狀態(tài)之例安全狀態(tài)之例 我們通過一個(gè)例子來說明安全性。假定系統(tǒng)中有三個(gè)進(jìn)程P1、 P2和P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配，如下表所示： 進(jìn) 程 最 大 需 求 已 分 配 可 用 P1P2P3104952233)由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果不按照安全序分配資源，則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在T0時(shí)刻以后，P3又請(qǐng)求1臺(tái)磁帶機(jī)，若此時(shí)系統(tǒng)把剩余3臺(tái)中的1臺(tái)分配給P3，則系統(tǒng)便進(jìn)入不

42、安全狀態(tài)。 因?yàn)椋藭r(shí)也無法再找到一個(gè)安全序列， 例如，把其余的2臺(tái)分配給P2，這樣，在P2完成后只能釋放出4臺(tái)，既不能滿足P1尚需5臺(tái)的要求，也不能滿足P3尚需6臺(tái)的要求，致使它們都無法推進(jìn)到完成，彼此都在等待對(duì)方釋放資源，即陷入僵局，結(jié)果導(dǎo)致死鎖。 安全狀態(tài)與不安全狀態(tài) 不安全狀態(tài):不存在一個(gè)安全序列，不安全狀態(tài)一定導(dǎo)致死鎖4.利用銀行家算法避免死鎖1)銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)

43、地改變。如果Availablej=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。 (2) 最大需求矩陣Max。這是一個(gè)nm的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。 (3) 分配矩陣Allocation。這也是一個(gè)nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。 (4) 需求矩陣Need。這也是一個(gè)nm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Needi,j=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。

44、Needi,j=Maxi,j-Allocationi,j 2)銀行家算法銀行家算法 設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Requestij=K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查： (1) 如果RequestijNeedi,j，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。 (2) 如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。 (3) 系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej =Availablej-Requestij

45、; Allocationi,j =Allocationi,j+Requestij; Needi,j =Needi,j-Requestij; (4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。 3)安全性算法安全性算法 (1) 設(shè)置兩個(gè)向量： 工作向量Work: 它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work =Available; Finish: 它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)

46、先做Finishi =false; 當(dāng)有足夠資源分配給進(jìn)程時(shí)， 再令Finishi =true。 (2) 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi=false; Needi,jWorkj； 若找到， 執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。 (3) 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj =Worki+Allocationi,j; Finishi =true; go to step 2; (4) 如果所有進(jìn)程的Finishi=true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 4)銀行家算法之例銀行家算法之例 假定系統(tǒng)中有五個(gè)進(jìn)程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖 3-15 所示。 圖 3-8 T0時(shí)刻的資源分配表 (1) T0時(shí)刻的安全性： 圖 3-9 T0時(shí)刻的安全序列 (2) P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系統(tǒng)先假定可為P1分配資源，并修改Available, Allocatio