操作系统——精髓与设计原理(第五章答案).ppt

1、操作系统第五章习题解答,5.2,A,B,D,C,D,D,C,E,E,E,C,B,E,C,E,E,C,C,B,D,A,E,B,E,C,E,E,C,B,C,A,C,B,5.3 a. (1).上限是100。因为最多只有100次加1操 作。这种情况发生在两个进程顺序执行时。 (2).下限是2，发生的情形可以描述如下： 说明：tally+实际上分三步执行，先执行Atally，再执行INC A，最后执行tallyA。此处A为寄存器，其值将在进程切换时保护起来。,b. 上限是50*N，下限是2。,5.6 a.用文字描述这个算法： 分步： 对于第i个进程： 为了得到服务首先要取得顺序号：即对numberi进行

2、写操作，此时应屏蔽所有其它进程对number数组的读操作。当对numberi的写操作完成时才允许其它进程对其的读操作。 查看是否有其他进程正在操作，若有则做空操作；与其它进程的顺序号比较，若小于则可得到服务，否则等待。 进入临界区 服务完毕将numberi置0。,总述： 当一个进程希望进入其临界区，它将得到一张票，票的号码将是所有等待进入临界区或已在临界区的进程所得到票的号码中最大者加1。拥有最小票号的进程将率先进入临界区。如果有多个进程得到的票具有相同的号码，则进程号更小的进程将更占优势。当一个进程离开其临界区，它将重置其中票号为0。,b.解释此算法如何避免死锁 死锁时的情形：每个人都拿到了

3、顺序号，但都拿不到面包。 在本算法中即使顺序号相同，但数组下标是不同的。所以进程总可推进不会发生死锁。 c.解释此算法如何加强互斥； (1)对临界资源面包是按照顺序号互斥的使用 (2)对number数组的操作通过写操作前置true保证其它进程此时不能对其读，从而保证读写互斥。,5.9 错误情形：假设有2个进程都调用Wait且s的初值为0。在第一个进程执行完SignalB(mutex)且尚未执行WaitB(delay)时，第二个进程开始调用Wait，也停在同一点（即SignalB(mutex)和WaitB(delay)之间）。这时，s的值为-2，而mutex是打开的。假如有另外2个进程在这时相继

4、调用了Signal，那么他们每个都会做SignalB(delay)操作，但程序中后一个SignalB将没有意义。,解决： void Wait(semaphore s) WaitB(mutex); s-; if(s0) SignalB(mutex); WaitB(delay); SignalB(mutex);void Signal(semaphore s) WaitB(mutex); s+; if(s=0) SignalB(delay); else SignalB(mutex);,5.11 改正后的程序： var car_available:semaphore(:=n) passenger_wa

5、it:semaphore(:=0) passenger i: wandering for a random time; signal(passenger_wait); wait(car_available); car j: wait(passenger_wait); take passenger wandering signal(car_available) parbegin passenger1;passenger2;passengerm; car1;car2;carn; parend,5.14,考虑图5.17。如果按照以下的顺序改变程序中的相应处程序的意思会改变吗? a. wait(e);

6、 wait(s) b. signal(s);signal(n) c. wait(n);wait(s) d. signal(s);signal(e),a.互换wait(e)和wait(s): 结果： 对于生产者进程来说，若wait(s)成功，则说明可以使用缓冲池。若wait(e)不成功说明没有空缓冲区可用，此时生产者进程等待。 对于消费者进程来说，若wait(n)成功，则说明缓冲池不空。若wait(s) 成功说明可以使用缓冲池，但此时由于生产者进程已将缓冲池占有，此时消费者进程等待。结果发生死锁。 b.意思不变 c.同a d.意思不变,5.16,这一问题给出了相应三种进程的信号量的使用。圣诞老人

7、（Santa Claus）在北极他的店里睡觉仅能被(1)、(2)唤醒。 (1)所有九个驯鹿都结束它们的假期从南太平洋回来 (2)仅当制造玩具的小孩子有困难时将其喊醒为了让圣诞老人多睡会儿觉，仅当三个小孩子有问题时将其唤醒。当三个小孩子有问题在解决时，其他小孩子想访问圣诞老人时必须等其他人回来。,如果圣诞老人醒来发现有三个小孩子在他的店门外等候，同时最后一条驯鹿已经从热带回来，圣诞老人已经决定让这些小精灵等到圣诞节之后，因为他的雪橇已经准备好了，这一点比较重要(假定驯鹿不想离开热带，因此他们会停留到最后一刻)。最后一只驯鹿到达时圣诞老人必须出发，以前到达的驯鹿在拉雪橇前在一个温暖的小屋里等待。使

8、用信号量解决这一问题。,分析： 三类进程：Santa Claus, reindeer, kids Santa Claus: sleep in North Pole waken by reindeer(9头) Kids(3个) Reindeer:Vacation in tropics Return North Pole Christmas activity Kids: Making toys having difficulties ,need help,Semaphore:wakesanta=0;唤醒圣诞老人的信号量 returnreindeer=1; 返回的驯鹿的计数器互斥信号量 needhe

9、lp=1;需要帮助的Elves的计数器互斥信号量 int :reindeercount=0, Kidscount=0; Santa Claus: while (true) wait(wakesanta);/等待被唤醒 if(reindeercount=9) christmas activity; send_reindeer(); wait(returnreindeer);/获得寻路返/回互斥信号量 reindeercount=0; signal(returnreindeer);/释放驯鹿/返回互斥信号量,if(elvescount=3) help_Kids(); wait(needhelp);/等待需要帮助信号量 Kidscount=0; signal(needhelp);/释放需要帮助信号/量 Reindeer i while truevacation on tropics; return to North Pole; wait(returnreindeer);/获得驯鹿返回互斥信号量 reindeercount+; if(reindeercount=9) signal(wakesanta)/释放唤醒圣诞老人信号量,else wait_in_hut(); signal(returnreindeer)/