第3章 調(diào)度與死鎖

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

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

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

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

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

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

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

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

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

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

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

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

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

14、，直響應(yīng)時(shí)間是從用戶通過(guò)鍵盤(pán)提交一個(gè)請(qǐng)求開(kāi)始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間，或者說(shuō)，直到屏至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間，或者說(shuō)，直到屏幕上顯示出結(jié)果為止的一段時(shí)間間隔。它包括三部幕上顯示出結(jié)果為止的一段時(shí)間間隔。它包括三部分時(shí)間：從鍵盤(pán)輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)分時(shí)間：從鍵盤(pán)輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間，處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間，以及將所間，處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間，以及將所形成的響應(yīng)信息回送到終端顯示器的時(shí)間。形成的響應(yīng)信息回送到終端顯示器的時(shí)間。3.2調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則u截止時(shí)間的保證截止時(shí)間的保證n評(píng)價(jià)實(shí)時(shí)系統(tǒng)性能、選擇實(shí)時(shí)調(diào)度算法的重要準(zhǔn)

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

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

17、1 5 C 2 2 D 3 4A0 40 4開(kāi)始時(shí)間開(kāi)始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 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調(diào)度算法調(diào)度算法短作業(yè)短作業(yè)/短進(jìn)程優(yōu)先調(diào)度算法短進(jìn)程優(yōu)先調(diào)度算法（SJFShortest Job First / SPF Shortest Process First)既適用于作業(yè)調(diào)度，又適用于進(jìn)程調(diào)度（非搶占既適用于作業(yè)調(diào)度，又適用于進(jìn)程調(diào)度（非搶占式或搶占式均可）式或搶占式均可）從后備作業(yè)隊(duì)列、就緒隊(duì)列

18、中選擇估計(jì)運(yùn)行時(shí)間從后備作業(yè)隊(duì)列、就緒隊(duì)列中選擇估計(jì)運(yùn)行時(shí)間最短的作業(yè)或進(jìn)程最短的作業(yè)或進(jìn)程優(yōu)點(diǎn)：調(diào)度性能較好優(yōu)點(diǎn)：調(diào)度性能較好缺點(diǎn)：缺點(diǎn)：1）不利于長(zhǎng)的作業(yè)或進(jìn)程）不利于長(zhǎng)的作業(yè)或進(jìn)程 2）不考慮作業(yè)或進(jìn)程的緊迫程度）不考慮作業(yè)或進(jìn)程的緊迫程度 3）估計(jì)運(yùn)行時(shí)間很難準(zhǔn)確獲得）估計(jì)運(yùn)行時(shí)間很難準(zhǔn)確獲得3.3調(diào)度算法調(diào)度算法例例1：作業(yè)調(diào)度：作業(yè)調(diào)度作業(yè)名作業(yè)名 到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 A 0 4 B 1 5 C 2 2 D 3 4開(kāi)始時(shí)間開(kāi)始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 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調(diào)度算法調(diào)度算法例例2：進(jìn)程調(diào)度：進(jìn)程調(diào)度進(jìn)程名進(jìn)程名 到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 A 0 3 B 0 5 C 0 3 D 0 4 E 8 3搶占方式搶占方式1 1、基于最短服務(wù)時(shí)間搶占、基于最短服務(wù)時(shí)間搶占：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、基于最短剩余服務(wù)時(shí)間搶占、基于最短剩余服務(wù)時(shí)間搶占：A C D E B0

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

21、類型u靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)n創(chuàng)建進(jìn)程時(shí)確定，在進(jìn)程的整個(gè)運(yùn)行期間保持不變創(chuàng)建進(jìn)程時(shí)確定，在進(jìn)程的整個(gè)運(yùn)行期間保持不變n簡(jiǎn)單易行，系統(tǒng)開(kāi)銷小，但不夠精確簡(jiǎn)單易行，系統(tǒng)開(kāi)銷小，但不夠精確n僅在要求不高的系統(tǒng)中才使用僅在要求不高的系統(tǒng)中才使用u動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)n創(chuàng)建進(jìn)程時(shí)確定初值，運(yùn)行期間基于某種原則動(dòng)態(tài)創(chuàng)建進(jìn)程時(shí)確定初值，運(yùn)行期間基于某種原則動(dòng)態(tài)改變改變n靈活，調(diào)度性能好，但系統(tǒng)開(kāi)銷大靈活，調(diào)度性能好，但系統(tǒng)開(kāi)銷大3.3調(diào)度算法調(diào)度算法例：進(jìn)程調(diào)度例：進(jìn)程調(diào)度進(jìn)程名進(jìn)程名 到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 優(yōu)先級(jí)優(yōu)先級(jí) 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調(diào)度算法調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法主要用于作業(yè)調(diào)度主要用于作業(yè)調(diào)度選擇具有最高響應(yīng)比的后備作業(yè)選擇具有最高響應(yīng)比的后備作業(yè)響應(yīng)比響應(yīng)比要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間要求服務(wù)時(shí)間響應(yīng)時(shí)間PR優(yōu)點(diǎn)：既照顧了作業(yè)到來(lái)的先后，又考慮了要求服優(yōu)點(diǎn)：既照顧了作業(yè)到來(lái)的先后，又考慮了要求服務(wù)時(shí)間的長(zhǎng)短，是務(wù)時(shí)間的長(zhǎng)短，是FCFS和和SJF的很好的折衷。的很好的折衷。缺點(diǎn)：算法較為復(fù)雜；每次調(diào)度時(shí)，均要重新計(jì)算缺點(diǎn)：算法較為復(fù)雜；每次調(diào)度時(shí)，均要重新計(jì)算響應(yīng)比。響

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

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

