處理機(jī)調(diào)度與死鎖

1、跳轉(zhuǎn)到第一頁(yè)操作系統(tǒng)的性能在很大程度上操作系統(tǒng)的性能在很大程度上取決于處理機(jī)調(diào)度性能的好壞，因取決于處理機(jī)調(diào)度性能的好壞，因而，處理機(jī)調(diào)度便成為操作系統(tǒng)設(shè)而，處理機(jī)調(diào)度便成為操作系統(tǒng)設(shè)計(jì)的中心問(wèn)題之一。計(jì)的中心問(wèn)題之一。第四章第四章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖跳轉(zhuǎn)到第一頁(yè)提高處理機(jī)的利用率及改善系統(tǒng)性提高處理機(jī)的利用率及改善系統(tǒng)性能（吞吐量、響應(yīng)時(shí)間）是處理機(jī)調(diào)度能（吞吐量、響應(yīng)時(shí)間）是處理機(jī)調(diào)度的主要目標(biāo)。的主要目標(biāo)。在多道程序環(huán)境下，進(jìn)程數(shù)目往往在多道程序環(huán)境下，進(jìn)程數(shù)目往往多于處理機(jī)數(shù)目。這就要求系統(tǒng)能按照多于處理機(jī)數(shù)目。這就要求系統(tǒng)能按照某種算法，動(dòng)態(tài)地把處理機(jī)分配給就緒某種算法

2、，動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程，使之執(zhí)行。隊(duì)列中的一個(gè)進(jìn)程，使之執(zhí)行。本章主要講述各種常用調(diào)度算法及本章主要講述各種常用調(diào)度算法及評(píng)價(jià)；介紹死鎖及其解決的辦法。評(píng)價(jià)；介紹死鎖及其解決的辦法。跳轉(zhuǎn)到第一頁(yè)4.1調(diào)度的基本概念調(diào)度的基本概念4.2調(diào)度算法調(diào)度算法4.3實(shí)時(shí)調(diào)度算法實(shí)時(shí)調(diào)度算法4.4多處理機(jī)調(diào)度多處理機(jī)調(diào)度本章主要內(nèi)容4.5死鎖死鎖4.6 解決死鎖問(wèn)題的方法解決死鎖問(wèn)題的方法跳轉(zhuǎn)到第一頁(yè)4.1.1 作業(yè)的狀態(tài)及概念作業(yè)的狀態(tài)及概念1.1.作業(yè)：在一次應(yīng)用業(yè)務(wù)處理過(guò)程中，從輸入開(kāi)始到輸出結(jié)作業(yè)：在一次應(yīng)用業(yè)務(wù)處理過(guò)程中，從輸入開(kāi)始到輸出結(jié)束，用戶要求計(jì)算機(jī)所做的有關(guān)該次業(yè)務(wù)

3、處理的全部工作為束，用戶要求計(jì)算機(jī)所做的有關(guān)該次業(yè)務(wù)處理的全部工作為一個(gè)作業(yè)。一個(gè)作業(yè)。如：用語(yǔ)言編制一個(gè)程序，系統(tǒng)完成如下工作：如：用語(yǔ)言編制一個(gè)程序，系統(tǒng)完成如下工作：編輯編輯 編編譯譯 鏈接鏈接 執(zhí)行執(zhí)行以上幾個(gè)步驟總和就是一個(gè)作業(yè)。以上幾個(gè)步驟總和就是一個(gè)作業(yè)。3.3.作業(yè)的組成：由程序、數(shù)據(jù)和作業(yè)說(shuō)明書(shū)組成。作業(yè)的組成：由程序、數(shù)據(jù)和作業(yè)說(shuō)明書(shū)組成。 微機(jī)中：微機(jī)中：批處理文件或批處理文件或SHELLSHELL程序方式編寫(xiě)作業(yè)說(shuō)明程序方式編寫(xiě)作業(yè)說(shuō)明書(shū)。書(shū)。 2.2.作業(yè)步：作業(yè)步是在一個(gè)作業(yè)的處理過(guò)程中，計(jì)算機(jī)相對(duì)獨(dú)作業(yè)步：作業(yè)步是在一個(gè)作業(yè)的處理過(guò)程中，計(jì)算機(jī)相對(duì)獨(dú)立的工作。立的

