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

第三章

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

處理機(jī)調(diào)度的基本概念3.2

調(diào)度算法3.3

實(shí)時(shí)調(diào)度(*)3.4產(chǎn)生死鎖的原因和必要條件3.5死鎖問題的解決方法低級調(diào)度中級調(diào)度高級調(diào)度高級調(diào)度提交收容外存就緒阻塞完成就緒執(zhí)行阻塞內(nèi)存3.1

處理機(jī)調(diào)度的基本概念高/中/低級調(diào)度調(diào)度隊(duì)列模型調(diào)度方式和算法的選擇準(zhǔn)則3.1.1處理機(jī)調(diào)度的層次1、高級調(diào)度（作業(yè)調(diào)度/長程調(diào)度/接納調(diào)度）多用于批處理系統(tǒng)，決定外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存。每次調(diào)度時(shí)要考慮：

(1)接納多少作業(yè)：取決于多道程序度

(2)接納哪些作業(yè)：取決于調(diào)度算法作業(yè)調(diào)度運(yùn)行頻率低，幾分鐘一次系統(tǒng)規(guī)模運(yùn)行速度2、低級調(diào)度（進(jìn)程調(diào)度/短程調(diào)度）用來決定就緒隊(duì)列中哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派程序(Dispatcher)執(zhí)行處理機(jī)分配操作。進(jìn)程狀態(tài)：Ready<－>Running引起進(jìn)程調(diào)度的原因有：進(jìn)程正常終止或異常終止正在執(zhí)行的進(jìn)程因某種原因而阻塞（I/O請求）分時(shí)系統(tǒng)中時(shí)間片用盡當(dāng)有一個(gè)優(yōu)先級更高的進(jìn)程就緒（可搶占式）在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語操作。如：wait/signal操作、Block原語、wakeup原語等運(yùn)行頻率高，幾十毫秒一次，算法不能太復(fù)雜，以免占用太多的CPU時(shí)間。進(jìn)程調(diào)度采用兩種方式：①非搶占方式：一旦分配處理機(jī)，進(jìn)程就一直執(zhí)行，直至完成或發(fā)生某事件而被阻塞，不允許其它進(jìn)程搶占處理機(jī)。優(yōu)點(diǎn)：簡單、系統(tǒng)開銷小，適合大多數(shù)批處理系統(tǒng)缺點(diǎn)：無法滿足緊急任務(wù)的需要，不適合實(shí)時(shí)系統(tǒng)②搶占方式：允許調(diào)度程序根據(jù)某原則，暫停正在執(zhí)行的進(jìn)程，將處理機(jī)重新分配。搶占原則：優(yōu)先權(quán)原則、短作業(yè)(進(jìn)程)優(yōu)先原則、時(shí)間片原則3、中級調(diào)度（中程調(diào)度）目的：為了緩解內(nèi)存緊張問題，將那些暫時(shí)不能運(yùn)行的進(jìn)程調(diào)到外存上去等待。當(dāng)進(jìn)程運(yùn)行條件具備、且內(nèi)存又空閑時(shí)，中級調(diào)度程序決定將外存上的哪些進(jìn)程重新調(diào)入內(nèi)存。進(jìn)程狀態(tài)：Ready<－>Readysuspend,Blocked<－>Blockedsuspend運(yùn)行頻率介于高級調(diào)度和低級調(diào)度之間。3.1.2調(diào)度隊(duì)列模型僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片完交互用戶進(jìn)程調(diào)度進(jìn)程完成等待事件事件發(fā)生……具有高、低兩級調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片完作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程完成等待事件1阻塞隊(duì)列阻塞隊(duì)列等待事件2等待事件n事件1發(fā)生事件2發(fā)生事件n發(fā)生后備隊(duì)列

