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

3.4實(shí)

時(shí)

調(diào)

度

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

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

對(duì)單處理機(jī)：

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

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

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

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

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

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

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

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

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

實(shí)現(xiàn)：一個(gè)按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列；松弛度最低（最緊迫）的任務(wù)排在隊(duì)列最前面；調(diào)度程序選擇就緒隊(duì)列中的隊(duì)首任務(wù)執(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。對(duì)于A，合適截止時(shí)間依次為20、40、60、80、100…;對(duì)于B，合適截止時(shí)間依次為50、100、150…;

圖3-11給出了A和B截止的時(shí)間點(diǎn)。

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

t3

t4

t5t6

t7

t8

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

一、死鎖的概念

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

指多個(gè)進(jìn)程因競(jìng)爭(zhēng)共享資源而造成的一種僵局，若無(wú)外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。

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

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

1)參與死鎖的進(jìn)程最少是兩個(gè)。

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

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

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

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

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

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

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

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

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

實(shí)質(zhì)：可共享資源不足。2.進(jìn)程的推進(jìn)順序不當(dāng)

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

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

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

3）不剝奪條件。進(jìn)程所獲得的資源在未被釋放之前，不能被其它進(jìn)程強(qiáng)行剝奪。

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

被占有

請(qǐng)求請(qǐng)求四、處理死鎖的基本方法

1.預(yù)防死鎖

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

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

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

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

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

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

策略：一個(gè)進(jìn)程只獲得初期所需資源后，開(kāi)始運(yùn)行。運(yùn)行過(guò)程逐步釋放已分配、已用完的全部資源，再請(qǐng)求新的所需資源。

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

分析：

按第一協(xié)議必須開(kāi)始請(qǐng)求獲得磁帶機(jī)、磁盤(pán)文件、打印機(jī)；打印機(jī)最后用，即影響效率又影響其他進(jìn)程運(yùn)行，還有可能打印機(jī)得不到，推遲運(yùn)行。

按第二協(xié)議開(kāi)始只需請(qǐng)求磁帶機(jī)和磁盤(pán)文件，便可運(yùn)行。等任務(wù)前（1）、（2）完成后釋放磁帶機(jī)和磁盤(pán)文件，再請(qǐng)求磁盤(pán)文件和打印機(jī)?？梢蕴岣咴O(shè)備利用率和減少進(jìn)程饑餓現(xiàn)象。3）棄“不剝奪”條件

策略：申請(qǐng)未果，則放棄。

問(wèn)題：

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

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

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

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

做法：系統(tǒng)給每類(lèi)資源賦予一個(gè)編號(hào)，每一個(gè)進(jìn)程按編號(hào)遞增的順序請(qǐng)求資源，釋放則相反。

編號(hào)的原則：較為緊缺的資源給以一個(gè)較大的序號(hào)。

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

問(wèn)題：

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

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

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

預(yù)防死鎖的幾種策略問(wèn)題：嚴(yán)重地?fù)p害了系統(tǒng)性能。

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

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

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

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

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

c.避免死鎖的實(shí)質(zhì)：系統(tǒng)在進(jìn)行資源分配時(shí)，如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。2)安全狀態(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：共有12臺(tái)，可用3臺(tái)尋找到安全序列：<P2，P1，P3>結(jié)論：系統(tǒng)在T0時(shí)刻是安全的。由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換例如：在T0時(shí)刻以后，P3又請(qǐng)求1臺(tái)磁帶機(jī)；T0：轉(zhuǎn)變新?tīng)顟B(tài)：結(jié)論：無(wú)法找到安全序列；系統(tǒng)在新?tīng)顟B(tài)下是不安全的。

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

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

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

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

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

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

描述如下：

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

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

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

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

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

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

圖3-16T0時(shí)刻的資源分配表

T0時(shí)刻的安全性：安全的。安全的進(jìn)程推進(jìn)序列：P1->P3->P4->P2->P0圖3-17

T0時(shí)刻的安全序列

c．銀行家算法

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

(1)檢查兩前提

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

申請(qǐng)≤需要

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

申請(qǐng)≤可用

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

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

T0時(shí)刻的安全序列

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

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

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

例題:某系統(tǒng)中有11臺(tái)打印機(jī)，N個(gè)進(jìn)程共享打印機(jī)資源，每個(gè)進(jìn)程要求3臺(tái)。但N的取值不超過(guò)(

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

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

系統(tǒng)做到：

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

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

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

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

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

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

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

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

1)保存處理機(jī)的現(xiàn)場(chǎng)信息。

2)按某種算法選取進(jìn)程。

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

1）進(jìn)程運(yùn)行結(jié)束；

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

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

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

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

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

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

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

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

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

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

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

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

2）處理機(jī)利用率好。

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

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

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