操作系統(tǒng)講義第三章

1、2022年2月24日操作系統(tǒng)講義1第第三三章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2022年2月24日第二章 進程管理2主要內(nèi)容主要內(nèi)容 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 3.3 幾種調(diào)度算法幾種調(diào)度算法 3.4 實時調(diào)度實時調(diào)度 3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法 3.7 死鎖的檢測和解除死鎖的檢測和解除2022年2月24日第二章 進程管理33.1 處理機調(diào)度的層次處理機調(diào)度的層次 作業(yè)的基本概念作業(yè)的基本概念1. 高級調(diào)度（高級調(diào)度（High Level Scheduli

2、ng） 主要功能：根據(jù)某種算法，把外存中把處于后備隊列中的那些作業(yè)調(diào)入內(nèi)存，當作業(yè)完成時做善后處理。 作業(yè)（Job）：包含通常的程序和數(shù)據(jù)，并且配有作業(yè)說明書； 作業(yè)步（Job Step）：“編譯” - “連接裝配” - “運行”； 作業(yè)流：若干個作業(yè)在系統(tǒng)外存形成的輸入流。 作業(yè)控制塊作業(yè)控制塊JCB（Job Control Block） 通常包含：作業(yè)標識、用戶名稱、用戶賬戶、作業(yè)類型（CPU繁忙，I/O繁忙，批量型，終端型）、作業(yè)狀態(tài)、調(diào)度信息（優(yōu)先級，作業(yè)運行時間）、資源需求（運行時間，內(nèi)存，I/O類型數(shù)量）、進入系統(tǒng)時間、開始處理時間、作業(yè)完成時間、作業(yè)退出時間、資源使用情況。202

3、2年2月24日第二章 進程管理43.1 處理機調(diào)度的層次處理機調(diào)度的層次1. 高級調(diào)度（高級調(diào)度（High Level Scheduling） 作業(yè)調(diào)度：作業(yè)調(diào)度：是根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存后備隊列中選取某些作業(yè)調(diào)入內(nèi)存，為他們創(chuàng)建進程、分配必要的資源，然后將進程插入就緒隊列，準備執(zhí)行。 目的：目的：提高內(nèi)存利用率和系統(tǒng)吞吐量，使那些暫時不能運行的進程不再占用內(nèi)存，把它們調(diào)至外存（存儲管理中的對換功能）。 1）接收多少個作業(yè)到內(nèi)存取決于多道程序度 2）接收哪些作業(yè)取決于調(diào)度算法 最簡單：先來先服務(wù)調(diào)度算法 最常用：短作業(yè)優(yōu)先調(diào)度算法

4、 較常用：優(yōu)先級調(diào)度算法 比較好：響應(yīng)比高者優(yōu)先調(diào)度算法2. 中級調(diào)度中級調(diào)度（Intermediate Level Scheduling）2022年2月24日第二章 進程管理53.1 處理機調(diào)度的層次處理機調(diào)度的層次3. 低級調(diào)度（低級調(diào)度（Low Level Scheduling） 它所調(diào)度的對象是進程（或內(nèi)核級線程），當CPU需要重新分配時，利用一定的算法把它分配給進程，它是最基本的調(diào)度。進程調(diào)度的功能進程調(diào)度的功能 （1）保存處理機的現(xiàn)場信息； （2）按照某種算法選擇進程（如優(yōu)先數(shù)算法，輪轉(zhuǎn)算法） （3）把處理器分配給進程。進程調(diào)度的三個基本機制進程調(diào)度的三個基本機制 （1）排隊器：事

5、先將系統(tǒng)所有就緒進程排成一個隊列，方便調(diào)度程序最快找到它； （2）分派器（分派程序）：把進程調(diào)度程序選定的進程從就緒隊列移出，切換上下文，然后把CPU分配給它； （3）上下文切換機制：保存當前程序的上下文，裝入分配程序的上下文；移出分派程序，裝入新選進程的CPU信息；2022年2月24日第二章 進程管理63.1 處理機調(diào)度的層次處理機調(diào)度的層次進程調(diào)度方式進程調(diào)度方式 3.低級調(diào)度（低級調(diào)度（Low Level Scheduling）l非搶占方式：非搶占方式：一旦處理機分配給某個進程，不管它要運行多長時間，都讓它一直運行下去，決不會因為其他原因而搶占正在運行進程的處理機。這種方式下引起進程調(diào)度

