操作系統(tǒng)進(jìn)程調(diào)度

第三章處理機(jī)調(diào)度與死鎖3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除教學(xué)目的:掌握優(yōu)先級、吞吐量、死鎖等基本概念熟練掌握處理機(jī)的各種調(diào)度算法掌握死鎖產(chǎn)生原因和必要條件熟練掌握用銀行家算法來避免死鎖的方法掌握死鎖的檢測和解除方法重點(diǎn)與難點(diǎn)：處理機(jī)的各種調(diào)度算法銀行家算法死鎖的解除方法3.1處理機(jī)調(diào)度的基本概念3.1.1高級、中級和低級調(diào)度3.1.2調(diào)度隊(duì)列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干原則高級調(diào)度：又稱為作業(yè)調(diào)度或長程調(diào)度。用于決定把后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，為它們創(chuàng)建進(jìn)程、分配必要的資源，再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。在批處理系統(tǒng)中，大多配有作業(yè)調(diào)度，但在分時和實(shí)時系統(tǒng)中，卻往往不配置作業(yè)調(diào)度。作業(yè)調(diào)度的運(yùn)行頻率較低，通常為幾分鐘一次。3.1.1高級、中級和低級調(diào)度——調(diào)度的類型執(zhí)行作業(yè)調(diào)度時，需要解決：（1）一次接納多少作業(yè)：即允許多少個作業(yè)同時在內(nèi)存中運(yùn)行。（2）接納哪些作業(yè)：即哪些作業(yè)調(diào)入內(nèi)存，取決于所采用的算法。比如先來先服務(wù)調(diào)度算法；或者是短作業(yè)優(yōu)先調(diào)度算法；還有基于作業(yè)優(yōu)先權(quán)的調(diào)度算法，響應(yīng)比高者優(yōu)先調(diào)度算法等。2.低級調(diào)度：又稱為進(jìn)程調(diào)度、短程調(diào)度。用于決定就緒隊(duì)列中的哪個進(jìn)程能獲得處理器,并將處理機(jī)分配給該進(jìn)程。進(jìn)程調(diào)度程序是操作系統(tǒng)最為核心的部分，進(jìn)程調(diào)度策略的優(yōu)劣直接影響到整個系統(tǒng)的性能。三種類型的操作系統(tǒng)中，都必須配置此級調(diào)度。低級調(diào)度方式分兩類：(1)非搶占方式一旦把處理機(jī)分配給某個進(jìn)程后，讓該進(jìn)程一直執(zhí)行，直到該進(jìn)程完成或者發(fā)生某事件而阻塞。引起進(jìn)程調(diào)度的因素：正在執(zhí)行的進(jìn)程執(zhí)行完畢；執(zhí)行中的進(jìn)程因?yàn)樘岢鯥/O請求而暫停執(zhí)行；進(jìn)程通信或同步過程中執(zhí)行了原語操作。(2)搶占方式當(dāng)一進(jìn)程正在處理機(jī)上執(zhí)行時，系統(tǒng)可根據(jù)某種原則暫停它的執(zhí)行，并將已分配給它的處理機(jī)重新分配給另一個進(jìn)程。搶占的原則有：

優(yōu)先權(quán)原則：就緒的高優(yōu)先權(quán)進(jìn)程有權(quán)搶占低優(yōu)先權(quán)進(jìn)程的CPU。

短作業(yè)優(yōu)先原則：就緒的短作業(yè)(進(jìn)程)有權(quán)搶占長作業(yè)(進(jìn)程)的CPU。

時間片原則：一個時間片用完后，系統(tǒng)重新進(jìn)行進(jìn)程調(diào)度。3.中級調(diào)度又稱平衡負(fù)載調(diào)度、中程調(diào)度。目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。實(shí)質(zhì)是進(jìn)程的內(nèi)外存對換功能：將外存中已具備運(yùn)行條件的進(jìn)程換入內(nèi)存，而將內(nèi)存中處于阻塞狀態(tài)的某些進(jìn)程換出至外存。

在三種調(diào)度中，進(jìn)程調(diào)度的運(yùn)行頻率最高，作業(yè)調(diào)度的周期較長，中級調(diào)度的運(yùn)行頻率在上述兩者之間。三級調(diào)度之間的關(guān)系3.1.2調(diào)度隊(duì)列模型

根據(jù)os中所引入的調(diào)度的類型，形成了三種類型的調(diào)度隊(duì)列模型：僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型；具有高級和低級調(diào)度的調(diào)度隊(duì)列模型；同時具有三級調(diào)度的調(diào)度隊(duì)列模型。1.僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型2.具有高級和低級調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件1作業(yè)調(diào)度事件1出現(xiàn)時間片完等待事件2事件2出現(xiàn)……等待事件n事件n出現(xiàn)后備隊(duì)列……3.同時具有三級調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列進(jìn)程調(diào)度CPU就緒，掛起隊(duì)列中級調(diào)度阻塞，掛起隊(duì)列阻塞隊(duì)列等待事件進(jìn)程完成時間片完作業(yè)調(diào)度交互型作業(yè)后備隊(duì)列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)3.1.3選擇調(diào)度方式和調(diào)度算法的若干原則面向用戶的準(zhǔn)則(1)周轉(zhuǎn)時間短作業(yè)周轉(zhuǎn)時間：作業(yè)提交計(jì)算機(jī)到作業(yè)完成為止的時間間隔。它是作業(yè)在系統(tǒng)里的等待時間與運(yùn)行時間之和。平均作業(yè)周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間：W=T/Ts

注意：帶權(quán)周轉(zhuǎn)時間總大于1。平均作業(yè)帶權(quán)周轉(zhuǎn)時間：主要用于評價批處理系統(tǒng)。T

:作業(yè)的周轉(zhuǎn)時間，Ts:作業(yè)的運(yùn)行時間。(2)

響應(yīng)時間快從用戶通過鍵盤提交一個請求到系統(tǒng)首次產(chǎn)生響應(yīng)之間的時間間隔稱響應(yīng)時間。主要用于評價分時系統(tǒng)。(3)

截止時間的保證任務(wù)必須開始執(zhí)行的最遲時間或必須完成的最遲時間稱截止時間。主要用于評價實(shí)時系統(tǒng)。(4)

優(yōu)先權(quán)準(zhǔn)則在三種OS中，都可遵循。2.面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高吞吐量:單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。(2)

處理機(jī)利用率好

CPU總的運(yùn)行時間=CPU有效工作時間

+CPU空閑等待時間

CPU利用率=CPU有效工作時間

/CPU總的運(yùn)行時間(3)

各類資源的平衡利用3.2調(diào)度算法3.2.1先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3基于時間片輪轉(zhuǎn)調(diào)度算法調(diào)度算法的概念:根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法稱為調(diào)度算法。通常將作業(yè)或進(jìn)程歸入各種就緒或阻塞隊(duì)列。有的算法適用于作業(yè)調(diào)度，有的算法適用于進(jìn)程調(diào)度，有的兩者都適應(yīng)。3.2.1先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法最簡單的調(diào)度算法。用于作業(yè)調(diào)度時：按照作業(yè)進(jìn)入系統(tǒng)的先后次序來挑選作業(yè)，先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選。用于進(jìn)程調(diào)度時：按照進(jìn)程就緒的先后次序來調(diào)度進(jìn)程。算法特點(diǎn)：容易實(shí)現(xiàn)，效率不高，只顧及作業(yè)等候時間，沒考慮作業(yè)要求服務(wù)時間的長短，不利于短作業(yè)而優(yōu)待了長作業(yè)。1.先來先服務(wù)調(diào)度算法（FCFS）例：在單道環(huán)境下，某批處理顯然有四道作業(yè)，已知他們的進(jìn)入系統(tǒng)的時刻、估計(jì)運(yùn)算時間如下：作業(yè)進(jìn)入時刻(h)運(yùn)行時間(h)ABCD012311001100

