操作系統(tǒng)第三章2

1、Operating SystemOperating SystemPage 12022-3-17Operating SystemOperating SystemPage 22022-3-17q處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 q調(diào)度算法調(diào)度算法 q實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 q多處理機(jī)系統(tǒng)中的調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度q死鎖概述死鎖概述q預(yù)防死鎖的方法預(yù)防死鎖的方法 q死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除Operating SystemOperating SystemPage 32022-3-173q日常生活中的例子日常生活中的例子q進(jìn)程死鎖的例子進(jìn)程死鎖的例子v競(jìng)爭(zhēng)外部設(shè)備競(jìng)爭(zhēng)外部設(shè)備v競(jìng)爭(zhēng)輔存空間競(jìng)

2、爭(zhēng)輔存空間q哲學(xué)家進(jìn)餐問(wèn)題哲學(xué)家進(jìn)餐問(wèn)題Operating SystemOperating SystemPage 42022-3-17交通死鎖的示例讓路！讓路！ 讓路！ 讓路！Operating SystemOperating SystemPage 52022-3-17進(jìn)程進(jìn)程A A進(jìn)程進(jìn)程B B 申請(qǐng)輸入設(shè)備申請(qǐng)輸入設(shè)備申請(qǐng)輸出設(shè)備申請(qǐng)輸出設(shè)備 申請(qǐng)輸出設(shè)備申請(qǐng)輸出設(shè)備申請(qǐng)輸入設(shè)備申請(qǐng)輸入設(shè)備 釋放輸入設(shè)備釋放輸入設(shè)備釋放輸出設(shè)備釋放輸出設(shè)備 釋放輸出設(shè)備釋放輸出設(shè)備釋放輸入設(shè)備釋放輸入設(shè)備 如果執(zhí)行次序?yàn)椋哼M(jìn)程如果執(zhí)行次序?yàn)椋哼M(jìn)程A A進(jìn)程進(jìn)程B B.， 則發(fā)生死鎖。則發(fā)生死鎖。輸入設(shè)備輸

3、出設(shè)備BA占有占有占有占有等待等待等待等待 A在干什么？ B在干什么？競(jìng)爭(zhēng)外設(shè)死鎖示例Operating SystemOperating SystemPage 62022-3-176ABCDELMNOPQFGHIJKAABBCCDDFGHILLMMNNOOFGHISPOOLing系統(tǒng)死鎖示例輸出井進(jìn)程B進(jìn)程C 滿啦！ 不夠！ 不夠！ 不夠！進(jìn)程AOperating SystemOperating SystemPage 72022-3-17q哲學(xué)家進(jìn)餐問(wèn)題（哲學(xué)家進(jìn)餐問(wèn)題（The Dinning Philosophers The Dinning Philosophers ProblemProbl

4、em） v5個(gè)哲學(xué)家坐在桌子邊，桌上有5個(gè)碗和5支筷子v哲家家的生活方式是交替地進(jìn)行思考和進(jìn)餐v哲學(xué)家饑餓時(shí)便拿起兩邊的筷子進(jìn)餐，但只有當(dāng)拿到兩支后才能進(jìn)餐v用餐畢，放下筷子繼續(xù)思考若某時(shí)刻5個(gè)哲學(xué)家同時(shí)拿起一根筷子，都在等待另一根筷子，則會(huì)陷入死鎖。Operating SystemOperating SystemPage 82022-3-17q死鎖的基本概念死鎖的基本概念q產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因q產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件q處理死鎖的基本方法處理死鎖的基本方法Operating SystemOperating Systemq可重用資源：可重復(fù)使用多次，只能互斥使用，且資源數(shù)目

5、固定，如輸入輸入設(shè)備、文件q可消耗資源：可動(dòng)態(tài)創(chuàng)建和消耗，資源數(shù)目變化。如消息通信中的消息q可搶占性資源：如CPU、內(nèi)存q不可搶占性資源：一旦分配不能強(qiáng)行收回，只能等進(jìn)程自行釋放。如：打印機(jī)、磁帶機(jī)Page 92022-3-17Operating SystemOperating SystemPage 102022-3-171. 1.死鎖的定義死鎖的定義 是指多個(gè)進(jìn)程運(yùn)行過(guò)程中因爭(zhēng)奪資源(不可搶占性資源)而造成的一種僵局（Deadly-Embrace），當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無(wú)外力作用，它們將無(wú)法再向前推進(jìn)。 參與死鎖的進(jìn)程最少是兩個(gè)參與死鎖的進(jìn)程最少是兩個(gè) 參與死鎖的所有進(jìn)程都在等待資源