6、的因素包括：執(zhí)行完畢或者發(fā)生某事件不能再執(zhí)行執(zhí)行進程提出I/O請求而暫停執(zhí)行在進程通信或者同步過程中執(zhí)行了某種原語操作，如P，Block等優(yōu)點：實現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)批處理系統(tǒng)；優(yōu)點：實現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)批處理系統(tǒng)；缺點：難以滿足緊急任務(wù)要求，可能造成難以預(yù)料的后果。缺點：難以滿足緊急任務(wù)要求，可能造成難以預(yù)料的后果。2022年2月24日第二章 進程管理73.1 處理機調(diào)度的層次處理機調(diào)度的層次進程調(diào)度方式進程調(diào)度方式 3.低級調(diào)度（低級調(diào)度（Low Level Scheduling）l搶占方式：搶占方式：允許調(diào)度程序根據(jù)某種原則去暫停某個正在執(zhí)行的進程，這些原則主要

7、包括：優(yōu)先權(quán)原則短作業(yè)優(yōu)先原則時間片原則優(yōu)點：防止一個長進程長時間占用處理機，公平服務(wù)，適優(yōu)點：防止一個長進程長時間占用處理機，公平服務(wù)，適合實時任務(wù)的需求；合實時任務(wù)的需求；缺點：需要付出較大的開銷。缺點：需要付出較大的開銷。2022年2月24日第二章 進程管理83.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則僅有進程調(diào)度的調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型 通常在分時系統(tǒng)中只設(shè)置進程調(diào)度，每個用戶建立一個進程，系統(tǒng)利用堆棧，樹或者鏈表來管理就緒進程隊列。 1. 調(diào)度隊列模型調(diào)度隊列模型進程執(zhí)行時可能出現(xiàn)的三種情況：進程執(zhí)行時可能出現(xiàn)的三種情況：在給定時間片完成，釋放處理機進入完成狀

8、態(tài)；本次時間片內(nèi)未完成，放入就緒隊列尾部；因為某事件被阻塞，放入阻塞隊列。就 緒 隊 列CPU阻 塞 隊 列交互用戶時間片完進程調(diào)度等待事件進程完成事件出現(xiàn)2022年2月24日第二章 進程管理93.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則具有高級和低級調(diào)度的調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型 作業(yè)調(diào)度按照一定的算法從外存的后備隊列選擇一批作業(yè)調(diào)入內(nèi)存，建立進程，送入就緒隊列，然后按照一定的進程調(diào)度算法選擇進程，分配CPU。 1. 調(diào)度隊列模型調(diào)度隊列模型就 緒 隊 列CPU阻 塞 隊 列作業(yè)調(diào)度時間片完進程調(diào)度等待事件1進程完成事件1出現(xiàn)隊 列后 備阻 塞 隊 列阻 塞 隊

9、列等待事件2等待事件n事件2出現(xiàn)事件n出現(xiàn)隊2022年2月24日第二章 進程管理103.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則同時具有三級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型 可把進程的就緒狀態(tài)分成內(nèi)存就緒和外存就緒，類似地，阻塞狀態(tài)也可進一步分成內(nèi)存阻塞和外存阻塞，調(diào)出操作可使進程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外存就緒，內(nèi)存阻塞轉(zhuǎn)為外存阻塞；中級調(diào)度可是外存就緒轉(zhuǎn)為內(nèi)存就緒。 1. 調(diào)度隊列模型調(diào)度隊列模型就 緒 隊 列CPU緒 掛 起隊 列就作業(yè)調(diào)度時間片完進程調(diào)度進程完成事件出現(xiàn)隊 列后 備塞掛 隊隊 列阻阻 塞 隊 列等待事件起批量作業(yè)掛起事件出現(xiàn)中級調(diào)度中級調(diào)度2022年2

