第三章 處理機調度

1、第三章第三章 處理機調度與死鎖處理機調度與死鎖 3.1 3.1 處理機調度的基本概念處理機調度的基本概念 3.2 3.2 調度算法調度算法 3.3 3.3 實時調度實時調度 3.4 3.4 多處理機系統(tǒng)中的調度多處理機系統(tǒng)中的調度 3.5 3.5 產生死鎖的原因和必要條件產生死鎖的原因和必要條件 3.6 3.6 預防死鎖的方法預防死鎖的方法 3.7 3.7 死鎖的檢測與解除死鎖的檢測與解除 第三章 處理機調度與死鎖 3.1 處理機調度的基本概念處理機調度的基本概念 3.1.1 高級、中級和低級調度高級、中級和低級調度 1.高級調度高級調度(High Scheduling)-作業(yè)調度作業(yè)調度 決

2、定把外存上處于后備隊列中的哪些作決定把外存上處于后備隊列中的哪些作業(yè)調入內存業(yè)調入內存,并為它們創(chuàng)建進程、分配必要的并為它們創(chuàng)建進程、分配必要的資源，然后將資源，然后將 新創(chuàng)建的進程排在就緒隊列上，新創(chuàng)建的進程排在就緒隊列上，準備執(zhí)行準備執(zhí)行第三章 處理機調度與死鎖 接納多少個作業(yè)接納哪些作業(yè)2. 低級調度低級調度(Low Level Scheduling)-進程調度進程調度 決定就緒隊列中的哪個進程應獲得處理決定就緒隊列中的哪個進程應獲得處理機，由分派程序執(zhí)行把處理機分配給該進程機，由分派程序執(zhí)行把處理機分配給該進程的具體操作的具體操作 1) 非搶占方式(Non-preemptive Mod

3、e) 2) 搶占方式(Preemptive Mode) 第三章 處理機調度與死鎖 引入的主要目的：為了提高內存利用率和系統(tǒng)吞吐量 使暫時不能運行的進程不再占用寶貴的內存資源，將它們調至外存上暫時等待（就緒駐外存狀態(tài)或掛起狀態(tài)），當這些進程重又具備運行條件、且內存又有空閑時，由中級調度來決定把外存上的哪些又具備運行條件的就緒進程，重新調入內存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上3. 中級調度中級調度(Intermediate-Level Scheduling) 中程調度中程調度第三章 處理機調度與死鎖 3.1.2 調度隊列模型調度隊列模型 1. 僅有進程調度的調度隊列模型僅有進程調度的調度隊

4、列模型 圖 3 - 1 僅具有進程調度的調度隊列模型 第三章 處理機調度與死鎖 就 緒隊 列阻 塞隊列進程調度CPU進程完成等待事件交互用戶事件出現(xiàn)時間片完CPU進程進程i進程調度進程調度進程進程j進程進程k進程進程p就緒隊列時間片完時間片完進程進程f進程進程b進程進程n進程進程l阻塞隊列等待事件等待事件事件出現(xiàn)事件出現(xiàn)進程完成進程完成進程進程X第三章 處理機調度與死鎖 2. 具有高級和低級調度的調度隊列模型具有高級和低級調度的調度隊列模型 圖 3-2 具有高、低兩級調度的調度隊列模型 第三章 處理機調度與死鎖 就 緒隊列進程調度CPU進程完成等待事件1作業(yè)調度事件1出現(xiàn)時間片完等待事件2事件

5、2出現(xiàn)等待事件n事件n出現(xiàn)后備 隊列作業(yè)3作業(yè)2作業(yè)1作業(yè)調度作業(yè)調度進程2就緒隊列CPU阻 塞 隊 列 1阻 塞 隊 列 n阻 塞 隊 列 2進程調度進程調度等待事件等待事件1進程1等待事件等待事件2等待事件等待事件n事件事件1出現(xiàn)出現(xiàn)事件事件2出現(xiàn)出現(xiàn)事件事件n出現(xiàn)出現(xiàn)第三章 處理機調度與死鎖 3. 同時具有三級調度的調度隊列模型同時具有三級調度的調度隊列模型 圖 3-3 具有三級調度時的調度隊列模型 第三章 處理機調度與死鎖 就緒隊列進程調度CPU就緒，掛起隊列中級調度阻塞，掛起隊列阻塞隊列等待事件進程完成時間片完作業(yè)調度交互型作業(yè)后備隊列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)3.1.3 選擇調度

