操作系統(tǒng)計(jì)算題總結(jié)

1、應(yīng)用類型知識(shí)要點(diǎn)一：進(jìn)程同步問題整形信號(hào)量：未遵循“讓權(quán)等待原則”wait(S): while S<=0 do no-op; S:=S-1;signal(S): S:=S+1記錄型信號(hào)量：執(zhí)行wait操作時(shí)，信號(hào)量的值加1，信號(hào)量的值小于0時(shí)阻塞；執(zhí)行signal操作時(shí)，信號(hào)量的值減1，信號(hào)量的值小于等于0時(shí)喚醒阻塞中的進(jìn)程。type semaphore=record value:integer; L:list of process; endprocedure wait(S)var S:semaphore;beginS.value=S.value-1;if S.value<0 th

2、en block(S.L);endprocedure signal(S)var S:semaphore;beginS.value:=S.value+1;if S.value<=0 then wakeup(S.L);endØ 生產(chǎn)者-消費(fèi)者問題Ø 讀者-寫者問題Ø 哲學(xué)家進(jìn)餐問題Ø 理發(fā)室問題進(jìn)程同步問題求解要領(lǐng)Ø 認(rèn)真審題、確立信號(hào)量及關(guān)鍵變量Ø 構(gòu)建算法基本步驟及邏輯結(jié)構(gòu)Ø 資源信號(hào)量申請(qǐng)先于互斥信號(hào)量申請(qǐng)Ø wait操作與signal操作配對(duì)出現(xiàn)利用信號(hào)量實(shí)現(xiàn)互斥主程序子程序Var mutex:semap

3、hore:=1;beginparbeginprocess1;process2;parendendprocess1beginrepeatwait(mutex);臨界區(qū)signal(mutex);until falseendprocess2beginrepeatwait(mutex);臨界區(qū)signal(mutex)until falseend1. 互斥信號(hào)量初值為12. 互斥信號(hào)量wait和signal肯定出現(xiàn)在同一進(jìn)程中，并出現(xiàn)在需要互斥訪問數(shù)據(jù)(臨界資源)前后利用信號(hào)量描述前趨關(guān)系Var a,b,c,d,e,f,g,h:semaphore:=0,0,0,0,0,0,0,0;beginparb

4、eginbegin S1;signal(a);signal(b);endbegin wait(a);S2;signal(c);signal(d);endbegin wait(b);S3;signal(e);endbegin wait(c);S4;signal(f);endbegin wait(d);S5;signal(g);endbegin wait(e);S6;signal(h);endbegin wait(f);wait(g);wait(f);S7;endparendendS1S2S3S4S5S6S7abcdefhg首先應(yīng)找出所有的前趨關(guān)系。然后，對(duì)每一種前趨關(guān)系，如Si->Sj，專

5、門設(shè)置一初值為0的信號(hào)量，并在Si結(jié)束之后執(zhí)行對(duì)該信號(hào)量的signal操作，而在Sj開始之前執(zhí)行對(duì)該信號(hào)量的wait操作，這樣便可保證程序段Si執(zhí)行完后才執(zhí)行程序段Sj。生產(chǎn)者-消費(fèi)者問題主程序(n為常量)Var buffer:array0,n-1 of item;in, out: integer:=0,0;mutex,empty,full:semaphore:=1,n,0;beginparbeginproducer1;produceri;producerM;consumer1;consumerj;consumerN;parendend生產(chǎn)者子程序消費(fèi)者子程序produceriVar next

6、p:item;beginrepeatProduce an item in nextp;wait(empty);wait(mutex);bufferin:=nextp;in=(in+1)mod n;signal(mutex);signal(full);until falseendconsumerjVar nextc:item;beginrepeatwait(full);wait(mutex);nextc:=bufferout;out:=(out+1) mod n;signal(mutex);signal(empty);Consume the item in nextc;until falseen

7、d生產(chǎn)者子程序(基于AND信號(hào)量)消費(fèi)者子程序(基于AND信號(hào)量)produceribeginrepeatProduce an item in nextp;Swait(empty, mutex);bufferin=nextp;in:=(in+1) mod n;Signal(mutex, full);until falseendconsumerjbeginrepeatSwait(full,mutex);nextc:=bufferout;out:=(out+1) mod n;Ssignal(mutex, empty);Consume the item in nextc;until falseend

