操作系统课后习题总结

1、PB();PC();Co endPB()iwhile 1(巩 fulll);从綴冲池1中収出一件产品;V(ecjpLyl):P epty2:將-件广品放入缓冲施2；V(full2):PC()(while!) P(full2；从缓冲池2中取出一件产晶;V(?mpty2);习题二参考答案4、答：在生产者一消费者问题中，Producer进程中P ( empty )和P(mutex)互换先后次序。先 执行P(mutex)，假设成功，生产者进程获得对缓冲区的访问权，但如果此时缓冲池已满，没 有空缓冲区可供其使用，后续的P( empty )原语没有通过，Producer阻塞在信- 号量 empty上,而此

2、时mutex已被改为0，没有恢复成初值1。切换到消费者进程后，Consumer进程执行P(full)成功，但其执行 P( mutex)时由于Producer正在访问缓冲区，所以不成功，阻塞 在信号量mutex上。生产者进程和消费者进程两者均无法继续执行，相互等待对方释放资 源，会产生死锁。在生产者和消费者进程中，V操作的次序无关紧要，不会出现死锁现象。5、答：罠 吟缓冲迪缓冲池2 nm艇荐：设遇四f i号呈甘mpdl*甘叩 fulllfllfU112f北風丛关系描述如下土 int Hiptvl=n；严&屮缓冲池1屮的空缓冲int enjty2=in; /*表示缓冲池2中的宇覆冲 耳数* -in

3、t/*农示缓冲池IPic满卢品旷卿沖麻护札Ini rullO：片衷不缰冲池2中装禍广品 的缓沖区救*/nmin( ) PA() cobegin paM *hile(l) 生产F产Hh?(empty 1); 树一件严骷故入缪冲池1;V(fulll);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)

4、prepare an orange;p(sp);put an orange on the plate;v(sg1);son()while(1)p(sg1);take an orange 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 的整 型变量 writecou

5、nt ，用来对写者进行计数；初值为 1 的互斥信号量 wmutex ，用来实现多个 写者对 writecount 的互斥访问。reader() while ( 1 )P(s)；P( rmutex )；if (readcount= =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);

6、 P(mutex); 写文件； V( mutex )； P( wmutex )； writecount- - ；If ( writecount= =0 ) V(S); V (wmutex);9、答：Barber:beginrepeatP(full) 剪发 ; V(empty); until false end信号量sofa:表示等候椅数，初值为 n 信号量 empty ：表示理发椅空，初值为 1 信号量 full :表示理发椅上有顾客，初值为 0 count :记录等候椅上的人数，初值为 0 信号量 mutux :用来实现对变量 count 的互斥访问 Var mutex,sofa,empty

7、,full: semaphore=1,n,1,0; count: integer: =0;Guest:beginrepeatP(mutex);if (count=n) thenbeginV(mutex);离开;endelsebegincount:=count+1;if (count1) then / 多个顾客时，坐等候椅上V(mutex);P(sofa); 坐沙发等 ;P(empty); 坐椅子上 ; V(sofa);V(full);else / 只有一个顾客时，坐到理发椅上 beginV(mutex);P(empty); 坐椅子上 ; V(full); end剪发离开；P(mutex); c

8、ount:=count-1;V(mutex);end until falseend11、答：本题中中共有三类进程，相当于机房管理员进程guard，学生进程student和教师进程teacher。相应的信号量和各个进程描述如下：semaphore computer=2m;/* 对应于计算机的资源信号量 */semaphore student=0;/* 对应于欲进入机房的学生 */semaphore enter=0;/* 用来控制学生是否可进入机房 */semaphore finish=test=0; /* 用来同步学生和教师教师须检查实习完毕的学生 */stude nt_i()/*i=1,2,

9、*/V(student);/* 激活管理员，有学生到达，要进入机房实验 */P(enter);/* 等待管理员激活进入机房 */进入机房上机实习；V(finish) ；/* 激活教师已经做完实验 */P(test);/* 等待教师检查作业 */离开机房；V(computer) ；/* 所占用的计算机变为空闲 */guard()int i;for(i=0;i+;in)P(computer); /* 等待有两个空闲计算机 */P(computer);P(student); /* 等待有两个学生达到 */P(student);V(enter); /* 激活两个等待进入机房的学生 */V(enter)