25、轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 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調(diào)度算法調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法適用于進(jìn)程調(diào)度適用于進(jìn)程調(diào)度-搶占方式搶占方式就緒隊(duì)列就緒隊(duì)列1（FCFS）s1CPU結(jié)束或結(jié)束或阻塞阻塞就緒隊(duì)列就緒隊(duì)列2（FCFS）s2CPU就緒隊(duì)列就緒隊(duì)列n（RR）snCPU提交提交高高優(yōu)優(yōu)先先級(jí)級(jí)低低（時(shí)間片（時(shí)間片s1s2 sn 且且si+1=2si）結(jié)束或結(jié)束或阻塞阻塞結(jié)束或結(jié)束或阻塞阻塞3.4實(shí)時(shí)調(diào)度

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

27、部中斷的快速響應(yīng)能力對(duì)外部中斷的快速響應(yīng)能力u快速的任務(wù)分派能力快速的任務(wù)分派能力3.4實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度算法的分類實(shí)時(shí)調(diào)度算法的分類實(shí)時(shí)調(diào)度是計(jì)算機(jī)科學(xué)中最活躍的研究領(lǐng)域之一實(shí)時(shí)調(diào)度是計(jì)算機(jī)科學(xué)中最活躍的研究領(lǐng)域之一分類分類u非搶占式調(diào)度算法非搶占式調(diào)度算法n非搶占式輪轉(zhuǎn)調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法n非搶占式優(yōu)先調(diào)度算法非搶占式優(yōu)先調(diào)度算法u搶占式調(diào)度算法搶占式調(diào)度算法n基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法n立即搶占的優(yōu)先權(quán)調(diào)度算法立即搶占的優(yōu)先權(quán)調(diào)度算法3.4實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度非搶占式調(diào)度算法非搶占式調(diào)度算法u非搶占式輪轉(zhuǎn)調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法n可

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

29、調(diào)度u立即搶占立即搶占(Immediate Preemption)的優(yōu)先權(quán)調(diào)度算法的優(yōu)先權(quán)調(diào)度算法n能獲得非?？斓捻憫?yīng)，可把調(diào)度延遲降低到幾毫秒能獲得非常快的響應(yīng)，可把調(diào)度延遲降低到幾毫秒至至100微秒，甚至更低。微秒，甚至更低。3.4實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度常用的幾種實(shí)時(shí)調(diào)度算法常用的幾種實(shí)時(shí)調(diào)度算法最早截止時(shí)間優(yōu)先算法（最早截止時(shí)間優(yōu)先算法（ EDFEarliest Deadline First）u根據(jù)任務(wù)的開(kāi)始截止時(shí)間來(lái)確定任務(wù)的優(yōu)先級(jí)，截止時(shí)根據(jù)任務(wù)的開(kāi)始截止時(shí)間來(lái)確定任務(wù)的優(yōu)先級(jí)，截止時(shí)間愈早，其優(yōu)先級(jí)愈高。間愈早，其優(yōu)先級(jí)愈高。u可用于搶占式調(diào)度，也可用于非搶占式調(diào)度可用于搶占式調(diào)度，也可

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

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

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

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

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

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

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

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

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

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

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

