操作系統(tǒng) 第3章 調(diào)度與死鎖

1、第3章 處理機調(diào)度與死鎖 在多道程序環(huán)境下，進程數(shù)目往往多于在多道程序環(huán)境下，進程數(shù)目往往多于處理機數(shù)目。要求系統(tǒng)能按某種算法，處理機數(shù)目。要求系統(tǒng)能按某種算法，動態(tài)地將處理機分配給就緒隊列中的一動態(tài)地將處理機分配給就緒隊列中的一個進程，使之執(zhí)行。個進程，使之執(zhí)行。 現(xiàn)代現(xiàn)代OS的運行性能，如吞吐量、作業(yè)平的運行性能，如吞吐量、作業(yè)平均周轉(zhuǎn)時間、響應(yīng)的及時性等，在很大均周轉(zhuǎn)時間、響應(yīng)的及時性等，在很大程度上取決于調(diào)度，因而，調(diào)度策略成程度上取決于調(diào)度，因而，調(diào)度策略成了了OS的一個關(guān)鍵問題。的一個關(guān)鍵問題。3.1 處理機調(diào)度的基本概念處理機調(diào)度的基本概念 3.1.1 3.1.1 高級、中級和低

2、級調(diào)度高級、中級和低級調(diào)度 1. 1. 高級調(diào)度高級調(diào)度又稱作業(yè)調(diào)度或長期調(diào)度（又稱作業(yè)調(diào)度或長期調(diào)度（long-term long-term scheduling)scheduling)。根據(jù)某種算法，決定把外存上處于后根據(jù)某種算法，決定把外存上處于后備隊列的哪些作業(yè)調(diào)入內(nèi)存?zhèn)潢犃械哪男┳鳂I(yè)調(diào)入內(nèi)存3.1 處理機調(diào)度的基本概念處理機調(diào)度的基本概念 作業(yè)作業(yè)：（用戶）利用計算機進行一次運行：（用戶）利用計算機進行一次運行所需工作的集合。要完成一個工作，用戶所需工作的集合。要完成一個工作，用戶必須先提交一個作業(yè)。如一個作業(yè)可能由必須先提交一個作業(yè)。如一個作業(yè)可能由多個程序構(gòu)成。多個程序構(gòu)成。在在

3、PC機或普通工作站和服務(wù)器上幾乎沒機或普通工作站和服務(wù)器上幾乎沒有作業(yè)的概念有作業(yè)的概念在巨型機和大型服務(wù)器上，主機的速度高在巨型機和大型服務(wù)器上，主機的速度高且造價高，要保證其利用率和效率，用專且造價高，要保證其利用率和效率，用專門的作業(yè)控制軟件作為前端機向主機提交門的作業(yè)控制軟件作為前端機向主機提交作業(yè)的唯一入口。用戶以批文件將作業(yè)提作業(yè)的唯一入口。用戶以批文件將作業(yè)提交到前端機是用戶啟動程序的主要方式。交到前端機是用戶啟動程序的主要方式。 2. 低級調(diào)度低級調(diào)度也稱進程調(diào)度或短期調(diào)度。用于決定也稱進程調(diào)度或短期調(diào)度。用于決定就緒隊列中哪個進程獲得處理機，之就緒隊列中哪個進程獲得處理機，之

4、后派發(fā)程序（后派發(fā)程序（dispatcher）將處理機）將處理機分配給該進程。分配給該進程。 進程調(diào)度可采用下面兩種方式進程調(diào)度可采用下面兩種方式1）非搶先式調(diào)度（）非搶先式調(diào)度（Non-preemptive Mode)一旦把處理機分配給某進程后，便讓該一旦把處理機分配給某進程后，便讓該進程一直執(zhí)行，直至該進程完成或阻塞進程一直執(zhí)行，直至該進程完成或阻塞時，才再把處理機分配給其他進程。時，才再把處理機分配給其他進程。正在執(zhí)行的進程正常結(jié)束或由于某種正在執(zhí)行的進程正常結(jié)束或由于某種錯誤而終止運行；錯誤而終止運行；執(zhí)行中的進程提出執(zhí)行中的進程提出I/O請求，在等待請求，在等待I/O完成前，進程阻塞

5、，轉(zhuǎn)進程調(diào)度；完成前，進程阻塞，轉(zhuǎn)進程調(diào)度；在進程通訊中，執(zhí)行中的進程執(zhí)行了在進程通訊中，執(zhí)行中的進程執(zhí)行了某種原語操作，如某種原語操作，如P操作、阻塞原語操作、阻塞原語和喚醒原語。和喚醒原語。2）搶先式調(diào)度（）搶先式調(diào)度（preemptive mode)允許暫停某個正在執(zhí)行的進程，將已允許暫停某個正在執(zhí)行的進程，將已分配給該進程的處理機重新分配給另分配給該進程的處理機重新分配給另一進程。一進程。時間片原則：在分時系統(tǒng)中，按照時間片原則：在分時系統(tǒng)中，按照時間片輪轉(zhuǎn)，分給進程的時間片用時間片輪轉(zhuǎn)，分給進程的時間片用完完優(yōu)先權(quán)原則：按照優(yōu)先級調(diào)度，有優(yōu)先權(quán)原則：按照優(yōu)先級調(diào)度，有更高優(yōu)先級進程變

6、為就緒更高優(yōu)先級進程變?yōu)榫途w短作業(yè)優(yōu)先原則短作業(yè)優(yōu)先原則 3. 中級調(diào)度中級調(diào)度在條件允許下，在外存掛起的進程集合在條件允許下，在外存掛起的進程集合中選擇哪些進程激活并調(diào)回內(nèi)存。中選擇哪些進程激活并調(diào)回內(nèi)存。為提高效率，加快進程運行，調(diào)節(jié)系統(tǒng)為提高效率，加快進程運行，調(diào)節(jié)系統(tǒng)的負荷，提高吞吐量。的負荷，提高吞吐量。有時需要在選擇內(nèi)存中阻塞或就緒的進有時需要在選擇內(nèi)存中阻塞或就緒的進程暫時放到外存（一般是硬盤），即所程暫時放到外存（一般是硬盤），即所謂的謂的掛起掛起。當這些進程又具備了運行條件、且內(nèi)存當這些進程又具備了運行條件、且內(nèi)存又稍有空閑時，中級調(diào)度把外存上的就又稍有空閑時，中級調(diào)度把外存

7、上的就緒進程調(diào)入內(nèi)存，放入就緒隊列。這種緒進程調(diào)入內(nèi)存，放入就緒隊列。這種內(nèi)外存的數(shù)據(jù)交換稱為內(nèi)外存的數(shù)據(jù)交換稱為對換對換。外存外存對換對換作業(yè)輸入作業(yè)輸入 spooling輸入程序輸入程序 spooling 高級調(diào)度高級調(diào)度就就緒緒阻阻塞塞就緒就緒運行運行完完成成阻阻塞塞后備后備作業(yè)作業(yè)輸出輸出4. 4. 三種調(diào)度之間的關(guān)系三種調(diào)度之間的關(guān)系低級調(diào)度低級調(diào)度中級調(diào)度中級調(diào)度就緒隊列就緒隊列阻塞隊列阻塞隊列cpu進程調(diào)度進程調(diào)度等待事件等待事件時間片完時間片完進程完成進程完成用戶用戶事件出現(xiàn)事件出現(xiàn)3.1.2 調(diào)度隊列模型 1.1.僅有進程調(diào)度的調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型 特點：單