8、讀者-寫者問題(讀者優(yōu)先)主程序Var readercount:integer:=0;rcmutex,wmutex:semaphore:=1,1;beginparbeginreader1;readeri;readerM;writer1;writerj;writerN;parendend讀者readeribeginrepeatwait(rcmutex);if readercount=0 then wait(wmutex);readercount:=readercount+1;signal(rcmutex);Perform read operation;wait(rcmutex);readerco

9、unt:=readercount-1;if readercount=0 then signal(wmutex);signal(rcmutex);until falseend寫者writerjbeginrepeatwait(wmutex);Perform write operation;signal(wmutex);until false;endreadercount:讀者數(shù)rcmutex:讀者進(jìn)程中用于readercount變量的互斥訪問wmutex:用于讀者與寫者、寫者與寫者之間的互斥訪問寫者與第一個(gè)讀者競(jìng)爭(zhēng)wmutex。一旦讀者獲得wmutex，那么直到所有讀者執(zhí)行結(jié)束由最后一個(gè)讀者釋放，

10、而每個(gè)寫者執(zhí)行結(jié)束都釋放，所以讀者優(yōu)先寫者執(zhí)行。讀者-寫者問題(寫者優(yōu)先)主程序Var readercount,writercount:integer:=0,0;rcmutex,wcmutex,wmutex,S:semaphore:=1,1,1,1;beginparbeginreader1;readeri;readerM;writer1;writerj;writerN;parendend讀者readeribeginrepeatwait(S);wait(rcmutex);if readercount=0 then wait(wmutex);readercount:=readercount+1;s

11、ignal(rcmutex);signal(S);Perform read operation;wait(rcmutex);readercount:=readercount-1;if readercount=0 then signal(wmutex);signal(rcmutex);until false;end寫者writerjbeginrepeatwait(wcmutex);if writercount=0 then wait(S);writercount:=writercount+1;signal(wcmutex);wait(wmutex);Perform write operation

12、;signal(wmutex);wait(wcmutex);writercount:=writercount-1;if writercount=0 then signal(S);signal(wcmutex);until falseendrcmutex:讀者進(jìn)程中用于readercount變量的互斥訪問wcmutex:寫者進(jìn)程中用于writercount變量的互斥訪問wmutex: 用于讀者與寫者、寫者與寫者之間的互斥訪問讀者與第一個(gè)寫者競(jìng)爭(zhēng)S信號(hào)量。一旦讀者獲得S信號(hào)量，那么直到所有讀者執(zhí)行結(jié)束由最后一個(gè)寫者釋放，而每個(gè)讀者執(zhí)行結(jié)束都釋放，所以寫者優(yōu)先讀者執(zhí)行。讀者-寫者問題(限定讀者數(shù))主

13、程序Var RN:integer:=10;rmax,wmutex:semaphore:=RN,1;beginparbeginreader1;readeri;readerM;writer1;writerj;writerN;parendend讀者readeribeginrepeat=Swait(rmax,1,1,wmutex,1,0);Swait(rmax,1,1);Swait(wmutex,1,0);Perform read operation;Ssignal(rmax,1);until false;end寫者writerjbeginrepeatSwait(wmutex,1,1, rmax,RN

14、,0);Perform write operationSignal(wmutex);until falseendRN:限定最多同時(shí)讀的讀者數(shù)rmax:空位置的數(shù)目，即系統(tǒng)還允許執(zhí)行讀操作的讀者數(shù)，超過這個(gè)數(shù)目后讀者將等待wmutex: 用于讀者與寫者、寫者與寫者之間的互斥訪問讀者執(zhí)行Swait(wmutex,1,0)保證無寫者(wmutex值保持不改變)寫者執(zhí)行Swait(wmutex,1,1,rmax,RN,0)保證既無寫者在寫又無讀者在讀(rmax值保持不變)哲學(xué)家進(jìn)餐問題主程序Var chopstick:array0,4 of semaphore:=1,1,1,1,1;beginparb