4、工作。 4.1 調(diào)度的基本概念調(diào)度的基本概念跳轉(zhuǎn)到第一頁(yè) 作業(yè)說(shuō)明書(shū)的主要內(nèi)容作業(yè)基本情況描述 作業(yè)控制描述 作業(yè)資源要求描述 要求處理時(shí)間用戶名作業(yè)名使用語(yǔ)言名允許最大處理時(shí)間控制方式操作順序出錯(cuò)處理等等內(nèi)存空間外設(shè)類型和數(shù)量處理機(jī)優(yōu)先級(jí)庫(kù)函數(shù)或?qū)嵱贸绦蛱D(zhuǎn)到第一頁(yè)4.4.作業(yè)的狀態(tài)及其轉(zhuǎn)換作業(yè)的狀態(tài)及其轉(zhuǎn)換不同的階段對(duì)應(yīng)不同的狀態(tài)：不同的階段對(duì)應(yīng)不同的狀態(tài)：后備狀態(tài)執(zhí)行狀態(tài)完成狀態(tài)后備狀態(tài)執(zhí)行狀態(tài)完成狀態(tài)等待等待就緒就緒后備后備狀態(tài)狀態(tài)等待等待就緒就緒執(zhí)行執(zhí)行交換調(diào)度交換調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度作業(yè)調(diào)度作業(yè)調(diào)度完成完成狀態(tài)狀態(tài)線程調(diào)度線程調(diào)度內(nèi)存內(nèi)存外存外存跳轉(zhuǎn)到第一頁(yè)4.1.2分級(jí)調(diào)度分級(jí)調(diào)

