湘潭大學操作系統(tǒng)第4章課件ppt

1、1計算機操作系統(tǒng)計算機操作系統(tǒng)第第4章章 處理機調(diào)度處理機調(diào)度2目目 錄錄l4.1 調(diào)度簡介調(diào)度簡介l4.2 調(diào)度算法調(diào)度算法l4.3 死鎖簡介死鎖簡介l4.4 死鎖檢測和恢復死鎖檢測和恢復l4.5 死鎖避免死鎖避免34.1 調(diào)度簡介調(diào)度簡介l 計算機系統(tǒng)中，處理器和內(nèi)存資源會出現(xiàn)供計算機系統(tǒng)中，處理器和內(nèi)存資源會出現(xiàn)供不應(yīng)求的情況，特別是多個不應(yīng)求的情況，特別是多個I/O設(shè)備與主機交設(shè)備與主機交互，作業(yè)不斷進入系統(tǒng)，或者是多個批處理作互，作業(yè)不斷進入系統(tǒng)，或者是多個批處理作業(yè)在磁盤的后備隊列中等待進入內(nèi)存的情況。業(yè)在磁盤的后備隊列中等待進入內(nèi)存的情況。操作系統(tǒng)在管理有限的資源的同時，需要考慮

2、操作系統(tǒng)在管理有限的資源的同時，需要考慮如何選取進入內(nèi)存的作業(yè)如何選取進入內(nèi)存的作業(yè)，如何分配有限的處如何分配有限的處理器資源給多個進程理器資源給多個進程等重要問題。處理器的調(diào)等重要問題。處理器的調(diào)度正是處理器和內(nèi)存資源調(diào)度和分配相關(guān)的工度正是處理器和內(nèi)存資源調(diào)度和分配相關(guān)的工作。作。44.1 調(diào)度簡介調(diào)度簡介l高級調(diào)度高級調(diào)度l高級調(diào)度又稱為作業(yè)調(diào)度作業(yè)調(diào)度、長調(diào)度長調(diào)度。調(diào)度對象是作調(diào)度對象是作業(yè)業(yè)。作業(yè)是一個比程序更為廣泛的概念，不僅包含通常的程序和數(shù)據(jù)，還配有一份作業(yè)說明書，系統(tǒng)根據(jù)該說明書來對程序的運行進行控制。在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。從輸入系統(tǒng)的一批作業(yè)

3、中按照預定調(diào)度策略選擇進入主存的作業(yè)，為其分配資源，創(chuàng)建進程，以上就是高級調(diào)度。作為啟動階段的調(diào)度，為進程的運行做好準備工作，等待進程調(diào)度選擇進程進行運行。54.1 調(diào)度簡介調(diào)度簡介l高級調(diào)度高級調(diào)度l高級調(diào)度能夠控制多道程序中被選進主存的作業(yè)數(shù)量，數(shù)量越多，每個作業(yè)獲得的CPU時間越少。對用戶而言，總希望自己作業(yè)的周轉(zhuǎn)時間盡可能的少，最好周轉(zhuǎn)時間就等于作業(yè)的執(zhí)行時間。然而對系統(tǒng)來說，則希望作業(yè)的平均周轉(zhuǎn)時間盡可能少，有利于提高CPU 的利用率和系統(tǒng)的吞吐量。為此，每個系統(tǒng)在選擇作業(yè)調(diào)度算法時，既應(yīng)考慮用戶的要求，又能確保系統(tǒng)具有較高的效率。64.1 調(diào)度簡介調(diào)度簡介l低級調(diào)度低級調(diào)度l低級調(diào)

4、度又稱為進程調(diào)度進程調(diào)度、短調(diào)度短調(diào)度。調(diào)度對象是進調(diào)度對象是進程程。根據(jù)主存資源，決定就緒隊列中的有多少個并且哪些進程應(yīng)獲得處理機，然后再由分派程序執(zhí)行把處理機分配給該進程的具體操作。包括對處理機現(xiàn)場信息的保存，如程序計數(shù)器、多個通用寄存器中的內(nèi)容等，將它們送入該進程的進程控制塊(PCB)中的相應(yīng)單元。然后按某種算法選取進程，把就緒隊列中被選中的進程的狀態(tài)改為運行狀態(tài)，并準備把處理機分配給它。74.1 調(diào)度簡介調(diào)度簡介l中級調(diào)度中級調(diào)度l中級調(diào)度介于高級調(diào)度和低級調(diào)度之間。該調(diào)度根據(jù)進程狀態(tài)決定輔存和主存之間的進程對換。主存資源緊缺時，將暫時不能運行的進程換出，進程轉(zhuǎn)為掛起狀態(tài)；主存資源空閑

5、，并且進程滿足運行條件時，再將進程調(diào)回主存。對主存的利用和系統(tǒng)吞吐率都有很大的提升。84.1 調(diào)度簡介調(diào)度簡介l在上述三種調(diào)度中，進程調(diào)度是操作系統(tǒng)最核心的部分，運行頻率最高，因此把它稱為短程調(diào)度。為避免進程調(diào)度占用太多的CPU時間，進程調(diào)度算法不宜太復雜。作業(yè)調(diào)度往往是發(fā)生在一個(批)作業(yè)運行完畢，退出系統(tǒng)，而需要重新調(diào)入一個(批)作業(yè)進入內(nèi)存時，故作業(yè)調(diào)度的周期較長，大約幾分鐘一次，因此把它稱為長程調(diào)度。在純粹的分時或?qū)崟r操作系統(tǒng)中通常不需要作業(yè)調(diào)度。中級調(diào)度的運行頻率基本上介于上述兩種調(diào)度之間。一些功能完善的操作系統(tǒng)為了提高主存利用率和作業(yè)吞吐率，會引入中級調(diào)度。94.1 調(diào)度簡介調(diào)度簡

6、介圖圖4.1 三種調(diào)度的層次關(guān)系三種調(diào)度的層次關(guān)系104.1 調(diào)度簡介調(diào)度簡介就緒隊列低級調(diào)度處理機掛起就緒隊列中級調(diào)度掛起阻塞隊列等待隊列等待事件完成時間片內(nèi)未完成高級調(diào)度交互型作業(yè)后備隊列掛起事件發(fā)生事件發(fā)生圖圖4.2 三種調(diào)度的隊列圖三種調(diào)度的隊列圖114.1 調(diào)度簡介調(diào)度簡介l如圖4.2所示，被高級調(diào)度選中的作業(yè)，從后備隊列中，通過多個作業(yè)步：編譯、鏈接、裝入、運行，稱為目標進程，進入主存的就緒隊列等候。就緒隊列中的進程以此被分配相同的時間片獲得處理器。如果進程在給定的時間片內(nèi)順利完成，便在釋放處理機進入完成狀態(tài)；l如果進程在本次分配的時間片內(nèi)尚未完成，該進程會到就緒隊列的末尾等待下一