15、eginphilosopher0;philosopheri; philosopher4;parendend哲學(xué)家進(jìn)餐問題子程序基于AND信號(hào)量機(jī)制philosopheribeginrepeatThink;Swait(chopstick(i+1) mod 5,chopsticki);Eat;Ssignal(chopstick(i+1)mod 5,chopsticki);until falseend哲學(xué)家進(jìn)餐問題子程序限制哲學(xué)家同時(shí)進(jìn)餐人數(shù)philosopherivar pmax:semaphore:=4;beginrepeatwait(pmax);wait(chopsticki);wait(ch

16、opstick(i+1) mod 5);Eat;signal(chopstick(i+1) mod 5);signal(chopsticki);signal(pmax);Think;until falseend理發(fā)師問題描述如下：理發(fā)店包含一間接待室和一間工作室，接待室內(nèi)有n(n>=1)把椅子，而工作室只有一把椅子。如果沒有顧客，理發(fā)師就去睡覺，如果顧客來時(shí)所有的椅子都有人，那么顧客離去；如果理發(fā)師在忙且接待室有空閑的椅子，那么此顧客會(huì)坐在其中一把空閑的椅子上等待；如果理發(fā)師在睡覺，則顧客會(huì)喚醒他。請(qǐng)采用信號(hào)量機(jī)制解決該理發(fā)師問題(可采用偽代碼描述)。解：要求描述理發(fā)師和顧客的行為，因?yàn)?/p>

17、需要兩類進(jìn)程Barber()和Customer()分別描述理發(fā)師和顧客的行為。理發(fā)師和顧客之間是同步的關(guān)系，理發(fā)師和椅子使臨界資源，所以顧客之間是互斥的關(guān)系。引入3個(gè)信號(hào)量和一個(gè)控制變量：Ø 控制變量waiting也用于記錄等候的顧客數(shù)，實(shí)際上是customers的一份拷貝。之所以使用waiting是因?yàn)闊o法讀取信號(hào)量的當(dāng)前值，初值均為0。Ø 信號(hào)量customers用來記錄等候理發(fā)的顧客數(shù)(不包括正在理發(fā)的顧客)，并用作阻塞理發(fā)師進(jìn)程，初值為0。Ø 信號(hào)量barbers用來記錄正在等候顧客的理發(fā)師數(shù)（為0或1），并用作阻塞顧客進(jìn)程，初值為0。Ø 信號(hào)量

18、mutex用于對(duì)waiting的訪問進(jìn)行互斥，初值為1。進(jìn)入理發(fā)店的顧客必須先看等候的顧客數(shù)，如果少于椅子數(shù)（n），他坐下來等，否則他就離開。PV操作代碼如下: int waiting=0; / 等候理發(fā)的顧客數(shù)(還沒理發(fā)的), 0nsemaphore customers=0, barbers=0, mutex=1; barber() while(TRUE) / 理完一人,還有顧客嗎? P(customers); / 若無顧客,理發(fā)師睡眠P(mutex); / 進(jìn)程互斥waiting := waiting -1; / 等候顧客數(shù)少一個(gè)V(barbers); / 理發(fā)師去為一個(gè)顧客理發(fā)V(mut

19、ex); / 開放臨界區(qū) cut-hair( ); / 正在理發(fā)(非臨界區(qū)操作) customer() /顧客進(jìn)入理發(fā)店P(guān)(mutex); /進(jìn)程互斥if (waiting < n) /還有空位 waiting := waiting+1; /等候顧客數(shù)加1V(customers); /有顧客了，如果理發(fā)師在睡則喚醒V(mutex);/開放臨界區(qū)P(barbers); /無理發(fā)師, 顧客坐著養(yǎng)神get-haircut( ); /一個(gè)顧客坐下等待理發(fā) else V(mutex);/顧客已滿，離開應(yīng)用類型知識(shí)要點(diǎn)二：分頁存儲(chǔ)地址結(jié)構(gòu)及地址變換Ø 分頁存儲(chǔ)管理地址結(jié)構(gòu)(由硬件機(jī)制決定)

20、 31 12 11 0頁 號(hào)頁內(nèi)地址Ø 邏輯地址與頁號(hào)及頁內(nèi)偏移地址之間的換算PageNo=INTAddr/PageLengthPageOffset=Addr mod PageLength舉例：對(duì)于1KB頁面，若給定邏輯地址2170B，則PageNo=2，PageOffset=122Ø 地址變換任務(wù) 關(guān)鍵在于頁號(hào)到物理塊號(hào)之間的轉(zhuǎn)變Ø 地址映射某虛擬存儲(chǔ)器的用戶編程空間共32個(gè)頁面，每頁1K，主存為16K。假定某時(shí)刻用戶頁表中已調(diào)入主存的頁面的虛頁號(hào)和物理頁號(hào)對(duì)照表如圖所示，則當(dāng)虛地址為十六進(jìn)制0A5C時(shí)，對(duì)應(yīng)的物理地址是多少？虛頁號(hào)物理頁號(hào)041102437解：

