武大操作系統(tǒng)各章習題解答

第1章3（9）p(22)假定操作系統(tǒng)的運行時間忽略不計，并能最大程度地并發(fā)執(zhí)行.用戶可用內(nèi)存：1MB-200KB=824KB可以存放用戶進程：824KB/200KB=4個4個進程同時I/O的概率為：0.84=0.41則CPU利用率=1-0.41=59%

3（9）2增加1MB內(nèi)存，可裝入9個用戶進程，9個進程同時I/O的概率為：0.89=0.13則CPU利用率=1-0.13=87%所以提高的利用率是28%第1章3（10）2個作業(yè)并發(fā)執(zhí)行的工作情況如下圖所示CPUABABA打印CPUCPU打印B輸入等待CPUCPU時間050100150200250300輸入B打印AA第1章3（10）①CPU有空閑等待，在100~150之間。因為A在打印，B在輸入。②B有等待CPU的情況，從0到50，180到200在等待。第2章3（4）p(41)根據(jù)Bernstein條件，先求出每條語句的讀集和寫集：R(S1)={x}W(S1)={a}R(S2)={y}W(S2)=R(S3)={a，b}W(S3)={c}R(S4)={c}W(S4)=c713r2r因R(S1)∩W(S2)={}R(S2)∩W(S1)={}W(S1)∩W(S2)={}故語句S1和S2可以并發(fā)執(zhí)行。第2章3（4）續(xù)又R(S3)∩W(S4)={}R(S4)∩W(S3)={c}W(S3)∩W(S4)={}故語句S3和S4不能并發(fā)執(zhí)行。第2章3（7）在該公式的求值過程中，有些運算分量的執(zhí)行是可以并行進行的。為了描述方便起見，我們設置了一些中間變量保存中間結果，并給每個語句命名，如下所示。第2章3（7）續(xù)1其求值過程如下圖所示。開始S1：X1=A*AS2：X2=3*BS3：X3=5*AS4：X4=X1＋X2S5：X5=B＋X3S6：X6=X4/X5結束第2章3（7）續(xù)2其求值過程的前趨圖如下圖所示。S1S2S3S4S5S6第2章3（9）產(chǎn)生每一種變化的具體原因如下表所示。

變化原因（1）時間片用完（2）因等待數(shù)據(jù)資源而阻塞（3）因等待I/O而阻塞（4）因獲得數(shù)據(jù)資源被喚醒（5）因I/O完成被喚醒第3章3(7)p(72)本題中使用一個信號量m用于互斥過河。同步算法描述如下：P（m）；過河；V（m）；第3章3(7)2若允許同向的多輛車通行本題中使用三個信號量：mutexl、mutexr用于互斥訪問共享變量countl及countr，初值均為1。wait用于申請過橋，初值也為1。同步算法描述如下：

第3章3(7)3semaphoremutexl=1；semaphoremutexr=1；semaphorewait=1；intcountl=0；Intcountr=0；main(){cobeginpassl()；passr()；coend}第3章3(7)4passl(){P（wait）；P（mutexl）；countl++；if（countl==1）P（mutexr）；V（mutexl）；V（wait）；

過河；P（mutexl）；countl--；if（countl==0）V（mutexr）；V（mutexl）；}第3章3(7)5passr(){P（wait）；P（mutexr）；countr++；if（countr==1）P（mutexl）；V（mutexr）；V（wait）；

過河；P（mutexr）；countr--；if（countr==0）V（mutexl）；V（mutexr）；}本題中使用4個信號量：S1表示是否可以開始點菜，初值為1S2表示是否可以開始做菜，初值為0S3表示是否可以開始打包，初值為0S4表示是否可以提交食品，初值為0同步算法描述如下：第3章3(10)第3章3(10)2semaphoreS1=1；semaphoreS2=0；semaphoreS3=0；semaphoreS4=0；main(){cobeginLB（）；CS（）；DBG（）；

CNY（）；coend}第3章3(10)3LB(){while(true){

顧客到達；

p(S1)；接受顧客點菜；

v(S2)；

}}第3章3(10)4CS(){while(true){p(S2)；準備顧客的飯菜；

v(S3)；

}}第3章3(10)5DBG(){while(true){p(S3)；打包顧客的飯菜；

v(S4)；

}}第3章3(10)6CNY(){while(true){p(S4)；收款并提交食品；

v(S1)；

}}第3章3(11)在汽車行駛過程中，司機活動與售票員活動之間的同步關系為：售票員關車門后，向司機發(fā)開車信號，司機接到開車信號后啟動車輛，在汽車正常行駛過程中售票員售票，到站時司機停車，售票員在車停后開車門讓乘客上下車。第3章3(11)2在本題中，應設置兩個信號量：s1、s2，s1表示是否允許司機啟動汽車，其初值為0；s2表示是否允許售票員開門，其初值為0。用P、V原語描述如下：第3章3(11)3semaphores1=0;semaphores2=0;main(){cobegindriver();busman();coend}第3章3(11)4driver(){while(true){p(s1);啟動車輛;正常行車;到站停車;v(s2);}}第3章3(11)5busman(){while(true){關車門;v(s1);售票;p(s2);開車門;上下乘客;}}第4章3（8）題p(101)3個作業(yè)并發(fā)執(zhí)行的工作情況如下圖所示Job2CPUJob3Job2Job1Job3Job1Job3Job1I2CPUI1CPU等待I2Job2CPUI1CPU等待I2Job3等待CPUI1CPU等待CPUI1時間(ms)0102030405060708090100110I2Job1Job2Job1I1Job2Job1Job3Job3第4章3（8）2由圖中可以看出：Job1從投入到運行完成需要110msJob2從投入到運行完成需要90msJob3從投入到運行完成需要110ms第4章3（8）3CPU在時間段60ms至70ms，80ms至90ms，100ms至110ms期間空閑，所以CPU的利用率為：(110－30)/110=72.7％。第4章3（8）4設備I1在時間段20ms至40ms，90ms至100ms期間空閑，所以設備I1的利用率為：(110－30)/110=72.7％；設備I2在時間段30ms至50ms期間空閑，所以設備I2的利用率為：(110－20)/110=81.8％。第4章3（10）由題設可知，當前時刻系統(tǒng)中有三個進程，P4尚未到達資源情況進程MaxAllocation