具有高、低、中三級調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列掛起就緒隊(duì)列CPU時(shí)間片完作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程完成事件出現(xiàn)阻塞隊(duì)列掛起等待事件中級調(diào)度事件發(fā)生后備隊(duì)列掛起阻塞隊(duì)列掛起3.1.3調(diào)度方式和算法的選擇準(zhǔn)則面向用戶的準(zhǔn)則周轉(zhuǎn)時(shí)間短——評價(jià)批處理系統(tǒng)響應(yīng)時(shí)間快——評價(jià)實(shí)時(shí)，分時(shí)系統(tǒng)截止時(shí)間保證——評價(jià)實(shí)時(shí)系統(tǒng)優(yōu)先權(quán)準(zhǔn)則——三種系統(tǒng)中皆適用公平性原則——分時(shí)系統(tǒng)面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高——評價(jià)批處理系統(tǒng)處理機(jī)利用率好——針對大中型系統(tǒng)各類資源的平衡利用——對大中型系統(tǒng)周轉(zhuǎn)時(shí)間(通常作為評價(jià)批處理系統(tǒng)的性能、選擇作業(yè)調(diào)度方式與算法的重要準(zhǔn)則之一)：

是指從作業(yè)被提交系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔。包括四部分：等待作業(yè)調(diào)度時(shí)間(高級調(diào)度)等待進(jìn)程調(diào)度時(shí)間(低級調(diào)度)執(zhí)行時(shí)間進(jìn)程等待I/O操作完成時(shí)間

平均周轉(zhuǎn)時(shí)間：

ti:作業(yè)周轉(zhuǎn)時(shí)間，tci：作業(yè)完成時(shí)間，tsi:作業(yè)提交（到達(dá)）時(shí)間ti=tci-tsi帶權(quán)周轉(zhuǎn)時(shí)間：

平均帶權(quán)周轉(zhuǎn)時(shí)間：

tr:作業(yè)實(shí)際運(yùn)行時(shí)間響應(yīng)時(shí)間(用來評價(jià)分時(shí)系統(tǒng)的性能，選擇分時(shí)系統(tǒng)中進(jìn)程調(diào)度算法的重要準(zhǔn)側(cè)之一)：從用戶通過鍵盤提交一個(gè)請求開始直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間。

響應(yīng)時(shí)間包括三部分時(shí)間：從鍵盤輸入的請求信息傳送到處理機(jī)的時(shí)間、處理時(shí)間、響應(yīng)信息回送終端的時(shí)間。3.2

調(diào)度算法先來先服務(wù)短作業(yè)（進(jìn)程）優(yōu)先高優(yōu)先權(quán)先調(diào)度時(shí)間片輪轉(zhuǎn)多級反饋隊(duì)列1、先來先服務(wù)（FCFS）可用于作業(yè)調(diào)度和進(jìn)程調(diào)度進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A01B1100C21D3100周轉(zhuǎn)時(shí)間=完成時(shí)間–

到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)（運(yùn)行）時(shí)間0111011011021022021100100199111001.99優(yōu)缺點(diǎn)：實(shí)現(xiàn)簡單有利于長作業(yè)（進(jìn)程），不利于短作業(yè)（進(jìn)程）。有利于CPU繁忙型作業(yè)，不利于I/O繁忙型作業(yè)。2、短作業(yè)/進(jìn)程優(yōu)先（SJF/SPF）短作業(yè)優(yōu)先（SJF）從后備隊(duì)列中選擇估計(jì)運(yùn)行時(shí)間最短的作業(yè)，調(diào)入內(nèi)存運(yùn)行。短進(jìn)程優(yōu)先（SPF）從就緒隊(duì)列中選出估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行。直到運(yùn)行完成，或發(fā)生某事件而被阻塞，進(jìn)程才會(huì)讓出處理機(jī)——非搶占式。優(yōu)點(diǎn)：有效地降低了作業(yè)的平均等待時(shí)間，提高系統(tǒng)的吞吐量。缺點(diǎn)：對長作業(yè)不利，有可能長期不被調(diào)度。完全沒考慮作業(yè)的緊迫程度（某些特殊的）。用戶做出的估計(jì)時(shí)間帶有很大的主觀性。2.259133.5141844E3.216182101252C2.678926731B1.5365.5111423D2.11帶權(quán)周轉(zhuǎn)時(shí)間84周轉(zhuǎn)時(shí)間4完成時(shí)間SJF2.81帶權(quán)周轉(zhuǎn)時(shí)間94周轉(zhuǎn)時(shí)間4完成時(shí)間FCFS4服務(wù)時(shí)間0到達(dá)時(shí)間平均A進(jìn)程名