6、參與死鎖的所有進(jìn)程都在等待資源 參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集注：如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)注：如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。崩潰。Operating SystemOperating SystemPage 112022-3-17q死鎖的基本概念死鎖的基本概念q產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因q產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件q處理死鎖的基本方法處理死鎖的基本方法Operating SystemOperating SystemPage 122022-3-173.5.2 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 競(jìng)爭(zhēng)資

7、源競(jìng)爭(zhēng)資源 競(jìng)爭(zhēng)不可搶占式資源(如打印機(jī)、文件)、可消耗資源 系統(tǒng)資源的個(gè)數(shù)系統(tǒng)資源的個(gè)數(shù)并發(fā)進(jìn)程的申請(qǐng)總數(shù)；并發(fā)進(jìn)程的申請(qǐng)總數(shù)；(2) 進(jìn)程間推進(jìn)順序非法進(jìn)程間推進(jìn)順序非法/資源分配不當(dāng)資源分配不當(dāng) 進(jìn)程在運(yùn)行過(guò)程中，請(qǐng)求和釋放資源的順序不當(dāng)，進(jìn)程在運(yùn)行過(guò)程中，請(qǐng)求和釋放資源的順序不當(dāng)，導(dǎo)致了進(jìn)程死鎖。導(dǎo)致了進(jìn)程死鎖。 Operating SystemOperating SystemPage 132022-3-17 若系統(tǒng)中只有一臺(tái)打印機(jī)若系統(tǒng)中只有一臺(tái)打印機(jī)R1R1和一臺(tái)讀卡機(jī)和一臺(tái)讀卡機(jī)R2R2，供進(jìn)，供進(jìn)程程P1P1和和P2P2共享。若資源分配共享。若資源分配形成環(huán)路形成環(huán)路，會(huì)產(chǎn)生死

8、鎖。，會(huì)產(chǎn)生死鎖。R1R2P1P2分配分配分配分配請(qǐng)求請(qǐng)求請(qǐng)求請(qǐng)求Operating SystemOperating SystemPage 142022-3-17q死鎖的基本概念死鎖的基本概念q產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因q產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件q處理死鎖的基本方法處理死鎖的基本方法Operating SystemOperating SystemPage 152022-3-17q 互斥條件互斥條件 v進(jìn)程對(duì)所分配到的資源進(jìn)行進(jìn)程對(duì)所分配到的資源進(jìn)行排它性的使用排它性的使用q 請(qǐng)求和保持條件請(qǐng)求和保持條件 v進(jìn)程已經(jīng)至少進(jìn)程已經(jīng)至少保持了一個(gè)保持了一個(gè)資源，但又提出了新資源，但又提

9、出了新的資源的資源請(qǐng)求請(qǐng)求，而該資源又已被其他進(jìn)程占有，而該資源又已被其他進(jìn)程占有q 不剝奪條件不剝奪條件 v進(jìn)程已獲得的資源在未使用完之前不能被剝奪進(jìn)程已獲得的資源在未使用完之前不能被剝奪q 循環(huán)等待條件循環(huán)等待條件v在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程-資源循環(huán)資源循環(huán)等待的環(huán)形鏈等待的環(huán)形鏈Operating SystemOperating SystemPage 162022-3-17q死鎖的基本概念死鎖的基本概念q產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因q產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件q處理死鎖的基本方法處理死鎖的基本方法Operating SystemOperati

10、ng SystemPage 172022-3-173.5.3 處理死鎖的基本方法處理死鎖的基本方法 目前用于處理死鎖的方法可歸結(jié)為以下四種：目前用于處理死鎖的方法可歸結(jié)為以下四種：1 1、預(yù)防死鎖、預(yù)防死鎖 通過(guò)設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個(gè)通過(guò)設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件，來(lái)防止發(fā)生死鎖。必要條件中的一個(gè)或幾個(gè)條件，來(lái)防止發(fā)生死鎖。2 2、避免死鎖、避免死鎖防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖，防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖，只需在事先加以較弱的限制條件。只需在事先加以較弱的限制條件。Operating SystemOperating

