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