第3章 調度與死鎖

1、第三章處理機調度與死鎖第三章處理機調度與死鎖 3.1處理機調度的層次處理機調度的層次 3.2調度隊列模型和調度準則調度隊列模型和調度準則 3.3調度算法調度算法 3.4實時調度實時調度 3.5產生死鎖的原因和必要條件產生死鎖的原因和必要條件 3.6預防和避免死鎖的方法預防和避免死鎖的方法3.7死鎖的檢測與解除死鎖的檢測與解除 3.1處理機調度的層次處理機調度的層次三級調度三級調度高級調度高級調度 中級調度中級調度 低級調度低級調度3.1處理機調度的層次處理機調度的層次 高級調度（也稱作業(yè)調度、接納調度）高級調度（也稱作業(yè)調度、接納調度）作業(yè)和作業(yè)步作業(yè)和作業(yè)步u作業(yè)（作業(yè)（Job）n作業(yè)程序數(shù)

2、據(jù)作業(yè)說明書作業(yè)程序數(shù)據(jù)作業(yè)說明書n批處理系統(tǒng)中，以作業(yè)為基本單位從外存調入內存批處理系統(tǒng)中，以作業(yè)為基本單位從外存調入內存u作業(yè)步（作業(yè)步（Job Step） u作業(yè)流作業(yè)流3.1處理機調度的層次處理機調度的層次作業(yè)控制塊作業(yè)控制塊JCB（Job Control Block）u是作業(yè)在系統(tǒng)中存在的唯一標志是作業(yè)在系統(tǒng)中存在的唯一標志u包含的內容包含的內容n作業(yè)標識、用戶名稱、用戶帳戶作業(yè)標識、用戶名稱、用戶帳戶n作業(yè)類型（作業(yè)類型（CPU 繁忙型、繁忙型、I/O 繁忙型、批量型、終繁忙型、批量型、終端型）、作業(yè)狀態(tài)、調度信息（優(yōu)先級、作業(yè)已運端型）、作業(yè)狀態(tài)、調度信息（優(yōu)先級、作業(yè)已運行時間

3、）行時間）n資源需求（預計運行時間、要求內存大小、要求資源需求（預計運行時間、要求內存大小、要求I/O設備的類型和數(shù)量等）、資源使用情況設備的類型和數(shù)量等）、資源使用情況n進入系統(tǒng)時間、開始處理時間、作業(yè)完成時間、作進入系統(tǒng)時間、開始處理時間、作業(yè)完成時間、作業(yè)退出時間業(yè)退出時間3.1處理機調度的層次處理機調度的層次作業(yè)調度作業(yè)調度u功能功能n選擇外存上處于后備隊列中的一個或幾個作業(yè)調入選擇外存上處于后備隊列中的一個或幾個作業(yè)調入內存，并為它們創(chuàng)建進程，分配必要的資源，然后，內存，并為它們創(chuàng)建進程，分配必要的資源，然后，再將新創(chuàng)建的進程排在就緒隊列，準備執(zhí)行。再將新創(chuàng)建的進程排在就緒隊列，準備

4、執(zhí)行。u使用系統(tǒng)使用系統(tǒng)n批處理系統(tǒng)批處理系統(tǒng)n分時系統(tǒng)和實時系統(tǒng)不需要分時系統(tǒng)和實時系統(tǒng)不需要3.1處理機調度的層次處理機調度的層次u作業(yè)調度時要決定作業(yè)調度時要決定n一次選擇多少個作業(yè)：取決于多道程序度和資源使一次選擇多少個作業(yè)：取決于多道程序度和資源使用情況用情況n選擇哪些作業(yè)：取決于作業(yè)調度算法和資源使用情選擇哪些作業(yè)：取決于作業(yè)調度算法和資源使用情況況u何時執(zhí)行作業(yè)調度功能何時執(zhí)行作業(yè)調度功能n有作業(yè)退出系統(tǒng)時有作業(yè)退出系統(tǒng)時n系統(tǒng)負荷不足時系統(tǒng)負荷不足時u執(zhí)行頻率執(zhí)行頻率n分鐘、小時或天分鐘、小時或天3.1處理機調度的層次處理機調度的層次低級調度（也稱進程調度、短程調度）低級調度（

5、也稱進程調度、短程調度）功能功能u從就緒隊列中選擇一個進程，然后，由分派程序將處理從就緒隊列中選擇一個進程，然后，由分派程序將處理機分配給該進程。機分配給該進程。n保存處理機的現(xiàn)場信息保存處理機的現(xiàn)場信息n按某種進程調度算法選取就緒進程按某種進程調度算法選取就緒進程n把處理器分配給該就緒進程把處理器分配給該就緒進程使用系統(tǒng)使用系統(tǒng)u各種系統(tǒng)均需要各種系統(tǒng)均需要3.1處理機調度的層次處理機調度的層次進程調度時只決定進程調度時只決定u選擇哪個就緒進程：取決于進程調度算法選擇哪個就緒進程：取決于進程調度算法執(zhí)行頻率執(zhí)行頻率u毫秒毫秒要解決的問題要解決的問題When：何時分配：何時分配CPU 進程調度

6、的時機進程調度的時機What：按什么原則分配：按什么原則分配CPU 進程調度算法進程調度算法How： 如何分配如何分配CPU CPU調度過程（進程的上下文切換）調度過程（進程的上下文切換）3.1處理機調度的層次處理機調度的層次進程調度的時機（進程調度的時機（When）u當進程從執(zhí)行態(tài)轉換到阻塞態(tài)時（例如提出當進程從執(zhí)行態(tài)轉換到阻塞態(tài)時（例如提出I/O請求、請求、等待子進程結束、等待子進程結束、wait操作等）操作等）u分時系統(tǒng)中時間片到分時系統(tǒng)中時間片到u當有一個優(yōu)先級更高的進程就緒（例如新創(chuàng)建一個進程，當有一個優(yōu)先級更高的進程就緒（例如新創(chuàng)建一個進程，一個進程由等待變成就緒）一個進程由等待變