10、月24日第二章 進程管理113.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則面向用戶的準則面向用戶的準則 （1）周轉(zhuǎn)時間短）周轉(zhuǎn)時間短 平均周轉(zhuǎn)時間T的計算如下： 平均帶權(quán)周轉(zhuǎn)時間W的計算如下： （2）響應(yīng)時間快：）響應(yīng)時間快：從用戶通過鍵盤提交一個請求開始，直到系統(tǒng)首次響應(yīng)為止的時間盡量快； （3）截止時間的保證：）截止時間的保證：是指某任務(wù)必須開始執(zhí)行的最遲時間，或必須完成的最遲時間必須有保證，這是評價實時系統(tǒng)性能的重要指標； （4）優(yōu)先權(quán)準則：）優(yōu)先權(quán)準則：遵循優(yōu)先權(quán)準則讓某些緊急的作業(yè)得到及時處理。 2. 選擇調(diào)度方式和算法的若干準則選擇調(diào)度方式和算法的若干準則niiTnT11ni

11、siTTnW112022年2月24日第二章 進程管理123.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則面向系統(tǒng)的準則面向系統(tǒng)的準則 2. 選擇調(diào)度方式和算法的若干準則選擇調(diào)度方式和算法的若干準則（1）系統(tǒng)吞吐量高：）系統(tǒng)吞吐量高：這個是評價批處理系統(tǒng)性能的另一個重要指標，因此是選擇批處理作業(yè)調(diào)度的重要準則。對于大型作業(yè)，一般吞吐量為每小時一道作業(yè)，對于中、小型作業(yè)，其吞吐量可能達到數(shù)十道。（2）處理機利用率好：）處理機利用率好：CPU價格昂貴，利用率成為衡量系統(tǒng)性能的重要指標，一般CPU的利用率在40%到90%之間比較合理。（3）各類資源的平衡利用：）各類資源的平衡利用：不僅要使處理機利

12、用率高，還要有效地利用其他各類資源，如內(nèi)存、外存和I/O設(shè)備，適當?shù)恼{(diào)度方式和算法可以使系統(tǒng)中的各類資源處于忙碌狀態(tài)。2022年2月24日第二章 進程管理133.3 調(diào)度算法調(diào)度算法是一種最簡單的調(diào)度算法，適用于作業(yè)調(diào)度和進程調(diào)度，每次調(diào)度是一種最簡單的調(diào)度算法，適用于作業(yè)調(diào)度和進程調(diào)度，每次調(diào)度都是從后備隊列中選擇一個或者多個最先進入該隊列的作業(yè)，將它都是從后備隊列中選擇一個或者多個最先進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，分配資源，創(chuàng)建進程，然后放入就緒隊列。們調(diào)入內(nèi)存，分配資源，創(chuàng)建進程，然后放入就緒隊列。 1. 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法FCFS（First Come First

13、 Service）FCFS算法比較有利于長作業(yè)（進程），不利于短作業(yè)（進程）算法比較有利于長作業(yè)（進程），不利于短作業(yè)（進程）進程名進程名到達到達 時間時間服務(wù)服務(wù) 時間時間開始執(zhí)開始執(zhí)行時間行時間完成完成 時間時間周轉(zhuǎn)周轉(zhuǎn) 時間時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間A010111B110011011001C21101102100100D31001022021991.992022年2月24日第二章 進程管理143.3 調(diào)度算法調(diào)度算法是指對短作業(yè)或者短進程優(yōu)先調(diào)度的算法，適用于作業(yè)調(diào)度和是指對短作業(yè)或者短進程優(yōu)先調(diào)度的算法，適用于作業(yè)調(diào)度和進程調(diào)度，進程調(diào)度，SJF算法就是從后備隊列中選擇一個運行時間最

14、短的算法就是從后備隊列中選擇一個運行時間最短的作業(yè)，然后把它們調(diào)入內(nèi)存運行。作業(yè)，然后把它們調(diào)入內(nèi)存運行。 2. 短作業(yè)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法SJF（Short Job First）SJF的優(yōu)點：能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量；的優(yōu)點：能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量；進程名進程名到達到達 時間時間服務(wù)服務(wù) 時間時間開始執(zhí)開始執(zhí)行時間行時間完成完成 時間時間周轉(zhuǎn)周轉(zhuǎn) 時間時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間A030331B145982C223531.5D35914112.2SJF的缺點的缺點： 1）對長作業(yè)不利；）對長作業(yè)不利；2）未考慮作業(yè)的緊迫度；）未考慮作業(yè)

15、的緊迫度；3）用戶）用戶估計執(zhí)行時間的不準確性。估計執(zhí)行時間的不準確性。2022年2月24日第二章 進程管理153.3 調(diào)度算法調(diào)度算法 3. FCFS和和SJF的性能比較的性能比較算法算法進程名進程名ABCDE平平 均均到達時間到達時間01234服務(wù)時間服務(wù)時間43524FCFS完成時間完成時間47121418周轉(zhuǎn)時間周轉(zhuǎn)時間461011149帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1225.53.52.8SJF完成時間完成時間4918613周轉(zhuǎn)時間周轉(zhuǎn)時間4816398帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間12.673.11.52.252.12022年2月24日第二章 進程管理163.3 調(diào)度算法調(diào)度算法是為了照顧緊迫

16、型緊迫型作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理，該算法會把處理機分配給優(yōu)先級最高優(yōu)先級最高的作業(yè)（或者進程）。 1）非搶占式優(yōu)先權(quán)調(diào)度算法）非搶占式優(yōu)先權(quán)調(diào)度算法，適用于批處理系統(tǒng)或?qū)崟r性要求不高的系統(tǒng)； 2）搶占式優(yōu)先權(quán)調(diào)度算法）搶占式優(yōu)先權(quán)調(diào)度算法，能更好地滿足緊迫作業(yè)，適合于嚴格的實時系統(tǒng)或者對性能要求較高的批處理和分時系統(tǒng)中。 4. 高優(yōu)先權(quán)優(yōu)先調(diào)度算法（高優(yōu)先權(quán)優(yōu)先調(diào)度算法（Priority Job First）2022年2月24日第二章 進程管理173.3 調(diào)度算法調(diào)度算法 4. 高優(yōu)先權(quán)優(yōu)先調(diào)度算法（高優(yōu)先權(quán)優(yōu)先調(diào)度算法（Priority Job First）優(yōu)先權(quán)的類型靜態(tài)優(yōu)先權(quán)