7、個時間片；l如果在執(zhí)行期間進程因為某事件而被阻塞，則進入等待隊列，進入掛起狀態(tài)，進入掛起阻塞隊列，直到等待的事件發(fā)生，再進入掛起就緒隊列，等待中級調(diào)度將其調(diào)回主存就緒隊列。124.1 調(diào)度簡介調(diào)度簡介l作業(yè)的相關(guān)介紹作業(yè)的相關(guān)介紹n在作業(yè)運行期間，每個作業(yè)都必須經(jīng)過若干個相對獨立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果，其中的每一個加工步驟就是一個作業(yè)步每一個加工步驟就是一個作業(yè)步，上一個作業(yè)步的輸出一般是下一個作業(yè)步的輸入。n例如，一個典型的作業(yè)可分成四個作業(yè)步： “編譯”，通過執(zhí)行編譯程序?qū)υ闯绦蜻M行編譯，產(chǎn)生若干個目標程序段； “鏈接”，將“編譯”作業(yè)步所產(chǎn)生的若干個目標程序段通過庫函數(shù)鏈

8、接在一起； “裝配”，將鏈接好的部分裝配成可執(zhí)行的目標程序；“運行”，將可執(zhí)行的目標程序讀入內(nèi)存并控制其運行。n若干個作業(yè)進入系統(tǒng)后，被依次存放在外存上，形成了輸入的作業(yè)流作業(yè)流；在操作系統(tǒng)的控制下，逐個作業(yè)進行處理，于是便形成了處理作業(yè)流處理作業(yè)流。 134.1 調(diào)度簡介調(diào)度簡介l作業(yè)的管理和調(diào)度作業(yè)的管理和調(diào)度n每個作業(yè)設(shè)置了一個作業(yè)控制塊保存了系統(tǒng)對作業(yè)進行管理和調(diào)度所需的全部信息，是作業(yè)在系統(tǒng)中存在的標志n在作業(yè)控制塊中通常應(yīng)包含的內(nèi)容有：作業(yè)標識、用戶名稱、用戶帳戶、作業(yè)類型、作業(yè)狀態(tài)、優(yōu)先級、作業(yè)已運行時間、 (預計運行時間、要求內(nèi)存大小、要求I/O設(shè)備的類型和數(shù)量等、進入系統(tǒng)時間

9、、開始處理時間、作業(yè)完成時間、作業(yè)退出時間、資源使用情況等。144.1 調(diào)度簡介調(diào)度簡介l作業(yè)管理l建立作業(yè)控制塊建立作業(yè)控制塊：系統(tǒng)便為每個進入系統(tǒng)的作業(yè)建立一個作業(yè)控制塊，根據(jù)作業(yè)類型將它插入相應(yīng)的后備隊列中l(wèi)調(diào)度調(diào)度：作業(yè)調(diào)度程序依據(jù)一定的調(diào)度算法來調(diào)度它們，將它們裝入內(nèi)存l控制控制：在作業(yè)運行期間，系統(tǒng)就按照作業(yè)控制塊中的信息對作業(yè)進行控制l回收資源回收資源：當一個作業(yè)執(zhí)行結(jié)束進入完成狀態(tài)時，系統(tǒng)負責回收分配給它的資源，撤消它的作業(yè)控制塊154.1 調(diào)度簡介調(diào)度簡介l作業(yè)調(diào)度l審查審查：根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求l將作業(yè)調(diào)入內(nèi)存將作業(yè)調(diào)入內(nèi)存：按照一定的

10、算法，從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存l為它們創(chuàng)建進程創(chuàng)建進程l分配分配必要的資源資源l插入就緒隊列插入就緒隊列：將新創(chuàng)建的進程插入就緒隊列，準備執(zhí)行164.1 調(diào)度簡介調(diào)度簡介l考慮的問題：考慮的問題：作業(yè)調(diào)度要考慮每次允許多少個作業(yè)同時在內(nèi)存中運行？當內(nèi)存中同時運行的作業(yè)數(shù)目太多時，可能會影響到系統(tǒng)的服務(wù)質(zhì)量，使周轉(zhuǎn)時間太長等如果在內(nèi)存中同時運行作業(yè)的數(shù)量太少時，又會導致系統(tǒng)的資源利用率和系統(tǒng)吞吐量太低l根據(jù)系統(tǒng)規(guī)模系統(tǒng)規(guī)模和運行速度運行速度等情況做適當?shù)恼壑詌依據(jù)所采用的調(diào)度算法，決定應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存，通常優(yōu)先調(diào)入內(nèi)存的作業(yè)有：最早進入外存的作業(yè)（先來先服務(wù)調(diào)度算法）外存

11、上最短的作業(yè)（短作業(yè)優(yōu)先調(diào)度算法）外存上優(yōu)先級最高的作業(yè)（優(yōu)先級調(diào)度算法） 174.1.2 調(diào)度準則1. 周轉(zhuǎn)時間周轉(zhuǎn)時間：指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。l周轉(zhuǎn)時間的長短是評價批處理系統(tǒng)的性能、選擇作業(yè)調(diào)度方式與算法的重要準則之一l周轉(zhuǎn)時間=后備隊列等待時間+就緒隊列等待時間*+CPU執(zhí)行時間*+等待I/O完成時間*l帶*項可能會發(fā)生多次 184.1.2 調(diào)度準則1. 周轉(zhuǎn)時間：周轉(zhuǎn)時間：l對每個用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時間最短。但作為計算機系統(tǒng)的管理者，則總是希望能使平均周轉(zhuǎn)時間最短，這不僅會有效地提高系統(tǒng)資源的利用率，而且還可使大多數(shù)用戶都感到滿意。所以一般

12、考慮平均情況，即平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間T：l平均周轉(zhuǎn)時間用來衡量不同調(diào)度算法對同一個作業(yè)流的調(diào)度性能niiTnT11194.1.2 調(diào)度準則l平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間W：作業(yè)周轉(zhuǎn)時間和服務(wù)時間的比值l平均帶權(quán)周轉(zhuǎn)時間用來衡量同一個調(diào)度算法對不同作業(yè)流的調(diào)度性能niiTTnW1s1204.1.2 調(diào)度準則2.響應(yīng)時間：響應(yīng)時間：是從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時間。l響應(yīng)時間=請求信息傳送到處理機+處理機處理信息+響應(yīng)信息回送到終端l響應(yīng)時間的長短可以評價分時系統(tǒng)的性能，這是選擇分時系統(tǒng)中進程調(diào)度算法的重要準則之一214.1.2 調(diào)度準則3.截止時間：截止時