5、度4.1.3 進(jìn)程調(diào)度的功能和時(shí)機(jī)進(jìn)程調(diào)度的功能和時(shí)機(jī)4.1.4 調(diào)度原則與性能衡量調(diào)度原則與性能衡量周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間： irwisieiiTTTTTniinTT11平均周轉(zhuǎn)時(shí)間：平均周轉(zhuǎn)時(shí)間： )/(11irniiiinTTWWW平均帶權(quán)周轉(zhuǎn)時(shí)間：平均帶權(quán)周轉(zhuǎn)時(shí)間： 作業(yè)調(diào)度、中級(jí)調(diào)度、進(jìn)程調(diào)度作業(yè)調(diào)度、中級(jí)調(diào)度、進(jìn)程調(diào)度 、線程調(diào)度、線程調(diào)度CPUCPU周期；調(diào)度方式周期；調(diào)度方式：剝奪方式和非剝奪方式：剝奪方式和非剝奪方式公平、有效、高吞吐量、及時(shí)響應(yīng)、支持優(yōu)先公平、有效、高吞吐量、及時(shí)響應(yīng)、支持優(yōu)先響應(yīng)時(shí)間、截止時(shí)間響應(yīng)時(shí)間、截止時(shí)間跳轉(zhuǎn)到第一頁(yè)4.2調(diào)度算法調(diào)度算法4.2.1 先來(lái)

6、先服務(wù)先來(lái)先服務(wù)FCFS( First-come-First-Serverd)作業(yè)號(hào)作業(yè)號(hào)到達(dá)時(shí)刻到達(dá)時(shí)刻運(yùn)行時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間開(kāi)始時(shí)間完成時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間10100101012151015142.8351151611114102161884平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間T10.75(ms)；平均帶權(quán)周轉(zhuǎn)時(shí)間；平均帶權(quán)周轉(zhuǎn)時(shí)間W4.7(ms)。優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，有利于長(zhǎng)作業(yè)和優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，有利于長(zhǎng)作業(yè)和CPUCPU繁忙的進(jìn)程繁忙的進(jìn)程缺點(diǎn)：使短作業(yè)等待長(zhǎng)作業(yè)，重要的作業(yè)等待可能不是很重要的長(zhǎng)作業(yè)，缺點(diǎn)：使短作業(yè)等待長(zhǎng)作業(yè)，重要的作業(yè)等待可能不是很重要的長(zhǎng)作業(yè)，不

7、能用于分時(shí)和實(shí)時(shí)系統(tǒng)。不能用于分時(shí)和實(shí)時(shí)系統(tǒng)。跳轉(zhuǎn)到第一頁(yè)4.2.2 短作業(yè)優(yōu)先短作業(yè)優(yōu)先SF(Shortest-job/Process First) 作業(yè)號(hào)作業(yè)號(hào)到達(dá)時(shí)刻到達(dá)時(shí)刻運(yùn)行時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間開(kāi)始時(shí)間完成時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間10100101012151318173.43511011664102111331.5平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間T9(ms)；平均帶權(quán)周轉(zhuǎn)時(shí)間；平均帶權(quán)周轉(zhuǎn)時(shí)間W2.975(ms)。優(yōu)點(diǎn)：有利于短作業(yè)或短進(jìn)程。降低了作業(yè)的平均等待時(shí)間，提高了優(yōu)點(diǎn)：有利于短作業(yè)或短進(jìn)程。降低了作業(yè)的平均等待時(shí)間，提高了系統(tǒng)的吞吐量。系統(tǒng)的吞吐量。缺點(diǎn)

8、：用戶可能有意或無(wú)意地縮短作業(yè)的估計(jì)執(zhí)行時(shí)間，致使該算法缺點(diǎn)：用戶可能有意或無(wú)意地縮短作業(yè)的估計(jì)執(zhí)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先；不一定能真正做到短作業(yè)優(yōu)先； 跳轉(zhuǎn)到第一頁(yè)4.2.3 最高響應(yīng)比優(yōu)先最高響應(yīng)比優(yōu)先HRN(Hight-Response-Next)R響應(yīng)時(shí)間響應(yīng)時(shí)間/需運(yùn)行的時(shí)間需運(yùn)行的時(shí)間1已等待的時(shí)間已等待的時(shí)間/需運(yùn)行的時(shí)間需運(yùn)行的時(shí)間 作業(yè)號(hào)作業(yè)號(hào)到達(dá)時(shí)刻到達(dá)時(shí)刻運(yùn)行時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間開(kāi)始時(shí)間完成時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間101001010121511161533511011664102161884平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間T9.75

9、(ms)；平均帶權(quán)周轉(zhuǎn)時(shí)間；平均帶權(quán)周轉(zhuǎn)時(shí)間W3.5（ms）。）。優(yōu)點(diǎn)：優(yōu)點(diǎn)：HRNHRN既照顧了短作業(yè)，也考慮了長(zhǎng)作業(yè)；既照顧了短作業(yè)，也考慮了長(zhǎng)作業(yè)；缺點(diǎn)：每次進(jìn)行調(diào)度前，都要進(jìn)行響應(yīng)比計(jì)算，會(huì)增加系統(tǒng)的開(kāi)銷；不能缺點(diǎn)：每次進(jìn)行調(diào)度前，都要進(jìn)行響應(yīng)比計(jì)算，會(huì)增加系統(tǒng)的開(kāi)銷；不能滿足緊迫作業(yè)或進(jìn)程的需要。滿足緊迫作業(yè)或進(jìn)程的需要。跳轉(zhuǎn)到第一頁(yè)4.2.4 優(yōu)先權(quán)優(yōu)先優(yōu)先權(quán)優(yōu)先HPF(Highest-Priority-First)進(jìn)程進(jìn)程到達(dá)時(shí)刻到達(dá)時(shí)刻CPU周期周期(ms)優(yōu)先數(shù)優(yōu)先數(shù)p10224P2082P3045P418103T23.5(ms)W3(ms)T26(ms)W3.89(ms)優(yōu)

10、點(diǎn)：可以使緊迫的任務(wù)得到優(yōu)先執(zhí)行。優(yōu)點(diǎn)：可以使緊迫的任務(wù)得到優(yōu)先執(zhí)行。缺點(diǎn)：靜態(tài)優(yōu)先級(jí)易于實(shí)現(xiàn)，系統(tǒng)開(kāi)銷小，但作業(yè)或進(jìn)程的優(yōu)先級(jí)缺點(diǎn)：靜態(tài)優(yōu)先級(jí)易于實(shí)現(xiàn)，系統(tǒng)開(kāi)銷小，但作業(yè)或進(jìn)程的優(yōu)先級(jí)不夠精確；動(dòng)態(tài)優(yōu)先級(jí)須計(jì)算優(yōu)先級(jí)，增加系統(tǒng)的開(kāi)銷。不夠精確；動(dòng)態(tài)優(yōu)先級(jí)須計(jì)算優(yōu)先級(jí)，增加系統(tǒng)的開(kāi)銷。跳轉(zhuǎn)到第一頁(yè)4.2.5 輪轉(zhuǎn)法輪轉(zhuǎn)法RR(Round Robin)4.2.6 多級(jí)反饋隊(duì)列算法多級(jí)反饋隊(duì)列算法MF(Multiple Feedback)q=R/Nmax優(yōu)點(diǎn)：可以使用戶得到及時(shí)的響應(yīng)和服務(wù)。優(yōu)點(diǎn)：可以使用戶得到及時(shí)的響應(yīng)和服務(wù)。缺點(diǎn)：短進(jìn)程用戶和缺點(diǎn)：短進(jìn)程用戶和I/OI/O繁忙型進(jìn)程是不利的。特

11、別是，當(dāng)繁忙型進(jìn)程是不利的。特別是，當(dāng)“緊迫型緊迫型”的進(jìn)程到來(lái)時(shí)，并不能及時(shí)的得到處理。的進(jìn)程到來(lái)時(shí)，并不能及時(shí)的得到處理。就緒隊(duì)列1就緒隊(duì)列iCPU就緒隊(duì)列nMFMF算法可以較好地協(xié)調(diào)長(zhǎng)進(jìn)程和短進(jìn)程的執(zhí)行。算法可以較好地協(xié)調(diào)長(zhǎng)進(jìn)程和短進(jìn)程的執(zhí)行。跳轉(zhuǎn)到第一頁(yè)4.3實(shí)時(shí)調(diào)度算法實(shí)時(shí)調(diào)度算法 4.3.1 實(shí)時(shí)系統(tǒng)的特點(diǎn)實(shí)時(shí)系統(tǒng)的特點(diǎn)計(jì)算結(jié)果的正確性、時(shí)限、周期與非周期任務(wù)；計(jì)算結(jié)果的正確性、時(shí)限、周期與非周期任務(wù)；快速的切換機(jī)制與搶占式的調(diào)度策略?？焖俚那袚Q機(jī)制與搶占式的調(diào)度策略。4.3.2 實(shí)時(shí)系統(tǒng)常用調(diào)度算法實(shí)時(shí)系統(tǒng)常用調(diào)度算法 1 1頻率單調(diào)調(diào)度頻率單調(diào)調(diào)度RMSRMS（Rate-Mon

12、otontic SchedulingRate-Monotontic Scheduling）算法）算法 2 2最早截止優(yōu)先最早截止優(yōu)先EDFEDF（Earliest-Deadline-FirstEarliest-Deadline-First）算法）算法 3 3最低松馳度優(yōu)先最低松馳度優(yōu)先LLFLLF（Least-laxity-FirstLeast-laxity-First）算法）算法 跳轉(zhuǎn)到第一頁(yè)4.4多處理機(jī)調(diào)度多處理機(jī)調(diào)度4.4.1 多處理機(jī)系統(tǒng)的類型多處理機(jī)系統(tǒng)的類型 4.4.2 多處理機(jī)系統(tǒng)調(diào)度方式多處理機(jī)系統(tǒng)調(diào)度方式1 1緊密耦合緊密耦合MPSMPS和松弛耦合和松弛耦合MPSMPS2

13、2對(duì)稱多處理器系統(tǒng)和非對(duì)稱多處理器系統(tǒng)對(duì)稱多處理器系統(tǒng)和非對(duì)稱多處理器系統(tǒng)1. 1. 非對(duì)稱多處理機(jī)系統(tǒng)調(diào)度方式非對(duì)稱多處理機(jī)系統(tǒng)調(diào)度方式2 2對(duì)稱多處理機(jī)系統(tǒng)調(diào)度方式對(duì)稱多處理機(jī)系統(tǒng)調(diào)度方式自調(diào)度和組調(diào)度自調(diào)度和組調(diào)度跳轉(zhuǎn)到第一頁(yè)4.5.1 死鎖的產(chǎn)生死鎖的產(chǎn)生1 1什么是死鎖什么是死鎖 R1R2P1P22 2產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因: :系統(tǒng)資源不足，進(jìn)程推進(jìn)順序不恰當(dāng)系統(tǒng)資源不足，進(jìn)程推進(jìn)順序不恰當(dāng)4.5死鎖死鎖 死鎖死鎖是指一組并發(fā)進(jìn)程彼此互相等待對(duì)方所擁有的資源，是指一組并發(fā)進(jìn)程彼此互相等待對(duì)方所擁有的資源，且這些并發(fā)進(jìn)程在得到對(duì)方的資源之前不會(huì)釋放自己所擁有的且這些并發(fā)進(jìn)程在得

14、到對(duì)方的資源之前不會(huì)釋放自己所擁有的資源，從而使并發(fā)進(jìn)程不能繼續(xù)向前推進(jìn)的狀態(tài)。陷入死鎖狀資源，從而使并發(fā)進(jìn)程不能繼續(xù)向前推進(jìn)的狀態(tài)。陷入死鎖狀態(tài)的進(jìn)程稱之為死鎖進(jìn)程。態(tài)的進(jìn)程稱之為死鎖進(jìn)程。跳轉(zhuǎn)到第一頁(yè)4.5.2 死鎖的必要條件死鎖的必要條件（1 1）互斥條件。指進(jìn)程竟?fàn)幍馁Y源具有互斥性，即在一段時(shí)間）互斥條件。指進(jìn)程竟?fàn)幍馁Y源具有互斥性，即在一段時(shí)間內(nèi)某資源被一個(gè)進(jìn)程占用，如果此時(shí)還有其它進(jìn)程請(qǐng)求使用該內(nèi)某資源被一個(gè)進(jìn)程占用，如果此時(shí)還有其它進(jìn)程請(qǐng)求使用該資源，則只能等待，直到占用該資源的進(jìn)程用完后主動(dòng)釋放。資源，則只能等待，直到占用該資源的進(jìn)程用完后主動(dòng)釋放。（2 2）不可剝奪條件（不可