21、虛擬地址(0A5C)=(10*16+5*16+12)頁號(hào)=INT2652/1K=2，其物理塊號(hào)為4 頁內(nèi)偏移=2652 mod 1K = 604物理地址為4*1K+604=(4700) =(125C) 應(yīng)用類型知識(shí)要點(diǎn)三：分頁存儲(chǔ)與數(shù)據(jù)訪問時(shí)間假定快表檢索時(shí)間為20ns，內(nèi)存訪問時(shí)間為100ns，則若能在快表中找到CPU給出的頁號(hào)，CPU存取一個(gè)數(shù)據(jù)將需要(100+20)=120ns，若不能在快表中找到CPU給出的頁號(hào)，則為存取一個(gè)數(shù)據(jù)將需要(100+100+20)=220ns。進(jìn)一步說，若假定快表查找命中率為80%，則其有效訪問時(shí)間為120*80%+220*(1-80%)=140ns。應(yīng)用類

22、型知識(shí)要點(diǎn)四：頁面置換算法與缺頁次數(shù)Ø 最佳置換算法OPT(向前看頁面引用序列)基本思想：選擇永不使用或是在最長時(shí)間內(nèi)不再被訪問(即據(jù)現(xiàn)在最長時(shí)間才會(huì)被訪問)的頁面淘汰出內(nèi)存評(píng)價(jià)：理想化算法，具有最好性能(對(duì)于固定分配方式，本法可保證獲得較低的缺頁率)，但實(shí)際上卻難于實(shí)現(xiàn)，故主要用于算法評(píng)價(jià)參照70120304230321201701777222222222222227770000004440000000000111333333331111111某進(jìn)程分配獲得三個(gè)物理塊采用預(yù)調(diào)頁策略(區(qū)別預(yù)調(diào)頁策略與請(qǐng)求調(diào)頁策略)，前3個(gè)頁面預(yù)先裝入第一行為頁面訪問(引用)序列第二、三、四行為內(nèi)存頁

23、面分布情況，前三列頁面預(yù)先裝入缺頁中斷次數(shù)為6次，缺頁率30%缺頁率=(發(fā)生缺頁次數(shù)/頁面序列長度)*100%Ø 先進(jìn)先出置換算法FIFO(向回看頁面分布情況)基本思想：選擇最先進(jìn)入內(nèi)存即在內(nèi)存中駐留時(shí)間最久的頁面換出到外存。進(jìn)程已調(diào)入內(nèi)存的頁面按進(jìn)入先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置替換指針以指向最老頁面。評(píng)價(jià)：簡(jiǎn)單直觀，但不符合進(jìn)程實(shí)際運(yùn)行規(guī)律，性能較差，故實(shí)際應(yīng)用極少。70120304230321201701777222244400000007770000333222221111100111100033333222221某進(jìn)程分配獲得三個(gè)物理塊采用預(yù)調(diào)頁策略(區(qū)別預(yù)調(diào)頁策略與請(qǐng)求調(diào)

24、頁策略)，前3個(gè)頁面預(yù)先裝入第一行為頁面訪問(引用)序列第二、三、四行為內(nèi)存頁面分布情況，前三列頁面預(yù)先裝入缺頁中斷次數(shù)為12次，缺頁率68%缺頁率=(發(fā)生缺頁次數(shù)/頁面序列長度)*100%Ø 最近最久未使用置換算法LRU(向回看頁面引用序列)(硬件支持)基本思想：以“最近的過去”作為“最近的將來”的近似，選擇最近一段時(shí)間最長時(shí)間未被訪問的頁面淘汰出內(nèi)存。評(píng)價(jià)：適用于各種類型的程序，性能較好，但需要較多的硬件支持。70120304230321201701777222244400011111110000000033333300000111333222222222777某進(jìn)程分配獲得三個(gè)