Need

AvailableP170254540P2604020

P3604515

P4第4章3（10）2P4到達，最大需求60，目前請求25，則此時的系統(tǒng)資源情況如下：資源情況進程MaxAllocation

Need

AvailableP170254540P2604020

P3604515

P460060第4章3（10）3若P4請求25個資源，系統(tǒng)按銀行家算法進行檢查：RequestP4(25)≤NeedP4(60)RequestP4(25)≤Available(40)系統(tǒng)先假定可為P4分配資源，并修改有關數(shù)據(jù)，如下所示。第4章3（10）4為P4分配資源后的情況如下：資源情況進程MaxAllocation

Need

AvailableP170254515P2604020

P3604515

P4602535第4章3（10）5再利用安全性算法檢查此時系統(tǒng)是否安全，可得如下所示的安全性分析。第4章3（10）6NeedP1：45NeedP2：20NeedP3：15NeedP4：35AllocP1：25AllocP2：40AllocP3：45AllocP4：25P3P1P2P4

true

true

truetrueFinish60

4515

15P3

15025

35

125P4

125402085P285254560P1Work+Alloc

AllocNeed

Work資源情況進程第4章3（10）7可以找到安全序列{P3、P1、P2、P4}，故可以將資源分配給進程P4。第4章3（10）8若P4請求35個資源，系統(tǒng)按銀行家算法進行檢查：RequestP4(35)≤NeedP4(60)RequestP4(35)≤Available(40)系統(tǒng)先假定可為P4分配資源，并修改有關數(shù)據(jù)，如下所示。第4章3（10）9為P4分配資源后的情況如下：資源情況進程MaxAllocation

Need

AvailableP17025455P2604020

P3604515

P4603525可以看出，系統(tǒng)空閑資源已不能滿足任何進程的需要，試分配作廢，讓進城P4等待。第4章3（12）解：設max（i）表示第i個進程的最大資源需求量，need（i）表示第i個進程還需要的資源量，alloc（i）表示第i個進程已分配的資源量。由題設條件可知：第4章3（12）2max（1）＋…＋max（n）=（need（1）＋…＋need（n））＋（alloc（1）+…＋alloc（n））<m＋n假設該系統(tǒng)發(fā)生死鎖，那么m個資源應該全部分配出去，即alloc（1）＋…＋alloc（n）=m由上述兩式可得：need（1）＋…＋need（n）＜n第4章3（12）3上式表示死鎖發(fā)生后，n個進程還需要的資源量之和小于n，這意味著此刻至少存在一個進程i，

need（i）=0，即它已獲得了所需要的全部資源。既然該進程已獲得了它所需要的全部資源，那么它就能執(zhí)行完成并釋放所占有的全部資源，這與前面的假設矛盾，從而證明在這個系統(tǒng)中不可能發(fā)生死鎖。D釋放第5章題3（6）p(129)

0128K256K384K512K640K768K896K1M初始狀態(tài)A申請70B申請35C申請80A釋放D申請60KB釋放C釋放512K256KAA512K256KBAB512KCB512KCB512KCD128K512KCD64512KC256K128K128K6464128K64128K128K128K128K128K第5章題3（6）2釋放作業(yè)B的二叉樹DC1M512K256K128K64K第6章題3（5）p(147)1）改為頁面地址長度是多少？頁面地址長度是12位。2）虛地址空間共有220個頁面緩存命中，需要時間A；在內(nèi)存但不在緩存，需要時間A+B；不在內(nèi)存在輔存，需要時間A+B+C數(shù)據(jù)平均訪問時間為：第6章題3（6）nn-1×A+(A+B)n1×mm-1×(A+B+C)n1×m1×+第6章題3（7）頁表項為248-13=235反置頁表項為2332-13=219第6章題3（8）存儲器的平均存儲時間為T=P*TC+(1-P)*(TC+TM)P=0.7時，T1=0.7*60+0.3*(60+1000)=360nsT2=0.7*80+0.3*(80+900)=350ns此時P2快P=0.9時，T1=0.9*60+0.1*(60+1000)=160nsT2=0.9*80+0.1*(80+900)=170ns此時P1快第7章題3（6）p(171)屏幕上有像素：640×480＝300×210個當用256彩色顯示時，每個像素需要8位二進制數(shù)（28＝256）表示，因此一屏信息需要存儲空間：8×300×210位＝300×210字節(jié)