操作系統(tǒng)第五章

1、5.1 資源管理概述5.2 資源分配機(jī)制5.3 資源分配策略5.4 死鎖5.1 資源管理的目的和任務(wù) 資源管理的目的： 1、保證資源的高利用率； 2、在“合理”時(shí)間內(nèi)使所有“顧客(client)”有獲得所需資源的機(jī)會(huì)； 3、對(duì)不可共享的資源實(shí)施互斥使用； 4、防止由資源分配不當(dāng)而引起的死鎖。1. 資源數(shù)據(jù)結(jié)構(gòu)的描述資源數(shù)據(jù)結(jié)構(gòu)的描述 構(gòu)造資源分配所需的數(shù)據(jù)結(jié)構(gòu)，應(yīng)包含該資源的物理名、邏輯名、類型、地址、分配狀態(tài)等信息。 2. 確定資源的分配原則確定資源的分配原則 (調(diào)度原則調(diào)度原則) 確定資源分配原則，即決定資源應(yīng)分給誰(shuí)，何時(shí)分配，分配多少等問(wèn)題。5.1.1 資源管理功能資源管理功能3. 實(shí)施

2、資源分配實(shí)施資源分配 根據(jù)所確定的資源分配原則以及用戶的要求，執(zhí)行資源分配。當(dāng)資源使用完畢后，收回資源以便重新分配給其他作業(yè)和進(jìn)程使用。 4. 存取控制和安全保護(hù)存取控制和安全保護(hù) 對(duì)資源的存取進(jìn)行控制并對(duì)資源實(shí)施安全保護(hù)措施。（eg:文件的管理文件的管理,任何一個(gè)用戶對(duì)任一文件的存取都要經(jīng)過(guò)文件管理器系統(tǒng)中的存取控制驗(yàn)證模塊的檢查）5.1.1 資源管理功能資源管理功能1. 資源描述器資源描述器 (1) 什么是資源描述器什么是資源描述器 描述各類資源的最小分配單位的數(shù)據(jù)結(jié)構(gòu)稱為資源描述器 rd (resource descriptor)。 如：主存最小分配單位： 在分區(qū)分配中主存分區(qū) 磁盤最小

3、分配單位： 磁盤面中的一個(gè)扇區(qū)什么是資源描述器（resource descriptor？)資源描述器的內(nèi)容資源名資源類型最小分配單位的大小最小分配單位的地址分配標(biāo)志描述器鏈接信息存取權(quán)限密級(jí)最后一次存取時(shí)間記賬信息 2. 資源信息塊資源信息塊 為了對(duì)每類資源實(shí)施有效的分配，我們?cè)O(shè)置相應(yīng)的資源信息塊rib（resource information blcok）,這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)能說(shuō)明資源、請(qǐng)求者、實(shí)施分配所需的必要信息。 對(duì)每一類可利用的資源，可將其組織成可利用資源的隊(duì)列。5.2 資源分配機(jī)構(gòu)資源分配機(jī)構(gòu) 2. 資源信息塊資源信息塊 (1) 什么是資源信息塊什么是資源信息塊 描述某類資源的請(qǐng)求

4、者、可用資源情況和該類資源描述某類資源的請(qǐng)求者、可用資源情況和該類資源分配程序等必要信息的數(shù)據(jù)結(jié)構(gòu)。分配程序等必要信息的數(shù)據(jù)結(jié)構(gòu)。 (2) 資源信息塊的內(nèi)容資源信息塊的內(nèi)容等待隊(duì)列頭指針可利用資源隊(duì)列頭指針資源分配程序入口地址 pcb1pcb2pcbkrd1rd2rdn5.2 資源分配機(jī)構(gòu)資源分配機(jī)構(gòu) (3) 中央處理機(jī)資源信息塊中央處理機(jī)資源信息塊 ready-q-startrunningscheduler-addr pcb1pcb2pcbkpcb5cpu - rib5.2 資源分配機(jī)構(gòu)資源分配機(jī)構(gòu)5.3資源分配策略當(dāng)資源可用時(shí)，滿足哪一個(gè)請(qǐng)求者？常用的分配策略:a.先請(qǐng)求先服務(wù)（FIFO）

