第三章處理機調度與死鎖3.1處理機調度的基本概念3.2作業調度3.3調度算法3.4實時調度3.5產生死鎖的原因和必要條件3.6預防死鎖的方法3.7死鎖的檢測與解除3.1處理機調度的基本概念3.1.1高級、中級和低級調度

處理器調度分為三級：高級調度（作業調度）（長程調度）中級調度（中期調度）低級調度（進程調度）（短程調度）按某種原則從后備狀態挑選作業調入內存運行為作業創建進程為選中作業分配資源1.高級調度(LowLevelScheduling)2.中程調度決定哪些作業允許參于競爭處理機資源。作用：起到短期調整系統負荷，以平順系統。方式：“掛起”，“解掛”。3.低級調度按某種原則將處理機分配給就緒進程。進程調度屬操作系統內核，執行頻率很高。進程調度是最基本的一種調度，它可以采用非搶占方式或搶占方式。

1)非搶占方式(Non-preemptiveMode)在采用非搶占調度方式時，可能引起進程調度的因素可歸結為這樣幾個：①正在執行的進程執行完畢，或因發生某事件而不能再繼續執行；②執行中的進程因提出I/O請求而暫停執行；③在進程通信或同步過程中執行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。這種調度方式的優點是實現簡單、系統開銷小，適用于大多數的批處理系統環境。3.1.2調度隊列模型1.僅有進程調度的調度隊列模型僅具有進程調度的調度隊列模型2.具有高級和低級調度的調度隊列模型具有高、低兩級調度的調度隊列模型就緒隊列的形式。

(2)設置多個阻塞隊列。圖3-2示出了具有高、低兩級調度的調度隊列模型。該模型與上一模型的主要區別在于如下兩個方面。3.同時具有三級調度的調度隊列模型具有三級調度時的調度隊列模型就緒隊列進程調度CPU就緒掛起隊列中級調度阻塞掛起隊列阻塞隊列等待事件進程完成時間片完作業調度交互型作業后備隊列批量作業掛起事件出現事件出現3.2.1作業調度的職能記錄已進入系統的作業情況JCB調度算法：按照某種調度算法從后備狀態挑選作業運行。運行準備：為選中作業創建進程，分配主存和外設。結束善后處理：收回資源，輸出必要信息。作業進入后備狀態建立作業退出系統時撤消3.2作業調度3.2.2作業控制塊作業存在唯一標志作業調度的依據記錄作業的有關信息，反映作業運行情況內容進入系統時建立退出系統時撤消作業名資源要求資源使用情況類型說明狀態3.2.3調度性能的衡量平均周轉時間：作業kTk=Tck-Tsk=T等待+T運行平均周轉時間T=1/nTk帶權周轉時間：作業kWk=Tk/TRk

平均帶權周轉時間W=1/nWkK=1nK=1

nTck：作業K完成時間Tsk：作業K提交時間TRk：作業K運行時間3.2.4選擇調度方式和調度算法的若干準則1.面向用戶的準則

周轉時間短。響應時間快。(3)截止時間的保證。(4)優先權準則。

2.面向系統的準則

系統吞吐量高。(2)處理機利用率好。(3)各類資源的平衡利用。

3.3調度算法

先進先服務調度算法短作業優先調度算法高優先權優先調度算法最高響應比優先時間片輪轉調度算法最短剩余時間優先調度算法均衡法多級反饋隊列調度算法3.3.1先來先服務調度算法其原則按照作業到達系統或進程進入就緒隊列先后次序來選擇。FIFO是一種非搶占算法。例題

進程到達時間服務時間優先數10322265344346565821作業1作業2作業3作業4作業5039131820T=1/5（3+7+9+12+12）=8.60W=1/5（1+1.17+2.25+2.40+6.00）=2.56

特點:吞吐量不定、耗費最小、無饑餓、對偏重于I/O進程不利，響應時間很高，尤其是進程執行時間變化很大時3.3.2短作業(進程)優先調度算法

