操作系統(tǒng)期末大題

1、一一 同步與互斥問(wèn)題同步與互斥問(wèn)題 分析題意，確定同步、互斥或同步與互斥問(wèn)題。分析題意，確定同步、互斥或同步與互斥問(wèn)題。 設(shè)信號(hào)量，給出信號(hào)量表示的含義（公用，私用）設(shè)信號(hào)量，給出信號(hào)量表示的含義（公用，私用）和初始值。和初始值。 描述算法，注意死鎖問(wèn)題。描述算法，注意死鎖問(wèn)題。把一個(gè)長(zhǎng)度為把一個(gè)長(zhǎng)度為n的有界緩沖區(qū)的有界緩沖區(qū)(n0)與一群生產(chǎn)者進(jìn)程與一群生產(chǎn)者進(jìn)程P1，P2，Pm和一群消費(fèi)者進(jìn)程和一群消費(fèi)者進(jìn)程C1，C2，Ck聯(lián)聯(lián)系起來(lái)系起來(lái) 3.6.4 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 設(shè)生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程是設(shè)生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程是互相等效互相等效的，其中，各生產(chǎn)者進(jìn)程的，其中，各

2、生產(chǎn)者進(jìn)程使用的過(guò)程使用的過(guò)程deposit(data)和各消費(fèi)者使用的過(guò)程和各消費(fèi)者使用的過(guò)程remove(data)可可描述如下：描述如下：1. 首先首先生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題是一個(gè)消費(fèi)者問(wèn)題是一個(gè)同步問(wèn)題同步問(wèn)題。即生產(chǎn)者和消費(fèi)者。即生產(chǎn)者和消費(fèi)者之間滿足如下條件：之間滿足如下條件： 1)消費(fèi)者想消費(fèi)者想接收數(shù)據(jù)接收數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有時(shí)，有界緩沖區(qū)中至少有一個(gè)一個(gè)單元是單元是滿的滿的 2)生產(chǎn)者想生產(chǎn)者想發(fā)送數(shù)據(jù)發(fā)送數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有時(shí)，有界緩沖區(qū)中至少有一個(gè)一個(gè)單元是單元是空的空的2. 由于有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進(jìn)程和各消費(fèi)者由于有界緩沖區(qū)是臨界資源，因此

3、，各生產(chǎn)者進(jìn)程和各消費(fèi)者進(jìn)程之間進(jìn)程之間必須互斥執(zhí)行必須互斥執(zhí)行。 3.6.4 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 公用信號(hào)量公用信號(hào)量mutex，保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間的互斥，保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間的互斥，表示表示可用有界緩沖區(qū)的個(gè)數(shù)，可用有界緩沖區(qū)的個(gè)數(shù)，初值為初值為1；信號(hào)量信號(hào)量avail為生產(chǎn)者進(jìn)程的私用信號(hào)量，為生產(chǎn)者進(jìn)程的私用信號(hào)量，表示表示有界緩沖區(qū)中的有界緩沖區(qū)中的空單元個(gè)數(shù)，空單元個(gè)數(shù)，初值為初值為n； 信號(hào)量信號(hào)量full為消費(fèi)者進(jìn)程的私用信號(hào)量，為消費(fèi)者進(jìn)程的私用信號(hào)量，表示表示有界緩沖區(qū)中非空有界緩沖區(qū)中非空單元個(gè)數(shù)，單元個(gè)數(shù)，初值為初值為0。從而有：從

4、而有： 3.6.4 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 deposit(data)： begin P(avail) P(mutex) 送數(shù)據(jù)入緩沖區(qū)某單元送數(shù)據(jù)入緩沖區(qū)某單元 V(full) V(mutex) End remove(data)： begin P(full) P(mutex) 取緩沖區(qū)中某單元數(shù)據(jù)取緩沖區(qū)中某單元數(shù)據(jù) V(avail) V(mutex) end 3.6.4 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 哲學(xué)家就餐問(wèn)題哲學(xué)家就餐問(wèn)題 有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每?jī)扇酥g放一只筷子每人面前有