25、物理塊采用預(yù)調(diào)頁策略(區(qū)別預(yù)調(diào)頁策略與請(qǐng)求調(diào)頁策略)，前3個(gè)頁面預(yù)先裝入第一行為頁面訪問(引用)序列第二、三、四行為內(nèi)存頁面分布情況，前三列頁面預(yù)先裝入缺頁中斷次數(shù)為9次，缺頁率45%缺頁率=(發(fā)生缺頁次數(shù)/頁面序列長度)*100%Ø 簡(jiǎn)單CLOCK置換算法(NRU)(硬件支持)Ø 改進(jìn)型CLOCK置換算法(硬件支持)評(píng)價(jià)：與簡(jiǎn)單CLOCK算法相比，可減少磁盤的I/O操作次數(shù)，但淘汰頁的選擇可能經(jīng)歷多次掃描(最多3輪加1次)，故實(shí)現(xiàn)算法自身的開銷增大。Ø 最少使用置換算法(硬件支持)基本思想：為內(nèi)存各頁設(shè)置一個(gè)以為寄存器用于記錄對(duì)應(yīng)被訪問頻率。選擇在最近時(shí)期使用最

26、少的頁面作為淘汰頁。評(píng)價(jià)：鑒于僅用一位寄存器有限各位來記錄頁面使用會(huì)導(dǎo)致訪問一次與訪問多次的等效性，本算法并不能真實(shí)全面地反映頁面適用情況。應(yīng)用類型知識(shí)要點(diǎn)五：文件結(jié)構(gòu)與記錄檢索次數(shù)Ø 索引順序文件組織方式檢索開銷分組大小Ø 兩級(jí)索引順序文件組織方式主文件分組大小低級(jí)索引表分組大小檢索開銷Ø 順序文件(定長記錄順序文件/變長記錄順序文件)1 邏輯記錄的排序(與關(guān)鍵字次序一致與否)串結(jié)構(gòu)與順序結(jié)構(gòu)2 順序文件讀寫操作讀寫指針RWptr<=>對(duì)應(yīng)記錄邏輯地址定長記錄RWptr+=recordLength變長紀(jì)錄RWptr+=currentRecordLen

27、gth(無法實(shí)現(xiàn)隨機(jī)存取)3 順序文件評(píng)析適于批量存取及磁帶介質(zhì)交互應(yīng)用場(chǎng)合單個(gè)記錄操作低效Ø 索引文件組織及檢索機(jī)制(主要解決變長記錄文件無法實(shí)現(xiàn)隨機(jī)存取問題)記錄號(hào)本身的物理含義很弱，強(qiáng)調(diào)真正具有物理含義的關(guān)鍵字索引表本身是定長記錄順序文件Ø 索引順序文件檢索效率分析對(duì)于擁有N條記錄的主數(shù)據(jù)文件，若基于順序查找法來檢索具有指定關(guān)鍵字的記錄，不同文件組織方式下的系統(tǒng)檢索開銷比較(假設(shè)不存在查找失敗的情況)1 順序文件組織方式(N+1)/2條(順序查找)2 索引文件組織方式(N+1)/2條(順序查找)3 索引順序文件組織方式+1(分組大小記錄，此時(shí)檢索效率最高)4 舉例說明