5、b. 優(yōu)先調(diào)度c.針對(duì)設(shè)備特性的調(diào)度a.先請(qǐng)求先服務(wù)FIFO 先請(qǐng)求先服務(wù)FIFO (First In First Out) 排序原則：按請(qǐng)求的先后次序排序。 每一個(gè)新產(chǎn)生的請(qǐng)求均排在隊(duì)尾，而當(dāng)資源可用時(shí)，資源分配程序則從隊(duì)列中選取第一個(gè)請(qǐng)求，并滿足其需要。 先請(qǐng)求先服務(wù)的隊(duì)列結(jié)構(gòu)a.先請(qǐng)求先服務(wù)FIFO 先請(qǐng)求先服務(wù)的隊(duì)列結(jié)構(gòu)b.優(yōu)先調(diào)度 在優(yōu)先調(diào)度策略下，對(duì)于每一個(gè)進(jìn)程要指定一個(gè)優(yōu)先級(jí)，優(yōu)先級(jí)反映了進(jìn)程要求處理的緊迫程度。 排序原則：按優(yōu)先級(jí)的高低排序。 每一個(gè)新產(chǎn)生的請(qǐng)求，按其優(yōu)先級(jí)的高低插到相應(yīng)的位置上。而當(dāng)資源可用時(shí)，選取隊(duì)列中第一個(gè)請(qǐng)求，并滿足其需要。b.優(yōu)先調(diào)度的隊(duì)列結(jié)構(gòu) 5.4

6、 死鎖的產(chǎn)生 操作系統(tǒng)的基本特征是并發(fā)與共享。系統(tǒng)允許多個(gè)進(jìn)程并發(fā)執(zhí)行，并且共享系統(tǒng)的軟、硬件資源。 為了最大限度的利用計(jì)算機(jī)系統(tǒng)的資源，操作系統(tǒng)應(yīng)采用動(dòng)態(tài)分配系統(tǒng)各種資源的策略。 然而，采用這種策略時(shí)，當(dāng)對(duì)某類資源的申請(qǐng)數(shù)目超過(guò)這類資源的入口數(shù)目入口數(shù)目，若分配不當(dāng)，可能出現(xiàn)進(jìn)程之間相互等資源又都不能向前推進(jìn)的情況。即造成進(jìn)程相互封鎖的危險(xiǎn)。造成進(jìn)程相互封鎖的危險(xiǎn)。5.4.1 死鎖的概念例子：死鎖的生活中的影子AB假設(shè)有這么兩個(gè)人A，B：地位平等地位平等且自私自私。任務(wù)：每個(gè)人都獨(dú)立去植樹器具：目前只有1把鏟子和1個(gè)水桶例子：死鎖的生活中的影子要求：每個(gè)人若想獨(dú)立去把植樹完成，植樹時(shí)必須同時(shí)

7、具備1把鏟子和1個(gè)水桶場(chǎng)景：現(xiàn)在，A手中有1把鏟子，B手中有1個(gè)水桶問(wèn)題：A、B兩人能否分別完成自己的任務(wù)呢？AB有鏟子有水桶缺水桶缺鏟子WaitingWaitingWaiting for dead分析什么是死鎖？ 死鎖的定義： 一組進(jìn)程中，每個(gè)進(jìn)程都無(wú)限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而無(wú)限期地僵持下去的局面 ，這種現(xiàn)象稱為進(jìn)程死鎖。 這一組進(jìn)程就稱為死鎖進(jìn)程設(shè)S1=1，打印機(jī)可用。S2=1，讀卡機(jī)可用。OS中的例子 操作系統(tǒng)中的例子有二個(gè)進(jìn)程P1、P2，兩個(gè)設(shè)備打印機(jī)R1，讀卡機(jī)R2 。 P(S1)； P(S2)； P(S2)； P(S1)； V(S1)； V(S2)； V(S2)

8、； V(S1)； P1P2 P(S1)； P(S2)； V(S1)； V(S2)； P(S2)； P(S1)； V(S2)； V(S1)； P1P2P1P2P1P2？ 兩種寫法，誰(shuí)可能造成死鎖？申請(qǐng)R2S2：1-1=0占用R2申請(qǐng)R1S1：1-1=0占用R1申請(qǐng)R1，但R1被P1占用申請(qǐng)R2，但R2被P2占用死鎖Hold and wait 2.銀行家問(wèn)題的例子 銀行共有資金10萬(wàn)元，客戶u1需貸款3萬(wàn)，客戶u2需貸款8萬(wàn)，客戶u3需貸款9萬(wàn) 。某一時(shí)刻： u2u3u1 已貸款還需資金1萬(wàn)2萬(wàn)2萬(wàn)6萬(wàn)6萬(wàn)3萬(wàn)銀行只剩下銀行只剩下一萬(wàn)元，造一萬(wàn)元，造成死鎖成死鎖。5.4.1 死鎖的概念死鎖的概念行

