操作系统典型题讲解（五）

进程基本概念中的典型问题分析某系统的进程状态转换图如下图所示：（1）说明引起各种状态转换的典型事件。（2）分析下述状态转换是否可立即引起其它的状态转换：1，2，3，4。进程状态转换图解答：（1）引起各种状态转换的典型事件如下表所示。（2）状态转换1不会立即引起其它状态转换。

状态转换2必然立即引发状态转换1：状态转换2发生后，进程调度程序必然要选出一个新的就绪进程投入运行，该新进程可能是其他进程，也可能是刚从执行状态转换成就绪状态的那个进程。

状态转换3可能立即引发状态转换l：状态转换3发生后，若就绪队列非空，则进程调度程序将选出一个就绪进程投入执行。

状态转换4可能引发状态转换1：状态转换4发生后，若CPU空闲，并且没有其它进程竞争CPU，则该进程将被立即调度。

另外，状态转换4还可能同时引发状态转换1和2：若系统采用抢占调度方式，而新就绪的进程具备抢占CPU的条件(如其优先权很高)，则它可立即得到CPU转换成执行状态，而原来正在执行的进程则转换成就绪状态。进程同步基本概念中的典型问题分析进程之间存在哪几种制约关系？各是什么原因引起的？下面活动分别属于哪种制约关系（1）若干个同学去图书馆借书。（2）两队举行篮球赛。（3）流水线生产的各道工序。（4）商品生产和社会消费。解答：

进程之间存在直接制约关系(即同步问题)和间接制约关系(即互斥问题)；同步问题是存在逻辑关系的进程之间相互等待所产生的制约关系，互斥问题是相互逻辑关系的进程竞争使用资源（临界资源）所发生的制约关系。（1）属于互斥关系，因为书的个数是有限的，一本书只能借给一个同学，其中书是临界资源。（2）属于互斥关系，篮球只有一个，两队都要竞争，其中篮球是临界资源。（3）属于同步关系，各道工序的开始都依赖前道工序的完成。（4）属于同步关系，商品没生产出来，消费无法进行，商品未消费完，生产也无须进行。为某临界区设置一把锁W，当W=1时，表示关锁；w=0时，表示锁已打开。试写出开锁原语和关锁原语，并利用它们去实现互斥。分析：在用锁来实现互斥时，必须为每个临界资源设置一把锁W。值得注意的是，锁W只能有开或关两种状态，相应地W只能取0或1两个值。进行关锁操作时，若W处于开的状态，则表示相应的临界资源空闲，进程只需将锁的状态置为关，便可直接进入临界区；否则，若W已处于关状态，则表示其他进程正在使用临界资源，故执行关锁操作的进程必须等待。进行开锁操作时，则必须将锁的状态置为开状态，以允许其他进程使用临界资源。相应的关锁原语lock(W)和开锁原语unlock(W)可描述如下：

lock(W)：whileW=1dono-op；

W：=l；

unlock(W)：W：=0在利用关锁原语和开锁原语实现进程互斥时可将临界区CS放在其间即

lock(W)；CS；unlock(W)；空指令，当W==1时什么都不做，即忙等！信号量机制及应用中的典型问题分析如下图所示，有一计算进程和打印进程，它们共享一个单缓冲区，计算进程不断地计算出结果并将它放入单缓冲区中，打印进程则负责从单缓冲区中取出每一个。结果进行打印。请用信号量来实现它们的同步关系。分析：可从临界资源的角度来思考，先找临界资源，并为每种临界资源设置信号量，在访问临界资源之前加wait操作来申请资源，访问完临界资源后加signal操作以释放临界资源。本题中有两类临界资源：第一类是计算进程争用的空闲缓冲区，初始状态下有一个空闲缓冲可供使用，故可为它设置初值为l的信号量empty；第二类是打印进程争用的已放入缓冲中的打印结果，初始状态下缓冲中无结果可供打印，故可为它设置初值为0的信号量full。//并行开始，parallel并行的//并行结束，parallel并行的//Semaphore是计数信号量，在类PASCAL语言中是赋初值//repeat重复，循环结构//Wait（s）就是s减1，若等于0则继续等待，等到大于0，继续执行//signal（s）就是s加1//buffer缓冲区C语言版：semaphorefull=0;semaphoreempty=1;do{

计算下一个数据；wait(empty);