用FCFS算法計(jì)算作業(yè)的運(yùn)行情況、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間：作業(yè)進(jìn)入時刻運(yùn)行時間開始時刻完成時刻周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間ABCD0123110011000110110211011022021100100199111001.99平均周轉(zhuǎn)時間T＝100（h）平均帶權(quán)周轉(zhuǎn)時間T’＝26.00（h）2.短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法（SJF/SPF）用于作業(yè)調(diào)度時：

SJF調(diào)度算法。以進(jìn)入系統(tǒng)的作業(yè)所要求的CPU時間為標(biāo)準(zhǔn)，總選取估計(jì)計(jì)算時間最短的作業(yè)投入運(yùn)行。用于進(jìn)程調(diào)度時：

SPF調(diào)度算法。從就緒隊(duì)列中選出估計(jì)運(yùn)行時間最短的進(jìn)程，將處理機(jī)分配給它。算法特點(diǎn)：易于實(shí)現(xiàn)，能有效降低作業(yè)的平均等待時間。缺點(diǎn)是：對長作業(yè)不利，有可能導(dǎo)致長作業(yè)（進(jìn)程）長期不被調(diào)度；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級；難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時間，從而影響調(diào)度性能。例：在單道環(huán)境下，某批處理顯然有四道作業(yè)，已知他們的進(jìn)入系統(tǒng)的時刻、估計(jì)運(yùn)算時間如下：作業(yè)進(jìn)入時刻(h)運(yùn)行時間(h)ABCD012311001100

用SJF/SPF算法計(jì)算作業(yè)的運(yùn)行情況、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間：作業(yè)進(jìn)入時刻運(yùn)行時間開始時刻完成時刻周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間ABCD0123110011000110110211011022021100100199111001.99平均周轉(zhuǎn)時間T＝100（h）平均帶權(quán)周轉(zhuǎn)時間T’＝26.00（h）思考：如果A、B、C、D四個作業(yè)同時到達(dá)，那么它們的運(yùn)行情況如何？試計(jì)算并比較。FCFS與SJF的比較

作業(yè)情

況調(diào)度算法進(jìn)程名ABCDE平均到達(dá)時間01234服務(wù)時間43524計(jì)算下面各個進(jìn)程的完成時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間，并比較兩種算法的優(yōu)劣。FCFS與SJF的比較

作業(yè)情

況調(diào)度算法進(jìn)程名ABCDE平均到達(dá)時間01234服務(wù)時間43524FCFS（a）完成時間47121418周轉(zhuǎn)時間461011149帶權(quán)周轉(zhuǎn)時間1225.53.52.8SJF（b）完成時間4918613周轉(zhuǎn)時間4816398帶權(quán)周轉(zhuǎn)時間12.673.11.52.252.13.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法用于作業(yè)調(diào)度時：系統(tǒng)將從后備隊(duì)列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。用于進(jìn)程調(diào)度時：該算法把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程。非搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)調(diào)度算法非搶占式優(yōu)先權(quán)算法：一旦將CPU分配給優(yōu)先權(quán)最高的進(jìn)程，該進(jìn)程就一直執(zhí)行下去，直至完成或發(fā)生某個事件。搶占式優(yōu)先權(quán)算法：要進(jìn)行優(yōu)先權(quán)的比較，高優(yōu)先權(quán)可以進(jìn)程可以通過調(diào)度程序立即停止當(dāng)前進(jìn)程，使得CPU重新分配。優(yōu)先權(quán)的類型：靜態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時確定的，且在進(jìn)程的整個運(yùn)行期間保持不變。靜態(tài)優(yōu)先權(quán)法簡單易行，但隨著進(jìn)程的推進(jìn)，其優(yōu)先權(quán)可能與進(jìn)程的情況不再相符。動態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時所確定的優(yōu)先權(quán)，可以隨著進(jìn)程的推進(jìn)而改變。

例如：可以規(guī)定就緒進(jìn)程的優(yōu)先權(quán)隨著等待時間的增長以速度a增加；正在執(zhí)行進(jìn)程的優(yōu)先權(quán)以速度b下降，這樣便可防止一個長作業(yè)長期壟斷處理機(jī)。HRRF實(shí)際上是一種動態(tài)優(yōu)先權(quán)調(diào)度算法。

FCFS與SJF/SPF是片面的調(diào)度算法。FCFS只考慮作業(yè)等候時間而忽視了作業(yè)的計(jì)算時間，SJF/SPF只考慮用戶估計(jì)的作業(yè)計(jì)算時間而忽視了作業(yè)等待時間。

HRRF是介乎這兩者之間的折衷算法，既考慮作業(yè)等待時間，又考慮作業(yè)的運(yùn)行時間，既照顧短作業(yè)又不使長作業(yè)的等待時間過長，改進(jìn)了調(diào)度性能。但每次調(diào)度前，都要進(jìn)行響應(yīng)比的計(jì)算，會增加系統(tǒng)開銷。3.高響應(yīng)比優(yōu)先調(diào)度算法（HRRF）：要求服務(wù)時間要求服務(wù)時間等待時間優(yōu)先權(quán)+=優(yōu)先權(quán)的變化規(guī)律可描述為：由于等待時間與服務(wù)時間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為：要求服務(wù)時間響應(yīng)時間要求服務(wù)時間要求服務(wù)時間等待時間RP=+=

如果等待時間相同，短作業(yè)容易得到較高優(yōu)先權(quán)。長作業(yè)等待時間足夠長后，也將獲得足夠高的優(yōu)先級。如果要求服務(wù)時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，實(shí)現(xiàn)的是先來先服務(wù)。例如：以下四個作業(yè)先后到達(dá)系統(tǒng)進(jìn)入調(diào)度：作業(yè)名到達(dá)時間所需CPU時間作業(yè)10 20

作業(yè)25 15

作業(yè)3105

作業(yè)415 10

FCFS調(diào)度算法：平均作業(yè)周轉(zhuǎn)時間T=(20+30+30+35)/4=28.75平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=(20/20+30/15+30/5+35/10)/4=3.13

SJF調(diào)度算法：調(diào)度順序?yàn)樽鳂I(yè)1、3、4、2，平均作業(yè)周轉(zhuǎn)時間T=(20+15+20+45)/4=25平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=(20/20+15/5+25/10+45/15)/4=2.25