11、 SystemPage 182022-3-173 3、檢測(cè)死鎖、檢測(cè)死鎖 只須檢查系統(tǒng)是否已進(jìn)入不安全區(qū)，允許系只須檢查系統(tǒng)是否已進(jìn)入不安全區(qū)，允許系統(tǒng)在運(yùn)行過(guò)程中發(fā)生死鎖。統(tǒng)在運(yùn)行過(guò)程中發(fā)生死鎖。4 4、 解除死鎖解除死鎖 常用的實(shí)施方法是撤消或掛起一些進(jìn)程，以常用的實(shí)施方法是撤消或掛起一些進(jìn)程，以便回收一些資源，再將這些資源分配給已處于阻便回收一些資源，再將這些資源分配給已處于阻塞狀態(tài)的進(jìn)程，使之轉(zhuǎn)為就緒狀態(tài)，以繼續(xù)運(yùn)行。塞狀態(tài)的進(jìn)程，使之轉(zhuǎn)為就緒狀態(tài)，以繼續(xù)運(yùn)行。Operating SystemOperating SystemPage 192022-3-17q破壞死鎖產(chǎn)生的四個(gè)必要條件的

12、破壞死鎖產(chǎn)生的四個(gè)必要條件的一個(gè)或幾個(gè)一個(gè)或幾個(gè)Operating SystemOperating SystemPage 202022-3-17q打破打破“互斥條件互斥條件” 允許進(jìn)程同時(shí)訪問(wèn)某些資源。（但有些允許進(jìn)程同時(shí)訪問(wèn)某些資源。（但有些資源不可以還應(yīng)該保證互斥訪問(wèn)，如打印資源不可以還應(yīng)該保證互斥訪問(wèn)，如打印機(jī)）機(jī)）Operating SystemOperating SystemPage 212022-3-17q 摒棄摒棄“請(qǐng)求和保持請(qǐng)求和保持”條件條件 所有進(jìn)程在開(kāi)始運(yùn)行之前必須所有進(jìn)程在開(kāi)始運(yùn)行之前必須一次性的一次性的申請(qǐng)申請(qǐng)整個(gè)運(yùn)行過(guò)程所需的全部資源整個(gè)運(yùn)行過(guò)程所需的全部資源v簡(jiǎn)單

13、、易于實(shí)現(xiàn)、安全簡(jiǎn)單、易于實(shí)現(xiàn)、安全v資源浪費(fèi)嚴(yán)重資源浪費(fèi)嚴(yán)重v進(jìn)程延遲運(yùn)行進(jìn)程延遲運(yùn)行Operating SystemOperating SystemPage 222022-3-17q摒棄摒棄“不剝奪不剝奪”條件條件 剝奪那些處于等待狀態(tài)的進(jìn)程的資源（申剝奪那些處于等待狀態(tài)的進(jìn)程的資源（申請(qǐng)新資源而不能得到滿足）請(qǐng)新資源而不能得到滿足）v實(shí)現(xiàn)復(fù)雜、代價(jià)高昂實(shí)現(xiàn)復(fù)雜、代價(jià)高昂v延長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間，還增加了系統(tǒng)延長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間，還增加了系統(tǒng)開(kāi)銷，降低了系統(tǒng)的吞吐量開(kāi)銷，降低了系統(tǒng)的吞吐量Operating SystemOperating SystemPage 232022-3-17q摒棄摒

14、棄“循環(huán)循環(huán)等待等待”條件條件系統(tǒng)將所有資源按類型分配序號(hào)并排隊(duì)系統(tǒng)將所有資源按類型分配序號(hào)并排隊(duì)所有進(jìn)程所有進(jìn)程申請(qǐng)申請(qǐng)資源必須資源必須按序號(hào)按序號(hào)遞增的順序遞增的順序v資源利用率和系統(tǒng)吞吐量較高資源利用率和系統(tǒng)吞吐量較高v但在資源管理和資源申請(qǐng)方面仍有問(wèn)題但在資源管理和資源申請(qǐng)方面仍有問(wèn)題Operating SystemOperating SystemPage 242022-3-17序號(hào)序號(hào)資源資源1輸入機(jī)輸入機(jī)2打印機(jī)打印機(jī)3磁帶機(jī)磁帶機(jī)進(jìn)程進(jìn)程需求資源需求資源P1打印機(jī)打印機(jī)磁帶機(jī)磁帶機(jī)P2磁帶機(jī)磁帶機(jī)打印機(jī)打印機(jī)存在問(wèn)題：資源的需求順序不等于存在問(wèn)題：資源的需求順序不等于序號(hào)，仍存在