10、;teacher()int i;for(i=0;i+;in)P(finish); /* 等待两个学生完成实验 */P(finishi);检查两个学生的实习结果；V(test)； /*检查完后，激活两个学生检查完毕，可以离开机房 */ V(test);附加 1：图书馆阅览室问题问题描述：假定阅览室最多可同时容纳100 个人阅读，读者进入时，必须在阅览室门口的一个登记表上登记，内容包括姓名、座号等，离开时要撤掉登记内容。用P、V操作描述读者进程的同步算法。mutex,emptyseat semaphore;阅读;mutex=1,Emptyseat=100;Cobegin Reader(i)P(mu

11、tex); 查登记表，置空； V(mutex);P(Emptyseat);P(mutex);查登记表，登记姓名，座位号等；V(mutex);附加 2：哲学家就餐问题离开；V(Emptyseat); Coend给所有哲学家编号，奇数号的哲学家必须先拿左边的筷子， 偶数号的哲学家必须先拿右边的 筷子。这样，任何一个哲学家拿到一支筷子后， 就已经阻止了他邻座的一个哲学家吃饭的企 图，除非某个哲学家一直吃下去，否则不会有人会饿死。Repeatbeginif (i mod 2)！=0 thenbeginP(chopsticki);P(chopstick(i+1) mod 5); eat;V(chopst

12、icki); V(chopstick(i+1) mod 5); think; elsebeginP(chopstick(i+1) mod 5);P(chopsticki);eat;V(chopstick (i+1) mod 5);V(chopsticki); think; endendenduntil false;第三章习题答案6、答：(1)采用先来先服务调度算法，则其调度顺序是1、2、3、4。作业号提交时间运行时间开始时间完成时间周转时间带权周转时间1234平均周转时间：T=+/4=平均带权周转时间： T=+11)/4=(2)采用短作业优先调度算法，则其调度顺序是1、4、3、2。作业号提交时

13、间运行时间开始时间完成时间周转时间带权周转时间1234平均周转时间：T=+4=平均带权周转时间：T=+4=7、答：各个作业执行的时间如下图所示:8:008:108:208:308:408:509:009:109:209:302345注：深黑色表示作业独占CPU时间，浅黑色表示作业平分CPU时间，白色表示 CPU空闲时间。(1) 作业调度顺序是：1，3，4，2，5。(2) 最大作业周转时间为55分钟。(3 )全部作业运行结束的时刻为：9: 30&答：& 00时，作业1运行；9： 10时，作业1运行完毕，其他3个作业均已到达，它们的响应比分别为：R2=1+(9:10-8:40)/30=2; R3=

14、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=R4=1+(9:20-9:10)/5=3作业4先运行，5分钟后，作业4运行完毕，最后作业 2运行。 作业的执行顺序为：1、3、4、2。第四章习题答案2、答:00000750(1)Need=10020642Work值的变化情况如下：POP2pitpi(1,52)竺(1,532)二(2禺,&6)竺(2,8,9,10) (3t,9,10) 因为存在一个安全序列 ,所以系统处于安全状态

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

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

17、5CH。用同样的方法可以求得，053C的物理地址是293CH, 103C的逻辑地位在第 4页，产生越界异常。7、答：(1)*2=3 微秒 (2)*2*15%+*85%= 微秒第六章 习题答案4、答： 0x2C27：0x7C270x1D71 ：缺页0x4000 :越界5、 答：m条指令实际花费时间应为执行m条指令花费的时间与操作系统处理一次页故障需要时间之和。一条指令执行平均需要 k(ns), m条指令执行需要 m * k (ns),执行m条指 令发生一次缺页中断，需要 n (ns)，也即m条指令实际花费时间为(m * k + n ) (ns)，则 平均每条指令的执行时间为( m * k + n

18、) / 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无法进行地址变换,因为产生了越界中断；逻辑地址 2, 30无法进行地址变换,因为产生了缺段中断； 逻辑地址 3, 70的主存地址为： 4000+

19、70=4070。12 、答：(1) 页面大小为4KB，故页内偏移为12位。系统采用48位虚拟地址，故虚页号为48-12=36 位。采用多级页表时,最高级页表项不能超出一页大小,故应采用36/9=4 级页表,最高级 页表项正好占据一页空间。(2) 系统进行页面访问操作时，首先读取页面对应的页表项，有98%的概率可以在 TLB中直接取到，然后进行地址转换，如果TLB为命中，则要通过一次内存访问来读取页表项。页面的平均访问时间为： 98%*(10+100) +(1-98%) *(10+100+100) =112ns(3) 二级页表的平均访问时间计算同理：98%*(10+100) +( 1-98%)

20、*(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 表示页面在内存； 0表示页面不在内存。请将虚地址 0X0

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