4.3　例题解答

例1　进程之间存在哪几种制约关系？各是什么原因引起的？下列活动分别属于哪种制约关系？

1）图书馆借书

2）两队举行篮球赛

3）流水生产线

4）乐队演奏

5）购买火车票

答：有直接制约关系（即同步问题）和间接制约关系（互斥问题）；同步问题是存在逻辑关系的进程之间相互等待所产生的制约关系，互斥问题是相互逻辑关系的进程间竞争使用资源所发生的制约关系。

1）属于互斥关系，因为书的个数是有限的，一本书只能借给一个同学。

2）既存在互斥关系，也存在同步关系。篮球只有一个，两队都要竞争；但对于同一个队的队员之间需要相互协作才有可能取得比赛的胜利。

3）属于同步关系，生产线上各道工序的开始都依赖前道工序的完成。

4）属于同步关系，乐队中的每个成员需要相互协作共同完成乐曲演奏任务。

5）属于互斥关系，一张火车票只能卖给一个人。

例2　举例说明P、V操作为什么要设计成原语操作（包括对同一信号量的操作必须互斥）。

答：假设P操作的流程如下：

P(s)

{

lock out interrupts;

s=s-1;

if(s＜0)

{

status=blocked;

insert(Q,q);

unlock interrupts;

scheduler;

}

else unlock interrupts;

end

}

设信号量s的初始值为1，当一个P操作执行完s=s-1后，s的值为0，该P操作不应该被阻塞。但若P操作不是一个原语，也就是说，在一个P操作执行的过程，可以有另一个P操作同时在执行，假设第2个P操作在第1个P操作执行语句if s＜0前也执行了s=s-1操作，则这时s的值为-1。这时第1个P操作将会被阻塞。这样的P操作不符合定义的P操作的语义。

同样的，对于V操作，其流程为：

procedure V(s)

begin

lock out interrupts;

s=s+1;

if s＜=0 then

begin

remove(Q,q);

status(R)=reada;

insert(RL,R);

length(RL)=length(RL)+1;

end

unlock interrupts;

end

设信号量s的初值为-1，当一个操作执行完s=s+1后，s的值为0，该V操作应该唤醒一个被P操作阻塞的进程。

但若V操作不是一个原语，也就是说，在第一个V操作的进程中，有另一个V操作同时在执行。假如第2个V操作在第1个V操作执行语句if s≤0前，也执行了s=s+1操作，则这时s的值为1。这时第1个V操作将不再去唤醒被阻塞的进程。这样的V操作也不符合V操作的语义。

同样的，当P操作的执行过程中插入了V操作，也会出现不符合原语语义的情况。例如，在P操作执行完s=s-1后，s的值为-1，经判断该操作应该被阻塞。但若在进行判断后、阻塞进程前执行完另外一个V操作，则该V操作并没有可以唤醒的被阻塞的进程。而当V操作执行完后继续执行P操作时，该P操作仍将阻塞该进程，这一进程将不被唤醒。

对于V操作的执行过程中插入了P操作，也会出现不符合原语操作的情况。例如，在V操作执行完s=s+1后，s的值为1，该进程无需其他进程。但若在进行判断前执行了一个P操作，则在后续操作中需要一个阻塞进程。

例3　试用P、V操作描述下列理发师和顾客之间的同步问题：

某个理发师当没有顾客时，去睡觉；当有顾客来理发，若理发师正在睡觉时，这个顾客会叫醒他，理发师给该顾客理发，理发期间若还有顾客到达则等待理发师依次理发，直到没有顾客到来，理发师又去睡觉。

【分析】

可将此题看做是N个生产者和一个消费者问题。顾客作为生产者，每到来一位，就应将计数器rc计数一次，以便让理发师理发至最后一位顾客，因此，顾客进程执行的第一个语句便是rc=rc+1。而第一个到来的顾客应负责唤醒理发师，理发师此时正在信号量wakeup上等待（P(wakeup)）；该信号量初值为0，由第一个顾客执行V（wakeup）。若该顾客不是第一个到达者，则在信号量wait上等待（P(wait)）；该信号量初值为0，等到理发师给前一位顾客理完发后执行V(wait)，便给该顾客理发。以上过程循环往复，理发师每处理完一个顾客，就令计数器rc值减1，当rc=0时，便知此时无顾客，理发师可继续睡觉，等待下一批顾客的到达。为了保证对计数器rc的互斥使用，还需要设置信号量mutex（初值为1）。

答：用P、V操作描述理发师和顾客之间的同步问题：

semaphore wakeup,wait,mutex;

wakeup=0;

wait=0;

mutex=1;

cobegin

顾客进程：

{

P(mutex);

rc=rc+1;

if(rc==1)

V(wakeup);

else

P(wait);

V(mutex);

理发;

}

理发师进程：

{

P(wakeup);

while(rc!=0)

{

理发;

P(mutex);

rc=rc-1;

if(rc!=0)

V(wait);

V(mutex);

}

}

coend