8、就緒、單阻塞隊列特點：單就緒、單阻塞隊列就緒隊列就緒隊列阻塞隊列阻塞隊列cpu進程調(diào)度進程調(diào)度等待事件等待事件時間片完時間片完進程完成進程完成作業(yè)作業(yè)調(diào)度調(diào)度后備隊列后備隊列2. 2. 具有高級和低級的調(diào)度隊列模型具有高級和低級的調(diào)度隊列模型特點特點 ：1)1)具有進程調(diào)度、作業(yè)調(diào)度具有進程調(diào)度、作業(yè)調(diào)度 2) 2)根據(jù)阻塞原因設(shè)置了多個阻塞隊列根據(jù)阻塞原因設(shè)置了多個阻塞隊列3.同時具有三級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型作業(yè)調(diào)度作業(yè)調(diào)度就就隊隊 列列緒緒CPU進程調(diào)度進程調(diào)度進程完成進程完成時間片完時間片完事件出現(xiàn)事件出現(xiàn)阻阻 塞塞列列起起 隊隊掛掛阻阻隊隊 列列塞塞等待事件

9、等待事件就緒掛起隊列就緒掛起隊列事件出現(xiàn)事件出現(xiàn)掛起掛起中級調(diào)度中級調(diào)度后后隊隊 列列備備交互型作業(yè)交互型作業(yè)批量作業(yè)批量作業(yè)掛起掛起選擇哪種模型應(yīng)根據(jù)系統(tǒng)的規(guī)模及目標制定選擇哪種模型應(yīng)根據(jù)系統(tǒng)的規(guī)模及目標制定3.1.3 選擇調(diào)度方式和算法的若干準則 我們可從不同的角度來判斷處理機調(diào)度我們可從不同的角度來判斷處理機調(diào)度算法的性能。實際的處理機調(diào)度算法選算法的性能。實際的處理機調(diào)度算法選擇是一個綜合的判斷結(jié)果。擇是一個綜合的判斷結(jié)果。 面向用戶的準則 面向系統(tǒng)的準則周轉(zhuǎn)時間短周轉(zhuǎn)時間短響應(yīng)時間快響應(yīng)時間快 截止時間的保證截止時間的保證 優(yōu)先權(quán)準則優(yōu)先權(quán)準則 系統(tǒng)吞吐量高系統(tǒng)吞吐量高處理機利用率好

10、處理機利用率好 資源的平衡利用資源的平衡利用 批處理系統(tǒng)的重要指標。批處理系統(tǒng)的重要指標。 作業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時間作業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時間為為周轉(zhuǎn)時間周轉(zhuǎn)時間。 包括：在外存后備隊列中等待，包括：在外存后備隊列中等待，CPU上執(zhí)行，上執(zhí)行，就緒隊列和阻塞隊列中等待，結(jié)果輸出等待。就緒隊列和阻塞隊列中等待，結(jié)果輸出等待。 平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間T和平均帶權(quán)周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間（帶權(quán)周（帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間W是是 T(周轉(zhuǎn)周轉(zhuǎn))/ (CPU執(zhí)行執(zhí)行)） 平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間: 帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 周轉(zhuǎn)時間周轉(zhuǎn)時間niiTnT11nisiiTTnW1

11、1作業(yè)作業(yè)提交時間提交時間/ /時時運行時間運行時間/h/h1 110.0010.002 22 210.1010.101 13 310.2510.250.250.25例例:有如下三道作業(yè)。系統(tǒng)為它們服務(wù)的有如下三道作業(yè)。系統(tǒng)為它們服務(wù)的順序是：順序是：1、2、3。求平均周轉(zhuǎn)時間和平。求平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。均帶權(quán)周轉(zhuǎn)時間。作作業(yè)業(yè)提交提交時間時間運行運行時間時間開始開始時間時間完成時完成時間間周轉(zhuǎn)周轉(zhuǎn)時間時間帶權(quán)帶權(quán)周轉(zhuǎn)周轉(zhuǎn)時間時間1 110.0010.002 22 210.1010.101 13 310.2510.25 0.250.25解：解：作作業(yè)業(yè)提交提交時間時間運行運行時間時

12、間開始開始時間時間完成時完成時間間周轉(zhuǎn)周轉(zhuǎn)時間時間帶權(quán)帶權(quán)周轉(zhuǎn)周轉(zhuǎn)時間時間1 110.0010.002 2101012.0012.002 22/22/22 210.1010.101 1121213.0013.002.92.92.9/12.9/13 310.2510.25 0.250.25131313.2513.253 33/0.253/0.25平均周轉(zhuǎn)時間：T=(2+2.9+3)/3=2.63h平均帶權(quán)周轉(zhuǎn)時間：W=(2+2.9+12)/3=5.3h。 分時系統(tǒng)的重要指標。分時系統(tǒng)的重要指標。 用戶輸入一個請求（如擊鍵）到系統(tǒng)給用戶輸入一個請求（如擊鍵）到系統(tǒng)給出首次響應(yīng)（如屏幕顯示）的時間。

13、出首次響應(yīng)（如屏幕顯示）的時間。 包括：從終端的鍵盤輸入的一個請求信包括：從終端的鍵盤輸入的一個請求信息傳送到處理機的時間；處理機對請求息傳送到處理機的時間；處理機對請求的處理時間；處理結(jié)果送到終端顯示器的處理時間；處理結(jié)果送到終端顯示器的時間。的時間。 響應(yīng)時間響應(yīng)時間 實時系統(tǒng)的重要指標。實時系統(tǒng)的重要指標。 開始截止時間和完成截止時間開始截止時間和完成截止時間 某任務(wù)必須開始執(zhí)行的最遲時間，或必某任務(wù)必須開始執(zhí)行的最遲時間，或必須完成的最遲時間。須完成的最遲時間。截止時間截止時間 批處理、分時、實時系統(tǒng)都可遵循批處理、分時、實時系統(tǒng)都可遵循 可以使關(guān)鍵任務(wù)達到更好的指標?？梢允龟P(guān)鍵任務(wù)達

14、到更好的指標。 公平性：不因作業(yè)或進程本身的特性而公平性：不因作業(yè)或進程本身的特性而使上述指標過分惡化。如長作業(yè)等待很使上述指標過分惡化。如長作業(yè)等待很長時間。長時間。優(yōu)先權(quán)原則優(yōu)先權(quán)原則 吞吐量吞吐量批處理系統(tǒng)的重要指標。批處理系統(tǒng)的重要指標。吞吐量指吞吐量指單位時間內(nèi)所完成的作業(yè)數(shù)，跟作業(yè)本單位時間內(nèi)所完成的作業(yè)數(shù)，跟作業(yè)本身特性和調(diào)度算法都有關(guān)系。身特性和調(diào)度算法都有關(guān)系。 處理機利用率高處理機利用率高大中型主機多用戶系統(tǒng)性能指標，系統(tǒng)價格昂貴。大中型主機多用戶系統(tǒng)性能指標，系統(tǒng)價格昂貴。PCPC一般不考慮這個指標。一般不考慮這個指標。 各種資源的均衡利用各種資源的均衡利用大中型主機多用

