操作系统课后习题总结(清华大学出版社)

1、习题二参考答案4、答：在生产者消费者问题中，Producer进程中P（empty）和P(mutex)互换先后次序。先执行P(mutex)，假设成功，生产者进程获得对缓冲区的访问权，但如果此时缓冲池已满，没有空缓冲区可供其使用，后续的P（empty）原语没有通过，Producer阻塞在信号量empty上,而此时mutex已被改为0，没有恢复成初值1。切换到消费者进程后,Consumer进程执行P（full）成功，但其执行P（mutex）时由于Producer正在访问缓冲区，所以不成功，阻塞在信号量mutex上。生产者进程和消费者进程两者均无法继续执行，相互等待对方释放资源，会产生死锁。在生产者和

2、消费者进程中，V操作的次序无关紧要，不会出现死锁现象。5、答：6、答：设信号量sp用于控制对盘子的互斥操作，信号量sg1用于计数，表示盘子中的苹果数目，信号量sg2用于计数，表示盘子中的桔子数目。Semaphore sp=1,sg1=0,sg2=0dad()while(1) prepare an apple; p(sp);put an apple on the plate;v(sg2);mom()while(1) prepare an orange; p(sp);put an orange on the plate;v(sg1);son()while(1) p(sg1);take an ora

3、nge from the plate;v(sg);eat the orange;daughter()while(1) p(sg2);take an apple from the plate;v(sg);eat the apple;7、答：为了使写者优先，在原来的读优先算法基础上增加一个初值为1的信号量S，使得当至少有一个写者准备访问共享对象时，它可使后续的读者进程等待写完成；初值为0的整型变量writecount，用来对写者进行计数；初值为1的互斥信号量wmutex，用来实现多个写者对writecount的互斥访问。reader（） while（1） P（s）； P（rmutex）； if（r

4、eadcount= =0）P（mutex）； readcount+； V（rmutex）； V（S）； 读文件； P（rmutex）； readcount ; if (readcount=0)V(mutex); V(rmutex); writer() while(1) P(wmutex); if(writecount= =0)P(S); writecount+; V(wmutex); P(mutex); 写文件； V（mutex）； P（wmutex）； writecount- -； If （writecount= =0）V(S); V (wmutex);9、答：信号量sofa：表示等候椅数，

5、初值为n信号量empty：表示理发椅空，初值为1信号量full：表示理发椅上有顾客，初值为0count：记录等候椅上的人数，初值为0信号量mutux：用来实现对变量count的互斥访问Var mutex,sofa,empty,full: semaphore=1,n,1,0; count: integer: =0;Guest: Barber:begin begin repeat repeatP(mutex); P(full)if (count=n) then 剪发;begin V(empty); V(mutex); until false 离开; endend else begin count:

6、=count+1; if (count1) then /多个顾客时，坐等候椅上 V(mutex); P(sofa); 坐沙发等; P(empty); 坐椅子上; V(sofa);V(full); else /只有一个顾客时，坐到理发椅上 begin V(mutex); P(empty); 坐椅子上; V(full); end 剪发 离开； P(mutex); count:=count-1; V(mutex); end until falseend11、答：本题中中共有三类进程，相当于机房管理员进程guard，学生进程student和教师进程teacher。相应的信号量和各个进程描述如下：sem

7、aphore computer=2m; /*对应于计算机的资源信号量*/semaphore student=0; /*对应于欲进入机房的学生*/semaphore enter=0; /*用来控制学生是否可进入机房*/semaphore finish=test=0; /*用来同步学生和教师教师须检查实习完毕的学生*/student_i() /*i=1,2,2n*/ V(student); /*激活管理员，有学生到达，要进入机房实验*/ P(enter); /*等待管理员激活进入机房*/ 进入机房上机实习； V(finish)； /*激活教师已经做完实验*/ P(test); /*等待教师检查作业

8、*/ 离开机房； V(computer)； /*所占用的计算机变为空闲*/ guard() int i; for(i=0;i+;in) P(computer); /*等待有两个空闲计算机*/ P(computer); P(student); /*等待有两个学生达到*/ P(student); V(enter); /*激活两个等待进入机房的学生*/ V(enter); teacher() int i; for(i=0;i+;in) P(finish); /*等待两个学生完成实验*/ P(finishi); 检查两个学生的实习结果； V(test)； /*检查完后，激活两个学生检查完毕，可以离开机

9、房*/ V(test); 附加1：图书馆阅览室问题问题描述：假定阅览室最多可同时容纳100个人阅读，读者进入时，必须在阅览室门口的一个登记表上登记，内容包括姓名、座号等，离开时要撤掉登记内容。用P、V操作描述读者进程的同步算法。mutex,emptyseat semaphore; 阅读;mutex=1,Emptyseat=100; P(mutex);Cobegin 查登记表，置空；Reader(i) V(mutex); P(Emptyseat); 离开； P(mutex); V(Emptyseat); 查登记表，登记姓名，座位号等； V(mutex); Coend附加2：哲学家就餐问题给所有哲