28、(N=10000)Ø 基于多級(jí)索引的索引順序文件(分組大小)建立多級(jí)索引以進(jìn)一步提高檢索效率舉例說明(N=10)1 索引順序文件組織方式檢索開銷1001條分組大小1000條記錄2 兩級(jí)索引順序文件組織方式主文件分組大小100條記錄低級(jí)索引表分組大小100條記錄檢索開銷151.5條應(yīng)用類型知識(shí)要點(diǎn)六：文件分配表占用空間關(guān)鍵計(jì)算盤塊總數(shù)(實(shí)際操作系統(tǒng)按簇分配，這里按盤塊分配)磁盤有多少個(gè)盤塊，F(xiàn)AT中就有多少個(gè)表項(xiàng)(前提是按盤塊分配)FAT表項(xiàng)應(yīng)足以表示最大的盤塊號(hào)文件分配表空間開銷計(jì)算設(shè)定盤塊大小為1KB對(duì)于1.2M的軟盤，共有盤塊1.2M/1KB=1.2K(2,2)(取4的倍數(shù)且較大

29、的那個(gè))故文件分配表表項(xiàng)取12位即1.5B所以FAT共需空間1.2K*1.5B=1.8KB對(duì)于200M的硬盤，共有盤塊200M/1KB=200K(2,2)故文件分配表表項(xiàng)取20位即2.5B所以FAT共需空間200K*2.5B=500KB應(yīng)用類型知識(shí)要點(diǎn)七：索引分配與文件最大長度兩級(jí)/多級(jí)索引分配基本思想對(duì)于太大的文件和索引塊太多時(shí)，直接用鏈接指針來鏈接索引塊的方法顯然是低效的，為此應(yīng)引入多級(jí)索引分配方式允許文件最大長度兩級(jí)索引、盤塊大小1KB、盤塊號(hào)占4B，則一個(gè)索引塊可含1KB/4B=256個(gè)盤塊號(hào)，于是兩級(jí)索引最多可含256*256=64K個(gè)盤塊號(hào)，允許文件最大長度為64MB混合分配方式(

30、UNIX系統(tǒng)4KB、4MB、4GB、4TB)直接尋址直接地址項(xiàng)存放對(duì)應(yīng)文件數(shù)據(jù)的盤塊的盤塊號(hào)盤塊大小4KB、盤塊號(hào)占4B，則支持長度在4KB*10=40KB以內(nèi)的文件一次間接尋址addr(10)指向?qū)?yīng)文件的一級(jí)索引塊一級(jí)索引塊可含4KB/4B=1K個(gè)盤塊號(hào)，故支持長度在(4KB*1K=4MB)+40KB以內(nèi)的文件多次間接尋址addr(11)、i.addr(12)分別指向?qū)?yīng)文件的兩級(jí)索引和三級(jí)索引塊，所以支持的文件長度可達(dá)(4KB*1K*1K*1K=4TB)+(4KB*1K*1K=4GB)+4MB+40KB應(yīng)用類型知識(shí)要點(diǎn)八文件查找與磁盤啟動(dòng)次數(shù)假定每次啟動(dòng)磁盤只裝入一個(gè)目錄盤塊盤塊大小1K

31、B，文件目錄共3200個(gè)FCB引入索引結(jié)點(diǎn)前FCB占64B，每盤塊包含16個(gè)FCB，文件目錄共需占用200個(gè)盤塊，故查找一個(gè)文件平均需啟動(dòng)磁盤100.5次(順序查找)引入索引結(jié)點(diǎn)后FCB占16B(文件名和索引結(jié)點(diǎn)指針分別占用14B和2B)，每盤塊包含64個(gè)目錄項(xiàng)，文件目錄共需占用50個(gè)盤塊，故查找一個(gè)文件平均需啟動(dòng)磁盤25.5+1次(順序查找，讀索引結(jié)點(diǎn)取地址信息只需一次，因?yàn)樗饕Y(jié)點(diǎn)在外存上是連續(xù)存放的)應(yīng)用類型知識(shí)要點(diǎn)九：銀行家算法及資源分配管理產(chǎn)生死鎖的必要條件1 互斥條件2 請(qǐng)求和保持條件3 不剝奪條件4 環(huán)路等待條件死鎖預(yù)防(要求進(jìn)程的資源分配是靜態(tài)的)死鎖預(yù)防的方法是使四個(gè)必要條件

32、中的第2、3、4個(gè)條件之一不能成立，來避免發(fā)生死鎖。至于條件1，因?yàn)樗窃O(shè)備的固有特性所決定的，不僅不能改變，還應(yīng)加以保證。死鎖避免允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)首先就資源分配的安全性進(jìn)行檢查，且僅當(dāng)確認(rèn)此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)時(shí)才可分配，否則予以拒絕。死鎖避免基本概念安全狀態(tài)系統(tǒng)可按某種進(jìn)程序列<P1, P2, , Pn>(稱之為安全分配序列)來為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程均能順利完成。不安全狀態(tài)系統(tǒng)無法找到一個(gè)安全分配序列的系統(tǒng)狀態(tài)。死鎖與狀態(tài)安全性之間的關(guān)系1. 并非所有不安全狀態(tài)都是死鎖狀態(tài)2.