6、方式和調度算法的若干準則選擇調度方式和調度算法的若干準則 1. 面向用戶的準則面向用戶的準則 (1) 周轉時間短。周轉時間短。 周轉時間：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔 niSiiTTnW11作業(yè)的周轉時間T與系統(tǒng)為它提供服務的時間TS之比，即W=T/TS，稱為帶權周轉時間第三章 處理機調度與死鎖 作業(yè)在外存后備隊列上的等待時間進程在就緒隊列上等待進程調度的時間進程在CPU上執(zhí)行的時間進程等待I/O操作完成的時間(2) 響應時間快。 (3) 截止時間的保證。 (4) 優(yōu)先權準則。 第三章 處理機調度與死鎖 2. 面向系統(tǒng)的準則面向系統(tǒng)的準則 (1) 系統(tǒng)吞吐量高。(2)

7、處理機利用率好。 (3) 各類資源的平衡利用。 第三章 處理機調度與死鎖 第三章 處理機調度與死鎖 3.2 調 度 算 法 先來先服務調度算法FCFS 短作業(yè)(進程)優(yōu)先調度算法SJ(P)F 高優(yōu)先權優(yōu)先調度算法 基于時間片的輪轉調度算法3.2.1 先來先服務和短作業(yè)先來先服務和短作業(yè)(進程進程)優(yōu)先調度算法優(yōu)先調度算法 第三章 處理機調度與死鎖 1先來先服務（FCFS）調度算法作業(yè)調度：從后備作業(yè)隊列中，選擇一個或多個最先進入該隊列的作業(yè)，將它們調入內存運行；進程調度：就緒隊列按進入的先后次序排列，調度時，選隊首進程投入運行。 A0t1020503040BC515352545D進程名ABCD

8、就緒時間051015要求服務時間1025510先來先服務先來先服務FCFS周轉時間帶權周轉時間101301.2306353.526.252.9252 2、短作業(yè)（進程）優(yōu)先調度算法（、短作業(yè)（進程）優(yōu)先調度算法（SJ(P)FSJ(P)F） 短作業(yè)優(yōu)先SJF調度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調入內存運行。 短進程SPF優(yōu)先調度算法是從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調度。A0t1020503040BC515352545D進程名ABCD就緒時間051015要求服務時間1

9、025510短作業(yè)優(yōu)先短作業(yè)優(yōu)先SJ(P)F周轉時間帶權周轉時間101451.85110117.51.2進程名ABCD平均就緒時間051015要求服務時間1025510先來先服務（FCFS）周轉時間1030303526.25帶權周轉時間11.263.52.925短進程優(yōu)先（SPF）周轉時間104551017.5帶權周轉時間11.8111.2FCFS和SPF調度算法的性能比較作業(yè)情況調度算法進程名ABCD平均到達時間051025要求服務時間20503540FCFS完成時間周轉時間帶權周轉時間SJF完成時間周轉時間帶權周轉時間3.2.2 3.2.2 高優(yōu)先權優(yōu)先調度算法高優(yōu)先權優(yōu)先調度算法 1.

10、優(yōu)先權調度算法的類型 非搶占式優(yōu)先權算法 搶占式優(yōu)先權調度算法2. 優(yōu)先權的類型優(yōu)先權的類型 1) 靜態(tài)優(yōu)先權 第三章 處理機調度與死鎖 確定進程優(yōu)先權的依據(jù)有如下三個方面：(1) 進程類型。 (2) 進程對資源的需求。 (3) 用戶要求。 A0t1020503040BC515352545D進程名ABCD就緒時間051015要求服務時間1025510優(yōu)先權0132高優(yōu)先權優(yōu)先高優(yōu)先權優(yōu)先(靜態(tài)靜態(tài))非搶占式優(yōu)先權調度A0t1020503040BC515352545D進程名ABCD就緒時間051015要求服務時間1025510優(yōu)先權0132高優(yōu)先權優(yōu)先高優(yōu)先權優(yōu)先(靜態(tài)靜態(tài))搶占式優(yōu)先權調度 2

11、) 動態(tài)優(yōu)先權 動態(tài)優(yōu)先權是指，在創(chuàng)建進程時所賦予的優(yōu)先權，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調度性能。例如，我們可以規(guī)定，在就緒隊列中的進程，隨其等待時間的增長，其優(yōu)先權以速率a提高。當采用搶占式優(yōu)先權調度算法時，如果再規(guī)定當前進程的優(yōu)先權以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機。 第三章 處理機調度與死鎖 進程名ABCD就緒時間051015要求服務時間1025510優(yōu)先權0132高優(yōu)先權優(yōu)先高優(yōu)先權優(yōu)先(動態(tài)動態(tài))非搶占式優(yōu)先權調度(優(yōu)先權以速率0.2/5ms提高)1.21.4A0t1020503040BC515352545D3) 高響應比優(yōu)先調度算法