10、学家编号，奇数号的哲学家必须先拿左边的筷子，偶数号的哲学家必须先拿右边的筷子。这样，任何一个哲学家拿到一支筷子后，就已经阻止了他邻座的一个哲学家吃饭的企图，除非某个哲学家一直吃下去，否则不会有人会饿死。Repeat elsebegin begin if (i mod 2)！=0 then P(chopstick(i+1) mod 5); begin P(chopsticki); P(chopsticki); eat; P(chopstick(i+1) mod 5); V(chopstick(i+1) mod 5); eat; V(chopsticki); V(chopsticki); thin

11、k; V(chopstick(i+1) mod 5); end think; end end until false;第三章 习题答案6、答：（1）采用先来先服务调度算法，则其调度顺序是1、2、3、4。作业号提交时间运行时间开始时间完成时间周转时间带权周转时间110.02.010.012.02.01.0210.21.012.013.02.82.8310.40.513.013.53.16.2410.50.313.513.83.311.0平均周转时间：T=(2.0+2.8+3.1+3.3)/4=2.8平均带权周转时间：T=(1.0+2.8+6.2+11)/4=5.25（2）采用短作业优先调度算法，

12、则其调度顺序是1、4、3、2。作业号提交时间运行时间开始时间完成时间周转时间带权周转时间110.02.010.012.02.01.0210.50.312.012.31.86.0310.40.512.312.82.44.8410.21.012.813.83.63.6平均周转时间：T=(2.0+1.8+2.4+3.6)/4=2.45平均带权周转时间：T=(1.0+6.0+4.8+3.6)/4=3.857、答：各个作业执行的时间如下图所示：8:00 8:10 8:20 8:30 8:40 8:50 9:00 9:10 9:20 9:3012345注：深黑色表示作业独占CPU时间，浅黑色表示作业平分C

13、PU时间，白色表示CPU空闲时间。（1）作业调度顺序是：1，3，4，2，5。（2）最大作业周转时间为55分钟。（3）全部作业运行结束的时刻为：9：30 8、答：8：00时,作业1运行；9：10时，作业1运行完毕，其他3个作业均已到达，它们的响应比分别为：R2=1+(9:10-8:40)/30=2；R3=1+(9:10-8:50)/10=3；R4=1+(9:10-9:10)/5=1作业3先运行，10分钟后，作业3运行完毕。9：20时，作业3运行完毕，其他两个作业的响应比是：R2=1+(9:20-8:40)/30=2.3R4=1+(9:20-9:10)/5=3作业4先运行，5分钟后，作业4运行完毕

14、，最后作业2运行。作业的执行顺序为：1、3、4、2。第四章 习题答案2、答：(1)Need=(2) Work值的变化情况如下：因为存在一个安全序列，所以系统处于安全状态。(3)先试着满足P1进程的要求，存在一个安全序列，所以系统仍处于安全状态，所以P1的这个请求应该马上满足。3、答：当N3时没有死锁的危险。当N=4时，可能出现四个进程各自占有2台磁带机，又各自申请1台磁带机的情况，这样就出现了死锁，若N4，死锁的可能性就更高了。第五章 习题答案5、答：（1）采用首次适应算法，在完成了题目所给的系列申请及释放内存操作后，空闲分区如下所示。分区大小起始地址030K150K120K280K2112K

