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

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

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

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

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

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

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

8、緒隊列；（2）在OS中設置多個阻塞隊列。當系統中僅設置一個阻塞隊列時，可能會使該隊列很長，尤其當系統較大時，該隊列中可能數百個進程。為了提高隊列的操作效率，通常都設置若干個（1，2,.,n）阻塞隊列，每個隊列對應于一種引起進程阻塞的事件。 2)具有高低級調度的調度隊列模型圖 3-2 具有高、低兩級調度的調度隊列模型3、同時具有三級調度的調度隊列模型 當在OS中引入中級調度后，可把就緒態分為內存就緒狀態、外存就緒狀態。可把阻塞狀態進一步分成內存阻塞和外存阻塞兩種狀態。在調出操作的情況下，可使內存就緒轉變為外存就緒、內存阻塞轉變為外存阻塞；在中級調度的作用下，外存就緒轉變為內存就緒。3)具有三級調

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

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

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

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

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

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

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

16、程），長期沒有調度的情況，因此，僅在要求不太高的系統中，才使用靜態優先權。（2）動態優先權 動態優先權是指在創建進程時所賦予的優先權，可以隨進程的推進而改變，以變獲得更好的性能。 5.高響應比優先調度算法優先權的變化規律可描述為： 由于等待時間與服務時間之和，就是系統對該作業的響應時間，故該優先權又相當于響應比RP。據此，又可表示為： 由上式可以看出：（1）如果作業的等待時間相同，則要求服務的時間愈短，其優先權愈高，因而該算法有利于短作業；（2）當要求服務的時間相同時，作業的優先權決定于其等待時間，因而實現了先來先服務；（3）對于長作業，當其等待時間足夠長時，其優先權便可升到很高，從而也可獲得

17、處理機。 該算法既照顧了短作業，又考慮了作業到達的先后順序，也不會使作業長期得不到服務。因此，該算法實現了一種較好的折衷。當然，再利用該算法時，每要進行調度之前，都需先進行響應應比的計算，這會增加系統的開銷3.2練習練習假如有四道作業，它們的進入時間和運行時間由下表給出，假如有四道作業，它們的進入時間和運行時間由下表給出，在單道程序環境下，分別填寫先來先服務、短作業優先和高響在單道程序環境下，分別填寫先來先服務、短作業優先和高響應比優先調度算法的完成時間和周轉時間，并求出平均周轉時應比優先調度算法的完成時間和周轉時間，并求出平均周轉時間和平均帶權周轉時間。間和平均帶權周轉時間。作業作業號號進入

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

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

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

21、最小，隨著隊列級別的降低，時間片加大* 各個隊列按照先進先出調度算法* 一個新進程就緒后進入第一級隊列* 進程由于等待而放棄CPU后，進入等待隊列，一旦等待的事件發生，則回到原來的就緒隊列* 當有一個優先級更高的進程就緒時，可以搶占CPU，被搶占進程回到原來一級就緒隊列末尾* 當第一級隊列空時，就去調度第二級隊列，如此類推* 當時間片到后，進程放棄CPU，回到下一級隊列 3)多隊列反饋調度算法8.進程調度的時機當一個進程運行完畢，或由于某種錯誤而終止運行當一個進程在運行中處于等待狀態（等待I/O）分時系統中時間片到當有一個優先級更高的進程就緒（可搶占式） 例如：新創建一個進程，一個等待進程變成

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

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

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

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

26、于是調度程序應搶占B1的處理機而調度A2運行.圖 3-8 利用ELLF算法進行調度的情況3.4 多處理機系統中的調度一、多處理機系統的類型1、引入原因（1）增加系統的吞吐量：單位時間內的工作總量。（2）節省投資：采用有N個處理機的系統，可以共用一個機箱，電源，和一部分資源（外設和內存）。（3）提高系統的可靠性：當一臺處理機發生故障時，系統能夠立即將該臺處理機上所處理的任務，遷移到其他一個或多個處理機上去，整個系統仍能正常運行。只是系統的性能稍有降低。2、多處理機類型（1）緊密偶合MPS 通過高速總線或高速開關實現過個處理機之間的互連，共享存儲器、I/O設備、系統中的所有資源和進程，都由OS實施

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

28、，都被固定地分配到一臺處理機上去執行。每一臺處理機設備一專用的就緒進程隊列，該隊列中的諸進程都被先后分配到該臺處理機上執行。缺點是會使各處理機的忙、閑不均。（2）動態分配（Dynamic Assignment） 在系統中僅設置一個公共的就緒隊列，系統中的所有就緒進程都被放在該隊列中。對一進程，可分配到任意一臺處理機上。一個進程的整個運行過程而言，在每次被調度執行時，都是隨機分配到一臺當時是空閑的處理機上去執行。動態分配的優點是消除了處理機忙閑不均的現象，但調度的開銷可能較大。(3)自調度(Self-Scheduling) 在系統中仍只設備一個公共就緒隊列，處理機自己去查看公共就緒隊列，選擇一個

