第3章死锁习题及答案

第三章 死锁习题一、填空题 1进程的“同步”和“互斥”反映了进程间 和 的关系。 【答案】直接制约、间接制约 【解析】进程的同步是指在异步环境下的并发进程因直接制约而互相发送消息，进行相互合作、相互等待，使得各进程按一定的速度执行的过程；而进程的互斥是由并发进程同时共享公有资源而造成的对并发进程执行速度的间接制约。 2死锁产生的原因是 和 。 【答案】系统资源不足、进程推进路径非法 【解析】死锁产生的根本原因是系统的资源不足而引发了并发进程之间的资源竞争。由于资源总是有限的，我们不可能为所有要求资源的进程无限地提供资源。而另一个原因是操作系统应用的动态分配系统各种资源的策略不当，造成并发进程联合推进的路径进入进程相互封锁的危险区。所以，采用适当的资源分配算法，来达到消除死锁的目的是操作系统主要研究的课题之一。 3产生死锁的四个必要条件是 、 、 、 。 【答案】互斥条件、非抢占条件、占有且等待资源条件、循环等待条件【解析】 互斥条件：进程对它所需的资源进行排它性控制，即在一段时间内，某资源为一进程所独占。 非抢占条件：进程所获得的资源在未使用完毕之前，不能被其它进程强行夺走，即只能由获得资源的进程自己释放。 占有且等待资源条件：进程每次申请它所需的一部分资源，在等待新资源的同时，继续占有已分配到的资源，循环等待条件：存在一进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。 4在操作系统中，信号量是表示 的物理实体，它是一个与 有关的整型变量，其值仅能由 原语来改变。 【答案】资源，队列，P-V 【解析】信号量的概念和 P-V原语是荷兰科学家 EWDijkstra提出来的。信号量是一个特殊的整型量，它与一个初始状态为空的队列相联系。信号量代表了资源的实体，操作系统利用它的状态对并发进程共享资源进行管理。信号量的值只能由P-V原语来改变。 5每执行一次P原语，信号量的数值S减1。如果S=0，该进程 ；若S0，则 该进程，并把它插入该 对应的 队列中。 【答案】继续执行，阻塞（等待），信号量，阻塞（等待） 【解析】从物理概念上讲，S0时的数值表示某类资源可用的数量。执行一次P原语，意味着请求分配一个单位的资源，因此描述为S=S1。当S0时，表示已无资源，这时请求资源的进程将被阻塞，把它排在信号量S的等待队列中。此时，S的绝对值等于信号量队列上的阻塞的进程数目。 6每执行一次V原语，信号量的数值S加1。如果 ，Q进程继续执行；如果S=0，则从对应的 队列中移出一个进程R，该进程状态变为 。 【答案】S0，等待，就绪 【解析】执行一次V原语，意味着释放一个单位的资源。因此，描述为S=S1。当S0时，表示信号量请求队列中仍然有因请求该资源而被阻塞的进程。因此，应将信号量对应的阻塞队列中的第一个进程唤醒，使之转至就绪队列。 7利用信号量实现进程的 ，应为临界区设置一个信号量 mutex。其初值为 ，表示该资源尚未使用，临界区应置于 和 原语之间。 【答案】互斥，1，P（mutex），V（mutex） 【解析】一次仅允许一个进程使用的资源称为临界资源，对临界资源实施操作的那段程序称为临界区。对于具有临界区问题的并发进程，它们之间必须互斥，以保证不同时进入临界区。利用信号量和P-V原语能方便地解决临界区问题。mutex为互斥公用信号量，初值为1，临界区的代码被置于P（mutex）、V（mutex）原语之间时，任何欲进入临界区的进程，必须在公用信号量mutex上执行P原语，在完成对临界资源的访问后再执行V原语。由于mutex初值为1，当第一个进程执行P原语后减为0，表示临界资源空闲，可分配给该进程使之进入临界区，在第一个进程没有退出临界区之前，若此时第二个进程想进入临界区，也应先执行P原语。而结果是mutex变为负值，就意味着临界资源已被占用，因此，第二个进程被阻塞。直到第一个进程执行V原语，释放该临界资源mutex到0后，方可唤醒第二个进程，使之进入临界区，待它完成对临界资源的访问后，又执行V原语，使mutex恢复到初始值。 8在多道环境下，由于进程的并发执行，一段程序为多个进程 时，要求在执行的过程中，该段程序的指令和数据不能被 ，这样的程序段称为 。 【答案】共享，修改，纯过程（或共享程序段） 【解析】在多道环境下，常常有许多于程序和应用程序是被多个用户所共用的，为了充分提高内存的利用率，把这些共享的程序和数据在内存只保留一个副本，这就要求这些程序和数据不能被修改。二、单项选择题 1在非剥夺调度方式下，运行进程执行V原语之后，其状态 。 （A）不变 （B）要变 （C）可能要变 （D）可能不变 【答案】（A） 【解析】进程的调度方式有两种；剥夺和非剥夺方式。在剥夺方式下，一旦有优先级高于当前执行进程优先级的进程存在时，便立即发生进程调度，转让处理机。而非剥夺方式是即使在就绪队列中有优先级高于当前执行进程的进程存在，当前进程仍将继续占有处理机，直到由于该进程自己的原因而让出处理机。 2两个进程争夺同一个资源 。 （A）一定死锁 （B）不一定死锁 （C）不死锁 （D）以上说法都不对 【答案】（B） 【解析】这和它们申请资源的顺序有关。 3 是一种只能由P操作和V操作进行访问的特殊变量，可以用来实现异步并行进程间的 以排它地访问共享数据，还可以用来实现 ，实现进程间在逻辑上的相互制约关系。 （A）调度 （B）类程 （C）进程 （D）互斥 （E）信号量 （F）控制变量 （G）同步 （H）共享变量 （I）规程 （J）分配 【答案】（E） （D） （G） 4可以被多个进程在任一时刻共享的代码必须是 。 （A）不能自身修改的纯码 （B）顺序代码 （C）无转移指令的代码 （D）汇编语言编制的代码 【答案】（A）【解析】规定共享代码必须是不自身修改的纯码，主要是为了保证程序执行的正确性。 5当对信号量进行V原操作之后， 。 （A）当S0，要唤醒一个就绪进程 （C）当S=0，要唤醒一个等待进程 （D）当S=0，要唤醒一个就绪进程 【答案】（C） 【解析】V操作的物理含义是回收释放的一个资源，即信号量的值加1。在这个过程中，如果信号量的值大于0，表明系统没有其他进程正在等待使用该资源，该进程继续执行或转进程调度，这取决于进程调度采用的方式。如果信号量的值小于或等于0，说明有进程曾经因申请该资源且为得到满足而处于该资源对应的等待队列中，现在释放一个资源就应从该资源的等待队列中唤醒一个进程,使之变为就绪状态。 6在下列叙述中，错误的一条是 。 （A）进程被撤消时，只需释放该进程的PCB就可以了，因为PCB是进程存在的唯一标志 （B）进程的互斥和同步都能用P/V原语实现 （C）用户程序中执行系统调用命令时，处理机的状态字将发生改变 （D）设备独立性是指用户在编程时，所使用的设备与实际设备无关 【答案】（A） 【解析】进程不仅要释放PCB结构，也要释放它所占有的所有资源；而且，当一个祖先进程撤消某个子进程时，还需要审查该子进程是否还有自己的子孙进程，若有的话，还需撤消某个子进程的PCB结构和释放它们所占有的资源。因此，叙述（A）是错误的。 把并发进程的同步和互斥问题一般化，可以得到一个抽象的一般模型，即生产者/消费者问题。叙述（B）正确。 处理机的状态将从目态转换到管态。叙述（C）正确。 用户编程所使用的设备称为逻辑设备，而逻辑设备与物理设备的对应由操作系统的设备管理程序完成。叙述（D）正确。 7正在运行的进程在信号量S上作P操作之后，当S0，进程将进入信号量的 。 （A）等待队列 （B）提交队列 （C）后备队列 （D）就绪队列 【答案】（A） 【解析】执行一次P操作意味着申请一个资源，即信号量S1。如果S）个进程，则系统中最不可能的是有 个进程处于死锁状态。 (A) (B) (C) (D)（0，消费者调用P（full）后总可去取物品。每取走一件物品后，由于调用V（empty），便增加了一个可用来存放物品的位置。用指针k和t分别指示生产者往缓冲器存物品和消费者从缓冲器中取物品的相对位置，它们的初值为0，那么，一个生产者和一个消费者共用容量为n的缓冲器时，可如下进行同步工作： 设信号量empty,full,初值为empty=n,full=0；整型变量k,t,初值k=t=0。 生产者进程： begin L1：produce a product; P（empty）； Bk:=product; k：=（k十1）mod n; V（full）; go to L1 end; 消费者进程： begin L2：P（full）； take a product from Bt； t：（t1）mod n； V（empty）； consume； go to L2 end 2死锁发生的必要条件有哪些？ 【解析】 发生死锁的必要条件有四点：互斥条件、不可抢占条件、部分分配条件和循环等待条件。 （1）互斥条件：系统中存在一个资源一次只能被一个进程所使用； （2）非抢占条件：系统中存在一个资源仅能被占有它的进程所释放，而不能被别的进程强行抢占； （3）占有且等待条件：系统中存在一个进程已占有了分给它的资源，但仍然等待其它资源； （4）循环等待条件：在系统中存在一个由若干进程形成的环形请求链，其中的每一个进程均占有若干种资源中的某一种，同时每一个进程还要求（链上）下一个进程所占有的资源。 3现有四个进程：R1，R2，W1和W2，它们共享可以存放一个数的缓冲区B。进程R1每次把从键盘上读入的一个数存到缓冲区B中，供进程W1打印输出；进程R2每次把从磁盘上读一个数存放到缓冲区B中，供进程W2打印输出。怎样用P、V操作协调四个并发进程的工作。【解析】设信号量e,f1,f2;其初值分别为 e=1,f1=0,f2=0R1： R2：L: P(e) 从键盘上读入 的一个数存到缓冲区B中 V(f1)Goto LL: P(e) 从键盘上读入的一个数存到缓冲区B中 V(f2)Goto LW1： W2：L: P(f1)将缓冲区B中的数据打印输出 V(e)Goto LL: P(f2)将缓冲区B中的数据打印输出 V(e)goto L六、综合应用题1设有3个并发执行的进程：输入进程Pi、计算进程Pc和输出进程Po。其中进程Pi不断地从键盘读入整数，放入缓冲区Buf1，Pc按输入顺序从Buf1中取数据，每次取出2个整数，计算其和，将结果放入缓冲区Buf2。Po负责将Buf2中的数据按顺序输出。设缓冲区Buf1、Buf2可存放的整数个数分别为m、n（m、n0）。要求利用信号量的P、V操作写出进程Pi、Pc、Po的算法。【参考答案】设信号量e1,f1,e2,f2，其初值分别为：e1=m,f1=0,e2=n,f2=0 3个并发进程分别为：Cobegin Pi: beginL1: P(e1); 向Buf1中输入1个数; V(f1); Goto L1;endPc:beginL2:P(f1);x=从Buf1中读1个数;V(e1);P(f1);y=从Buf1中读1个数;V(e1);z=x+y;P(e2);将z送入Buf2中;V(f2);Goto L2;endPo: beginL3:P(f2); W=从Buf2中读1个数; 打印W； V(e2); Goto L3;EndCoend2今有3个并发进程R、M、P，它们共享一个缓冲器B。进程R负责向B中输入数据；进程R每输入一数据，进程M对其进行加工；进程M加工完成后，进程P负责打印输出。缓冲器B中每次只能存放一个数据，数据一旦被打印，进程R又可存放下一个数据，。它们之间的关系