15、資源浪費(fèi)。序號(hào)，仍存在資源浪費(fèi)。進(jìn)程的資源需求順序進(jìn)程的資源需求順序資源編號(hào)資源編號(hào)Operating SystemOperating SystemPage 252022-3-17方法方法資源分配策略資源分配策略各種可能模式各種可能模式 主要優(yōu)點(diǎn)主要優(yōu)點(diǎn)主要缺點(diǎn)主要缺點(diǎn)預(yù)防預(yù)防Prevention保守的；寧可資保守的；寧可資源閑置（從機(jī)制源閑置（從機(jī)制上使死鎖條件不上使死鎖條件不成立，即摒棄三成立，即摒棄三個(gè)必要條件）個(gè)必要條件）一次請(qǐng)求所有一次請(qǐng)求所有資源資源適用于作突發(fā)式處理的適用于作突發(fā)式處理的進(jìn)程；不必剝奪進(jìn)程；不必剝奪效率低；進(jìn)程初始化效率低；進(jìn)程初始化時(shí)間延長(zhǎng)時(shí)間延長(zhǎng)剝奪次數(shù)過(guò)多；

16、多次剝奪次數(shù)過(guò)多；多次對(duì)資源重新起動(dòng)對(duì)資源重新起動(dòng)不便靈活申請(qǐng)新資源不便靈活申請(qǐng)新資源資源剝奪資源剝奪適用于狀態(tài)可以保存和適用于狀態(tài)可以保存和恢復(fù)的資源恢復(fù)的資源資源資源按序申請(qǐng)按序申請(qǐng)避免避免Avoidance是是“預(yù)防預(yù)防”和和“檢測(cè)檢測(cè)”的折衷的折衷（在運(yùn)行時(shí)判斷（在運(yùn)行時(shí)判斷是否可能死鎖）是否可能死鎖）尋找可能的安尋找可能的安全的運(yùn)行順序全的運(yùn)行順序 不必進(jìn)行剝奪不必進(jìn)行剝奪使用條件：必須知道使用條件：必須知道將來(lái)的資源需求；進(jìn)將來(lái)的資源需求；進(jìn)程可能會(huì)長(zhǎng)時(shí)間阻塞程可能會(huì)長(zhǎng)時(shí)間阻塞檢測(cè)檢測(cè)Detection寬松的；只要允寬松的；只要允許，就分配資源許，就分配資源定期檢查死鎖定期檢查死鎖

17、是否已經(jīng)發(fā)生是否已經(jīng)發(fā)生不延長(zhǎng)進(jìn)程初始化時(shí)間；不延長(zhǎng)進(jìn)程初始化時(shí)間；允許對(duì)死鎖進(jìn)行現(xiàn)場(chǎng)處允許對(duì)死鎖進(jìn)行現(xiàn)場(chǎng)處理理通過(guò)剝奪解除死鎖，通過(guò)剝奪解除死鎖，造成損失造成損失可以在編譯時(shí)（而不必可以在編譯時(shí)（而不必在運(yùn)行時(shí)）就進(jìn)行檢查在運(yùn)行時(shí)）就進(jìn)行檢查Operating SystemOperating SystemPage 262022-3-17q 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)q利用銀行家算法避免死鎖利用銀行家算法避免死鎖Operating SystemOperating SystemPage 272022-3-17q安全狀態(tài)安全狀態(tài)v系統(tǒng)在進(jìn)行系統(tǒng)在進(jìn)行資源分配之前資源分配之前，先計(jì)算此次資源，先計(jì)算此