15、搶占條件）。指已分配給某一進(jìn)程的）不可剝奪條件（不可搶占條件）。指已分配給某一進(jìn)程的資源，在它未使用完之前，不能強(qiáng)行剝奪，只能在使用完后，資源，在它未使用完之前，不能強(qiáng)行剝奪，只能在使用完后，由進(jìn)程自己釋放。由進(jìn)程自己釋放。（3 3）部分分配條件（請(qǐng)求與保持條件）。指進(jìn)程已經(jīng)占用了一）部分分配條件（請(qǐng)求與保持條件）。指進(jìn)程已經(jīng)占用了一部分資源，但又提出新的資源請(qǐng)求，而該資源又被其它的進(jìn)程部分資源，但又提出新的資源請(qǐng)求，而該資源又被其它的進(jìn)程所占用，此時(shí)請(qǐng)求進(jìn)程只能阻塞，但又對(duì)自己占用的資源保持所占用，此時(shí)請(qǐng)求進(jìn)程只能阻塞，但又對(duì)自己占用的資源保持不放。不放。（4 4）環(huán)路條件（循環(huán)等待條件）。

16、指進(jìn)程發(fā)生死鎖時(shí)，必然存）環(huán)路條件（循環(huán)等待條件）。指進(jìn)程發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程資源的環(huán)形鏈。即一組進(jìn)程在一個(gè)進(jìn)程資源的環(huán)形鏈。即一組進(jìn)程P1P1，P2P2，PnPn，其，其中，中，P1P1正在等待正在等待P2P2占用的資源；占用的資源；P2P2正在等待正在等待P3P3占用的資源，占用的資源，PnPn正在等待正在等待P1P1占用的資源。圖占用的資源。圖4 47 7所示為兩個(gè)進(jìn)程竟?fàn)幩緸閮蓚€(gè)進(jìn)程竟?fàn)巸蓚€(gè)資源的環(huán)形鏈圖。兩個(gè)資源的環(huán)形鏈圖。跳轉(zhuǎn)到第一頁(yè)4.6.1 死鎖的預(yù)防死鎖的預(yù)防1 1防止防止“部分分配部分分配”條件的出現(xiàn)條件的出現(xiàn)2 2防止防止“環(huán)路等待環(huán)路等待”條件的出現(xiàn)條件的出現(xiàn)