5、一只空盤子，每?jī)扇酥g放一只筷子 每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉 為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩只筷子，并且為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩只筷子，并且每個(gè)人只能直接從自己的左邊或右邊去取筷子每個(gè)人只能直接從自己的左邊或右邊去取筷子設(shè)設(shè)fork5為為5 個(gè)信號(hào)量，初值為均個(gè)信號(hào)量，初值為均1, forki 表示表示i號(hào)筷子被拿號(hào)筷子被拿（i= 0， 1， 2， 3， 4）Philosopheri：while (1) 思考；思考； P(forki); P(fork(i+1) % 5)； 進(jìn)食；進(jìn)食； V(forki); V(fo

6、rk(i+1) % 5)；解解以上解法會(huì)出現(xiàn)死鎖，為防止死鎖發(fā)生可采取的措施：以上解法會(huì)出現(xiàn)死鎖，為防止死鎖發(fā)生可采取的措施： 最多允許最多允許4 4個(gè)哲學(xué)家同時(shí)坐在桌子周圍個(gè)哲學(xué)家同時(shí)坐在桌子周圍 僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子拿筷子 給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿左邊給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反之。的筷子，偶數(shù)號(hào)的哲學(xué)家則反之。 分分 析析 設(shè)設(shè)fork5為為5 個(gè)信號(hào)量個(gè)信號(hào)量, 初值為均初值為均1， forki 表表示示i號(hào)筷子被拿號(hào)筷子被拿 設(shè)信號(hào)量設(shè)信號(hào)量S

7、，初值為，初值為4 S用于封鎖第用于封鎖第5個(gè)哲學(xué)家個(gè)哲學(xué)家無(wú)死鎖哲學(xué)家就餐問(wèn)題無(wú)死鎖哲學(xué)家就餐問(wèn)題 解解1 1Philosopheri：while (1) 思考； P(S)P(forki); P(fork(i+1) % 5)； 進(jìn)食；V(forki); V(fork(i+1) % 5)； V(S)設(shè)設(shè)fork5為為5 個(gè)信號(hào)量，初值為均個(gè)信號(hào)量，初值為均1， forki 表示表示i號(hào)筷子被拿號(hào)筷子被拿無(wú)死鎖哲學(xué)家就餐問(wèn)題無(wú)死鎖哲學(xué)家就餐問(wèn)題 解解2 2Philosopheri：Beginif i mod 2 = 0then 思考；思考；P(forki); P(forki+1 mod 5)；

8、進(jìn)食；進(jìn)食；V(forki); V(forki+1mod 5)；else 思考；思考；P(forki+1 mod 5); P(forki)； 進(jìn)食；進(jìn)食；V(forki+1 mod 5); V(forki)；二二 作業(yè)調(diào)度作業(yè)調(diào)度 畫表格計(jì)算周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間畫表格計(jì)算周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間 給出作業(yè)（進(jìn)程）調(diào)度序列給出作業(yè)（進(jìn)程）調(diào)度序列 計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間4.4 調(diào)度算法調(diào)度算法 思想：思想：按作業(yè)和就緒進(jìn)程來(lái)到的次序進(jìn)行調(diào)度。這按作業(yè)和就緒進(jìn)程來(lái)到的次序進(jìn)行調(diào)度。這種算法優(yōu)先考慮在系統(tǒng)中等待時(shí)間最長(zhǎng)的作業(yè)，而種算法優(yōu)先考慮在系統(tǒng)中等待

9、時(shí)間最長(zhǎng)的作業(yè)，而不管它要求運(yùn)行時(shí)間的長(zhǎng)短。不管它要求運(yùn)行時(shí)間的長(zhǎng)短。 優(yōu)點(diǎn)：優(yōu)點(diǎn)：算法簡(jiǎn)單，公平，容易實(shí)現(xiàn)算法簡(jiǎn)單，公平，容易實(shí)現(xiàn) 缺點(diǎn)：缺點(diǎn)：對(duì)于短作業(yè)或短進(jìn)程，等待時(shí)間長(zhǎng)對(duì)于短作業(yè)或短進(jìn)程，等待時(shí)間長(zhǎng)作業(yè)調(diào)度算法作業(yè)調(diào)度算法FCFS（First come first serve）4.4 調(diào)度算法調(diào)度算法作業(yè)調(diào)度算法作業(yè)調(diào)度算法FCFS下面是下面是4 4個(gè)作業(yè)在系統(tǒng)中從提交、運(yùn)行的信息。個(gè)作業(yè)在系統(tǒng)中從提交、運(yùn)行的信息。作業(yè)作業(yè)提交提交時(shí)間時(shí)間運(yùn)行運(yùn)行時(shí)間時(shí)間開(kāi)始開(kāi)始時(shí)間時(shí)間完成完成時(shí)間時(shí)間周轉(zhuǎn)周轉(zhuǎn)時(shí)間時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間18228.50.5390.149.50.2平均周轉(zhuǎn)時(shí)間：平