例4　Hansen在1973年提出了用消息缓冲作为进程通信的一种基本方式。发送进程调用send过程将消息送往缓冲区，接收进程调用过程receive，将消息从缓冲区中取出送往自己的数据区。图4-6给出了不完整的send和receive过程。请填充适当的P、V操作，并说明所用信号量的意义和初值。

图　4-6　send和receive过程

【分析】

本题是生产者-消费者问题，与标准的生产者-消费者问题的不同之处在于，本题中的消息缓冲区个数是无限制的，因此，不需要设置生产者-消费者问题解答中的生产者进程的私有信号量avail。在框图中所给出的信号量s2，相当于生产者-消费者问题解答中的消费者进程的私有信号量full，在本题中，s2就是接收进程的私有信号量，表示等待接受的消息个数。

此外，为了正确控制程序流程，还要设置一个信号量s1，相当于生产者-消费者问题中的信号量mutex，以控制对缓冲区的互斥访问。

答：图4-6中所缺的步骤如下所示。

（1）P(s1)

（2）V(s1)

（3）P(s2)

（4）P(s1)

（5）V(s1)

其中，s1是用于控制互斥访问消息链的互斥信号量，其初值为1；s2是用于记录消息个数的同步信号量，其初值为0。

例5　简述管程与进程的区别。

答：两者的区别存在于以下几个方面：

1）管程定义的是公用数据结构，而进程则是私有数据结构。

2）管程把共享变量上的同步操作集中起来，而临界区却分散在每个进程中。

3）管程是为管理共享资源而建立的，进程主要是为实现系统的并发性而引入的。

4）管程被进程调用，通常是被欲使用共享资源的进程所调用。管程和调用它的进程不能并行工作，而进程之间能并行工作，并发性是其固有特性。

5）管程是语言或操作系统的固有成分，没有创建或撤销；而进程有生命周期，由创建而产生至撤销便消亡。

例6　试用P、V操作实现采用公用信箱的信箱通信中的send原语和receive原语。信箱类型定义如下：

typedef struct mailbox

{

int in,out;//取值范围为0～n-1

semaphore s1,s2;//发送进程和接收进程的私有信号量，初值分别为n和0

semaphore mutex;//对信箱互斥操作的信号量，初值分别为1

message letter[n];//信箱体，可以保存n封信件

}mailbox;

答：P、V操作实现send原语和receive原语分别描述如下：

send(mailbox MB;message M)

{

P(MB.s1);

P(MB.mutex);

MB.letter[MB.in]=M;

MB.in=(MB.in+1)%MB.n;

V(MB.mutex);

V(MB.s2);

}

receive(mailbox MB;message N)

{

P(MB.s2);

P(MB.mutex);

N=MB.letter[MB.out];

MB.out=(MB.in+1)%MB.n;

V(MB.mutex);

V(MB.s1);

}

例7　简述银行家算法的主要思想，并说明该算法是否可以用于解决现实中的死锁问题。

答：银行家算法是一种最有代表性的死锁避免算法。在银行家算法中，客户代表进程，资金代表资源，银行家代表操作系统。该算法允许进程动态申请资源，但系统每次在进行资源分配之前，先计算此次分配资源的安全性，若此次资源分配不会导致系统进入不安全状态（或存在安全序列），则分配资源；否则，不分配资源，让进程等待。

该算法有很大的理论意义，但在现实中受到很多限制，实际上很难实施。原因在于：

1）系统难以事先知道进程的总数和每个进程申请的最大资源数；有时，每个进程申请的最大资源数根据执行代码的不同路径有所不同；与输入的数据有关，不同的输入数据，每个进程申请的最大资源数就有所不同。

2）该算法要求所涉及的进程不能有同步要求，因此该算法很难解决现实中的死锁问题。

3）若出现各种异常现象，比较难处理。

例8　一组合作进程，执行顺序如图4-7所示。请用P、V操作实现进程之间的同步操作。

图　4-7　进程执行顺序

【分析】

进程同步关系在于，前一个进程完成之后向后续进程发信号量，后续进程若没有收到信号量，则需等待；若收到，则开始运行。分别设置以下信号量：

进程P2的私有信号量s12；进程P3的私有信号量s13；进程P4的私有信号量s24、s34，分别用于P4与P2和P3的同步控制；进程P5的私有信号量s25、s35，分别用于P5与P2和P3的同步控制；进程P6的私有信号量s46、s56，分别用于P6与P4和P5的同步控制。所有初值均为0。

答：P、V操作实现进程之间的同步操作描述如下：

semaphore s12,s13,s24,s34;

semaphore s25,s35,s46,s56;

s12=s13=s24=s34=s25=s35=s46=s56=0;

cobegin

P1();

P2();

P3();

P4();

P5();

P6();

coend

P1()

{

V(s12);

V(s13);

do all work;

}

P2()

{

P(s12);

do all work;

V(s24);

V(s25);

}

P3()

{

P(s13);

do all work;

V(s34);

V(s35);

}

P4()

{

P(s24);

P(s34);

do all work;

V(s46);

}

P5()

{

P(s25);

P(s35);

do all work;

V(s56);

}

P6()

{

P(s46);

P(s56);

do all work;

}