15、戶系統(tǒng)性能指標。如大中型主機多用戶系統(tǒng)性能指標。如CPUCPU繁忙的繁忙的作業(yè)和作業(yè)和I/OI/O繁忙（指次數(shù)多，每次時間短）的作繁忙（指次數(shù)多，每次時間短）的作業(yè)搭配。對業(yè)搭配。對PCPC及實時系統(tǒng)該指標并不重要。及實時系統(tǒng)該指標并不重要。面向系統(tǒng)準則面向系統(tǒng)準則 易于實現(xiàn)易于實現(xiàn) 執(zhí)行開銷比執(zhí)行開銷比 調(diào)度算法本身的調(diào)度性能準則調(diào)度算法本身的調(diào)度性能準則3.2 3.2 調(diào)度算法調(diào)度算法 OSOS中調(diào)度的實質(zhì)是一種資源分配，因而中調(diào)度的實質(zhì)是一種資源分配，因而調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。略所規(guī)定的資源分配算法。 有的調(diào)度算法適用

16、于作業(yè)調(diào)度，有的算有的調(diào)度算法適用于作業(yè)調(diào)度，有的算法適用于進程調(diào)度，有的兩者都適應(yīng)。法適用于進程調(diào)度，有的兩者都適應(yīng)。 3.2.1先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法 1. 1. FCFSFCFS算法算法(1) (1) 算法描述算法描述按照作業(yè)提交或進程變?yōu)榫途w狀態(tài)的先后按照作業(yè)提交或進程變?yōu)榫途w狀態(tài)的先后次序，分派次序，分派CPUCPU。當前作業(yè)或進程占用。當前作業(yè)或進程占用CPUCPU，直到執(zhí)行完或阻塞，才出讓直到執(zhí)行完或阻塞，才出讓CPUCPU（非搶占非搶占方式）。方式）。在作業(yè)或進程喚醒后（如在作業(yè)或進程喚醒后（如I/OI/O完成），并完成），并不立即恢復執(zhí)行，而是進入就緒隊列排隊。不立即

17、恢復執(zhí)行，而是進入就緒隊列排隊。最簡單的算法。最簡單的算法。 (2) FCFS(2) FCFS的特點的特點比較有利于長作業(yè)，而不利于短作比較有利于長作業(yè)，而不利于短作業(yè)。業(yè)。有利于有利于CPUCPU繁忙的作業(yè)，而不利于繁忙的作業(yè)，而不利于I/OI/O繁忙的作業(yè)。繁忙的作業(yè)。例：例： 進程進程 到達時間到達時間 執(zhí)行時間執(zhí)行時間P10.0 24 P21.0 3 P32.0 3 Gantt 圖圖: 平均等待時間平均等待時間: (0 + 23 + 25)/3 = 16 平均周轉(zhuǎn)時間：平均周轉(zhuǎn)時間：(24+26+28)/3=26 平均帶權(quán)周轉(zhuǎn)時間：平均帶權(quán)周轉(zhuǎn)時間： (24/24+26/3+28/3)

18、/3=6.33P1P2P32427300 2.2.短作業(yè)（進程）優(yōu)先調(diào)度算法短作業(yè)（進程）優(yōu)先調(diào)度算法(Shortest (Shortest Job/Process FirstJob/Process First，SJF/SPFSJF/SPF） (1) (1) 算法描述算法描述對預計執(zhí)行時間短的作業(yè)（進程）優(yōu)對預計執(zhí)行時間短的作業(yè)（進程）優(yōu)先分派處理機。通常后來的短作業(yè)不先分派處理機。通常后來的短作業(yè)不搶先正在執(zhí)行的作業(yè)。搶先正在執(zhí)行的作業(yè)。是對是對FCFSFCFS算法的改進，其目標是減少算法的改進，其目標是減少平均周轉(zhuǎn)時間。平均周轉(zhuǎn)時間。 (2) SJF(2) SJF的特點的特點優(yōu)點：優(yōu)點：比

19、比FCFSFCFS改善平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)改善平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，縮短作業(yè)的等待時間；時間，縮短作業(yè)的等待時間；提高系統(tǒng)的吞吐量；提高系統(tǒng)的吞吐量； 缺點缺點：對長作業(yè)非常不利，可能長時間得不到執(zhí)對長作業(yè)非常不利，可能長時間得不到執(zhí)行；行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級；先級；難以準確估計作業(yè)（進程）的執(zhí)行時間，難以準確估計作業(yè)（進程）的執(zhí)行時間，從而影響調(diào)度性能。從而影響調(diào)度性能。 進程進程 到達時間到達時間 執(zhí)行時間執(zhí)行時間P10.0 7 P22.0 4 P34.0 1 P45.0 4 非搶先式非搶先式SJF 平均等待時間平均

20、等待時間 = (0 + 6 + 3 + 7)/4 = 4 平均周轉(zhuǎn)時間（平均周轉(zhuǎn)時間（7+10+411）/4=8 平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間=P1P3P273160P4812 3. 3. SJFSJF的變型的變型“最短剩余時間優(yōu)先最短剩余時間優(yōu)先”SRT(Shortest SRT(Shortest Remaining Time)Remaining Time)（允許比當前進程剩允許比當前進程剩余時間更短的進程來搶占）余時間更短的進程來搶占）“最高響應(yīng)比優(yōu)先最高響應(yīng)比優(yōu)先”HRRN(Highest HRRN(Highest Response Ratio Next)Response Ratio

21、 Next)（響應(yīng)比響應(yīng)比R = R = ( (等待時間等待時間 + + 要求執(zhí)行時間要求執(zhí)行時間) / ) / 要求要求執(zhí)行時間，是執(zhí)行時間，是FCFSFCFS和和SJFSJF的折衷）的折衷） 進程進程 到達時間到達時間 執(zhí)行時間執(zhí)行時間P10.0 7 P22.0 4 P34.0 1 P45.0 4 最短剩余時間優(yōu)先（搶先式最短剩余時間優(yōu)先（搶先式SJF） 平均等待時間平均等待時間 = (9 + 1 + 0 +2)/4 = 3 平均周轉(zhuǎn)時間（平均周轉(zhuǎn)時間（16516）/4=7P1P3P242110P457P2P1163.2.2 優(yōu)先權(quán)調(diào)度算法(Priority Scheduling) 本算法

22、適用于作業(yè)調(diào)度和進程調(diào)度。本算法適用于作業(yè)調(diào)度和進程調(diào)度。 算法用于作業(yè)調(diào)度時，系統(tǒng)從后備隊列算法用于作業(yè)調(diào)度時，系統(tǒng)從后備隊列中選擇優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。中選擇優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。 用于進程調(diào)度時，系統(tǒng)把處理機派發(fā)給用于進程調(diào)度時，系統(tǒng)把處理機派發(fā)給就緒隊列中優(yōu)先權(quán)最高的進程。就緒隊列中優(yōu)先權(quán)最高的進程。1. 優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法的類型的類型 可分成可分成搶占式搶占式和和非搶占式非搶占式非搶占式方式：除非自愿或時間片到，非搶占式方式：除非自愿或時間片到，當前的進程不可以被優(yōu)先級更高的進程當前的進程不可以被優(yōu)先級更高的進程搶用搶用CPU。搶占方式：當前的進程在其時間片未用搶占

23、方式：當前的進程在其時間片未用完時就可被優(yōu)先級更高的進程搶用完時就可被優(yōu)先級更高的進程搶用CPU（自己則進入就緒狀態(tài)）。自己則進入就緒狀態(tài)）?？蓳屨汲潭仍礁?，對實時系統(tǒng)的滿足越可搶占程度越高，對實時系統(tǒng)的滿足越好。好。 完全不可搶占或用戶態(tài)不可搶占完全不可搶占或用戶態(tài)不可搶占：無論在用戶：無論在用戶態(tài)或核心態(tài)下執(zhí)行代碼，都不可被搶用態(tài)或核心態(tài)下執(zhí)行代碼，都不可被搶用CPU。WINDOWS95,98。這種這種OS可能會出現(xiàn)某個進可能會出現(xiàn)某個進程長期獨占程長期獨占CPU的情況，如死循環(huán)，這樣會影的情況，如死循環(huán)，這樣會影響其他進程執(zhí)行的公平和及時。響其他進程執(zhí)行的公平和及時。 內(nèi)核完全不可搶占內(nèi)

24、核完全不可搶占：在用戶態(tài)下執(zhí)行代碼可以：在用戶態(tài)下執(zhí)行代碼可以隨時被搶用隨時被搶用CPU，但在核心態(tài)下執(zhí)行代碼，則但在核心態(tài)下執(zhí)行代碼，則完全不可以被搶用完全不可以被搶用CPU。例如傳統(tǒng)的例如傳統(tǒng)的UNIX（SVR3和和4.3BSD UNIX及其以前的版本）、及其以前的版本）、WINDOWS NT。這些這些OS通常在系統(tǒng)調(diào)用或通常在系統(tǒng)調(diào)用或中斷處理時屏蔽大部分中斷，系統(tǒng)調(diào)用返回或中斷處理時屏蔽大部分中斷，系統(tǒng)調(diào)用返回或中斷返回時再開放大部分中斷。中斷返回時再開放大部分中斷。 內(nèi)核部分可搶占內(nèi)核部分可搶占：在用戶態(tài)下執(zhí)行代碼可以隨：在用戶態(tài)下執(zhí)行代碼可以隨時被搶用時被搶用CPU，但在核心態(tài)時則

25、大部分時間都但在核心態(tài)時則大部分時間都不可以被搶用不可以被搶用CPU，而只在某些時刻（稱為可而只在某些時刻（稱為可搶占點，搶占點，Preemption Point），），可以被搶用可以被搶用CPU。例如例如 UNIX SVR4。 完全可搶占或內(nèi)核完全可搶占完全可搶占或內(nèi)核完全可搶占：無論處于用戶：無論處于用戶態(tài)還是核心態(tài)，都可以隨時被搶用態(tài)還是核心態(tài)，都可以隨時被搶用CPU 。例例如：如：Solaris 、Windows 2000 / XP。實際實際上，上，Solaris和和Windows 2000 / XP并不是并不是100%完全可搶先，它只是將內(nèi)核中不可搶先完全可搶先，它只是將內(nèi)核中不可搶

26、先的代碼段盡量減少而已。任何的代碼段盡量減少而已。任何OS都不可能是都不可能是100%的完全可搶先的。的完全可搶先的。 例題：在單例題：在單CPU和兩臺和兩臺I/O（I1,I2)設(shè)備的多道設(shè)備的多道程序環(huán)境下，同時投入三個作業(yè)運行，它們的執(zhí)程序環(huán)境下，同時投入三個作業(yè)運行，它們的執(zhí)行軌跡如下：行軌跡如下： Job1: I2(30ms) CPU(10ms) I1 (30ms) CPU (10ms) Job2: I1 (20ms) CPU(20ms) I2(40ms) Job3: CPU(30ms) I1(20ms) 如果如果CPU、I1、I2都能并行工作，優(yōu)先級從高都能并行工作，優(yōu)先級從高到低為