10、均周轉(zhuǎn)時(shí)間：T=1.725 T=1.725 平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間W=6.875W=6.87581010.510.610 10.5 10.6 10.8 221.61.314166.54.4 調(diào)度算法調(diào)度算法 思想：思想：比較作業(yè)緩沖區(qū)中的作業(yè)預(yù)計(jì)的運(yùn)行時(shí)間，比較作業(yè)緩沖區(qū)中的作業(yè)預(yù)計(jì)的運(yùn)行時(shí)間，選擇選擇預(yù)計(jì)時(shí)間最短的作業(yè)預(yù)計(jì)時(shí)間最短的作業(yè)進(jìn)入運(yùn)行狀態(tài)。進(jìn)入運(yùn)行狀態(tài)。 優(yōu)點(diǎn)：優(yōu)點(diǎn)：算法簡(jiǎn)單，可得到最大系統(tǒng)吞吐率，效率高。算法簡(jiǎn)單，可得到最大系統(tǒng)吞吐率，效率高。 缺點(diǎn)：缺點(diǎn)：主要問(wèn)題是對(duì)長(zhǎng)作業(yè)不利，如果系統(tǒng)不斷地主要問(wèn)題是對(duì)長(zhǎng)作業(yè)不利，如果系統(tǒng)不斷地接收短作業(yè)，就會(huì)使長(zhǎng)作業(yè)長(zhǎng)時(shí)間等待。接

11、收短作業(yè)，就會(huì)使長(zhǎng)作業(yè)長(zhǎng)時(shí)間等待。短作業(yè)優(yōu)先算法短作業(yè)優(yōu)先算法SJF （shortest job first）4.4 調(diào)度算法調(diào)度算法短作業(yè)優(yōu)先算法短作業(yè)優(yōu)先算法SJF作業(yè)作業(yè)提交提交時(shí)間時(shí)間運(yùn)行運(yùn)行時(shí)間時(shí)間開(kāi)始開(kāi)始時(shí)間時(shí)間完成完成時(shí)間時(shí)間周轉(zhuǎn)周轉(zhuǎn)時(shí)間時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間18228.50.5390.149.50.2平均周轉(zhuǎn)時(shí)間：平均周轉(zhuǎn)時(shí)間：T=1.55 T=1.55 平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間W=5.15W=5.15810.31010.110 10.8 10.1 10.3 22.31.10.814.61144.4 調(diào)度算法調(diào)度算法響應(yīng)比響應(yīng)比=響應(yīng)時(shí)間響應(yīng)時(shí)間/預(yù)計(jì)執(zhí)行時(shí)間預(yù)計(jì)

12、執(zhí)行時(shí)間 響應(yīng)時(shí)間響應(yīng)時(shí)間=等待時(shí)間等待時(shí)間+預(yù)計(jì)執(zhí)行時(shí)間預(yù)計(jì)執(zhí)行時(shí)間 所以響應(yīng)比為：所以響應(yīng)比為：1+作業(yè)等待時(shí)間作業(yè)等待時(shí)間/預(yù)計(jì)執(zhí)行時(shí)間預(yù)計(jì)執(zhí)行時(shí)間 思想思想：當(dāng)需要從就緒隊(duì)列中選擇進(jìn)程投入運(yùn)行時(shí)，先計(jì)算每：當(dāng)需要從就緒隊(duì)列中選擇進(jìn)程投入運(yùn)行時(shí)，先計(jì)算每個(gè)進(jìn)程的個(gè)進(jìn)程的響應(yīng)響應(yīng)比，選擇比，選擇響應(yīng)響應(yīng)比最高的進(jìn)程運(yùn)行比最高的進(jìn)程運(yùn)行 優(yōu)點(diǎn)優(yōu)點(diǎn)：短作業(yè)響應(yīng)比高，執(zhí)行時(shí)間短；長(zhǎng)作業(yè)響應(yīng)比隨著等：短作業(yè)響應(yīng)比高，執(zhí)行時(shí)間短；長(zhǎng)作業(yè)響應(yīng)比隨著等待時(shí)間增加而提高，不會(huì)過(guò)長(zhǎng)等待。既照顧了短作業(yè)、也考待時(shí)間增加而提高，不會(huì)過(guò)長(zhǎng)等待。既照顧了短作業(yè)、也考慮到了長(zhǎng)作業(yè)。慮到了長(zhǎng)作業(yè)。 缺點(diǎn)缺點(diǎn)：每次調(diào)度前