33、當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)后，便可能陷入死鎖3. 只要保證系統(tǒng)處于安全狀態(tài)，便可避免死鎖安全狀態(tài)及向不安全狀態(tài)的轉(zhuǎn)換資源名稱資源總數(shù)可用資源量可用資源量磁帶機(jī)1232進(jìn)程最大需求已分配(尚需)已分配(尚需)P1105(5)5(5)P242(2)2(2)P392(7)3(6)T0時(shí)刻存在安全分配序列<P2, P1, P3>若在T0時(shí)刻應(yīng)進(jìn)程請(qǐng)求將所剩磁帶機(jī)中的1臺(tái)分配給P3，則系統(tǒng)進(jìn)入不安全狀態(tài)(如上圖)銀行家算法之?dāng)?shù)據(jù)結(jié)構(gòu)(下標(biāo)i對(duì)應(yīng)進(jìn)程，下標(biāo)j對(duì)應(yīng)資源)可用資源向量/請(qǐng)求向量ml Availablej=k表示系統(tǒng)現(xiàn)有k個(gè)Rj類資源l Requestj=k表示進(jìn)程Pi請(qǐng)求k個(gè)Rj類資源最

34、大需求矩陣/分配矩陣/需求矩陣n,ml Maxi,j=k表示進(jìn)程Pi最多需要k個(gè)Rj類資源l Allocationi,j=k表示進(jìn)程Pi已分配k個(gè)Rj類資源l Needi,j=k表示進(jìn)程Pi尚需k個(gè)Rj類資源工作向量m/Finish布爾向量nl Workj=k表示系統(tǒng)”可”提供k個(gè)Rj類資源l Finishi表示進(jìn)程Pi可否擁有足夠資源完成運(yùn)行銀行家算法之主體算法1. 進(jìn)程Pi發(fā)出資源請(qǐng)求Request2. 若非RequestNeedi，出錯(cuò)返回3. 若非RequestAvailable，則應(yīng)使Pi等待并返回4. 系統(tǒng)試探性地滿足Pi請(qǐng)求，并作以下修改：Ø Available=Ava

35、ilable-RequestØ Allocationi=Allocationi+RequestØ Needi=Needi-Request5. 系統(tǒng)調(diào)用安全性算法進(jìn)行資源分配檢查，若安全則執(zhí)行分配，否則恢復(fù)試探分配前狀態(tài)，并使Pi等待銀行家算法之安全性子算法另Work=Available，F(xiàn)inish=FALSE從進(jìn)程集合中查找一個(gè)滿足Finishi=FALSE且NeediWork的進(jìn)程。若找到，則可假定Pi能獲得所需資源并順利執(zhí)行，故有：Work=Work+AllocationiFinishi=TRUE然后重復(fù)執(zhí)行第2步；否則轉(zhuǎn)至第3步執(zhí)行如果Finish=TRUE，則表示

36、系統(tǒng)處于安全狀態(tài)；否則系統(tǒng)處于不安全狀態(tài)銀行家算法應(yīng)用舉例之一(無任何進(jìn)程發(fā)出資源申請(qǐng))進(jìn)程MAXAllocationNeedWorkAllocation+WorkFinishABCABCABCABCABCP0753010743745755TRUEP1322200122332532TRUEP29023026007551057TRUEP3222211011532743TRUEP4433002431743745TRUE系統(tǒng)資源總量AvailableA,B,C=10,5,7T0時(shí)刻Available A,B,C=3,3,2安全分配序列？<P1,P3,P4,P0,P2>1. Work= A

37、vailable=3,3,2可滿足P1或P3，先滿足P1(如果P1走不通，再看P3)2. Work=5,3,2，滿足P33. Work=7,4,3，滿足P44. Work=7,4,5，滿足P05. Work=7,5,5，滿足P16. Work=10,5,7，分配完畢，此時(shí)Work與系統(tǒng)資源總量相等銀行家算法應(yīng)用舉例之二(進(jìn)程P1發(fā)出資源申請(qǐng))進(jìn)程MAXAllocationNeedWorkAllocation+WorkFinishABCABCABCABCABCP0753010743745755TRUEP13222/30/00/21/02/22/0230532TRUEP29023026007551057TRUEP3222211011532743TRUEP4433002431743745TRUET1時(shí)刻AvailableA,B,C=3,3,21. 進(jìn)程P1發(fā)出資源請(qǐng)求Request(1,0,2)2. Request(1,0,2)<Need