操作系統(tǒng)第3章(2)(第四版)

3.4實

時

調(diào)

度

一、實現(xiàn)實時調(diào)度的基本條件提供必要的信息；

就緒時間、截止時間、處理時間、資源要求、優(yōu)先級；系統(tǒng)處理能力強；

對單處理機：

m個周期性硬實時任務(wù)；處理時間：Ci；周期時間：Pi

滿足：采用搶占式調(diào)度機制；具有快速切換機制：對外部中斷的快速響應(yīng)能力。(具有快速硬件中斷機構(gòu))

快速的任務(wù)分派能力。（快速任務(wù)切換，減少任務(wù)切換時間）

二、實時調(diào)度算法的分類（調(diào)度方式的不同）1．非搶占式調(diào)度算法----適用：不太嚴格，小型實時系統(tǒng)1)非搶占式輪轉(zhuǎn)調(diào)度算法適用：工業(yè)生產(chǎn)的群控系統(tǒng)，不太嚴格實時系統(tǒng)；響應(yīng)：數(shù)秒~數(shù)十秒計算機對象實時任務(wù)輪轉(zhuǎn)2)非搶占式優(yōu)先調(diào)度算法適用：較嚴格實時系統(tǒng)；響應(yīng)：數(shù)百毫秒調(diào)用就緒隊列新任務(wù)插入隊首當前任務(wù)CPU完成或終止被調(diào)用優(yōu)先級高2．搶占式調(diào)度算法-適用：較嚴格實時系統(tǒng)基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法適用：大多數(shù)實時系統(tǒng)；響應(yīng)：幾十毫秒~幾毫秒新任務(wù)當前任務(wù)CPU產(chǎn)生時鐘中斷搶占優(yōu)先級高等待時鐘中斷2)立即搶占(ImmediatePreemption)的優(yōu)先權(quán)調(diào)度算法適用：大多數(shù)實時系統(tǒng)；響應(yīng)：幾毫秒~100微秒只要當前任務(wù)未處于臨界區(qū)，便立即剝奪當前任務(wù)的執(zhí)行。三、常用的幾種實時調(diào)度算法1．最早截止時間優(yōu)先即EDF(EarliestDeadlineFirst)算法

算法：根據(jù)任務(wù)的開始截止時間來確定任務(wù)的優(yōu)先級。截止時間愈早，其優(yōu)先級愈高。要求：系統(tǒng)中保持一個實時任務(wù)就緒隊列，該隊列按各任務(wù)截止時間的早晚排序；適用：搶占式調(diào)度、非搶占式調(diào)度。

該算法用于非搶占式調(diào)度方式示例。在該例子中具有四個非周期任務(wù)，它們先后到達。

任務(wù)1任務(wù)執(zhí)行→任務(wù)到達→任務(wù)1t圖3-9DEF算法用于非搶占式調(diào)度方式任務(wù)3任務(wù)4任務(wù)2任務(wù)2任務(wù)3任務(wù)4開始截止時間：任務(wù)1的任務(wù)3的任務(wù)4的任務(wù)2的結(jié)束下一步下一步2．最低松弛度優(yōu)先即LLF(LeastLaxityFirst)算法

算法：根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度愈高，優(yōu)先級就愈高。

例如：一個任務(wù)在200ms時必須完成，它本身所需的運行時間有100ms，該任務(wù)的緊急程度(松弛程度)為100ms。

實現(xiàn)：一個按松弛度排序的實時任務(wù)就緒隊列；松弛度最低（最緊迫）的任務(wù)排在隊列最前面；調(diào)度程序選擇就緒隊列中的隊首任務(wù)執(zhí)行。適用：可搶占調(diào)度

例：一個實時系統(tǒng)中有兩個周期性實時任務(wù)，A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms；任務(wù)B只要求每50ms執(zhí)行一次，執(zhí)行時間25ms。對于A，合適截止時間依次為20、40、60、80、100…;對于B，合適截止時間依次為50、100、150…;

圖3-11給出了A和B截止的時間點。

圖3-11A和B任務(wù)每次必須完成的時間020406080100120140160180200AAAAAAAAAAtBBBB松弛度=必須完成的時間點-本身所需運行時間-當前時間:A1(10)B1(20)0102030405060708090100t1t2

t3

t4

t5t6

t7

t8