作調(diào)業(yè)度情算況法3、高優(yōu)先權(quán)優(yōu)先調(diào)度算法（HPF）作業(yè)調(diào)度：從后備隊(duì)列中選擇若干個(gè)優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。進(jìn)程調(diào)度：把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程非搶占式優(yōu)先權(quán)算法：一旦分配處理機(jī)給優(yōu)先權(quán)最高的進(jìn)程，進(jìn)程便一直執(zhí)行直至完成，或發(fā)生某事件而被阻塞。主要用于批處理系統(tǒng)和實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)。搶占式優(yōu)先權(quán)算法：一旦系統(tǒng)中出現(xiàn)一個(gè)新的就緒進(jìn)程Pi，就將其優(yōu)先權(quán)與正在執(zhí)行的進(jìn)程Pj進(jìn)行比較，如果Pi>Pj，那么就做進(jìn)程切換，使Pi投入運(yùn)行。常用于要求嚴(yán)的實(shí)時(shí)系統(tǒng)，以及對性能要求高的批處理和分時(shí)系統(tǒng)中。關(guān)鍵：優(yōu)先權(quán)的確定優(yōu)先權(quán)類型一：靜態(tài)優(yōu)先權(quán)在進(jìn)程創(chuàng)建時(shí)確定的，在進(jìn)程整個(gè)運(yùn)行期間保持不變。通常根據(jù)進(jìn)程類型、進(jìn)程對資源的要求、用戶要求來確定進(jìn)程優(yōu)先權(quán)簡單易行，但不夠精確，可能出現(xiàn)優(yōu)先權(quán)低的進(jìn)程長期得不到執(zhí)行的情況。t(等待)優(yōu)先權(quán)t(運(yùn)行)優(yōu)先權(quán)優(yōu)先權(quán)類型二：動(dòng)態(tài)優(yōu)先權(quán)在進(jìn)程創(chuàng)建時(shí)創(chuàng)立的優(yōu)先權(quán)，可隨進(jìn)程的推進(jìn)或等待時(shí)間的增加而改變。如等待時(shí)間長，優(yōu)先權(quán)升高。高響應(yīng)比優(yōu)先調(diào)度算法（FCFS和SJF的折中）為每個(gè)進(jìn)程引入動(dòng)態(tài)優(yōu)先權(quán)，隨著等待時(shí)間增加優(yōu)先權(quán)提高。W1+T+WT=TRp=響應(yīng)時(shí)間作業(yè)估計(jì)運(yùn)行時(shí)間=T——作業(yè)估計(jì)運(yùn)行時(shí)間（要求服務(wù)時(shí)間）W——作業(yè)在后備隊(duì)列中的等待時(shí)間作業(yè)等待時(shí)間相同，則作業(yè)要求的服務(wù)時(shí)間愈短，優(yōu)先權(quán)愈高，因而有利于短作業(yè)。當(dāng)要求的服務(wù)時(shí)間相同，則等待時(shí)間愈長，優(yōu)先權(quán)愈高，因而實(shí)現(xiàn)了先來先服務(wù)。長作業(yè)也能保證得到執(zhí)行。

