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

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

2、爭輔存空間q哲學家進餐問題哲學家進餐問題Operating SystemOperating SystemPage 42022-3-17交通死鎖的示例讓路！讓路！ 讓路！ 讓路！Operating SystemOperating SystemPage 52022-3-17進程進程A A進程進程B B 申請輸入設(shè)備申請輸入設(shè)備申請輸出設(shè)備申請輸出設(shè)備 申請輸出設(shè)備申請輸出設(shè)備申請輸入設(shè)備申請輸入設(shè)備 釋放輸入設(shè)備釋放輸入設(shè)備釋放輸出設(shè)備釋放輸出設(shè)備 釋放輸出設(shè)備釋放輸出設(shè)備釋放輸入設(shè)備釋放輸入設(shè)備 如果執(zhí)行次序為：進程如果執(zhí)行次序為：進程A A進程進程B B.， 則發(fā)生死鎖。則發(fā)生死鎖。輸入設(shè)備輸

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

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

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

6、參與死鎖的所有進程都在等待資源 參與死鎖的進程是當前系統(tǒng)中所有進程的子集參與死鎖的進程是當前系統(tǒng)中所有進程的子集注：如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，甚至導致系統(tǒng)注：如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，甚至導致系統(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)生死鎖的原因 競爭資

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

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

9、出了新的資源的資源請求請求，而該資源又已被其他進程占有，而該資源又已被其他進程占有q 不剝奪條件不剝奪條件 v進程已獲得的資源在未使用完之前不能被剝奪進程已獲得的資源在未使用完之前不能被剝奪q 循環(huán)等待條件循環(huán)等待條件v在發(fā)生死鎖時，必然存在一個進程在發(fā)生死鎖時，必然存在一個進程-資源循環(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ù)防死鎖 通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件，來防止發(fā)生死鎖。必要條件中的一個或幾個條件，來防止發(fā)生死鎖。2 2、避免死鎖、避免死鎖防止系統(tǒng)進入不安全狀態(tài)，從而避免發(fā)生死鎖，防止系統(tǒng)進入不安全狀態(tài)，從而避免發(fā)生死鎖，只需在事先加以較弱的限制條件。只需在事先加以較弱的限制條件。Operating SystemOperating

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

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

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

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

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

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

17、是否已經(jīng)發(fā)生是否已經(jīng)發(fā)生不延長進程初始化時間；不延長進程初始化時間；允許對死鎖進行現(xiàn)場處允許對死鎖進行現(xià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)在進行系統(tǒng)在進行資源分配之前資源分配之前，先計算此次資源，先計算此

18、次資源分配的安全性。若此次分配不會導致系統(tǒng)進分配的安全性。若此次分配不會導致系統(tǒng)進入入不安全狀態(tài)不安全狀態(tài)，則將資源分配給進程；，則將資源分配給進程； 否則，否則，令進程等待。令進程等待。v所謂所謂安全狀態(tài)安全狀態(tài)，是指系統(tǒng)能按某種進程執(zhí)行，是指系統(tǒng)能按某種進程執(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)無法找到這樣一。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。不安全狀態(tài)。

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

20、配，如下表所示： 29P324P23510P1可 用 已 分 配 最 大 需 求 進 程 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時刻以后，時刻以后，P3又請求又請求1臺磁帶機，臺磁帶機， 若此時系統(tǒng)把剩余若此時系統(tǒng)把剩余3臺中的臺中的1臺分配給臺分配給P3，則系統(tǒng)便進，則系統(tǒng)便進入不安全狀態(tài)。入不安全狀態(tài)。進 程 最 大 需 求 已 分 配

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。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值初始值是系統(tǒng)中

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

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

24、K，表示進程Pi需要K個Rj類型的資源。當Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查： (1) 如果Requestij Needi,j，便轉(zhuǎn)向步驟(2)；否則認為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。 (2) 如果Requestij Availablej，便轉(zhuǎn)向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。 Operating SystemOperating SystemPage 342022-3-17 (3) 系統(tǒng)試探著把資源分配給進程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)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。 Operating SystemOperating SystemPage 352022-3-173. 安全性算法安全性算法 (1) (1) 設(shè)置兩個向量：設(shè)置兩個向量： 工作向量Work: 它表示系統(tǒng)可提供給進程繼續(xù)運行的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時

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

27、完成，并釋獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：放出分配給它的資源，故應(yīng)執(zhí)行： Workj := Worki + Allocationi,j; Finishi := true; go to step 2; (4) (4) 如果所有進程的如果所有進程的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、五個進程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖 3-15 所示。 圖 3-15 T0時刻的資源分配表 2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMaxNeedi,j = Maxi,j Allocationi,j Operating SystemOperating SystemPage 382022-3-17(1) T0時刻的安全性： 圖 3-16 T0時刻的安全序列

29、truetruetruetruetrueFinish77532C54443B02210C10010B30112C40312B75322C44433B100710P07047P45213P110367P27205P3AAAAWork + AllocationAllocationNeedWork存在安全序列：存在安全序列：P1-P3-P4-P2-P0，系統(tǒng)在系統(tǒng)在T0時刻處于安全狀態(tài)。時刻處于安全狀態(tài)。Operating SystemOperating SystemPage 392022-3-17 (2) P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進行檢查： 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 再利用安全性算法檢查此時系統(tǒng)是否安全。 truetruetruetruetrueFinish75532C55443B20212C01010B03110C04312B55320C54433B10367P27047P45302P17077P07205P3AAAAWork + AllocationAllocat

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

33、leABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431Operating SystemOperating SystemPage 432022-3-17 (4) P0請求資源：P0發(fā)出請求向量Request0(0，2，0)，系統(tǒng)按銀行家算法進行檢查： 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)暫時先假定可為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請求資源：P0發(fā)出請求向量改為Request0(0, 1, 0)，系統(tǒng)按銀行家算法進行檢查： 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 再利用安全性算法檢查此時系統(tǒng)是否安全。 truetruetruetruetrueFinish75532C55332B20212C02010B03110C033

37、12B55320C53322B10367P27047P45302P17077P07205P3AAAAWork + AllocationAllocationNeedWork圖 3-17 P1申請資源時的安全性檢查 存在安全序列：存在安全序列：P1-P3-P4-P0-P2，系統(tǒng)處于安全狀態(tài)，可以滿足系統(tǒng)處于安全狀態(tài)，可以滿足P0資源分配請求。資源分配請求。Operating SystemOperating SystemPage 482022-3-17作業(yè)：作業(yè)：系統(tǒng)某時刻的資源分配情況如下：系統(tǒng)某時刻的資源分配情況如下： 資資源源進程進程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試問：試問：1)該狀態(tài)是否安全？該狀態(tài)是否安全？ 2) 若進程若進程P2提出請求提出請求request2(0,1,0)，系統(tǒng)能否將資源，系統(tǒng)能否將資源分配給它？分配給它？ 3)若進程若進程P5提出請求提出請求request5(0,1,0),能否分配？能否分配？Operating SystemOperating SystemPage 492022-3-17q處理機調(diào)度的基本概念處理機調(diào)度的基本概念 q調(diào)度算法調(diào)度算法 q實時調(diào)度實時調(diào)度 q多處理機系

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

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

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

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

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

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