13、間：是指某任務(wù)必須開始執(zhí)行的最遲時間，或必須完成的最遲時間。l這是評價實時系統(tǒng)性能的重要指標，選擇實時調(diào)度算法的重要準則4. 優(yōu)先權(quán)：優(yōu)先權(quán)：l在批處理、分時和實時系統(tǒng)中選擇調(diào)度算法時，都可遵循優(yōu)先權(quán)準則，以便讓某些緊急的作業(yè)能得到及時處理。在要求較嚴格的場合，往往還須選擇搶占式調(diào)度方式，才能保證緊急作業(yè)得到及時處理 224.1.2 調(diào)度準則5. 吞吐量：吞吐量：在單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。l用于評價批處理系統(tǒng)性能的一個重要指標，是選擇批處理作業(yè)調(diào)度的重要準則l與批處理作業(yè)的平均長度具有密切關(guān)系。對于同一批作業(yè)，若采用了較好的調(diào)度方式和算法，則可顯著地提高系統(tǒng)的吞吐量6. 處理機利用率：處

14、理機利用率：l由于CPU價格十分昂貴，致使處理機的利用率成為衡量系統(tǒng)性能的十分重要的指標l調(diào)度方式和算法對處理機的利用率起著十分重要的作用7. 公平性：公平性：l有效地利用其它各類資源，如內(nèi)存、外存和I/O設(shè)備等l選擇適當?shù)恼{(diào)度方式和算法可以保持系統(tǒng)中各類資源都處于忙碌狀態(tài)234.2 調(diào)調(diào) 度度 算算 法法 1 1先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法l先來先服務(wù)算法（First Come First Served， FCFS）按照作業(yè)/進程進入隊列的先后順序進行挑選，先進入的將優(yōu)先進行后續(xù)步驟。該算法既可用于高級調(diào)度，也可用于低級調(diào)度。當在高級調(diào)度中采用該算法時，每次調(diào)度都是從后備作業(yè)隊列中選

15、擇一個或多個最先進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放入就緒隊列。在低級調(diào)度中采用該算法時，則每次調(diào)度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發(fā)生某事件而阻塞后才放棄處理機。該算法比較有利于長作業(yè)該算法比較有利于長作業(yè)(進進程程)，而不利于短作業(yè)，而不利于短作業(yè)(進程進程)。例例1，有以下，有以下4個作業(yè)，采用先來先服務(wù)算法，到達時個作業(yè)，采用先來先服務(wù)算法，到達時間和調(diào)度服務(wù)時間如下表所示間和調(diào)度服務(wù)時間如下表所示作業(yè)到達時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間10200202012423204339

16、1.738143443636418200442442261.1324使用先來先服務(wù)算法得到的平均周轉(zhuǎn)時間與作業(yè)到達順序和調(diào)度順序有關(guān)平均周轉(zhuǎn)時間：20393622680.254T。平均帶權(quán)周轉(zhuǎn)時間：1 1.736 1.139.964W。254.2 調(diào)調(diào) 度度 算算 法法2. 2. 短作業(yè)短作業(yè)( (進程進程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法l短作業(yè)優(yōu)先調(diào)度算法（shot job first, SJF）按照進入系統(tǒng)的作業(yè)所要求的所要求的CPU運行時間的長短運行時間的長短為挑選依據(jù)，優(yōu)先選取預計計算時間最短的作業(yè)?？梢苑謩e用于高級調(diào)度和低級調(diào)度。264.2 調(diào)調(diào) 度度 算算 法法l短作業(yè)優(yōu)先(SJF)

17、的調(diào)度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。而短進程優(yōu)先(SPF)調(diào)度算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時再重新調(diào)度。SJF調(diào)度算法能有效地降低作業(yè)的平均等待時間，調(diào)度算法能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量提高系統(tǒng)吞吐量。例例2，例，例1所示的所示的4個作業(yè)，采用短作業(yè)優(yōu)先調(diào)度算法個作業(yè)，采用短作業(yè)優(yōu)先調(diào)度算法27與FCFS調(diào)度算法相比，平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間都要短，這說明SJF調(diào)度算法有效的降低了作業(yè)的平均等待時間，提高了系統(tǒng)吞吐量，具有

18、較好的調(diào)度性能作業(yè)到達時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間102002020124232144401.7438120211313418200442442261.13平均周轉(zhuǎn)時間：平均帶權(quán)周轉(zhuǎn)時間：2040 1322674.754T1 1.74 13 1.134.224W284.2 調(diào)調(diào) 度度 算算 法法l該調(diào)度算法主要的不足之處是長作業(yè)的運行得不到保證，如果有一長作業(yè)(進程)進入系統(tǒng)的后備隊列(就緒隊列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進來的)短作業(yè)(進程)，將導致長作業(yè)(進程)長期不被調(diào)度。l其他缺點包括：不能保證緊迫性作業(yè)(進程)會被及時處理由于作業(yè)(進程)的長短只是根

19、據(jù)用戶所提供的估計執(zhí)行時間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計運行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。 294.2 調(diào)調(diào) 度度 算算 法法3. 3. 優(yōu)先級算法優(yōu)先級算法l優(yōu)先級算法根據(jù)事先設(shè)定好的進程的優(yōu)先級進程的優(yōu)先級來選取就緒隊列中優(yōu)先級最高的進程投入運行。在運行過程中，如果就緒隊列中出現(xiàn)優(yōu)先級更高的進程，則根據(jù)系統(tǒng)的策略：搶占式或非搶占式進行調(diào)度 304.2 調(diào)調(diào) 度度 算算 法法l非搶占式：非搶占式：當前進程繼續(xù)運行直到完成；或出現(xiàn)需要等待的事件放棄處理機，再調(diào)度優(yōu)先級高的進程運行。l搶占式：搶占式：當前進程占用的處理機被立即剝奪，將處理機分配給優(yōu)先級高的進

20、程，使之運行。只要高優(yōu)先級只要高優(yōu)先級的進程出現(xiàn)，無論當前進程完成與否，都必須立即停的進程出現(xiàn)，無論當前進程完成與否，都必須立即停止，重新將處理機分配給新到的優(yōu)先權(quán)最高的進程止，重新將處理機分配給新到的優(yōu)先權(quán)最高的進程。搶占式的優(yōu)先級調(diào)度算法能更好地滿足緊迫作業(yè)的要求。314.2 調(diào)調(diào) 度度 算算 法法l優(yōu)先級的劃分有兩種方法：其中一種是靜態(tài)優(yōu)先級靜態(tài)優(yōu)先級，在創(chuàng)建進程時確定的，且在進程的整個運行期間保持不變。依據(jù)是進程類型（系統(tǒng)進程優(yōu)先于用戶進程），進程對資源的需求（時間短，需要內(nèi)存少的優(yōu)先考慮），用戶進程的緊迫程度等。該方法簡單易行，系統(tǒng)開銷小，但不夠精確，很可能會長時間忽略優(yōu)先級低的作業(yè)

21、。另一種方法是動態(tài)優(yōu)先級動態(tài)優(yōu)先級，會隨著時間的推移而進行調(diào)整，沒有固定的規(guī)定，以獲得更好調(diào)度性能為前提不斷的更改。比如，在就緒隊列中，等待時間越長的進程，其優(yōu)先權(quán)也會以一定的速率提高；正在運行的進程，CPU處理時間越長，其優(yōu)先權(quán)以一定的速率減小。就能避免長進程長時間占據(jù)處理機，其他相對較短進程無限等待的困境。324.2 調(diào)調(diào) 度度 算算 法法l優(yōu)先級的表示是通過某一范圍內(nèi)的一個整數(shù)來表示的，例如，07或0255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)；優(yōu)先數(shù)；l有的系統(tǒng)用小數(shù)字表示高優(yōu)先級，當數(shù)值愈大時，其優(yōu)先級愈低；l有的系統(tǒng)的規(guī)定與之相反，用大數(shù)字表示高優(yōu)先級。 4.2 調(diào)調(diào) 度度 算算 法法

22、進程到達時間服務(wù)時間優(yōu)先級開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P10330331P2265319172.83P34314731P465271261.2P582412146333表表 4.3 采用搶占式優(yōu)先級調(diào)度算法的進程調(diào)度信息采用搶占式優(yōu)先級調(diào)度算法的進程調(diào)度信息3 1736675T 12.83 1 1.231.8065W 平均周轉(zhuǎn)時間：平均帶權(quán)周轉(zhuǎn)時間：。344.2 調(diào)調(diào) 度度 算算 法法4. 4. 時間片輪轉(zhuǎn)算法時間片輪轉(zhuǎn)算法l時間片輪轉(zhuǎn)算法將CPU分配給就緒隊列中的第一個進程，每每次分配一個時間片。次分配一個時間片。但時間片耗盡時，如果進程未完成，則讓出處理機，轉(zhuǎn)到就緒隊列的隊尾，等待

23、下一輪的時間片的分配。l系統(tǒng)將所有的就緒進程按先來先服務(wù)的原則排成一個隊列將所有的就緒進程按先來先服務(wù)的原則排成一個隊列，每次調(diào)度時，把處理機分配給隊首進程，并令其執(zhí)行一個時間片。當執(zhí)行的時間片用完時發(fā)出中斷請求，調(diào)度程序便據(jù)此信號來停止該進程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執(zhí)行一個時間片。這樣就可以保證系統(tǒng)能在給定的時間這樣就可以保證系統(tǒng)能在給定的時間內(nèi)響應(yīng)所有用戶的請求內(nèi)響應(yīng)所有用戶的請求。354.2 調(diào)調(diào) 度度 算算 法法l在時間片輪轉(zhuǎn)算法中，時間片的大小對系統(tǒng)性能有很時間片的大小對系統(tǒng)性能有很大的影響大的影響l選擇很小的時間片將

24、有利于短作業(yè)，因為它能較快地完成，但會頻繁地發(fā)生中斷、進程上下文的切換，從而增加系統(tǒng)的開銷l選擇太長的時間片，使得每個進程都能在一個時間片內(nèi)完成，時間片輪轉(zhuǎn)算法便退化為FCFS算法，無法滿足交互式用戶的需求l一個較為可取的大小是時間片略大于一次典型的交互時間，這樣可使大多數(shù)進程在一個時間片內(nèi)完成時間片大小對響應(yīng)時間的影響時間片大小對響應(yīng)時間的影響364.2 調(diào)調(diào) 度度 算算 法法進程到達時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P1030331P226319172.83P34471171.75P4651120142.8P582151794.537表表 4.4 采用時間片輪轉(zhuǎn)調(diào)度算法的進程

25、信息采用時間片輪轉(zhuǎn)調(diào)度算法的進程信息（時間片為（時間片為4ms）平均周轉(zhuǎn)時間：平均帶權(quán)周轉(zhuǎn)時間：3 177 149105T12.83 1.752.84.52.5765W384.2 調(diào)調(diào) 度度 算算 法法5. 5. 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法l最高響應(yīng)比優(yōu)先算法同時兼顧作業(yè)的等待時間和處理時間，做有效的協(xié)調(diào)和折中，既能既能照顧短作業(yè)的調(diào)度，同時也不會讓長作業(yè)等待照顧短作業(yè)的調(diào)度，同時也不會讓長作業(yè)等待的時間超出合理的范圍的時間超出合理的范圍。要求服務(wù)時間要求服務(wù)時間等待時間要求服務(wù)時間周轉(zhuǎn)時間響應(yīng)比394.2 調(diào)調(diào) 度度 算算 法法與其他幾種調(diào)度算法的比較：與其他幾種調(diào)度算法的比較

26、：l先來先服務(wù)：只考慮作業(yè)等待時間，忽視作業(yè)計算時間。l短作業(yè)優(yōu)先：考慮作業(yè)預計的計算時間，忽視作業(yè)的等待時間。l最高響應(yīng)比：綜合前兩種算法的優(yōu)點：既照顧了短作業(yè)，又考慮了作業(yè)到達的先后次序，不會使長作業(yè)長期得不到服務(wù)。缺點：計算每個作業(yè)的響應(yīng)比需要耗費一定的時間，性能比短作業(yè)優(yōu)先算法略差。l如果我們能為每個作業(yè)引入前面所述的動態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級隨著等待時間的增加而以一定的速率提高，則長作業(yè)在等待一定的時間后，必然有機會分配到處理機。404.2 調(diào)調(diào) 度度 算算 法法高響應(yīng)比調(diào)度算法：l如果作業(yè)的等待時間相同等待時間相同，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)l當要

27、求服務(wù)的時間相同服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而實現(xiàn)的是先來先服務(wù)l對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高，當其等待時間足夠長時，其優(yōu)先級便可升到很高，從而也可獲得處理機414.2 調(diào)調(diào) 度度 算算 法法l例5，系統(tǒng)中僅有4個作業(yè)，它們到達系統(tǒng)的時間和要求服務(wù)的時間如下表所示，我們分別用先來先服務(wù)、短作業(yè)優(yōu)先和最高響應(yīng)比優(yōu)先算法來進行調(diào)度，分別得到響應(yīng)的平均周轉(zhuǎn)時間。作業(yè)到達時間（ms）要求服務(wù)時間（ms）1020231231054188424.2 調(diào)調(diào) 度度 算算 法法l使用先來先服務(wù)算法，調(diào)度順序：1,2,3,4。l平均周轉(zhuǎn)時間

28、T=（20+29+27+27）/4=25.75msl使用短作業(yè)優(yōu)先算法，調(diào)度順序：1,3,4,2。l平均周轉(zhuǎn)時間 T=（20+15+15+42）/4=23ms434.2 調(diào)調(diào) 度度 算算 法法l使用最高響應(yīng)比優(yōu)先算法，需要先計算各作業(yè)的響應(yīng)比，再決定調(diào)度的作業(yè)。調(diào)度順序為：時間0ms：只有作業(yè)1，選取作業(yè)1，執(zhí)行時間20ms。時間20ms：就緒隊列中有作業(yè)2,3,4。響應(yīng)比依次為：（17+12）/12=2.42，（10+5）/5=3，（2+8）/8=1.25。響應(yīng)比最高的是作業(yè)3，因此調(diào)度作業(yè)3，執(zhí)行時間5ms。時間25ms：就緒隊列中有作業(yè)2,4。響應(yīng)比依次為：（22+12）/12=2.83

29、，（7+8）/8=1.875。響應(yīng)比最高的是作業(yè)2，因此調(diào)度作業(yè)2，執(zhí)行時間12ms。時間37ms：就緒隊列中僅有作業(yè)4，因此調(diào)度作業(yè)4，執(zhí)行時間8ms。l所以調(diào)度順序為：1,3,2,4。l平均周轉(zhuǎn)時間T=（20+15+34+27）/4=24msl由例5可見，最高響應(yīng)比優(yōu)先算法性能介于先來先服務(wù)算法和短作業(yè)優(yōu)先算法之間。4.2 調(diào)調(diào) 度度 算算 法法作業(yè)到達時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間102002020123122537342.833105202515341883745273.3844表表 4.5 采用最高響應(yīng)比優(yōu)先調(diào)度算法的進程信息采用最高響應(yīng)比優(yōu)先調(diào)度算法的進程信息平均

30、周轉(zhuǎn)時間：平均帶權(quán)周轉(zhuǎn)時間：2034 1527244T12.8333.382.554W4.2.6 多級反饋隊列調(diào)度算法l調(diào)度機制可描述如下：(1) 設(shè)置多個就緒隊列設(shè)置多個就緒隊列。 為每個隊列設(shè)置不同的優(yōu)先級，第一個隊列優(yōu)先級最高，第二個次之，其余隊列優(yōu)先級逐個降低。 (2) 每個隊列都采用采用FCFS算法算法。 (3) 按隊列優(yōu)先級調(diào)度按隊列優(yōu)先級調(diào)度，先調(diào)度第一個就緒隊列，為空時，再調(diào)度第二個，依次類推。每個進程執(zhí)行一次時間片之后加入下一個就緒隊列，如到達最后第n個就緒隊列還沒結(jié)束，則按照時間片輪轉(zhuǎn)調(diào)度算法進行調(diào)度。454.2.6 多級反饋隊列調(diào)度算法464.2.7 4.2.7 實時調(diào)度

31、算法實時調(diào)度算法可以按不同方式對實時調(diào)度算法加以分類： 根據(jù)實時任務(wù)性質(zhì)實時任務(wù)性質(zhì)，可將實時調(diào)度的算法分為硬實時調(diào)度算法和軟實時調(diào)度算法； 根據(jù)調(diào)度方式調(diào)度方式，則可分為非搶占調(diào)度算法和搶占調(diào)度算法。 1. 1. 非搶占式調(diào)度算法非搶占式調(diào)度算法 (1) 非搶占式輪轉(zhuǎn)調(diào)度算法。每次選擇隊列中的第一個任務(wù)投入運行。該算法可獲得數(shù)秒至數(shù)十秒的響應(yīng)時間，用于要求不太嚴格的實時控制系統(tǒng)。 (2) 非搶占式優(yōu)先調(diào)度算法。有較高優(yōu)先級的任務(wù)到達時，將該任務(wù)插入隊頭，待當前執(zhí)行的任務(wù)自我終止或運行完成后調(diào)度執(zhí)行。有可能獲得數(shù)秒至數(shù)百毫秒級的響應(yīng)時間，有可能獲得數(shù)秒至數(shù)百毫秒級的響應(yīng)時間，可用于有一定要求的

32、實時控制系統(tǒng)中?？捎糜谟幸欢ㄒ蟮膶崟r控制系統(tǒng)中。2. 2. 搶占式調(diào)度算法搶占式調(diào)度算法 (1) 基于時鐘中斷的搶占式優(yōu)先級調(diào)度算法。某到達的任務(wù)優(yōu)先級高于當前任務(wù)的優(yōu)先級，這時并不立即搶占當前任務(wù)的處理機，而是等到時鐘中斷時鐘中斷到來時再搶占處理機。這種調(diào)度算法能獲得較好的響應(yīng)效果，調(diào)度延遲可降為幾十毫秒至幾毫秒，可用于大多數(shù)的實時系統(tǒng)中。 (2) 立即搶占(Immediate Preemption)的優(yōu)先級調(diào)度算法。要求操作系統(tǒng)具有快速響應(yīng)外部事件的能力，一旦出現(xiàn)一旦出現(xiàn)外部中斷，只要當前任務(wù)沒有處于臨界區(qū)，便能搶占當前任外部中斷，只要當前任務(wù)沒有處于臨界區(qū)，便能搶占當前任務(wù)的執(zhí)行務(wù)的執(zhí)

33、行，把處理機分配給請求中斷的緊迫任務(wù)。這種算法能獲得非?？斓捻憫?yīng)，調(diào)度延遲可低到幾毫秒至100微秒，甚至更低。進程進程1實時進程請求調(diào)度實時進程請求調(diào)度調(diào)度實時進程運行調(diào)度實時進程運行進程進程2進程進程n實時進程實時進程非搶占輪轉(zhuǎn)調(diào)度非搶占優(yōu)先權(quán)調(diào)度當前進程實時進程 實時進程請求調(diào)度實時進程請求調(diào)度當前進程運行完成當前進程運行完成基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度當前進程實時進程實時進程請求調(diào)度實時進程請求調(diào)度時鐘中斷到來時時鐘中斷到來時調(diào)度時間當前進程 實時進程實時進程實時進程請求調(diào)度實時進程請求調(diào)度調(diào)度時間實時進程搶占當前進程，實時進程搶占當前進程，并立即執(zhí)行并立即執(zhí)行立即搶占的優(yōu)先權(quán)調(diào)度4