例2：下表說明了采用響應(yīng)比高者(HRRN)優(yōu)先調(diào)度算法時(shí)上述作業(yè)組合運(yùn)行的情況。表中單位：小時(shí)，并以十進(jìn)制計(jì)作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間18.002.0028.500.5039.000.1049.500.20平均周轉(zhuǎn)時(shí)間t=1.625平均帶權(quán)周轉(zhuǎn)時(shí)間w=5.6758.0010.0010.0010.1010.1010.6010.6010.802.002.101.101.3014.2116.5采用HRN算法時(shí)，這四個(gè)作業(yè)的執(zhí)行次序?yàn)椋篔1，J3，J2，J4。之所以會(huì)是這樣的次序，是因?yàn)樵撍惴ㄔ谝粋€(gè)作業(yè)運(yùn)行完時(shí)要計(jì)算剩下的所有作業(yè)的響應(yīng)比，然后選響應(yīng)比高者去運(yùn)行。例如，當(dāng)J1結(jié)束時(shí)，J2、J3、J4的響應(yīng)比計(jì)算如下：

rp2=1+作業(yè)等待時(shí)間／執(zhí)行時(shí)間

=1+(10.00-8.50)／0.5 =1+3rp3=1+作業(yè)等待時(shí)間／執(zhí)行時(shí)間

=1+(10.00-9.00)／0.10 =1+10rp4=1+作業(yè)等待時(shí)間／執(zhí)行時(shí)間

=1+(10.00-9.50)／0.20 =1+2.5從計(jì)算結(jié)果可看出，J3的響應(yīng)比最高，所以讓J3先運(yùn)行。當(dāng)J3運(yùn)行結(jié)束以及以后選中的作業(yè)運(yùn)行結(jié)束時(shí)，都用上述方法計(jì)算出當(dāng)時(shí)各作業(yè)的響應(yīng)比，然后選出響應(yīng)比高的去運(yùn)行。4、時(shí)間片輪轉(zhuǎn)RR特別適用于分時(shí)系統(tǒng)的搶占方式調(diào)度算法。系統(tǒng)將所有的就緒進(jìn)程按FIFO原則排成一個(gè)隊(duì)列，將CPU分配給隊(duì)首進(jìn)程，執(zhí)行一個(gè)時(shí)間片。在時(shí)間片內(nèi)進(jìn)程未完，則插入就緒隊(duì)列未尾，CPU交給下一個(gè)進(jìn)程。時(shí)間片選擇問題：固定時(shí)間片、可變時(shí)間片與時(shí)間片大小有關(guān)的因素：系統(tǒng)響應(yīng)時(shí)間、就緒進(jìn)程個(gè)數(shù)、CPU能力時(shí)間片的大小對系統(tǒng)性能有很大影響：時(shí)間片小，意味著會(huì)頻繁地執(zhí)行進(jìn)程調(diào)度和進(jìn)程上下文的切換，這無疑會(huì)增加系統(tǒng)開銷；時(shí)間片太長，則RR算法退化為FCFS算法，無法滿足短作業(yè)和交互式用戶的需求；一個(gè)較為可取的時(shí)間片大小是略大于一次典型的交互所需要的時(shí)間，使大多數(shù)交互式進(jìn)程能在一個(gè)時(shí)間片內(nèi)完成，從而可以獲得很小的響應(yīng)時(shí)間。3.2513173.25131744E2.259113.5141642C2673.67111231B5101336923D2.71帶權(quán)周轉(zhuǎn)時(shí)間8.44周轉(zhuǎn)時(shí)間4完成時(shí)間RRq=43.433.75帶權(quán)周轉(zhuǎn)時(shí)間11.815周轉(zhuǎn)時(shí)間15完成時(shí)間RRq=14服務(wù)時(shí)間0到達(dá)時(shí)間平均A進(jìn)程名

作時(shí)業(yè)間情片況