9、家的例子）對(duì)于客戶來(lái)說(shuō)，只有所需要的所有貸對(duì)于客戶來(lái)說(shuō)，只有所需要的所有貸款全部得到滿足，這樣生意才能完成，款全部得到滿足，這樣生意才能完成，之后才能把所貸款項(xiàng)歸還。之后才能把所貸款項(xiàng)歸還。貸不到款，客戶死貸不到款，客戶死貸款得不到歸還，銀行家死貸款得不到歸還，銀行家死起因：起因：1）系統(tǒng)資源不足）系統(tǒng)資源不足 系統(tǒng)資源數(shù)目系統(tǒng)資源數(shù)目 進(jìn)程需求進(jìn)程需求結(jié)論與問(wèn)題：結(jié)論與問(wèn)題：死鎖一定是系統(tǒng)資源不足死鎖一定是系統(tǒng)資源不足的，那么系統(tǒng)資源不足是不是一定造的，那么系統(tǒng)資源不足是不是一定造成死鎖呢成死鎖呢2）聯(lián)合推進(jìn)路線非法）聯(lián)合推進(jìn)路線非法（進(jìn)程推進(jìn)順序不當(dāng)）（進(jìn)程推進(jìn)順序不當(dāng)） 5.4.2產(chǎn)生死

10、鎖的起因和條件產(chǎn)生死鎖的起因和條件A2B2C2D2申請(qǐng)r1申請(qǐng)r2釋放r2釋放r1A1B1C1D1申請(qǐng)r1申請(qǐng)r2釋放r1釋放r2兩進(jìn)程均占用r1兩進(jìn)程均占用r2xyP2進(jìn)展P1進(jìn)展0A 死鎖點(diǎn) 5.4.2產(chǎn)生死鎖的起因和條件產(chǎn)生死鎖的起因和條件路線1路線2ttt2t1死鎖產(chǎn)生的條件 1971年Coffman總結(jié)出了對(duì)于可再使用資源，系統(tǒng)產(chǎn)生死鎖必定同時(shí)保持四個(gè)必要條件：1. 互斥條件（mutual exclusion）2. 占有和等待條件（hold and wait）3. 不剝奪條件（no preemption）4. 循環(huán)等待條件（circular wait）死鎖產(chǎn)生的條件 1. 互斥條件（

11、mutual exclusion）：進(jìn)程應(yīng)互斥使用資源，任一時(shí)刻一個(gè)資源僅為一個(gè)進(jìn)程獨(dú)占，若另一個(gè)進(jìn)程請(qǐng)求一個(gè)已被占用的資源時(shí)，它被置成等待狀態(tài)，直到占用者釋放資源。死鎖產(chǎn)生的條件 2.占有和等待條件（hold and wait）（或稱部分分配條件）：一個(gè)進(jìn)程請(qǐng)求資源得不到滿足而等待時(shí)，不釋放已占有的資源。死鎖產(chǎn)生的條件 3. 不剝奪條件（no preemption）：任一進(jìn)程不能從另一進(jìn)程那里搶奪資源，即已被占用的資源，只能由占用進(jìn)程自己來(lái)釋放。4. 循環(huán)等待條件（circular wait）：存在一個(gè)循環(huán)等待鏈，其中，每一個(gè)進(jìn)程分別等待它前一個(gè)進(jìn)程所持有的資源，造成永遠(yuǎn)等待。死鎖產(chǎn)生的條件

12、 以上前三個(gè)條件互斥條件（mutual exclusion）占有和等待條件（hold and wait）不剝奪條件（no preemption）是死鎖存在的必要條件（necessary condition），但不是充分條件。死鎖產(chǎn)生的條件 第四個(gè)條件：循環(huán)等待條件（circular wait）是前三個(gè)條件同時(shí)存在時(shí)產(chǎn)生的結(jié)果，所以，這些條件并不完全獨(dú)立。但單獨(dú)考慮每個(gè)條件是有用的，只要能破壞只要能破壞這四個(gè)必要條件之一，死鎖就可防止這四個(gè)必要條件之一，死鎖就可防止。5.4.3 解決死鎖問(wèn)題的策略-預(yù)防死鎖 一、解決死鎖問(wèn)題的幾個(gè)策略 為了不發(fā)生死鎖，必須設(shè)法破壞產(chǎn)生死鎖的四個(gè)必要條件之一。 條

