【文章內(nèi)容簡(jiǎn)介】 chopstick[(i+1)%5])。 think }while(1)。 } (8) 利用 AND 型信號(hào)量和管程解決生產(chǎn)者 消費(fèi)者問題。 解： 利用 AND 信號(hào)量解決生產(chǎn)者－消費(fèi)者問題的算法描述如下： var mutex,empty,full: semaphore:=1,n,0。 buffer: array[0,...,n1] of item。 in out: integer := 0, 0。 begin parbegin producer: begin repeat . . . produce an item in nextp。 . . . Swait(empty, mutex)。 buffer(in) := nextp。 in := (in+1) mod n。 Ssignal(mutex, full)。 until false。 end consumer: begin repeat Swait(full, mutex)。 nextc := buffer(out)。 out := (out+1) mod n。 Ssignal(mutex, empty)。 consume the item in nextc。 until false。 end parend end 利用管程機(jī)制解決生產(chǎn)者 消費(fèi)者問題，首先需要建立一個(gè)管程 ProducerConsumer，其中包含兩個(gè)過程 insert(item)和 consumer(item)。生產(chǎn)者 消費(fèi)者同步問題可以用偽代碼描述如下： monitor ProducerConsumer condition full,empty。 int count。 void insert(int item) { if (count==N) wait(full)。 insert(item)。 count=count+1。 if (count==1) signal(empty)。 } int remover() { if (count==0) wait(empty)。 remove=remove_item。 count=count1。 if (count==N1) signal(full)。 } count=0。 end monitor void producer() { while (true) { item=produce_item。 (item)。 } } void consumer() { while (true) { item=。 consume(item) } } (9) 進(jìn)程的高級(jí)通信機(jī)制有哪些？請(qǐng)簡(jiǎn)要說明。 解： 進(jìn)程的高級(jí)通信機(jī)制分為三大類：共享存儲(chǔ)系統(tǒng)、消息傳遞系統(tǒng)和管道通信系統(tǒng)。 1. 共享存儲(chǔ)器系統(tǒng)：在共享存儲(chǔ)器系統(tǒng)中，相互通信的進(jìn)程通過共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲(chǔ)區(qū)實(shí)現(xiàn)進(jìn)程之間的通信。該系統(tǒng)又可進(jìn)一步細(xì)分為兩種方式：基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式和基于共享存儲(chǔ)區(qū)的通信方式。 2. 消息傳遞系統(tǒng)：消息傳遞機(jī)制可以實(shí)現(xiàn)不同主機(jī)間多個(gè) CPU 上進(jìn)程的通信。這種方式需要使用兩條原語 send 和 receive 來發(fā)送和接收格式化的消息 (message)。 3. 管道通信系統(tǒng)：管道通信是一種以文件 系統(tǒng)為基礎(chǔ)實(shí)現(xiàn)的適用于在進(jìn)程之間實(shí)現(xiàn)大量數(shù)據(jù)傳送的通信方式。 (10) 什么是死鎖？產(chǎn)生死鎖的原因和必要條件是什么？ 解： 所謂死鎖是指在一個(gè)進(jìn)程集合中的所有進(jìn)程都在等待只能由該集合中的其它一個(gè)進(jìn)程才能引發(fā)的事件而無限期地僵持下去的局面。 產(chǎn)生死鎖的原因可以歸結(jié)為兩點(diǎn)： 1）競(jìng)爭(zhēng)資源， 2） 各進(jìn)程之間的推進(jìn)順序不當(dāng)。 產(chǎn)生死鎖的必要條件有四個(gè)： 1） 互斥條件 ， 2） 不剝奪條件 ， 3）請(qǐng)求和保持條件， 4）環(huán)路條件。 (11) 死鎖的預(yù)防策略有哪些？請(qǐng)簡(jiǎn)要說明。 解： 死鎖的預(yù)防策略有三，說明如下 ： 1. 摒棄請(qǐng)求和保持條件： 為摒棄請(qǐng)求和保持條件，系統(tǒng)中需要使用靜態(tài)資源分配法，該方法規(guī)定每一個(gè)進(jìn)程在開始運(yùn)行前都必須一次性地申請(qǐng)其在整個(gè)運(yùn)行過程中所需的全部資源。此時(shí)，若系統(tǒng)有足夠的資源，就把進(jìn)程需要的全部資源一次性地分配給它；若不能全部滿足進(jìn)程的資源請(qǐng)求，則一個(gè)資源也不分給它，即使有部分資源處于空閑狀態(tài)也不分配給該進(jìn)程。這樣，當(dāng)一個(gè)進(jìn)程申請(qǐng)某個(gè)資源時(shí)，它不能占有其它任何資源，在進(jìn)程運(yùn)行過程中也不會(huì)再提出資源請(qǐng)求。這種方法破壞了請(qǐng)求和保持條件，從而避免死鎖的發(fā)生。 2. 摒棄不剝奪條件： 要摒棄“不剝奪條件”，可以使 用如下策略：進(jìn)程在需要資源時(shí)才提出請(qǐng)求，并且進(jìn)程是逐個(gè)地申請(qǐng)所需資源，如果一個(gè)進(jìn)程已經(jīng)擁有了部分資源，然后又申請(qǐng)另一個(gè)資源而不可得時(shí)，其現(xiàn)有資源必須全部釋放。在這種方法中，進(jìn)程只能在獲得其原有資源和所申請(qǐng)的新資源時(shí)才能繼續(xù)執(zhí)行。 3. 摒棄環(huán)路等待條件： 為確保環(huán)路等待條件不成立，可以在系統(tǒng)中實(shí)行資源有序分配策略，即系統(tǒng)中的所有資源按類型被賦予一個(gè)唯一的編號(hào)，每個(gè)進(jìn)程只能按編號(hào)的升序申請(qǐng)資源。 (12) 某系統(tǒng)中有 A、 B、 C、 D 四類資源，且其總數(shù)量都是 8 個(gè)。某時(shí)刻系統(tǒng)中有 5 個(gè)進(jìn)程，判斷下列資源狀態(tài)是否安全？若進(jìn)程 P2 申請(qǐng)資源 (1， 1， 1， 1)，能否為其分配？ 進(jìn)程 Need A B C D Allocation A B C D P0 0 0 4 3 0 0 2 2 P1 2 6 3 0 1 1 0 0 P2 3 2 1 5 2 1 0 3 P3 4 0 2 0 2 0 0 0 P4 0 5 5 4 0 2 2 2 解： 現(xiàn)在對(duì)該時(shí)刻的狀態(tài)進(jìn)行安全分析： 由于 Available 向量為（ 3， 4， 4， 1），所以 Work 向量初始化為（ 3， 4， 4， 1） 此時(shí)的 Work 小于任意的 Need[i]向量，所以系統(tǒng)處于不安全狀態(tài) 由于 Request2(1,1,1,1)Available（ 3,4,4,1）且 Request2（ 1,1,1,1） Need2（ 1,1,1,2） 所以先試著把 P2 所申請(qǐng)的資源分配給它， Available 變?yōu)椋?2,3,3,0）得到系統(tǒng)狀態(tài)如下表所示： Allocation Need Available A B C D A B C D A B C D P0 0 0 2 2 0 0 4 3 2 3 3 0 P1 1 1 0 0 2 6 3 0 P2 3 2 1 4 2 1 0 4 P3 2 0 0 0 4 0 2 0 P4 0 2 2 2 0 5 5 4 然后進(jìn)行安全性檢測(cè)： 此時(shí) Available 向量為（ 2,3,3,0），所以 Work 向量初始化為（ 2,3,3,0），此時(shí)的 Work 小于任意的 Need[i]向量，所以系統(tǒng)處于不安全狀態(tài)，所以不可以為 P2 分配資源 (13) 三個(gè)進(jìn)程 P P P3 都需要 5 個(gè)同類資源才能正常執(zhí)行直到終止，且這些進(jìn)程只有在需要 設(shè)備時(shí)才申請(qǐng)，則該系統(tǒng)中不會(huì)發(fā)生死鎖的最小資源數(shù)量是多少？請(qǐng)說明理由。 解： 系統(tǒng)中不會(huì)發(fā)生死鎖的最小資源數(shù)量是 13，這樣可以保證當(dāng)每一個(gè)進(jìn)程都占有 4 個(gè)資源的時(shí)候，有一個(gè)進(jìn)程可以獲得最后一個(gè)資源后被運(yùn)行，運(yùn)行完畢后釋放資源，于是其余進(jìn)程也能順利運(yùn)行完，所以不會(huì)死鎖。 (14) 在解決死鎖問題的幾個(gè)方法中，哪種方法最易于實(shí)現(xiàn)，哪種方法使資源的利用率最高？ 解： 預(yù)防死鎖這個(gè)方法 實(shí)現(xiàn)簡(jiǎn)單，效果突出 ；避免死鎖這種方法 系統(tǒng)吞吐量和資源利用率較高 。 (15) 考慮由 n個(gè)進(jìn)程共享的具有 m個(gè)同類資源的系統(tǒng)，如果對(duì)于 i=1,2,3,… ,n,有 Need[i]0并且所有進(jìn)程的最大需求量之和小于 m+n，試證明系統(tǒng)不會(huì)產(chǎn)生死鎖。 解： 本題中只有一種資源，不妨設(shè) Max[i]為第 i 個(gè)進(jìn)程的資源總共需要量， Need[i]為第 i 個(gè)進(jìn)程還需要的資源數(shù)量， Allocation[i]表示第 i 個(gè)進(jìn)程已經(jīng)分配到的資源數(shù)量， Available 為系統(tǒng)剩余的資源數(shù)，其中 i=1,2,3,… ,n。 假設(shè)此系統(tǒng)可以發(fā)生死鎖。 系統(tǒng)剩余的資源數(shù)量為 Available（ Available=0），由假設(shè)，因?yàn)橄到y(tǒng)處于死鎖狀態(tài)，所以 Available 個(gè)資源無法 分配出去，所以每個(gè)進(jìn)程的 Need[i]都大于 Available， 即 Need[i]=Available+1 所以 ∑ Need[i]=n*(Available+1)=n*Available+n, ① 因?yàn)槭Ｏ碌馁Y源數(shù)是 Available，所以已經(jīng)分配出去的資源數(shù)為 m – Available。 即 ∑ Allocation[i]=m – Available ② 由 ① 式和 ② 式可以得到： ∑ Need[i] + ∑ Allocation[i]=n*Available+n+ m – Available=（ n1） *Available+m+n ③ 又因?yàn)?n=1，所以（ n1） =0，又因?yàn)?Available=0，所以（ n1） *Available=0 ④ 由 ③ 式和 ④ 式可以得到∑ Need[i] + ∑ Allocation[i]=0+m+n=m+n ⑤ 根據(jù)題意知： ∑ Max[i]m+n ⑥ 又因?yàn)椋?Max[i]=Need[i]+Allocation[i],所以∑ Max[i]= ∑ Need[i] + ∑ Allocation[i] ⑦ 由 ⑥ 式和 ⑦ 式得：∑ Need[i] + ∑ Allocation[i]m+n ⑧ 由假設(shè)推出的 ⑤ 式和由題意推出的 ⑧ 式相矛盾，所以假設(shè)是錯(cuò)誤的，即系統(tǒng)不會(huì)產(chǎn)生死鎖。 (16) 某車站售票廳，在任何時(shí)刻最多可以容納 20 名購票者進(jìn)入，當(dāng)售票廳中少于 20名購票者 時(shí)，廳外的購票者可立即進(jìn)入，否則需要在外面等待。若把一個(gè)購票者看作一個(gè)進(jìn)程，請(qǐng)回答以下問題： ① 用信號(hào)量管理這些并發(fā)進(jìn)程時(shí)，應(yīng)該怎樣定義信號(hào)量，寫出信號(hào)量的初值以及信號(hào)量的各取值的含義。 ② 根據(jù)所定義的信號(hào)量，寫出相應(yīng)的程序來保證進(jìn)程能夠正確地并發(fā)執(zhí)行。 ③ 如果購票者最多為 n 個(gè)人，試寫出信號(hào)量取值的可能變化范圍 (最大值和最小值 )。 解： ①定義信號(hào)量 S,初值為 20，當(dāng) s 0 時(shí)，它表示可以繼續(xù)進(jìn)入購票廳的人數(shù)，當(dāng) s = 0時(shí)表示廳內(nèi)已有 20 人正在購票，當(dāng) s 0 時(shí) | s |表示正等待進(jìn)入的人 數(shù)。 ② semaphore S=20。 begin parbegin procedure:begin repeat wait(s)。 Enter and buy ticket。 signal(s)。 until false。 end parend end ③ 最大值為 20，最小值為 20n (17) 在測(cè)量控制系統(tǒng)中的數(shù)據(jù)采集任務(wù)時(shí)，把所采集的數(shù)據(jù)送往一單緩沖區(qū)；計(jì)算任務(wù)從該單緩沖區(qū)中取出數(shù)據(jù)進(jìn)行計(jì)算。 試寫出利用信號(hào)量機(jī)制實(shí)現(xiàn)兩 個(gè) 任務(wù)共享單緩沖區(qū)的同步算法。 解： semaphore mutex = 1。 semaphore full = 0。 semaphore empty = 1。 begin parbegin collect: begin repeat ?? collect data in nextp。 wait(empty)。 wait(mutex)。 buffer:=nextp。 signal(mutex)。 signal(full)。 until false。 end pute: begin repeat ?? wait(full)。 wait(mutex)。 nextc:=buffer。 signal(mutex)。 signal(empty)。 pute data in nextc。 until false。