12、優(yōu)先權的變化規(guī)律可描述為： 由于等待時間與服務時間之和，就是系統(tǒng)對該作業(yè)的響應時間，故該優(yōu)先權又相當于響應比RP。據(jù)此，又可表示為： 第三章 處理機調度與死鎖 要求服務時間要求服務時間等待時間優(yōu)先權+要求服務時間響應時間要求服務時間要求服務時間等待時間優(yōu)先權+3.2.3 基于時間片的輪轉調度算法基于時間片的輪轉調度算法 1. 時間片輪轉法時間片輪轉法RR 在早期的時間片輪轉法中，系統(tǒng)將所有的就緒進程按先來先服務的原則，排成一個隊列，每次調度時，把CPU分配給隊首進程，并令其執(zhí)行一個時間片。時間片的大小從幾ms到幾百ms。當執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調度程序便據(jù)此信號來停

13、止該進程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進程，在一給定的時間內，均能獲得一時間片的處理機執(zhí)行時間。第三章 處理機調度與死鎖 A0t1020503040BC515352545D進程名ABCD就緒時間051015要求服務時間1025510時間片輪轉法時間片輪轉法RR時間片為5個單位時間2. 多級反饋隊列調度算法多級反饋隊列調度算法 第三章 處理機調度與死鎖 就緒隊列1就緒隊列2就緒隊列3就緒隊列nS1S2S3至CPU至CPU至CPU至CPU(時間片：S1S 2S3)圖 3-5 多級反饋隊列調度算

14、法 3. 多級反饋隊列調度算法的性能多級反饋隊列調度算法的性能 (1) 終端型作業(yè)用戶。 (2) 短批處理作業(yè)用戶。 (3) 長批處理作業(yè)用戶。第三章 處理機調度與死鎖 假定在單CPU條件下有下列要執(zhí)行的作業(yè):作業(yè)ABCDE到達時間01234運行時間61215優(yōu)先級31342（1）用一個執(zhí)行時間圖描述在下列算法時各自執(zhí)行這些作業(yè)的情況：FCFS、RR（時間片1）和非搶占式優(yōu)先級。（2）對于上述每種算法，各個作業(yè)的周轉時間是多少？平均周轉時間是多少？（3）對于上述每種算法，各個作業(yè)的帶權周轉時間是多少？平均帶權周轉時間是多少？作業(yè)ABCDE到達時間01234運行時間61215優(yōu)先級31342FC

15、FS周轉時間帶權周轉時間RR周轉時間帶權周轉時間非搶占式優(yōu)先周轉時間帶權周轉時間123456789 1011 12 13 14 15t3.3 實實 時時 調調 度度 3.3.1 實現(xiàn)實時調度的基本條件實現(xiàn)實時調度的基本條件 1. 提供必要的信息提供必要的信息2. 系統(tǒng)處理能力強系統(tǒng)處理能力強3. 采用搶占式調度機制采用搶占式調度機制4. 具有快速切換機制具有快速切換機制第三章 處理機調度與死鎖 3.3.2 實時調度算法的分類實時調度算法的分類 1. 非搶占式調度算法非搶占式調度算法 (1) 非搶占式輪轉調度算法。 (2) 非搶占式優(yōu)先調度算法。 第三章 處理機調度與死鎖 2. 搶占式調度算法搶

16、占式調度算法 (1) 基于時鐘中斷的搶占式優(yōu)先權調度算法。(2) 立即搶占(Immediate Preemption)的優(yōu)先權調度算法。 圖 3-6 實時進程調度 第三章 處理機調度與死鎖 (a) 非搶占輪轉調度當前進程實時進程實時進程請求調度實時進程槍占當前進程，并立即執(zhí)行(d) 立即搶占的優(yōu)先權調度調度時間進程 1進程 2實時進程要求調度進程 n實時進程調度實時進程運行(b) 非搶占優(yōu)先權調度當前進程實時進程實時進程請求調度當前進程運行完成調度時間當前進程實時進程請求調度時鐘中斷到來時調度時間(c) 基于時鐘中斷搶占的優(yōu)先權搶占調度調度時間實時進程.3.3.3 常用的幾種實時調度算法常用的

17、幾種實時調度算法 1. 最早截止時間優(yōu)先即最早截止時間優(yōu)先即EDF(Earliest Deadline First)算法算法 開始截止時間2. 最低松弛度優(yōu)先即最低松弛度優(yōu)先即LLF(Least Laxity First)算法算法 松馳度=完成截止時間-其本身運行時間-當前時間 第三章 處理機調度與死鎖 進程名ABCD就緒時間051015要求服務時間1025510開始截止時間5152520最早截止時間優(yōu)先最早截止時間優(yōu)先EDF搶占式調度A0t1020503040BC515352545D進程名ABCD就緒時間051015要求服務時間1025510完成截止時間30403555松馳度最低松馳度優(yōu)先最