5、多級反饋隊(duì)列多級反饋隊(duì)列調(diào)度算法的思想：設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級和不同長度的時(shí)間片；在優(yōu)先權(quán)愈高的隊(duì)列中，為每個(gè)進(jìn)程設(shè)置的執(zhí)行時(shí)間片就愈小。新創(chuàng)建的進(jìn)程，首先被掛到第一優(yōu)先級的隊(duì)列，然后按FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到其執(zhí)行時(shí)，如它能在設(shè)定時(shí)間片內(nèi)完成，便撤離系統(tǒng)；如果不能完成，便被掛入第二級隊(duì)列的末尾，……，最后一級隊(duì)列采用時(shí)間片輪轉(zhuǎn)法；僅當(dāng)?shù)谝患夑?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二級隊(duì)列中的進(jìn)程運(yùn)行，依次類推……；如果有優(yōu)先權(quán)高的新進(jìn)程到來，那么將搶占低級進(jìn)程的處理機(jī)?！嗉壏答侁?duì)列調(diào)度算法示意圖CPU時(shí)間片完進(jìn)程調(diào)度進(jìn)程完成就緒隊(duì)列一就緒隊(duì)列二就緒隊(duì)列三就緒隊(duì)列n時(shí)間片完時(shí)間片完時(shí)間片?。髢?yōu)先級高－－－－低多級反饋隊(duì)列調(diào)度算法的性能多級反饋隊(duì)列調(diào)度算法不必事先知道各種進(jìn)程所需的執(zhí)行時(shí)間，能較好地滿足各種類型用戶(進(jìn)程)的需要，是目前公認(rèn)的一種較好的進(jìn)程調(diào)度算法。終端（交互）型作業(yè)用戶短批處理作業(yè)用戶長批處理作業(yè)用戶6、基于公平原則的調(diào)度算法保證調(diào)度算法保證處理機(jī)分配的公平性。如果系統(tǒng)有n個(gè)相同類型的進(jìn)程同時(shí)運(yùn)行，為公平起見，須保證每個(gè)進(jìn)程獲得相同的處理機(jī)時(shí)間1/n。公平共享調(diào)度算法調(diào)度的公平性主要針對用戶而言，使每個(gè)用戶能獲得相同的處理機(jī)時(shí)間。3.5

產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件1、產(chǎn)生死鎖的原因死鎖（Deadlock）：是指兩個(gè)或兩個(gè)以上的進(jìn)程在運(yùn)行過程中，因爭奪資源而造成的一種互相等待（誰也無法再繼續(xù)推進(jìn)）的現(xiàn)象，若無外力作用，它們都將無法推進(jìn)下去。例如，系統(tǒng)有5臺(tái)打印機(jī)，進(jìn)程A需要4臺(tái)，進(jìn)程B需要4臺(tái)，進(jìn)程AB并發(fā)執(zhí)行，A已經(jīng)占3臺(tái)，B已經(jīng)占2臺(tái)，此時(shí)陷入死鎖。產(chǎn)生死鎖的原因：競爭資源進(jìn)程間推進(jìn)順序非法1、競爭資源引起進(jìn)程死鎖：可剝奪性資源：CPU、RAM等；非剝奪性資源：打印機(jī)、磁帶機(jī)等；競爭非剝奪性資源：系統(tǒng)中配備的非剝奪性資源的數(shù)量不能滿足諸進(jìn)程運(yùn)行的需要時(shí)，會(huì)使進(jìn)程因爭奪資源而陷入僵局。打印機(jī)P1磁帶機(jī)P2永久性資源：打印機(jī)臨時(shí)性資源：進(jìn)程通信中的消息、數(shù)據(jù)等競爭臨時(shí)性資源：P1Request(s3);Release(s1);P2Request(s1);Release(s2);P3Request(s2);Release(s3);s1P1s2P2P3s3P1Release(s1);Request(s3);P2Release(s2);Request(s1);P3Release(s3);Request(s2);2、進(jìn)程間推進(jìn)順序不當(dāng)引起死鎖進(jìn)程推進(jìn)順序合法——不會(huì)導(dǎo)致死鎖進(jìn)程推進(jìn)順序非法——可能會(huì)導(dǎo)致死鎖順序合法s1P1s2P2P3s3順序非法s1P1s2P2P3s3請求R2請求R1請求R1請求R2釋放R1釋放R2釋放R2釋放R1ttP1進(jìn)程P2進(jìn)程不安全區(qū)2、產(chǎn)生死鎖的必要條件互斥條件一個(gè)資源一次只能被一個(gè)進(jìn)程使用。請求和保持條件（部分分配）保留已經(jīng)得到的資源，還要求其它的資源。不可剝奪條件（不可搶占）資源只能被占有者釋放，不能被其它進(jìn)程強(qiáng)行搶占。環(huán)路等待條件（循環(huán)等待）系統(tǒng)中的進(jìn)程形成了環(huán)形的資源請求鏈。打印機(jī)P1磁帶機(jī)P23.6死鎖問題的解決方法預(yù)防死鎖避免死鎖檢測與解除死鎖1、預(yù)防死鎖預(yù)防：通過設(shè)置某些限制條件，破壞導(dǎo)致死鎖的四個(gè)必要條件之一。“互斥條件”——由資源的性質(zhì)決定。摒棄“請求和保持”條件------一次性預(yù)分配法在開始運(yùn)行前（創(chuàng)建時(shí)），一次性分配給進(jìn)程它所需的“全部”資源。簡單易實(shí)現(xiàn)，安全性高；資源浪費(fèi)。摒棄“不可剝奪”條件------先釋放后申請分配法當(dāng)進(jìn)程有新的資源請求時(shí)，如果得不到滿足，要先釋放原先占有的資源，待以后重新申請。等價(jià)于此進(jìn)程“被剝奪”了已經(jīng)占有的資源。實(shí)現(xiàn)比較復(fù)雜，系統(tǒng)代價(jià)很高。摒棄“循環(huán)等待”條件------資源順序分配法把系統(tǒng)資源按類型排序，進(jìn)程要按照資源的序號遞增的次序提出資源申請。較上述兩種方法的綜合性能要好；但系統(tǒng)配置資源的序號要穩(wěn)定，固定的訪問順序不一定合理。例如：