t圖3-12利用LLF算法對兩個周期性實時任務(wù)進行調(diào)度A2(10)A3(10)A4(10)B1(5)B2(15)B2(10)初始：t=0時刻，計算A，B松弛度：A1=20–10–0=10B1=50–25–0=25t=10時刻，計算A，B松弛度：A2=40–10–10=20B1=50–25–10=15t=30時刻，計算A，B松弛度：A2=40–10–30=0B1=50–5–30=15t=40時刻，計算A，B松弛度：A3=60–10–40=10B1=50–5–40=5t=45時刻，計算A，B松弛度：A3=60–10–45=5B2=100–25–45=30t=55時刻，計算A，B松弛度：A4=80–10–55=35B2=100–25–55=20t=70時刻，計算A，B松弛度：A4=80–10–70=0B2=100–10–70=20t=80時刻，計算A，B松弛度：A5=100–10–80=10B2=100–10–80=10結(jié)束●●下一步下一步下一步下一步下一步下一步下一步下一步最低松弛度優(yōu)先（LLF）3.5產(chǎn)生死鎖的原因和必要條件

一、死鎖的概念

1.死鎖問題P(s1)P(s2)臨界區(qū)V(s2)V(s1)P(s2)P(s1)臨界區(qū)V(s1)V(s2)........................進程1進程2就緒就緒執(zhí)行執(zhí)行阻塞s1s2阻塞狀態(tài)：狀態(tài)：死鎖2.死鎖概念

指多個進程因競爭共享資源而造成的一種僵局，若無外力作用，這些進程都將永遠不能再向前推進。

即：一組進程中，每個進程都無限等待被該組進程中另一進程所占有的資源，因而永遠無法得到的資源，這種現(xiàn)象稱為進程死鎖，這一組進程就稱為死鎖進程。

3.關(guān)于死鎖的一些結(jié)論

1)參與死鎖的進程最少是兩個。

2)參與死鎖的進程至少有兩個已經(jīng)占有資源。

3)參與死鎖的所有進程都在等待資源。

4)參與死鎖的進程是當前系統(tǒng)中所有進程的子集。

注：如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。

4.永久性資源和臨時性資源永久性資源：可以被多個進程多次使用（可再用資源）可搶占資源(可剝奪)；如：主存、CPU不可搶占資源（不可剝奪）；如：打印機臨時性資源：只可使用一次的資源；如信號量，中斷信號，同步信號（可消耗性資源）“申請--分配--使用--釋放”模式二、產(chǎn)生死鎖的原因

產(chǎn)生的根本原因是系統(tǒng)能夠提供的資源數(shù)少于需要該資源的進程數(shù)(系統(tǒng)資源不足)。

1）競爭系統(tǒng)資源(不可剝奪)。

2）進程的推進順序不當。死鎖起因是并發(fā)進程的資源競爭，但資源競爭并不一定產(chǎn)生死鎖。1.競爭系統(tǒng)資源（非可剝奪）

若系統(tǒng)中只有一臺打印機R1和一臺磁帶機R2，可供進程P1和P2共享。若形成環(huán)路，這樣會產(chǎn)生死鎖。

實質(zhì)：可共享資源不足。2.進程的推進順序不當

在進程P1和P2并發(fā)執(zhí)行時，按照左圖曲線①②③所示順序推進時，兩進程會順利完成，我們稱這種推進順序是合法的。若按曲線④的順序推進時，進入不安全區(qū)D內(nèi)，兩進程再推進會產(chǎn)生死鎖。三、產(chǎn)生死鎖的必要條件

1）互斥條件。進程對其所要求的資源進行排它性控制，即一次只有一個進程可以使用一個資源。

2）請求和保持條件。進程已經(jīng)保持了至少一個資源，但又提出了新的資源請求。

3）不剝奪條件。進程所獲得的資源在未被釋放之前，不能被其它進程強行剝奪。

4）環(huán)路條件。在發(fā)生死鎖時，必然存在一個進程資源的循環(huán)等待鏈，P1P2R1R2被占有

被占有

請求請求四、處理死鎖的基本方法

1.預(yù)防死鎖

原理：設(shè)置某些限制條件，破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件，來預(yù)防發(fā)生死鎖。

優(yōu)點：較簡單、直觀的。

缺點：導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量降低。