7、成就緒）u當一個進程運行完畢，或由于某種錯誤而終止運行當一個進程運行完畢，或由于某種錯誤而終止運行3.1處理機調度的層次處理機調度的層次進程調度方式進程調度方式u非搶占方式（非搶占方式（Nonpreemptive Mode）n一旦把處理機分配給某個進程，便讓該進程一直執(zhí)一旦把處理機分配給某個進程，便讓該進程一直執(zhí)行，直至該進程完成或發(fā)生某事件而阻塞時，才把行，直至該進程完成或發(fā)生某事件而阻塞時，才把處理機分配給其它進程。處理機分配給其它進程。u搶占方式（搶占方式（Preemptive Mode）n允許調度程序根據(jù)某種原則，去停止某個正在執(zhí)行允許調度程序根據(jù)某種原則，去停止某個正在執(zhí)行的進程，將

8、已分配給該進程的處理機，重新分配給的進程，將已分配給該進程的處理機，重新分配給另一進程。另一進程。 時間片原則時間片原則 搶占原則搶占原則 優(yōu)先權原則優(yōu)先權原則 短進程優(yōu)先原則短進程優(yōu)先原則僅在情況僅在情況1和和4下，才進行調度下，才進行調度在情況在情況1、2、3、4時均可調度時均可調度3.1處理機調度的層次處理機調度的層次中級調度（也稱中程調度）中級調度（也稱中程調度）功能功能u負責進程在內存和外存對換區(qū)之間換進負責進程在內存和外存對換區(qū)之間換進/換出換出是內存對換功能的一部分是內存對換功能的一部分目的目的u提高內存利用率和系統(tǒng)吞吐量提高內存利用率和系統(tǒng)吞吐量執(zhí)行頻率執(zhí)行頻率u介于作業(yè)調度和

9、進程調度之間介于作業(yè)調度和進程調度之間3.2調度隊列模型和調度準則調度隊列模型和調度準則 調度隊列模型調度隊列模型僅有進程調度的調度隊列模型僅有進程調度的調度隊列模型阻阻 塞塞 隊隊 列列 1 1就就 緒緒 隊隊 列列CPU進程調度進程調度進程完成進程完成交互用戶交互用戶等待事件等待事件1 1事件出現(xiàn)事件出現(xiàn)時間片用完時間片用完阻阻 塞塞 隊隊 列列 2 2等待事件等待事件2 2阻阻 塞塞 隊隊 列列 n n等待事件等待事件n n事件出現(xiàn)事件出現(xiàn)事件出現(xiàn)事件出現(xiàn) 3.2調度隊列模型和調度準則調度隊列模型和調度準則具有高級和低級調度的調度隊列模型具有高級和低級調度的調度隊列模型阻阻 塞塞 隊隊

10、列列 1 1就就 緒緒 隊隊 列列CPU進程調度進程調度進程完成進程完成后備隊列后備隊列等待事件1事件出現(xiàn)時間片用完時間片用完阻阻 塞塞 隊隊 列列 2 2等待事件2阻阻 塞塞 隊隊 列列 n n等待事件n事件出現(xiàn)事件出現(xiàn) 作業(yè)作業(yè)調度調度交互用戶交互用戶批處理批處理作業(yè)作業(yè)3.2調度隊列模型和調度準則調度隊列模型和調度準則同時具有三級調度的調度隊列模型同時具有三級調度的調度隊列模型就緒隊列進程調度CPU就緒，掛起隊列中級調度阻塞，掛起隊列阻塞隊列等待事件進程完成時間片完作業(yè)調度交互型作業(yè)后備隊列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)3.2調度隊列模型和調度準則調度隊列模型和調度準則選擇調度方式和調度算

11、法的若干準則選擇調度方式和調度算法的若干準則3.2調度隊列模型和調度準則調度隊列模型和調度準則面向系統(tǒng)的準則面向系統(tǒng)的準則u系統(tǒng)吞吐量高系統(tǒng)吞吐量高u處理機利用率好處理機利用率好u各類資源的平衡利用各類資源的平衡利用3.2調度隊列模型和調度準則調度隊列模型和調度準則面向用戶的準則面向用戶的準則u周轉時間短周轉時間短n評價批處理系統(tǒng)的性能、選擇作業(yè)調度方式與算法評價批處理系統(tǒng)的性能、選擇作業(yè)調度方式與算法的重要準則之一的重要準則之一n作業(yè)周轉時間是指從作業(yè)被提交給系統(tǒng)開始，到作作業(yè)周轉時間是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔，它包括四部分時間：業(yè)完成為止的這段時間間隔，它包括

12、四部分時間：作業(yè)在外存后備隊列上等待作業(yè)調度的時間，進程作業(yè)在外存后備隊列上等待作業(yè)調度的時間，進程在就緒隊列上等待進程調度的時間，進程在在就緒隊列上等待進程調度的時間，進程在CPU上上執(zhí)行的時間，以及進程等待執(zhí)行的時間，以及進程等待I/O操作完成的時間操作完成的時間3.2調度隊列模型和調度準則調度隊列模型和調度準則n對每個用戶而言，都希望自己作業(yè)的周轉時間最短。對每個用戶而言，都希望自己作業(yè)的周轉時間最短。但作為計算機系統(tǒng)的管理者，則總是希望能使平均但作為計算機系統(tǒng)的管理者，則總是希望能使平均周轉時間最短，這不僅會有效地提高系統(tǒng)資源的利周轉時間最短，這不僅會有效地提高系統(tǒng)資源的利用率，而且還

13、可使大多數(shù)用戶都感到滿意。用率，而且還可使大多數(shù)用戶都感到滿意。n平均周轉時間可描述為：平均周轉時間可描述為：niiTnT11niiTTnW1s1n作業(yè)的周轉時間作業(yè)的周轉時間T與系統(tǒng)為它提供服務的時間與系統(tǒng)為它提供服務的時間Ts之之比，即比，即W = T/Ts，稱為帶權周轉時間，而平均帶權，稱為帶權周轉時間，而平均帶權周轉時間則可描述為：周轉時間則可描述為： 3.2調度隊列模型和調度準則調度隊列模型和調度準則u響應時間快響應時間快n評價分時系統(tǒng)的性能、選擇分時系統(tǒng)中進程調度算評價分時系統(tǒng)的性能、選擇分時系統(tǒng)中進程調度算法的重要準則之一法的重要準則之一n響應時間是從用戶通過鍵盤提交一個請求開始