18、低松馳度優(yōu)先LLF搶占式調度A0t1020503040BC515352545D201020301510 1510505 020151003.4 多處理機系統(tǒng)中的調度 3.3.1 3.3.1 多處理器系統(tǒng)的類型多處理器系統(tǒng)的類型 3.3.2 3.3.2 進程分配方式進程分配方式 3.3.3 3.3.3 進程（線程）調度方式進程（線程）調度方式3.3.1 多處理器系統(tǒng)的類型多處理系統(tǒng)MPS（MultiProcessor System） 從多處理器之間耦合的緊密程度可以把MPS分為兩類：緊密耦合MPS和松弛耦合MPS 根據(jù)系統(tǒng)中所用處理器的相同與否可分為兩類：對稱MPS和非對稱MPS1 1、緊密耦合

19、、緊密耦合MPSMPS和松弛耦合和松弛耦合MPSMPS 緊密耦合（Tightly Coupted）通常通過高速總線或高速交叉開關來實現(xiàn)多個處理器之間的互連。共享主存儲器系統(tǒng)和I/O設備。系統(tǒng)中所有進程和資源由OS統(tǒng)一控制管理。 松散耦合（Loosely Coupted）通常通過通道或通信線路來實現(xiàn)多臺計算機之間互連。每臺計算機都有自己的存儲器和I/O設備，可以獨立工作。2 2、對稱、對稱MPSMPS和非對稱和非對稱MPSMPS 對稱多處理系統(tǒng)SMPS（Symmetric MultiProcessor System）在系統(tǒng)中所包含的各處理器單元在功能上和結構上都相同。當前的絕大多數(shù)MPS屬于此類

20、。 非對稱多處理器系統(tǒng)。系統(tǒng)中有多種類型的處理單元，它們的功能和結構各不相同，其中只有一個主處理器，其余為從處理器。3.3.2 進程分配方式 在多處理器系統(tǒng)中，進程的調度與系統(tǒng)結構有關。 在同構性系統(tǒng)中，由于所有的處理器都是相同的，因而可將進程分配到任一處理器上運行； 在非對稱MPS，對任一進程而言，都只能將其分配到某一適合于其運行的處理機上去執(zhí)行。 下面分別介紹對稱MPS和非對稱MPS中的進程分配方式。1 1、對稱、對稱MPSMPS中的進程分配方式中的進程分配方式 靜態(tài)分配靜態(tài)分配（Static Assignment）方式：一個進程從開始執(zhí)行直至其完成都被固定的分配到一個處理器上去執(zhí)行。優(yōu)點

21、是進程調度開銷小，缺點是各處理器可能出現(xiàn)忙閑不均。 動態(tài)分配動態(tài)分配（Dynamic Assignment）方式：在系統(tǒng)中僅設置一個公共的就緒隊列，分配進程總是給空閑處理器且對某一進程的執(zhí)行來講也可能曾在不同的處理器上。優(yōu)點是消除忙閑不均現(xiàn)象。缺點是對松散耦合系統(tǒng)增大開銷。2、非對稱MPS中的進程分配方式 對于非對稱MPS，其OS大多是采用主-從式OS,即OS的核心部分駐留在一臺主機上，而從機上只是用戶程序，進程調度只由主機執(zhí)行。每當從機空閑時向主機發(fā)一索求進程信號，然后等待主機分配進程。主機中保持有一個就緒隊列。此種方式優(yōu)點是系統(tǒng)處理比較簡單，缺點是不可靠性。（克服缺點的方法是利用多臺而非一

22、臺管理系統(tǒng)）3.3.3 進程（線程）調度方式 自調度自調度（Self-SchedulingSelf-Scheduling）方式）方式 成組調度成組調度（Gang SchedulingGang Scheduling）方式）方式 專用處理器專用處理器（Dedicated Processor Dedicated Processor AssignmentAssignment）分配方式）分配方式1、自調度（Self-Scheduling）方式 均衡調度均衡調度(balanced scheduling)(balanced scheduling) 一個就緒隊列一個就緒隊列( (多處理機互斥訪問多處理機互斥訪

23、問) ) 優(yōu)點優(yōu)點 不需要專門的處理機從事任務分派工作不需要專門的處理機從事任務分派工作 任務分配均衡任務分配均衡 缺點缺點 當當CPUCPU較多時較多時, ,就緒隊列成為瓶頸就緒隊列成為瓶頸 線程兩次調度可能處于不同處理機線程兩次調度可能處于不同處理機 不能保證同組線程同時調度不能保證同組線程同時調度自調度(self scheduling)就緒隊列就緒隊列進程進程(線程線程)進程進程(線程線程)進程進程(線程線程)CPUCPUCPU自調度(self scheduling) 例子例子: : Mach, Mach, 改進的自調度改進的自調度 全局隊列全局隊列 局部隊列局部隊列 調度時調度時 首先