17、：靜態(tài)優(yōu)先權(quán)：創(chuàng)建進程時確定，在整個運行期間保持不變；進程類型，系統(tǒng)進程要比用戶進程優(yōu)先級高；進程對資源的要求，要求少的優(yōu)先級高；用戶要求，用戶進程的緊迫程度。優(yōu)點：簡單易行，系統(tǒng)開銷小缺點：不夠精確，優(yōu)先權(quán)低的作業(yè)（進程）長期得不到調(diào)度動態(tài)優(yōu)先權(quán)：動態(tài)優(yōu)先權(quán)：創(chuàng)建時賦予，可以隨著進程的而推進或隨其等待事件的增加而改變，以便獲得更好的調(diào)度性能。優(yōu)點：使調(diào)度更加公平，調(diào)度性能高缺點：系統(tǒng)開銷稍大2022年2月24日第二章 進程管理183.3 調(diào)度算法調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 每個作業(yè)的優(yōu)先級動態(tài)計算，作業(yè)的優(yōu)先級隨等待時間的增加而不斷提高。 4. 高優(yōu)先權(quán)優(yōu)先調(diào)度算法（高

18、優(yōu)先權(quán)優(yōu)先調(diào)度算法（Priority Job First）結(jié)論：如果作業(yè)等待事件相同，要求服務(wù)時間越短，優(yōu)先級越高，該算法利于短作業(yè)；如果要求服務(wù)時間相同，那么等待時間越長，優(yōu)先權(quán)越高，它實現(xiàn)的是先來先服務(wù)；對于長作業(yè)，作業(yè)的優(yōu)先級隨著等待時間的增加而提高，如果等待時間足夠長也可以獲得處理機。優(yōu)點：既照顧了短作業(yè)，又考慮了作業(yè)的先后順序，使長作業(yè)也可以得到服務(wù)；缺點：但優(yōu)先級的計算增加了系統(tǒng)的開銷。響應(yīng)比RP=等待時間+要求服務(wù)時間要求服務(wù)時間=響應(yīng)時間要求服務(wù)時間2022年2月24日第二章 進程管理193.3 調(diào)度算法調(diào)度算法基本原理基本原理 系統(tǒng)將所有就緒進程按照先來先服務(wù)的原則排成一個隊