17、4.6.2 死鎖的避免死鎖的避免1 1安全狀態(tài)安全狀態(tài)T T存在安全序列（存在安全序列（p2p2，p1p1，p3p3），系統(tǒng)處于安全狀），系統(tǒng)處于安全狀態(tài)。態(tài)。此時(shí)，系統(tǒng)進(jìn)入不安全狀態(tài)。此時(shí)，系統(tǒng)進(jìn)入不安全狀態(tài)。 4.6解決死鎖的方法解決死鎖的方法跳轉(zhuǎn)到第一頁(yè)2 2銀行家算法銀行家算法（1 1）數(shù)據(jù)結(jié)構(gòu)）數(shù)據(jù)結(jié)構(gòu) 銀行家算法中用到下列數(shù)據(jù)結(jié)構(gòu)，令銀行家算法中用到下列數(shù)據(jù)結(jié)構(gòu)，令n n是系統(tǒng)中的進(jìn)程數(shù)，是系統(tǒng)中的進(jìn)程數(shù)，m m是資源類數(shù)。是資源類數(shù)。 可用資源向量可用資源向量A A（AvailableAvailable）。向量）。向量A A的長(zhǎng)度為的長(zhǎng)度為m m，向量元素，向量元素Aj(j=1A

18、j(j=1，2 2，m)m)為系統(tǒng)中資源類為系統(tǒng)中資源類r rj j的當(dāng)前可用數(shù)。的當(dāng)前可用數(shù)。 最大需求矩陣最大需求矩陣M M（MaxMax）。）。M M是一個(gè)是一個(gè)n nm m的矩陣，矩陣元素的矩陣，矩陣元素Mi,jMi,j為進(jìn)為進(jìn)程程p pi i關(guān)于資源類關(guān)于資源類r rj j的最大需求數(shù)，每個(gè)進(jìn)程必須預(yù)先申報(bào)。的最大需求數(shù)，每個(gè)進(jìn)程必須預(yù)先申報(bào)。 資源占用矩陣資源占用矩陣U U（UseUse）。）。U U是一個(gè)是一個(gè)n nm m的矩陣，矩陣元素的矩陣，矩陣元素Ui,jUi,j為進(jìn)為進(jìn)程程p pi i關(guān)于資源類關(guān)于資源類r rj j的當(dāng)前占用數(shù)。的當(dāng)前占用數(shù)。 剩余需求矩陣剩余需求矩陣N