24、考慮局部隊列首先考慮局部隊列 然后考慮全局隊列然后考慮全局隊列2、成組調度（Gang Scheduling）方式 將一組相關(合作)的線程同時分派到多個處理機上運行 避免合作線程之間的相互等待 降低開銷,提高運行效率2、成組調度（Gang Scheduling）方式1.1. 面向所有應用程序平均分配處理器時間面向所有應用程序平均分配處理器時間2.2. 面向所有線程平均分配處理器時間面向所有線程平均分配處理器時間 按線程平均分配處理器時間按線程平均分配處理器時間的方法更有效。的方法更有效。兩種分配處理器時間的方法兩種分配處理器時間的方法3、專用處理器（Dedicated Processor As

25、signment）方式對系統(tǒng)的性能和效率來講，單個處理器對系統(tǒng)的性能和效率來講，單個處理器的利用率已不太重要。的利用率已不太重要。由于每個進（線）程專用一臺處理器，由于每個進（線）程專用一臺處理器，可避免進（線）程的切換，從而大大加可避免進（線）程的切換，從而大大加速了程序運行。速了程序運行。最新版最新版TOP500TOP500超級計算機排行榜超級計算機排行榜2007年6月27日下午，在德國德累斯頓舉行的ISC07（國際超級計算大會）上，第29屆TOP500超級計算機名單正式對外公布。本屆排行榜的最大特點表現(xiàn)在：前十位的系統(tǒng)排名幾乎全面洗牌，入選TOP500、TOP100的門檻大幅提升。排行榜

26、還反映了一些新的變化，如雙核處理器已占據(jù)主流地位，InfiniBand份額大幅增加，歐洲HPC應用開始恢復，HP和IBM分列數(shù)量和性能兩大贏家等。 全球最快的10臺超級計算機排名排名所在地所在地廠商及計算機名稱廠商及計算機名稱1DOE/NNSA/LLNL United States IBM BlueGene/L 2Oak Ridge National LaboratoryUnited StatesCray Jaguar 3NNSA/Sandia National LaboratoriesUnited States Cray Red Storm4IBM Thomas J. Watson Rese

27、arch CenterUnited States IBM BGW5Stony Brook/BNL, New York Center for Computional SciencesUnited States IBM New York Blue6DOE/NNSA/LLNLUnited States IBM ASC Purple 7Rensselaer Polytechnic Institute, Computional Center for Nanotechnology InnovationsUnited States IBM eServer Blue Gene Solution8NCSAUni

28、ted States Dell Abe 9Barcelona Supercomputing CenterSpain IBM MareNostrum 10Leibniz RechenzentrumGermany SGI HLRB-II 關于死鎖死鎖（死鎖（DeadlockDeadlock）, ,是指多個進程是指多個進程在運行過程中因爭奪資源而造成的在運行過程中因爭奪資源而造成的一種僵局，當進程處于這種狀態(tài)時，一種僵局，當進程處于這種狀態(tài)時，若無外力作用，它們都將無法再向若無外力作用，它們都將無法再向前推進。前推進。3.5 產生死鎖的原因和必要條件 3.5.1 3.5.1 產生死鎖的原因產生死鎖的

29、原因 3.5.2 3.5.2 產生死鎖的必要條件產生死鎖的必要條件 3.5.3 3.5.3 處理死鎖的基本方法處理死鎖的基本方法3.5.1 產生死鎖的原因產生死鎖的原因可歸結為如下兩點：產生死鎖的原因可歸結為如下兩點：1.1. 競爭資源。競爭資源。2.2. 進程間推進順序非法。進程間推進順序非法?？蓜儕Z和非剝奪性資源可剝奪和非剝奪性資源永久性資源和臨時性資源永久性資源和臨時性資源. Request(B); Request(A); Release(A); Release(B);P2. Request(A); Request(B); Release(B); Release(A);P1v例如：例如：

30、死鎖發(fā)生：雙方都擁有部分資源，同時在請求對方已死鎖發(fā)生：雙方都擁有部分資源，同時在請求對方已占有的資源。如次序：占有的資源。如次序：P1 P2 P1 P2競爭非剝奪性資源競爭非剝奪性資源P1:P2:v(consumable resource)：可以動態(tài)生成和消耗，可以動態(tài)生成和消耗，一般不限制數(shù)量。如硬件中斷、信號、消息、緩沖一般不限制數(shù)量。如硬件中斷、信號、消息、緩沖區(qū)內的數(shù)據(jù)。區(qū)內的數(shù)據(jù)。. Receive(P1,N); Send(P1,R);P2. Receive(P2,R); Send(P2,N);P1死鎖發(fā)生：雙方都等待對方去生成資源，死鎖發(fā)生：雙方都等待對方去生成資源，如次序：如次