進(jìn)程A占有3號資源，現(xiàn)在又申請5號資源——占有資源號小于申請資源號，此申請可以滿足。進(jìn)程B占有5號資源，現(xiàn)在又申請3號資源——由于5>3，所以此申請不能滿足。進(jìn)程B要想得到3號資源，必須先放棄5號以及所有編號比3大的資源。例：哲學(xué)家就餐——給哲學(xué)家和筷子編號0－4

信號量定義：semaphorechopstick[4]={1,1,1,1,1};

第i(i=0,1,2,3)位哲學(xué)家活動(dòng)描述：第4位哲學(xué)家活動(dòng)描述:while(true){while(true){wait(chopstick[i]);wait(chopstick[0]);wait(chopstick[(i+1)]);wait(chopstick[4]); …………eating;eating; …………signal(chopstick[i]);signal(chopstick[0]);signal(chopstick[(i+1)]);signal(chopstick[4]); …………thinking;thinking;}}2、避免死鎖避免死鎖的方法：在資源的動(dòng)態(tài)分配過程中，用某種方法防止系統(tǒng)進(jìn)入不安全狀態(tài)。安全狀態(tài)：系統(tǒng)能按某種進(jìn)程順序(P1,P2,…,Pn)

，來為每個(gè)進(jìn)程Pi分配其所需資源，直至最大需求，使每個(gè)進(jìn)程都可以順利完成。（稱(P1,P2,…,Pn)為安全序列）反之，則系統(tǒng)處于不安全狀態(tài)。不安全狀態(tài)不一定發(fā)生死鎖，但死鎖一定屬于不安全狀態(tài)。安全狀態(tài)進(jìn)程最大需求已分配系統(tǒng)可用P1P2P310495223系統(tǒng)資源總數(shù)：12不32利用銀行家算法避免死鎖銀行家算法的實(shí)質(zhì)就是要設(shè)法保證系統(tǒng)動(dòng)態(tài)分配資源后仍然保持安全狀態(tài)，從而避免死鎖的發(fā)生。要求進(jìn)程預(yù)先告知自己的最大資源需求，并且假設(shè)系統(tǒng)擁有固定的資源總量。數(shù)據(jù)結(jié)構(gòu)：可用資源向量Available

Available[j]=k

最大需求矩陣MaxMax[i,j]=k