13、件1（互斥條件）：難以否定，但可采用相應(yīng)的技術(shù)，如利用假脫機(jī)技術(shù)，即用可共享使用的設(shè)備模擬非共享的設(shè)備；5.4.3 解決死鎖問(wèn)題的策略-預(yù)防死鎖 條件2（占有和等待條件）：容易否定也容易實(shí)現(xiàn)，可制定相應(yīng)的規(guī)則即可，例如，當(dāng)一個(gè)進(jìn)程（程序）申請(qǐng)某資源被拒絕，則必須釋放已占用的資源，如需要再與其它所需資源一起申請(qǐng)。 在資源分配策略上可以采取靜態(tài)資源分配的方式一次性的把所需資源全部分配到位，否則就不分配。5.4.3 解決死鎖問(wèn)題的策略-預(yù)防死鎖 條件3（不剝奪條件）：也是很容易否定的，只要分配策略上規(guī)定一個(gè)進(jìn)程（或程序）一次將所需資源一次申請(qǐng)到位。用完后釋放?？梢匀坑猛旰?，統(tǒng)一釋放，也可使用完后立

14、即釋放，只要是一次申請(qǐng)到的，系統(tǒng)就不會(huì)出現(xiàn)死鎖。5.4.3 解決死鎖問(wèn)題的策略-預(yù)防死鎖條件4（循環(huán)等待條件）：通過(guò)有序資源分配法，可以破壞環(huán)路條件。實(shí)際上系統(tǒng)還可以不采用部分分配，也就破壞了環(huán)路等待條件。 死鎖的解決策略歸納起來(lái)，可以采用以下策略之一來(lái)解決死鎖問(wèn)題： 忽略該問(wèn)題 采用靜態(tài)資源分配來(lái)預(yù)防死鎖 采用有控分配方法來(lái)避免死鎖 當(dāng)死鎖發(fā)生時(shí)檢測(cè)死鎖，并設(shè)法修復(fù)鴕鳥算法 象鴕鳥一樣對(duì)死鎖視而不見(jiàn)是最簡(jiǎn)單的方法. 每個(gè)人對(duì)該方法的看法都不相同. 數(shù)學(xué)家認(rèn)為要徹底防止死鎖的產(chǎn)生,不論代價(jià)有多大; 工程師們想要了解死鎖發(fā)生的頻率,系統(tǒng)因各種原因崩潰的頻率,以及死鎖的嚴(yán)重程度. UNIX潛在地受

15、到了一些死鎖的威協(xié),但是這些死鎖從來(lái)沒(méi)有發(fā)生,甚至從來(lái)沒(méi)有被檢測(cè)到.處理死鎖的UNIX辦法是忽略它,由于大多數(shù)用戶寧可在極偶然的情況下產(chǎn)生死鎖,也不愿被限制只能創(chuàng)建一個(gè)進(jìn)程,只能打開一個(gè)文件等等.為了研究解決死鎖的方法，可借助于有為了研究解決死鎖的方法，可借助于有向圖這一強(qiáng)有力的工具。圖中有兩種節(jié)向圖這一強(qiáng)有力的工具。圖中有兩種節(jié)點(diǎn)：方塊和圓圈。點(diǎn)：方塊和圓圈。圓圈代表進(jìn)程，方塊圓圈代表進(jìn)程，方塊代表資源。代表資源。 從資源節(jié)點(diǎn)從資源節(jié)點(diǎn)(方塊方塊)到進(jìn)程節(jié)點(diǎn)到進(jìn)程節(jié)點(diǎn)(圓圈圓圈)的的有向弧有向弧表示資源已經(jīng)分配給進(jìn)程表示資源已經(jīng)分配給進(jìn)程； 從進(jìn)程到資源的有向弧表示進(jìn)程從進(jìn)程到資源的有向弧表