34、.2.7 4.2.7 實時調(diào)度算法實時調(diào)度算法最早截止時間優(yōu)先 (Earliest Deadline First, EDF)算法 根據(jù)任務(wù)的截止時間確定任務(wù)的優(yōu)先級，截止時間愈早，優(yōu)先級愈高，具有最早截止時間的任務(wù)排在隊首，每次總是選擇隊首第一個任務(wù)調(diào)度執(zhí)行。1.非搶占式調(diào)度方式用于非周期實時任務(wù)圖a給出了將該算法用于非搶占調(diào)度方式之例。圖a. EDF算法用于非搶占調(diào)度方式4.2.7 4.2.7 實時調(diào)度算法實時調(diào)度算法最早截止時間優(yōu)先 (Earliest Deadline First, EDF)算法 2. 搶占式調(diào)度方式用于周期實時任務(wù) 圖b給出了將該算法用于搶占調(diào)度方式之例。在該例中有兩個

35、周期任務(wù)，任務(wù)A和任務(wù)B的周期時間分別為20 ms和50 ms，每個周期的處理時間分別為10ms和25ms。圖b 最早截止時間優(yōu)先算法用于搶占調(diào)度方式之例4.2.7 4.2.7 實時調(diào)度算法實時調(diào)度算法最低松弛度優(yōu)先(Least Laxity First,LLF)算法 該算法在確定任務(wù)的優(yōu)先級時，根據(jù)的是任務(wù)的緊任務(wù)的緊急急(或松弛或松弛)程度程度。任務(wù)緊急程度愈高，賦予該任務(wù)的優(yōu)先級就愈高，以使之優(yōu)先執(zhí)行。 該算法主要用于可搶占調(diào)度方式中。假如在一個實時系統(tǒng)中有兩個周期性實時任務(wù)A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms，任務(wù)B要求每50ms執(zhí)行一次，執(zhí)行時間為25ms。由此可