短作業(進程)優先調度算法SJ(P)F，是指對短作業或短進程優先調度的算法。它們可以分別用于作業調度和進程調度。短作業優先(SJF)的調度算法，是從后備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。而短進程優先(SPF)調度算法，則是從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它，使它立即執行并一直執行到完成，或發生某事件而被阻塞放棄處理機時，再重新調度。作業1作業2作業5作業3作業4039111520T=1/5（3+7+11+14+3）=7.60W=1/5（1+1.17+2.75+2.80+1.50）=1.84SJ(P)F調度算法也存在不容忽視的缺點：(1)該算法對長作業不利，更嚴重的是，如果有一長作業(進程)進入系統的后備隊列(就緒隊列)，由于調度程序總是優先調度那些(即使是后進來的)短作業(進程)，將導致長作業(進程)長期不被調度。(2)該算法完全未考慮作業的緊迫程度，因而不能保證緊迫性作業(進程)會被及時處理。(3)由于作業(進程)的長短只是根據用戶所提供的估計執行時間而定的，而用戶又可能會有意或無意地縮短其作業的估計運行時間，致使該算法不一定能真正做到短作業優先調度。特點：吞吐量高、能提供較好的響應時間，對長進程不利、可能產生饑餓3.3.3高優先權優先調度算法選擇優先級高的進程和作業作為調度對象。按搶占與否優先數可分：非搶占的優先調度算法可搶占的優先調度算法按靜態，動態優先數可分：靜態優先數動態優先數

1）非搶占式優先權算法在這種方式下，系統一旦把處理機分配給就緒隊列中優先權最高的進程后，該進程便一直執行下去，直至完成；或因發生某事件使該進程放棄處理機時，系統方可再將處理機重新分配給另一優先權最高的進程。這種調度算法主要用于批處理系統中；也可用于某些對實時性要求不嚴的實時系統中。2)搶占式優先權調度算法在這種方式下，系統同樣是把處理機分配給優先權最高的進程，使之執行。但在其執行期間，只要又出現了另一個其優先權更高的進程，進程調度程序就立即停止當前進程(原優先權最高的進程)的執行，重新將處理機分配給新到的優先權最高的進程。因此，在采用這種調度算法時，是每當系統中出現一個新的就緒進程i時，就將其優先權Pi與正在執行的進程j的優先權Pj進行比較。如果Pi≤Pj，原進程Pj便繼續執行；但如果是Pi＞Pj,則立即停止Pj的執行，做進程切換，使i進程投入執行。顯然，這種搶占式的優先權調度算法，能更好地滿足緊迫作業的要求，故而常用于要求比較嚴格的實時系統中，以及對性能要求較高的批處理和分時系統中。

3)靜態優先權靜態優先權是在創建進程時確定的，且在進程的整個運行期間保持不變。一般地，優先權是利用某一范圍內的一個整數來表示的，例如，0~7或0~255中的某一整數，又把該整數稱為優先數。只是具體用法各異：有的系統用“0”表示最高優先權，當數值愈大時，其優先權愈低；而有的系統恰恰相反。確定進程優先權的依據有如下三個方面：進程類型。(2)進程對資源的需求。(3)用戶要求。4)動態優先權動態優先權是指，在創建進程時所賦予的優先權，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調度性能。例如，我們可以規定，在就緒隊列中的進程，隨其等待時間的增長，其優先權以速率a提高。若所有的進程都具有相同的優先權初值，則顯然是最先進入就緒隊列的進程，將因其動態優先權變得最高而優先獲得處理機，此即FCFS算法。若所有的就緒進程具有各不相同的優先權初值，那么，對于優先權初值低的進程，在等待了足夠的時間后，其優先權便可能升為最高，從而可以獲得處理機。當采用搶占式優先權調度算法時，如果再規定當前進程的優先權以速率b下降，則可防止一個長作業長期地壟斷處理機。非搶占的優先調度作業1作業2作業4作業3作業5039141820T=1/5（3+7+14+8+12）=8.8W=1/5（1+1.17+3.5+1.6+6）=2.853.3.4高響應比優先調度算法

優先權的變化規律可描述為：由于等待時間與服務時間之和，就是系統對該作業的響應時間，故該優先權又相當于響應比RP。據此，又可表示為：(1)如果作業的等待時間相同，則要求服務的時間愈短，其優先權愈高，因而該算法有利于短作業。(2)當要求服務的時間相同時，作業的優先權決定于其等待時間，等待時間愈長，其優先權愈高，因而它實現的是先來先服務。(3)對于長作業，作業的優先級可以隨等待時間的增加而提高，當其等待時間足夠長時，其優先級便可升到很高，從而也可獲得處理機。作業1作業2作業3作業5作業4039131520T=1/5（3+7+9+14+7）=8.00W=1/5（1.00+1.17+2.25+2.80+3.5）=2.14最高響應比是一種非搶占算法3.3.5時間片輪轉調度算法把CPU的時間分割成時間片，處于就緒狀態的進程輪流獲得時間片。時間片輪轉調度算法是搶占算法。其調度算法的性能取決于時間片Q。Q=4（時間片為4）作業1作業2作業3作業4作業2作業5作業40371115171920T=1/5（3+15+7+14+11）=10.00W=1/5（1.00+2.50+1.75+2.80+5.50）=2.71Q=1（時間片為1）12123243254325