16、示進(jìn)程當(dāng)前正當(dāng)前正處于阻塞狀態(tài)，等待資源變?yōu)榭捎?。處于阻塞狀態(tài)，等待資源變?yōu)榭捎?。資源分配圖資源分配圖2.資源進(jìn)程有向圖 R2P1P2R1表示資源表示進(jìn)程R2P1R1分配請(qǐng)求分配請(qǐng)求分配分配請(qǐng)求P2 5.4.2產(chǎn)生死鎖的起因和條件產(chǎn)生死鎖的起因和條件RASBTDUC(a)進(jìn)程A 分配了一個(gè)資源(b)進(jìn)程B 請(qǐng)求了一個(gè)資源(c)進(jìn)程D和進(jìn)程形成環(huán)路，已處于死鎖狀態(tài)資源分配圖資源分配圖5.4 死鎖的預(yù)防死鎖的預(yù)防靜態(tài)分配策略靜態(tài)分配策略 所謂所謂靜態(tài)分配靜態(tài)分配是指一個(gè)進(jìn)程必須在執(zhí)行前就申是指一個(gè)進(jìn)程必須在執(zhí)行前就申請(qǐng)它所要的全部資源，并且直到它所要的資源請(qǐng)它所要的全部資源，并且直到它所要的資源都

17、得到滿足后才開始執(zhí)行。都得到滿足后才開始執(zhí)行。 采用靜態(tài)分配后，進(jìn)程在執(zhí)行中不再申請(qǐng)資源采用靜態(tài)分配后，進(jìn)程在執(zhí)行中不再申請(qǐng)資源，因而，不會(huì)出現(xiàn)占有了某些資源再等待另一，因而，不會(huì)出現(xiàn)占有了某些資源再等待另一些資源的情況，即些資源的情況，即破壞了第二個(gè)條件（占有和破壞了第二個(gè)條件（占有和等待條件）等待條件）的出現(xiàn)。的出現(xiàn)。5.4 死鎖的預(yù)防死鎖的預(yù)防靜態(tài)分配策略靜態(tài)分配策略靜態(tài)分配策略實(shí)現(xiàn)簡(jiǎn)單，被許多操作系統(tǒng)采靜態(tài)分配策略實(shí)現(xiàn)簡(jiǎn)單，被許多操作系統(tǒng)采用。但這種策略嚴(yán)重地降低了資源利用率，用。但這種策略嚴(yán)重地降低了資源利用率，其缺點(diǎn)也是明顯的：其缺點(diǎn)也是明顯的： 一個(gè)用戶（進(jìn)程）在程序運(yùn)行之前很難

18、提出一個(gè)用戶（進(jìn)程）在程序運(yùn)行之前很難提出將要使用的全部設(shè)備；將要使用的全部設(shè)備； 用戶的作業(yè)必須等待，直到所有的資源滿足用戶的作業(yè)必須等待，直到所有的資源滿足時(shí)才能投入運(yùn)行。實(shí)際上某些設(shè)備可能很晚時(shí)才能投入運(yùn)行。實(shí)際上某些設(shè)備可能很晚的時(shí)候才使用的時(shí)候才使用5.4 死鎖的預(yù)防死鎖的預(yù)防靜態(tài)分配策略靜態(tài)分配策略設(shè)備（資源）的浪費(fèi)太大，有些資源在進(jìn)程運(yùn)行過(guò)設(shè)備（資源）的浪費(fèi)太大，有些資源在進(jìn)程運(yùn)行過(guò)程中可能只有很少的時(shí)間才用到，有的甚至不會(huì)用程中可能只有很少的時(shí)間才用到，有的甚至不會(huì)用到。到。 例如：一個(gè)分支語(yǔ)句，只有當(dāng)程序出錯(cuò)的時(shí)候才將例如：一個(gè)分支語(yǔ)句，只有當(dāng)程序出錯(cuò)的時(shí)候才將錯(cuò)誤從打印機(jī)輸

19、出，但如果采用靜態(tài)資源分配策略錯(cuò)誤從打印機(jī)輸出，但如果采用靜態(tài)資源分配策略的話，也要把打印機(jī)分配給這個(gè)程序，所以這種分的話，也要把打印機(jī)分配給這個(gè)程序，所以這種分配策略對(duì)系統(tǒng)來(lái)說(shuō)是很浪費(fèi)的。配策略對(duì)系統(tǒng)來(lái)說(shuō)是很浪費(fèi)的。5.4 死鎖的預(yù)防死鎖的預(yù)防層次分配層次分配 在層次分配策略下，資源被分成多個(gè)層次，一個(gè)進(jìn)程得到某一層的一個(gè)資源后，它只能再申請(qǐng)?jiān)谳^高一層的資源；當(dāng)一個(gè)進(jìn)程要釋放某層的一個(gè)資源時(shí)，必須先釋放所占用的較高層的資源。 層次分配層次分配策略將阻止第四個(gè)條件（循環(huán)等待條件）的出現(xiàn)。5.4 死鎖的預(yù)防死鎖的預(yù)防層次分配層次分配 這種策略的一個(gè)變種是按序分配策略。把系統(tǒng)的所有資源排列成一個(gè)順