36、知，任務(wù)A和B每次必須完成的時間分別為：A1、A2、A3、和B1、B2、B3、，見圖c。4.2.7 4.2.7 實時調(diào)度算法實時調(diào)度算法圖c A和B任務(wù)每次必須完成的時間584.2.8 多處理器調(diào)度問題l現(xiàn)代操作系統(tǒng)一般采用多處理器調(diào)度方式。主要考慮如何為進程分配處理器，以及選擇怎樣的調(diào)度算法。l1.將處理器放入處理器池，采用兩類分配方式：A 靜態(tài)分配。每個處理器對應(yīng)一個就緒隊列，這樣調(diào)度需要的開銷并不多，但是對應(yīng)的就緒隊列長的處理就緒隊列長的處理器就會比較繁忙，而對應(yīng)的就緒隊列短的處理器就會器就會比較繁忙，而對應(yīng)的就緒隊列短的處理器就會相對空閑，處理器利用率低相對空閑，處理器利用率低。B 動

37、態(tài)分配。所有處理器都對應(yīng)同一個就緒隊列，那個處理器空閑，就選擇就緒隊列中的進程占用該處理器。合理利用空閑的處理器。合理利用空閑的處理器。594.2.8 多處理器調(diào)度問題l負載共享調(diào)度算法l進程并不指派到具體的處理器上，只有一個全局的就緒隊列，一旦有處理器空閑，就選擇進程的一個線程占有處理器。l算法分析：將負載平均分配到多個處理器上，確保處理器的充分利用。但是就緒隊列必須互斥訪就緒隊列必須互斥訪問，不能出現(xiàn)同一個線程運行在不同的處理器上問，不能出現(xiàn)同一個線程運行在不同的處理器上的情況的情況。由于互斥訪問，會導致一些等待的情況，影響性能。l具體的負載共享調(diào)度算法有：先來先服務(wù)、最小線程數(shù)優(yōu)先和搶占