27、到低為Job1、Job2、Job3，采用可搶占式優(yōu)，采用可搶占式優(yōu)先級調(diào)度方式。先級調(diào)度方式。 求求(1) 每個作業(yè)的周轉(zhuǎn)時間每個作業(yè)的周轉(zhuǎn)時間(2) CPU的利用率的利用率(3) I/O設(shè)備利用率設(shè)備利用率Job1的周轉(zhuǎn)時間的周轉(zhuǎn)時間80ms，Job2 和和Job3周轉(zhuǎn)時間各為周轉(zhuǎn)時間各為90msCPU利用率利用率 70ms/90ms = 77.78%I1 利用率利用率 I2利用率利用率 = 70ms /90ms 77.78%0ms102030405060708090時間時間CPUJob3Job2Job1 Job2 Job3Job1I1Job2Job1Job3I2Job1Job22.2.優(yōu)先

28、權(quán)的類型優(yōu)先權(quán)的類型 1 1）靜態(tài)優(yōu)先級）靜態(tài)優(yōu)先級 創(chuàng)建進程時就確定，直到進程終止前都不改創(chuàng)建進程時就確定，直到進程終止前都不改變。通常是一個整數(shù)。變。通常是一個整數(shù)。 依據(jù)依據(jù)：進程類型（系統(tǒng)進程優(yōu)先級較高）進程類型（系統(tǒng)進程優(yōu)先級較高）對資源的需求（對對資源的需求（對CPUCPU和內(nèi)存需求較少的和內(nèi)存需求較少的進程，優(yōu)先級較高）進程，優(yōu)先級較高）用戶要求（緊迫程度和付費多少）用戶要求（緊迫程度和付費多少） 特點特點：簡單，系統(tǒng)開銷小簡單，系統(tǒng)開銷小不精確，僅在要求不高的系統(tǒng)中使用不精確，僅在要求不高的系統(tǒng)中使用 2) 動態(tài)優(yōu)先級動態(tài)優(yōu)先級在創(chuàng)建進程時賦予的優(yōu)先級，在進程在創(chuàng)建進程時賦予的

29、優(yōu)先級，在進程運行過程中可以自動改變，以便獲得運行過程中可以自動改變，以便獲得更好的調(diào)度性能。更好的調(diào)度性能。如：如：在就緒隊列中，等待時間延長則優(yōu)在就緒隊列中，等待時間延長則優(yōu)先級提高，從而使優(yōu)先級較低的進先級提高，從而使優(yōu)先級較低的進程在等待足夠的時間后，其優(yōu)先級程在等待足夠的時間后，其優(yōu)先級提高到可被調(diào)度執(zhí)行；提高到可被調(diào)度執(zhí)行；進程每執(zhí)行一個時間片，就降低其進程每執(zhí)行一個時間片，就降低其優(yōu)先級，從而一個進程持續(xù)執(zhí)行時，優(yōu)先級，從而一個進程持續(xù)執(zhí)行時，其優(yōu)先級降低到出讓其優(yōu)先級降低到出讓CPUCPU。 響應(yīng)比響應(yīng)比R R = (= (等待時間等待時間 + + 要求執(zhí)行時間要求執(zhí)行時間)

30、/ ) / 要求執(zhí)行時間要求執(zhí)行時間1 1等待時間等待時間/ /要求執(zhí)行時間要求執(zhí)行時間 是是FCFSFCFS和和SJFSJF的折衷：的折衷：作業(yè)等待時間相同，服務(wù)時間越短，優(yōu)先權(quán)越作業(yè)等待時間相同，服務(wù)時間越短，優(yōu)先權(quán)越高高-SJFSJF；要求服務(wù)時間相同，等待時間越長，優(yōu)先權(quán)越要求服務(wù)時間相同，等待時間越長，優(yōu)先權(quán)越高高-FCFSFCFS；長作業(yè)隨著等待時間的增加，優(yōu)先長作業(yè)隨著等待時間的增加，優(yōu)先權(quán)增加。權(quán)增加。 缺點：缺點： 響應(yīng)比的計算增加系統(tǒng)開銷響應(yīng)比的計算增加系統(tǒng)開銷3.高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 (Highest Response Ratio Next，HRRN，

31、HRN) 例：如表所示四個作業(yè)進入系統(tǒng)，分別計算例：如表所示四個作業(yè)進入系統(tǒng)，分別計算HRRN算法下的平均周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間。算法下的平均周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間。作業(yè)作業(yè)提交時間（時）提交時間（時）運行時間（分）運行時間（分）12348:008:509:009:50120501020作業(yè)作業(yè)開始時間開始時間完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間12348:0010:1010:0011:0010:0011:0010:1011:201201307090Job1完成后的響應(yīng)比：完成后的響應(yīng)比：Job2: 70/50=1.4 Job3: 60/10=6Job4: 10/20=0.5所以調(diào)度所以調(diào)度Job