19、列，每次調(diào)度把CPU分配給隊首進程，并令其執(zhí)行一個時間片，當執(zhí)行時間片用完，調(diào)度程序停止其執(zhí)行，并把它送到隊列尾部。 5. 基于時間片的輪轉(zhuǎn)調(diào)度算法（基于時間片的輪轉(zhuǎn)調(diào)度算法（Round Robin）時間片大小時間片大小如果太小利于短作業(yè)，但是會頻繁中斷，進程上下文切換，增加系統(tǒng)開銷；如果太大則每個進程都能在時間片內(nèi)完成，則退化為FCFS算法，無法滿足交互式用戶的需求。2022年2月24日第二章 進程管理203.3 調(diào)度算法調(diào)度算法 5. 基于時間片的輪轉(zhuǎn)調(diào)度算法（基于時間片的輪轉(zhuǎn)調(diào)度算法（Round Robin）(a) q=1(b) q=4 1 2 3 4 5 6 7 8 9 10 11 1

20、2 13 14 15 16 17 18ABACBDAECBDAECABCDEECECC2022年2月24日第二章 進程管理213.3 調(diào)度算法調(diào)度算法 5. 時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法RR算法算法進程名進程名ABCDE平平 均均到達時間到達時間01234服務(wù)時間服務(wù)時間43524RRq=1完成時間完成時間1210181117周轉(zhuǎn)時間周轉(zhuǎn)時間1291681311.6帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間333.243.253.29RRq=4完成時間完成時間47181317周轉(zhuǎn)時間周轉(zhuǎn)時間461610139.8帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間123.253.252.892022年2月24日第二章 進程管理223.3 調(diào)度

21、算法調(diào)度算法調(diào)度算法的實施過程調(diào)度算法的實施過程設(shè)置多個就緒隊列，賦予不同的優(yōu)先級，各個隊列優(yōu)先級遞減，時間片遞增；新進程放入第一個隊列尾部，F(xiàn)CFS原則排隊調(diào)度，時間片內(nèi)完成則撤離系統(tǒng)，如果沒完則轉(zhuǎn)入下個隊列尾部，以此類推，在第n個隊列采取時間片輪轉(zhuǎn)調(diào)度；第一隊列空閑，調(diào)度第二隊列，以此類推，新進程如果優(yōu)先級高，可搶占處理機。 6. 多級反饋隊列調(diào)度算法（多級反饋隊列調(diào)度算法（Round Robin With Multiple Feedback）2022年2月24日第二章 進程管理233.3 調(diào)度算法調(diào)度算法 6. 多級反饋隊列調(diào)度算法（多級反饋隊列調(diào)度算法（Round Robin With

22、 Multiple Feedback）算法的性能算法的性能終端型作業(yè)用戶，大多數(shù)交互性，作業(yè)??；短批處理作業(yè)用戶，周轉(zhuǎn)時間短；長批處理用戶，不用擔心作業(yè)長期得不到處理。就緒隊列1就緒隊列2就緒隊列3就緒隊列4至CPU至CPU至CPU至CPUS1S2S3（時間片：S1S2 S3）新進程2022年2月24日第二章 進程管理243.4 實時調(diào)度實時調(diào)度提供必要的信息提供必要的信息就緒時間，任務(wù)就緒的起始時間；開始截止時間和完成截止時間；處理時間，一個任務(wù)從開始執(zhí)行直至完成所需的時間；資源要求，任務(wù)執(zhí)行的時候需要的一組資源；優(yōu)先級，對緊迫任務(wù)設(shè)置“絕對絕對”優(yōu)先級，松弛任務(wù)設(shè)置“相對相對”優(yōu)先級。 1

23、. 實現(xiàn)實時調(diào)度的基本條件實現(xiàn)實時調(diào)度的基本條件2022年2月24日第二章 進程管理253.4 實時調(diào)度實時調(diào)度 1. 實現(xiàn)實時調(diào)度的基本條件實現(xiàn)實時調(diào)度的基本條件具有快速切換機制具有快速切換機制對外部中斷的快速響應(yīng)能力；快速的任務(wù)分派能力。系統(tǒng)處理能力強系統(tǒng)處理能力強表示周期時間表示處理時間，其中ii1PC1niiiPC采用搶占式調(diào)度機制采用搶占式調(diào)度機制采用單處理機系統(tǒng)，增強處理能力，減少每個任務(wù)處理時間；采用多處理機調(diào)度單處理機實時調(diào)度條件：2022年2月24日第二章 進程管理263.4 實時調(diào)度實時調(diào)度非搶占式調(diào)度算法非搶占式調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法；非搶占式優(yōu)先級調(diào)度算法。搶占式