14、，直響應時間是從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)首次產生響應為止的時間，或者說，直到屏至系統(tǒng)首次產生響應為止的時間，或者說，直到屏幕上顯示出結果為止的一段時間間隔。它包括三部幕上顯示出結果為止的一段時間間隔。它包括三部分時間：從鍵盤輸入的請求信息傳送到處理機的時分時間：從鍵盤輸入的請求信息傳送到處理機的時間，處理機對請求信息進行處理的時間，以及將所間，處理機對請求信息進行處理的時間，以及將所形成的響應信息回送到終端顯示器的時間。形成的響應信息回送到終端顯示器的時間。3.2調度隊列模型和調度準則調度隊列模型和調度準則u截止時間的保證截止時間的保證n評價實時系統(tǒng)性能、選擇實時調度算法的重要準

15、則評價實時系統(tǒng)性能、選擇實時調度算法的重要準則n截止時間是指某任務必須開始執(zhí)行的最遲時間，或截止時間是指某任務必須開始執(zhí)行的最遲時間，或必須完成的最遲時間。必須完成的最遲時間。u優(yōu)先權準則優(yōu)先權準則n在批處理、分時和實時系統(tǒng)中選擇調度算法時，都在批處理、分時和實時系統(tǒng)中選擇調度算法時，都可遵循優(yōu)先權準則，以便讓某些緊急的作業(yè)能得到可遵循優(yōu)先權準則，以便讓某些緊急的作業(yè)能得到及時處理。及時處理。n在要求較嚴格的場合，往往還須選擇搶占式調度方在要求較嚴格的場合，往往還須選擇搶占式調度方式，才能保證緊急作業(yè)得到及時處理。式，才能保證緊急作業(yè)得到及時處理。 3.3調度算法調度算法 先來先服務調度算法先

16、來先服務調度算法（FCFSFirst Come First Served）既適用于作業(yè)調度，又適用于進程調度（非搶占既適用于作業(yè)調度，又適用于進程調度（非搶占方式）方式）后備作業(yè)隊列、就緒隊列按后備作業(yè)隊列、就緒隊列按FIFO排列，調度時選排列，調度時選擇處于隊首的作業(yè)或進程擇處于隊首的作業(yè)或進程優(yōu)點：簡單、易于實現(xiàn)優(yōu)點：簡單、易于實現(xiàn) 缺點缺點u有利于長的作業(yè)或進程，不利于短的有利于長的作業(yè)或進程，不利于短的u有利于有利于CPU繁忙型的作業(yè)或進程，不利于繁忙型的作業(yè)或進程，不利于I/O繁忙型的繁忙型的3.3調度算法調度算法例例進程名進程名 到達時間到達時間 服務時間服務時間 A 0 4 B

17、1 5 C 2 2 D 3 4A0 40 4開始時間開始時間 完成時間完成時間 周轉時間周轉時間 帶權周轉時間帶權周轉時間 0 4 4 1 4 9 8 1.6 9 11 9 4.5 11 15 12 3平均平均 8.25 2.5258.25 2.525D15 15 B9 9C11113.3調度算法調度算法短作業(yè)短作業(yè)/短進程優(yōu)先調度算法短進程優(yōu)先調度算法（SJFShortest Job First / SPF Shortest Process First)既適用于作業(yè)調度，又適用于進程調度（非搶占既適用于作業(yè)調度，又適用于進程調度（非搶占式或搶占式均可）式或搶占式均可）從后備作業(yè)隊列、就緒隊列

18、中選擇估計運行時間從后備作業(yè)隊列、就緒隊列中選擇估計運行時間最短的作業(yè)或進程最短的作業(yè)或進程優(yōu)點：調度性能較好優(yōu)點：調度性能較好缺點：缺點：1）不利于長的作業(yè)或進程）不利于長的作業(yè)或進程 2）不考慮作業(yè)或進程的緊迫程度）不考慮作業(yè)或進程的緊迫程度 3）估計運行時間很難準確獲得）估計運行時間很難準確獲得3.3調度算法調度算法例例1：作業(yè)調度：作業(yè)調度作業(yè)名作業(yè)名 到達時間到達時間 服務時間服務時間 A 0 4 B 1 5 C 2 2 D 3 4開始時間開始時間 完成時間完成時間 周轉時間周轉時間 帶權周轉時間帶權周轉時間 0 4 4 1 10 15 14 2.8 4 6 4 2 6 10 7 1

19、.75平均平均 7.25 1.88757.25 1.8875A0 40 4D10 10 B1515C6 63.3調度算法調度算法例例2：進程調度：進程調度進程名進程名 到達時間到達時間 服務時間服務時間 A 0 3 B 0 5 C 0 3 D 0 4 E 8 3搶占方式搶占方式1 1、基于最短服務時間搶占、基于最短服務時間搶占：A C D E D B0 3 6 8 11 13 18 0 3 6 8 11 13 18 A C D E B0 3 6 10 13 18 0 3 6 10 13 18 非搶占方式非搶占方式2 2、基于最短剩余服務時間搶占、基于最短剩余服務時間搶占：A C D E B0

20、3 6 10 13 18 0 3 6 10 13 18 3.3調度算法調度算法高優(yōu)先權優(yōu)先調度算法高優(yōu)先權優(yōu)先調度算法適用于作業(yè)調度和進程調度（非搶占式或搶占式適用于作業(yè)調度和進程調度（非搶占式或搶占式均可）均可）選擇具有最高優(yōu)先權的后備作業(yè)或就緒進程選擇具有最高優(yōu)先權的后備作業(yè)或就緒進程優(yōu)先權（優(yōu)先級、優(yōu)先數(shù)）優(yōu)先權（優(yōu)先級、優(yōu)先數(shù)）u利用某一范圍內的一個整數(shù)來表示利用某一范圍內的一個整數(shù)來表示u不同系統(tǒng)的具體用法各異不同系統(tǒng)的具體用法各異u確定進程優(yōu)先權的依據(jù)確定進程優(yōu)先權的依據(jù)n進程類型進程類型n進程對資源的需求進程對資源的需求n用戶要求用戶要求3.3調度算法調度算法優(yōu)先權的類型優(yōu)先權的

21、類型u靜態(tài)優(yōu)先權靜態(tài)優(yōu)先權n創(chuàng)建進程時確定，在進程的整個運行期間保持不變創(chuàng)建進程時確定，在進程的整個運行期間保持不變n簡單易行，系統(tǒng)開銷小，但不夠精確簡單易行，系統(tǒng)開銷小，但不夠精確n僅在要求不高的系統(tǒng)中才使用僅在要求不高的系統(tǒng)中才使用u動態(tài)優(yōu)先權動態(tài)優(yōu)先權n創(chuàng)建進程時確定初值，運行期間基于某種原則動態(tài)創(chuàng)建進程時確定初值，運行期間基于某種原則動態(tài)改變改變n靈活，調度性能好，但系統(tǒng)開銷大靈活，調度性能好，但系統(tǒng)開銷大3.3調度算法調度算法例：進程調度例：進程調度進程名進程名 到達時間到達時間 服務時間服務時間 優(yōu)先級優(yōu)先級 A 0 10 3 B 0 1 5 C 0 5 2 D 5 3 4B A