19、 N（NeedNeed）。）。N N是一個(gè)是一個(gè)n nm m的矩陣，矩陣元素的矩陣，矩陣元素NIi,jNIi,j是是進(jìn)程進(jìn)程p pi i還需要的資源類還需要的資源類r rj j的單位數(shù)。顯然有，的單位數(shù)。顯然有，NIi,jNIi,jMi,jMi,jUi,jUi,j。 （2 2）簡(jiǎn)記法）簡(jiǎn)記法 為了簡(jiǎn)化對(duì)算法的描述，對(duì)上述數(shù)據(jù)結(jié)構(gòu)采用如下的簡(jiǎn)記法為了簡(jiǎn)化對(duì)算法的描述，對(duì)上述數(shù)據(jù)結(jié)構(gòu)采用如下的簡(jiǎn)記法 令令X X和和Y Y為長(zhǎng)度是為長(zhǎng)度是m m的向量，若的向量，若XYXY，當(dāng)且僅當(dāng)對(duì)任意的，當(dāng)且僅當(dāng)對(duì)任意的i i（i i1 1，2 2，m m）有）有XiYiXiYi。 對(duì)于對(duì)于n nm m的矩陣的矩

20、陣Z Zn nm m，Z Zi i（i i1 1，2 2，n n）表示矩陣）表示矩陣Z Zn nm m的第的第i i個(gè)行個(gè)行向量。向量。跳轉(zhuǎn)到第一頁(yè)（3 3）算法描述）算法描述 令令RRRRi i是長(zhǎng)度為是長(zhǎng)度為m m的進(jìn)程的進(jìn)程p pi i的資源請(qǐng)求向量，元素的資源請(qǐng)求向量，元素RRi,jRRi,j是進(jìn)程是進(jìn)程p pi i希望請(qǐng)求分配的資源類希望請(qǐng)求分配的資源類r rj j的單位數(shù)。當(dāng)進(jìn)程的單位數(shù)。當(dāng)進(jìn)程p pi i向系統(tǒng)提交一個(gè)資源請(qǐng)求向系統(tǒng)提交一個(gè)資源請(qǐng)求向量向量RRRRi i時(shí)，系統(tǒng)調(diào)用銀行家算法執(zhí)行下述工作：時(shí)，系統(tǒng)調(diào)用銀行家算法執(zhí)行下述工作： 若若RRRRi i NNi i，則有（