24、調(diào)度算法搶占式調(diào)度算法基于時鐘中斷的調(diào)度算法立即搶占的調(diào)度算法 2. 實時調(diào)度算法分類實時調(diào)度算法分類最早截止時間優(yōu)先最早截止時間優(yōu)先EDF（Earliest Deadline First）算法）算法 3. 常用的幾種實時調(diào)度算法常用的幾種實時調(diào)度算法最低松弛度優(yōu)先級最低松弛度優(yōu)先級LLF（Least Laxity First）算法）算法 任務(wù)的松弛度任務(wù)的松弛度=必須完成時間必須完成時間 - 其本身運行時間其本身運行時間 - 當前時間當前時間 松弛度松弛度=0表示該任務(wù)必須馬上執(zhí)行，否則會造成嚴重后果。表示該任務(wù)必須馬上執(zhí)行，否則會造成嚴重后果。2022年2月24日第二章 進程管理273.5

25、 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件競爭資源：多個進程共享資源，資源數(shù)目不足所引起進競爭資源：多個進程共享資源，資源數(shù)目不足所引起進程對資源的競爭；程對資源的競爭；可剝奪資源和非可剝奪性資源競爭非剝奪性資源競爭臨時性資源 1. 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 死鎖（死鎖（Deadlock）：）：是指多個進程在運行過程中因爭奪資源而造成的一種僵局（DeadlyEmbrace），當進程出于這種僵持狀態(tài)時，若無外力作用，它們將無法再向前推進。2022年2月24日第二章 進程管理283.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 1. 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因進程推進順序非法

26、：請求和釋放資源順序不當。進程推進順序非法：請求和釋放資源順序不當。1）進程推進順序合法 2）進程推進順序非法P1：Request(R1); Request(R2);P1：Release(R1); Release(R2);P2：Request(R1); Request(R2);P2：Release(R1); Release(R2);P1：Request(R1); P2：Request(R2); P1：Request(R2); P2：Request(R1); P1P2R1R22022年2月24日第二章 進程管理293.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件（1） 互斥條件互斥條件，

27、一段時間內(nèi)某資源只能由一個進程占用；（2） 請求和保持條件請求和保持條件，部分分配資源；（3） 不剝奪條件不剝奪條件，進程已獲得資源不能被剝奪；（4） 環(huán)路等待條件環(huán)路等待條件，發(fā)生死鎖時必然存在進程-資源的環(huán)形鏈。 2. 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件（1）預(yù)防死鎖預(yù)防死鎖：通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的一個或者幾個，預(yù)防死鎖的發(fā)生；（2）避免死鎖：避免死鎖：在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進入不安全狀態(tài)，從而避免發(fā)生死鎖；（3）檢測死鎖：檢測死鎖：通過系統(tǒng)所設(shè)置的檢測機制，及時地檢測出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進程和資源；（4）解除死鎖：

28、解除死鎖：與死鎖檢測配合，通過撤銷和掛起一些進程，以便回收一些資源，再將這些資源分配給處于阻塞狀態(tài)的進程，使之就緒，以繼續(xù)運行。 3. 處理死鎖的基本方法處理死鎖的基本方法2022年2月24日第二章 進程管理303.6 預(yù)防死鎖的方法預(yù)防死鎖的方法（1） 摒棄“請求和保持請求和保持”條件，部分分配資源；（2） 摒棄“不剝奪不剝奪”條件，進程已獲得資源不能被剝奪；（3） 摒棄“環(huán)路等待環(huán)路等待”條件，發(fā)生死鎖時必然存在進程-資源的環(huán)形鏈。 1. 預(yù)防死鎖預(yù)防死鎖安全狀態(tài)安全狀態(tài) 是指系統(tǒng)能按某種進程順序（P1，P2， ，Pn），來為沒個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使