将数据添加到缓冲区；signal(full);}whileTRUE试写出相应的程序来描述如下图所示的前趋关系。Vara,b,c,d,e,f,g,h;semaphore:=0,0,0,0,0,0,0,0;BeginParbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S3;signal(e);end;beginwait(c);S4;signal(f);end;beginwait(d);S5;signal(g);end;beginwait(e);S6;signal(h);end;beginwait(f);wait(g);wait(h);S7;end;Parendend解题方法：（1）首先找出所有的直接前趋关系；（2）然后对每一种直接前趋关系，如Si→Sj，专门设置一初值为0的信号量；abcdefgh（3）在Si结束之后执行对该信号量的signal操作，在Sj开始之前执行对该信号量的wait操作，即可保证程序段Si执行完后才执行程序段Sj。设有8个程序段p1，p2，…,p8，它们在并发执行时有如下图所示的制约关系，试用信号量实现这些程序段之间的同步。经典进程同步问题中的典型问题分析有三个进程PA、PB和PC协作解决文件打印问题：PA将文件记录从磁盘读入内存的缓冲区l中，每执行一次读一个记录：PB将缓冲区1中的内容复制到缓冲区2中，每执行一次复制一个记录；PC将缓冲区2中的内容打印出来，每执行一次打印一个记录。缓冲区的大小与记录大小一样。请用信号量来保证文件的正确打印。本题其实就是一个生产者一消费者问题。

对缓冲区1来说，PA是生产者，PB是消费者；

对缓冲区2来说，PB是生产者，PC是消费者。

需要说明的有两点：

①缓冲区1和缓冲区2都只能存放一个记录，故无需设置in、out指针，原来生产者一消费者问题中的mutex信号量也因此可以省去；

②PB进程既是消费者，又是生产者。单生产者和单消费者有两个进程：一组生产者进程和一组消费者进程共享一个初始为空、固定大小为n的缓存（缓冲区）。生产者的工作是制造一段数据，只有缓冲区没满时，生产者才能把消息放入到缓冲区，否则必须等待，如此反复;同时，只有缓冲区不空时，消费者才能从中取出消息，一次消费一段数据（即将其从缓存中移出），否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或者一个消费者从中取出消息。问题的核心是：1.要保证不让生产者在缓存还是满的时候仍然要向内写数据;2.不让消费者试图从空的缓存中取出数据。生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，他们也是同步关系。解决思路：对于生产者，如果缓存是满的就去睡觉。消费者从缓存中取走数据后就叫醒生产者，让它再次将缓存填满。若消费者发现缓存是空的，就去睡觉了。下一轮中生产者将数据写入后就叫醒消费者。不完善的解决方案会造成“死锁”，即两个进程都在“睡觉”等着对方来“唤醒”。只有生产者和消费者两个进程，正好是这两个进程存在着互斥关系和同步关系。那么需要解决的是互斥和同步PV操作的位置。使用“进程间通信”，“信号标”semaphore就可以解决唤醒的问题：我们使用了两个信号标：full和empty。

信号量mutex作为互斥信号量，它用于控制互斥访问缓冲池，互斥信号量初值为1；

信号量full用于记录当前缓冲池中“满”缓冲区数，初值为0。

信号量empty用于记录当前缓冲池中“空”缓冲区数，初值为n。新的数据添加到缓存中后，full在增加，而empty则减少。如果生产者试图在empty为0时减少其值，生产者就会被“催眠”。下一轮中有数据被消费掉时，empty就会增加，生产者就会被“唤醒”。该类问题要注意对缓冲区大小为n的处理，当缓冲区中有空时便可对empty变量执行P操作，一旦取走一个产品便要执行V操作以释放空闲区。对empty和full变量的P操作必须放在对mutex的P操作之前。1、若生产者进程已经将缓冲区放满，消费者进程并没有取产品，即empty=0，当下次仍然是生产者进程运行时，它先执行P(mutex)封锁信号量，再执行P(empty)时将被阻塞，希望消费者取出产品后将其唤醒。轮到消费者进程运行时，它先执行P(mutex)，然而由于生产者进程已经封锁mutex信号量，消费者进程也会被阻塞，这样一来生产者进程与消费者进程都将阻塞，都指望对方唤醒自己，陷入了无休止的等待。2、若消费者进程已经将缓冲区取空，即full=0,下次如果还是消费者先运行，也会出现类似的死锁。不过生产者释放信号量时，mutex、full先释放哪一个无所谓，消费者先释放mutex还是empty都可以。多生产者和多消费者在多个制造商和多个消费者出现的情况下就会造成拥护不堪的情况，会导致两个或多个进程同时向一个磁道写入或读出数据。要理解这种情况是如何出现的，我们可以借助于putItemIntoBuffer()函数。它包含两个动作：一个来判断是否有可用磁道，另一个则用来向其写入数据。如果进程可以由多个制造商并发执行，下面的情况则会出现：1、两个制造商为emptyCount减值；2、一个制造商判断缓存中有可用磁道；3、第二个制造商与第一个制造商一样判断缓存中有可用磁道；4、两个制造商同时向同一个磁道写入数据。多个生产者向一个缓冲区中存入数据，多个生产者从缓冲区中取数据。这是有界缓冲区问题，队列改写，生产者们之间、消费者们之间、生产者消费者之间互相互斥。