高響應(yīng)比調(diào)度算法：開始只有作業(yè)1，被選中執(zhí)行時間20；作業(yè)1執(zhí)行完畢，響應(yīng)比依次為1+15/15、1+10/5、1+5/10，作業(yè)3被選中，執(zhí)行時間5；作業(yè)3執(zhí)行完畢，響應(yīng)比依次為1+20/15、1+10/10，作業(yè)2被選中，執(zhí)行時間15；作業(yè)2執(zhí)行完畢，作業(yè)4被選中，執(zhí)行時間10；平均作業(yè)周轉(zhuǎn)時間T=(20+15+35+35)/4=26.25平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=(20/20+15/5+35/15+35/10)/4=2.423.2.3基于時間片輪轉(zhuǎn)調(diào)度算法把CPU劃分成若干時間片,并且按順序賦給就緒隊(duì)列中的每一個進(jìn)程，進(jìn)程輪流占有CPU，當(dāng)時間片用完時，即使進(jìn)程未執(zhí)行完畢，系統(tǒng)也剝奪該進(jìn)程的CPU，將該進(jìn)程排在就緒隊(duì)列末尾。同時系統(tǒng)選擇另一個進(jìn)程運(yùn)行。時間片長度的選取非常重要，時間片長度的選擇會直接影響系統(tǒng)開銷和響應(yīng)時間。1.時間片輪轉(zhuǎn)法（RR）簡單輪轉(zhuǎn)法調(diào)度模型輪轉(zhuǎn)法中時間片大小的影響2.多級反饋隊(duì)列調(diào)度算法（FB）將就緒隊(duì)列分為N級，每個就緒隊(duì)列分配給不同的時間片，隊(duì)列級別越高，時間片越長，級別越小，時間片越短；新進(jìn)程進(jìn)入內(nèi)存后，放入第一隊(duì)列末尾，按FCFS原則等待調(diào)度，如果在一個時間片結(jié)束時沒完成，將該進(jìn)程轉(zhuǎn)入第二隊(duì)列末尾重新等待調(diào)度執(zhí)行……如此下去，當(dāng)一個長作業(yè)從第一級隊(duì)列降到最后一級隊(duì)列時，便在該隊(duì)列中采取時間片輪轉(zhuǎn)方式運(yùn)行。僅當(dāng)?shù)谝魂?duì)列空閑時，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行……類推之，僅當(dāng)?shù)?～(i-1)級隊(duì)列均空時，才調(diào)度第i級隊(duì)列上的進(jìn)程執(zhí)行。如果處理機(jī)正在為某隊(duì)列的進(jìn)程服務(wù)，又有新進(jìn)程插入到較高優(yōu)先級的隊(duì)列中，則新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)。多級反饋隊(duì)列調(diào)度算法多級反饋隊(duì)列調(diào)度算法性能：較好的性能，能夠較好地滿足各種類型用戶的需要。終端型作業(yè)用戶短批處理作業(yè)用戶長批處理作業(yè)用戶補(bǔ)充練習(xí)進(jìn)程名到達(dá)時間服務(wù)時間A03B26C44D65E82補(bǔ)充練習(xí)分別用以下調(diào)度算法：先來先服務(wù)（FCFS）非搶占短進(jìn)程優(yōu)先（SPF）搶占的短進(jìn)程優(yōu)先（SPF）高響應(yīng)比優(yōu)先（HRN）時間片輪轉(zhuǎn)（RR，時間片=1）分別計(jì)算出各進(jìn)程的完成時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。3.3實(shí)時調(diào)度3.3.1實(shí)現(xiàn)實(shí)時調(diào)度的基本條件3.3.2實(shí)時調(diào)度算法的分類3.3.3常用的兩種實(shí)時調(diào)度算法1.實(shí)時調(diào)度

根據(jù)實(shí)時系統(tǒng)的特點(diǎn)，對實(shí)時系統(tǒng)中的調(diào)度有特殊的要求，故引入一種新的調(diào)度方式——實(shí)時調(diào)度。3.3.1實(shí)現(xiàn)實(shí)時調(diào)度的基本條件思考：實(shí)時系統(tǒng)的特點(diǎn)是什么2.實(shí)時系統(tǒng)的特點(diǎn)

有限等待時間（決定性）有限響應(yīng)時間用戶控制可靠性高系統(tǒng)出錯處理能力強(qiáng)3.實(shí)現(xiàn)實(shí)時調(diào)度的基本條件

提供必要的信息如：就緒時間、開始或完成截止時間、處理時間、資源要求、絕對或相對優(yōu)先級（硬實(shí)時或軟實(shí)時）系統(tǒng)處理能力強(qiáng)采用搶占式調(diào)度機(jī)制具有快速切換機(jī)制對外部中斷的快速響應(yīng)能力、快速的任務(wù)分派能力3.3.2實(shí)時調(diào)度算法的分類根據(jù)時實(shí)任務(wù)性質(zhì)，分為：硬實(shí)時調(diào)度算法軟實(shí)時調(diào)度算法根據(jù)調(diào)度方式，分為（√）：非搶占式調(diào)度算法搶占式調(diào)度算法根據(jù)調(diào)度程序調(diào)度時間，分為：靜態(tài)調(diào)度算法動態(tài)調(diào)度算法在多處理機(jī)環(huán)境下，分為：集中式調(diào)度算法分布式調(diào)度算法1.非搶占式調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法將實(shí)時任務(wù)排成輪轉(zhuǎn)隊(duì)列，調(diào)度程序每次選擇隊(duì)列中的第一個任務(wù)運(yùn)行，當(dāng)任務(wù)自我終止或運(yùn)行完成后，此時調(diào)度程序選擇下一個隊(duì)首任務(wù)運(yùn)行；未完成的任務(wù)被掛在輪轉(zhuǎn)隊(duì)列的隊(duì)尾。用于要求不太嚴(yán)格的實(shí)時控制系統(tǒng)。非搶占式優(yōu)先調(diào)度算法在就緒隊(duì)列中，優(yōu)先級高的任務(wù)位于隊(duì)首，當(dāng)任務(wù)自我終止或運(yùn)行完成后，調(diào)度程序選擇下一個隊(duì)首任務(wù)運(yùn)行。用于有一定要求的實(shí)時控制系統(tǒng)。2.搶占式調(diào)度算法基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法當(dāng)新到來的實(shí)時任務(wù)的優(yōu)先級高于當(dāng)前任務(wù)，則等到時鐘中斷到來時，調(diào)度程序剝奪當(dāng)前任務(wù)的執(zhí)行，將處理機(jī)分配給新到的高優(yōu)先權(quán)任務(wù)。用于大多數(shù)的實(shí)時系統(tǒng)。立即搶占的優(yōu)先權(quán)調(diào)度算法操作系統(tǒng)能快速相應(yīng)外部時間中斷，一旦出現(xiàn)外部中斷，只要當(dāng)前任務(wù)未處于臨界區(qū)，便立即剝奪當(dāng)前任務(wù)的執(zhí)行，將處理機(jī)分配給請求中斷的緊迫任務(wù)。用于實(shí)時要求比較嚴(yán)格的實(shí)時控制系統(tǒng)。進(jìn)程，并立即執(zhí)行(a)非搶占輪轉(zhuǎn)調(diào)度當(dāng)前進(jìn)程實(shí)時進(jìn)程實(shí)時進(jìn)程請求調(diào)度實(shí)時進(jìn)程搶占當(dāng)前(d)立即搶占的優(yōu)先權(quán)調(diào)度調(diào)度時間進(jìn)程

1進(jìn)程

2實(shí)時進(jìn)程要求調(diào)度進(jìn)程

n實(shí)時進(jìn)程調(diào)度實(shí)時進(jìn)程運(yùn)行(b)非搶占優(yōu)先權(quán)調(diào)度當(dāng)前進(jìn)程實(shí)時進(jìn)程實(shí)時進(jìn)程請求調(diào)度當(dāng)前進(jìn)程運(yùn)行完成調(diào)度時間當(dāng)前進(jìn)程實(shí)時進(jìn)程請求調(diào)度時鐘中斷到來時調(diào)度時間(c)基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度調(diào)度時間實(shí)時進(jìn)程

實(shí)時進(jìn)程調(diào)度比較圖響應(yīng)時間：數(shù)秒至數(shù)十秒響應(yīng)時間：幾十毫秒至幾毫秒響應(yīng)時間：數(shù)秒至數(shù)百毫秒響應(yīng)時間：幾百毫秒至幾毫秒3.3.3常用的兩種實(shí)時調(diào)度算法1.最早截止時間優(yōu)先算法（即EDF算法）