31、序：P1 P2競爭臨時性資源競爭臨時性資源P1:P2:正確的進程推進順序正確的進程推進順序 P1: Release(S1); Request(S3); P2: Release(S2); Request(S1); P3: Release(S3); Request(S2); 死鎖的進程推進順序死鎖的進程推進順序 P1: Request(S3); Release(S1); P2: Request(S1); Release(S2); P3: Request(S2); Release(S3);進程推進順序不當引起死鎖進程推進順序不當引起死鎖S3S1S2P1P3P2P2Rel(R1)P2Rel(R2)P2

32、Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)D進程推進順序對死鎖的影響進程推進順序對死鎖的影響3.5.2 產生死鎖的必要條件雖然進程在運行過程中可能發(fā)生死鎖，雖然進程在運行過程中可能發(fā)生死鎖，但死鎖的發(fā)生也必須具備一定的條件。但死鎖的發(fā)生也必須具備一定的條件?？梢钥闯?，必須具備以下四個條件。可以看出，必須具備以下四個條件。3.5.2 產生死鎖的必要條件 1 1. .互斥條件互斥條件：指進程對所分配到的資源指進程對所分配到的資源進行排他性使用，即在一段時間內某進行排他性使用，即在一段時間內某資源只由一個進程占用。如果此時還資源只由一個進

33、程占用。如果此時還有其他進程請求該資源，則請求者只有其他進程請求該資源，則請求者只能等待，直至占有該資源的進程用畢能等待，直至占有該資源的進程用畢釋放。釋放。3.5.2 產生死鎖的必要條件 2.2.請求和保持條件：請求和保持條件：指進程已經保持指進程已經保持了至少一個資源，但又提出了新的了至少一個資源，但又提出了新的資源請求，而該資源又被其他進程資源請求，而該資源又被其他進程占有，此時請求進程阻塞，但又對占有，此時請求進程阻塞，但又對自己已獲得的其他資源保持不放。自己已獲得的其他資源保持不放。3.5.2 產生死鎖的必要條件 3.3.不剝奪條件：不剝奪條件：指進程已獲得的資源，指進程已獲得的資源

34、，在未使用完之前，不能被剝奪，只在未使用完之前，不能被剝奪，只能在使用完時由自己釋放。能在使用完時由自己釋放。3.5.2 產生死鎖的必要條件4.4.環(huán)路等待條件：環(huán)路等待條件：指在發(fā)生死鎖時，必然指在發(fā)生死鎖時，必然存在一個存在一個“進程進程資源資源”的環(huán)形鏈，的環(huán)形鏈，即進程集合即進程集合P0,P1,P2,P0,P1,P2,Pn,Pn中的中的P0P0正在等待一個正在等待一個P1P1占用的資源；占用的資源；P1P1正在正在等待一個等待一個P2P2占用的資源，占用的資源，PnPn正正在等待一個已被在等待一個已被P0P0占用的資源。占用的資源。3.5.3 處理死鎖的基本方法一、預防死鎖消除產生死鎖

35、的必要條件二、避免死鎖分配資源時防止進入不安全狀態(tài)三、檢測死鎖不預防死鎖，出現(xiàn)死鎖就解除四、解除死鎖與檢測死鎖配合使用思考題思考題 一臺計算機共8臺磁帶機，由N個進程共享，每個進程最多要3臺，問N為多少時不會有死鎖，為什么？ 3.6 預防與避免死鎖的方法 3.6.1 3.6.1 預防死鎖預防死鎖 3.6.2 3.6.2 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài) 3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖3.6.1 預防死鎖 預防死鎖的方法是使四個必要條件中的第2、3、4條件之一不能成立，來避免發(fā)生死鎖。至于必要條件1，因為它是由設備的固有條件所決定的，不僅不能改變，還應加以保證。下面

36、分別對三種情況加以說明：1、摒棄“請求和保持”條件靜態(tài)資源分配法靜態(tài)資源分配法優(yōu)點優(yōu)點：算法簡單、易于實現(xiàn)且很安全：算法簡單、易于實現(xiàn)且很安全缺點缺點：資源浪費嚴重，進程延遲運行。：資源浪費嚴重，進程延遲運行。2、摒棄“不剝奪”條件 系統(tǒng)規(guī)定，進程是逐個地提出對資源的要求的。當一個已經保持了某些資源的進程，提出新的要求不被滿足時必須釋放它已經保持的所有資源，待以后需要時再重新申請。從而摒棄了“不剝奪”條件。 該方法實現(xiàn)起來比較復雜且付出很大代價?？赡軙斐汕肮ΡM棄，反復申請和釋放(抖動)情況。3、摒棄“環(huán)路等待”條件 有序資源分配法： 與前兩種策略比較，資源利用率和系統(tǒng)吞吐量都有較明顯的改善。

