第四次作業(yè)參考答案

第四次作業(yè)參考答案1.作業(yè)Job1–Job5，在時刻0按作業(yè)號的順序依次到達單處理器系統(tǒng)。作業(yè)的執(zhí)行時間，優(yōu)先權(quán)（優(yōu)先權(quán)越高數(shù)值越?。┤缦卤硭荆鹤鳂I(yè)號執(zhí)行時間（ms）優(yōu)先權(quán)Job1103Job211Job323Job414Job552請分別采用先來先服務(wù)、時間片輪轉(zhuǎn)、短作業(yè)優(yōu)先以及非搶占的優(yōu)先權(quán)調(diào)度算法計算作業(yè)的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。答：（1）先來先服務(wù)：作業(yè)達到時間Ts開始時間Tb結(jié)束時間Tf執(zhí)行時間Te周轉(zhuǎn)時間Tr=Tf-Ts帶權(quán)周轉(zhuǎn)時間(Tr/Te)Job1001010101Job20101111111Job3011132136.5Job40131411414Job5014195193.8平均周轉(zhuǎn)時間T(10+11+13+14+19)/5=13.4平均帶權(quán)周轉(zhuǎn)時間W(1+11+6.5+14+3.8)/5=7.26（2）時間片輪轉(zhuǎn)：假設(shè)時間片的長度為1，調(diào)度的順序為1、2、3、4、5、1、3、5、1、5、1、5、1、5、1、1、1、1、1。作業(yè)達到時間Ts開始時間Tb結(jié)束時間Tf執(zhí)行時間Te周轉(zhuǎn)時間Tr=Tf-Ts帶權(quán)周轉(zhuǎn)時間(Tr/Te)Job1001910191.9Job2012122Job3027273.5Job4034144Job504145142.8平均周轉(zhuǎn)時間T(19+2+7+4+14)/5=9.2平均帶權(quán)周轉(zhuǎn)時間W(1.9+2+3.5+4+2.8)/5=2.84（3）短作業(yè)優(yōu)先調(diào)度：作業(yè)達到時間Ts開始時間Tb結(jié)束時間Tf執(zhí)行時間Te周轉(zhuǎn)時間Tr=Tf-Ts帶權(quán)周轉(zhuǎn)時間(Tr/Te)Job2001111Job4012122Job3024242Job5049591.8Job1091910191.9平均周轉(zhuǎn)時間T(1+2+4+9+19)/5=7平均帶權(quán)周轉(zhuǎn)時間W(1+2+2+1.8+1.9)/5=1.74（4）非搶占優(yōu)先級調(diào)度：作業(yè)達到時間Ts開始時間Tb結(jié)束時間Tf執(zhí)行時間Te周轉(zhuǎn)時間Tr=Tf-Ts帶權(quán)周轉(zhuǎn)時間(Tr/Te)Job2001111Job5016561.2Job1061610161.6Job3016182189Job40181911919平均周轉(zhuǎn)時間T(1+6+16+18+19)/5=12平均帶權(quán)周轉(zhuǎn)時間W(1+1.2+1.6+9+19)/5=6.362.在道數(shù)不受限制的多道程序系統(tǒng)中，作業(yè)進入系統(tǒng)的后備隊列時立即進行作業(yè)調(diào)度。現(xiàn)有4個作業(yè)進入系統(tǒng)，有關(guān)信息為：作業(yè)名進入后備隊列的時刻執(zhí)行時間（min）優(yōu)先數(shù)Job18:00601Job28:30502Job38:40304Job48:50103如果作業(yè)調(diào)度和進程調(diào)度均采用高優(yōu)先級調(diào)度算法（數(shù)值越大則優(yōu)先級越高），請計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。答：因為進入系統(tǒng)后立即進行作業(yè)調(diào)度，而且作業(yè)到達的時刻不同，所以后備隊列中沒有作業(yè)，作業(yè)進入就緒隊列等待調(diào)度。調(diào)度順序如下：作業(yè)進入后備隊列的時刻Ts進入就緒隊列的時刻開始時間Tb結(jié)束時間Tf執(zhí)行時間Te（min）周轉(zhuǎn)時間Tr=Tf-Ts（min）帶權(quán)周轉(zhuǎn)時間(Tr/Te)Job18:008:008:009:0060601Job38:408:409:009:3030501.67Job48:508:509:309:4010505Job28:308:309:4010:30501202.4平均周轉(zhuǎn)時間T(60+50+50+120)/4=70平均帶權(quán)周轉(zhuǎn)時間W(1+1.67+5+2.4)/4=2.523.在單道批處理系統(tǒng)中，下列三個作業(yè)采用先來先服務(wù)算法和最高響應(yīng)比優(yōu)先算法進行調(diào)度，哪種算法的性能較好？作業(yè)提交時刻運行時間開始時刻完成時刻周轉(zhuǎn)時間/min帶權(quán)周轉(zhuǎn)時間/min110:002:00210:101:00310:250:25平均周轉(zhuǎn)時間T=平均帶權(quán)周轉(zhuǎn)時間W=答：因為是單道批處理系統(tǒng)，所有內(nèi)存為一個進程所獨占（操作系統(tǒng)除外），其它作業(yè)在外存的后備隊列中等待作業(yè)調(diào)度，當前進程結(jié)束后，根據(jù)作業(yè)調(diào)度算法選擇合適的作業(yè)進入運行。（1）先來先服務(wù)調(diào)度算法：作業(yè)進入后備隊列的時刻Ts進入就緒隊列的時刻開始時間Tb結(jié)束時間Tf執(zhí)行時間Te（min）周轉(zhuǎn)時間Tr=Tf-Ts（min）帶權(quán)周轉(zhuǎn)時間(Tr/Te)Job110:0010:0010:0012:001201201Job210:1012:0012:0013:00601702.83Job310:2513:0013:0013:25251807.2平均周轉(zhuǎn)時間T（min）(120+170+180)/3=156.67平均帶權(quán)周轉(zhuǎn)時間W(1+2.83+7.2)/3=3.68（2）最高響應(yīng)比優(yōu)先算法作業(yè)進入后備隊列的時刻Ts進入就緒隊列的時刻開始時間Tb結(jié)束時間Tf執(zhí)行時間Te（min）周轉(zhuǎn)時間Tr=Tf-Ts（min）帶權(quán)周轉(zhuǎn)時間(Tr/Te)Job110:0010:0010:0012:001201201Job310:2512:0012:0012:25251204.8Job210:1012:2512:2513:25601953.25平均周轉(zhuǎn)時間T（min）(120+120+195)/3=145平均帶權(quán)周轉(zhuǎn)時間W(1+4.8+3.25)/3=3.02結(jié)論：最高響應(yīng)比調(diào)度要優(yōu)于先來先服務(wù)調(diào)度。4.有一個四道作業(yè)的操作系統(tǒng)，若在一段時間內(nèi)先后到達六個作業(yè)，其提交時刻和估計運行時間為：作業(yè)提交時刻估計運行時間（min）18:006028:203538:252048:302558:35568:4010系統(tǒng)采用剩余最短時間調(diào)度算法，作業(yè)被調(diào)度進入系統(tǒng)后不會退出，但作業(yè)運行時可被剩余時間更短的作業(yè)所搶占。請計算平均周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間。答：作業(yè)調(diào)度的順序如下圖所示。作業(yè)進入后備隊列的時刻Ts進入就緒隊列的時刻開始時間Tb結(jié)束時間Tf執(zhí)行時間Te（min）周轉(zhuǎn)時間Tr=Tf-Ts（min）帶權(quán)周轉(zhuǎn)時間(Tr/Te)18:008:008:0010:35601552.5828:208:208:209:5535952.7138:258:258:258:452020148:308:309:009:2525552.258:358:458:458:50515368:408:508:509:0010202平均周轉(zhuǎn)時間T（min）(155+95+20+55+15+20)/6=60平均帶權(quán)周轉(zhuǎn)時間W(2.58+2.71+1+2.2+3+2)/6=2.255.某操作系統(tǒng)采用輪轉(zhuǎn)調(diào)度進程。分配給A類進程時間片長100ms，分配給B類進程的時間片長400ms，若假定就緒隊列中有4個A類進程和1個B類進程。所有進程的平均服務(wù)時間為2s。不考慮I/O和系統(tǒng)開銷，計算A類進程和B類進程的平均周轉(zhuǎn)時間。答：當B類進程沒有結(jié)束時，A、B類進程輪轉(zhuǎn)周期是：0.1s×4+0.4s=0.8s。經(jīng)過5個輪轉(zhuǎn)周期，B進程結(jié)束，此時所需的時間為：0.8s×5=4s，所以B類進程的平均周轉(zhuǎn)時間為4s。B類進程結(jié)束后，再需0.4s×15=6s后，A類進程結(jié)束，A類進程的平均周轉(zhuǎn)時間為4+6=10s6.有三個并發(fā)進程：R負責(zé)從輸入設(shè)備讀入信息塊，M負責(zé)對信息塊進行加工處理，P負責(zé)打印輸出信息塊?，F(xiàn)提供：（1）一個緩沖區(qū)，可放置K個信息塊；（2）兩個緩沖區(qū)，每個緩沖區(qū)可放置K個信息塊。試用信息量和P、V操作寫出三個進程正確的流程。答：（1）進程R、M和P之間存在同步的關(guān)系。設(shè)置資源信號量sread，初始值為K，用于R進程和M進程之間的同步；資源信號量smanage，初始值為0，用于M進程和P進程之間的同步；資源信號量sprint，初始值為0，用于P進程和R進程之間的同步。（2）兩個緩沖區(qū)A、B，A緩沖用于R進程讀入信息塊，M進程從A緩沖中取出信息經(jīng)過加工后放入B緩沖，P進程從B緩沖中取出信息塊輸出，整個過程如下圖所示：針對緩沖區(qū)A，設(shè)置資源信號量sempty_A=K、sfull_A=0，保證R和M的同步；針對緩沖區(qū)B，設(shè)置sempty_B=K、sfull_B=0，保證M和P的同步。7.設(shè)在公共汽車上司機和售票員的活動分別如下。（1）司機的活動：啟動汽車，正常行駛，到站停車。（2）售票員的活動：關(guān)車門，售票，開車門。如汽車不斷到站、停車、行駛的過程中，使用信號量和P、V操作實現(xiàn)其同步。答：在汽車行駛過程中，司機和售票員兩個進程之間的同步關(guān)系為：售票員關(guān)門→售票員向司機發(fā)送開車信號→司機啟動汽車→售票員賣票→到站司機停車→售票員開門上下客。設(shè)置信號量sstart用于司機啟動車輛于售票員關(guān)門的同步，信號量sopen用于售票員開門與司機停車間的同步。兩個信號量的初始值都為0。8.三名吸煙者在同一個房間，還有一位香煙供應(yīng)者。為了制造并抽掉香煙，每位吸煙者需要三樣?xùn)|西：煙草、紙和火柴，供應(yīng)者有豐富的貨物供應(yīng)。三位吸煙者中，第一個人有自己的煙草，第二個人有自己的紙，第三個人有自己的火柴。供應(yīng)者隨機地將兩樣?xùn)|西放在桌子上，允許一位吸煙者進行對健康不利的吸煙。當吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再把兩樣?xùn)|西放在桌子上，喚醒另一個吸煙者。試采用信號量和P、V操作同步他們的過程。答：涉及的進程共有四個：一個供應(yīng)商進程provider，三個吸煙者進程smoker1、smoker2、smoker3。為了保證四個進程的同步，設(shè)置四個信號量sprovider、ssmoker1、ssmoker2、ssmoker3。Sprovider初始值為1，用于阻塞供應(yīng)商進程：當供應(yīng)商提供一類材料供某個吸煙者吸煙后，則不能再繼續(xù)提供材料；ssmoker1初始值為0，用于阻塞第一個吸煙者（擁有煙草的吸煙者）：當供應(yīng)商提供第一個吸煙者所需的材料后，喚醒第一個消費者；ssmoker2（擁有紙的吸煙者）和ssmoker3（擁有火柴的吸煙者）同理。9.理發(fā)店里有一位理發(fā)師、一把理發(fā)椅和n把供等候理發(fā)的顧客休息的椅子。如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺，當有顧客到來時，顧客就喚醒理發(fā)師；如果理發(fā)師正在理發(fā)時又有新顧客到達，那么，如果還有空椅子，顧客就坐下來等候，否則就會離開理發(fā)店。試使用信號量和P、V操作實現(xiàn)同步過程。答：設(shè)置三個信號量用于控制理發(fā)師進程和顧客進程的同步和互斥：customers記錄等候理發(fā)的顧客數(shù)，并用于阻塞理發(fā)師進程，初始值為0；barber記錄正在等候顧客的理發(fā)師數(shù)，并用于阻塞顧客進程，其初始值為0；互斥信號量mutex用于互斥訪問臨界資源，初始值為1。此外由于要對顧客人數(shù)進行計數(shù)，但信號量customers的原子性無法得到顧客人數(shù)，所以單獨設(shè)置一個整形變量waiting，用于記錄待理發(fā)的顧客數(shù)，它是一個臨界資源。10.東西向汽車駛過獨木橋，為了保證交通安全，只要橋上無車，則允許一方的汽車過橋，待其全部過完后才允許另一方的汽車過橋。請用信號量和P、V操作寫出汽車過獨木橋的同步算法。答：汽車過橋的兩個方向設(shè)為A（西→東）、B（東→西），countA和countB為兩個方向過橋時在橋上的汽車數(shù)，初始值為0。使用3個信號量用于控制左邊汽車的過橋進程（left）和右邊汽車過橋進程（right），分別是：mutex，用于左右過河的互斥，初始值為1；mutexA，用于對countA的互斥訪問，初始值為1；mutexB，用于對countB的互斥訪問，初始值為1。11.桌上有一只盤子，最多可容納兩個水果，每次僅能放入或取出一個水果。爸爸向盤子中放蘋果，媽媽向盤子中放橘子，兩個兒子專等吃盤子里的橘子，兩個女兒專等吃盤子里的蘋果。使用信號量和P、V操作解決爸爸、媽媽、兒子和女兒間的同步問題。答：設(shè)置四個信號量用于控制四個進程（父親進程、母親進程、兒子進程和女兒進程）的同步和互斥，這四個信號量分別是：mutex，互斥信號量，初始值為1，用于對盤子的互斥訪問；sapple，資源信號量，初始值為0，表示盤中蘋果的數(shù)量；sorange，資源信號量，初始值為0，表示盤中橘子的數(shù)量；empty，資源信號量，表示還可以向盤中放的水果數(shù)量，初始值為2。12.某銀行辦理存儲業(yè)務(wù)，由n名儲蓄員負責(zé)。每位顧客進入銀行后先至取號機領(lǐng)取一個號并且在等待區(qū)找到空沙發(fā)坐下來等待叫號。取號機給出的號碼依次遞增，并假定有足夠多的空沙發(fā)容納顧客。當一位儲蓄員空閑下來就呼叫下一個號。請使用信號量和P、V操作正確編寫儲蓄員進程和顧客進程的程序。答：涉及的進程有兩類，一類是顧客進程，另一類是儲蓄員進程。設(shè)置三個信號量：mutex，互斥信號量，初始值為1，用于取號、叫號的互斥；scustomer，資源信號量，初始值為0，表示等待服務(wù)的顧客人數(shù)，當其大于0時，喚醒儲蓄員進程服務(wù)；sserver，資源信號量，初始值為n。13.設(shè)當前的系統(tǒng)狀態(tài)如下，此時Available=（1,1,2）。進程ClaimAllocationR1R2R3R1R2R3P1322100P2613511P3314211P4422002（1）系統(tǒng)是否處于安全狀態(tài)？為什么？（2）進程P2發(fā)出請求向量Request2（1,0,1），系統(tǒng)能否把資源分配給它？（3）若在進程P2申請后，P1發(fā)出請求向量Request1（1,0,1），系統(tǒng)能否把資源分配給它？（4）若在進程P1申請資源后，P3發(fā)出請求向量Request3（0,0,1），系統(tǒng)能否把資源分配給它？答：（1）系統(tǒng)此時的資源分配如下：進程ClaimAllocationNeedAvailableR1R2R3R1R2R3R1R2R31,1,2P1322100222P2613511102P3314211103P4422002420由上表可知，當滿足P2的資源要求后，系統(tǒng)的資源分配情況如下表所示：進程ClaimAllocationNeedAvailableR1R2R3R1R2R3R1R2R36,2,3P1322100222P2P3314211103P4422002420滿足P1的資源要求后，系統(tǒng)的資源分配情況如下表所示：進程ClaimAllocationNeedAvailableR1R2R3R1R2R3R1R2R38,4,5P1P2P3314211103P4422002420滿足P4的資源要求后，系統(tǒng)的資源分配情況如下表所示：進程ClaimAllocationNeedAvailableR1R2R3R1R2R3R1R2R38,4,7P1P2P3314211103P4此時可用資源能夠滿足P3的需求。因為存在安全序列P2、P1、P4、P3可保證所有的進程結(jié)束，因此系統(tǒng)是安全的。（2）滿足P2的資源申請后，系統(tǒng)資源的分配情況如下表所示：進程ClaimAllocationNeedAvailableR1R2R3R1R2R3R1R2R30,1,1P1322100222P2613511001P3314211103P4422002420此時還存在安全序列P2、P1、P4、P3保證全部進程結(jié)束，因此系統(tǒng)是安全的。（3）滿足P2的資源申請后，系統(tǒng)的可用資源如上表所示為（0,1,1），P1發(fā)出申請（1,0,1），此時可用資源無法滿足P1的申請，若分配資源后，系統(tǒng)死鎖，因此不能分配。（4）P1申請資源后，系統(tǒng)資源已不足，無法滿足P3的資源申請。14.系統(tǒng)有A、B、C、D四種資源，在某個時刻進程P0、P1、P2、P3和P4對資源的占有和需求情況如下表所示，試解答下列問題。進程AllocationClaimAvailableABCDABCDABCDP0003200441622P110002750P21354361010P303320984P4001406610（1）系統(tǒng)此時處于安全狀態(tài)嗎？（2）若此時進程P2訂正：此處應(yīng)為P2，不是P1。發(fā)出請求request1（訂正：此處應(yīng)為P2，不是P1。答：（1）此時的資源分配情況如下表所示：進程AllocationClaimNeedAvailableABCDABCDABCD1,6,2,2P0003200440012P1100027501750P213543610102356P3033209840652P40014066100656滿足P0的資源要求后，系統(tǒng)的資源分配情況如下表所示：進程AllocationClaimNeedAvailableABCDABCDABCD1,6,5,4P0P1100027501750P213543610102356P3033209840652P40014066100656滿足P3的資源要求后，系統(tǒng)的資源分配情況如下表所示：進程AllocationClaimNeedAvailableABCDABCDABCD1,9,8,6P0P1100027501750P213543610102356P3P40014066100656滿足P1的資源要求后，系統(tǒng)的資源分配情況如下表所示：進程AllocationClaimNeedAvailableABCDABCDABCD2,9,8,6P0P1P213543610102356P3P40014066100656到此，剩下的P2和P4，無論誰再提出申請，系統(tǒng)可用的資源均可滿足。因為存在安全序列P0、P3、P1、P2、P4，使得所有進程均可結(jié)束，所以系統(tǒng)是安全的。（2）滿足P2的資源申請后，系統(tǒng)的資源分配情況如下表所示：進程AllocationClaimNeedAvailableABCDABCDABCD0,4,0,0P0003200440012P1100027501750P225763610101134P3033209840652P40014066100656此時，系統(tǒng)資源已不能滿足任何一個進程的資源申請，系統(tǒng)處于不安全狀態(tài)，因此不能滿足P2的資源請求。15.已知：Need=1100（1）系統(tǒng)此時處于安全狀態(tài)嗎？（2）若第二個進程提出資源請求request2(0,0,1,0)，系統(tǒng)能分配資源給它嗎？（