根據(jù)任務(wù)的開始截止時間來確定任務(wù)的優(yōu)先級。該調(diào)度算法首先運(yùn)行隊(duì)首進(jìn)程，即開始截止時間最近的那個進(jìn)程。算法即可采用非搶占調(diào)度方式，也可采用搶占調(diào)度方式。13421234開始截止時間執(zhí)行任務(wù)任務(wù)到達(dá)t1342例：非搶占調(diào)度方式下的EDF算法。2.最低松弛度優(yōu)先算法（即LLF算法）

根據(jù)任務(wù)的緊迫程度（或松弛程度）來確定任務(wù)的優(yōu)先級。松弛度最低的任務(wù)排在就緒隊(duì)列的最前面，調(diào)度程序總是選擇隊(duì)列中的首任務(wù)執(zhí)行。算法主要用于可搶占調(diào)度方式中。

松弛度=必須完成時間-其本身的運(yùn)行時間-當(dāng)前時間例：如果系統(tǒng)中有兩個周期性的實(shí)時任務(wù)A和B：任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms；任務(wù)B要求每50ms執(zhí)行一次，執(zhí)行時間為25ms；任務(wù)A和B每次必須完成的時間分別為A1、A2、A3…和B1、B2、B3…見圖。調(diào)度情況：t3.4多處理機(jī)系統(tǒng)中的調(diào)度3.4.1多處理機(jī)系統(tǒng)的類型3.4.2進(jìn)程分配方式3.4.3進(jìn)程(線程)調(diào)度方式多處理機(jī)系統(tǒng)簡介MPS，MultiProcessorSystem20世紀(jì)70年代出現(xiàn)多處理機(jī)系統(tǒng)：是一個具有兩個或多個處理機(jī)并能相互進(jìn)行通信以協(xié)同一個大的給定問題求解的計(jì)算機(jī)系統(tǒng)。3.4.1多處理機(jī)系統(tǒng)的類型根據(jù)多處理器之間耦合的緊密程度，分為緊密耦合MPS松散耦合MPS根據(jù)系統(tǒng)中所用處理器的相同與否，分為對稱多處理器系統(tǒng)SMPS非對稱多處理器系統(tǒng)3.4.2進(jìn)程分配方式1.對稱式多處理系統(tǒng)中的進(jìn)程分配方式：靜態(tài)分配方式 每個CPU設(shè)立一個就緒隊(duì)列，進(jìn)程從開始執(zhí)行到完成，都在同一個CPU上。優(yōu)點(diǎn)：調(diào)度算法開銷小。缺點(diǎn)：容易出現(xiàn)處理機(jī)忙閑不均。動態(tài)分配方式各個CPU采用一個公共就緒隊(duì)列，隊(duì)首進(jìn)程每次分派到當(dāng)前空閑的CPU上執(zhí)行。優(yōu)點(diǎn)：消除個處理機(jī)忙閑不均的現(xiàn)象。

缺點(diǎn)：對松散耦合系統(tǒng)，會增加調(diào)度開銷。2.非對稱式多處理系統(tǒng)中的進(jìn)程分配方式

主－從處理機(jī)系統(tǒng)。操作系統(tǒng)核心駐留在主機(jī)上，由主處理機(jī)執(zhí)行調(diào)度，從機(jī)上只是用戶程序；主機(jī)管理一個公共就緒隊(duì)列，并分派進(jìn)程給從處理機(jī)執(zhí)行；各個處理機(jī)有固定分工，如執(zhí)行OS的系統(tǒng)功能，I/O處理，應(yīng)用程序。優(yōu)點(diǎn)：系統(tǒng)處理較簡單。缺點(diǎn)：存在不可靠性。當(dāng)主機(jī)太忙時，會出現(xiàn)系統(tǒng)瓶頸；當(dāng)主機(jī)出現(xiàn)故障時，會導(dǎo)致整個系統(tǒng)癱瘓?？朔椒ǎ豪枚嗯_處理機(jī)（而非一臺）來管理整個系統(tǒng)。注重整體運(yùn)行效率（而不是個別處理機(jī)的利用率）。更多樣的調(diào)度算法。多處理機(jī)訪問OS數(shù)據(jù)結(jié)構(gòu)時的互斥（對于共享內(nèi)存系統(tǒng)）。調(diào)度單位廣泛采用線程。3.多處理機(jī)調(diào)度與單處理機(jī)調(diào)度的區(qū)別3.4.3進(jìn)程(線程)調(diào)度方式

指在系統(tǒng)中設(shè)置一個公用的進(jìn)程(或線程)隊(duì)列，所有的處理器在空閑時，都可自己到該隊(duì)列中取一進(jìn)程(或線程)來執(zhí)行。是最簡單、最常用的調(diào)度方式，采用單處理機(jī)環(huán)境下的調(diào)度方式。

需要對就緒隊(duì)列的數(shù)據(jù)結(jié)構(gòu)進(jìn)行互斥訪問控制。1.自調(diào)度(self-scheduling)方式：優(yōu)點(diǎn)：易將單處理機(jī)系統(tǒng)的調(diào)度機(jī)制移植到多處理機(jī)系統(tǒng)。避免處理機(jī)忙閑不均的現(xiàn)象。缺點(diǎn)：瓶頸問題（對就緒隊(duì)列的訪問）低效性線程切換頻繁為了解決自調(diào)度方式中線程被頻繁切換的問題。是指將一組相互合作的進(jìn)程或隸屬于同一個進(jìn)程的一組線程分配到一組處理器上去同時執(zhí)行。分配處理機(jī)時間時，可采用兩種方式：面向所有應(yīng)用程序平均分配處理機(jī)時間面向所有線程平均分配處理機(jī)時間2.成組調(diào)度(gangscheduling)方式兩種分配處理器時間的方式：面向所有應(yīng)用程序平均分配處理機(jī)時間面向所有線程平均分配處理機(jī)時間優(yōu)點(diǎn)：對于一組相互合作的線程，成組調(diào)度能夠提高這些線程的執(zhí)行并行度，有利于減少阻塞和加快推進(jìn)速度，最終提高系統(tǒng)的吞吐量。每次調(diào)度可以完成多個線程的分派，能夠減少調(diào)度次數(shù)，從而減少調(diào)度的開銷。是指在一個應(yīng)用程序執(zhí)行期間，專門為該應(yīng)用程序分配一組處理器，每個線程分配一個CPU。這組處理器僅供該應(yīng)用程序?qū)Ｓ?，直至該?yīng)用程序執(zhí)行完成。適用于CPU數(shù)量眾多的高度并行系統(tǒng)，單個CPU利用率已不太重要。線程的總和不應(yīng)超過系統(tǒng)中的處理機(jī)數(shù)目。缺點(diǎn)：有線程阻塞時，造成CPU的閑置優(yōu)點(diǎn)：線程執(zhí)行時不需切換，相應(yīng)的開銷可以大大減小，推進(jìn)速度更快。3.專用處理機(jī)分配(dedicatedprocessorassignment)方式以下是線程數(shù)對加速比的影響：1234567891011121314151617181920212223241234567加速比線程數(shù)矩陣相乘FFT0例：具有16個處理器的系統(tǒng)，運(yùn)行兩個應(yīng)用程序：

矩陣相乘、快速傅立葉變換。2023/2/671 1.多道程序環(huán)境下，操作系統(tǒng)分配資源以（）為基本單位。A.程序B.指令C.進(jìn)程D.作業(yè)2.一個進(jìn)程被喚醒意味著（）。A.該進(jìn)程重新占有了CPU