29、每個進程都順利執(zhí)行。安全狀態(tài)實例安全狀態(tài)實例:假設(shè)系統(tǒng)中有三個進程P1，P2，P3，共12臺磁帶機。2. 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)進程最大需求已分配可用P11053P242P3922022年2月24日第二章 進程管理313.6 預(yù)防死鎖的方法預(yù)防死鎖的方法數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 3. 銀行家算法銀行家算法（1）可利用資源向量Available（m個元素的數(shù)組），其中Availablej = k，表示系統(tǒng)中 Rj 類資源有 k 個。 （2）最大需求矩陣Max（nm）的矩陣，Maxi,j=k，表示進程Pi請求Rj類資源的最大數(shù)據(jù)是k個。（3）分配矩陣Allocation（ nm）的矩陣， Allocat

30、ioni,j=k，表示Pi已經(jīng)分得Rj類資源的數(shù)目是k個。（4）需求矩陣Need （ nm）的矩陣， Needi,j=k，表示Pi請求Rj類資源的數(shù)目是k個。上述關(guān)系：上述關(guān)系： Needi,j= Maxi,j - Allocationi,j；2022年2月24日第二章 進程管理323.6 預(yù)防死鎖的方法預(yù)防死鎖的方法算法描述算法描述 3. 銀行家算法銀行家算法 假設(shè)Request i 是Pi的請求向量，Request i j=k表示Pi請求k個Rj類資源，Pi申請后，系統(tǒng)進行檢查：（1）如果Request i j Need i,j ，則轉(zhuǎn)（2），否則出錯（需要資源超過它宣布的最大值）。 （2

31、）如果Request i j Available j ，則轉(zhuǎn)（3），否則尚無足夠的資源，Pi必須等待。 （3）系統(tǒng)為Pi分配資源（試探性的分配）： Availablej=Availablej - Request i j ; Allocationi,j=Allocationi,j + Request i j; Needi,j=Needi,j - Request i j;（4）執(zhí)行安全性算法，若安全則分配（為Pi），否則不分配，令Pi等待。2022年2月24日第二章 進程管理333.6 預(yù)防死鎖的方法預(yù)防死鎖的方法安全性算法安全性算法 3. 銀行家算法銀行家算法（1）設(shè)置兩個向量：工作向量Work

32、，表示系統(tǒng)可提供給進程急需運行所需的各類資源數(shù)目，含有m個元素，初始work = Available；向量Finish，表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成，初始時Finish=false，有足夠資源分配時，F(xiàn)inish=true； （2）在進程集合中找到一個能滿足下述條件的進程： a）Finishii=false; b）Needi,j Workj；如果找到則轉(zhuǎn)（3），否則轉(zhuǎn)（4）；（3）進程Pi獲得資源可順利完成，并釋放資源，則執(zhí)行 Workj=Workj + Allocationi,j; Finishi=true; 轉(zhuǎn)（2）；（4）如果所有進程的Finishi=true都滿足，

33、表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)進入不安全狀態(tài)。2022年2月24日第二章 進程管理343.6 預(yù)防死鎖的方法預(yù)防死鎖的方法假設(shè)系統(tǒng)中有五個進程假設(shè)系統(tǒng)中有五個進程P0, P1, P2, P3, P4和三類資源和三類資源A, B, C，各，各種資源的數(shù)量分別為種資源的數(shù)量分別為10、5、7，在，在T0時刻的資源分配情況下表：時刻的資源分配情況下表： 4. 銀行家算法的實例銀行家算法的實例進程進程/資源資源MaxAllocationNeedAvailableA B CA B CA B CA B CP0P1P2P3P47 5 33 2 29 0 22 2 24 3 30 1 02 0 0(3 0 2

34、)3 0 22 1 10 0 27 4 31 2 2(0 2 0)6 0 00 1 14 3 13 3 2(2 3 0)2022年2月24日第二章 進程管理353.6 預(yù)防死鎖的方法預(yù)防死鎖的方法 4. 銀行家算法的實例銀行家算法的實例進程進程/資源資源WorkNeedAllocationWork+AllocationFinishA B CA B CA B CA B CP1P3P4P2P03 3 25 3 27 4 37 4 5 10 4 71 2 20 1 14 3 16 0 0 7 4 32 0 02 1 10 0 23 0 2 0 1 05 3 27 4 37 4 510 4 710 5