20、序，例如，系統(tǒng)若共有n個(gè)進(jìn)程，共有m個(gè)資源，用ri表示第i個(gè)資源，于是這m個(gè)資源是：r1,r2,rm 規(guī)定如果進(jìn)程不得在占用資源ri(1im)后再申請(qǐng)rj(ji)，即這種算法資源按申請(qǐng)多項(xiàng)資源時(shí)必須以上升的次序依次申請(qǐng)。5.4有序資源分配法 例如：進(jìn)程P1，使用資源的順序是R1，R2； 進(jìn)程P2，使用資源的順序是R2，R1； 若采用動(dòng)態(tài)分配有可能形成環(huán)路條件，造成死鎖。5.4有序資源分配法 采用有序資源分配法：R1的編號(hào)為1，R2的編號(hào)為2； P1：申請(qǐng)次序應(yīng)是：R1，R2 P1：申請(qǐng)次序應(yīng)是：R1，R2 這樣就破壞了環(huán)路條件，避免了死鎖的發(fā)生。5.4.5 死鎖的避免 為了提高設(shè)備的利用率，應(yīng)

21、采用動(dòng)態(tài)的設(shè)備分配方法，但應(yīng)設(shè)法避免發(fā)生死鎖，若存在發(fā)生死鎖的可能性，則拒絕分配。5.4.5 死鎖的避免 預(yù)防死鎖： 采用的分配策略本身就否定了產(chǎn)生死鎖的四個(gè)必要條件之一，這就保證了不會(huì)發(fā)生死鎖； 死鎖避免： 與預(yù)防死鎖相反，它允許系統(tǒng)中同時(shí)存在四個(gè)必要條件，如果能掌握并發(fā)進(jìn)程中與每個(gè)進(jìn)程有關(guān)的資源動(dòng)態(tài)申請(qǐng)情況，做出明智和合理的選擇，仍然可以避免死鎖的發(fā)生。5.4.5 死鎖的避免 死鎖避免不是通過(guò)對(duì)進(jìn)程隨意強(qiáng)加一些規(guī)則，而是通過(guò)對(duì)每一次資源申請(qǐng)進(jìn)行認(rèn)真的分析來(lái)判斷它是否能安全地分配。5.4.5 死鎖的避免 問(wèn)題是：是否存在一種算法總能做出正確的選擇從而避免死鎖？ 答案是肯定的，但條件是必須事先

22、獲得與進(jìn)程有關(guān)的一些特定信息。本節(jié)將討論使用銀行家算法（銀行家算法（bankers algorithm）避免死鎖的方法。銀行家算法銀行家算法 避免死鎖算法中最有代表性的算法是Dijkstra E.W 于1968年提出的銀行家算法：它的模型基于一個(gè)小城鎮(zhèn)的銀行家，現(xiàn)將該算法描述如下：假定一個(gè)銀行家擁有資金，數(shù)量為，被N個(gè)客戶共享。銀行家對(duì)客戶提出下列約束條件：銀行家算法銀行家算法 每個(gè)客戶必須預(yù)先說(shuō)明自己所要求的最大資金量； 每個(gè)客戶每次提出部分資金量申請(qǐng)和獲得分配； 如果銀行滿足了某客戶對(duì)資金的最大需求量，那么，客戶在資金運(yùn)作后，應(yīng)在有限時(shí)間內(nèi)全部歸還銀行。銀行家算法銀行家算法 在銀行家算法中

23、，客戶可看作進(jìn)程，資金可看作資源，銀行家可看作操作系統(tǒng)，這里敘述的是單資源銀行家算法，單資源的銀行家算法單資源的銀行家算法 在上圖a中列出了4個(gè)客戶，每個(gè)客戶都有一個(gè)貸款額度，銀行家知道不可能所有客戶同時(shí)都需要最大貸款額，所以，他只保留10個(gè)單位的資金來(lái)為客戶服務(wù)，而不是22個(gè)單位。 圖（b）所示的狀態(tài)是客戶們各做自己的生意，在某些時(shí)刻需要貸款。客戶已獲得的貸款（已分配的資源）和可用的最大數(shù)額貸款稱為與資源分配相關(guān)的系統(tǒng)狀態(tài)。單資源的銀行家算法 一個(gè)狀態(tài)被稱為是安全的，其條件是存在一個(gè)狀態(tài)序列狀態(tài)序列能夠使所有的客戶均得到其所有的貸款(即所有的進(jìn)程得到所需的全部資源并終止)。單資源的銀行家算法