37、 但也存在嚴重問題：為資源編號限制新設備的增加；進程使用設備順序與申請順序相反；限制用戶編程自由。r1r2rkrm.申請次序申請次序3.6.2 系統(tǒng)安全狀態(tài) 在避免死鎖的方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可避免發(fā)生死鎖。檢測檢測可滿足請求可滿足請求 分配分配 不分配不分配安全安全不安全不安全系統(tǒng)處于安全狀態(tài)系統(tǒng)處于安全狀態(tài)：存在安全進程序列：存在安全進程序列進程序列進程序列安全安全，p1,p2,pn可依次進行完。可依次進行完。安全安全不安全不安全死鎖死鎖1、安全狀態(tài)2、安全狀態(tài)之例 假定系統(tǒng)中有三個進程A、B和C，共有12臺磁帶機。進程A總共要求10

38、臺，B和C分別要求4臺和9臺。假設在T0時刻，進程A、B和C已分別獲得5臺、2臺和2臺，尚有3臺未分配，如下表所示：進程進程最大需求最大需求已分配已分配可用可用A1053B42C92233.6.3 利用銀行家算法避免死鎖1.1. 銀行家算法中的數(shù)據(jù)結構銀行家算法中的數(shù)據(jù)結構（1）可利用資源向量）可利用資源向量Available。這是一個含有。這是一個含有m個元素的個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目;（2）最大需求矩陣）最大需求矩陣Max。這是一個。這是一個n*m的矩陣，它定義了系的矩陣，它定義了系統(tǒng)中統(tǒng)中n個進程中的每一個進程對

39、個進程中的每一個進程對m類資源的最大需求。類資源的最大需求。（3）分配矩陣）分配矩陣Allocation。這也是一個。這也是一個n*m的矩陣，它定義的矩陣，它定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。（4）需求矩陣）需求矩陣Need。這也是一個。這也是一個n*m的矩陣，用以表示每的矩陣，用以表示每一個進程尚需的各類資源數(shù)。一個進程尚需的各類資源數(shù)?？衫觅Y源向量Available(A B C)2 5 3最大需求矩陣 Max(A B C)P1 3 2 2P2 5 2 2P3 7 4 5分配矩陣Allocation(A B C) 2 0 0

40、 2 1 1 3 0 2需求矩陣Need(A B C) 1 2 2 3 1 1 4 4 3- -= =3.6.3 利用銀行家算法避免死鎖2.銀行家算法銀行家算法 設設Requesti是進程是進程Pi的請求向量，如果的請求向量，如果Requesti j=K，表示進程，表示進程Pi需要需要K個個Rj類型的資源。類型的資源。當當Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查：檢查：Pi請求資源請求資源RequestI NeedI請求超量，錯返請求超量，錯返RequestI Available不滿足，等待不滿足，等待Available:=Available-Request

41、IAllocationI:=AllocationI+RequestINeedI:=NeedI-RequestI安全安全確認，分配完確認，分配完成成Available:=Available+RequestIAllocationI:=AllocationI-RequestINeedI:=NeedI+RequestIpi等待等待FTFTTF銀行家算法案例3.6.3 利用銀行家算法避免死鎖3.安全性算法（1）設置兩個向量： 工作向量work：表示系統(tǒng)可提供給進程繼續(xù)運行的各類資源數(shù)目，在執(zhí)行安全算法開始時，work:=Available; Finish:它表示系統(tǒng)是否有足夠的資源分配進程，使之運行完成

42、。開始時先做Finishi:=false;當有足夠資源分配給進程時，再令Finishi:=true。安全性檢測算法FWork:=Available;Finish:=false; 有滿足條件的有滿足條件的j:Finishj=falseNeedj WorkFinishj=true;Work:=Work+AllocationjT j ,finishj=trueTF安全安全不安全不安全4、銀行家算法之例 假定系統(tǒng)中有四個進程P1,P2,P3,P4和三類資源A,B,C，各種資源的數(shù)量分別為10、4、7，在T0時刻的資源分配情況如下所示: 資源情況進程MaxA B CAllocationA B CNeed