B.它的優(yōu)先權(quán)變?yōu)樽畲驝.其PCB移至等待隊(duì)列隊(duì)首D.進(jìn)程變?yōu)榫途w狀態(tài)3.通常用戶進(jìn)程被建立后，（）。A便一直存在于系統(tǒng)中，直到被操作人員撤消B隨著作業(yè)運(yùn)行正常或不正常結(jié)束而撤消C隨著時間片輪轉(zhuǎn)而撤消與建立D隨著進(jìn)程的阻塞或喚醒而撤消與建立課堂練習(xí)題：2023/2/6724.操作系統(tǒng)通過（）對進(jìn)程進(jìn)行管理。A.進(jìn)程

B.進(jìn)程控制塊C.進(jìn)程啟動程序D.進(jìn)程控制區(qū)5.下面對進(jìn)程的描述中，錯誤的是（）A.進(jìn)程是動態(tài)的概念B.進(jìn)程執(zhí)行需要處理器C.進(jìn)程是有生命期的D.進(jìn)程是指令的集合6.一個運(yùn)行的進(jìn)程用完了分配給它的時間片后，它的狀態(tài)變?yōu)椋ǎ?。A.就緒

B.等待C.運(yùn)行D.由用戶自己確定7.下列的進(jìn)程狀態(tài)變化中，（）變化是不可能發(fā)生的。A.運(yùn)行—就緒B.運(yùn)行—等待C.等待—運(yùn)行D.等待—就緒答案：1、C2、D3、B4、B5、D6、A7、C3.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因3.5.2產(chǎn)生死鎖的必要條件3.5.3處理死鎖的基本方法在多道程序中，由于多個并發(fā)進(jìn)程共享系統(tǒng)的資源，如果使用不當(dāng)可能會造成一種僵局，即當(dāng)某個進(jìn)程提出資源的使用請求后，使得系統(tǒng)中一些進(jìn)程處于無休止的阻塞狀態(tài)，在無外力的作用下，這些進(jìn)程將無法繼續(xù)進(jìn)行下去，這就是死鎖。死鎖的定義死鎖舉例1可能會發(fā)生死鎖已經(jīng)發(fā)生死鎖死鎖舉例2可分配空間為200K。當(dāng)兩個進(jìn)程都執(zhí)行第二次空間請求時，發(fā)生死鎖。P1:……Request80Kbytes；……Request60Kbytes；P2:……Request70Kbytes；……Request80Kbytes；3.5.1產(chǎn)生死鎖的原因

一個操作系統(tǒng)基本上是一個資源管理者，它負(fù)責(zé)分配不同類型的資源給進(jìn)程使用。系統(tǒng)中的資源分兩類：

可剝奪性資源—指資源占有進(jìn)程雖然需要使用該資源，但另一個進(jìn)程卻能強(qiáng)行把資源從占有者進(jìn)程處搶來。

不可剝奪性資源—指只有占用者進(jìn)程不再需要使用該資源而主動釋放資源外，其它進(jìn)程不得在占有者進(jìn)程使用資源過程中強(qiáng)行搶占。1.資源資源可剝奪：CPU、主存、硬盤，該資源可為幾個進(jìn)程共同使用。不可剝奪：打印機(jī)、讀卡機(jī)、磁帶驅(qū)動器，該資源為某個進(jìn)程獨(dú)享。永久性資源和臨時性資源：永久性資源——可順序重復(fù)使用的資源：如打印機(jī)；臨時性資源——由一個進(jìn)程產(chǎn)生，被另一進(jìn)程使用一短暫時間后便無用的資源：如消息，故也稱之為消耗性資源。2.產(chǎn)生死鎖的環(huán)境多道程序設(shè)計(jì)技術(shù)多個并發(fā)進(jìn)程資源共享(獨(dú)占)沒有外力可以借助

競爭資源（不可剝奪性、臨時性）當(dāng)系統(tǒng)中供多個進(jìn)程共享的資源不足時，將引起進(jìn)程對資源的競爭而產(chǎn)生死鎖。

進(jìn)程推進(jìn)順序不合理進(jìn)程在運(yùn)行過程中具有異步性特征，如果它們之間的請求和釋放資源的順序不當(dāng)，也同樣會導(dǎo)致進(jìn)程產(chǎn)生死鎖。3.死鎖產(chǎn)生的根本原因(1)競爭資源產(chǎn)生的死鎖：請求邊分配邊進(jìn)程資源進(jìn)程資源請求邊分配邊請求邊分配邊進(jìn)程進(jìn)程請求邊分配邊（打印機(jī)）（磁帶機(jī)）………生產(chǎn)出一產(chǎn)品；P（empty）P（mutex）將產(chǎn)品放入緩沖區(qū)；V（mutex）V（full）

………(2)進(jìn)程推進(jìn)順序不合理產(chǎn)生的死鎖：例1：生產(chǎn)者—消費(fèi)者問題中，若PV操作使用不當(dāng)，把生產(chǎn)者進(jìn)程兩個P操作次序互換，先執(zhí)行P(mutex)，后執(zhí)行P(empty)，則會引起死鎖。………P（full）P（mutex）從緩沖區(qū)取出產(chǎn)品；V（mutex）V（empty）消費(fèi)該產(chǎn)品；

………生產(chǎn)者消費(fèi)者

例2：P1、P2、兩個進(jìn)程分別請求R1、R2兩種資源P1:…Request(R1);…Request(R2);…Release(R1);…Release(R2);…P2:…Request(R2);…Request(R1);…Release(R2);…Release(R1);…進(jìn)程推進(jìn)順序圖213DP2Req(R2)P2Req(R1)P1Req(R1)P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1)P1Rel(R2)4在進(jìn)程P1和P2并發(fā)執(zhí)行時，按照上圖曲線①②③所示順序推進(jìn)時，兩進(jìn)程會順利完成，我們稱這種推進(jìn)順序是合法的。若按曲線④的順序推進(jìn)時，進(jìn)入不安全區(qū)D內(nèi)，兩進(jìn)程再推進(jìn)會產(chǎn)生死鎖。3.5.2產(chǎn)生死鎖的必要條件三個必要條件：互斥條件：涉及的資源是非共享的。請求和保持條件：進(jìn)程在等待一新資源時繼續(xù)占有已分配的資源。不剝奪條件：不能強(qiáng)行剝奪進(jìn)程擁有的資源。

環(huán)路等待條件：存在一種進(jìn)程的循環(huán)鏈，鏈中的每一個進(jìn)程已獲得的資源同時被鏈中的下一個進(jìn)程所請求。

環(huán)路等待舉例

若系統(tǒng)中只有一臺打印機(jī)R1和一臺讀卡機(jī)R2，可供進(jìn)程P1和P2共享。若形成環(huán)路，這樣會產(chǎn)生死鎖。關(guān)于死鎖的有關(guān)結(jié)論1參與死鎖的進(jìn)程最少是兩個參與死鎖的進(jìn)程至少有兩個已經(jīng)占有資源參與死鎖的所有進(jìn)程都在等待資源參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集

注：如果死鎖發(fā)生，會浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。前三個條件是死鎖產(chǎn)生的必要條件，但不是充分條件；互斥條件是臨界資源的固有屬性，保證進(jìn)程互斥訪問臨界資源是必要的，不能因?yàn)榛コ鈺?dǎo)致死鎖而禁止互斥；“保持和請求”條件很多時候都存在，也是合理的。不可能要求進(jìn)程每次申請新資源時，必須釋放已占有資源；“非剝奪”條件也是應(yīng)該保留的。允許剝奪的資源是指那些，一旦剝奪中斷進(jìn)程的執(zhí)行以后，可以從斷點(diǎn)恢復(fù)執(zhí)行的資源。否則，屬于非剝奪資源。關(guān)于死鎖的有關(guān)結(jié)論2第四個條件實(shí)際上是前三個條件的可能導(dǎo)致的結(jié)果，即只有存在互斥、請求和保持與非剝奪條件，就可能出現(xiàn)循環(huán)等待，只要系統(tǒng)出現(xiàn)循環(huán)等待，則一定會出現(xiàn)死鎖；這四個條件構(gòu)成了死鎖產(chǎn)生的充分必要條件。關(guān)于死鎖的有關(guān)結(jié)論2續(xù)3.5.3處理死鎖的基本方法(1)