共享缓冲区作为一个环绕缓冲区，存数据到尾时再从头开始。我们使用一个互斥量保护生产者向缓冲区中存入数据。由于有多个生产者，因此需要记住现在向缓冲区中存入的位置。使用一个互斥量保护缓冲区中消息的数目，这个生产的数据数目作为生产者和消费者沟通的桥梁。使用一个条件变量用于唤醒消费者。由于有多个消费者，同样消费者也需要记住每次取的位置。在选项中选择生产条目的数目，生产者的线程数目，消费者的线程数目。生产者将条目数目循环放入缓冲区中，消费者从缓冲区中循环取出并在屏幕上打印出来。为了克服这个问题，我们需要一个方法，以确保一次只有一个制造商在执行调用函数。换个说法来讲，我们需要一个有“互斥信号标”（mutalexclusion）的“关键扇区”（criticalsection）。为了实现这一点，我们使用一个叫mutex二位信号标。因为一个二位信号标的值只能是1或0，只有一个进程能执行down(mutex)或up(mutex)。有三个进程PA、PB和PC协作解决文件打印问题：PA将文件记录从磁盘读入内存的缓冲区l中，每执行一次读一个记录：PB将缓冲区1中的内容复制到缓冲区2中，每执行一次复制一个记录；PC将缓冲区2中的内容打印出来，每执行一次打印一个记录。缓冲区的大小与记录大小一样。请用信号量来保证文件的正确打印。本题其实就是一个生产者一消费者问题。

对缓冲区1来说，PA是生产者，PB是消费者；

对缓冲区2来说，PB是生产者，PC是消费者。

需要说明的有两点：

①缓冲区1和缓冲区2都只能存放一个记录，故无需设置in、out指针，原来生产者一消费者问题中的mutex信号量也因此可以省去；

②PB进程既是消费者，又是生产者。死锁中的典型问题分析死锁概念：

多道程序环境下，多个进程可能竞争一定数量的资源。进程所申请的资源被其他等待进程占有，该进程可能无法改变其状态，成为死锁。必要条件：资源互斥占有并等待非抢占循环等待死锁明确死锁产生的四个必要条件明确死锁的处理方法明确死锁预防的处理方法明确死锁避免的处理方法（包括安全状态、死锁状态关系等）产生死锁的必要条件有哪些？答：同时具备下列四个必要条件时，就会产生死锁1、互斥（Mutualexclusion

）条件：一个资源一次只能被一个进程所使用，即是排它性使用。2、不剥夺（Nopreemption）条件：进程已经获得的资源，在未使用完以前，不能被别的进程剥夺，只能在使用完以后，由自己释放。3、请求和保持（Hold-and-wait）条件：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的其它资源保持不放。4、环路等待（Circularwait）条件：存在一种进程资源的循环等待链，链中的每一个进程已经获得资源的同时被链中的下一个进程所请求。死锁处理方法死锁预防死锁避免死锁检测忽略互斥-通常无计可施占有并等待-静态分配非抢占-允许抢占循环等待-有序申请资源安全状态和安全队列资源分配图算法银行家算法死锁恢复终止进程资源抢占单实例–等待图多实例—类似银行家检测算法的应用问题某系统中有三个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是______A.9B.10C.11D.12答案：B最少要10个。由于各进程最大需求量之和要小于“进程数+资源数”3+x>12X>9所以最少要10个资源。【例】死锁产生的必要条件有4个，要预防死锁发生，必须破坏死锁的四个必要条件之一，但破坏（）条件是不太实际的。实现起来最简单的条件是（）A请求和保持B互斥C不剥夺D环路等待【解答】B。因为这是由设备的固有特性决定的A采用静态分配方法实现，在进程开始运行前，将它需要的全部资源分配给它。在运行过程中，不再请求。这是早期操作系统采用的方法，但资源的利用率不高。【例】通过撤消进程可进行死锁恢复，还可以采用（）方法解除死锁A阻塞进程B资源剥夺C提高进程优先级D降低进程优先级【解答】B采用资源剥夺法，将剥夺的资源分配给死锁进程，以解决死锁。

在一个实际的计算机系统中，资源可以更新和增减，进程可以创建和撤销。如果系统用banker算法处理死锁，那么，在什么情况下，下列改变可以安全地进行而不会引起死锁发生?

(1)增加Available(增添新资源)；

(2)减少Available(资源永久性地从系统中删除)：

(3)增大Max(对一进程而言，它可能希望更多的资源)；

(4)减少Max(一进程决定不需要那么多资源)；

(5)增加进程数；