32、3執(zhí)行。執(zhí)行。Job3完成后的響應(yīng)比：完成后的響應(yīng)比：Job2: 80/50=1.8Job4: 20/20=1所以調(diào)度所以調(diào)度Job2執(zhí)行執(zhí)行 平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間102.5 帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間W= T(周轉(zhuǎn)周轉(zhuǎn))/ (CPU執(zhí)行執(zhí)行) 平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間 (120/120 + 130/50 + 70/10 + 90/20) /4=3.775 例：滿足短作業(yè)優(yōu)先且不會發(fā)生饑餓現(xiàn)例：滿足短作業(yè)優(yōu)先且不會發(fā)生饑餓現(xiàn)象的調(diào)度算法是：象的調(diào)度算法是： A FCFS B 高響應(yīng)比優(yōu)先高響應(yīng)比優(yōu)先 C 時間片輪轉(zhuǎn)時間片輪轉(zhuǎn) D 非搶先式非搶先式SJF3.2.3 基于時間片的輪轉(zhuǎn)調(diào)度

33、算法 1.1.時間片輪轉(zhuǎn)法（時間片輪轉(zhuǎn)法（Round Robin, RR)Round Robin, RR)本算法主要用于微觀調(diào)度（進程調(diào)度）本算法主要用于微觀調(diào)度（進程調(diào)度）設(shè)計目標是提高資源利用率設(shè)計目標是提高資源利用率基本思路是通過時間片輪轉(zhuǎn)，提高進程基本思路是通過時間片輪轉(zhuǎn)，提高進程并發(fā)性和響應(yīng)時間特性，從而提高資源并發(fā)性和響應(yīng)時間特性，從而提高資源利用率利用率 時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法 (1)(1)算法描述算法描述 將將系統(tǒng)中所有的就緒進程按照系統(tǒng)中所有的就緒進程按照FCFSFCFS原則，排原則，排成一個隊列。成一個隊列。每次調(diào)度時將每次調(diào)度時將CPUCPU分派給隊首進程，讓其執(zhí)分派給

34、隊首進程，讓其執(zhí)行一個時間片。在一個時間片結(jié)束時，發(fā)生行一個時間片。在一個時間片結(jié)束時，發(fā)生時鐘中斷。調(diào)度程序據(jù)此暫停當前進程的執(zhí)時鐘中斷。調(diào)度程序據(jù)此暫停當前進程的執(zhí)行，將其送到就緒隊列的末尾，并通過上下行，將其送到就緒隊列的末尾，并通過上下文切換執(zhí)行當前的隊首進程。文切換執(zhí)行當前的隊首進程。時間片的長度從幾個時間片的長度從幾個msms到幾百到幾百msms。進程可以未使用完一個時間片，就出讓進程可以未使用完一個時間片，就出讓CPUCPU（如阻塞）。如阻塞）。時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法 (2) (2) 時間片長度的確定時間片長度的確定時間片長度變化的影響時間片長度變化的影響過長過長 退化為退化為

35、FCFSFCFS算法算法過短過短 用戶的一次請求需要多個時間片用戶的一次請求需要多個時間片才能處理完，上下文切換次數(shù)增加，響應(yīng)才能處理完，上下文切換次數(shù)增加，響應(yīng)時間長。時間長。 就緒進程的數(shù)目：數(shù)目越多，時間片越小就緒進程的數(shù)目：數(shù)目越多，時間片越小系統(tǒng)的處理能力：應(yīng)當使用戶輸入通常在一系統(tǒng)的處理能力：應(yīng)當使用戶輸入通常在一個時間片內(nèi)能處理完，否則使響應(yīng)時間，平個時間片內(nèi)能處理完，否則使響應(yīng)時間，平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間延長。均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間延長。 例：降低進程優(yōu)先級的合理時機是例：降低進程優(yōu)先級的合理時機是A 進程的時間片用完進程的時間片用完B 進程剛完成進程剛完成IO，

36、進入就緒隊列，進入就緒隊列C 進程長期處于就緒隊列中進程長期處于就緒隊列中D 進程從就緒態(tài)轉(zhuǎn)為運行態(tài)進程從就緒態(tài)轉(zhuǎn)為運行態(tài)輪轉(zhuǎn)調(diào)度算法（時間片輪轉(zhuǎn)調(diào)度算法（時間片20） 進程進程 執(zhí)行時間執(zhí)行時間P153 P2 17 P368 P4 24 The Gantt chart is: P1P2P3P4P1P3P4P1P3P302037577797117121134154162進程進程 到達時間到達時間 執(zhí)行時間執(zhí)行時間P1 0 3 P2 1 6 P3 4 4 P4 6 2時間片時間片 = 2 P1P2P3P4P1P2P3P2 2 4 6 8 9 11 13 15作業(yè)作業(yè)進程進程 到達時間到達時間 執(zhí)

37、行時間執(zhí)行時間 P1 0 10 P2 1 8 P3 2 2 P4 3 4 P5 4 8 畫畫Gantt圖說明使用圖說明使用FCFS、非搶先式、非搶先式SJF、搶、搶先式先式SJF、RR（時間片（時間片3）調(diào)度算法進程調(diào)）調(diào)度算法進程調(diào)度情況。并分別求四種算法的平均周轉(zhuǎn)時間，度情況。并分別求四種算法的平均周轉(zhuǎn)時間，平均等待時間。平均等待時間。 例：假設(shè)某操作系統(tǒng)采用時間片輪轉(zhuǎn)調(diào)例：假設(shè)某操作系統(tǒng)采用時間片輪轉(zhuǎn)調(diào)度策略，時間片大小為度策略，時間片大小為100ms，就緒進，就緒進程隊列的平均長度為程隊列的平均長度為5，如果在系統(tǒng)中運，如果在系統(tǒng)中運行一個需要在行一個需要在CPU上執(zhí)行上執(zhí)行0.8s時

38、間的程時間的程序，則該程序的平均周轉(zhuǎn)時間是序，則該程序的平均周轉(zhuǎn)時間是 ,平平均等待時間是均等待時間是 。（不考慮。（不考慮IO情況及情況及系統(tǒng)調(diào)度開銷）系統(tǒng)調(diào)度開銷）答：答： 排在隊列尾的周轉(zhuǎn)時間排在隊列尾的周轉(zhuǎn)時間4s，排在，排在隊列第四的周轉(zhuǎn)時間隊列第四的周轉(zhuǎn)時間3.9s排在頭排在頭的周轉(zhuǎn)時間的周轉(zhuǎn)時間3.6s，平均：，平均：3.8s同理：平均等待同理：平均等待 3.0s 2.2.多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法( (Round Robin Round Robin with Multiple Feedback)with Multiple Feedback) 多級反饋隊列算法是時間