24、 圖b所示的狀態(tài)是安全的,why? 因?yàn)樵谟?個(gè)單位資金可用的情況下，銀行家可以延遲除Marvin之外的所有請(qǐng)求，這樣便可以使Marvin運(yùn)行結(jié)束，然后釋放所有的4個(gè)單位資金。如此這樣下去便可以滿足Snganne或者Barbarn的請(qǐng)求，等等。 安全貸款序列：Marvin， Sugzanne， Barbarn ,Andy單資源的銀行家算法 圖c所示的狀態(tài)，該狀態(tài)是不安全的。如果忽然所有的客戶都申請(qǐng)，希望得到最大貸款額，而銀行家無(wú)法滿足其中任何一個(gè)的要求，則發(fā)生死鎖。 不安全狀態(tài)并不一定導(dǎo)致死鎖，因?yàn)轭櫩陀锌赡懿恍枰娜抠J款額，但銀行家不能指望這種情況發(fā)生，不敢抱這種僥幸心理。 單資源的銀行

25、家算法單資源的銀行家算法總結(jié) 銀行家算法就是對(duì)每一個(gè)請(qǐng)求進(jìn)行檢查，檢查如果滿足它是否會(huì)導(dǎo)致不安全狀態(tài)。 若是，則不滿足該請(qǐng)求；否則便滿足。 檢查狀態(tài)是否安全的方法是看他是否有足夠的資源滿足一個(gè)距最大需求最近的客戶滿足一個(gè)距最大需求最近的客戶。 如果可以，則這筆投資認(rèn)為是能夠收回的，然后接著檢查下一個(gè)距最大需求最近的客戶，如此反復(fù)下去。如果所有投資最終都被收回，則該狀態(tài)是安全的，最初的請(qǐng)求可以批準(zhǔn)。 單資源銀行家算法總結(jié) 單資源銀行家算法可陳述如下： 當(dāng)一個(gè)進(jìn)程提出資源請(qǐng)求時(shí)，當(dāng)一個(gè)進(jìn)程提出資源請(qǐng)求時(shí)，假定分配假定分配給它，給它，并檢查并檢查系統(tǒng)因此是否仍處于安全系統(tǒng)因此是否仍處于安全狀態(tài)。狀態(tài)

26、。如果安全如果安全，則滿足它的請(qǐng)求。，則滿足它的請(qǐng)求。否否則，推遲它的請(qǐng)求則，推遲它的請(qǐng)求。5.4.6 死鎖的檢測(cè)和恢復(fù) 死鎖的檢測(cè)： 死鎖的檢測(cè)代價(jià)很高； 通常的方法是程序員的經(jīng)驗(yàn)，如UNIX系統(tǒng)中，可考察進(jìn)程的運(yùn)行時(shí)間。在UNIX系統(tǒng)中有命令PS可顯示進(jìn)程占用CPU的時(shí)間，若發(fā)現(xiàn)有一組進(jìn)程在一段時(shí)間內(nèi)沒(méi)有占用CPU，就認(rèn)為這類進(jìn)程出現(xiàn)了死鎖。5.4.6 死鎖的檢測(cè)和恢復(fù) 死鎖排除的方法： 1、撤消陷于死鎖的全部進(jìn)程； 2、逐個(gè)撤消陷于死鎖的進(jìn)程，直到死鎖不存在； 3、從陷于死鎖的進(jìn)程中逐個(gè)強(qiáng)迫放棄所占用的資源，直至死鎖消失。一道考研題一道考研題 下列關(guān)于銀行家算法的敘述中，正確的是（ ）。

