1、調度與死鎖內容提要調度的類型及其功能調度的性能評價常用的調度算法死鎖調度的含義調度就是選出待分派的作業或進程處理機調度的主要目的是為了分配處理機調度的類型高級調度：作業調度中級調度：存儲對換低級調度：進程調度進程的調度方式非搶占方式搶占方式進程調度的時機現行進程完成或錯誤終止現行進程提出I/O請求，等待I/O完成時在進程通信中，執行中的進程執行了某種原語操作，如P操作、阻塞原語時，都可能引起進程調度在分時系統，按照時間片輪轉，分給進程的時間片用完時優先級調度時，有更高優先級進程變為就緒時進程調度的主要功能保存讓權進程的現場擇優選出一個就緒進程為選中進程恢復現場，令其投入運行作業調度和進程調度的

2、區別作業調度是宏觀調度，進程調度是微觀調度作業調度為進程的活動做準備，進程調度使進程真正活動起來作業調度執行次數較少，進程調度活動頻繁作業調度可以不設，進程調度必不可少僅有進程調度的調度隊列模型就 緒 隊 列阻 塞 隊 列CPU事件出現交互用戶時間片完進程調度等待事件進程完成常用的調度性能評價標準CPU的利用率系統吞吐量周轉時間響應時間就緒隊列等待時間周轉時間周轉時間是指從作業提交給系統開始，到作業完成為止的時間通常把周轉時間作為評價批處理系統性能、選擇作業調度方式與算法的準則平均周轉時間與平均帶權周轉時間平均周轉時間可描述為：通常把周轉時間作為評價批處理系統性能、選擇作業調度方式與算法的準則

3、常用調度算法 對于不同的系統和系統目標，通常采用不同的調度算法。目前存在很多調度算法，有的適用于作業調度，有的適用于進程調度，有的兩者都適用。先來先服務調度算法 先來先服務（FCFS）算法的思想很簡單：每次調度是從作業后備隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源，創建進程，然后放入就緒隊列。FCFS算法示意圖作業T作業1作業2作業3012242730表示作業到達時間表示作業執行過程FCFS算法性能分析作業 到達時間 運行時間 開始時間 完成時間 周轉時間 帶權周轉時間平均周轉時間 T=26 平均帶權周轉時間 W=6.331 0 24 0 24 24 12 1 3

4、 24 27 26 8.673 2 3 27 30 28 9.33FCFS的特征較利于長作業或進程有利于占用CPU時間多的作業容易實現，但效率較低短作業（進程）優先調度算法短作業(SJF)調度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行短進程(SPF)調度算法是從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它，使它立即執行SJ(P)F調度算法的缺點對長作業非常不利完全未考慮作業的緊迫程度由于作業（進程）的長短，只是根據用戶估計的時間而定，致使算法不一定能真正做到短作業優先調度時間片輪轉調度算法 系統使每個進程依次按時間片輪流執行。在通常的輪轉法中，系統

5、將所有就緒進程按先來先服務原則，排成一個隊列。每次調度時，把CPU分配給隊首進程，并對其執行一個時間片。時間片的大小從幾ms到幾百ms。 時間片用完時，停止該進程的執行，并將其送入就緒隊列的末尾。影響時間片長短的因素系統的響應時間就緒隊列進程的數目進程的轉換時間CPU運行指令速度優先權調度算法 為照顧到緊迫型作業進入到系統后就能獲得優先處理，引入最高優先權調度算法。當該算法用于作業調度時，系統將從后備隊列中選擇若干優先權最高的作業調入內存；當算法用于進程調度時，把處理機分配給就緒隊列中優先權最高的進程。算法分類非搶占式優先權算法搶占式優先權算法優先權的類型靜態優先權。確定依據為：進程類型、進程

6、對資源的需求、用戶要求動態優先權多級隊列調度 多級隊列調度是根據作業的性質或類型不同，將就緒隊列分成若干個子隊列，每個作業固定屬于某個隊列。每個隊列采用一種算法，不同隊列可采用不同的調度算法。多級反饋隊列調度算法 多級反饋隊列調度算法不必事先了解各進程所需的執行時間，而且還可滿足各種類型進程的需要，是目前公認的比較好的進程調度算法。多級反饋隊列中就緒隊列種類剛剛被創建的進程等待進程調度已經被調度執行過，但還沒有執行完，等待下一次調度正在執行的進程還未用完時間片，因請求I/O，等待I/O完成被迫放棄CPU，當等待原因解除后，進入就緒隊列等待運行多級反饋隊列調度的實施過程系統設置多個就緒隊列，進程

7、在其生命期內可能在多個隊列中存在各個隊列賦予不同的優先級。第一個隊列的優先級最高，其余各隊列的優先權逐個降低各個隊列中進程執行的時間片大小也各不相同，在優先權越高的隊列中，每個進程的執行時間片就越小多級反饋隊列調度的實施過程新進程進入內存后，排在最高優先級隊列的末尾，按FCFS原則等待調度。該進程執行時，如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入下一個較低優先級隊列的隊尾當一個長進程從第一隊列依次降到第n隊列后，在第n隊列中便采取按時間片輪轉的方式運行多級反饋隊列調度的實施過程調度時，總是先調度優先級高的隊列。僅當該隊列空時，才調度次高優先級隊列，以此類推，第n個隊列進程被調度時