39、片輪轉(zhuǎn)算法和多級反饋隊列算法是時間片輪轉(zhuǎn)算法和優(yōu)先級算法的綜合和發(fā)展。優(yōu)先級算法的綜合和發(fā)展。1) 1) 算法描述算法描述設(shè)置多個就緒隊列，分別賦予不同的優(yōu)設(shè)置多個就緒隊列，分別賦予不同的優(yōu)先級，隊列先級，隊列1 1的優(yōu)先級最高。每個隊列的優(yōu)先級最高。每個隊列執(zhí)行時間片的長度也不同，規(guī)定優(yōu)先級執(zhí)行時間片的長度也不同，規(guī)定優(yōu)先級越低則時間片越長。越低則時間片越長。 假設(shè)有三個就緒隊列：假設(shè)有三個就緒隊列：Q1Q1時間片為時間片為8 8Q2Q2時間片為時間片為1616Q3Q3FCFSFCFS 新進程進入內(nèi)存后，先投入隊列新進程進入內(nèi)存后，先投入隊列1 1的末尾，若的末尾，若按隊列按隊列1 1一個時

40、間片未能執(zhí)行完，則降低投入一個時間片未能執(zhí)行完，則降低投入到隊列到隊列2 2的末尾，若仍未完成，降低到最后的的末尾，若仍未完成，降低到最后的隊列，按隊列，按FCFSFCFS算法調(diào)度直到完成。算法調(diào)度直到完成。 僅當較高優(yōu)先級的隊列為空，才調(diào)度較低優(yōu)先僅當較高優(yōu)先級的隊列為空，才調(diào)度較低優(yōu)先級的隊列中的進程執(zhí)行。如果進程執(zhí)行時有新級的隊列中的進程執(zhí)行。如果進程執(zhí)行時有新進程進入較高優(yōu)先級的隊列，則搶先執(zhí)行新進進程進入較高優(yōu)先級的隊列，則搶先執(zhí)行新進程，并把被搶先的進程投入原隊列的末尾。程，并把被搶先的進程投入原隊列的末尾。多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法 2 2）算法性能）算法性能終端型

41、進程：讓其進入最高優(yōu)先級隊列，終端型進程：讓其進入最高優(yōu)先級隊列，以及時響應(yīng)以及時響應(yīng)I/OI/O交互。通常執(zhí)行一個小時交互。通常執(zhí)行一個小時間片，可處理完一次間片，可處理完一次I/OI/O請求的數(shù)據(jù)，然請求的數(shù)據(jù)，然后轉(zhuǎn)入到阻塞隊列。后轉(zhuǎn)入到阻塞隊列。計算型進程（長批處理作業(yè)）：每次都執(zhí)計算型進程（長批處理作業(yè)）：每次都執(zhí)行完時間片，進入更低級隊列。最終采用行完時間片，進入更低級隊列。最終采用最大時間片來執(zhí)行，減少調(diào)度次數(shù)。最大時間片來執(zhí)行，減少調(diào)度次數(shù)。短批處理作業(yè)：短批處理作業(yè)： 先放入第先放入第1 1級，一般經(jīng)級，一般經(jīng)過過1 1，2 2級即可完成。級即可完成。多級反饋隊列調(diào)度算法多級

42、反饋隊列調(diào)度算法 3）優(yōu)點：優(yōu)點：為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時間而照顧短進程間而照顧短進程為獲得較好的為獲得較好的I/OI/O設(shè)備利用率和縮短設(shè)備利用率和縮短響應(yīng)時間而照顧響應(yīng)時間而照顧I/OI/O型進程型進程不必估計進程的執(zhí)行時間，動態(tài)調(diào)節(jié)不必估計進程的執(zhí)行時間，動態(tài)調(diào)節(jié)多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法3.4 實時調(diào)度實時調(diào)度3.4.1 3.4.1 實現(xiàn)實時調(diào)度的基本條件實現(xiàn)實時調(diào)度的基本條件 1. 提供必要的信息提供必要的信息系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的下系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的下述信息：述信息：（1）就緒時間：該任務(wù)成為就緒狀）就緒時間

43、：該任務(wù)成為就緒狀態(tài)的起始時間。態(tài)的起始時間。（2）開始截止時間和完成截止時間）開始截止時間和完成截止時間（3）處理時間）處理時間（4）資源要求）資源要求 （5）優(yōu)先級）優(yōu)先級 2. 系統(tǒng)處理能力強系統(tǒng)處理能力強 設(shè)有設(shè)有m個周期性硬實時任務(wù)，處理時間為個周期性硬實時任務(wù)，處理時間為Ci，周期時間為周期時間為Pi，在單處理機環(huán)境下滿足：，在單處理機環(huán)境下滿足： 若采用多處理機系統(tǒng)，設(shè)系統(tǒng)中處理機數(shù)目若采用多處理機系統(tǒng)，設(shè)系統(tǒng)中處理機數(shù)目為為N，則應(yīng)滿足，則應(yīng)滿足11miiiPCNPCmiii 1 3. 采用搶占式調(diào)度機制采用搶占式調(diào)度機制 4. 具有快速切換機制具有快速切換機制（1）對外部中斷

44、的快速響應(yīng)能力）對外部中斷的快速響應(yīng)能力 具有快速硬件中斷機構(gòu)，且禁止中具有快速硬件中斷機構(gòu)，且禁止中斷的時間間隔盡量短。斷的時間間隔盡量短。（2）快速任務(wù)分派能力）快速任務(wù)分派能力為提高任務(wù)切換的速度，系統(tǒng)中每為提高任務(wù)切換的速度，系統(tǒng)中每個運行單位要適當?shù)匦?。個運行單位要適當?shù)匦　?.4.2 實時調(diào)度算法的分類實時調(diào)度算法的分類 1. 非搶占式調(diào)度算法非搶占式調(diào)度算法1）非搶占式輪轉(zhuǎn)調(diào)度算法）非搶占式輪轉(zhuǎn)調(diào)度算法該算法用于工業(yè)生成的群控系統(tǒng)中，該算法用于工業(yè)生成的群控系統(tǒng)中，同于前面的同于前面的RR算法。算法。2）非搶占式優(yōu)先調(diào)度算法）非搶占式優(yōu)先調(diào)度算法在實時系統(tǒng)中給要求嚴格的任務(wù)賦在實

45、時系統(tǒng)中給要求嚴格的任務(wù)賦予高優(yōu)先級，置于隊首，當前任務(wù)予高優(yōu)先級，置于隊首，當前任務(wù)自我終止或運行完才能被調(diào)度執(zhí)行。自我終止或運行完才能被調(diào)度執(zhí)行。 2. 搶占式調(diào)度算法搶占式調(diào)度算法 1） 基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法在某實時任務(wù)到達后，若其優(yōu)先級高于占在某實時任務(wù)到達后，若其優(yōu)先級高于占有處理機的進程優(yōu)先級，并不搶占，等到有處理機的進程優(yōu)先級，并不搶占，等到時鐘中斷到達時再搶占。時鐘中斷到達時再搶占。調(diào)度延遲可降為幾十至幾毫秒。調(diào)度延遲可降為幾十至幾毫秒。 2）立即搶占）立即搶占操作系統(tǒng)具有快速響應(yīng)外部中斷的能力。操作系統(tǒng)具有快速響應(yīng)外部中斷的能力