18、次資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入入不安全狀態(tài)不安全狀態(tài)，則將資源分配給進(jìn)程；，則將資源分配給進(jìn)程； 否則，否則，令進(jìn)程等待。令進(jìn)程等待。v所謂所謂安全狀態(tài)安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程執(zhí)行，是指系統(tǒng)能按某種進(jìn)程執(zhí)行順序順序(P1, P2, (P1, P2, ，Pn)Pn)順利地完成順利地完成，則系統(tǒng)，則系統(tǒng)處于安全狀態(tài)。處于安全狀態(tài)。執(zhí)行序列執(zhí)行序列P1, P2, P1, P2, , Pn, Pn序列為安全序列序列為安全序列。如果系統(tǒng)無(wú)法找到這樣一。如果系統(tǒng)無(wú)法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。不安全狀態(tài)。

19、Operating SystemOperating SystemPage 282022-3-17 2. 安全狀態(tài)之例安全狀態(tài)之例 假定系統(tǒng)中有三個(gè)進(jìn)程假定系統(tǒng)中有三個(gè)進(jìn)程P P1 1、 P P2 2和和P P3 3，共有，共有1212臺(tái)磁帶機(jī)。臺(tái)磁帶機(jī)。進(jìn)程進(jìn)程P P1 1總共要求總共要求1010臺(tái)磁帶機(jī)，臺(tái)磁帶機(jī)，P P2 2和和P P3 3分別要求分別要求4 4臺(tái)和臺(tái)和9 9臺(tái)。假臺(tái)。假設(shè)在設(shè)在T T0 0時(shí)刻，進(jìn)程時(shí)刻，進(jìn)程P P1 1、P P2 2和和P P3 3已分別獲得已分別獲得5 5臺(tái)、臺(tái)、2 2臺(tái)和臺(tái)和2 2臺(tái)磁臺(tái)磁帶機(jī)，尚有帶機(jī)，尚有3 3臺(tái)空閑未分配，如下表所示：臺(tái)空閑未分

20、配，如下表所示： 29P324P23510P1可 用 已 分 配 最 大 需 求 進(jìn) 程 41 5100109312存在安全序列：存在安全序列：P2-P1-P3，系統(tǒng)處于安全狀態(tài)。，系統(tǒng)處于安全狀態(tài)。Operating SystemOperating SystemPage 292022-3-17 3. 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 但是，若在但是，若在T0時(shí)刻以后，時(shí)刻以后，P3又請(qǐng)求又請(qǐng)求1臺(tái)磁帶機(jī)，臺(tái)磁帶機(jī)， 若此時(shí)系統(tǒng)把剩余若此時(shí)系統(tǒng)把剩余3臺(tái)中的臺(tái)中的1臺(tái)分配給臺(tái)分配給P3，則系統(tǒng)便進(jìn)，則系統(tǒng)便進(jìn)入不安全狀態(tài)。入不安全狀態(tài)。進(jìn) 程 最 大 需 求 已 分 配

21、 可 用 P11053P242P3923240 4不安全狀態(tài)Operating SystemOperating SystemPage 302022-3-17q預(yù)防死鎖預(yù)防死鎖q系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)q利用銀行家算法避免死鎖利用銀行家算法避免死鎖Operating SystemOperating SystemPage 312022-3-173.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖 1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值初始值是系統(tǒng)中

22、所配置的該類全部可用資源的數(shù)目全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Availablej = K，則表示系統(tǒng)中現(xiàn)有，則表示系統(tǒng)中現(xiàn)有Rj類資源類資源K個(gè)。個(gè)。 Operating SystemOperating SystemPage 322022-3-17 (2) 最大需求矩陣最大需求矩陣Max。這是一個(gè)nm的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Maxi,j = K，則表示進(jìn)程，則表示進(jìn)程i需要需要Rj類資源的最大數(shù)目為類資源的最大數(shù)目為K。 (3) 分配矩陣分配矩陣Allocation。這也是一個(gè)nm的矩陣，它定義了系統(tǒng)中每一類資源

23、當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K，表示進(jìn)程，表示進(jìn)程i當(dāng)前已分得當(dāng)前已分得Rj類資源的數(shù)目為類資源的數(shù)目為K。 (4) 需求矩陣需求矩陣Need。這也是一個(gè)nm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Needi,j = K，則表示進(jìn)程，則表示進(jìn)程i還需要還需要Rj類資源類資源K個(gè)，個(gè)，方能完成其任務(wù)。 Needi,j = Maxi,j Allocationi,j Operating SystemOperating SystemPage 332022-3-17 2. 銀行家算法銀行家算法 設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Requestij =