43、A B C AvailableA B CP1P2P3P43 2 2 9 0 22 2 24 3 32 0 03 0 22 1 10 0 21 2 26 0 0 0 1 14 3 13 3 2 資源情況進程WorkA B CAllocationA B CAllocation+WorkFinish(1)T0時刻的安全性：4、銀行家算法之例 資源情況進程MaxA B CAllocationA B CNeedA B C AvailableA B CP1P2P3P43 2 2 9 0 22 2 24 3 32 0 03 0 22 1 10 0 21 2 26 0 0 0 1 14 3 13 3 2Wor

44、k P1 3 3 22 0 0 5 3 2true P3 5 3 22 1 1 7 4 3true P4 7 4 30 0 2 7 4 5true P2 7 4 53 0 2 10 4 7trueT0時刻系統(tǒng)是安全的，存在安全序列P1,P3,P4,P2Request1(1,0,2)=Need1(1,2,3)；Request1(1,0,2)=Available(3,3,2)；試探性把資源分配給P1,并修改相應的數(shù)據(jù),形成的資源變化情況上表所示；由所執(zhí)行安全性檢查得知:可以找到一個安全序列P1,P3,P4,P2,即此時系統(tǒng)是安全的,可以滿足請求。 資源情況進程WorkA B CAllocation

45、A B CAllocation+WorkFinish(2)P1請求資源，發(fā)出請求向量 Request1(1,0,2)；4、銀行家算法之例 資源情況進程MaxA B CAllocationA B CNeedA B C AvailableA B CP1P2P3P43 2 2 9 0 22 2 24 3 32 0 03 0 22 1 10 0 21 2 26 0 0 0 1 14 3 13 3 2Request1(1,0,2) P1 2 3 03 0 2 5 3 2true P3 5 3 22 1 1 7 4 3true P4 7 4 30 0 2 7 4 5true P2 7 4 53 0 2 1

46、0 4 7true2 3 03 0 20 2 0WorkRequest4(3,3,0)Need4(4,3,1)；Request4(3,3,0)Available(2,3,0)；(3)P4請求資源，發(fā)出請求向量 Request4(3,3,0)；4、銀行家算法之例 資源情況進程MaxA B CAllocationA B CNeedA B C AvailableA B CP1P2P3P43 2 2 9 0 22 2 24 3 33 0 23 0 22 1 10 0 20 2 06 0 0 0 1 14 3 12 3 0Request4(3,3,0)當前系統(tǒng)資源不能滿足P4的請求，不予分配；Reque

47、st4(0,2,0)Need4(4,3,1)；Request4(0,2,0)Available(2,3,0)；(4)P4請求資源，發(fā)出請求向量 Request4(0,2,0)；4、銀行家算法之例 資源情況進程MaxA B CAllocationA B CNeedA B C AvailableA B CP1P2P3P43 2 2 9 0 22 2 24 3 33 0 23 0 22 1 10 0 20 2 06 0 0 0 1 14 3 12 3 0Request4(0,2,0)系統(tǒng)試探性為P4分配資源，并修改相應的數(shù)據(jù)，開成的資源分配情況如上所示；2 1 00 2 24 1 1Work進行安全

48、性檢查：可用資源Available(2,1,0)已不能滿足任何進程的需要，系統(tǒng)進入不安全狀態(tài)，故系統(tǒng)不能滿足P4的請求3.7 死鎖的檢測與解除 3.7.1 3.7.1 死鎖的檢測死鎖的檢測 3.7.2 3.7.2 死鎖的解除死鎖的解除3.7.1 死鎖的檢測當系統(tǒng)為進程分配資源時，若未采取任當系統(tǒng)為進程分配資源時，若未采取任何限制性措施，則系統(tǒng)必須提供檢測和何限制性措施，則系統(tǒng)必須提供檢測和解除死鎖的手段，為此系統(tǒng)必須：解除死鎖的手段，為此系統(tǒng)必須：1.1. 保存有關資源的請求和分配信息；保存有關資源的請求和分配信息；2.2. 提供一種算法，以利用這些信息來檢測提供一種算法，以利用這些信息來檢測

49、系統(tǒng)是否已進入死鎖狀態(tài)。系統(tǒng)是否已進入死鎖狀態(tài)。1 資源分配圖定義定義: G=(V,E), V=P R, P=p1,p2,pn, R=r1,r2,rm, E=(pi,rj) (rj,pi), pi P, rj R. 申請邊申請邊(pi,rj): pi申請申請rj； 分配邊分配邊(rj,pi): rj分配分配pi;圖示：圖示： 進程：進程： 資源：資源： 申請邊：由進程到資源類；申請邊：由進程到資源類； 分配邊：由資源實例到進程。分配邊：由資源實例到進程。r2 P2P1r11 資源分配圖申請：申請：pi申請申請rj中的一個資源實例，由中的一個資源實例，由pi向向rj畫一申畫一申請邊，如可滿足，改為分配邊。請邊，如可滿足，改為分配邊