8、，必須是前n-1個隊列為空如果處理機正在第i個隊列中為某進程服務時，又有新進程進入優先權較高的隊列，則此時新進程將搶占正在運行進程的處理機，由調度程序把正在運行的進程放回到第i個隊列的末尾，把處理機分配給新到的進程多級反饋隊列調度算法示意圖就緒隊列1就緒隊列2就緒隊列3就緒隊列4至CPU至CPU至CPU至CPUS1S2S3死鎖 在多道程序系統中，雖可通過進程的并發執行改善系統的資源利用率和提高處理能力，但也可能引發一種危險死鎖。 死鎖(dead lock)，是指多個進程因競爭資源而造成的一種僵局。若無外力作用，這些進程將永遠不能向前推進。產生死鎖的原因競爭資源進程推進順序非法資源分配圖 代表進

9、程 代表資源 代表進程請求資源 代表資源已分配給進程資源分配死鎖舉例P1P2R1R2進程推進不當引發死鎖舉例例如：兩個進程P1，P2 共享兩個系統資源R1和R2合法順序為：P1: Request(R1); P1: Request(R2);P1: Release(R1); P1: Release(R2);P2: Request(R2); P2: Request(R1);P2: Release(R2); P2: Release(R1);非法順序為：P1: Request(R1); P2: Request(R2);P1: Request(R2); P2: Request(R1);產生死鎖的原因互斥條

10、件請求和保持條件不剝奪條件環路等待條件處理死鎖的基本方法預防死鎖避免死鎖檢測死鎖解除死鎖預防死鎖的方法 因產生死鎖須四個必要條件。若能破壞其中的一個或幾個條件，則死鎖不發生。摒棄請求和保持條件系統要求所有進程一次性地申請整個運行過程中所需的全部資源。只要有一種資源要求不能滿足，也讓該進程等待該方法的優點是簡單，容易實現，而且安全缺點是資源浪費嚴重，進程執行被延遲摒棄不剝奪條件系統要求一個已經保持了某些資源的進程，當它提出新的資源要求而不被滿足時，必須釋放它已經保持的所有資源，待以后再重新申請這種方法實現起來比較復雜，且要付出很大代價摒棄環路等待條件系統將所有資源按類型排成線性隊列，并賦予不同的

11、序號。所有進程申請資源時必須嚴格按資源序號遞增的順序提出。這種解決方法使資源利用率和系統吞吐量有明顯改善。但對資源給予固定序號，將限制系統資源的擴充和程序編寫的自由。避免死鎖的方法 該方法把系統的狀態分為安全狀態和不安全狀態。只要能使系統處于安全狀態，就可以避免死鎖的發生。安全狀態所謂安全狀態，系統能按某種順序如(P1, P2, , Pn)，稱為安全序列，來為每個進程分配其所需資源，直至最大需求，使每個進程都可順利完成若系統不存在這樣一個安全序列，則稱系統處于不安全狀態避免死鎖的實質在于：如何使系統不進入不安全狀態銀行家算法 最有代表性的避免死鎖的算法，是Dijkstra提出的銀行家算法。該算

12、法因用于銀行系統現金貸款的發放而得名。系統中必須設置若干數據結構。銀行家算法中的數據結構可利用資源向量Available最大需求數組Max分配矩陣Allocation需求矩陣Need上述三個矩陣間存在下述關系： Needi,j=Maxi,j Allocationi,j銀行家算法的步驟設Requesti是進程Pi的請求向量。(1)如果RequestiNeedi，則轉向步驟(2)；否則報錯(2)若RequestiAvailable，轉向步驟(3)；否則Pi等待(3)系統試探把資源分配給進程Pi，并修改下面的數值： Availablei=Availablei-Requesti Allocationi

13、=Allocationi+Requesti Needi=Needi-Requesti(4)執行安全性算法安全性算法的步驟(1)設置兩個向量：工作向量Work和完成向量Finish(2)從進程集合中找到一個滿足以下條件的進程Pi： 1. Finishi=False 2.NeediWorki 若能找到，執行步驟(3)；否則執行步驟(4) 安全性算法的步驟(3)當進程Pi順利完成，并釋放資源，可執行： Worki=Worki+Allocationi Finishi=true go to step (2)(4)若所有的Finishi=true，則表示系統處于安全狀態；否則就是不安全狀態銀行家算法舉例

14、假定系統中有五個進程P0， P1， P2， P3， P4和三類資源A，B，C，各類資源的數目分別是10、5、7。T0時刻的資源分配MaxA B CAllocationA B CNeedA B CAvailableA B CP0 P1 P2 P3 P4 7 5 33 2 29 0 22 2 24 3 30 1 02 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 2銀行家算法舉例利用安全性算法，T0時刻存在一個安全序列P1，P3，P4，P2，P0，故系統是安全的。P1請求資源，請求向量為Request1，0，2，則資源分配如下圖資源分配MaxA B

15、CAllocationA B CNeedA B CAvailableA B CP0 P1 P2 P3 P47 5 33 2 29 0 22 2 24 3 30 1 03 0 23 0 22 1 10 0 27 4 30 2 06 0 00 1 14 3 12 3 0銀行家算法舉例P4請求資源，請求向量為Request3，3，0，系統按銀行家算法進行檢查，可用資源不能滿足請求資源， P4等待。P0請求資源，請求向量為Request0，2，0 ，則資源分配如下圖資源分配MaxA B CAllocationA B CNeedA B CAvailableA B CP0 P1 P2 P3 P47 5 33 2 29 0 22 2 24 3 30 3 03 0 23 0 22 1 10 0 27 2 30 2 06 0 00 1 14 3 12 1 0銀行家算法舉例P4請求系統按銀行家算法進行檢查， P0分