預(yù)防死鎖：

通過設(shè)置某些限制條件，去破壞死鎖四個必要條件中的一個或多個，來防止死鎖。較易實(shí)現(xiàn)，廣泛使用，但由于所施加的限制往往太嚴(yán)格，可能導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量的降低。(2)

避免死鎖：

不事先采取限制去破壞產(chǎn)生死鎖的條件，而是在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖的發(fā)生。實(shí)現(xiàn)較難，只需要較弱的限制條件，可獲得較高的資源利用率和系統(tǒng)吞吐量。

事先并不采取任何限制，允許發(fā)生死鎖，但可以通過系統(tǒng)的檢測機(jī)構(gòu)及時檢測出死鎖的發(fā)生，并精確確定與死鎖有關(guān)的進(jìn)程和資源。(3)

檢測死鎖：

與檢測死鎖相配套，用于將進(jìn)程從死鎖狀態(tài)解脫出來。常用的方法是撤消或掛起一些進(jìn)程。以回收一些資源，再將它們分配給處于阻塞狀態(tài)的進(jìn)程，使之轉(zhuǎn)為就緒狀態(tài)。實(shí)現(xiàn)難度大，但可獲得較好的資源利用率和系統(tǒng)吞吐量。(4)

解除死鎖：3.6死鎖的預(yù)防和避免3.6.1預(yù)防死鎖3.6.2避免死鎖3.6.3利用銀行家算法避免死鎖1.摒棄“請求和保持”條件

系統(tǒng)要求所有進(jìn)程在開始運(yùn)行之前，要一次性地申請?jiān)谡麄€運(yùn)行過程中所需的全部資源。若系統(tǒng)有足夠資源則完全分配；否則，進(jìn)程等待。3.6.1預(yù)防死鎖優(yōu)點(diǎn)：簡單、易于實(shí)現(xiàn)且安全。

基本思想：打破產(chǎn)生死鎖的四個必要條件中的一個或幾個。缺點(diǎn)：實(shí)用性不強(qiáng)：在許多情況下，一個進(jìn)程在執(zhí)行之前不可能知道它所需要的全部資源。這是由于進(jìn)程在執(zhí)行時是動態(tài)的，不可預(yù)測的；資源利用率低：無論所分資源何時用到，一個進(jìn)程只有在占有所需的全部資源后才能執(zhí)行。即使有些資源最后才被該進(jìn)程用到一次，但該進(jìn)程在生存期間卻一直占有它們，造成長期占著不用的狀況。造成極大的資源浪費(fèi)；延遲進(jìn)程的運(yùn)行：因?yàn)檫M(jìn)程只有獲得了其所需的全部資源才開始運(yùn)行，但有些資源可能長期被其它進(jìn)程占用，導(dǎo)致該進(jìn)程遲遲不能運(yùn)行。2.摒棄“不剝奪”條件

一個已擁有資源的進(jìn)程，若它再提出新資源要求而不能立即得到滿足時，它必須釋放已經(jīng)擁有的所有資源。以后需要時再重新申請。缺點(diǎn)：實(shí)現(xiàn)復(fù)雜、要付出很大的代價。原因：一個資源在使用一段時間后被釋放，可能會造成前階段工作的失效；反復(fù)地申請和釋放資源，又會使進(jìn)程的執(zhí)行無限推遲，從而進(jìn)一步增加系統(tǒng)的開銷，降低系統(tǒng)的吞吐量。3.摒棄“環(huán)路等待”條件

系統(tǒng)中的所有資源都有一個確定的唯一號碼，所有分配請求必須以序號上升的次序進(jìn)行。例如：系統(tǒng)中有下列設(shè)備：輸入機(jī)(1)，打印機(jī)(2)，穿孔機(jī)(3)，磁帶機(jī)(4)，磁盤(5)。有一進(jìn)程要先后使用輸入機(jī)、磁盤、打印機(jī)，則它申請?jiān)O(shè)備時要按輸入機(jī)、打印機(jī)、磁盤的順序申請。優(yōu)點(diǎn)：同前兩法相比，其資源利用率和系統(tǒng)吞吐量有較明顯的改善。缺點(diǎn)：系統(tǒng)中各類資源的編號必須相對穩(wěn)定，限制了新設(shè)備類型的增加；進(jìn)程實(shí)際需要資源的順序不一定與資源的編號一致，因此仍會造成資源浪費(fèi)。

該方法在系統(tǒng)運(yùn)行過程中，對進(jìn)程發(fā)出的每一個系統(tǒng)能夠滿足的資源申請進(jìn)行動態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。此方法把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可避免死鎖的發(fā)生。其中最具有代表性的避免死鎖算法是—銀行家算法。3.6.2避免死鎖1.安全狀態(tài)

如果系統(tǒng)能按某種順序（P1，P2，…,Pn）為每個進(jìn)程分配其所需的資源，直至所有進(jìn)程都能運(yùn)行完成，稱系統(tǒng)處于安全狀態(tài)。若不存在這樣一個安全序列稱系統(tǒng)處于不安全狀態(tài)。其中，<P1，P2，…,Pn>稱為安全序列。

并非所有的不安全狀態(tài)都導(dǎo)致死鎖，但當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)后，便可能進(jìn)而進(jìn)入死鎖狀態(tài)；只要系統(tǒng)處于安全狀態(tài)，便可避免進(jìn)入死鎖狀態(tài)

避免死鎖的本質(zhì)在于：當(dāng)進(jìn)行資源分配時，如何避免進(jìn)入不安全狀態(tài)。系統(tǒng)的狀態(tài)安全狀態(tài)不安全狀態(tài)死鎖安全狀態(tài)：指在某個時刻，當(dāng)多個進(jìn)程動態(tài)的申請資源時，如果存在一種順序，使得系統(tǒng)按照這種順序逐次地為每個進(jìn)程分配所需資源后每個進(jìn)程都可以在最終得到最大需求量后，依次順利地完成。避免死鎖的關(guān)鍵就是：讓系統(tǒng)在動態(tài)分配資源的過程中，不要進(jìn)入不安全狀態(tài)。安全狀態(tài)舉例：

有三個進(jìn)程p1、p2、p3，有12臺磁帶機(jī)。P1共要求10臺，P2共要求4臺，P3共要求9臺。在T0時刻，p1、p2、p3分別獲得5、2、2臺，尚有3臺空閑。進(jìn)程最大需求已分配還需可用p110553p2422p3927