4324402345678910111213141516171819T=1/5（4+16+13+14+7）=10.8W=1/5（1.33+2.67+3.25+2.80+3.50）=2.71RR算法主要用于分時系統或事務處理系統，可保證對各終端用戶的及時響應。但它對偏重CPU的進程和偏重I/O的進程有不同的處理結果，可以采用虛擬時間片輪轉(VRR)策略來避免這個問題。新加入的特性是附加一個FCFS策略隊列來收集從I/O等待中釋放的進程。特點：吞吐量在時間片小的時候可能很低，對所有進程公平對待、特別是短進程提供好的響應時間，無饑餓3.3.6最短剩余時間優先調度算法最短剩余時間：從作業當前運行到完成所需時間。最短剩余時間優先調度是搶占算法。用于分時系統其輪轉時間最優作業1作業2作業3作業5作業2作業40348101520T=1/5（3+13+4+14+2）=7.20W=1/5（1.00+2.17+1.00+2.80+1.00）=1.59

特點：吞吐量高、能提供較好的響應時間，對長進程不利、可能產生饑餓3.3.7均衡法作業分類A——I/O量多B——比較適中C——占用CPU時間A、C按一定比列搭配。B類不受限制。3.3.8多級反饋隊列調度算法系統中有多個就緒隊列各級就緒隊列具有不同的時間片各級隊列均按FIFO原則排隊調度方法：首先調度優先級高的進程，當優先級高的進程為空，才調度下一級。Q=1（每級反饋隊列每一級時間片為1）1121324354523423424201234567891011121314151617181920T=1/5（4+18+12+13+3）=10.00W=1/5（1.33+3.00+3.00+2.60+1.50）=2.29Q=2**N（每級反饋隊列每一級時間片以2冪次方遞增）11213224533445222344T=1/5（4+15+14+14+6）=10.06W=1/5（1.33+2.50+3.50+2.80+3.00）=2.6301234567891011121314151617181920

特點：吞吐量不定，消耗可能高、有利于偏重I/O進程，可能會饑餓多級反饋隊列調度算法的性能

終端型作業用戶。(2)短批處理作業用戶。(3)長批處理作業用戶。3.4實時調度3.4.1實現實時調度的基本條件1.提供必要的信息就緒時間。(2)開始截止時間和完成截止時間。(3)處理時間。(4)資源要求。(5)優先級。2.系統處理能力強

3.采用搶占式調度機制4.具有快速切換機制(1)對外部中斷的快速響應能力。(2)快速的任務分派能力。3.4.2實時調度算法的分類1.非搶占式調度算法非搶占式輪轉調度算法。(2)非搶占式優先調度算法。

非搶占時間片輪轉調度

非搶占式優先權調度

2.搶占式調度算法基于時鐘中斷的搶占式優先權調度算法。(2)立即搶占(ImmediatePreemption)的優先權調度算法?；跁r鐘搶占的優先權搶占調度

立即搶占優先權調度3.4.3常用的幾種實時調度算法最早截止時間優先即EDF(EarliestDeadlineFirst)算法

根據任務的開始截止時間或完成截止時間來確定任務的優先級，截止時間越早，其優先級越高最早截止時間優先調度算法有搶占式和非搶占式1）非搶占式調度用于非周期性實時任務2）搶占式調度方式用于周期實時任務假如在一個實時系統中，有兩個周期性實時任務A和B，任務A要求每20ms執行一次，執行時間為10ms；任務B只要求每50ms執行一次，執行時間為25ms。進程到達時間執行時間完成期限進程到達時間執行時間完成期限A101020B102550A2201040B25025100A3401060A4601080A58010100

B1A1A2A30102030405060708090100B2A4A5A1期限A2期限A3期限A4期限A5期限B1期限B2期限B1期限B2期限0102030405060708090100A1B1A2B1A3B2A1期限A2期限A3期限A4期限A5期限B1誤期A4B2A5B固定優先級（A優先級高，且可搶占）B1期限B2期限0102030405060708090100B1A2A3B2A5固定優先級（B優先級高）A1期限A2期限A3期限A4期限A5期限A1誤期A4誤期B1期限B2期限0102030405060708090100A1B1A2B1A3BA4B2A5A1期限A2期限A3期限A4期限A5期限使用完成期限最早期限調度都能完成2.最低松弛度優先即LLF(LeastLaxityFirst)算法該算法是根據任務緊急(或松弛)的程度，來確定任務的優先級。任務的緊急程度愈高，為該任務所賦予的優先級就愈高，以使之優先執行。在實現該算法時要求系統中有一個按松弛度排序的實時任務就緒隊列，松弛度最低的任務排在隊列最前面，調度程序總是選擇就緒隊列中的隊首任務執行。該算法主要用于可搶占調度方式A和B任務每次必須完成的時間A每隔20MS執行一次，執行時間為10MSB每隔50MS執行一次，執行時間為25MS