38、式最小線程數(shù)優(yōu)先。604.2.8 多處理器調(diào)度問題l群調(diào)度算法l一組線程同時被調(diào)度到同一個處理器上運行。使得多個線程能夠并行執(zhí)行，減少進程切換等損失，提高性能。處理器的分配方面如果平均分配會產(chǎn)生處理器資源的浪費，應(yīng)該根據(jù)線程數(shù)加權(quán)的方式，來按比例分配處理器時間，避免浪費。614.2.8 多處理器調(diào)度問題l動態(tài)調(diào)度算法l操作系統(tǒng)和應(yīng)用進程共同進行調(diào)度決策操作系統(tǒng)和應(yīng)用進程共同進行調(diào)度決策。如何在應(yīng)用進程之間分配處理器由操作系統(tǒng)決定；應(yīng)用線程決定在已分配的處理器上哪些可運行的線程可執(zhí)行、哪些需要掛起。操作系統(tǒng)調(diào)度的具體原則如下：分配空閑的處理器以滿足進程的請求沒有空閑的處理器，從當前分配多個處理器

39、的任一個進程中回收一個處理器，將該處理器分配給請求的進程。任何分配都無法滿足該請求，則該進程保持未完成的狀態(tài)，直到有足夠的處理器可用或者進程取消該請求。每釋放一個或者多個處理器時，都要對還沒解決過的請求處理器的進程隊列進行掃描，為其中的尚未沒分配過的進程分配處理器，如果還有多余的處理器資源，則再次掃面隊列，按照先來先服務(wù)原則分配處理器。624.3 死鎖簡介死鎖簡介 4.3.1 資源資源l計算機系統(tǒng)中存在一些只能被一個進程一個進程所使用的資源，如磁帶機、打印機等獨占設(shè)備。l兩個進程同時進入臨界區(qū)會導致數(shù)據(jù)錯誤或者系統(tǒng)錯誤。所以操作系統(tǒng)需要控制進程獨立對這些臨界資源進行訪問。l對資源的訪問需要以下

40、步驟：申請，訪問，歸還。如果某一個進程申請資源的時候，資源正在被其他進程使用，則該申請的進程需要等待。634.3.1 資源資源l資源可以分成如下兩類：可剝奪性資源可剝奪性資源，是指某進程在獲得這類資源后，該資源可以再被其他進程或系統(tǒng)剝奪。如：處理機和內(nèi)存。優(yōu)先權(quán)高的進程可以剝奪優(yōu)先權(quán)低的進程的處理機。內(nèi)存區(qū)可由存儲器管理程序把一個進程從一個存儲區(qū)移到另一個存儲區(qū)，此即剝奪了該進程原來占有的存儲區(qū)。甚至可將一個進程從內(nèi)存調(diào)出到外存上。不可剝奪性資源不可剝奪性資源，當系統(tǒng)把這類資源分配給某進程后，再不能強行收回，只能在進程用完后自行釋放，如磁帶機、打印機等。 644.3.2 死鎖產(chǎn)生原因和必要條件