29、進程令其執行。2.非對稱MPS中的進程分配方式（異構型） 即OS的核心部分駐留在主機上,而從機（Slave）只是執行用戶程序，進程調度主機執行。每當機空閑時，主機發送一要求進程的信號這種主一從方式的進成調度。（1）主/從式進程分配的主要優點： 系統處理比較簡單，因為所有進程分配都由一臺主機獨自處理，使進程間的同步問題得以簡化。切進程調度程序也很容易從單處理機的進程調度程序演化而來。（2）主/從式進程分配的主要缺點： 可靠性不高：主機一旦出現故障，將會導致整個系統癱瘓，而且也很容易因主機太忙，來不及處理而形成系統瓶頸。三、進程（線程）調度 在多處理機系統中，比較有代表性的進（線）程調度方式有：自

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

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

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

33、分配1/5的時間。按線程數平均分配時間的方法更有效。3、專用處理機分配 專用處理機分配在一個應用程序執行期間，專門為該應用程序分配一組處理機，每一個線程一個。這組處理機供該應用程序專用直至應用程序完成。這會造成處 理機的嚴重浪費。但把這種調度方式用于并發程序相當高的多處理機的環境。 3.5產生死鎖的原因和必要條件產生死鎖的原因和必要條件3.5.1 死鎖的概念死鎖的概念1.1.死鎖例子死鎖例子: : 一個由于一個由于申請不同類型資源申請不同類型資源而產生死鎖而產生死鎖的例子的例子 設系統有一臺打印機設系統有一臺打印機(R1)(R1)一臺掃描儀一臺掃描儀(R2)(R2)，兩進程共享這兩臺設備。，兩

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

35、進程都無限等即：一組進程中，每個進程都無限等待被該組進程中另一進程所占有的資待被該組進程中另一進程所占有的資源，因而永遠無法得到的資源，這種源，因而永遠無法得到的資源，這種現象稱為進程死鎖，這一組進程就稱現象稱為進程死鎖，這一組進程就稱為死鎖進程。為死鎖進程。 3.關于死鎖的一些結論關于死鎖的一些結論 參與死鎖的進程最少是兩個 參與死鎖的進程至少有兩個已經占有資源 參與死鎖的所有進程都在等待資源 參與死鎖的進程是當前系統中所有進程的子集注：如果死鎖發生，會浪費大量系統資源，甚至導致系統崩潰。 4.永久性資源和臨時性資源永久性資源：可以被多個進程多次永久性資源：可以被多個進程多次使用（可再用資源

36、）使用（可再用資源） 可搶占資源可搶占資源 不可搶占資源不可搶占資源臨時性資源：只可使用一次的資源；臨時性資源：只可使用一次的資源；如信號量如信號量, ,中斷信號，同步信號中斷信號，同步信號等（可消耗性資源）等（可消耗性資源）“申請申請-分配分配-使用使用-釋放釋放”模式模式3.5.2 產生死鎖的原因1.1.競爭系統資源競爭系統資源2.2.進程的推進順序不當進程的推進順序不當 1. 1. 競爭系統資源 若系統中只有一臺打印機若系統中只有一臺打印機R1R1和一臺和一臺讀卡機讀卡機R2R2，可供進程，可供進程P1P1和和P2P2共享。若共享。若形形成環路成環路，這樣會產生死鎖，這樣會產生死鎖。 2

37、.2.進程的推進順序不當 在進程在進程P1P1和和P2P2并發執行時，按照左圖曲并發執行時，按照左圖曲線線所示順序推進時，兩進程會順所示順序推進時，兩進程會順利完成，我們稱這種推進順序是合法的。利完成，我們稱這種推進順序是合法的。若按曲線若按曲線的順序推進時，進入不安全的順序推進時，進入不安全區區D D內，兩進程再推進會產生死鎖。內，兩進程再推進會產生死鎖。 3.5.3 產生死鎖的必要條件 互斥條件互斥條件（資源獨占）（資源獨占） 請求和保持條件請求和保持條件（部分分配，（部分分配，占有申請）占有申請） 不剝奪條件（不剝奪條件（不可強占）不可強占） 環路等待條件。環路等待條件。解決死鎖的基本辦

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

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

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

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

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

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

44、Needi,j=Maxi,j-Allocationi,j 2)銀行家算法銀行家算法 設Requesti是進程Pi的請求向量，如果Requestij=K，表示進程Pi需要K個Rj類型的資源。當Pi發出資源請求后，系統按下述步驟進行檢查： (1) 如果RequestijNeedi,j，便轉向步驟2；否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。 (2) 如果RequestijAvailablej，便轉向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。 (3) 系統試探著把資源分配給進程Pi，并修改下面數據結構中的數值： Availablej =Availablej-Requestij

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

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