松弛度=必須完成時間-其本身的運行時間-當前時間

利用ELLF算法進行調度的情況t1A1(10)10203040506080t0t1=0B1(15)t2t370A2(10)A3(5)A4(10)t4t5t6t7t8B1(5)B2(20)B2(10)3.5產生死鎖的原因和必要條件3.5.1死鎖問題的提出1.死鎖的定義死鎖是指計算機系統和進程所處的一種狀態。常定義為：在系統中的一組進程，由于競爭系統資源或由于彼此通信而永遠阻塞，我們稱這些進程處于死鎖狀態。例1銀行借款假定某行有一筆法郎可供一批顧客借用，并假定：每個顧客預知他的最大借款總額，且不超過銀行擁有可用資金總和。每次借款以一法郎為單位。每當顧客提出借款請求，銀行可立即給予，或讓顧客等一段時間。只有當顧客達到他的預定最大借款額時，他才在有限時間一次歸還。死鎖的產生：當各顧客借款總額之和大于銀行可借用資金總和，而每顧客都未達到他的預定最大借款額。安全狀態：如果在某時刻，銀行有可能使它當時的所有的顧客在以后有限時間內完成全部成交，則此刻的狀態是安全。不安全狀態：永遠不具有成交的可能，則為不安全。

C2P4（4）Q2（1）R2（7）C4P4（4）R2（7）C8R2（7）C10安全狀態C1P4（4）Q2（1）R3（6）C3P4（4）R3（6）

不安全狀態C：借款總額，P，Q，R：顧客例2相同類型資源假設內存有M個頁面，N個進程，這里M，N滿足2MN，如果分配和回收以頁為單位，且每個進程以如下方式申請和釋放資源。

申請一頁申請一頁釋放一頁釋放一頁死鎖的產生：各進程的執行次序輪轉R1R2R3P1P2P3P4M=3，N=4框：資源圈：進程圈框：分配邊框圈：請求邊例3：不同類型資源假定系統有N種外部設備R1，R2???RN，系統又有N個進程P1，P2???PN，它們以這種方式要求資源。P1：申請R1申請R2釋放R1釋放R2P2：申請R2申請R3釋放R2釋放R3PN：申請RN申請R1釋放RN釋放R1???

死鎖的產生：各進程的執行次序輪轉P3R1

R2P2P1R32.產生死鎖的原因

(1)競爭資源。(2)進程間推進順序非法。(1)競爭資源引起進程死鎖

資源：可以引起一個進程進入等待狀態的事物可搶占資源、不可搶占資源共享資源、獨享資源可重用資源(永久)、消耗性資源(臨時)（2）進程推進順序不當引起死鎖進程推進順序合法圖3-14進程推進順序對死鎖的影響進程推進順序非法若并發進程P1和P2按曲線④所示的順序推進，它們將進入不安全區D內。此時P1保持了資源R1,P2保持了資源R2,系統處于不安全狀態。因為，這時兩進程再向前推進，便可能發生死鎖。例如，當P1運行到P1:Request(R2)時，將因R2已被P2占用而阻塞；當P2運行到P2:Request(R1)時，也將因R1已被P1占用而阻塞，于是發生了進程死鎖。3.產生死鎖的必要條件互斥條件(2)請求和保持條件(3)不剝奪條件(4)環路等待條件3.5.2處理死鎖的基本方法預防死鎖。(2)避免死鎖。(3)檢測死鎖。(4)解除死鎖。

3.6預防死鎖

通過設置某些限制條件，以破壞產生死鎖的必要條件一個或幾個，來防止死鎖。預防死鎖是一種較可取的方法，但資源的利用率較低。3.6.1摒棄“互斥條件”條件互斥是正確使用非共享資源的唯一手段。故不能通過取消互斥來預防死鎖。3.6.2摒棄“請求和保持”條件