41、死鎖產(chǎn)生原因和必要條件l死鎖的定義所謂死鎖所謂死鎖 (Deadlock)，是指多個進程因競爭資源而造成的一種僵局(Deadly-Embrace)，若無外力作用，這些進程將永遠不能再向前推進。 在一組進程發(fā)生死鎖的情況下，這組死鎖進程中的每一個進程，都在等待另一個死鎖進程所占有的資源。 654.3.2 死鎖產(chǎn)生原因和必要條件死鎖產(chǎn)生原因和必要條件1. 死鎖產(chǎn)生的原因死鎖產(chǎn)生的原因和臨界資源的訪問及進程的并發(fā)執(zhí)行有關(guān)。資源競爭資源競爭：當系統(tǒng)中供多個進程共享的資源如打印機，其數(shù)目不足以滿足諸進程的需要時，會引起諸多進程對資源的競爭而產(chǎn)生死鎖；進程推進順序不當進程推進順序不當：進程在運行過程中，請求

42、和釋放資源的順序不當，也同樣會導致產(chǎn)生進程死鎖。 66進程推進順序不當引起死鎖進程推進順序不當引起死鎖 P1req(R1) P1req(R2) P1rel(R1) P1rel(R2)P2rel(R1)P2rel(R2)P2req(R1)P2req(R2)abcdefg1、推進順序、推進順序P1req(R1)P1req(R2)P1rel(R1)P1rel(R2)P2req(R2)P2req(R1)P2rel(R2)P2rel(R1)3、推進順序 P1req(R1) P1req(R2) P2req(R2) P1rel(R1) P1rel(R2) P2req(R1) P2rel(R2) P2rel(

43、R1)4、推進順序：、推進順序：P1req(R1) ； P2req(R2) , P1和和P2再再繼續(xù)推進將發(fā)生死鎖繼續(xù)推進將發(fā)生死鎖四種顏色的線段為四種推進順序2、類似情形、類似情形1674.3.2 死鎖產(chǎn)生原因和必要條件死鎖產(chǎn)生原因和必要條件2. 死鎖產(chǎn)生的必要條件互斥互斥: 進程對所分配到的資源必須獨立使用，即在一段時間內(nèi)某資源只由一個進程占用，不能共享。如果此時還有其它進程請求該資源，則請求者只能等待，直至占有該資源的進程使用完畢，對資源進行釋放。請求和保持請求和保持：進程已經(jīng)持有了至少一個資源，但又提出了新的資源請求，而該資源又已被其它進程占有，此時請求進程阻塞，但又對已獲得的其它資源

44、保持繼續(xù)持有。不可剝奪不可剝奪: 在未使用完之前，不能剝奪進程已獲得的資源，只能在使用完時由自己釋放。循環(huán)等待循環(huán)等待：在發(fā)生死鎖時，必然存在一個進程和進程之間等待相互資源的環(huán)形鏈。使得鏈中每個進程的資源需求都得不到滿足。684.3.3 死鎖的表示方法死鎖的表示方法系統(tǒng)資源分配圖來表示死鎖一個系統(tǒng)資源分配圖（System Resource Allocation Graph, SRAG）可以定義為一個二元組 ，其中 是頂點的集合， 是有向邊的集合。 是由系統(tǒng)內(nèi)的所有進程組成的集合，每一個 代表一個進程； 是由系統(tǒng)內(nèi)所有資源組成的集合，每一個 代表一類資源。如果 ，則存在一條從 指向 的有向邊，它

45、表示進程 提出了一個要求分配 類資源中的一個資源的請求。( ,)SRAGV EVE12 ,nPP PPiP12 , , nRr rrjr,ijP rEiPjriPjr694.3.3 死鎖的表示方法死鎖的表示方法系統(tǒng)資源分配圖來表示死鎖圖 4.7 SRAG示例704.3.4 死鎖的判定死鎖的判定根據(jù)SRAG的定義，可以使用以下規(guī)則判定死鎖如果SRAG中無環(huán)路無環(huán)路，則系統(tǒng)不會死鎖不會死鎖。如果SRAG中有環(huán)路有環(huán)路，且處于此環(huán)中的每類資源只有一個每類資源只有一個，如圖4.7(c)所示，則系統(tǒng)出現(xiàn)死鎖死鎖。此時，環(huán)是系統(tǒng)存在死鎖的充分必要條件。如果SRAG中有環(huán)路有環(huán)路，但是處于此環(huán)中的每類資源的

46、個數(shù)不全為每類資源的個數(shù)不全為1，如圖4.7(d)所示，則系統(tǒng)不一定會發(fā)生死鎖不一定會發(fā)生死鎖。此時，環(huán)只是產(chǎn)生死鎖的必要條件而不是充分條件。系統(tǒng)存在死鎖狀態(tài)的充要條件是當且僅當系統(tǒng)的當且僅當系統(tǒng)的SRAG是不可完全簡是不可完全簡化的化的。如果資源滿足某個進程的要求，則在SRAG中消去此進程的所有請求邊和分配邊，使其成為孤立結(jié)點。對所有進程執(zhí)行該操作。如果所有進程都成為孤立結(jié)點，則稱該圖是可完全簡化的；否則稱該圖是不可完全簡化的。714.4 死鎖預防死鎖預防l破壞死鎖產(chǎn)生的條件中的一項或多項，就能夠預防死鎖情況的發(fā)生。由于臨界資源的特性，不能共享，所以互斥這個條件不能被破壞，只能考慮另外三種條

47、件。724.4 死鎖預防死鎖預防l破壞破壞“請求和保持請求和保持”條件條件l請求請求：將對資源的申請放在進程運行之前一次性進對資源的申請放在進程運行之前一次性進行行，得到了所需所有資源的進程在整個運行期間不會再提出資源要求，從而破壞了請求條件。l分配分配：在分配資源時，只要有一種資源不能滿足某只要有一種資源不能滿足某進程的要求，即使其它所需的各資源都空閑，也不進程的要求，即使其它所需的各資源都空閑，也不分配給該進程分配給該進程，而讓該進程等待。由于在該進程的等待期間，它并未占有任何資源，因而破壞了保持條件。 734.4 死鎖預防死鎖預防l破壞破壞“不剝奪不剝奪”條件條件l進程逐個地提出對資源的

48、要求。 當一個已經(jīng)保持了某些當一個已經(jīng)保持了某些資源的進程，再提出新的資源請求而不能立即得到滿足資源的進程，再提出新的資源請求而不能立即得到滿足時，必須釋放它已經(jīng)保持了的所有資源時，必須釋放它已經(jīng)保持了的所有資源，待以后需要時再重新申請。 已經(jīng)占有的資源，在運行過程中會被暫時地釋放掉，從而破壞了“不剝奪”條件。 744.4 死鎖預防死鎖預防l破壞破壞“環(huán)路等待環(huán)路等待”條件條件l系統(tǒng)將所有資源按類型分成不同等級進行排列，并賦予不同的等級號。例如，資源a序號為1，資源b的序號為2，資源c的序號為3，。所有進程對資源的請求必須嚴格按照資所有進程對資源的請求必須嚴格按照資源序號遞增的次序提出源序號遞