分配矩陣AllocationAllocation[i,j]=k

需求矩陣NeedNeed[i,j]=k

資源請求向量RequestiRequesti[j]=k安全性算法：工作向量Work、Finish1、Requesti[j]<=Need[i,j]，則轉(zhuǎn)向步驟2；否則出錯(cuò)2、Requesti[j]<=Available[j]，則轉(zhuǎn)向步驟3；否則進(jìn)程i等待3、系統(tǒng)試探著把資源分給進(jìn)程i；Available[j]=Available[j]-Requesti[j]；Allocation[i,j]=Allocation[i,j]+Requesti[j]Need[i,j]=Need[i,j]-Requesti[j]4、執(zhí)行安全性算法，檢查分配后是否處于安全狀態(tài)，若安全將資源分配；否則將試探分配作廢，恢復(fù)原來狀態(tài)，進(jìn)程i等待銀行家算法1、設(shè)置2個(gè)向量Work=Available，F(xiàn)inish[i]=false2、找滿足條件的進(jìn)程i：Finish[i]=falseNeed[i,j]<=Work[j]，若找到執(zhí)行步驟3，否則執(zhí)行步驟43、當(dāng)進(jìn)程Pi獲得資源后，順利執(zhí)行至完成，并釋放出分配給它的資源Work[j]=Work[j]+Allocation[i,j]；Finish[i]=true；gotostep24、如果所有進(jìn)程Finish[i]=true,處于安全狀態(tài)，否則處于不安全狀態(tài)。安全性算法MaxAllocationNeedAvailableABCABCABCABCP0P1P2P3P4753322902222433010200302211002743122600011431332資源總數(shù)

1057進(jìn)程資源某時(shí)刻資源分配情況ABCWork＋AllocationABCABCABCFinishAllocationNeedWork進(jìn)程資源安全序列302020230(2)若此時(shí)P1請求資源，發(fā)出請求向量Request1(1,0,2)系統(tǒng)按銀行家算法進(jìn)行檢查：

Request1(1,0,2)<=Need1(1,2,2)

Request1(1,0,2)<=Available(3,3,2)

系統(tǒng)先假定可為P1分配資源，并修改向量的值。

再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。

ABCWork＋AllocationABCABCABCFinishAllocationNeedWork進(jìn)程資源安全序列P1332122200532trueP3532011211743trueP4743431002745trueP27456003021047trueP010477430101057trueP1230020302532trueP3532011211743trueP4743431002745trueP0745743010755trueP27556003021057trueABCABCABCABC332資源總數(shù)

1057743122600011431010200302211002753322902222433P0P1P2P3P4AvailableNeedAllocationMax進(jìn)程資源某時(shí)刻資源分配情況302020230（3）若此時(shí)P4請求資源，發(fā)出請求向量Request4(3,3,0)系統(tǒng)按銀行家算法進(jìn)行檢查：

Request4(3,3,0)<=Need4(4,3,1)

Request4(3,3,0)>Available(2,3,0)

因此，讓P4等待。ABCABCABCABC332資源總數(shù)

1057743122600011431010200302211002753322902222433P0P1P2P3P4AvailableNeedAllocationMax進(jìn)程資源某時(shí)刻資源分配情況302020230（4）若此時(shí)P0請求資源，發(fā)出請求向量Request0(0,2,0)系統(tǒng)按銀行家算法進(jìn)行檢查：

Request0(0,2,0)<=Need0(7,4,3)

Request0(0,2,0)<=Available(2,3,0)