采用資源靜態分配：每個進程執行前，一次分配其所有資源允許進程僅當自己未占有資源時才申請資源。例1：如果有這樣進程，它從讀卡機中拷貝磁盤文件，排序磁盤文件，然后將結果打印在打印機上，并將起拷貝到磁帶。按第一種制約：在進程運行前。為其分配所有資源，讀卡機，磁盤文件，打印機，磁帶機按第二種制約：先申請讀卡機，磁盤文件釋放兩者申請磁盤文件，打印機釋放兩者申請磁盤文件，磁帶機釋放兩者。3.6.3摒棄“不剝奪”條件適用于狀態容易保護，稍后又容易恢復的資源。如CPU，內存。3.6.4摒棄“環路等待”條件為使“循環等待”條件不滿足，我們把所有資源按類型進行排隊，并賦予不同的編號。

每個進程

釋放按序號遞減次序進行申請按序號遞增次序進行

優點：資源的申請與分配逐步進行，比預分配策略的資源利用率高；缺點：嚴格限制資源的順序性，不允許增加資源請求在使用資源的順序與系統規定不一致時，資源利用率降低；不能搶占。

3.7死鎖的避免和銀行家算法

3.7.1安全狀態在避免死鎖的方法中，允許進程動態地申請資源，但系統在進行資源分配之前，應先計算此次資源分配的安全性。若此次分配不會導致系統進入不安全狀態，則將資源分配給進程；否則，令進程等待。所謂安全狀態，是指系統能按某種進程順序(P1,P2,…，Pn)(稱〈P1,P2,…,Pn〉序列為安全序列)，來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。如果系統無法找到這樣一個安全序列，則稱系統處于不安全狀態。3.7.2利用銀行家算法避免死鎖1.銀行家算法中的數據結構

Resource:一個長度為m向量,表示系統擁有的資源數目Available：一個長度為m向量，表示每類資源的可用數目如果Available[j]=k，表明Rj類資源有k個。Max：一個m×n矩陣，定義每個進程的最大資源需求數如果Max[i,j]=k,表示進程i需要Rj類資源有k個。Allocation：一個m×n矩陣，定義當前分配給每個進程每類資源的數目。如果Allocation[i,j]=k，則表示進程i獲得Rj類資源有k個。Need：一個m×n矩陣，表示每個進程還需多少資源。如果

Need[i,j]=k，表示進程i還需要Rj類資源有k個。2.銀行家算法設：Requesti是進程Pi的請求向量當Pi發出資源請求后，系統按如下步驟進行檢查：如果Requesti

Needi則goto2,否則認為出錯。如果Requesti

Available則goto3，否則表示無足夠資源，Pi等待。系統進行試探分配，并求該相應數據結構數據

Available：=Available-RequestiAllocationi：=Allocationi+RequestiNeedi：=Needi-Requesti系統執行安全性算法：安全，把資源分配給Pi，否則，Pi等待。3.安全性算法設Work和Finish是長度分別為m,n的向量初試值Work：=Available，Finishi：=False（所有）從進程集合中找到一個能滿足下列條件的進程

a.Finishi=Falseb.Needi

Work如找到goto3否則goto4

當進程Pi

獲得資源后，順利執行，直至完成，并釋放分配給它的資源。Work：=Work+AllocationiFinishi：=Truegoto2如果所有進程的Finishi=True則表示系統安全，否則為不安全。4.銀行家算法之例假定系統中有五個進程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝，各種資源的數量分別為10、5、7，在T0時刻的資源分配情況如圖3-15所示。圖3-15T0時刻的資源分配表(1)T0時刻的安全性：圖3-16T0時刻的安全序列(2)P1請求資源：P1發出請求向量Request1(1，0，2)，系統按銀行家算法進行檢查：①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available1(3,3,2)③系統先假定可為P1分配資源，并修改Available,Allocation1和Need1向量，由此形成的資源變化情況如圖3-15中的圓括號所示。④再利用安全性算法檢查此時系統是否安全。圖3-17P1申請資源時的安全性檢查(3)P4請求資源：P4發出請求向量Request4(3，3，0)，系統按銀行家算法進行檢查：①Request4(3,3,0)≤Need4(4,3,1);②Request4(3,3,0)Available(2,3,0)，讓P4等待。(4)P0請求資源：P0發出請求向量Requst0(0，2，0)，系統按銀行家算法進行檢查：①Request0(0,2,0)≤Need0(7,4,3);②Request0(0,2,0)≤Available(2,3,0);③系統暫時先假定可為P0分配資源，并修改有關數據，如圖3-18所示。圖3-18為P0分配資源后的有關資源數據3.8死鎖的檢測與解除3.8.1死鎖的檢測1.資源分配圖(ResourceAllocationGraph)圖3-19每類資源有多個時的情況