41、時(shí)，順序?yàn)?234或或3412 不會(huì)出錯(cuò)。但為不會(huì)出錯(cuò)。但為 1324 時(shí)，會(huì)死鎖。時(shí)，會(huì)死鎖。3.5產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件u競(jìng)爭(zhēng)臨時(shí)性資源可能引發(fā)死鎖競(jìng)爭(zhēng)臨時(shí)性資源可能引發(fā)死鎖n例，進(jìn)程例，進(jì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產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件進(jìn)程推進(jìn)順序不當(dāng)引發(fā)死鎖進(jìn)程推進(jìn)順序不當(dāng)引發(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進(jìn)程進(jìn)程p1和進(jìn)和進(jìn)程程p2交替占交替占用用CPU執(zhí)行執(zhí)行時(shí)，順序?yàn)闀r(shí)，順序?yàn)?或或2或或3時(shí)，時(shí)，不會(huì)出錯(cuò)。不會(huì)出錯(cuò)。但為但為 4 時(shí)，時(shí)，會(huì)死鎖。會(huì)死鎖。3.5產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件互斥條件互斥條件u每個(gè)資源要么已分配給了一個(gè)進(jìn)程，要么空閑每個(gè)資源要么已分配給了一個(gè)進(jìn)程，要么空閑請(qǐng)求和保持條件請(qǐng)求和保持條件u已經(jīng)得到資源的進(jìn)程可以申請(qǐng)新的資源，申請(qǐng)失敗時(shí)變

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

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

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

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

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

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

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

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

51、 9 2進(jìn)程進(jìn)程 最大需求最大需求 已分配已分配 可用可用 P1 10 5 2 P2 4 2 P3 9 3a ab b3.6預(yù)防和避免死鎖的方法預(yù)防和避免死鎖的方法結(jié)果：結(jié)果：T0時(shí)刻系統(tǒng)處于安全狀態(tài)。（安全序列時(shí)刻系統(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結(jié)果：結(jié)果：T1時(shí)刻系統(tǒng)處于不安全狀態(tài)。時(shí)刻系統(tǒng)處于不安全狀態(tài)。P1P2 P3可用可用 5(5)2(2)3(6)25(5)4(0)3(6)05(5) 3(6)43.6預(yù)防和避免死鎖的方法預(yù)防和避免死鎖的方

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

53、表示進(jìn)程表示進(jìn)程 Pi 對(duì)對(duì) Rj 類資源的剩余需求量。類資源的剩余需求量。nRequesti ：進(jìn)程：進(jìn)程 Pi 的請(qǐng)求向量的請(qǐng)求向量3.6預(yù)防和避免死鎖的方法預(yù)防和避免死鎖的方法u銀行家算法：進(jìn)程銀行家算法：進(jìn)程 Pi 發(fā)出資源請(qǐng)求發(fā)出資源請(qǐng)求 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是是將試分配作廢；將試分配作廢；恢復(fù)原資源分配狀態(tài)；恢復(fù)原資源分配狀態(tài)；進(jìn)程進(jìn)程Pi阻塞。阻塞。不安全不安全狀態(tài)狀態(tài)錯(cuò)誤錯(cuò)誤否否否否進(jìn)程進(jìn)程Pi 阻塞阻塞3.6預(yù)防和避免死鎖的方法預(yù)防和避免死鎖的方法u安全性算法安全性算法Work:=Available;Finish i :=false ( i=1,2,n);找一滿足下列條件的進(jìn)程：找一滿足下列條件的進(jìn)程：Finish i =false 且且 Needi Work Work:=Work+Allocationi ; Finish i :=true;找到找到 所有進(jìn)程的所有進(jìn)程的Finish i =tr

55、ue？找不到找不到是是系統(tǒng)系統(tǒng)狀態(tài)狀態(tài)安全安全不是不是系統(tǒng)系統(tǒng)狀態(tài)狀態(tài)不安全不安全3.6預(yù)防和避免死鎖的方法預(yù)防和避免死鎖的方法u例：系統(tǒng)中有五個(gè)進(jìn)程例：系統(tǒng)中有五個(gè)進(jìn)程P0 , P1 , P2 , P3 , P4和三類資源和三類資源A , B , C，每類資源的數(shù)量分別為，每類資源的數(shù)量分別為10、5、7，在，在T0時(shí)時(shí)刻的資源分配情況如下表。問(wèn)：刻的資源分配情況如下表。問(wèn)：P1發(fā)出請(qǐng)求向量發(fā)出請(qǐng)求向量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預(yù)防和避免死鎖的方法預(yù)防和避免死鎖的方法結(jié)論：結(jié)論：因分配后的因分配后的系統(tǒng)狀態(tài)安全，故可以系統(tǒng)狀態(tài)安全，故可以 立即將立即將P1所申請(qǐng)的資源分配給它。所申請(qǐng)的資源分配給它。 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)試分配試分配（結(jié)果見(jiàn)（結(jié)果見(jiàn)紅字紅字）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死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除 死鎖的檢測(cè)死鎖的檢測(cè)資源分配圖資源分配圖RAG（Resource Allocation Graph） RAG=(N, E)，其中，其中:結(jié)點(diǎn)集結(jié)點(diǎn)集N

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