24、K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查： (1) 如果Requestij Needi,j，便轉(zhuǎn)向步驟(2)；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。 (2) 如果Requestij Availablej，便轉(zhuǎn)向步驟(3)；否則， 表示尚無(wú)足夠資源，Pi須等待。 Operating SystemOperating SystemPage 342022-3-17 (3) 系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej := Availablej - Requestij; Allocationi,j :

25、= Allocationi,j + Requestij; Needi,j := Needi,j - Requestij; (4) 系統(tǒng)執(zhí)行安全性算法執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。 Operating SystemOperating SystemPage 352022-3-173. 安全性算法安全性算法 (1) (1) 設(shè)置兩個(gè)向量：設(shè)置兩個(gè)向量： 工作向量Work: 它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開(kāi)始時(shí)

26、，Work := Available; Finish: 它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開(kāi)始時(shí)先做Finishi := false; 當(dāng)有足夠資源分配給進(jìn)程時(shí)， 再令Finishi := true。 Operating SystemOperating SystemPage 362022-3-17 (2) (2) 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi = false; Needi,j Workj； 若找到， 執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。 (3) (3) 當(dāng)進(jìn)程當(dāng)進(jìn)程PiPi獲得資源后，可順利執(zhí)行，直至

27、完成，并釋獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：放出分配給它的資源，故應(yīng)執(zhí)行： Workj := Worki + Allocationi,j; Finishi := true; go to step 2; (4) (4) 如果所有進(jìn)程的如果所有進(jìn)程的Finishi = trueFinishi = true都滿足，都滿足， 則表示系則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 Operating SystemOperating SystemPage 372022-3-174. 銀行家算法之例銀行家算法之例 假定系統(tǒng)中有

28、五個(gè)進(jìn)程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖 3-15 所示。 圖 3-15 T0時(shí)刻的資源分配表 2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMaxNeedi,j = Maxi,j Allocationi,j Operating SystemOperating SystemPage 382022-3-17(1) T0時(shí)刻的安全性： 圖 3-16 T0時(shí)刻的安全序列

29、truetruetruetruetrueFinish77532C54443B02210C10010B30112C40312B75322C44433B100710P07047P45213P110367P27205P3AAAAWork + AllocationAllocationNeedWork存在安全序列：存在安全序列：P1-P3-P4-P2-P0，系統(tǒng)在系統(tǒng)在T0時(shí)刻處于安全狀態(tài)。時(shí)刻處于安全狀態(tài)。Operating SystemOperating SystemPage 392022-3-17 (2) P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查： R

30、equest1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2)MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431Operating SystemOperating SystemPage 402022-3-17 系統(tǒng)先假定可為P1分配資源，并修改Available, Allocation1和Need1向量，由此形成的資源變化情況如圖所示。 Request1(1，0，2) 2C3B110

31、23C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMax322000032Operating SystemOperating SystemPage 412022-3-17 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。 truetruetruetruetrueFinish75532C55443B20212C01010B03110C04312B55320C54433B10367P27047P45302P17077P07205P3AAAAWork + AllocationAllocat

