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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

25、信息采用時(shí)間片輪轉(zhuǎn)調(diào)度算法的進(jìn)程信息（時(shí)間片為（時(shí)間片為4ms）平均周轉(zhuǎn)時(shí)間：平均帶權(quán)周轉(zhuǎn)時(shí)間：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)先算法同時(shí)兼顧作業(yè)的等待時(shí)間和處理時(shí)間，做有效的協(xié)調(diào)和折中，既能既能照顧短作業(yè)的調(diào)度，同時(shí)也不會(huì)讓長(zhǎng)作業(yè)等待照顧短作業(yè)的調(diào)度，同時(shí)也不會(huì)讓長(zhǎng)作業(yè)等待的時(shí)間超出合理的范圍的時(shí)間超出合理的范圍。要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間要求服務(wù)時(shí)間周轉(zhuǎn)時(shí)間響應(yīng)比394.2 調(diào)調(diào) 度度 算算 法法與其他幾種調(diào)度算法的比較：與其他幾種調(diào)度算法的比較

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

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

28、T=（20+29+27+27）/4=25.75msl使用短作業(yè)優(yōu)先算法，調(diào)度順序：1,3,4,2。l平均周轉(zhuǎn)時(shí)間 T=（20+15+15+42）/4=23ms434.2 調(diào)調(diào) 度度 算算 法法l使用最高響應(yīng)比優(yōu)先算法，需要先計(jì)算各作業(yè)的響應(yīng)比，再?zèng)Q定調(diào)度的作業(yè)。調(diào)度順序?yàn)椋簳r(shí)間0ms：只有作業(yè)1，選取作業(yè)1，執(zhí)行時(shí)間20ms。時(shí)間20ms：就緒隊(duì)列中有作業(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í)行時(shí)間5ms。時(shí)間25ms：就緒隊(duì)列中有作業(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í)行時(shí)間12ms。時(shí)間37ms：就緒隊(duì)列中僅有作業(yè)4，因此調(diào)度作業(yè)4，執(zhí)行時(shí)間8ms。l所以調(diào)度順序?yàn)椋?,3,2,4。l平均周轉(zhuǎn)時(shí)間T=（20+15+34+27）/4=24msl由例5可見，最高響應(yīng)比優(yōu)先算法性能介于先來(lái)先服務(wù)算法和短作業(yè)優(yōu)先算法之間。4.2 調(diào)調(diào) 度度 算算 法法作業(yè)到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間102002020123122537342.833105202515341883745273.3844表表 4.5 采用最高響應(yīng)比優(yōu)先調(diào)度算法的進(jìn)程信息采用最高響應(yīng)比優(yōu)先調(diào)度算法的進(jìn)程信息平均

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

55、向步驟(2)；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。 (2) 如果Requestij Availablej，便轉(zhuǎn)向步驟(3)；否則，表示尚無(wú)足夠資源，Pi須等待。 834.5.1 銀行家算法銀行家算法 (3) 系統(tǒng)試探著把資源分配給進(jìn)程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、式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。 844.5.1 銀行家算法銀行家算法綜上所述，存在以下兩種類型的判斷：l安全的分配：l判斷該時(shí)刻T0是否存在安全序列 lT0存在安全序列則對(duì)某進(jìn)程Pi的請(qǐng)求進(jìn)行判斷 lRequestij Needi,j lRequestij Availablej l以上 、均滿足分配，得到Pi的新配置 l對(duì)全新的環(huán)境T1判斷是否存在安全序列 lT1存在安全序列則對(duì)某進(jìn)程Pj的請(qǐng)求進(jìn)行判斷 1.重復(fù)1-3直到找到一個(gè)具體的安全序列 Pi,Pj,Pn為止854.5.1 銀行家算法銀行家算法l不安全的分配：

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