武大操作系统各章习题解答

第1章3（9）p(22)假定操作系统的运行时间忽略不计，并能最大程度地并发执行.用户可用内存：1MB-200KB=824KB可以存放用户进程：824KB/200KB=4个4个进程同时I/O的概率为：0.84=0.41则CPU利用率=1-0.41=59%

3（9）2增加1MB内存，可装入9个用户进程，9个进程同时I/O的概率为：0.89=0.13则CPU利用率=1-0.13=87%所以提高的利用率是28%第1章3（10）2个作业并发执行的工作情况如下图所示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)根据Bernstein条件，先求出每条语句的读集和写集：R(S1)={x}W(S1)={a}R(S2)={y}W(S2)={b}R(S3)={a，b}W(S3)={c}R(S4)={c}W(S4)={d}因R(S1)∩W(S2)={}R(S2)∩W(S1)={}W(S1)∩W(S2)={}故语句S1和S2可以并发执行。第2章3（4）续又R(S3)∩W(S4)={}R(S4)∩W(S3)={c}W(S3)∩W(S4)={}故语句S3和S4不能并发执行。第2章3（7）在该公式的求值过程中，有些运算分量的执行是可以并行进行的。为了描述方便起见，我们设置了一些中间变量保存中间结果，并给每个语句命名，如下所示。第2章3（7）续1其求值过程如下图所示。开始S1：X1=A*AS2：X2=3*BS3：X3=5*AS4：X4=X1＋X2S5：X5=B＋X3S6：X6=X4/X5结束第2章3（7）续2其求值过程的前趋图如下图所示。S1S2S3S4S5S6第2章3（9）产生每一种变化的具体原因如下表所示。

变化原因（1）时间片用完（2）因等待数据资源而阻塞（3）因等待I/O而阻塞（4）因获得数据资源被唤醒（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)在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客上下车。第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个作业并发执行的工作情况如下图所示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）由题设可知，当前时刻系统中有三个进程，P4尚未到达资源情况进程MaxAllocation

Need

AvailableP170254540P2604020

P3604515

P4第4章3（10）2P4到达，最大需求60，目前请求25，则此时的系统资源情况如下：资源情况进程MaxAllocation

Need

AvailableP170254540P2604020

P3604515

P460060第4章3（10）3若P4请求25个资源，系统按银行家算法进行检查：RequestP4(25)≤NeedP4(60)RequestP4(25)≤Available(40)系统先假定可为P4分配资源，并修改有关数据，如下所示。第4章3（10）4为P4分配资源后的情况如下：资源情况进程MaxAllocation

Need

AvailableP170254515P2604020

P3604515

P4602535第4章3（10）5再利用安全性算法检查此时系统是否安全，可得如下所示的安全性分析。第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个资源，系统按银行家算法进行检查：RequestP4(35)≤NeedP4(60)RequestP4(35)≤Available(40)系统先假定可为P4分配资源，并修改有关数据，如下所示。第4章3（10）9为P4分配资源后的情况如下：资源情况进程MaxAllocation

Need

AvailableP17025455P2604020

P3604515

P4603525可以看出，系统空闲资源已不能满足任何进程的需要，试分配作废，让进城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假设该系统发生死锁，那么m个资源应该全部分配出去，即alloc（1）＋…＋alloc（n）=m由上述两式可得：need（1）＋…＋need（n）＜n第4章3（12）3上式表示死锁发生后，n个进程还需要的资源量之和小于n，这意味着此刻至少存在一个进程i，

need（i）=0，即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放所占有的全部资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。D释放第5章题3（6）p(129)

0128K256K384K512K640K768K896K1M初始状态A申请70B申请35C申请80A释放D申请60KB释放C释放512K256KAA512K256KBAB512KCB512KCB512KCD128K512KCD64512KC256K128K128K6464128K64128K128K128K128K128K第5章题3（6）2释放作业B的二叉树DC1M512K256K128K64K第6章题3（5）p(147)1）改为页面地址长度是多少？页面地址长度是12位。2）虚地址空间共有220个页面缓存命中，需要时间A；在内存但不在缓存，需要时间A+B；不在内存在辅存，需要时间A+B+C数据平均访问时间为：第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位二进制数（28＝256）表示，因此一屏信息需要存储空间：8×300×210位＝300×210字节