1)棄“互斥條件”。為了破壞資源使用的互斥條件，就要允許多個進程同時訪問共享資源。但是這種方法受到資源本身固有特性的限制，對某些資源是行不通的。例如打印機，就不允許多個進程在其運行期間交替打印數(shù)據(jù)，打印機只能互斥使用。而文件，可能允許多個進程對其進行讀訪問，但只允許互斥地寫訪問?？傊河捎谑芟抻谫Y源本身，互斥條件難以破壞。

2)棄“請求和保持”條件第一種協(xié)議：

策略：資源一次性分配。(資源的靜態(tài)分配策略)優(yōu)點：簡單、易于實現(xiàn)，且很安全。缺點：（1）資源嚴重浪費。一個進程一次獲得其所需的全部資源且獨占，其中可能有些資源很少使用，甚至在整個運行期間都未使用，這就嚴重地惡化了系統(tǒng)資源利用率。（2）進程延遲運行。僅當進程獲得其所需全部資源后，方能開始運行，但可能有許多資源長期被其它進程占用，致使進程推遲運行，這往往要經(jīng)過很長的時延。（饑餓現(xiàn)象）第二種協(xié)議：

策略：一個進程只獲得初期所需資源后，開始運行。運行過程逐步釋放已分配、已用完的全部資源，再請求新的所需資源。

如進程任務(wù):（1）數(shù)據(jù)從磁帶機復(fù)制到磁盤文件；（2）對磁盤文件進行排序；（3）打印機打印結(jié)果；

分析：

按第一協(xié)議必須開始請求獲得磁帶機、磁盤文件、打印機；打印機最后用，即影響效率又影響其他進程運行，還有可能打印機得不到，推遲運行。

按第二協(xié)議開始只需請求磁帶機和磁盤文件，便可運行。等任務(wù)前（1）、（2）完成后釋放磁帶機和磁盤文件，再請求磁盤文件和打印機。可以提高設(shè)備利用率和減少進程饑餓現(xiàn)象。3）棄“不剝奪”條件

策略：申請未果，則放棄。

問題：

1）實現(xiàn)比較復(fù)雜，代價很大。

2）一個資源在使用一段時間后被釋放，可能會造成前階段工作的失效，即使采取某些防范措施，也還會使前后兩次運行的信息不連續(xù)。

3）還可能由于反復(fù)地申請和釋放資源，使進程的執(zhí)行無限推遲。這不僅延長了進程的周轉(zhuǎn)時間，還增加了系統(tǒng)開銷，又降低了系統(tǒng)吞吐量。4）棄“環(huán)路等待”條件

策略：資源有序分配策略。

做法：系統(tǒng)給每類資源賦予一個編號，每一個進程按編號遞增的順序請求資源，釋放則相反。

編號的原則：較為緊缺的資源給以一個較大的序號。

優(yōu)點：較前兩種策略，資源利用率和系統(tǒng)吞吐量，都有顯著的改善。

問題：

a.限制了新設(shè)備類型的增加；

b.發(fā)生作業(yè)使用資源的順序與系統(tǒng)規(guī)定順序不同的情況，造成資源的浪費，如：某進程先用磁帶機，后用打印機，但按系統(tǒng)規(guī)定，它應(yīng)先申請打印機，后申請磁帶機，致使打印機長期閑置。

c.限制了用戶簡單、自由的編程。2.避免死鎖(允許動態(tài)申請資源)

預(yù)防死鎖的幾種策略問題：嚴重地損害了系統(tǒng)性能。

死鎖避免定義：在系統(tǒng)運行過程中，對進程發(fā)出的每一個系統(tǒng)能夠滿足的資源申請進行動態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。由于在避免死鎖的策略中，允許進程動態(tài)地申請資源。因而，系統(tǒng)在進行資源分配之前預(yù)先計算資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進入不安全狀態(tài)，則將資源分配給進程；否則，進程等待。其中最具有代表性的避免死鎖算法是銀行家算法。P進程R資源動態(tài)申請系統(tǒng)是否滿足申請資源要求？否不予分配檢查是試分配新狀態(tài)系統(tǒng)進入新狀態(tài)是否安全？檢查不分配等待不安全允許最終分配安全系統(tǒng)可用資源>=申請資源思考：1、什么是安全狀態(tài)？1）安全狀態(tài)與不安全狀態(tài)

安全狀態(tài)指系統(tǒng)能按某種進程順序來為每個進程分配其所需資源，直至最大需求，使每個進程都可順序完成。若系統(tǒng)不存在這樣一個序列，則稱系統(tǒng)處于不安全狀態(tài)。