22、D C 0 1 11 14 19 非搶占方式非搶占方式B A D A C 0 1 5 8 14 19 搶占方式搶占方式3.3調度算法調度算法高響應比優(yōu)先調度算法高響應比優(yōu)先調度算法主要用于作業(yè)調度主要用于作業(yè)調度選擇具有最高響應比的后備作業(yè)選擇具有最高響應比的后備作業(yè)響應比響應比要求服務時間要求服務時間等待時間要求服務時間響應時間PR優(yōu)點：既照顧了作業(yè)到來的先后，又考慮了要求服優(yōu)點：既照顧了作業(yè)到來的先后，又考慮了要求服務時間的長短，是務時間的長短，是FCFS和和SJF的很好的折衷。的很好的折衷。缺點：算法較為復雜；每次調度時，均要重新計算缺點：算法較為復雜；每次調度時，均要重新計算響應比。響

23、應比。3.3調度算法調度算法例例作業(yè)名作業(yè)名J1J2J3到達時間到達時間8:008:309:30服務時間服務時間2小時小時1小時小時0.25小時小時 三個作業(yè)在一臺處理機三個作業(yè)在一臺處理機上單道運行，上單道運行，9:40 進行作業(yè)進行作業(yè)調度，問三個作業(yè)的執(zhí)行次調度，問三個作業(yè)的執(zhí)行次序？序？9:40 調度時：調度時：J1：1+100/120 = 1+5/6J2：1+70/60 = 1+7/6J3：1+10/15 = 1+4/6選擇選擇J2作業(yè)調度作業(yè)調度10:40（J2完成）調度時：完成）調度時：J1：1+160/120 = 1+4/3J3：1+70/15 = 1+14/3選擇選擇J3作業(yè)

24、調度作業(yè)調度執(zhí)行次序：執(zhí)行次序：J2、J3、J13.3調度算法調度算法時間片輪轉調度算法（時間片輪轉調度算法（RRRound Robin）僅適用于進程調度（搶占方式）僅適用于進程調度（搶占方式）主要為分時系統(tǒng)設計主要為分時系統(tǒng)設計就緒隊列按就緒隊列按FIFO排列，調度時選擇隊首進程。但排列，調度時選擇隊首進程。但該進程占用該進程占用CPU至多執(zhí)行一個時間片，便放棄至多執(zhí)行一個時間片，便放棄CPU3.3調度算法調度算法例：時間片例：時間片=2進程名進程名 到達時間到達時間 服務時間服務時間 A 0 4 B 0 5 C 0 2 D 0 4開始時間開始時間 完成時間完成時間 周轉時間周轉時間 帶權周

25、轉時間帶權周轉時間 0 10 10 2.5 2 15 15 3 4 6 6 3 6 14 14 3.5A B C D A B D B0 2 4 6 8 10 12 14 15 0 2 4 6 8 10 12 14 15 3.3調度算法調度算法多級反饋隊列調度算法多級反饋隊列調度算法適用于進程調度適用于進程調度-搶占方式搶占方式就緒隊列就緒隊列1（FCFS）s1CPU結束或結束或阻塞阻塞就緒隊列就緒隊列2（FCFS）s2CPU就緒隊列就緒隊列n（RR）snCPU提交提交高高優(yōu)優(yōu)先先級級低低（時間片（時間片s1s2 sn 且且si+1=2si）結束或結束或阻塞阻塞結束或結束或阻塞阻塞3.4實時調度

26、實時調度 實現(xiàn)實時調度的基本條件實現(xiàn)實時調度的基本條件提供必要的信息提供必要的信息u就緒時間就緒時間u開始截止時間和完成截止時間開始截止時間和完成截止時間u處理時間處理時間u資源要求資源要求u優(yōu)先級優(yōu)先級系統(tǒng)處理能力強系統(tǒng)處理能力強11miiiPC3.4實時調度實時調度調度方式調度方式u大部分采用搶占式調度方式，具有較高的靈活性，較小大部分采用搶占式調度方式，具有較高的靈活性，較小的延遲，但算法復雜，開銷比較大的延遲，但算法復雜，開銷比較大u要求不太嚴格的系統(tǒng)中，也可以采用非剝奪調度方式，要求不太嚴格的系統(tǒng)中，也可以采用非剝奪調度方式，以簡化系統(tǒng)以簡化系統(tǒng)具有快速切換機制具有快速切換機制u對外

27、部中斷的快速響應能力對外部中斷的快速響應能力u快速的任務分派能力快速的任務分派能力3.4實時調度實時調度實時調度算法的分類實時調度算法的分類實時調度是計算機科學中最活躍的研究領域之一實時調度是計算機科學中最活躍的研究領域之一分類分類u非搶占式調度算法非搶占式調度算法n非搶占式輪轉調度算法非搶占式輪轉調度算法n非搶占式優(yōu)先調度算法非搶占式優(yōu)先調度算法u搶占式調度算法搶占式調度算法n基于時鐘中斷的搶占式優(yōu)先權調度算法基于時鐘中斷的搶占式優(yōu)先權調度算法n立即搶占的優(yōu)先權調度算法立即搶占的優(yōu)先權調度算法3.4實時調度實時調度非搶占式調度算法非搶占式調度算法u非搶占式輪轉調度算法非搶占式輪轉調度算法n可

28、獲得數(shù)秒至數(shù)十秒的響應時間可獲得數(shù)秒至數(shù)十秒的響應時間n可用于要求不太嚴格的實時控制系統(tǒng)中可用于要求不太嚴格的實時控制系統(tǒng)中3.4實時調度實時調度u非搶占式優(yōu)先調度算法非搶占式優(yōu)先調度算法n可獲得僅為數(shù)秒至數(shù)百毫秒級的響應時間可獲得僅為數(shù)秒至數(shù)百毫秒級的響應時間n可用于有一定要求的實時控制系統(tǒng)中可用于有一定要求的實時控制系統(tǒng)中 3.4實時調度實時調度搶占式調度算法搶占式調度算法u基于時鐘中斷的搶占式優(yōu)先權調度算法基于時鐘中斷的搶占式優(yōu)先權調度算法n調度延遲可降為幾十至幾毫秒，響應效果較好調度延遲可降為幾十至幾毫秒，響應效果較好n可用于大多數(shù)的實時系統(tǒng)中可用于大多數(shù)的實時系統(tǒng)中3.4實時調度實時