13、計(jì)算響應(yīng)比增加了系統(tǒng)開(kāi)銷。：每次調(diào)度前計(jì)算響應(yīng)比增加了系統(tǒng)開(kāi)銷。最高響應(yīng)比優(yōu)先最高響應(yīng)比優(yōu)先HRN（highest response-ratio next）4.4 調(diào)度算法調(diào)度算法作業(yè)作業(yè)提交提交時(shí)間時(shí)間運(yùn)行運(yùn)行時(shí)間時(shí)間開(kāi)始開(kāi)始時(shí)間時(shí)間完成完成時(shí)間時(shí)間周轉(zhuǎn)周轉(zhuǎn)時(shí)間時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間18228.50.5390.149.50.20平均周轉(zhuǎn)時(shí)間：平均周轉(zhuǎn)時(shí)間：T=1.625 W=5.675最高響應(yīng)比優(yōu)先最高響應(yīng)比優(yōu)先HRN810.11010.610 10.6 10.1 10.8 22.11.11.314.2116.5三三 地址映射地址映射 根據(jù)公式計(jì)算邏輯地址的頁(yè)號(hào)和頁(yè)內(nèi)地址根據(jù)公式計(jì)算邏

14、輯地址的頁(yè)號(hào)和頁(yè)內(nèi)地址 p=intA/L d=A mod L 根據(jù)頁(yè)表查找頁(yè)面號(hào)。根據(jù)頁(yè)表查找頁(yè)面號(hào)。 頁(yè)面號(hào)乘以頁(yè)長(zhǎng)頁(yè)面號(hào)乘以頁(yè)長(zhǎng)，加上位移量（加上位移量（d）計(jì)算邏計(jì)算邏輯地址輯地址 多次計(jì)算直到找到數(shù)據(jù)、指令為止。多次計(jì)算直到找到數(shù)據(jù)、指令為止。邏輯空間邏輯空間上的上的地址地址為：頁(yè)號(hào)為：頁(yè)號(hào)+頁(yè)內(nèi)地址，頁(yè)內(nèi)的頁(yè)內(nèi)地址，頁(yè)內(nèi)的地址空間是連續(xù)的，頁(yè)之間不必連續(xù)。地址空間是連續(xù)的，頁(yè)之間不必連續(xù)。199100頁(yè)號(hào)p頁(yè)內(nèi)地址d如果給定的邏輯地址是如果給定的邏輯地址是A，頁(yè)面大小是，頁(yè)面大小是L，則，則頁(yè)頁(yè) 號(hào)號(hào)p和和頁(yè)內(nèi)地址頁(yè)內(nèi)地址d可以按以下公式求得：可以按以下公式求得： p=intA/L

15、d=A mod L例例：邏輯地址：邏輯地址100 頁(yè)面大小頁(yè)面大小 1k 5.4.1 頁(yè)式管理的基本原理頁(yè)式管理的基本原理5.4.2 靜態(tài)頁(yè)面管理靜態(tài)頁(yè)面管理地址變換：地址變換：根據(jù)邏輯空間的頁(yè)號(hào)，查找頁(yè)表對(duì)應(yīng)項(xiàng)找到對(duì)應(yīng)的根據(jù)邏輯空間的頁(yè)號(hào)，查找頁(yè)表對(duì)應(yīng)項(xiàng)找到對(duì)應(yīng)的物理頁(yè)面號(hào)，物理頁(yè)面號(hào)，頁(yè)面號(hào)乘以頁(yè)長(zhǎng)頁(yè)面號(hào)乘以頁(yè)長(zhǎng)，加上位移量（頁(yè)內(nèi)加上位移量（頁(yè)內(nèi)地址）地址）就是物理地址。每個(gè)作業(yè)的邏輯地址是連續(xù)就是物理地址。每個(gè)作業(yè)的邏輯地址是連續(xù)的，重定位到內(nèi)存空間后就不一定連續(xù)了。的，重定位到內(nèi)存空間后就不一定連續(xù)了。變換過(guò)程全部由變換過(guò)程全部由硬件硬件地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)自動(dòng)完成自動(dòng)完成。 5.