關(guān)鍵：尋找一個進程推進安全序列。結(jié)論：

a.安全狀態(tài)一定是沒有死鎖發(fā)生的。

b.并非所有的不安全狀態(tài)都必然會轉(zhuǎn)為死鎖狀態(tài)。

c.避免死鎖的實質(zhì)：系統(tǒng)在進行資源分配時，如何使系統(tǒng)不進入不安全狀態(tài)。2)安全狀態(tài)之例假定系統(tǒng)中有三個進程P1、P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設(shè)在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配。T0：共有12臺，可用3臺尋找到安全序列：<P2，P1，P3>結(jié)論：系統(tǒng)在T0時刻是安全的。由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換例如：在T0時刻以后，P3又請求1臺磁帶機；T0：轉(zhuǎn)變新狀態(tài)：結(jié)論：無法找到安全序列；系統(tǒng)在新狀態(tài)下是不安全的。

P3請求1臺磁帶機后系統(tǒng)進入不安全狀態(tài)，不可對其分配。4）利用銀行家算法避免死鎖a．銀行家算法中的數(shù)據(jù)結(jié)構(gòu)

(1)可利用資源向量Available。含有m個元素的數(shù)組。如：Available[j]=K，表示系統(tǒng)中現(xiàn)有Rj類資源K個。初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目。

(2)最大需求矩陣Max。這是一個n×m的矩陣，系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如：Max[i,j]=K，表示進程i需要Rj類資源的最大數(shù)目為K。

(3)分配矩陣Allocation。這也是一個n×m的矩陣，系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。如:Allocation[i,j]=K，則表示進程i當前已分得RJ類資源的數(shù)目為K。

(4)需求矩陣Need。這也是一個n×m的矩陣，表示每一個進程尚需的各類資源數(shù)。如果Need[i,j]=K，則表示進程i還需要Rj類資源K個，才能完成其任務(wù)。上述三個矩陣間存在下述關(guān)系：Need[i,j]=Max[i,j]-Allocation[i,j]b．安全性算法—判斷狀態(tài)是否安全。

關(guān)鍵：尋找一個進程安全的推進序列。

描述如下：

(1)設(shè)置兩個向量：

①工作向量Work，表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work:=Available。

②Finish，它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish[i]:=false；當有足夠資源分配給進程時，再令Finish[i]:=true。

(2)算法從進程集合中找到一個能滿足下述條件的進程：①Finish[i]=false；未推進的進程②Need[i,j]≤Work[j]；若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。

③當進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Work[j]:=Work[j]+Allocation[i,j]；Finish[i]:=true；gotostep2；

④如果所有進程的Finish[i]=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。例：判斷當前狀態(tài)是否是否安全的。假定系統(tǒng)中有五個進程{P0，P1，P2，P3，P4}和三類資源{A，B，C}，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖所示。

圖3-16T0時刻的資源分配表

T0時刻的安全性：安全的。安全的進程推進序列：P1->P3->P4->P2->P0圖3-17

T0時刻的安全序列

c．銀行家算法

當Pi發(fā)出資源請求后,如:Requesti[j]=K，表示進程Pi需要K個Rj類型的資源，系統(tǒng)按下述步驟進行：

(1)檢查兩前提

①如果Requesti[j]≤Need[i,j]

申請≤需要

②如果Requesti[j]≤Available[j]

申請≤可用

(2)系統(tǒng)試探分配資源給進程Pi，修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Available[j]:=Available[j]-Requesti[j]；Allocation[i,j]:=Allocation[i,j]+Requesti[j]；Need[i,j]:=Need[i,j]-Requesti[j]；

(3)系統(tǒng)執(zhí)行安全性算法。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進程Pi等待。5）銀行家算法之例假定系統(tǒng)中有五個進程{P0，P1，P2，P3，P4}和三類資源{A，B，C}，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖所示。

圖3-16T0時刻的資源分配表(1)T0時刻的安全性：安全的圖3-17

T0時刻的安全序列

(2)?P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進行檢查：①Request1(1，0，2)≤Need1(1，2，2)②Request1(1，0，2)≤Available1(3，3，2)③

系統(tǒng)先試為P1分配資源，并修改Available，Allocation1和Need1向量，形成新狀態(tài)。