系統(tǒng)暫時(shí)先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)進(jìn)行安全性檢查，Available(2,1,0)已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源。0307232103、檢測與解除死鎖當(dāng)系統(tǒng)為進(jìn)程分配資源時(shí)，若未采取任何限制性措施，則系統(tǒng)必須提供檢測和解除死鎖的手段。為此，系統(tǒng)必須：（1）保存有關(guān)資源的請求和分配信息；（2）提供—種算法，以利用這些信息來檢測系統(tǒng)是否已進(jìn)入死鎖狀態(tài)。死鎖的檢測方法資源分配圖的化簡，檢查是否存在循環(huán)等待。周期性檢測進(jìn)程阻塞的時(shí)間，當(dāng)超過限度；或CPU利用率降到某個(gè)值時(shí)則視為死鎖。資源分配圖凡屬于E中的一個(gè)邊e∈E，都連接著P中的一個(gè)結(jié)點(diǎn)和R中的一個(gè)結(jié)點(diǎn)，e={pi,rj}是資源請求邊，由進(jìn)程pi指向資源rj，它表示進(jìn)程pi請求一個(gè)單位的rj資源。e={rj,pi}是資源分配邊，由資源rj指向進(jìn)程pi,它表示把一個(gè)單位的資源rj分配給進(jìn)程pi。死鎖定理把資源分配圖加以簡化的方法，來檢測系統(tǒng)處于S狀態(tài)時(shí)，是否為死鎖狀態(tài)。簡化方法如下：在資源分配圖中，找出—個(gè)既不阻塞又非獨(dú)立的進(jìn)程結(jié)點(diǎn)pi。在順利情況下，pi可獲得所需資源而繼續(xù)執(zhí)行，直至運(yùn)行完畢，再釋放其所占有的全部資源。這相當(dāng)于消去pi所有的請求邊和分配邊，使之成為孤立的結(jié)點(diǎn)。pi釋放資源后．便可使p2獲得資源而繼續(xù)運(yùn)行，直到p2完成后又釋放出它所占有的全部資源。在進(jìn)行一系列的簡化后，若能消去圖中所有的邊，使所有進(jìn)程都成為孤立結(jié)點(diǎn)，則稱該圖是可完全簡化的；若不能通過任何過程使該圖完全簡化，則稱該圖是不可完全簡化的。S為死鎖狀態(tài)的充分條件是，當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的。該充分條件稱為死鎖定理。P1P2r1r2資源分配圖的化簡過程：死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)可利用資源向量Available,表示m類資源中每一類資源的可用數(shù)目；把不占用資源也無資源請求的進(jìn)程記入L表中，進(jìn)程集合即Li∪L從進(jìn)程集合中找到一個(gè)Requesti≤Work的進(jìn)程，將其資源分配圖簡化，增加Work=Work+Allocationi

,將其記入L若不能把所有進(jìn)程都記入L表中，則系統(tǒng)狀態(tài)S的資源分配圖不可完全簡化，系統(tǒng)將發(fā)生死鎖。死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)Work∶=Available;L∶={Li|Allocationi=0∩Requesti=0}forallLiLdobeginforallRequesti≤WorkdobeginWork∶=Work+Allocationi;Li∪L;endenddeadlock∶=﹁(L={p1,p2,…,pn});將進(jìn)程從死鎖狀態(tài)中解脫出來。剝奪資源：從其他進(jìn)程剝奪足夠的資源給死鎖進(jìn)程，以解除死鎖狀態(tài)。撤銷進(jìn)程：撤銷全部死鎖進(jìn)程或者選擇被撤進(jìn)程代價(jià)最小的。終止所有死鎖進(jìn)程，代價(jià)較大逐個(gè)終止進(jìn)程，每終止一個(gè)進(jìn)程，都需要用死鎖檢測算法確定系統(tǒng)死鎖是否已經(jīng)解除。死鎖的解除第三章小結(jié)進(jìn)程調(diào)度、三種調(diào)度隊(duì)列模型調(diào)度算法：FCFS、SJF/SPF、HPF/HRRN、RR(平均)周轉(zhuǎn)時(shí)間、(平均)帶權(quán)周轉(zhuǎn)時(shí)間死鎖、產(chǎn)生死鎖的必要條件安全序列銀行家算法第三章作業(yè)1、設(shè)系統(tǒng)中有4個(gè)進(jìn)程P1，P2，P3和P4.在某一時(shí)刻系統(tǒng)狀態(tài)如下：最大需求量已分配資源量P162P274P332P42