21、，則有（RRiRRiU Ui i）M Mi i，即進(jìn)程，即進(jìn)程p pi i請(qǐng)求的資源單位數(shù)大請(qǐng)求的資源單位數(shù)大于它申請(qǐng)的最大需求數(shù)，故請(qǐng)求無(wú)效，作出錯(cuò)處理；否則進(jìn)行下一步。于它申請(qǐng)的最大需求數(shù)，故請(qǐng)求無(wú)效，作出錯(cuò)處理；否則進(jìn)行下一步。 若若RRRRi i A A，則進(jìn)程，則進(jìn)程p pi i必須等待，即系統(tǒng)當(dāng)前沒(méi)有足夠的資源滿足必須等待，即系統(tǒng)當(dāng)前沒(méi)有足夠的資源滿足進(jìn)程進(jìn)程p pi i當(dāng)前的請(qǐng)求；否則進(jìn)行下一步；當(dāng)前的請(qǐng)求；否則進(jìn)行下一步； 系統(tǒng)進(jìn)行假分配，即假設(shè)系統(tǒng)給進(jìn)程系統(tǒng)進(jìn)行假分配，即假設(shè)系統(tǒng)給進(jìn)程p pi i分配所請(qǐng)求的資源，對(duì)資分配所請(qǐng)求的資源，對(duì)資源分配狀態(tài)作如下修改：源分配狀態(tài)作如

22、下修改： A AA ARRRRi i；U Ui iU Ui iRRRRi i；N Ni iNiNiRRRRi i； 調(diào)用安全算法檢查此次資源分配后的現(xiàn)行狀態(tài)是否安全狀態(tài)。若調(diào)用安全算法檢查此次資源分配后的現(xiàn)行狀態(tài)是否安全狀態(tài)。若安全，則正式將資源分配給進(jìn)程安全，則正式將資源分配給進(jìn)程p pi i，完成進(jìn)程，完成進(jìn)程p pi i的資源請(qǐng)求分配工作。的資源請(qǐng)求分配工作。否則，拒絕分配讓進(jìn)程等待，并恢復(fù)此次的假設(shè)分配，即撤消步驟否則，拒絕分配讓進(jìn)程等待，并恢復(fù)此次的假設(shè)分配，即撤消步驟對(duì)對(duì)分配狀態(tài)所作的修改。分配狀態(tài)所作的修改。跳轉(zhuǎn)到第一頁(yè)（4 4）安全算法描述）安全算法描述 設(shè)向量設(shè)向量W W（W

23、orkWork），向量元素），向量元素Wj(j=1Wj(j=1，2 2，m)m)表示系統(tǒng)可表示系統(tǒng)可供給各個(gè)進(jìn)程繼續(xù)運(yùn)行的供給各個(gè)進(jìn)程繼續(xù)運(yùn)行的j j類資源數(shù)；向量類資源數(shù)；向量F F（FinishFinish），向量元素），向量元素Fi(i =1Fi(i =1，2 2，n)n)表示系統(tǒng)是否有足夠的資源可使進(jìn)程表示系統(tǒng)是否有足夠的資源可使進(jìn)程pipi完成。初完成。初始化始化W WA A，F(xiàn)i=falseFi=false。 從進(jìn)程集合中找到一個(gè)進(jìn)程從進(jìn)程集合中找到一個(gè)進(jìn)程p pi i，有，有Fi=falseFi=false且且NiWNiW，則執(zhí)行，則執(zhí)行步驟步驟；如果這樣的進(jìn)程不存在，則轉(zhuǎn)去執(zhí)行步驟；如果這樣的進(jìn)程不存在，則轉(zhuǎn)去執(zhí)行步驟； 進(jìn)程進(jìn)程p pi i可得到所需的全部資源，順利執(zhí)行完成，并釋放它所占可得到所需的全部資源，順利執(zhí)行完成，并釋放它所占用的資源，所以執(zhí)行用的資源，所以執(zhí)行W WW WU Ui i及及Fi=trueFi=true，轉(zhuǎn)去執(zhí)行，轉(zhuǎn)去執(zhí)行； 若對(duì)所有的進(jìn)程，都有若對(duì)所有的進(jìn)程，都有Fi=trueFi=true，則存在一個(gè)安全序列，現(xiàn)行，則存在一個(gè)安全序列，現(xiàn)行狀態(tài)是安全的，否則是不安全的。狀態(tài)是安全的，否則是不安全的。例例410 )0010(，A0014063213541000001245U16420020100207