兩前提修改后④再利用安全性算法檢查此時系統(tǒng)是否安全。圖3-17P1申請資源時的安全性檢查結(jié)論：找到了一個安全序列，系統(tǒng)是安全的，可以為P1分配資源(3)?P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進行檢查：①Request4(3，3，0)≤Need4(4，3，1)；②Request4(3，3，0)≤Available(2，3，0)，讓P4等待。圖：已分配了P1的資源分配表優(yōu)點：能時刻保證系統(tǒng)處于安全狀態(tài)。缺點：需要不斷進行測試，需花費較多時間。借助銀行家算法預(yù)測系統(tǒng)的安全性：例如，某系統(tǒng)有同類資源m個，可并發(fā)執(zhí)行且共享該類資源的進程最多n個，而每個進程申請該類資源的最大量為x（1≤x≤m），只要不等式n（x-1）+1≤m成立，則系統(tǒng)一定不會發(fā)生死鎖。

例題:某系統(tǒng)中有11臺打印機，N個進程共享打印機資源，每個進程要求3臺。但N的取值不超過(

)時，系統(tǒng)不會發(fā)生死鎖。A．4B．5C．6 D．73.死鎖的檢測和解除

當系統(tǒng)為進程分配資源時，若未采取任何限制性措施來保證不進入死鎖狀態(tài)，則系統(tǒng)必須提供檢測和解除死鎖的手段。

系統(tǒng)做到：

1)保存有關(guān)資源的請求和分配信息；

2)提供一種算法，以利用這些信息來檢測系統(tǒng)是否已進入死鎖狀態(tài)。

發(fā)現(xiàn)死鎖是根據(jù)死鎖狀態(tài)的定義，利用死鎖描述中介紹的資源分配圖來考察某一時刻系統(tǒng)狀態(tài)是否合理，即是否能使所有進程都得到它們所申請的資源而運行結(jié)束。

解除死鎖：與檢測死鎖相配套的一種措施。

方法：剝奪資源、撤消進程；死鎖的檢測和解除措施有可能使系統(tǒng)獲得較好的資源利用率和吞吐量，但在實現(xiàn)上難度也最大。一、調(diào)度的類型和層次1.調(diào)度層次

1）作業(yè)調(diào)度（高級調(diào)度）：批處理系統(tǒng)、運行頻率低。

2）中級調(diào)度（交換調(diào)度）：解決內(nèi)存緊張。

3）進程調(diào)度（低級調(diào)度）：OS中必須配置、運行頻率高。2、作業(yè)控制塊—JCB：控制和管理作業(yè)運行。作業(yè)的5個狀態(tài)：“提交”、“后備”、“活動”、“完成”、“退出”。3、進程調(diào)度功能：

1)保存處理機的現(xiàn)場信息。

2)按某種算法選取進程。

3)把處理器分配給進程。由分派程序(Dispatcher)把處理器分配給進程。從選中的進程PCB中恢復(fù)處理機現(xiàn)場。時機：

1）進程運行結(jié)束；

2）執(zhí)行中的進程發(fā)生某個等待事件；

3）分時系統(tǒng)時間片到；

4）在采用可搶占調(diào)度方式的系統(tǒng)中，當具有更高優(yōu)先級的進程要求使用處理機。總結(jié)：

進程調(diào)度方式：

1）非搶先調(diào)度方式

2）可搶先調(diào)度方式4、調(diào)度隊列模型

1、2、3種。5、調(diào)度總則面向用戶：

1）周轉(zhuǎn)時間短。評價批處理系統(tǒng)。

2）響應(yīng)時間快。評價分時系統(tǒng)。

3）截止時間的保證。評價實時系統(tǒng)。

4）優(yōu)先權(quán)準則。都可遵循。面向系統(tǒng)：

1）系統(tǒng)吞吐量高。

2）處理機利用率好。

3）各類資源的平衡利用。二、調(diào)度算法（重點）1.先來先服務(wù)調(diào)度算法(FCFS)：

適用：進程調(diào)度、作業(yè)調(diào)度，有利于長作業(yè)。2.短作業(yè)(進程)優(yōu)先調(diào)度算法（SJ(P)F）適用：短作業(yè)，但會有“餓死”現(xiàn)象。3.高優(yōu)先權(quán)優(yōu)先調(diào)度算法（HPF）

適用：作業(yè)調(diào)度、進程調(diào)