49、增的次序提出，這樣，在所形成的資源分配圖中，不可能再出現(xiàn)環(huán)路，破壞了“環(huán)路等待”條件。 這種方法稱為有序資源分配法有序資源分配法。75有序資源分配法有序資源分配法l這種算法資源按某種規(guī)則對系統(tǒng)中的所有資源統(tǒng)一編號，申請時必須以某種順序依次申請，如上升的次序。l例如：進程A，使用資源的順序是R1，R2；進程B，使用資源的順序是R2，R1；如果采用動態(tài)分配有可能形成環(huán)路條件：A保持資源R1，B保持資源R2，它們各自所需的另一個資源都在對方手中，造成死鎖。 l采用有序資源分配法：R1的編號為1，R2的編號為2； A和B對各自所需要資源的申請次序都是：R1，R2 。這樣就破壞了請求和保持條件，避免了死

50、鎖的發(fā)生。764.5 死鎖避免死鎖避免l死鎖的預防會犧牲系統(tǒng)的并發(fā)性能和資源的利用率，死鎖避免通過合理的資源分配確保不會死鎖避免通過合理的資源分配確保不會出現(xiàn)循環(huán)等待的條件出現(xiàn)循環(huán)等待的條件，除了能夠避免死鎖，還能夠支持進程的并發(fā)及資源的合理使用。并且死鎖避免的過程是動態(tài)的，沒有強制和預先設(shè)置的規(guī)則。774.5.1 銀行家算法銀行家算法(Dijkstra,1965)l基本思想基本思想：先判斷系統(tǒng)是否處于安全狀態(tài)，然后試探性地接受一個進程的資源請求，試探性分配資源，計算分配之后剩余的可用資源是否能滿足系統(tǒng)中其他進程的需要，并且是否有進程能夠獲取足夠多的資源來完成進程，釋放資源。l如果考慮了完成進

51、程的資源釋放和其他進程的需求，能夠最終使得每個進程都能夠順利完成，則將真正實施該進程的分配需求；否則，說明系統(tǒng)將處于不安全狀態(tài)，不會真正實施該分配需求，等待其他進程的資源申請。784.5.1 銀行家算法銀行家算法l1 安全狀態(tài)安全狀態(tài) 安全狀態(tài)是指系統(tǒng)能按某種順序如（稱為安全序列）為每個進程分配其所需資源，直至最大需求，使每個進程都可順序完成。若系統(tǒng)不存在這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。在該方法中，允許進程動態(tài)地申請資源，但系統(tǒng)在進行資源分配之前，應(yīng)先計算此次資源分配的安全性。 并非所有不安全態(tài)都是死鎖態(tài)，但系統(tǒng)進入不安全態(tài)后，便可能繼而進入死鎖態(tài)。反之，只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便

52、可避免死鎖。避免死鎖的實質(zhì)是：如何使系統(tǒng)如何使系統(tǒng)不進入不安全狀態(tài)。不進入不安全狀態(tài)。安全狀態(tài)之例安全狀態(tài)之例 假定系統(tǒng)中有三個進程P1、P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設(shè)在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配，如下表所示： T0時刻系統(tǒng)是安全的，因這時存在一安全序列 ,即只要系統(tǒng)按此序列分配資源，每個進程都可順利完成。79804.5.2 銀行家算法銀行家算法l銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu)( (資源資源m，進程，進程n) ) (1) 可利用資源向量可利用資源向量Availa

53、ble。該向量為一個數(shù)組，含有m個元素，每一個元素代表一類可利用的資源數(shù)目。將系統(tǒng)中所配置的該類全部可用資源的數(shù)目設(shè)置為初始值，隨著該類資源的分配和回收，其數(shù)值會動態(tài)的發(fā)生改變。系統(tǒng)中第j類資源有K個，能用以下式子表示：Availablej=K。 (2) 最大需求矩陣最大需求矩陣Max。該矩陣大小為nm，表示系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。進程i需要第j類資源的最大數(shù)目為K，能用以下式子表示：Maxi,j=K。 814.5.2 銀行家算法銀行家算法 (3) 分配矩陣分配矩陣Allocation。該矩陣大小為nm的矩陣，表示系統(tǒng)中每一類資源當前已分配給每一個進程的資源數(shù)。進程i

54、當前已分得第j類資源的數(shù)目為K，可以表示成：Allocationi,j=K。 (4) 需求矩陣需求矩陣Need。該矩陣大小依然為nm，表示每一個進程還需要的各類資源數(shù)。進程i還需要第j類資源K個，可以表示為：Needi,j=K。 其中后三者之間存在如下關(guān)系：Needi, j = Maxi, j - Allocationi, j824.5.2 銀行家算法銀行家算法l銀行家算法銀行家算法 設(shè)Request i是進程Pi的請求向量，如果Request ij=K，表示進程Pi需要K個R j類型的資源。當Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查： (1) 如果Request ij Needi,j，便轉(zhuǎn)

55、向步驟(2)；否則認為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。 (2) 如果Requestij Availablej，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。 834.5.1 銀行家算法銀行家算法 (3) 系統(tǒng)試探著把資源分配給進程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Availablej := Availablej - Request ij；Allocationi,j := Allocationi,j + Request ij；Needi,j := Needi,j - Request ij； (4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正

56、式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。 844.5.1 銀行家算法銀行家算法綜上所述，存在以下兩種類型的判斷：l安全的分配：l判斷該時刻T0是否存在安全序列 lT0存在安全序列則對某進程Pi的請求進行判斷 lRequestij Needi,j lRequestij Availablej l以上 、均滿足分配，得到Pi的新配置 l對全新的環(huán)境T1判斷是否存在安全序列 lT1存在安全序列則對某進程Pj的請求進行判斷 1.重復1-3直到找到一個具體的安全序列 Pi,Pj,Pn為止854.5.1 銀行家算法銀行家算法l不安全的分配：

57、l判斷該時刻T0是否存在安全序列 lT0存在安全序列則對某進程Pi的請求進行判斷 lRequestij Needi,j lRequestij Availablej l以上 、至少有一個不滿足分配，Pi等待1.不同意進程Pi的請求，對另一個進程Pj的請求進行安全性判斷86安全性算法安全性算法 (1) 設(shè)置兩個向量： 工作向量Work，含m個元素,表示系統(tǒng)可提供給進程繼續(xù)運行所需要的各類資源數(shù)，算法開始時，Work: = Available. 完成向量Finish，表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成，開始時Finishi :=false；當有足夠資源分配給進程時，令Finishi := true。 (2) 從進程集中找一個能滿足下述條件的進程： Finishi := false； Needi Work。若找到，執(zhí)行步驟(3)，否則執(zhí)行步驟(4)。(3) 當進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故