【正文】 兒： begin repeat ﹎﹎﹎﹎﹎﹎﹎﹎ 拿盒中的桔子 ﹎﹎﹎﹎﹎﹎﹎﹎ 吃桔子 until false end 女： begin repeat ﹎﹎﹎﹎﹎﹎﹎﹎ 拿盒中的蘋果 ﹎﹎﹎﹎﹎﹎﹎﹎ 吃蘋果 until false end parend end 18 3． 假定在一個處理機上執(zhí)行以下五個作業(yè)： 作業(yè)號 到達時間 運行時間 A 0 4 B 1 3 C 2 5 D 3 2 E 4 4 (1)畫出采用 FCFS調(diào)度算法時調(diào) 度圖，并計算每個作業(yè)的周轉(zhuǎn)時間和計算平均周轉(zhuǎn)時間。 (2)畫出采用 SJF調(diào)度算法時調(diào)度圖，并計算每個作業(yè)的周轉(zhuǎn)時間和計算平均周轉(zhuǎn)時間。 (3)寫出采用 HRN（響應(yīng)比高者優(yōu)先）調(diào)度算法時選擇作業(yè)號的次序和選擇作業(yè)的依據(jù)（各作業(yè)的響應(yīng)比）。 4．試描述避免死鎖的銀行家算法，若系統(tǒng)運行中出現(xiàn)下述資源分配情況 進程 ALLOCATION NEED AVAILABLE A B C D A B C D A B C D P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 該系統(tǒng)是否安全？如果進程 P2此時提出資源申請（ 1， 2， 2， 2），系統(tǒng)能否將資源分配給它？為什么？ 答案 ： 1．解 : 首先找出兩進程并發(fā)執(zhí)行時必須在執(zhí)行序列上遵循的同步規(guī)則： 第 1條同步規(guī)則是 只有當(dāng) P 進程“ Add to BufI”后， Q 進程才能來“ Remove from BufI”， 否則 Q進程只能等待 。 為了滿足第 1條同步規(guī)則，設(shè)置一個同步信號量 fullI，它是后做動作的 Q進程擁有的私有資源，它是 Q進程動作“ Remove from BufI”成功所需的資源――緩沖器 BufI裝滿輸入數(shù)據(jù)，由于初始時緩沖器 BufI空，它的初值為 0。后做動作的 Q進程在動作“ Remove from BufI”前對信號量 fullI施加 P操作，表示申請資源。由于它又是消耗性的資源，必須由先做動作“ add to BufI”的 P進程在動作完成后對信號量 fullI施加 V操作，表示釋放資源。（這在課件答案中用紅的顏色字表示） 兩進程并發(fā)執(zhí)行時必須在執(zhí)行序列上遵循的同步規(guī)則還有三個： 第二條同步規(guī)則是只有當(dāng) Q進程“ Remove from BufI”后， P進程才能將“ add to BufI” ,否則 P 進程也只能等待。為了滿足第 2 條同步規(guī)則，設(shè)置另一個同步信號量 emptyI，它是后做動作的進程 P所擁有的私有資源，它代表的資源是緩沖器 BufI空，它的初值為 1 。后做動作的 P進程在“ add to BufI”動作前對信號量 emptyI施加 P操作，表示申請資源。由于它又是消耗性的資源，必須由它的合作進程 Q“ Remove from BufI”后對 emptyI信號量施加 V操作來釋放資源。（這在課件答案中用黑的顏色字表示） 第三條同步規(guī)則是 只有當(dāng) Q 進程“ Add to BufO”后， R 進程才能來“ Remove from BufO”， 19 否則 R進程只能等待 。 為了滿足第 3條同步規(guī)則，設(shè)置一個同步信號量 fullO，它是后做動作的 R進程擁有的私有資源，它是 R進程動作“ Remove from BufO”成功所需的資源――緩沖器 BufO裝滿處理過的數(shù)據(jù)，由于初始時緩沖 BufO器空，它的初值為 0。后做動作的 R進程在動作“ Remove from BufO”前對信號量 fullO施加 P操作，表示申請資源。由于它又是消耗性的資源，必須由先做動作“ add to BufO”的 Q 進程在動作完成后對信號量 fullO 施加 V操作，表示釋放資源。（這在課件答案中用綠的顏色字表示） 第四條同步規(guī)則是只有當(dāng) R進程“ Remove from BufO”后， Q進程才能將“ add to BufO” ,否則 Q 進程也 只能等待。為了滿足第 4 條同步規(guī)則，設(shè)置另一個同步信號量 emptyO，它是后做動作的進程 Q所擁有的私有資源，它代表的資源是緩沖器 BufO空，它的初值為 1 。后做動作的 Q進程在“ add to BufO”動作前對信號量 emptyO施加 P操作，表示申請資源。由于它又是消耗性的資源，必須由它的合作進程 R在“ Remove from BufO”后對 emptyO信號量施加 V操作來釋放資源。（這在課件答案中用蘭的顏色字表示） Program ito。 var BufI,BufO:buffer。 var BufI,BufO:buffer。 (信號量 )﹎ emptyI,fullI,emptyO,fullO﹎ :SEMAPHORE:= (信號量初值 )﹎ 1,0,1,0。﹎； begin parbegin procedure P begin repeat input from IO。 ﹎﹎﹎﹎ P(emptyI) 。﹎﹎﹎﹎ Add to BufI。 ﹎﹎﹎﹎ V(fullI) 。﹎﹎﹎﹎ until false end。 procedure Q。 begin repeat ﹎﹎ P(fullI) 。﹎﹎﹎ Remove from BufI。 ﹎﹎ V(emptyI) 。﹎﹎﹎﹎ transform。 ﹎﹎ P(emptyO) 。﹎﹎﹎﹎ Add to BufO。 ﹎﹎ V(fullO) 。﹎﹎﹎﹎﹎ until false end。 procedure R。 begin repeat 20 ﹎﹎ P(fullO) 。﹎﹎﹎ Remove from BufO。 ﹎ V(emptyO) 。﹎﹎ Output ...。 until false end。 parend end : var (信號量 )﹎﹎ S , S1 , S2 ﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎ ： semaphore： = (信號量初值 ) ﹎﹎ 1 , 0 , 0 ﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎； begin parbegin 媽 :begin repeat 準(zhǔn)備 ﹎﹎ P (S ) ﹎﹎ 向盒內(nèi)放桔子 ﹎﹎ V (S1 ) ﹎﹎ 準(zhǔn)備 ﹎﹎ P (S ) ﹎﹎ 向盒內(nèi)放蘋果 ﹎﹎ V (S2) ﹎﹎ until false end 兒： begin repeat ﹎﹎ P (S1 ) ﹎﹎ 拿盒中的桔子 ﹎﹎ V (S) ﹎﹎ 吃桔子 until false end 女： begin repeat ﹎﹎ P (S2 ) ﹎﹎ 拿盒中的蘋果 ﹎﹎ V (S) ﹎﹎ 吃蘋果 until false end parend end 21 3． 解 : 1. 先來先服務(wù)調(diào)度算法 FCFS作業(yè)調(diào)度次序的計算： FCFS按照作業(yè)到達的先后次序 來選擇作業(yè)，按作業(yè)到達 時間 的先后次序五個作業(yè)調(diào)度次序為 A、 B、 C、 D、 E。 2. 短作業(yè)優(yōu)先調(diào)度算法 SJF作業(yè)調(diào)度次序的計算： SJF在到達的作業(yè)中挑選所需運行時間最短的作業(yè)進入主存先運行，調(diào)度次序如下： T=0：只有作業(yè) A已到達，調(diào)度作業(yè) A運行。 T=4：作業(yè) A完成，作業(yè) B、 C、 D、 E已全部到達，比較作業(yè) B、 C、 D、 E的運行時間，按運行時間短的作業(yè)先運行，則調(diào)度次序為 D、 B、 E、 C。 調(diào)度圖： T 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 FCFS A A A A B B B C C C C C D D E E E E SJF A A A A D D B B B E E E E C C C C C 進 程 A B C D E 平均 到達時間 Ta 0 1 2 3 4 運行時間 TS 4 3 5 2 4 FCFS 完成時間 Tf 周轉(zhuǎn)時間 Tq 4 4 7 6 12 10 14 11 18 14 9 SJF 完成時間 Tf 周轉(zhuǎn)時間 Tq 4 4 9 8 18 16 6 3 13 9 8 (HRRN)(作業(yè) )調(diào)度算法作業(yè)調(diào)度次序的計算： T=0：只有作業(yè) A已到達，調(diào)度作業(yè) A運行。 T=4：作業(yè) A完成，作業(yè) B、 C、 D、 E已到達，計算作業(yè) B、 C、 D、 E響應(yīng)比 RP分別為： 1+3/1+2/ 1+1/ 1+0/4，作業(yè) B響應(yīng)比最大調(diào)度運行。 T=7：作業(yè) B完成，作業(yè) C、 D、 E已到達，計算作業(yè) C、 D、 E響應(yīng)比 RP分別為： 1+5/ 1+4/1+3/4，作業(yè) D響應(yīng)比最大調(diào)度運行。 T=9：作業(yè) D完成，作業(yè) C、 E已到達，計算作業(yè) C、 E響應(yīng)比 RP分別為： 1+7/ 1+5/4，作業(yè) C響應(yīng)比最大調(diào)度運行。 T=14：作業(yè) C完成，作業(yè) E已到達，調(diào)度作業(yè) E運行。 T=18：作業(yè) E完成。 4. 解 : 進程 Allocation Need Availabe Avelable+ Allocation No A B C D A B C D A B C D A B C D P0 0 0 3 2 0 0 1 2 1 6 2 2 1 6 5 4 1 P1 1 0 0 0 1 7 5 0 1 9 8 6 2 9 8 6 3 P2 1 3 5 4 2 3 5 6 2 9 8 6 3 12 13 10 4 P3 0 3 3 2 0 6 5 2 1 6 5 4 1 9 8 6 2 P4 0 0 1 4 0 6 5 6 3 12 13 10 3 12 14 14 5 可以找到一個 安全序列 {P0、 P P P P4}，系統(tǒng)是安全的。 進程 P2此時提出資源申請（ 1， 2， 2， 2） , 如系統(tǒng)實施此次分配使系統(tǒng)可用 資源 減到 （ 0， 4， 22 0， 0）， 再也無法滿足各進程對資源的需求，系統(tǒng)進入一個不安全狀態(tài)， 系統(tǒng)不能將資源分配給進程 P2。 進程 Allocation Need Availabe Avelable+ Allocation No A B C D A B C D A B C D A B C D P0 0 0 3 2 0 0 1 2 0 4 0 0 P1 1 0 0 0 1 7 5 0 P2 2 5 7 6 1 1 3 4 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 第三章 1. 某虛擬存儲器的用戶空間共有 32 個頁面，每頁 lKB，主存為 16KB。假定某時刻系統(tǒng)為用戶的第 0、 l、 3頁分別分配到物理塊號為 7中，試分別寫出虛擬地址1234和 2345的頁號 和頁內(nèi)地址，并將虛擬地址變換為物理地址。 2． 考慮一個分頁系統(tǒng)，其頁表存放在內(nèi)存， 如果內(nèi)存讀寫周期為 ， 快表的訪問時間為 。如果設(shè)立一個可存放 64 個頁表表項的快表，