操作系统精髓与设计原理第五版中文答案全

2.1情况（a）和情况（b）具有相同的答案。•假设处理器的操作不能重叠，但I/O操作可以。•1job：时间周期=NT•处理器利用率=50%；*2jobs：时间周期=NT•处理器利用率=100%；*4jobs：时间周期=（2N-1）NT•处理器利用率=100%•2.2I/O限制程序只用相对较少的处理时间，因此，受到短期调度算法的偏爱。然而，如果一个处理器限制程序在一段很长的时间内被处理器时间拒绝，那同样的这个短期调度算法则会允许处理机去处理过去一段时间一直没有使用处理机的程序，所以，并不是永远不受理处理器限制程序所需的处理器时间。•2.3关于分时系统，我们所关注的是周转时间。•首选的是时间片，因为它在一个很短的时间给•所有的程序一个访问权限去使用处理器。在批•处理系统，我们所关注的是吞吐量和更少量的上•下文转换，对于进程来说获得了更多的处理时•间。因此，最小化上下文转换的处理是有优势•的。2.4应用程序运用系统调用去调用操作系统所提供的功能。关键的是，系统调用导致转换到进入内核模式的系统程序。操作系统第三章习题解答*3.1系统和用户进程的创建和删除：在系统中进程对于信息共享，加速计算，模块性和便利性都能并发执行。并发的执行需要进程的创建和删除机制。进程所需要的资源在进程被创建时获得或者在其运行的时候分配。当进程结束时，操作系统需要收回任何可重用资源。•进程的挂起和恢复：在进程调度中，当进程在等待某些资源时，操作系统需要把进程状态改变成等待或者就绪状态。当进程所要求的资源可用时，操作系统需要把它的状态变为运行状态恢复它的执行。•进程同步机制：协调进程分享数据。并发访问使用共享数据可能导致数据不一致性，操作系统不得不为其提供一种进程同步机制用来确保协作进程有序的实行，从而保证数据的一致性。•进程通信机制：在操作系统下执行的进程要么是独立的进程要么是协作的进程。协作进程必须使用某些方法来实现进程间的通信。•死锁处理机制：在一个多道程序设计环境里，一些进程可能因为有限数量的资源而产生竞争。如果一个死锁发生，全部等待的进程都不会从等待状态改变成运行状态，那么资源被浪费，工作不会被完成。*3.4对处于就绪/挂起状态的所有进程通过一•个固定的优先级层次来划分，如分成一到两•个优先级，只有当就绪/挂起状态的进程优先•级高于所有就绪状态进程的优先级时，才把处理机分配给它。3.6a）采用4种模式的优点在于：系统能够提高对存储器的访问使用的灵活性，同时对内存储器的运行起到很好的保护作用。缺点：复杂度和处理开销。例如，处理器运行在不同的访问模式需要分离可访问的堆栈。b）原则上，模式越多，灵活性适应性越大，但系统越复杂，举出一种有4种以上模式的情况较难。3.7a）当j<i时，一个在Di中运行的进程被阻止访问Dj中的对象。因此，如果Dj中包含的信息比Di优先权更高或者比Di更安全，这个限制是适当的。然而，这个安全政策可以用下面的方法更简单的获得。一个在Dj中运行的进程可以从Dj中读取数据，并且可以把数据复制到Di中，随后，在Di中运行的进程便可读取这些信息。•b）一个近似的解决这个问题的方法就是大家都知道的可信系统。在以后的章节会详细解释。*3.8a）一个应用程序可能正处理从另一个进程收到的数据并且把结果储存在磁盘上。如果有等待取自其它进程的数据，应用程序可能进入下一个进程取出数据并且处理它。如果一个先前的磁盘写操作已经完成并且有处理的数据写出，应用程序会将其写入下一个磁盘。需要考虑的一点就是，进程等待输入进程的额外数据和磁盘的可用性。*b）有几种处理的方式。或者一种特定类型的队列来处理，或者进程可能被放进两个单独的队列。无论哪种情况，操作系统必须处理细节，提醒进程注意双方事件一个接一个的发生。3.9这技术基于一个假设一一中断进程A响应中断后将会继续进行。•但是，通常，一个中断将引起基本监督程序抢占进程A有利于另一个进程B。有必要在描叙进程A相关进程中断的位置复制进程A的执行状态，机器最好第一时间把它们储存在那里，以方便后续操作的进行。*3.10因为存在进程不能被抢占的情况（例如正在内核模式里执行的进程），因此操作系统不能快速回复实时需求。操作系统第四章习题解答4.1是的。因为更多的状态信息必须保留下来用于一个程序到另一个程序的转换。•4.2因为，关于用户级线程，一个进程的线程结构对于操作系统来讲是不可视的，它仅仅是基于进程调度的一个基本单位。•进程和线程的区别在于：•简而言之，一个程序至少有一个进程，一个进程至少有一个线程.线程的划分尺度小于进程，使得多线程程序的并发性高。另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。线程在执行过程中与进程还是有区别的。•每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。•（续）•进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源分配和调度的一个独立单位.线程是进程的一个实体，是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器,一组寄存器和栈）,但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源.一个线程可以创建和撤销另一个线程;同一个进程中的多个线程之间可以并发执行.4.4这里的这个问题是机器花费了它工作中大量时间去等待I/O的完成。在一个多线程程序中，一个内核级线程使系统调用阻塞，而其它内核级线程可以继续运行，而对于一个单独的处理器，一个进程只有使所有调用阻塞，才能使其它线程继续。4.5不会。当一个进程退出，它将带走关于它I的所有东西，内核级线程、进程结构、存储空I间，也包括线程。4.6尽可能多的关于地址空间的信息能够和其它地址空间进行交换，从而保存到主存储器中。*4.7a)如果采取保守策略，那么最多有20/4=5个作业同时执行。因为分配给各自进程的设备中有一个设备在大多数时间里都是空闲的，在同一时间，最多有5个设备空闲，最好的情况，没有设备空闲，全部都在工作状态。*b)为了提高设备的利用率，最初每个作业分配3个磁带设备，第4个则要按需求分配。根据这个策略，至多有[20/3]=6个作业能被同时激活，最小空闲设备数是0，最大空闲设备数是2。*4.8每一个调用都可能改变一个线程的优先级或者一个可运行的、具有更高优先级的线程也可以调用调度程序，而且它依次抢占低优先级的活跃线程。因此，可运行的、高优先级线程不具备题目所述。*5.25.3a..上限是100。因为最多只有100次加1操作。这种情况发生在两个进程顺序执行时。.下限是2,发生的情形可以描述如下：说明：tally++实际上分三步执行，先执行AJally，再执行INCA，最后执行tally。A。此处A为寄存器，其值将在进程切换时保护起来。5.6*a.用文字描述这个算法：•分步：•对于第i个进程：为了得到服务首先要取得顺序号：即对number[i]进行写操作，此时应屏蔽所有其它进程对number数组的读操作。当对number[i]的写操作完成时才允许其它进程对其的读操作。•查看是否有其他进程正在操作，若有则做空操作；与其它进程的顺序号比较，若小于则可得到服务，否则等待。•进入临界区•服务完毕将number[i]置0。总述：•当一个进程希望进入其临界区，它将得到一张票，票的号码将是所有等待进入临界区或已在临界区的进程所得到票的号码中最大者加1。拥有最小票号的进程将率先进入临界区。如果有多个进程得到的票具有相同的号码，则进程号更小的进程将更占优势。当一个进程离开其临界区，它将重置其中票号为0。•b.解释此算法如何避免死锁•死锁时的情形：每个人都拿到了顺序号，但都拿不到面包。•在本算法中即使顺序号相同，但数组下标是不同的。所以进程总可推进不会发生死锁。•c.解释此算法如何加强互斥；•(1)对临界资源面包是按照顺序号互斥的使用•(2)对number数组的操作通过写操作前置true保证其它进程此时不能对其读，从而保证读写互斥。5.9•错误情形:假设有2个进程都调用Wait且s的初值为0。在第一个进程执行完SignalB(mutex)且尚未执行WaitB(delay)时，第二个进程开始调用Wait，也停在同一点(即SignalB(mutex)和WaitB(delay)之间)。这时，s的值为-2，而mutex是打开的。假如有另外2个进程在这时相继调用了Signal,那么他们每个都会做SignalB(delay)操作，但程序中后一个SignalB将没有意义。•解决：•voidWait(semaphores){WaitB(mutex);s--;if(s<0){SignalB(mutex);WaitB(delay);}SignalB(mutex);}voidSignal(semaphores){WaitB(mutex);s++;if(s<=0)SignalB(delay);elseSignalB(mutex);}5.11改正后的程序：varcar_available:semaphore(:=n)passenger_wait:semaphore(:=0)passengeri:wanderingforarandomtime;signal(passenger_wait);wait(car_available);carj:wait(passenger_wait);takepassengerwanderingsignal(car_available)parbeginpassenger1passenger2...passengermcar1car2...carnparend5.14•考虑图5.17。如果按照以下的顺序改变程序中的相应处程序的意思会改变吗?..■，、.一、wait(e);wait(s)signal(s);signal(n)wait(n);wait(s)•,•戏、.，/、signal(s);signal(e)a.互换wait(e)和wait(s):•结果：对于生产者进程来说，若wait(s)成功，则说明可以使用缓冲池。若wait(e)不成功说明没有空缓冲区可用，此时生产者进程等待。•对于消费者进程来说，若wait(n)成功，则说明缓冲池不空。若wait(s)成功说明可以使用缓冲池，但此时由于生产者进程已将缓冲池占有，此时消费者进程等待。结果发生死锁。•一〜E十工意思不变•—同a意思不变5.16•这一问题给出了相应三种进程的信号量的使用。圣诞老人(SantaClaus)在北极他的店里睡觉仅能被(1)、(2)唤醒。•(1)所有九个驯鹿都结束它们的假期从南太平洋回来•(2)仅当制造玩具的小孩子有困难时将其喊醒为了让圣诞老人多睡会儿觉，仅当三个小孩子有问题时将其唤醒。当三个小孩子有问题在解决时，其他小孩子想访问圣诞老人时必须等其他人回来。如果圣诞老人醒来发现有三个小孩子在他的店门外等候，同时最后一条驯鹿已经从热带回来，圣诞老人已经决定让这些小精灵等到圣诞节之后，因为他的雪橇已经准备好了，这一点比较重要(假定驯鹿不想离开热带，因此他们会停留到最后一刻)。最后一只驯鹿到达时圣诞老人必须出发，以前到达的驯鹿在拉雪橇前在一个温暖的小屋里等待。使用信号量解决这一问题。分析：三类进程：SantaClaus,reindeer,kidsSantaClaus:sleepinNorthPolewakenbyreindeer（9头）Kids（3个）Reindeer:VacationintropicsReturnNorthPoleChristmasactivityKids:MakingtoysIhavingdifficulties,needhelpSemaphore:wakesanta=0;唤醒圣诞老人的信号量returnreindeer=1;返回的驯鹿的计数器互斥信号量needhelp=1;需要帮助的Elves的计数器互斥信号量int:reindeercount=0,Kidscount=0;SantaClaus:(while(true)(wait(wakesanta);//等待被唤醒if(reindeercount==9)(christmasactivity;send_reindeer();wait(returnreindeer);//获得寻路返〃回互斥信号量reindeercount=0;signal(returnreindeer);//释放驯鹿〃返回互斥信号量｝if(elvescount>=3)(help_Kids();wait(needhelp);//等待需要帮助信号量Kidscount=0;signal(needhelp);//释放需要帮助信号〃量｝｝Reindeeri(whiletrue(vacationontropics;returntoNorthPole;wait(returnreindeer);//获得驯鹿返回互斥信号量reindeercount++;if(reindeercount==9)signal(wakesanta)//释放唤醒圣诞老人信号量else{wait_in_hut();signal(returnreindeer放驯鹿返回互斥信号量}}Kidsi:{makingtoys;wait(needhelp)获获得需要帮助信号量Kidscount++;ifelvescount==3signal(wakesanta释/放唤醒圣诞/老人信号量elsesignal(needhelp释放需要帮助互/斥信号量}6.1互斥：在每一时刻，只能有一辆车占用十字路口的一个象限；占有且等待：没有车倒退；每辆车一直在等待，直到它前面的十字路口的象限可以使用；非抢占：没有车辆能够强迫另一辆车给自己让路；循环等待：每辆车一直等待另外的车辆占用的十字路口的象限。6.2Q获得B，然后获得A，然后释放B和入；当P恢复执行的时候，它可以获得全部资源。Q获得B，然后获得A；P执行并阻塞在对A的请求上；Q释放B和入，当P恢复执行时，它可以获得全部资源。Q获得B，P获得并释放A，然后Q获得A并释放B和A，当P恢复执行时，它可以获得BoP获得A，Q获得B，P释放A，Q获得A并释放B，P获得B并且释放B。P获得并释放A，P获得B；Q执行并阻塞在对B的请求上；P释放B，当Q恢复执行时，它可以获得全部资源。P获得A并且释放A，P获得B并且释放B，当Q恢复执行时，他可以获得全部资源。6.3如果Q在P请求A之前获得B和入，那么Q能够使用并稍后释放这两个资源，允许P继续执行。如果？在Q请求A之前获得A，那么Q至多执行到请求A之前，然后被阻塞。尽管这样，一NP释放A，Q就能够继续执行。一旦。释放B，P也能继续执行。6.5w=2100进程P3的请求等于W，标记P3，W=210书012=02220(3)进程P2的请求小于W,标记P2,W=2220+2001=4221•(4)进程P1的请求小于W,标记P1,W=4221+0010=4231•(5)所有的进程都标记了，所以系统不存在死锁6.10a.第四个进程到达，最大需求是60,初始要求是25第四个进程到达，最大需求是60,初始需求是356.13三个进程共享四个资源单元最坏情况是，3个进程各只得到1个资源单元。这时系统尚存有1个资源单元，因而将不会死锁。b.定义：claim[i]=进程i总共需要的资源数目；allocation[i]=M程i已经分配的资源数目；deficit[i]=®程i仍然需要的资源数目。根据题意，我们有下式成立：在一个死锁的情况下，所有的资源都是被占有的，所以有下式成立：并且，此时，每个进程都在等待资源。从以上两个式子我们可以得出：也就是说至少有一个进程j，它已经获得了所有所需要的资源(deficit[j]=0)，将完成其工作并释放所有的资源，剩下的进程将依次完成工作，因此死锁不会发生。6.14安全状态，需要的最小资源数目是3。依次用P1-P4来表示四个进程。从矩阵可以看出，四个进程还需要的资源数目为（2，1，6,5），当有一个可用资源时，？2可以执行完成，并释放占用资源，可用资源数目为2，允许P1执行完成，可用资源数目为3，此时，P3需要6个资源，P4需要5个资源，既最小情况还需要2个额外资源，P4执行完成，释放资源后，P3再执行完成。6.17如果至少有一个左撇子或右撇子，则当所有哲学家都准备拿起第一根筷子时，必定会有两个哲学家竞争一根筷子而其中一个得不到处于等待，这样必定有一个哲学家可以获得两根筷子，而不至于发生死锁。同样也不会发生饥饿7.1重定位支持模块化程序设计保护进程隔离；保护和访问控制共享保护和访问控制逻辑组织支持模块化程序设计物理组织长期存储；自动分配和管理7.2分区数目等于主存的字节数除以每个分区的字节数：每8位二进制数表示个分区中的一个分区。7.3定义，和h分别为内存中段的数量和空洞的数量。假定在动态分区的内存中，存储段的创建和释放以相同的概率发生，那么对于任一分区，它后面紧挨着的那个部分是一个分区或者是一个空洞的概率各为0.5所以，对于有s个段的内存中，空洞的平均数量为s/2既空洞的数量是段数量的一半。7.5最佳适配算法在每次分割之后切割下来的剩余部分总是最小的，这样会在存储器中留下很多难以利用的小空闲区。最坏适配算法当有进程调入的时候每次都分配最大的空闲存储块，这样块中剩余的空闲空间就足够大从而可以满足另外的请求。缺点是第一次分配的时候就把最大的空闲区分配了，当有大的空间分配请求时极易分配失败。7.6第一个块分配到第二个空闲块，起始地址为80M，第二个块分配到第一个空闲块，起始地址为20M，第三个块分配到第二个空闲块起始地址为120M。第一个块分配到第四个空闲块，起始地址为230M，第二个块分配到第一个空闲块，起始地址为20M，第三个块分配到第三个空闲块，起始地址为160M。从上一次放置的位置开始扫描(注意只往后看)，所以三个块的起始地址分别为80M，120M和160M。每次都找最大的空闲块。三个块的起始地址为80M，230M和360M。7.7a.b.7.80110111101000110111000007.9其中，mod表示求余运算。7.10我们完全可以采用斐波那契(Fibonacci)数列作为块的划分准则，从而建立起与普遍采用的对分伙伴系统(binarybuddysystem)不同的伙伴系统。与对分伙伴系统相比，按照斐波那契数列建立起来的伙伴系统能够提供更多不同的块容量；也就是说，整个内存空间划分得更细致了，块的容量更具有多样性。因此，在为进程分配存储空间时，可以找到最佳适配的存储块，因而可以使内部碎片的尺寸得以减小，这是这种伙伴系统具有的显著优点。7.12逻辑地址空间为：逻辑地址空间包含的位数为26位。一个帧的大小和页的大小相同都是。存储器地址空间/帧大小=，所以指定帧需要22位。逻辑地址空间有个页，所以含有个页表项。加上一个有效/无效位，制定一个帧的位数为22,所以总共为23位。7.14从段表可以看出，段表中的四个字段依次为段0,1，2,3。物理地址=660+198=858物理地址=222+156=378由于段内偏移（530）＞段的长度（442），所以发生段错误。物理地址=996+444=1440物理地址=660+222=8828.1•a•步骤：•从虚地址求取页号和页内偏移（利用公式：虚地址=页号*页长+页内偏移）•利用页表由页号求取对应的块号•求物理地址（利用公式：物理地址=块号*块长+块内偏移，注意到块长=页长，块内偏移=页内偏移）b.I（i）1052=1024+28虚拟页号为1，得到帧号为7。物理地址=7*1024+28=7196（ii）2221=2*1024+173虚拟页号为2,页错误。（iii）5499=5*1024+379虚拟页号为5，得到帧号为0。物理地址=0*1024+379=379

8.4•a.b.•c.d.8.6•a.b.8.2，所以在虚拟存储器中指定页需要22存储器地址空间/页大小=位。，所以在虚拟存储器中指定页需要22个页表项。每个每一页包含页表占据了8位，因此22位需要用到三级页表。个页表项。每个两级的页表包含个页表项，一级页表包含个页表项(8+8+6=22)。我们这里有三级，三级所占位数为6,8,8,则页的个数为：右三级所占位数为：8，6，8，则页的个数为：若三级所占位数为：8，8，6，则页的个数为：3号页帧的内容将被置换，因为它最早被加载。1号页帧的内容将被置换，因为它的上次访问时间离当前最久。0号页帧的内容将被置换，因为其中R位和M位的值为(0,1)。3号页帧的内容将被置换，因为由将来的访问序列可知，页面3的访问顺序最靠后。命中率=16/33命中率=16/33采用上述两种替换策略得到的命中率相等。一般来说，采用c.对于这个特定的访问序列，生的时刻与LRU的情况相当接近，LRU替换策略的命中率会高于采用FIFO替换策略的情况，而对于这个特定的访问序列来说，一个页面被载入之后，很少发生在接下来的5次连续访问中再次被访问的情形，因此缺页发从而使得对应的命中率接近于采用上述两种替换策略得到的命中率相等。一般来说，采用生的时刻与LRU的情况相当接近，8.8存储器地址从4000开始：(R1)(R1)4000400140024003ONEcompareR1,R2branchgreater4009EstablishindexregisterforiEstablishninR2Testi>n

(R3)B(R1)AccessB[i]usingindexregisterR1(R3)(R3)+C(R1)AddC[i]usingindexregisterR1A(R1)(R3)StoresuminA[i]usingindexregisterR1(R1)(R1)+ONEIncrementibranch40026000-6999storageforA7000-7999storageforB8000-8999storageforCstorageforONEstorageforn8.10•假设需要i级，则可以表示的地址空间大小••要求表示64位地址空间，则要求10i+12>=64，所以i至少取6•一8.8存储器地址从4000开始：(R1)(R1)4000400140024003ONEcompareR1,R2branchgreater4009EstablishindexregisterforiEstablishninR2Testi>n8.11•.一一400ns•__15%*420+85%*220=2508.12\.缺页下限小•b.缺页上限=?•8.17•a.每段的最大尺寸=8*2K=16K•b.该任务的逻辑地址空间最大=4*16K=64K•c.逻辑地址格式是：2位表示段号，3位表示页号，其他11位表示页内偏移。最后的11位转换为十六进制为2BC•8.18

•a.逻辑地址格式是：前5位表示页号，后11位表示页内偏移。•b.页表长度：25=32个条目；页表宽度：20-11=9位。•c.页表宽度由9位变为8位。9.1每个方块表示一个执行单元，方块中的数字表示当前执行的进程。FCFSAAABBBBBCCDDDDDEEEEERR,q=1ABABCABCBDBDEDEDEDEERR,q=4AAABBBBCCBDDDDEEEEDESPNAAACCBBBBBDDDDDEEEEESRTAAACCBBBBBDDDDDEEEEEHRRNAAABBBBBCCDDDDDEEEEEFeedback,q=1ABACBCABBDBDEDEDEDEEFeedback,q=2iABAACBBCBBDDEDDEEDEEFCFSAAABBBBBCCDDDDDEEEEERR,q=1ABABCABCBDBDEDEDEDEERR,q=4AAABBBBCCBDDDDEEEEDESPNAAACCBBBBBDDDDDEEEEESRTAAACCBBBBBDDDDDEEEEEHRRNAAABBBBBCCDDDDDEEEEEFeedback,q=1ABACBCABBDBDEDEDEDEEFeedback,q=2iABAACBBCBBDDEDDEEDEE9.7首先，调度器计算在时间t+r1+r2+r3时刻的响应比，此时，三个作业都已经完成。这个时候第三个作业具有最小的响应比（图中可以看出），所以，调度器决定最后执行第三个作业；继续查看在时间t+r1+r2时，第一和第二个作业都已完成，此时，第一个任务的响应比要小些，所以，在时间t的时候第二个作业被选择执行,既执行顺序为r2,r1,r3。这个算法在每完成一个作业之后重新查看作业的响应比，跟高响应比优先算法是有区别的，如果是后者那么在时间t的时候就会选择第一个作业。9.14在多级反馈队列调度器的调度下，I/O-bound的进程比CPU-bound的进程更有利，也就是说，调度器更倾向于选择I/O-bound的进程进行分派。原因在于I/O-bound的进程会比较长时间地阻塞；在阻塞过程中，CPU-bound的进程得到多次分派执行，因而会很快进入低