现代操作系统第四版第二章

1、现代操作系统第二章进度与线程习题图2-2中给出了三个进度状态，在理论上，三个状态能够有六种变换，每个状态两个。可是，图中只给出了四种变换。有没有可能发生其余两种变换中的一个或两个A:从堵塞到运转的变换是能够想象的。假定某个进度在I/O上堵塞，并且I/O结束，假如此时CPU安闲，该进度就能够从堵塞态直接转到运转态。而此外一种变换（从堵塞态到就绪态）是不行能的。一个就绪进度是不行能做任何会产生堵塞的I/O或许其余什么事情。只有运转的进度才能被堵塞。2.假定要设计一种先进的计算机系统构造，它使用硬件而不是中止来达成进度切换。CPU需要哪些信息请描绘用硬件达成进度切换的工作过程。A:应当有一个存放器包

2、含目行进度表项的指针。当I/O结束时，CPU将把目前的机器状态存入到目行进度表项中。而后，将转到中止设施的中止向量，读取另一个过程表项的指针（服务例程），而后，就能够启动这个进度了。3.今世计算机中，为何中止办理程序起码有一部分是用汇编语言编写的A：往常，高级语言不一样意接见CPU硬件，而这类接见是必需的。比如，中止办理程序可能需要禁用和启用某个特定设施的中止服务，或许办理进度货仓区的数据。此外，中止服务例程需要赶快地履行。（增补）主若是出于效率方面的考量。中止办理程序需要在尽量短的时间内达成所需的必需办理，尽量减少对线程/程序流造成的影响，所以大多半状况下用汇编直接编写，跳过了通用编译过程中

3、冗余的适配部分。4.中止或系统调用把控制转给操作系统时，为何往常会用到与被中止进度的栈分其余内核栈A：内核使用独自的货仓有若干的原由。此中两个原由以下：第一，不希望操作系统崩溃，因为某些用户程序不一样意足够的货仓空间。第二，假如内核将数据保存在用户空间，而后从系统调用返回，那么歹意的用户可能使用这些数据找出某些对于其余进度的信息。5.一个计算机系统的内存有足够的空间容纳5个程序。这些程序有一半的时间处于等候I/O的安闲状态。请问CPU时间浪费的比率是多少A：5=%6.一个计算机的RAM有4GB，此中操作系统占512MB。所有进度都占256MB（为了简化计算）并且特点相同。若是CPU利用率达到9

4、9%，最大I/O等候是多少A：内存中最多可放(4GB-512MB)/256MB=14个进度，设每个进度的I/O等候占总运转时间的比率为p，则CPU利用率=1-p1499%=p%7.多个作业能够并行运转，比它们次序履行达成的要快。假定有两个作业同时开始履行，每个需要20分钟的CPU时间。假如次序履行，那么最后一个作业需要多长时间能够达成假如并行履行又需要多长时间假定I/O等候占50%。每个进度的时间为40min。次序履行时，最后一个作业需要80min才能达成。并行履行时，cpu利用率为1-pn=75%,cpu计算时间为40min，故总时间t=40/75%=8.考虑一个I/O等候占6级多道程序系统

5、（内存中可同时容纳40%，那么CPU利用率是多少6个程序）。假定每个进度的A：利用率=1-pn=1-6=%9.假定要从互联网上下载一个2GB大小的文件，文件内容能够从一组镜像服务器获取，每个服务器能够传输文件的一部分。假定每个传输恳求给定开端字节和结束字节。如何用多线程优化下载时间A：客户端进度能够创立独自的线程;每个线程都能够从此中一个镜像服务器获取文件的不一样部分。这有助于减少停机时间。自然，所有线程都共享一个网络链接。这个链接能够成为一个瓶颈，因为线程的数目变得特别大。10.为何图2-11a的模式不适适用于在内存使用高速缓存的文件服务器每个进程能够有自己的高速缓存吗A：即便是有可能实现，