16、4.2 靜態(tài)頁(yè)面管理靜態(tài)頁(yè)面管理地址變換：地址變換： 請(qǐng)求表請(qǐng)求表中讀出中讀出MOV r1，2500虛地址為虛地址為100 8*1024+452=8644 四四 頁(yè)面置換頁(yè)面置換 根據(jù)引用頁(yè)面序列畫出頁(yè)面置換圖根據(jù)引用頁(yè)面序列畫出頁(yè)面置換圖 給出被置換頁(yè)面序列，調(diào)入內(nèi)存頁(yè)面序列給出被置換頁(yè)面序列，調(diào)入內(nèi)存頁(yè)面序列 計(jì)算缺頁(yè)次數(shù)，缺頁(yè)率，命中率計(jì)算缺頁(yè)次數(shù)，缺頁(yè)率，命中率5.4.4 請(qǐng)求頁(yè)式管理的置換算法請(qǐng)求頁(yè)式管理的置換算法先進(jìn)先出算法先進(jìn)先出算法(FIFO- First Input First Output）, 先進(jìn)入內(nèi)存的頁(yè)面先淘汰。先進(jìn)入內(nèi)存的頁(yè)面先淘汰。 優(yōu)點(diǎn)優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單。：實(shí)現(xiàn)簡(jiǎn)單

17、。 缺點(diǎn)缺點(diǎn)：常用的頁(yè)會(huì)被淘汰。：常用的頁(yè)會(huì)被淘汰。缺頁(yè)率缺頁(yè)率15/20=75%123412512345111444555555222111113333332222244123412512345111111555544222222111153333332222444444333Belady現(xiàn)象現(xiàn)象：分配給一個(gè)進(jìn)程的：分配給一個(gè)進(jìn)程的頁(yè)面增加，反而出現(xiàn)缺頁(yè)增頁(yè)面增加，反而出現(xiàn)缺頁(yè)增加的現(xiàn)象加的現(xiàn)象5.4.4 請(qǐng)求頁(yè)式管理的置換算法請(qǐng)求頁(yè)式管理的置換算法缺頁(yè)率為缺頁(yè)率為9/12=75%缺頁(yè)率缺頁(yè)率=10/12=83.3%原因是原因是沒(méi)有考慮頁(yè)的執(zhí)行順序沒(méi)有考慮頁(yè)的執(zhí)行順序5.4.4 請(qǐng)求頁(yè)式管理

18、的置換算法請(qǐng)求頁(yè)式管理的置換算法最優(yōu)淘汰算法（OPT-Optimal replacement algorithm）：是理想算法。系統(tǒng)預(yù)測(cè)作業(yè)將要訪問(wèn)的頁(yè)面。淘汰預(yù)測(cè)不被訪問(wèn)或長(zhǎng)時(shí)間后才被訪問(wèn)中的頁(yè)面。缺頁(yè)率缺頁(yè)率9/20=45%幾乎無(wú)法實(shí)現(xiàn)幾乎無(wú)法實(shí)現(xiàn)!5.4.4 請(qǐng)求頁(yè)式管理的置換算法請(qǐng)求頁(yè)式管理的置換算法最近最近最久未使用頁(yè)面淘汰法（LRU - Least Recently Used）： 淘汰最近一段時(shí)間最久沒(méi)訪問(wèn)的頁(yè)面。 缺點(diǎn)：每頁(yè)設(shè)訪問(wèn)記錄，每次更新，系統(tǒng)開(kāi)銷大。缺頁(yè)率缺頁(yè)率12/20=60%五五 死鎖避免死鎖避免 先驗(yàn)證系統(tǒng)初始狀態(tài)的安全性，找出安全先驗(yàn)證系統(tǒng)初始狀態(tài)的安全性，找出安

19、全序列。序列。 根據(jù)申請(qǐng)資源情況，結(jié)合剩余資源檢查申根據(jù)申請(qǐng)資源情況，結(jié)合剩余資源檢查申請(qǐng)合理性。請(qǐng)合理性。 驗(yàn)證分配后系統(tǒng)安全性，給出安全序列，驗(yàn)證分配后系統(tǒng)安全性，給出安全序列，否則不能分配資源給相應(yīng)進(jìn)程。否則不能分配資源給相應(yīng)進(jìn)程。銀行家算法實(shí)例銀行家算法實(shí)例 假定系統(tǒng)有四個(gè)進(jìn)程假定系統(tǒng)有四個(gè)進(jìn)程P1,P2,P3,P4,三種類型的資三種類型的資源源R1,R2,R3,數(shù)量分別為數(shù)量分別為9，3，6，在，在T0時(shí)刻時(shí)刻的的資源分配情況如下：資源分配情況如下：ProcessMaxallocatedNeed FinishAvailableP13/2/21/0/02/2/2 false1/1/2P

20、26/1/35/1/11/0/2 falseP33/1/42/1/11/0/3 falseP44/2/20/0/2 4/2/0 false驗(yàn)證驗(yàn)證T0時(shí)刻的安全性時(shí)刻的安全性分析分析： 1. 四進(jìn)程執(zhí)行狀態(tài)都是未完成，四進(jìn)程執(zhí)行狀態(tài)都是未完成，F(xiàn)inish=false 2. 找找Pi，其需要的資源，其需要的資源need=有效資源有效資源work 3. 當(dāng)前的當(dāng)前的work=1/1/2， need P1 P2 P3 P4 (2/2/2), (1/0/2), (1/0/3), (4/2/0) 4. 找到找到P2滿足條件，如果讓滿足條件，如果讓P2運(yùn)行結(jié)束，運(yùn)行結(jié)束，驗(yàn)證驗(yàn)證T0時(shí)刻的安全性時(shí)刻的安

21、全性存在運(yùn)行序列：存在運(yùn)行序列：P2,P1,P3,P4ProcessWorkneedallocation Work-new FinishP21/1/21/0/25/1/1falseP12/2/21/0/0falseP31/0/32/1/1falseP44/2/00/0/2 false0/1/00/0/06/1/3true6/2/36/2/34/0/10/0/03/2/27/2/37/2/36/2/00/0/0truetruetrue0/0/03/1/49/3/49/3/45/1/44/2/29/3/6P2請(qǐng)求資源請(qǐng)求資源1，0，1 現(xiàn)在現(xiàn)在P2請(qǐng)求資源請(qǐng)求資源1/0/1，按照銀行家算法檢查：，

22、按照銀行家算法檢查： Request21/0/1=Need21/0/2 Request21/0/1=Available21/1/2 假定可以分配，修改假定可以分配，修改Available, Allocation, NeedProcessMaxallocatedNeedFinishAvailableP13/2/21/0/02/2/2false0/1/1P26/1/36/1/20/0/1falseP33/1/42/1/11/0/3falseP44/2/20/0/2 4/2/0false進(jìn)行安全性檢查進(jìn)行安全性檢查驗(yàn)證驗(yàn)證P2分配資源后的安全性分配資源后的安全性存在運(yùn)行序列：存在運(yùn)行序列：P2,P1

23、,P3,P4ProcessWorkneedallocation Work-new FinishP20/1/10/0/16/1/2falseP12/2/21/0/0falseP31/0/32/1/1falseP44/2/00/0/2 false0/1/00/0/06/1/3true6/2/36/2/34/0/10/0/03/2/27/2/37/2/36/2/00/0/0truetruetrue0/0/03/1/49/3/49/3/45/1/44/2/29/3/6P1請(qǐng)求資源請(qǐng)求資源1/0/1，按照銀行家算法檢查：，按照銀行家算法檢查：Request11/0/1 Available10/1/1條件不滿足，不能分配，讓條件不滿足，不能分配，讓P1等待。等待。P1請(qǐng)求資源請(qǐng)求資源1，0，1P3請(qǐng)求資源請(qǐng)求資源0，0，1 現(xiàn)在現(xiàn)在P3請(qǐng)求資源請(qǐng)求資源0/0/1，按照銀行家算法檢查：，按照銀行家算法檢查： Request30/0/1=Need31/0/3 Request30/0/1=Available30/1/1 假定可以分配，修改假定可以分配，修改Available, Allocati