32、ionNeedWork圖 3-17 P1申請(qǐng)資源時(shí)的安全性檢查 存在安全序列：存在安全序列：P1-P3-P4-P0-P2，系統(tǒng)處于安全狀態(tài)，可以滿足系統(tǒng)處于安全狀態(tài)，可以滿足P1資源分配請(qǐng)求。資源分配請(qǐng)求。Operating SystemOperating SystemPage 422022-3-17 (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等待。MaxAllocationNeedAvailab

33、leABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431Operating SystemOperating SystemPage 432022-3-17 (4) P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量Request0(0，2，0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0);MaxAllocationNeedAvailableABCABCABCABCP0753010743230P13223020

34、20P2902302600P3222211011P4433002431Operating SystemOperating SystemPage 442022-3-17 系統(tǒng)暫時(shí)先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖 3-18 所示。 Request0(0，2，0)MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431723210030圖 3-18 為P0分配資源后的有關(guān)資源數(shù)據(jù) 不安全狀態(tài)Operating SystemOperating System

35、Page 452022-3-17 (5) P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量改為Request0(0, 1, 0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request0(0, 1, 0)Need0(7, 4, 3); Request0(0, 1, 0)Available(2, 3, 0);MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431Operating SystemOperating SystemPage 462022-3-17 系統(tǒng)先假定可為P0分配資源，并修

36、改Available, Allocation0和Need0向量，由此形成的資源變化情況如圖所示。 Request0(0, 1, 0) 0C3B11003C31024B21220C01001B32223C32025B404P4639P22707P0022P3033P1AAAAAvailableNeedAllocationMax733220020Operating SystemOperating SystemPage 472022-3-17 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。 truetruetruetruetrueFinish75532C55332B20212C02010B03110C033

37、12B55320C53322B10367P27047P45302P17077P07205P3AAAAWork + AllocationAllocationNeedWork圖 3-17 P1申請(qǐng)資源時(shí)的安全性檢查 存在安全序列：存在安全序列：P1-P3-P4-P0-P2，系統(tǒng)處于安全狀態(tài)，可以滿足系統(tǒng)處于安全狀態(tài)，可以滿足P0資源分配請(qǐng)求。資源分配請(qǐng)求。Operating SystemOperating SystemPage 482022-3-17作業(yè)：作業(yè)：系統(tǒng)某時(shí)刻的資源分配情況如下：系統(tǒng)某時(shí)刻的資源分配情況如下： 資資源源進(jìn)程進(jìn)程Allocation NeedAvailableA B CA

38、 B CA B CP1P2P3P4P53 1 10 0 01 1 01 0 10 0 01 0 00 1 23 0 00 1 02 1 01 2 0試問(wèn)：試問(wèn)：1)該狀態(tài)是否安全？該狀態(tài)是否安全？ 2) 若進(jìn)程若進(jìn)程P2提出請(qǐng)求提出請(qǐng)求request2(0,1,0)，系統(tǒng)能否將資源，系統(tǒng)能否將資源分配給它？分配給它？ 3)若進(jìn)程若進(jìn)程P5提出請(qǐng)求提出請(qǐng)求request5(0,1,0),能否分配？能否分配？Operating SystemOperating SystemPage 492022-3-17q處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 q調(diào)度算法調(diào)度算法 q實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 q多處理機(jī)系

39、統(tǒng)中的調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度q死鎖概述死鎖概述q預(yù)防死鎖的方法預(yù)防死鎖的方法q避免死鎖避免死鎖 q死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除Operating SystemOperating SystemPage 502022-3-17q死鎖的檢測(cè)死鎖的檢測(cè)q死鎖的解除死鎖的解除Operating SystemOperating SystemPage 512022-3-17 允許死鎖發(fā)生，操作系統(tǒng)不斷監(jiān)視系統(tǒng)允許死鎖發(fā)生，操作系統(tǒng)不斷監(jiān)視系統(tǒng)進(jìn)展情況，判斷死鎖是否發(fā)生進(jìn)展情況，判斷死鎖是否發(fā)生 一旦死鎖發(fā)生則采取專門的措施，解除一旦死鎖發(fā)生則采取專門的措施，解除死鎖并以最小的代價(jià)恢復(fù)操作系統(tǒng)運(yùn)行死鎖并

40、以最小的代價(jià)恢復(fù)操作系統(tǒng)運(yùn)行Operating SystemOperating SystemPage 522022-3-17q資源分配圖資源分配圖v表示法表示法: :資源類資源類: :用方框表示（資用方框表示（資源的不同類型）源的不同類型）資源實(shí)例資源實(shí)例: :用方框中的圓用方框中的圓點(diǎn)表示（存在于每個(gè)資點(diǎn)表示（存在于每個(gè)資源中）源中） 進(jìn)程進(jìn)程 : :用圓圈中加進(jìn)程名用圓圈中加進(jìn)程名表示表示分配邊：分配邊：資源實(shí)例資源實(shí)例進(jìn)程進(jìn)程的一條有向邊的一條有向邊申請(qǐng)邊：申請(qǐng)邊：進(jìn)程進(jìn)程資源類的資源類的一條有向邊一條有向邊P1P2r1r2獲得獲得申請(qǐng)申請(qǐng)Operating SystemOperatin