27、 A. 銀行家算法可以預(yù)防死鎖 B. 當(dāng)系統(tǒng)處于安全狀態(tài)時(shí)，系統(tǒng)中一定無(wú)死鎖進(jìn)程 C. 當(dāng)系統(tǒng)處于不安全狀態(tài)時(shí)，系統(tǒng)中一定會(huì)出現(xiàn)死鎖進(jìn)程 D. 銀行家算法破壞了死鎖必要條件中的“請(qǐng)求和保持”條件一道考研題 某時(shí)刻進(jìn)程的資源使用情況如下所示。進(jìn)程已分配資源尚需資源可用資源R1R2R3R1R2R3R1 R2 R3P1200001021P2120132P3011131P4001200 此時(shí)的安全序列是（）。（11年聯(lián)考） A. P1, P2, P3, P4 B. P1, P3, P2, P4 C. P1, P4, P3, P2 D. 不存在一道考研題 假設(shè)5個(gè)進(jìn)程P0、P1、P2、P3、P4共享三類

28、資源R1、R2、R3，這些資源總數(shù)分別為18、6、22。T0時(shí)刻的資源分配情況如下表所示，此時(shí)存在的一個(gè)安全序列是（）。（12年聯(lián)考）進(jìn)程已分配資源資源最大需求R1R2R3R1R2R3P03235510P1403536P24054011P3204425P4314424 A. P0, P1, P2, P3, P4 B. P1, P0, P3, P4, P2 C. P2, P1, P0, P3, P4 D. P3, P4, P2, P1, P0回顧：資源競(jìng)爭(zhēng)產(chǎn)生死鎖回顧：資源競(jìng)爭(zhēng)產(chǎn)生死鎖 m個(gè)資源被個(gè)資源被n個(gè)進(jìn)程共享，每個(gè)進(jìn)程要求個(gè)進(jìn)程共享，每個(gè)進(jìn)程要求k個(gè)資個(gè)資源，則當(dāng)源，則當(dāng) m=n*(k-

29、1) 時(shí)，如果分配不當(dāng)就可能發(fā)時(shí)，如果分配不當(dāng)就可能發(fā)生死鎖。生死鎖。 死鎖的定義：在兩個(gè)或多個(gè)并發(fā)進(jìn)程中，如果死鎖的定義：在兩個(gè)或多個(gè)并發(fā)進(jìn)程中，如果每個(gè)進(jìn)程持有某種資源而又都等待著別的進(jìn)程釋放每個(gè)進(jìn)程持有某種資源而又都等待著別的進(jìn)程釋放它或它們現(xiàn)在保持著的資源，否則就不能向前推進(jìn)。它或它們現(xiàn)在保持著的資源，否則就不能向前推進(jìn)。此時(shí)每個(gè)進(jìn)程都占用了一定的資源但又都不能向前此時(shí)每個(gè)進(jìn)程都占用了一定的資源但又都不能向前推進(jìn)，稱這一組進(jìn)程產(chǎn)生可死鎖。推進(jìn)，稱這一組進(jìn)程產(chǎn)生可死鎖。 某計(jì)算機(jī)系統(tǒng)中有8臺(tái)打印機(jī)，有K個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每個(gè)進(jìn)程最多需要3臺(tái)打印機(jī)。該系統(tǒng)可能會(huì)發(fā)生死鎖的K的最小值是（ ）。

30、 A. 2B. 3C. 4D. 5死鎖的避免死鎖的避免 1. 1. 有序資源使用法有序資源使用法 系統(tǒng)中的所有資源類都分給一個(gè)唯一的序系統(tǒng)中的所有資源類都分給一個(gè)唯一的序號(hào)，并要求每個(gè)進(jìn)程均應(yīng)嚴(yán)格按照遞增的次序號(hào)，并要求每個(gè)進(jìn)程均應(yīng)嚴(yán)格按照遞增的次序請(qǐng)求資源。請(qǐng)求資源。 有序資源使用法破壞了產(chǎn)生死鎖的環(huán)路條有序資源使用法破壞了產(chǎn)生死鎖的環(huán)路條件，從而不可能產(chǎn)生死鎖。件，從而不可能產(chǎn)生死鎖。 缺點(diǎn)：對(duì)于實(shí)際資源使用順序與資源序號(hào)缺點(diǎn)：對(duì)于實(shí)際資源使用順序與資源序號(hào)不一致的作業(yè)仍存在著資源浪費(fèi)現(xiàn)象。不一致的作業(yè)仍存在著資源浪費(fèi)現(xiàn)象。 例如：例如：進(jìn)程進(jìn)程PA，使用資源的順序是，使用資源的順序是R1，R2； 進(jìn)程進(jìn)程P