35、 7truetruetruetruetrue(1) T0時刻的安全性：存在安全序列時刻的安全性：存在安全序列P1 , P3, P4, P2, P0。2022年2月24日第二章 進程管理363.6 預(yù)防死鎖的方法預(yù)防死鎖的方法 4. 銀行家算法的實例銀行家算法的實例進程進程/資源資源WorkNeedAllocationWork+AllocationFinishA B CA B CA B CA B CP1P3P4P0P22 3 05 3 27 4 37 4 5 7 5 50 2 00 1 14 3 17 4 3 6 0 0 3 0 22 1 10 0 20 1 0 3 0 2 5 3 27 4 3

36、7 4 57 5 510 5 7truetruetruetruetrue(2) P1請求資源，發(fā)出請求向量請求資源，發(fā)出請求向量Request 1 (1,0,2)，進行檢查，進行檢查Request 1 (1,0,2) Need 1 (1,2,2); Request 1 (1,0,2) Available 1 (3,3,2);存在存在安全序列安全序列P1 , P3, P4, P0, P2。(3) P4請求資源，發(fā)出請求向量請求資源，發(fā)出請求向量Request 4 (3,3,0)，檢查，檢查Request 4 (3,3,0) Need 4 (4,3,1); Request 4 (3,3,0) Av

37、ailable 4 (2,3,0); 讓讓P4等待。等待。2022年2月24日第二章 進程管理373.6 預(yù)防死鎖的方法預(yù)防死鎖的方法 4. 銀行家算法的實例銀行家算法的實例進程進程/資源資源AllocationNeedAvailableA B CA B CA B CP0P1P2P3P40 3 03 0 23 0 22 1 10 0 27 3 20 2 06 0 00 1 14 3 12 1 0(4) P0請求資源，發(fā)出請求向量請求資源，發(fā)出請求向量Request 0 (0,2,0)，進行檢查，進行檢查Request 0 (0,2,0) Need 0 (7,4,3); Request 0 (0

38、,2,0) Available 0 (2,3,0);假定假定為為P0分配資源。分配資源。(5) 進行安全性檢查，進行安全性檢查，Available(2, 1, 0)已不能滿足任何進程需要，故已不能滿足任何進程需要，故系統(tǒng)進入不安全狀態(tài)。系統(tǒng)進入不安全狀態(tài)。2022年2月24日第二章 進程管理383.7 死鎖的檢測與解除死鎖的檢測與解除資源分配圖（資源分配圖（Resource Allocation Graph） RAG是由一組結(jié)點N和一組邊E組成的一個對偶RAG=（N，E），對它的約定如下： （1） P=p1, p2, , pn R=r1, r2, , rn P 和R是兩個互斥的子集，N=PR

39、（2） eE，它連接P中的一個結(jié)點和R中的一個結(jié)點 e=（pi, rj) 資源請求邊（ pi指向rj ）表示pi請求一個單位的rj ； e=（rj, pi) 資源請求邊（ rj 指向pi ）表示pi分配到一個單位的rj ； 1. 死鎖的檢測死鎖的檢測P1P2R1R22022年2月24日第二章 進程管理393.7 死鎖的檢測與解除死鎖的檢測與解除資源分配圖的簡化資源分配圖的簡化 （1）從RAG中找出既不阻塞又不是孤點的進程Pi，消去由Pi出發(fā)的和指向Pi的所有邊（請求邊和分配邊），這等價于Pi獲得它所需的資源，不斷向前推進，一直運行完畢，釋放出它們所占有的全部資源。 （2）進程Pi所釋放的資源可以喚醒某些阻塞于該資源的進程Pj，消去Pj所有的邊，使之成為孤點。 （3）如此下去，最后，若消去圖中所有的邊，則稱該圖是可完全化簡的。 （4）若有向圖不能通過任何過程予以簡化，則稱該圖是不可完全簡化的。 1. 死鎖的檢測死鎖的檢測死鎖定理死鎖定理 引理：引理：一個給定的進程資源分配圖，對所有的簡化順序，將導(dǎo)致相同的結(jié)果（再也不能簡化）。 死鎖定理：死鎖定理：S是死鎖狀態(tài)，S狀態(tài)的進程資源分配圖是不可完全簡化的（充分條件）。2022年2月24日第二章 進程管理403.7 死鎖的檢測與解除死鎖的檢測與解除死鎖檢測中的