經(jīng)分析，在T0時刻，系統(tǒng)是安全的。因?yàn)榇嬖谝粋€安全序列p2、p1、p3。見下圖。單銀行家算法（Banker’sAlgorithm）1965年由Dijkstra為T.H.E系統(tǒng)設(shè)計(jì)基本思想：借用了銀行借貸系統(tǒng)的分配策略?；谶@樣一些規(guī)則：客戶銀行1、第一次申請需要聲明最大資金需求量2、滿足最大需求后要及時歸還資金3、客戶申請的貸款數(shù)量不超過它自己擁有的最大值時，銀行要盡量滿足客戶需求進(jìn)程資源操作系統(tǒng)3.6.3利用銀行家算法避免死鎖最有代表性的避免死鎖算法，由Dijkstra提出。客戶銀行進(jìn)程資源操作系統(tǒng)客戶銀行進(jìn)程資源3、客戶申請的貸款數(shù)量不超過它自己擁有的最大值時，銀行要盡量滿足客戶需求操作系統(tǒng)客戶銀行進(jìn)程資源1、第一次申請需要聲明最大資金需求量2、滿足最大需求后要及時歸還資金操作系統(tǒng)客戶銀行進(jìn)程資源1、第一次申請需要聲明最大資金需求量2、滿足最大需求后要及時歸還資金操作系統(tǒng)客戶銀行進(jìn)程資源3、客戶申請的貸款數(shù)量不超過它自己擁有的最大值時，銀行要盡量滿足客戶需求1、第一次申請需要聲明最大資金需求量2、滿足最大需求后要及時歸還資金客戶銀行操作系統(tǒng)資源進(jìn)程操作系統(tǒng)資源客戶銀行進(jìn)程操作系統(tǒng)資源1、第一次申請需要聲明最大資金需求量2、滿足最大需求后要及時歸還資金客戶銀行進(jìn)程操作系統(tǒng)資源算法流程客戶abcd舉例：假設(shè)一個銀行擁有資金數(shù)量為10（單位省略），現(xiàn)在有4個客戶a,b,c,d要來貸款，所需最大資金需求量為8，5，6，7，為方便期間我們用圖形表示如下。已用資金最大需求仍需資金088055066077銀行剩余資金10初始狀態(tài)客戶已用資金最大需求仍需資金abcd187253165275銀行剩余資金4狀態(tài)1Q：如何分配才能保證銀行資金能夠順利周轉(zhuǎn)？客戶已用資金最大需求仍需資金abcd187550165275銀行剩余資金1狀態(tài)2客戶已用資金最大需求仍需資金abcd187－－－165275銀行剩余資金6狀態(tài)3客戶已用資金最大需求仍需資金abcd187－－－160275銀行剩余資金1狀態(tài)4客戶已用資金最大需求仍需資金abcd187－－－－－－275銀行剩余資金7狀態(tài)5客戶已用資金最大需求仍需資金abcd187－－－－－－270銀行剩余資金2狀態(tài)6分配策略：bcad客戶已用資金最大需求仍需資金abcd187－－－－－－－－－銀行剩余資金9狀態(tài)7客戶已用資金最大需求仍需資金abcd187－－－－－－－－－銀行剩余資金9狀態(tài)8以上討論的是單銀行家算法——只涉及到了一種資源，實(shí)際中資源的種類是多樣的，一個進(jìn)程往往需要申請多個資源才能完成工作。解決這一問題需要使用多銀行家算法。1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu)可利用資源向量Available。它是一個含有m個元素的數(shù)組，其中每個元素代表一類可利用資源的數(shù)目。最大需求矩陣Max。n*m矩陣，表示n個進(jìn)程的每一個對m類資源的最大需求。分配矩陣Allocation。n*m矩陣，表示每個進(jìn)程分配的資源數(shù)。需求矩陣Need。n*m矩陣，表示每個進(jìn)程還需要各類資源數(shù)。2.銀行家算法描述當(dāng)進(jìn)程pi提出資源申請時，系統(tǒng)執(zhí)行下列步驟：(1)

若Request[i]≤Need[i]，轉(zhuǎn)(2)；否則錯誤返回。(2)

若Request[i]≤Available，轉(zhuǎn)(3)；否則進(jìn)程等待。(3)

假設(shè)系統(tǒng)分配了資源，則有：

Available:=Available-Request[i];Allocation[i]:=Allocation[i]+Request[i];Need[i]:=Need[i]-Request[i](4)

執(zhí)行安全性算法，若系統(tǒng)新狀態(tài)是安全的，則分配完成；若系統(tǒng)新狀態(tài)是不安全的，則恢復(fù)原狀態(tài)，進(jìn)程等待。3.安全性算法為進(jìn)行安全性檢查，設(shè)置兩個向量：工作向量Work:表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，含有m個元素，在執(zhí)行安全算法開始時，Work:=Available;Finish:表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時先做Finish[i]:=false;當(dāng)有足夠資源分配給進(jìn)程時，再令Finish[i]:=true。安全性算法步驟：(1)Work:=Available;Finish:=false；(2)

尋找滿足下列條件的i：

a)Finish[i]=false；

b)Need[i]≤Work； 若找到，轉(zhuǎn)(3)；若找不到，則轉(zhuǎn)(4)。(3)Work:=Work+Allocation[i]；

Finish[i]:=true；

轉(zhuǎn)(2)。(4)

若對所有i，F(xiàn)inish[i]=true，則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)。銀行家算法實(shí)例假定系統(tǒng)中有五個進(jìn)程｛P0,P1,P2,P3,P4｝三類資源｛A,B,C｝各種資源的數(shù)量分別為10、5、7在T0時刻的資源分配情況如圖所示。（1）判斷T0時刻的安全性

資源進(jìn)程情況MaxABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122P2902302600P3222211011P4433002431(1)T0時刻的安全性檢查：T0時刻可以找到一個安全序列{p1,p3,p4,p0,p2}。系統(tǒng)是安全的。(2)

T0時刻P1請求資源，請求向量Request1(1,0,2)。執(zhí)行銀行家算法：①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available(3,3,2)③系統(tǒng)先假定可為P1分配資源，并修改Available,Allocation1和Need1向量。④進(jìn)行安全性檢查：可以找到一個安全序列{p1,p3,p4,p0,p2}。故系統(tǒng)是安全的，可以將P1的請求分配給它。

資源進(jìn)程情況MaxABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122P2902302600P3222211011P4433002431(3)

P4請求資源，請求向量Rrequest4(3,3,0)。執(zhí)行銀行家算法:①Request4(3,3,0)≤Need4(4,3,1);②Request4(3,3,0)≤Available(2,3,0);

所以P4等待。P4的請求不能分配。

資源進(jìn)程情況MaxABCAllocationABCNeedABCAvailableABCP0753020723210P1322302122P2902302600P3222211011P4433002431(4)

P0請求資源,請求向量Request0(0,2,0)Request0(0,2,0)，執(zhí)行銀行家算法：①Request0(0,2,0)≤Need0(7,4,3);②Request0(0,2,0)≤Available(2,3,0);③系統(tǒng)暫時先假定可為P0分配資源。④進(jìn)行安全性檢查：Available{2,1,0}已不能滿足任何進(jìn)程需要，所以系統(tǒng)進(jìn)入不安全狀態(tài)，P0的請求不能分配。

資源進(jìn)程情況MaxABCAllocationABCNeedABCAvailableABCP0753010743230P1322302122P2902302600P3222211011P44330024313.7死鎖的檢測與解除3.7.1死鎖的檢測3.7.2死鎖的解除

死鎖檢測與解除是指系統(tǒng)設(shè)有專門的機(jī)構(gòu)，當(dāng)死鎖發(fā)生時，該機(jī)構(gòu)能夠檢測到死鎖發(fā)生的位置和原因，并能通過外力破壞死鎖發(fā)生的必要條件，從而使得并發(fā)進(jìn)程從死鎖狀態(tài)中恢復(fù)出來。

該辦法允許死鎖發(fā)生，操作系統(tǒng)不斷監(jiān)視系統(tǒng)進(jìn)展情況，判斷死鎖是否發(fā)生。一旦死鎖發(fā)生則采取專門的措施，解除死鎖并以最小的代價恢復(fù)操作系統(tǒng)運(yùn)行。死鎖的檢測工具是:資源分配圖3.7.1死鎖的檢測1.資源分配圖定義：是描述進(jìn)程申請資源和資源分配情況的關(guān)系模型圖。表示系統(tǒng)中某個時刻進(jìn)程對資源的申請和占有情況。定義為：二元組G=（V，E）其中：