6、也是很难保持文件系统的一致性。假定某个客户进度给服务器进度1发送恳求要更新文件。该进度更新其内存的cache项。而后，另一个客户进度给服务器进度2发送恳求读取该文件。不幸的是，假如该文件还在cache中，服务器进度2对此绝不知情，将返回过时的数据。假如第一个进度在缓冲后将文件写到磁盘中，而服务器进度2每次读取时检查磁盘其缓存的备份是不是最新的，系统还能够工作，可是需要防止磁盘接见的所有缓存系统。(个人以为，高速缓存应当每个进度共享，因为不是每个进度都需要屡次读写数据，假如每个进度都分派cache会造成资源浪费。）11.当一个多线程进度创立子进度时，假如子进度复制父进度的所有线程，就会出现问题：

7、若是夫进度中有一个线程正在等候键盘输入，此刻就有两个线程在等候键盘输入，父进度和子进度各有一个。这类问题在单线程进度中也会发生吗A：不会。假如单线程进度在键盘上堵塞，就不可以创立子进度。（而多线程进度在一个线程堵塞时能够运转另一个线程，整个进度不会所以被堵塞。）12.在图2-8中，给出了一个多线程Web服务器。假如读取文件的唯一门路是正常的堵塞read系统调用，那么Web服务器应当使用用户级线程仍是内核级线程为何A：当工作者线程从磁盘读取Web页时，它就会被堵塞。假如使用用户级线程，该动作将堵塞整个进度，而损坏多线程的价值。这就是使用内核线程的原由：某些线程的堵塞不会影响到其余线程。13.在本

8、章中，我们介绍了多线程Web服务器，说明它比单线程服务器和有限状态机服务器更好的原由。存在单线程服务器更好一些的情况吗请举例。A：在多线程Web服务器中，由分派程序从网络中读入工作恳求，在检查恳求后，分派线程精选一个空转的（即被堵塞的）工作线程，提交该恳求。在工作线程被唤醒后，他检查相关的恳求能否在Web页面高速缓存中，这个高速缓存是所有线程否能够接见的。假如没有，该线程开始一个从磁盘调入页面的read操作，并且堵塞知道该磁盘操作达成。在上述线程被堵塞在磁盘操作上时，分派线程可能精选另一个线程运转，能够有效利用CPU资源。而在单线程服务器上，只好等第一个线程达成后，才能开始第二个线程。也存在单

9、线程服务器更好的情况。假如服务器是完整CPU绑定的，则不需要多线程。这只会增添不用要的复杂性。假定某个百万人口地区的电话查号系统(近似于114)，假如每个(姓名，电话号码)记录为64个字符，整个的数据库则为64MB，这就很简单所有读入服务器内存中以供给迅速的查问。14。既然计算机中只有一套存放器，为何在图2-12中的存放器会合是按每个线程中列出而不是按每个进度列出。A：当一个线程停止时，它在存放器中有值。它们一定被保存，就像进度停止时，一定保存存放器。多线程和多进度没有什么不一样，所以每个线程需要自己的寄存器保存区。15.在没有时钟中止的系统中，一个线程放弃CPU后可能不再会获取CPU资源，那

10、么为何线程还要经过调用thread_yield自发放弃CPUA：进度中的线程合作。它们相互不敌对。假如应用程序需要堵塞以运转得更好，那么一个线程能够调用thread_yield自发放弃CPU。毕竟，同一个进度中的线程的所有代码往常是一个程序员写的。16.线程能够被时钟中止抢占吗假如能够，在什么情况下能够假如不可以够，为什么不可以够A：用户级线程不可以被时钟剥夺，除非整个进度的时间片用完。内核级线程能够独自地被剥夺。在后一种状况下，假如线程运转过久，时钟将中止应目行进度，因此目前线程也被中止。内核能够自由地从同一个进度中选用其余线程运转。17.请对使用单线程文件服务器和多线程文件服务器读取文件进

11、行比较。假定所需要的数据都在块高速缓存中，获取工作恳求，分派工作，并办理其余必需工作需要花销12ms。假如在时间过去1/3时，需要一个磁盘操作，额外花销75ms，此时该线程进入眠眠。单线程服务器每秒钟能够办理多少个恳求多线程服务器呢A：在单线程状况下，cache命中需要12ms，cache未命中需要87ms，其加权均匀为2/312+1/387=37ms，一秒钟能够达成1s/37ms=27个.在多线程状况下，所有磁盘等候都是重叠的，所以每个恳求耗时12ms，一秒钟能够达成1s/12ms=个（个人以为这样算不太正确，因为最后的几个线程假如cache未命中的话，就需要87ms，可能是完不行的，可是这

12、个题意翻译的不是很清楚，什么叫做“时间过去1/3时”，预计原意应当是”有1/3的时间需要额外的磁盘操作“。这样均匀算下来也能够忽视cache未命中发生的散布状况。）18.在用户态实现线程的最大的长处是什么最大的弊端是什么A：最大的优势就是效率。不需要堕入内核来切换线程。最大的弊端是，假如一个线程堵塞，整个进度都会堵塞。19.在图2-15中创立线程和线程打印信息是随机交叉在一同的。有没有方法能够严格依照以下序次运转：创立线程1，线程1打印信息，线程1结束，创立线程2，线程2打印信息，线程2结束，以此类推；假如有，是什么方法，假如没有请解说原由。A：是的，这是能够做到的。每次履行pthread-c

13、reate后，主程序能够调用pthread_join等候刚才创立的线程退出后再创立下一个线程。20.在议论线程中的全局变量时，曾使用过程create_global将储存分派给指向变量的指针，而不是变量自己。这是必需的吗仍是直接使用变量自己也可行A：将储存分派给指针是的确必需的，因为全局变量的大小是未知的。它可能是从字符到浮点数数组的任何种类。假如保存其值，就不得不把其大小传达给create_global，这都没有问题，可是一定将其种类作为set_global的第二个参数，那么read_global返回值的种类是不确立的。21.考虑一个线程所有在用户态实现的系统，该运转时系统每秒钟获取一个时钟中

14、止。当某个线程正在运转时系统中履行时发生一个时钟中止，此时会出现什么问题你有什么解决该问题的建议吗A：runtime系统能够正幸亏这一时刻堵塞或许排除堵塞某个线程，并且忙于办理调动行列。此时其实不合适于时钟中止办理程序开始检查该行列能否应当进行线程切换，因为它们可能处于不一致的状态。解决方法能够是：当进入runtime系统后，设置一个标记。时钟办理程序将看到该标记，并且设置其自己的标记，而后返回。当runtime系统达成时，它将检测时钟标记，看能否有时钟中止发生，并且此刻运转时钟办理程序。22.假定一个操作系统中不存在近似于select的系统调用来提早认识在从文件、管道或设施中读取时能否安全，

15、可是该操作系统的确同意设置报警时钟，以便中止堵塞的系统调用。在上述条件下，能否有可能在用户态中实现一个线程包请议论。A：这是可能的，可是效率很低。线程想要做一个系统调用，第一设定警报准时器，而后才履行调用。假如线程堵塞，准时器将控制送还给线程包。自然，大多半调用是不堵塞的，而准时器一定被消除。每个可能被堵塞的系统调用都一定作为3个系统调用来履行。假如准时器过早无效，各样问题都可能发生。用这类方法成立线程包其实不好。23.两个进度在一个共享内存的多办理器（两个CPU）上运转，当他们要共享一块内存时，图2-23中使用turn变量的忙等候解决方案还有效吗A：仍旧有效，但也依旧是忙等候。24.在抢占式

16、进度调动的条件下，图2-24中互斥问题的Peterson解法可行吗假如是非抢占式调动呢A：对抢占式调动可行。事实上，这类解法就是为它设计的。而对于非抢占式调度，可能会失败。考虑这类状况：turn被初始化为0，但进度1先开始运转了，它就会向来循环，但不开释CPU，拥有忙等候的弊端。节中所议论的优先级反转问题在用户级线程中能否可能发生为何A：当低优先级进度位于其临界区，而高优先级进度就绪并且被调动时，将发生优先级倒置问题。假如使用忙等候，高优先级进度将向来运转。对于用户级线程，不行能发生低优先级线程忽然被剥夺而同意高优先级线程运转，因为是不行剥夺的。而内核级线程，就会出现这个问题。节中描绘了一种有

17、高优先级进度H和低优先级进度L的状况，致使了H堕入死循环。若采纳轮转调动算法而不是优先级调动算法，还会发生这样问题吗请讨论。A：不会发生这样的问题。在轮转调动算法下。L早晚会运转，最后它将会走开临界区。重点是，在优先级调动算法下，L永久不会运转；在轮转循环下，它按期获取一个正常的时间片，所以有时机走开其临界区。27.在使用线程的系统中，若使用用户级线程，是每个线程一个栈仍是每个进度一个栈假如使用内核级线程呢请解说。A：每个线程都是自己调用例程，所以它一定有其自己的货仓以保存局部变量、返回地点等等。这一点用户级线程和内核级线程是相同的。28.在开发计算机时，往常第一用一个程序模拟履行，一次运转一

18、条指令，多办理器也严格按此模拟。在这类没有同时势件发生的情况下，会出现竞争条件吗A：（竞争条件指多个线程或许进度在读写一个共享数据时结果依靠于它们履行的相对时间的情况。竞争条件发生在当多个进度或许线程在读写数据时，其最后的的结果依靠于多个进度的指令履行次序。）是的。模拟计算机也能够是多道程序设计的。比如，在进度A运转时，它读取一些共享变量。而后发生了一个模拟时钟周期和进度B运转。它也读取相同的变量，而后对变量进行了加1操作。当进度A运转时，假如它也对变量进行了加1操作，就发生了竞争条件。将生产者-花费者问题扩展成一个多生产者-多花费者的问题，生产（花费）者都写（读）一个共享的缓冲区，每个生产者

19、和花费者都在自己的线程中履行。图2-28中使用信号量的解法在这个系统中还可行吗A：可行。在给定的某个时刻，只有一个生产者（花费者）能够向（从）缓冲区增添（拿出）项目。30.考虑对于两个进度P0和P1的互斥问题的解决方案。假定变量初始值为0。P0的代码以下：p1的代码是将上述代码中的0替代为1。该方法能否能办理互斥问题中所有可能的情况A：该解决方案知足互斥，因为两个流程不行能同时处于CriticalSection。也就是说，当turn为0时，P0能够履行其临界区，但P1不可以履行。当turn为1也有相像的状况。可是，这假定P0一定先运转。假如P1产生某些东西并将其放入缓冲区，那么当P0能够进入其

20、临界区时，它会发现缓冲区为空并堵塞。并且，该解决方案需要严格交替两个过程，这是不希望发生的。31.一个能够障蔽中止的操作系统如何实现信号量A：履行信号量操作，操作系统第一要禁用中止。而后，它读守信号量的值。假如履行down操作，而信号量等于0，就将调用进度放入与信号量相关的堵塞进度列表中。假如履行up操作，一定检测看能否有任何进度在信号量上被堵塞。假如有一个或多个进度被堵塞，从堵塞进度的列表中移出一个，使之就绪。当所有这些操作都达成后，就能够开启中止了。书中的原话是：操作系统只需在履行以下操作时临时障蔽所有中止：测试信号量、更新信号量以及在需要时是某个进度睡眠。:32.请说明如何仅经过二元信号

21、量和一般机器指令实现计数信号量（即能够保持一个随意值的信号量）。:A：用两个二值信号量和一个计数器counter实现一个计数信号量：M用于互斥，B用于堵塞，counter用于记录up减去down的次数，再用一个链表来记录堵塞在这个计数信号量上的进度。down的实现：进度先对M进行down来获取counter、链表的独占接见权，并把counter减1。假如counter大于等于0，直接对M进行up即可；不然，记录在链表再up，而后对B进行down进而阻塞这个进度。up的实现：进度相同先对M进行down，counter加1，若其大于0，直接对M进行up即可；不然counter小于等于0，把链表中一

22、个进度移出，而后对B、M挨次up。33.假如一个系统只有两个进度，能够使用一个屏障来同步这两个进度吗为何A:假如程序操作按阶段履行，直到两个进度都达成目前阶段才能进入下一阶段，这时就应当使用屏障。(这个答案也有点奇异，我以为只需这两个进度不是生产者-花费者模式就能够使用屏障。）34.假如线程在内核态实现，能够使用内核信号量对同一个进度中的两个线程进行同步吗假如线程在用户态实现呢假定在其余进度中没有线程一定接见该信号量。请解说你的答案。A：对于内核线程，线程能够在信号量上堵塞，而内核能够运转该进度中的其余线程。因此，使用信号量没有问题。而对于用户级线程，当某个线程在信号量上堵塞时，内核将以为整个

23、进度都被堵塞，并且不再履行它。所以，在用户态线程的同步失败。35.管程内的同步体制使用条件变量和两个特别操作wait和signal。一种更通用的同步形式是只用一条原语waituntil，它以随意的布尔谓词作为参数。比如waituntilx0ory+zTSQ0;44.有5个待运转作业，预计它们的运转时N分别是9,6,3,5和X。采纳哪一种次序运转这些作业将获取最短的均匀响应时间（答案将依靠于X）A:最短作业优先能够使得均匀响应时间最短。0X3:X,3,5,6,9.3X5:3,X,5,6,9.5X6:3,5,X,6,9.69:3,5,6,9,X.45.有5个批办理作业A到E，它们几乎同时抵达一个计

24、算中心。预计它们的运行时间分别为10，6，2，4和8分钟。其优先级（由外面设定）分别为3，5，2，1和4，此中5为最高优先级。对于以下每种调动算法，计算其均匀进度周转时间，可忽视进度切换的开支。轮转法。优先级调动。先来先服务（依照10，6，2，4，8序次运转)。最短作业优先。对(a)，假定系统拥有多道程序办理能力，每个作业均公正共享CPU时间;对(b)到(d)，假定任一时刻只有一个作业运转，直到结束。所有的作业都完整部是CPU密集型作业。A:对于时间片轮转，在头10分钟里，每个作业获取1/5的CPU时间。在第10分钟时，C结束。在接下来的8分钟里，每个作业获取1/4的CPU时间，而后D达成，而后，在接下来的6分钟内，余下的3个作业各获取1/3的CPU时间，直到B结束，以此类推。所以，5个作业的达成时间分别为是10,18,24,28和30,均匀为22分钟。对于优先级调动，5最初运转，6分钟达成。其余作业分别在第14,24,26和30分钟达成，均匀为分钟。假如作业按A-E的序次履行，则分别在第10,16,18,22和30分钟达成，所以，均匀为分钟。最后，最短作业优先调动的达成时间分别为第2,6,12,20和30分钟，均匀为14分钟。46.运转在CTSS上的一个进度需要30个时间片达成。该进度一定被调入多少次，包含第一次(在该进度运转以前）A:CTSS(兼容分时系统）建立优先级类：