41、g SystemPage 532022-3-17q死鎖定理死鎖定理 如果資源分配圖中沒(méi)有環(huán)路，則系統(tǒng)如果資源分配圖中沒(méi)有環(huán)路，則系統(tǒng)中沒(méi)有死鎖，如果圖中存在環(huán)路則系統(tǒng)中中沒(méi)有死鎖，如果圖中存在環(huán)路則系統(tǒng)中可能存在死鎖?？赡艽嬖谒梨i。 如果如果每個(gè)資源類中只包含一個(gè)資源實(shí)每個(gè)資源類中只包含一個(gè)資源實(shí)例例，則環(huán)路是死鎖存在的充分必要條件。，則環(huán)路是死鎖存在的充分必要條件。Operating SystemOperating SystemPage 542022-3-17q死鎖定理死鎖定理有環(huán)有死鎖有環(huán)有死鎖Operating SystemOperating SystemPage 552022-3-17

42、q死鎖定理死鎖定理有環(huán)無(wú)死鎖有環(huán)無(wú)死鎖Operating SystemOperating SystemPage 562022-3-17q死鎖定理死鎖定理資源分配圖化簡(jiǎn)資源分配圖化簡(jiǎn)v找出一個(gè)既不阻塞又非獨(dú)立的進(jìn)程結(jié)點(diǎn)找出一個(gè)既不阻塞又非獨(dú)立的進(jìn)程結(jié)點(diǎn)pipi，在順利，在順利的情況下的情況下pipi可獲得資源而繼續(xù)運(yùn)行，再釋放所有資可獲得資源而繼續(xù)運(yùn)行，再釋放所有資源。消去源。消去pipi所有的請(qǐng)求邊和分配邊，將其變?yōu)楣铝⑺械恼?qǐng)求邊和分配邊，將其變?yōu)楣铝⒔Y(jié)點(diǎn)結(jié)點(diǎn)v再把相應(yīng)的資源分配給一個(gè)等待該資源的進(jìn)程，即再把相應(yīng)的資源分配給一個(gè)等待該資源的進(jìn)程，即將某進(jìn)程的申請(qǐng)邊變?yōu)榉峙溥厡⒛尺M(jìn)程的申請(qǐng)邊變

43、為分配邊v在進(jìn)行一系列化簡(jiǎn)后若能消去圖中所有的邊，使所在進(jìn)行一系列化簡(jiǎn)后若能消去圖中所有的邊，使所有進(jìn)程結(jié)點(diǎn)成為孤立結(jié)點(diǎn)，則稱該圖是有進(jìn)程結(jié)點(diǎn)成為孤立結(jié)點(diǎn)，則稱該圖是可完全簡(jiǎn)化可完全簡(jiǎn)化的的；否則是；否則是不可完全簡(jiǎn)化的不可完全簡(jiǎn)化的vS S為死鎖的充分條件是：為死鎖的充分條件是：當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)S S狀態(tài)的資源分配狀態(tài)的資源分配圖是不可完全簡(jiǎn)化的圖是不可完全簡(jiǎn)化的。該充分條件稱為。該充分條件稱為死鎖定理死鎖定理Operating SystemOperating SystemPage 572022-3-17q死鎖定理死鎖定理資源分配圖的簡(jiǎn)化資源分配圖的簡(jiǎn)化 Operating SystemOp

44、erating SystemPage 582022-3-17q死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu) v可利用資源向量可利用資源向量AvailableAvailable它表示了它表示了m m類資源中每一類資源的可用類資源中每一類資源的可用數(shù)目數(shù)目v把不占用資源的進(jìn)程把不占用資源的進(jìn)程( (向量向量Allocation:=0Allocation:=0) )記入記入L L表中，表中， 即即LiLLiLv從進(jìn)程集合中找到一個(gè)從進(jìn)程集合中找到一個(gè)RequestRequesti iWorkWork的的進(jìn)程，做如下處理：進(jìn)程，做如下處理： 將其資源分配圖簡(jiǎn)化，釋放出資源，將其資源分配圖簡(jiǎn)化，釋放出資源，增加工作向量增加工作向量Work=Work+AllocationWork=Wo