V：結(jié)點(diǎn)集，分為P(進(jìn)程集合)，R(資源集合)兩部分。即P={p1,p2,…,pn}；R={r1,r2,…,rm}。

E：邊的集合，其元素為有序二元組(pi,rj)或(rj,pi)。資源請求邊：e={pi,rj}

進(jìn)程資源的一條有向邊表示進(jìn)程pi申請rj類資源中的一個資源。資源分配邊：e={rj,pi}

資源進(jìn)程的一條有向邊表示rj類中的一個資源已被進(jìn)程pi占用。例：R1R2P2P3P4P1P1P2r1r2請求r2資源請求邊資源分配邊規(guī)則：（1）圓表示一個進(jìn)程；（2）方塊表示一個資源類，其中的圓點(diǎn)表示該類型資源中的單個資源；（3）從資源指向進(jìn)程的箭頭表示資源被分配給了這個進(jìn)程；（4）從進(jìn)程指向資源的箭頭表示進(jìn)程申請一個這類資源；(1)如果資源分配圖中無環(huán)路，則此時系統(tǒng)沒有發(fā)生死鎖。(2)如果資源分配圖中有環(huán)路，且每個資源類中僅有一個資源，則系統(tǒng)中發(fā)生了死鎖，此時，環(huán)路是系統(tǒng)發(fā)生死鎖的充要條件，環(huán)路中的進(jìn)程便為死鎖進(jìn)程。(3)如果資源分配圖中有環(huán)路，且涉及的資源類中有多個資源，則環(huán)路的存在只是產(chǎn)生死鎖的必要條件而不是充分條件。

可以利用把資源分配圖加以簡化的方法，來檢測系統(tǒng)是否為死鎖狀態(tài)。簡化方法如下：

（1）在資源分配圖中，找一個進(jìn)程pi，其請求邊均能立即得到滿足。

（2）若找到這樣的pi，則將與pi相連的邊全部刪去，轉(zhuǎn)（1）。否則過程結(jié)束。如果簡化后，所有進(jìn)程都成為孤立結(jié)點(diǎn)，則稱該圖是可完全簡化的；否則，稱該圖是不可完全簡化。

當(dāng)且僅當(dāng)系統(tǒng)某狀態(tài)s所對應(yīng)的資源分配圖是不可完全簡化的，則s是死鎖狀態(tài)。該充分條件稱為死鎖定理。2.死鎖定理死鎖檢測方法——化簡算法化簡舉例結(jié)論：系統(tǒng)不會發(fā)生死鎖。死鎖判斷標(biāo)準(zhǔn)分析：一個進(jìn)程死鎖意味著永久被阻塞。對于臨時性資源來講，它有生產(chǎn)者，生產(chǎn)者會源源不斷的生產(chǎn)資源，因此只要生產(chǎn)者進(jìn)程不被阻塞，可以認(rèn)為資源最終一定是充分的，可以滿足各消費(fèi)進(jìn)程的需要。需要的資源可以滿足則進(jìn)程一定不會死鎖。結(jié)論：判斷系統(tǒng)是否死鎖的關(guān)鍵在于判斷生產(chǎn)者進(jìn)程的狀態(tài)，若生產(chǎn)者進(jìn)程不被阻塞，則可以認(rèn)為它總會生產(chǎn)出該類資源，也就是說，某類資源的生產(chǎn)者進(jìn)程只要不被阻塞，申請這類資源的所有申請者進(jìn)程都可以得到滿足。3.7.2死鎖的解除

剝奪資源強(qiáng)迫從其它進(jìn)程剝奪足夠數(shù)量的資源給死鎖進(jìn)程，直至死鎖不存在。撤消進(jìn)程終止參與死鎖的進(jìn)程，收回它們占有的資源，從而解除死鎖。又分兩種情況：

一次性撤消參與死鎖的全部進(jìn)程，剝奪全部資源。逐步撤消參與死鎖的進(jìn)程，直至有足夠的資源可用。例:某一時刻，一個系統(tǒng)中有T1、T2、T3、T4這四個進(jìn)程，永久性資源有R1兩個、R2三個，臨時性資源有S1、S2各一個。T1產(chǎn)生S1，申請兩個單位的R2；T2占有兩個單位的R1和一個單位的R2，同時申請兩個單位的S2；T3占有一個單位的R2，同時申請一個單位的S1；T4生產(chǎn)S2，申請一個單位的S1和一個單位的R1根據(jù)以上的敘述畫出資源分配圖，并說明是否有死鎖，如果有，請指出涉及哪些進(jìn)程。死鎖的檢測和解除舉例資源分配圖系統(tǒng)中有T1、T2、T3、T4這四個進(jìn)程，永久性資源有R1兩個、R2三個，臨時性資源有S1、S2各一個。(1)T1產(chǎn)生S1，申請兩個單位的R2；(2)T2占有兩個單位的R1和一個單位的R2，同時申請兩個單位的S2；(3)T3占有一個單位的R2，同時申請一個單位的S1；(4)T4生產(chǎn)S2，申請一個單位的S1和一個單位的R1。分析：T1的執(zhí)行有賴于R2資源的釋放；R2釋放資源需要T2或T3執(zhí)行完；T3執(zhí)行需要S1資源，顯然T3不是一個阻塞進(jìn)程，T3可以首先執(zhí)行完。T3釋放資源后T1可以生成S1，T4可以得到S1但是T4還需要資源R1，而R1的資源已經(jīng)用完，有待T2釋放資源T2需要得到T4生成的S2才能釋放資源，于是發(fā)生死鎖。涉及進(jìn)程T2,T4。思考題：1、死鎖的預(yù)防方法中，不太可能的一種方法是（）。

A.摒棄互斥條件B.摒棄請求和保持條件

C.摒棄不剝奪條件D.摒棄環(huán)路等待條件2、某系統(tǒng)采用了銀行家算法，則下列敘述正確的是（）。

A.系統(tǒng)處于不安全狀態(tài)時一定會發(fā)生死鎖

B.系統(tǒng)處于不安全狀態(tài)時可能會發(fā)生死鎖

C.系統(tǒng)處于安全狀態(tài)時也可能會發(fā)生死鎖

D.不安全狀態(tài)是死鎖的一個特例3、系統(tǒng)出現(xiàn)死鎖的原因是()A.計(jì)算機(jī)系統(tǒng)發(fā)生了重大故障B．有多個封鎖的進(jìn)程同時存在C．若干進(jìn)程因競爭資源而無休止的等待著，它方釋放已占有的資源D．資源數(shù)大大少于進(jìn)程數(shù)，或進(jìn)程同時申請的資源數(shù)大大超過資源總數(shù)4、解決死鎖的途徑是()A．立即關(guān)機(jī)排除故障

B．立即關(guān)機(jī)再重新開機(jī)

C.不要共享資源，增加獨(dú)占資源D．設(shè)計(jì)預(yù)防死鎖，運(yùn)行檢測并恢復(fù)5、下面不屬于競爭資源引起死鎖的是（

）。

A.進(jìn)程推進(jìn)順序合法

B.可剝奪和非剝奪性資源

C.競爭非剝奪性資源

D.競爭臨時性資源6、下面不屬余產(chǎn)生死鎖的必要條件的是（

）。

A.互斥條件

B.請求和保護(hù)條件

C.剝奪條件

D.環(huán)路等待條件7、下面4個選項(xiàng)中，屬于處理死鎖的基本方法是（

）。

A.資源獨(dú)占

B.資源共享

C.進(jìn)程并發(fā)

D.