(6)减少进程数。解(1)任何时候都不会引起死锁发生：(2)仅当每一进程的Max请求数不超过可用资源的总数时，系统才保持在安全态：(3)仅当每一进程的Max请求数不超过可用资源的总数时，系统才保持在安全态；(4)任何时候都不会引起死锁发生；(5)任何时候都不会引起死锁发生：(6)任何时候都不会引起死锁发生。

考虑下图所示的交通死锁情况。（1）说明图中导致死锁的四个必要条件成立。（2）提出一个避免死锁的规则。交通死锁图解(1)此例中导致死锁的四个条件成立：①互斥。每条道路只能被一辆车占用。②占用并等待．每辆车都占用了一段道路，并等待其前方的道路被释放。③非抢占。资源不可抢占。单行线，汽车不能抢路超车。④循环等待。每辆车都等待着前方的汽车把路让出来，且形成了一个环路。(2)在每个十字路口设置红绿灯，当南北方向的路通车时，东西方向的路上汽车等待．反之亦然。【例】一台计算机有6台磁带机，由n个进程竞争使用，每个进程可能需要两台磁带机，那么n是多少时，系统才没有死锁的危险？【解答】对于三个进程，每个进程能够有两个驱动器。对于4个进程，驱动器可以按照（2，2，1，1）的方法进行分配，使前面两个进程先结束。

对于5个进程，可以按照（2，1，1，1，1）的方法进行分发，使一个进程先结束。

对于六个进程，每个进程都拥有一个磁带驱动器同时需要另外一个驱动器，产生了死锁。因此，对于n<6的系统来说是无锁的。【例】设系统中仅有一个资源类，其中共有3个资源实例，使用此类资源的进程共有3个，每个进程至少请求一个资源，它们所需资源最大量的总和为X，则发生死锁的必要条件是（X的取值）【解答】假设3个进程所需该类资源数分别是a,b,c个，因此有：

a+b+c=X假设发生了死锁，也即当每个进程都申请了部分资源，还需最后一个资源，而此时系统中已经没有了剩余资源，即：

(a-1)+(b-1)+(c-1)≥3X=a+b+c≥6因此，如果发生死锁，则必须满足的必要条件是（X≥6）【例】假设某系统中有4种资源(R1,R2,R3,R4)，在某时刻系统中共有5个进程，进程P1，P2，P3，P4，P5的最大资源需求数量和此刻已分配到资源数向量分别如下系统中当前可用资源向量为(2,1,0,0),问1当前系统是否是安全的？2如果进程P3发出资源请求向量(0,1,0,0)，系统能否将资源分配给它？【分析】(1)进程的最大资源需求数减去当前进程已获得的资源数就是进程仍需要的资源数，此刻各个进行的仍需要资源数向量为：P1(0,0,0,0);P2(0,7,5,0);P3(6,6,2,2);P4(2,0,0,2);P5(0,3,2,0)而系统的可用资源向量为(2,1,0,0),这时存在如下执行序列，使进程顺序执行完毕，状态安全进程可用资源数P1完成后(2,1,1,2)P4完成后(4,4,6,6)P5完成后(4,7,9,8)P2完成后(6,7,9,8)P3完成后(6,7,1,12)满足资源需求的进程执行序列为：进程名可用资源数P1完成后(2,0,1,2)P4完成后(4,3,6,6)P5完成后(4,6,9,8)此时可用资源不能满足P2,P3的需求，即此时系统状态是不安全的，将拒绝资源请求此时系统可用资源为(2,0,0,0)，各进程仍需要资源向量为：P1(0,0,0,0);P2(0,7,5,0);P3(6,5,2,2);P4(2,0,0,2);P5(0,3,2,0)在P3发出资源请求(0,1,0,0)后，假设系统把资源分配给P3,则各进程已分配资源数为：P1(0,0,1,2);P2(2,0,0,0);P3(0,1,3,4);P4(2,3,5,4);P5(0,3,3,2)12考虑下表所示的系统瞬时状态，利用banker算法回答下面的问题：

(1)数组Need的内容是什么?(2)该系统处于安全态吗?若是，给出一安全序列。

(3)若进程P1的请求(0420)到达，该请求是否能立即满足?

(1)由于Need：Max-Allocation，所以Need的内容是：

0000 0750100200200642(2)是处于安全态，序列（P0，P2，P1，P3，P4）满足安全性要求。(3)能立即得到满足，因为①(0420)<=Available=(1520)②(0420)<=Maxi=(1750) ③分配后的新系统状态如下表所示，且序列（P0，P2，P1，P3，P4）满足安全性要求。生产者-消费者问题中，如果对调生产者进程中的两个P操作和两个V操作，则可能发生什么情况？解：生产者-消费者的同步问题中，如果对调生产者进程中的两个P操作和两个V操作，那么生产者和消费者的进程分别描述如下：producer(){while(生产未完成){生产一个产品；

P(mutex);p(empty);

送一个产品到有界缓冲区；