15、400K （2）采用最佳适应算法，在完成了题目所给的系列申请及释放内存操作后，空闲分区如下所示。分区大小起始地址030K400K142K470K290K210K （3）采用最差适应算法，在完成了题目所给的系列申请及释放内存操作后，空闲分区如下所示。分区大小起始地址030K150K180K220K252K460K （4）如再申请100K，有上述结果可知，采用首次适应算法后剩下的空闲分区能满足这一申请要求，采用最佳适应算法和最差适应算法均不能满足申请要求。6、答：（1）程序空间的大小为32KB，因此逻辑地址的有效位数是15位。（2）内存储空间的大小是16KB，因此物理地址至少需要14位。（3）当页

16、面为1KB时，虚地址0A5C表示页号为00010，页内地址是1001011100。该页在内存的第4块，即块号为0100，因此0A5C的物理地址是01001001011100，即125CH。用同样的方法可以求得，053C的物理地址是293CH，103C的逻辑地位在第4页，产生越界异常。7、答：（1）1.5*2=3 微秒 （2）1.5*2*15%+1.5*85%=1.725 微秒第六章 习题答案4、答：0x2C27：0x7C270x1D71：缺页0x4000：越界5、答：m条指令实际花费时间应为执行m条指令花费的时间与操作系统处理一次页故障需要时间之和。一条指令执行平均需要k（ns），m条指令执行

17、需要m * k（ns），执行m条指令发生一次缺页中断，需要n（ns），也即m条指令实际花费时间为（m * k + n）（ns），则平均每条指令的执行时间为（m * k + n）/ m（ns）。答：（1）每执行一次Aij:=0就产生一次缺页中断，总共需要产生（128*128-1）次缺页中断。（2）产生（128-1）次中断。6、答：LRU方法：10次，FIFO方法：14次，Optimal方法：8次。10、答：（1）一个作业最多可以有28=256个段。（2）每段的最大长度为216=64KB=65 536字节。（3）逻辑地址0，430主存地址为：2100+430=2530； 逻辑地址1，50无法进行地

18、址变换，因为产生了越界中断； 逻辑地址2，30无法进行地址变换，因为产生了缺段中断； 逻辑地址3，70的主存地址为：4000+70=4070。12、答：（1）页面大小为4KB，故页内偏移为12位。系统采用48位虚拟地址，故虚页号为48-12=36位。采用多级页表时，最高级页表项不能超出一页大小，故应采用36/9=4级页表，最高级页表项正好占据一页空间。（2）系统进行页面访问操作时，首先读取页面对应的页表项，有98%的概率可以在TLB中直接取到，然后进行地址转换，如果TLB为命中，则要通过一次内存访问来读取页表项。页面的平均访问时间为：98%*（10+100）+（1-98%）*（10+100+1

19、00）=112ns（3）二级页表的平均访问时间计算同理：98%*（10+100）+（1-98%）*（10+100+100+100+100）=114ns（4）设快表命中率为P，则应满足：P*（10+100）+（1-P）*（10+100+100+100+100）=95%（5）系统采用48位虚地址，每段最大为4G，故段内地址为32位，段号：48-32=16位。每个用户最多可以有216个段，段内采用页式地址，与（1）中计算同理，（32-12）/9，取上整为3，故段内应采用3级页表。4、详解一个程序P的用户空间为16K，存储管理采用请求式分页系统，每个页面大小为2K，存在以下的页表：其中，有效位=1表示

20、页面在内存；0表示页面不在内存。请将虚地址0X060C，0X1502，0X1D71，0X2C27，0X4000转换为物理地址。 注：请求分页存储管理系统的地址变换与分页存储管理系统的地址变换类似，只是增加了缺页中断处理部分。当由逻辑地址计算出页号后，查找页表确定此页在不在内存，如果在内存就计算物理地址，如果不在内存中，就产生一个缺页中断将所缺的页按照一定的策略调入内存。程序P共有8页，页面大小为2K，即211，页号占剩余高位。答：逻辑地址0X060C的二进制表示如下: 0000 0 110 0000 1100 页号 页内地址其页号为0，从表中可知该页对应的物理块号为12，所以，将二进制表示中的页号换为块号，则物理地址用二进制表示为：0110 0