29、調度u立即搶占立即搶占(Immediate Preemption)的優(yōu)先權調度算法的優(yōu)先權調度算法n能獲得非?？斓捻憫砂颜{度延遲降低到幾毫秒能獲得非?？斓捻憫砂颜{度延遲降低到幾毫秒至至100微秒，甚至更低。微秒，甚至更低。3.4實時調度實時調度常用的幾種實時調度算法常用的幾種實時調度算法最早截止時間優(yōu)先算法（最早截止時間優(yōu)先算法（ EDFEarliest Deadline First）u根據(jù)任務的開始截止時間來確定任務的優(yōu)先級，截止時根據(jù)任務的開始截止時間來確定任務的優(yōu)先級，截止時間愈早，其優(yōu)先級愈高。間愈早，其優(yōu)先級愈高。u可用于搶占式調度，也可用于非搶占式調度可用于搶占式調度，也可

30、用于非搶占式調度3.4實時調度實時調度u非搶占式調度方式用于非周期實時任務非搶占式調度方式用于非周期實時任務n例例任務任務到達時間到達時間 開始截止時間開始截止時間 執(zhí)行時間執(zhí)行時間A024B2155C365D6104ACDB 0 4 9 13 171342開始截止時間任務執(zhí)行任務到達12 341342t3.4實時調度實時調度u搶占式調度方式用于周期實時任務搶占式調度方式用于周期實時任務n在一個實時系統(tǒng)中，有兩個周期性實時任務在一個實時系統(tǒng)中，有兩個周期性實時任務A和和B，任務任務A要求每要求每 20 ms執(zhí)行一次，執(zhí)行時間為執(zhí)行一次，執(zhí)行時間為 10 ms；任務任務B只要求每只要求每50 m

31、s執(zhí)行一次，執(zhí)行時間為執(zhí)行一次，執(zhí)行時間為 25 ms。進程進程到達時間到達時間執(zhí)行時間執(zhí)行時間完成截止時間完成截止時間A(1)01020A(2)201040A(3)401060A(4)601080A(5)8010100B(1)02550B(2)5025100開始截止時間開始截止時間 103050709025753.4實時調度實時調度A1 B1 A2B1A3 B2 A4B2A5B1A2A3B2A5A1B1B1 A2 B1 A3 B2 A4 B2 A5 B2A1A2B2A3A4A5B1最后期限B2最后期限A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限到達時間、執(zhí)行時間和最后期限A1

32、固定優(yōu)先級調度固定優(yōu)先級調度A2 B1A3A4A5，B2A5，B2A4A1(錯過)A2 B1 A3(錯過)A1A2 B1(錯過)A3A4A5，B201020304050 60708090100 時間 t/ms使用完成最后期限最早和最后期限調度(A有較高優(yōu)先級)(B有較高優(yōu)先級)A1 B1 A2 B1 A3B2A4B2A5B1A2A3B2A5A1B1B1 A2 B1 A3 B2 A4 B2 A5B2A1A2B2A3A4A5B1最后期限B2最后期限A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限到達時間、執(zhí)行時間和最后期限A1固定優(yōu)先級調度固定優(yōu)先級調度A2 B1 A3A4A5，B2A

33、5，B2A4A1(錯過)A2 B1 A3(錯過)A1A2 B1(錯過)A3A4A5，B2010 20 30 40 50 60 70 80 90 100時間t/ms使用完成最后期限最早和最后期限調度(A有較高優(yōu)先級)(B有較高優(yōu)先級)0 10 20 30 45 55 60 70 90 1003.4實時調度實時調度最低松弛度優(yōu)先算法（最低松弛度優(yōu)先算法（LLFLeast Laxity First）u根據(jù)任務緊急（或松弛）的程度，來確定任務的優(yōu)先級，根據(jù)任務緊急（或松弛）的程度，來確定任務的優(yōu)先級，任務的緊急程度愈高，為該任務所賦予的優(yōu)先級就愈高，任務的緊急程度愈高，為該任務所賦予的優(yōu)先級就愈高，以

34、使之優(yōu)先執(zhí)行。以使之優(yōu)先執(zhí)行。u主要用于可搶占調度方式中主要用于可搶占調度方式中u例，在一個實時系統(tǒng)中，有兩個周期性實時任務例，在一個實時系統(tǒng)中，有兩個周期性實時任務A和和B，任務任務A要求每要求每 20 ms執(zhí)行一次，執(zhí)行時間為執(zhí)行一次，執(zhí)行時間為 10 ms；任務；任務B只要求每只要求每50 ms執(zhí)行一次，執(zhí)行時間為執(zhí)行一次，執(zhí)行時間為 25 ms。3.4實時調度實時調度最低松弛度優(yōu)先算法（最低松弛度優(yōu)先算法（LLFLeast Laxity First）u根據(jù)任務緊急（或松弛）的程度，來確定任務的優(yōu)先級，根據(jù)任務緊急（或松弛）的程度，來確定任務的優(yōu)先級，任務的緊急程度愈高，為該任務所賦予的

35、優(yōu)先級就愈高，任務的緊急程度愈高，為該任務所賦予的優(yōu)先級就愈高，以使之優(yōu)先執(zhí)行。以使之優(yōu)先執(zhí)行。u主要用于可搶占調度方式中主要用于可搶占調度方式中u例，在一個實時系統(tǒng)中，有兩個周期性實時任務例，在一個實時系統(tǒng)中，有兩個周期性實時任務A和和B，任務任務A要求每要求每 20 ms執(zhí)行一次，執(zhí)行時間為執(zhí)行一次，執(zhí)行時間為 10 ms；任務；任務B只要求每只要求每50 ms執(zhí)行一次，執(zhí)行時間為執(zhí)行一次，執(zhí)行時間為 25 ms。A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0t1A1(10)10203040 506080t0t10B1(20)t2t370A2(10

36、)A3(10)A4(10)t4t5t6t7t8B1(5)B2(15)B2(10)3.5產生死鎖的原因和必要條件產生死鎖的原因和必要條件 死鎖（死鎖（Deadlock）假若在一個進程集合中的每個進程都在等待只能假若在一個進程集合中的每個進程都在等待只能由該集合中的其它一個進程才能引發(fā)的事件，那由該集合中的其它一個進程才能引發(fā)的事件，那么這種狀態(tài)被看成是死鎖。么這種狀態(tài)被看成是死鎖。多數(shù)情況下，進程是在等待該集合中的另一個進多數(shù)情況下，進程是在等待該集合中的另一個進程正占有的資源。但由于所有進程都在等待，都程正占有的資源。但由于所有進程都在等待，都不能運行，因而無法釋放任何資源，于是該集合不能運行

37、，因而無法釋放任何資源，于是該集合中的所有進程都不能被喚醒。中的所有進程都不能被喚醒。3.5產生死鎖的原因和必要條件產生死鎖的原因和必要條件產生死鎖的原因產生死鎖的原因競爭資源。當系統(tǒng)中供多個進程共享的資源如打競爭資源。當系統(tǒng)中供多個進程共享的資源如打印機、公用隊列等，其數(shù)目不足以滿足諸進程的印機、公用隊列等，其數(shù)目不足以滿足諸進程的需要時，會引起諸進程對資源的競爭而產生死鎖。需要時，會引起諸進程對資源的競爭而產生死鎖。進程間推進順序非法。進程在運行過程中，請求進程間推進順序非法。進程在運行過程中，請求和釋放資源的順序不當，也同樣會導致產生進程和釋放資源的順序不當，也同樣會導致產生進程死鎖。死

38、鎖。 3.5產生死鎖的原因和必要條件產生死鎖的原因和必要條件競爭資源引起死鎖競爭資源引起死鎖u資源：在任何時候都只能被一個進程使用的任何對象。資源：在任何時候都只能被一個進程使用的任何對象。u資源分類資源分類n永久性資源：可以被多個進程多次使用（可再用資永久性資源：可以被多個進程多次使用（可再用資源）源）可剝奪性資源：可從擁有它的進程中剝奪而不會產生可剝奪性資源：可從擁有它的進程中剝奪而不會產生任何副作用。任何副作用。非剝奪性資源：從擁有它的進程中剝奪會產生錯誤。非剝奪性資源：從擁有它的進程中剝奪會產生錯誤。n臨時性資源：只可使用一次的資源（可消耗性資源）臨時性資源：只可使用一次的資源（可消耗

39、性資源）3.5產生死鎖的原因和必要條件產生死鎖的原因和必要條件u資源使用順序資源使用順序n申請資源申請資源 使用資源使用資源 釋放資源釋放資源 n 某進程申請資源失敗，則轉為阻塞狀態(tài)，進入資源某進程申請資源失敗，則轉為阻塞狀態(tài)，進入資源等待隊列。等待隊列。n 申請資源的命令與系統(tǒng)有關。有些系統(tǒng)提供的是申請資源的命令與系統(tǒng)有關。有些系統(tǒng)提供的是request命令；有些系統(tǒng)則將資源看作特殊文件，用命令；有些系統(tǒng)則將資源看作特殊文件，用open命令打開來表示進程申請資源。另外，命令打開來表示進程申請資源。另外，wait/signal操作也可表示對資源的申請和釋放。操作也可表示對資源的申請和釋放。3.

40、5產生死鎖的原因和必要條件產生死鎖的原因和必要條件u競爭非剝奪性資源可能引發(fā)死鎖競爭非剝奪性資源可能引發(fā)死鎖n例：系統(tǒng)中只有一臺打印機和一臺磁帶機例：系統(tǒng)中只有一臺打印機和一臺磁帶機 進程進程p1 進程進程p2 1. request(打印機打印機); 3. request(磁帶機磁帶機); 2. request(磁帶機磁帶機); 4. request(打印機打印機); 使用使用; 使用使用; release(打印機打印機); release(打印機打印機); release(磁帶機磁帶機); release(磁帶機磁帶機);進程進程p1和和 進程進程p2交替占用交替占用CPU執(zhí)行時，順序為執(zhí)行

41、時，順序為1234或或3412 不會出錯。但為不會出錯。但為 1324 時，會死鎖。時，會死鎖。3.5產生死鎖的原因和必要條件產生死鎖的原因和必要條件u競爭臨時性資源可能引發(fā)死鎖競爭臨時性資源可能引發(fā)死鎖n例，進程例，進程P1、P2、P3互發(fā)消息互發(fā)消息S1、S2和和S3 P1： Request(S3)； Release(S1)； P2： Request(S1)； Release(S2)； P3： Request(S2)； Release(S3)； S2P1S3P3S1P23.5產生死鎖的原因和必要條件產生死鎖的原因和必要條件進程推進順序不當引發(fā)死鎖進程推進順序不當引發(fā)死鎖u例例p1 req(

42、r1) p1 req(r2) p1 rel(r1) p1 rel(r2)p2 rel(r1)p2 rel(r2)p2 req(r1)p2 req(r2)4 41 12 23 3進程進程p1和進和進程程p2交替占交替占用用CPU執(zhí)行執(zhí)行時，順序為時，順序為1或或2或或3時，時，不會出錯。不會出錯。但為但為 4 時，時，會死鎖。會死鎖。3.5產生死鎖的原因和必要條件產生死鎖的原因和必要條件產生死鎖的必要條件產生死鎖的必要條件互斥條件互斥條件u每個資源要么已分配給了一個進程，要么空閑每個資源要么已分配給了一個進程，要么空閑請求和保持條件請求和保持條件u已經(jīng)得到資源的進程可以申請新的資源，申請失敗時變

43、為阻塞狀已經(jīng)得到資源的進程可以申請新的資源，申請失敗時變?yōu)樽枞麪顟B(tài)，此時它仍然保持著原有資源不放。態(tài)，此時它仍然保持著原有資源不放。不剝奪條件不剝奪條件u已經(jīng)分配給一個進程的資源不能被剝奪，只能由占有它的進程主已經(jīng)分配給一個進程的資源不能被剝奪，只能由占有它的進程主動釋放。動釋放。環(huán)路等待條件環(huán)路等待條件u系統(tǒng)一定有兩個或兩個以上的進程組成的一條環(huán)路，該環(huán)路中的系統(tǒng)一定有兩個或兩個以上的進程組成的一條環(huán)路，該環(huán)路中的每個進程都在等待著相鄰進程正占用著的資源每個進程都在等待著相鄰進程正占用著的資源3.5產生死鎖的原因和必要條件產生死鎖的原因和必要條件處理死鎖的四種策略處理死鎖的四種策略預防死鎖預

44、防死鎖u通過破除死鎖的四個必要條件之一，通過破除死鎖的四個必要條件之一，來防止死鎖產生。來防止死鎖產生。避免死鎖避免死鎖u仔細地對資源進行動態(tài)分配，以避仔細地對資源進行動態(tài)分配，以避免死鎖發(fā)生。免死鎖發(fā)生。檢測與解除死鎖檢測與解除死鎖u檢測系統(tǒng)中是否出現(xiàn)死鎖，若出現(xiàn)檢測系統(tǒng)中是否出現(xiàn)死鎖，若出現(xiàn)則解除掉。則解除掉。忽略該問題忽略該問題允許系統(tǒng)發(fā)生允許系統(tǒng)發(fā)生死鎖，然后解除死鎖，然后解除假裝死鎖假裝死鎖永不發(fā)生永不發(fā)生保證系統(tǒng)永遠保證系統(tǒng)永遠不會發(fā)生死鎖不會發(fā)生死鎖3.5產生死鎖的原因和必要條件產生死鎖的原因和必要條件鴕鳥算法鴕鳥算法思想：不采取任何措施，對死鎖視而不見。思想：不采取任何措施，對

45、死鎖視而不見。實例：實例：UNIX系統(tǒng)（還有其它許多系統(tǒng)）。系統(tǒng)（還有其它許多系統(tǒng)）。由于不預防、避免死鎖，故系統(tǒng)中可能發(fā)生死鎖。由于不預防、避免死鎖，故系統(tǒng)中可能發(fā)生死鎖。而發(fā)生時又無法知道（因不檢測），造成系統(tǒng)崩而發(fā)生時又無法知道（因不檢測），造成系統(tǒng)崩潰，需要重啟。潰，需要重啟。之所以被某些系統(tǒng)采用，是因為死鎖不常發(fā)生。之所以被某些系統(tǒng)采用，是因為死鎖不常發(fā)生。3.6預防和避免死鎖的方法預防和避免死鎖的方法預防死鎖預防死鎖如果能夠保證四個必要條件中至少有一個不成立，如果能夠保證四個必要條件中至少有一個不成立，那么死鎖將不會產生。（那么死鎖將不會產生。（Havender，1968）但其中的

46、但其中的“互斥互斥”條件不能破除。條件不能破除。3.6預防和避免死鎖的方法預防和避免死鎖的方法摒棄摒棄“請求和保持請求和保持”條件條件u方法方法n規(guī)定進程在執(zhí)行前要一次性地申請運行所需全部資規(guī)定進程在執(zhí)行前要一次性地申請運行所需全部資源。只有資源全部到手，進程方可運行，否則進程源。只有資源全部到手，進程方可運行，否則進程等待。等待。u優(yōu)點優(yōu)點n簡單、易于實現(xiàn)簡單、易于實現(xiàn)u 缺點缺點n資源利用率低資源利用率低n進程運行被延遲進程運行被延遲3.6預防和避免死鎖的方法預防和避免死鎖的方法摒棄摒棄“不剝奪不剝奪”條件條件u方法方法n保持資源的進程申請新資源失敗時，在轉為阻塞狀保持資源的進程申請新資源

47、失敗時，在轉為阻塞狀態(tài)之前，必須釋放其占用的全部資源。而該進程自態(tài)之前，必須釋放其占用的全部資源。而該進程自身則必須等到重新獲得原有資源及新資源后，才能身則必須等到重新獲得原有資源及新資源后，才能重新運行。重新運行。u缺點缺點n實現(xiàn)復雜，代價大實現(xiàn)復雜，代價大u適用范圍適用范圍n資源的狀態(tài)能夠很方便的保存和恢復，例如資源的狀態(tài)能夠很方便的保存和恢復，例如CPU寄寄存器和存儲空間。存器和存儲空間。3.6預防和避免死鎖的方法預防和避免死鎖的方法摒棄摒棄“環(huán)路等待環(huán)路等待”條件條件u方法方法1n保證每個進程在任何時候只能占用一個資源。要用保證每個進程在任何時候只能占用一個資源。要用第二個，必須先釋放

48、第一個。第二個，必須先釋放第一個。u方法方法2n將系統(tǒng)中所有資源賦予一個全局編號，進程申請資將系統(tǒng)中所有資源賦予一個全局編號，進程申請資源時，必須按編號遞增順序進行。源時，必須按編號遞增順序進行。n缺點：缺點：1. 找不出一種人人滿意的編號順序。找不出一種人人滿意的編號順序。 2. 仍存在資源浪費。仍存在資源浪費。 3. 用戶編程受到限制。用戶編程受到限制。3.6預防和避免死鎖的方法預防和避免死鎖的方法避免死鎖避免死鎖思路思路u允許進程動態(tài)的申請資源允許進程動態(tài)的申請資源u將系統(tǒng)狀態(tài)分為將系統(tǒng)狀態(tài)分為 n安全狀態(tài)：不會發(fā)生死鎖安全狀態(tài)：不會發(fā)生死鎖n不安全狀態(tài)：可能發(fā)生死鎖不安全狀態(tài)：可能發(fā)生

49、死鎖避免系統(tǒng)進入不安全狀態(tài)！避免系統(tǒng)進入不安全狀態(tài)！做法做法u每次進行資源分配時，首先檢測一下每次進行資源分配時，首先檢測一下資源分配后資源分配后系統(tǒng)處系統(tǒng)處于何種狀態(tài)，若處于于何種狀態(tài)，若處于安全安全狀態(tài)，則正式實施本次狀態(tài)，則正式實施本次分配分配；若處于若處于不安全不安全狀態(tài)，則狀態(tài)，則不予分配不予分配，申請資源的進程阻塞。，申請資源的進程阻塞。3.6預防和避免死鎖的方法預防和避免死鎖的方法系統(tǒng)的安全狀態(tài)系統(tǒng)的安全狀態(tài)u安全狀態(tài)安全狀態(tài)n指系統(tǒng)能按某種進程順序（指系統(tǒng)能按某種進程順序（P1，P2，Pn）（稱）（稱P1，P2，Pn序列為安全序列），來為每個序列為安全序列），來為每個進程進程

50、Pi 分配其所需資源，直至滿足每個進程對資源分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。的最大需求，使每個進程都可順利地完成。u如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。安全狀態(tài)。3.6預防和避免死鎖的方法預防和避免死鎖的方法u例，系統(tǒng)有三個進程例，系統(tǒng)有三個進程P1、P2和和P3 ，共用，共用12臺磁帶機。臺磁帶機。在在T0和和T1時刻，系統(tǒng)的資源分配情況分別如下表時刻，系統(tǒng)的資源分配情況分別如下表a和和b。進程進程 最大需求最大需求 已分配已分配 可用可用 P1 10 5 3 P2 4 2 P3

51、 9 2進程進程 最大需求最大需求 已分配已分配 可用可用 P1 10 5 2 P2 4 2 P3 9 3a ab b3.6預防和避免死鎖的方法預防和避免死鎖的方法結果：結果：T0時刻系統(tǒng)處于安全狀態(tài)。（安全序列時刻系統(tǒng)處于安全狀態(tài)。（安全序列）P1P2 P3可用可用 5(5)2(2)2(7)35(5)4(0)2(7)15(5) 2(7)510(0) 2(7)0 2(7)10 9(0)3 12結果：結果：T1時刻系統(tǒng)處于不安全狀態(tài)。時刻系統(tǒng)處于不安全狀態(tài)。P1P2 P3可用可用 5(5)2(2)3(6)25(5)4(0)3(6)05(5) 3(6)43.6預防和避免死鎖的方法預防和避免死鎖的方

52、法利用銀行家算法避免死鎖利用銀行家算法避免死鎖u數(shù)據(jù)結構數(shù)據(jù)結構n個進程個進程 (P1, , Pn)，m類資源類資源(R1, , Rm)n可利用資源向量可利用資源向量Available（m）Availablej表示表示 Rj 類資源的可用數(shù)目。類資源的可用數(shù)目。n最大需求矩陣最大需求矩陣Max（nm）Maxi, j表示進程表示進程 Pi 對對 Rj 類資源的最大需求量。類資源的最大需求量。n分配矩陣分配矩陣Allocation（nm）Allocation i, j表示已分配給進程表示已分配給進程 Pi 的的 Rj 類資源的類資源的數(shù)目。數(shù)目。n需求矩陣需求矩陣Need（nm）Need i, j

53、表示進程表示進程 Pi 對對 Rj 類資源的剩余需求量。類資源的剩余需求量。nRequesti ：進程：進程 Pi 的請求向量的請求向量3.6預防和避免死鎖的方法預防和避免死鎖的方法u銀行家算法：進程銀行家算法：進程 Pi 發(fā)出資源請求發(fā)出資源請求 RequestiRequesti Needi ? 執(zhí)行安全性算法，檢查分配后的系統(tǒng)狀態(tài)執(zhí)行安全性算法，檢查分配后的系統(tǒng)狀態(tài)正式分配正式分配安全狀態(tài)安全狀態(tài)Requesti Available ?是是 試分配：試分配： Available:= Available Requesti Allocationi:= Allocationi + Request

54、iNeedi:= Needi Requesti是是將試分配作廢；將試分配作廢；恢復原資源分配狀態(tài)；恢復原資源分配狀態(tài)；進程進程Pi阻塞。阻塞。不安全不安全狀態(tài)狀態(tài)錯誤錯誤否否否否進程進程Pi 阻塞阻塞3.6預防和避免死鎖的方法預防和避免死鎖的方法u安全性算法安全性算法Work:=Available;Finish i :=false ( i=1,2,n);找一滿足下列條件的進程：找一滿足下列條件的進程：Finish i =false 且且 Needi Work Work:=Work+Allocationi ; Finish i :=true;找到找到 所有進程的所有進程的Finish i =tr

55、ue？找不到找不到是是系統(tǒng)系統(tǒng)狀態(tài)狀態(tài)安全安全不是不是系統(tǒng)系統(tǒng)狀態(tài)狀態(tài)不安全不安全3.6預防和避免死鎖的方法預防和避免死鎖的方法u例：系統(tǒng)中有五個進程例：系統(tǒng)中有五個進程P0 , P1 , P2 , P3 , P4和三類資源和三類資源A , B , C，每類資源的數(shù)量分別為，每類資源的數(shù)量分別為10、5、7，在，在T0時時刻的資源分配情況如下表。問：刻的資源分配情況如下表。問：P1發(fā)出請求向量發(fā)出請求向量Request1 (1 ,0 ,2)，能否分配？，能否分配？Process Max Allocation Need Available A B C A B C A B C A B C P0 7

56、 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 3.6預防和避免死鎖的方法預防和避免死鎖的方法結論：結論：因分配后的因分配后的系統(tǒng)狀態(tài)安全，故可以系統(tǒng)狀態(tài)安全，故可以 立即將立即將P1所申請的資源分配給它。所申請的資源分配給它。 Process Max Allocation Need Available P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6

57、 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 Request1 (1 ,0 ,2)試分配試分配（結果見（結果見紅字紅字）2 3 00 2 03 0 2安全性算法：安全性算法：Work= 2 3 0 Finish = falsefalsefalsefalsefalsetrue5 3 27 4 3true7 4 5true10 4 7true10 5 7true 3.7死鎖的檢測與解除死鎖的檢測與解除 死鎖的檢測死鎖的檢測資源分配圖資源分配圖RAG（Resource Allocation Graph） RAG=(N, E)，其中，其中:結點集結點集N

58、=P R 進程結點子集進程結點子集P=p1,p2,pn，用，用 表示。表示。 資源結點子集資源結點子集R=r1,r2,rm，用，用 表示，每類資源中的一個表示，每類資源中的一個 單位用一個單位用一個 表示。表示。邊集邊集E 請求邊請求邊 ：進程請求一個單位的資源并正在等待。：進程請求一個單位的資源并正在等待。 分配邊分配邊 ：一個單位的資源已分配給進程。：一個單位的資源已分配給進程。pirjrjpi3.7死鎖的檢測與解除死鎖的檢測與解除死鎖定理死鎖定理u死鎖定理死鎖定理nS為死鎖狀態(tài)的充分條件是，當且僅當為死鎖狀態(tài)的充分條件是，當且僅當S狀態(tài)的資源狀態(tài)的資源分配圖是不可完全簡化的。分配圖是不可完全簡化的。3.7死鎖的檢測與解除死鎖的檢測與解除uRAG的簡化過程的簡化過程n找只有分配邊而沒有請求邊相連的進程結點，將其找只有分配邊而沒有請求邊相連