46、。一旦出現(xiàn)外部中斷，只要當前進程未處于一旦出現(xiàn)外部中斷，只要當前進程未處于臨界區(qū)，立即搶占臨界區(qū)，立即搶占CPU。進程1進程2進程n實時進程實時進程實時進程要求調(diào)度實時進程要求調(diào)度實時進程運行實時進程運行調(diào)度時間調(diào)度時間非搶占輪轉(zhuǎn)調(diào)度算法非搶占輪轉(zhuǎn)調(diào)度算法 當前進程實時進程實時進程實時進程要求調(diào)度實時進程要求調(diào)度當前進程完成當前進程完成調(diào)度時間調(diào)度時間非搶占優(yōu)先權(quán)調(diào)度算法非搶占優(yōu)先權(quán)調(diào)度算法 當前進程實時進程實時進程實時進程要求調(diào)度實時進程要求調(diào)度時鐘中斷到來時鐘中斷到來調(diào)度時間調(diào)度時間基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法 當前進程實時進程實時進程實時進程要求調(diào)

47、度實時進程要求調(diào)度搶占并立即執(zhí)行搶占并立即執(zhí)行調(diào)度時間調(diào)度時間立即搶占的優(yōu)先權(quán)調(diào)度算法立即搶占的優(yōu)先權(quán)調(diào)度算法3.4.3 常用的幾種實時調(diào)度算法常用的幾種實時調(diào)度算法 1. 最早截止時間優(yōu)先最早截止時間優(yōu)先 EDF（Earliest Deadline First）根據(jù)任務(wù)的開始截止時間確定任務(wù)的根據(jù)任務(wù)的開始截止時間確定任務(wù)的優(yōu)先級。具有最早截止時間的任務(wù)排優(yōu)先級。具有最早截止時間的任務(wù)排在隊列的最前面。在隊列的最前面。即可用于搶占式調(diào)度，又可用于非搶即可用于搶占式調(diào)度，又可用于非搶占式調(diào)度。占式調(diào)度。 1）非搶占式調(diào)度方式用于非周期實時任）非搶占式調(diào)度方式用于非周期實時任務(wù)務(wù) 1 3 4 2

48、開始截止時間開始截止時間任務(wù)執(zhí)行任務(wù)執(zhí)行任務(wù)到達任務(wù)到達12 341234 2） 搶占式調(diào)度方式用于周期實時任務(wù)搶占式調(diào)度方式用于周期實時任務(wù)A1A2B1B1A3B2A4B2A5B2固定優(yōu)先級調(diào)度固定優(yōu)先級調(diào)度A優(yōu)先級高優(yōu)先級高102030405060708090100A1最后期限最后期限B1A1A2B2A3A2最后期限最后期限A4A3最后期限最后期限A5A4最后期限最后期限A5最后期限最后期限B1最后期限最后期限B2最后期限最后期限0B1A2A3B2A5固定優(yōu)先級調(diào)度固定優(yōu)先級調(diào)度B優(yōu)先級高優(yōu)先級高B1錯過錯過A1錯過錯過A4錯過錯過A1B1A2B1A3B2A4B2A5搶占式搶占式EDF 2

49、. 最低松弛度優(yōu)先最低松弛度優(yōu)先LLF（Least Laxity First）算法算法 任務(wù)的緊急程度愈高，該任務(wù)的優(yōu)先級愈高。任務(wù)的緊急程度愈高，該任務(wù)的優(yōu)先級愈高。 松弛度松弛度 = 必須完成時間必須完成時間-本身運行時間本身運行時間-當當前時間前時間 如，如，t=0時，某任務(wù)在時，某任務(wù)在200ms時必須完成，時必須完成，他本身執(zhí)行的時間是他本身執(zhí)行的時間是100ms，則其松弛度，則其松弛度為為100ms。 LLF算法按松弛度排就緒隊列，松弛度最低算法按松弛度排就緒隊列，松弛度最低的排在隊列最前面，優(yōu)先被調(diào)度執(zhí)行。的排在隊列最前面，優(yōu)先被調(diào)度執(zhí)行。 LLF主要用于可搶占調(diào)度方式中。主要用

50、于可搶占調(diào)度方式中。t1A1(10)A2(10)A3(10)A4(10)B1(20)B1(5)B2(15)B2(10)01020304050607080LLF調(diào)度調(diào)度102030405060708090100A1最后期限最后期限B1A1A2B2A3A2最后期限最后期限A4A3最后期限最后期限A5A4最后期限最后期限A5最后期限最后期限B1最后期限最后期限B2最后期限最后期限03.5 產(chǎn)生死鎖的原因和必要條件 死鎖死鎖：指多個進程因競爭共享資源而造：指多個進程因競爭共享資源而造成的一種僵局，若無外力作用，這些進成的一種僵局，若無外力作用，這些進程永遠不能向前推進。程永遠不能向前推進。 3.5.1

51、 產(chǎn)生死鎖的原因 競爭資源競爭資源資源數(shù)目不能滿足進程需要資源數(shù)目不能滿足進程需要 順序不當順序不當進程運行過程中，請求和釋放資源順進程運行過程中，請求和釋放資源順序不當序不當1 1 競爭資源引起死鎖競爭資源引起死鎖 可剝奪和不可剝奪資源可剝奪和不可剝奪資源可剝奪的如：處理機、內(nèi)存（優(yōu)先權(quán)可剝奪的如：處理機、內(nèi)存（優(yōu)先權(quán)高的剝奪優(yōu)先權(quán)低的）高的剝奪優(yōu)先權(quán)低的）不可剝奪資源如：磁帶、打印機不可剝奪資源如：磁帶、打印機 競爭不可剝奪資源可能會引起死鎖競爭不可剝奪資源可能會引起死鎖 死鎖發(fā)生：雙方都擁有部分資源，同時在請求死鎖發(fā)生：雙方都擁有部分資源，同時在請求對方已占有的資源。對方已占有的資源。

52、. Request(B); Request(A); Release(A); Release(B);P2. Request(A); Request(B); Release(B); Release(A);P11 1 競爭資源引起死鎖競爭資源引起死鎖 競爭臨時性資源可能會引起死鎖競爭臨時性資源可能會引起死鎖可以動態(tài)生成和消耗，一般不限制數(shù)可以動態(tài)生成和消耗，一般不限制數(shù)量。如硬件中斷、信號、消息、緩沖量。如硬件中斷、信號、消息、緩沖區(qū)內(nèi)的數(shù)據(jù)。區(qū)內(nèi)的數(shù)據(jù)。 . Receive(P1,Q); Send(P1,R);P2. Receive(P2,M); Send(P2,N);P11 1 競爭資源引起死鎖

