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

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

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

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

過(guò)河；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）；

過(guò)河；P（mutexr）；countr--；if（countr==0）V（mutexl）；V（mutexr）；}本題中使用4個(gè)信號(hào)量：S1表示是否可以開始點(diǎn)菜，初值為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){

顧客到達(dá)；

p(S1)；接受顧客點(diǎn)菜；

v(S2)；

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

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

Need

AvailableP170254540P2604020

P3604515

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

Need

AvailableP170254540P2604020

P3604515

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

Need

AvailableP170254515P2604020

P3604515

P4602535第4章3（10）5再利用安全性算法檢查此時(shí)系統(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資源情況進(jìn)程第4章3（10）7可以找到安全序列{P3、P1、P2、P4}，故可以將資源分配給進(jìn)程P4。第4章3（10）8若P4請(qǐng)求35個(gè)資源，系統(tǒng)按銀行家算法進(jìn)行檢查：RequestP4(35)≤NeedP4(60)RequestP4(35)≤Available(40)系統(tǒng)先假定可為P4分配資源，并修改有關(guān)數(shù)據(jù)，如下所示。第4章3（10）9為P4分配資源后的情況如下：資源情況進(jìn)程MaxAllocation

Need

AvailableP17025455P2604020

P3604515

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

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

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