【正文】 分配給該優(yōu)先級高的進(jìn)程，使之執(zhí)行。 當(dāng)新到達(dá)的作業(yè)對應(yīng)的進(jìn)程比正在執(zhí)行的作業(yè)對應(yīng)進(jìn)程的運行時間明顯短時，系統(tǒng)剝奪當(dāng)前進(jìn)程的執(zhí)行，而將處理 器 分配給新的短進(jìn)程，使之優(yōu)先執(zhí)行。 (18) 說明時間片輪轉(zhuǎn)調(diào)度算法的基本思路。每次調(diào)度時將 CPU 分派給隊首進(jìn)程，讓其執(zhí)行一個時間片。在一個時間片結(jié)束時，發(fā)生時鐘中斷。這樣可以保證就緒隊列中的所有進(jìn)程都有機(jī)會獲得 處理器而運行 的機(jī)會，可以提高進(jìn)程并發(fā)性和響應(yīng)時間特性，從而提高資源利用率。 解： 多級反饋隊列調(diào)度算法則不必 事先知道各進(jìn)程的執(zhí)行時間，又可以滿足各種類型進(jìn)程的調(diào)度需要， 它是一種目前公認(rèn)較好的進(jìn)程調(diào)度算法。每隊列分配不同的時間片，規(guī)定優(yōu)先級越低則時間片越長。若一個時間片未能執(zhí)行完，則降低插入到隊列 2 的末尾；依此類推，降低到最后的隊列 ，則按“時間片輪轉(zhuǎn)”算法調(diào)度直到完成。 4. 只有當(dāng)較高優(yōu)先級的隊列為空時，才調(diào)度較低優(yōu)先級隊列中的進(jìn)程執(zhí)行。 (20) 什么是靜態(tài)和動態(tài)優(yōu)先級？如何確定靜態(tài)優(yōu)先級？ 解： 靜態(tài)優(yōu)先級是在系統(tǒng)創(chuàng)建時確定的，一經(jīng)確定之后在整個進(jìn)程運行期間不再改變。 (21) 在一個單道批處理系統(tǒng)中，一組作業(yè)的到達(dá)時間和運行時間如下表所示。 作業(yè) 到達(dá)時間 運行時間 1 2 3 4 解： 用 T 表示周轉(zhuǎn)時間，用 W 表示帶權(quán)周轉(zhuǎn)時間 FCFS 的作業(yè)調(diào)度情況如下： 作業(yè) 提交時間 運行時間 開始時間 結(jié)束時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 1 2 3 4 FCFS 的 T =（ +++） / 4 = W =（ +++） / 4 = SJF 的作業(yè)調(diào)度情況如下： 作業(yè) 提交時間 運行時間 開始時間 結(jié)束時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 1 2 3 4 SJF 的 T=（ +++） / 4 = W =（ +++） / 4 = 高響應(yīng)比優(yōu)先的作業(yè)調(diào)度情況如下： 作業(yè) 提交時間 運行時間 開始時間 結(jié)束時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 1 2 3 4 高響應(yīng)比算法的 T=（ +++） / 4 = W =（ +++） / 4 = 第 4章 進(jìn)程同步與死鎖 (1) 什么是進(jìn)程同步？什么是進(jìn)程互斥？ 解： 同步是進(jìn)程間的直接制約關(guān)系，這種制約主要源于進(jìn)程間的合作。 進(jìn)程互斥是進(jìn)程間的間接制約關(guān)系， 當(dāng)多個進(jìn)程需要使用相同的資源，而此類資源在任一時刻卻只能供一個進(jìn) 程使用，獲得資源的進(jìn)程可以繼續(xù)執(zhí)行，沒有獲得資源的進(jìn)程必須等待，進(jìn)程的 運行具有時間次序的特征，誰先從系統(tǒng)獲 得共享資源，誰就先運行， 這種對共享資源的排它性使用所造成的進(jìn)程間的間接制約關(guān)系稱為進(jìn)程互斥。 (2) 進(jìn)程執(zhí)行時為什么要設(shè)置進(jìn)入?yún)^(qū)和退出區(qū)？ 解： 為了實現(xiàn)多個進(jìn)程對臨界資源的互斥訪問，必須在臨界區(qū)前面增加一段用于檢查欲訪問的臨界資源是否正被訪問的代碼，如果未被訪問， 該進(jìn)程便可進(jìn)入臨界區(qū)對資源進(jìn)行訪問，并設(shè)置正被訪問標(biāo)志，如果正被訪問，則本進(jìn)程不能進(jìn)入臨界區(qū)，實現(xiàn)這一功能的代碼成為“進(jìn)入?yún)^(qū)”代碼；在退出臨界區(qū)后，必須執(zhí)行“退出區(qū)”代碼，用于恢復(fù)未被訪問標(biāo)志。 解： 同步機(jī)制都應(yīng)遵循下面的 4 條準(zhǔn)則： 1. 空閑讓進(jìn) 。 2. 忙則等待 。 3. 有限等待 。 4. 讓權(quán)等待 。 (4) 整型信號量是否能完全遵循同步機(jī)構(gòu)的四條基本準(zhǔn)則？為什么？ 解： 不能。 (5) 在生產(chǎn)者 消費者問題中，若缺少了 V(full)或 V(empty)，對進(jìn)程的執(zhí)行有什么影響？ 解： 如果缺少了 V(full)，那么表明從第一個生產(chǎn)者進(jìn)程開始就沒有對信號量 full 值改變，即使緩沖池存放 的產(chǎn)品已滿了，但 full 的值還是 0，這樣消費者進(jìn)程在執(zhí)行 P(full)時會認(rèn)為緩沖池是空的而取不到產(chǎn)品，那么消費者進(jìn)程則會一直處于等待狀態(tài)。 (6) 在生產(chǎn)者 消費者問題中，若將 P(full)和 P(empty)交換位置，或?qū)?V(full)或 V(empty)交換位置，對進(jìn)程執(zhí)行有什么影響？ 解： 對 full 和 empty 信號量的 P、 V 操作應(yīng)分別出現(xiàn)在合作進(jìn)程中，這樣做的目的是能正確表征各進(jìn)程對臨界資源的使用情況，保證正確的進(jìn)程通信聯(lián)絡(luò)。 解： 對哲學(xué)家按順序從 0 到 4 編號，哲學(xué)家 i 左邊的筷子的編號為 i，哲學(xué)家右邊的筷子的編號為（ i+1） %5。 //定義信號量數(shù)組 chopstick[5]，由于侉子是臨街資源（互斥），故設(shè)置初值均為 1。 wait(chopstick[(i+1)%5])。 wait(chopstick[i])。 signal(chopstick[(i+1)%5])。 } (8) 利用 AND 型信號量和管程解決生產(chǎn)者 消費者問題。 buffer: array[0,...,n1] of item。 begin parbegin producer: begin repeat . . . produce an item in nextp。 buffer(in) := nextp。 Ssignal(mutex, full)。 end consumer: begin repeat Swait(full, mutex)。 out := (out+1) mod n。 consume the item in nextc。 end parend end 利用管程機(jī)制解決生產(chǎn)者 消費者問題，首先需要建立一個管程 ProducerConsumer，其中包含兩個過程 insert(item)和 consumer(item)。 int count。 insert(item)。 if (count==1) signal(empty)。 remove=remove_item。 if (count==N1) signal(full)。 end monitor void producer() { while (true) { item=produce_item。 } } void consumer() { while (true) { item=。 解： 進(jìn)程的高級通信機(jī)制分為三大類：共享存儲系統(tǒng)、消息傳遞系統(tǒng)和管道通信系統(tǒng)。該系統(tǒng)又可進(jìn)一步細(xì)分為兩種方式：基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式和基于共享存儲區(qū)的通信方式。這種方式需要使用兩條原語 send 和 receive 來發(fā)送和接收格式化的消息 (message)。 (10) 什么是死鎖？產(chǎn)生死鎖的原因和必要條件是什么？ 解： 所謂死鎖是指在一個進(jìn)程集合中的所有進(jìn)程都在等待只能由該集合中的其它一個進(jìn)程才能引發(fā)的事件而無限期地僵持下去的局面。 產(chǎn)生死鎖的必要條件有四個： 1） 互斥條件 ， 2） 不剝奪條件 ， 3）請求和保持條件， 4）環(huán)路條件。 解： 死鎖的預(yù)防策略有三，說明如下 ： 1. 摒棄請求和保持條件： 為摒棄請求和保持條件，系統(tǒng)中需要使用靜態(tài)資源分配法，該方法規(guī)定每一個進(jìn)程在開始運行前都必須一次性地申請其在整個運行過程中所需的全部資源。這樣，當(dāng)一個進(jìn)程申請某個資源時，它不能占有其它任何資源，在進(jìn)程運行過程中也不會再提出資源請求。 2. 摒棄不剝奪條件： 要摒棄“不剝奪條件”，可以使 用如下策略：進(jìn)程在需要資源時才提出請求，并且進(jìn)程是逐個地申請所需資源，如果一個進(jìn)程已經(jīng)擁有了部分資源，然后又申請另一個資源而不可得時，其現(xiàn)有資源必須全部釋放。 3. 摒棄環(huán)路等待條件： 為確保環(huán)路等待條件不成立，可以在系統(tǒng)中實行資源有序分配策略，即系統(tǒng)中的所有資源按類型被賦予一個唯一的編號，每個進(jìn)程只能按編號的升序申請資源。某時刻系統(tǒng)中有 5 個進(jìn)程，判斷下列資源狀態(tài)是否安全？若進(jìn)程 P2 申請資源 (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)在對該時刻的狀態(tài)進(jìn)行安全分析： 由于 Available 向量為（ 3， 4， 4， 1），所以 Work 向量初始化為（ 3， 4， 4， 1） 此時的 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 所申請的資源分配給它， 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)行安全性檢測： 此時 Available 向量為（ 2,3,3,0），所以 Work 向量初始化為（ 2,3,3,0），此時的 Work 小于任意的 Need[i]向量，所以系統(tǒng)處于不安全狀態(tài)，所以不可以為 P2 分配資源 (13) 三個進(jìn)程 P P P3 都需要 5 個同類資源才能正常執(zhí)行直到終止，且這些進(jìn)程只有在需要 設(shè)備時才申請，則該系統(tǒng)中不會發(fā)生死鎖的最小資源數(shù)量是多少？請說明理由。 (14) 在解決死鎖問題的幾個方法中，哪種方法最易于實現(xiàn)，哪種方法使資源的利用率最高？ 解： 預(yù)防死鎖這個方法 實現(xiàn)簡單，效果突出 ；避免死鎖這種方法 系統(tǒng)吞吐量和資源利用率較高 。 解： 本題中只有一種資源，不妨設(shè) Max[i]為第 i 個進(jìn)程的資源總共需要量， Need[i]為第 i 個進(jìn)程還需要的資源數(shù)量， Allocation[i]表示第 i 個進(jìn)程已經(jīng)分配到的資源數(shù)量， Available 為系統(tǒng)剩余的資源數(shù)，其中 i=1,2,3,… ,n。 系統(tǒng)剩余的資源數(shù)量為 Available（ Available=0），由假設(shè)，因為系統(tǒng)處于死鎖狀態(tài)，所以 Available 個資源無法 分配出去，所以每個進(jìn)程的 Need[i]都大于 Available， 即 Need[i]=Available+1 所以 ∑ Need[i]=n*(Available+1)=n*Available+n, ① 因為剩下的資源數(shù)是 Available，所以已經(jīng)分配出去的資源數(shù)為 m – Available。 (16) 某車站售票廳，在任何時刻最多可以容納 20 名購票者進(jìn)入，當(dāng)售票廳中少于 20名購票者 時，廳外的購票者可立即進(jìn)入，否則需要在外面等待。 ② 根據(jù)所定義的信號量，寫出相應(yīng)的程序來保證進(jìn)程能夠正確地并發(fā)執(zhí)行。 解： ①定義信號量 S,初值為 20，當(dāng) s 0 時，它表示可以繼續(xù)進(jìn)入購票廳的人數(shù)，當(dāng) s = 0時表示廳內(nèi)已有 20 人正在購票，當(dāng) s 0 時 | s |表示正等待進(jìn)入的人 數(shù)。 begin parbegin procedure:begin repeat wait(s)。 signal(s)。 end parend end ③ 最大值為 20，最小值為 20n (17) 在測量控制系統(tǒng)中的數(shù)據(jù)采集任務(wù)時，把所采集的數(shù)據(jù)送往一單緩沖區(qū)；計算任務(wù)從該單緩沖區(qū)中取出數(shù)據(jù)進(jìn)行計算。 解： semaphore mutex = 1。 semaphore empty = 1。 wait(empty)。 buffer:=nextp。 signal(full)。 end pute: begin repeat ?? wait(full)。 nextc:=buffer。 signal(empty)。 until false。爸爸可以向盤中放蘋果，也可以向盤中放桔子，兒子專等著吃盤中的桔子，女兒專等著吃盤中的蘋果。 解： 本題中應(yīng)設(shè)置三個信號量 S、 So、 Sa，信號量 S 表示盤中是否為空，其初值為 1； So表示盤中是否有桔子，其初值為 0； Sa 表示盤中是否有蘋果，其初值為 0。 兒子： P(