53、競爭資源引起死鎖 多個進程并發(fā)執(zhí)行，相互的推進順序不多個進程并發(fā)執(zhí)行，相互的推進順序不確定，可能會導致兩種結(jié)果：不出現(xiàn)死確定，可能會導致兩種結(jié)果：不出現(xiàn)死鎖和出現(xiàn)死鎖。鎖和出現(xiàn)死鎖。 2 2 進程推進順序不當引起死鎖進程推進順序不當引起死鎖3.5.2 產(chǎn)生死鎖的必要條件 只有只有4 4個條件個條件都滿足都滿足時，才會出現(xiàn)死鎖。時，才會出現(xiàn)死鎖。 互斥互斥：任一時刻只允許一個進程使用資源：任一時刻只允許一個進程使用資源 請求和保持請求和保持：進程保持了至少一個資源，但：進程保持了至少一個資源，但又提出了新的資源請求，該資源又被其他進又提出了新的資源請求，該資源又被其他進程占用。程占用。 不剝奪不

54、剝奪：進程已經(jīng)占用的資源，未使用完，：進程已經(jīng)占用的資源，未使用完，不能被剝奪。不能被剝奪。 環(huán)路等待環(huán)路等待：存在進程資源環(huán)形鏈，即有進：存在進程資源環(huán)形鏈，即有進程集合程集合P0, P1, P2,P0, P1, P2,.Pn,P0.Pn,P0等待等待P1P1占用的占用的資源，資源，P1P1等待等待P2P2占用的資源占用的資源.PnPn等待等待P0P0占占用的資源。用的資源。 3.5.3 處理死鎖的方法 1. 1. 預防死鎖預防死鎖加限制條件，破壞產(chǎn)生死鎖加限制條件，破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個。的四個必要條件中的一個或幾個。2. 2. 避免死鎖避免死鎖在資源的動態(tài)分配過程中，在

55、資源的動態(tài)分配過程中，防止系統(tǒng)進入不安全狀態(tài)。防止系統(tǒng)進入不安全狀態(tài)。3. 3. 檢測死鎖允許系統(tǒng)進入死鎖，但系統(tǒng)檢測死鎖允許系統(tǒng)進入死鎖，但系統(tǒng)及時檢測，并采取措施。及時檢測，并采取措施。4. 4. 解除死鎖當檢測到系統(tǒng)進入了死鎖，解除死鎖當檢測到系統(tǒng)進入了死鎖，采取措施解除。采取措施解除。3.6 預防和避免死鎖的方法 死鎖的預防 采用某種策略，限制并發(fā)進程對資源的請求，使系統(tǒng)在任何時刻都不滿足死鎖的四個必要條件 一一. 摒棄摒棄“請求保持請求保持”條件（針對死鎖的條件（針對死鎖的第第2個條件）個條件）預先靜態(tài)分配法：預先分配進程運行預先靜態(tài)分配法：預先分配進程運行所需的全部資源，保證不等待

56、資源所需的全部資源，保證不等待資源優(yōu)點：簡單優(yōu)點：簡單 、易于實現(xiàn)、安全、易于實現(xiàn)、安全缺點：缺點：資源被嚴重浪費，降低了對資源的資源被嚴重浪費，降低了對資源的利用率，降低進程的并發(fā)程度；利用率，降低進程的并發(fā)程度；有可能無法預先知道所需資源有可能無法預先知道所需資源3.6.1 預防死鎖預防死鎖 二、摒棄二、摒棄“不可剝奪不可剝奪”條件條件當一個已經(jīng)保持了某些資源的進程，當一個已經(jīng)保持了某些資源的進程，再提出新的資源請求而不能立即得到再提出新的資源請求而不能立即得到滿足時，必須釋放它已持有的資源。滿足時，必須釋放它已持有的資源。缺點缺點：實現(xiàn)較復雜，需付出代價。實現(xiàn)較復雜，需付出代價。反復申請

57、釋放資源，降低系統(tǒng)吞吐反復申請釋放資源，降低系統(tǒng)吞吐率。率。3.6.1 預防死鎖預防死鎖3.6.1 預防死鎖預防死鎖 三、摒棄三、摒棄“環(huán)路等待環(huán)路等待”條件條件有序資源使用法：把資源分類按順序有序資源使用法：把資源分類按順序排列，所有進程排列，所有進程 對資源的請求必須按對資源的請求必須按照資源序號遞增次序提出。保證不形照資源序號遞增次序提出。保證不形成環(huán)路；成環(huán)路；缺點缺點：資源序號固定，限制新設(shè)備的增加；資源序號固定，限制新設(shè)備的增加；降低資源利用率；降低資源利用率；限制了用戶簡單、自主地編程。限制了用戶簡單、自主地編程。 3.6.2 系統(tǒng)的安全狀態(tài) 安全狀態(tài)安全狀態(tài)是指系統(tǒng)能按某種進程

58、順序（是指系統(tǒng)能按某種進程順序（P1, P2, .Pn），為進程），為進程Pi分配其所需資分配其所需資源，直至進程的最大需求，使每個進源，直至進程的最大需求，使每個進程都可順利完成。程都可順利完成。 則（則（P1, P2, .Pn）稱為稱為安全序列安全序列。若系統(tǒng)無法找到安全序列，則稱系統(tǒng)若系統(tǒng)無法找到安全序列，則稱系統(tǒng)處于處于不安全狀態(tài)。不安全狀態(tài)。 安全狀態(tài)之例安全狀態(tài)之例設(shè)系統(tǒng)共有設(shè)系統(tǒng)共有12臺磁帶機，臺磁帶機，T0時刻系統(tǒng)時刻系統(tǒng)狀態(tài)如下：狀態(tài)如下： 進程進程最大需求最大需求已分配已分配可用可用P11053P242 P392 安全序列：安全序列：P2,P1,P3P2,P1,P3，當前

59、系統(tǒng)為安全狀態(tài)，當前系統(tǒng)為安全狀態(tài) 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換若不按照安全序列分配資源，系統(tǒng)可若不按照安全序列分配資源，系統(tǒng)可能會由安全狀態(tài)進入不安全狀態(tài)。能會由安全狀態(tài)進入不安全狀態(tài)。例：例：T0時刻后，時刻后，P3請求請求1臺磁帶機，臺磁帶機，系統(tǒng)分配給它，則進入不安全狀態(tài)。系統(tǒng)分配給它，則進入不安全狀態(tài)。進程進程最大需求最大需求已分配已分配可用可用P11053（2）P242 P392（3） 安全、不安全、死鎖狀態(tài)的關(guān)系安全、不安全、死鎖狀態(tài)的關(guān)系 3.6.3 避免死鎖-銀行家算法 銀行家算法銀行家算法（DijkstraDijkstra, 1965, 1965

60、）問題問題在銀行中，客戶申請貸款的數(shù)量是有限在銀行中，客戶申請貸款的數(shù)量是有限的。銀行家應(yīng)盡量滿足所有客戶的貸款的。銀行家應(yīng)盡量滿足所有客戶的貸款需求。需求。銀行家就好比操作系統(tǒng)，資金就是資源，銀行家就好比操作系統(tǒng)，資金就是資源，客戶就相當于要申請資源的進程?？蛻艟拖喈斢谝暾堎Y源的進程。3.6.3 避免死鎖-銀行家算法 為保證資金的安全，銀行家規(guī)定：為保證資金的安全，銀行家規(guī)定： 當一個顧客對資金的最大需求量不超過銀行當一個顧客對資金的最大需求量不超過銀行家現(xiàn)有的資金時就可接納該顧客家現(xiàn)有的資金時就可接納該顧客(試探性分配試探性分配) 顧客可以分期貸款，但貸款的總數(shù)不能超過顧客可以分期貸款，