1、生产流水线问题问题描述：设自行车生产线上有一只箱子，其中有N 个位置( N3) ，每个位置可存放一个车架或一个车轮; 又设有三个工人，其活动分别为:工人1活动：do加工一个车架; 车架放入箱中; while (1)工人2活动：do加工一个车轮; 车轮放入箱中; while (1)工人3活动：do箱中取一车架;箱中取二车轮;组装为一台车; while (1)试分别用信号灯与PV 操作实现三个工人的合作，要求解中不含死锁。问题分析：用信号灯与PV 操作实现三个工人的合作首先不考虑死锁问题，工人1与工人3、工人2与工人3构成生产者与消费者关系，这两对生产/消费关系通过共同的缓冲区相联系。从资源的角度
2、来看，箱子中的空位置相当于工人1和工人2的资源，而车架和车轮相当于工人3的资源。定义三个信号灯：semaphore empty=N;semaphore wheel=0;semaphore frame=0;三位工人的活动分别为：procedure 工人1：do加工一个车架;P(empty);车架放入箱中;V(frame); while (1)procedure 工人2；do加工一个车轮;P(empty); 车轮放入箱中;V(wheel); while (1)procedure 工人3：do P(frame);箱中取一车架;V(empty);P(wheel);P(wheel);箱中取二车轮;V(e
3、mpty);V(empty);组装为一台车; while (1)分析上述解法易见，当工人1推进速度较快时，箱中空位置可能完全被车架占满或只留有一个存放车轮的位置，而当此时工人3同时取2个车轮时将无法得到，而工人2又无法将新加工的车轮放入箱中；当工人2推进速度较快时，箱中空位置可能完全被车轮占满，而当此时工人3同取车架时将无法得到，而工人1又无法将新加工的车架放入箱中。上述两种情况都意味着死锁。为防止死锁的发生，箱中车架的数量不可超过N-2，车轮的数量不可超过N-1，这些限制可以用两个信号灯来表达。如此，可以给出不含死锁的完整解法如下：semaphore s1=N-2;semaphore s2=
4、N-1;semaphore empty=N;semaphore wheel=0;semaphore frame=0;Procedure 工人 1：do 加工一个车架;P(s1);P(empty); 车架放入箱中;V(frame); while (1)procedure 工人2：do 加工一个车轮;p(s2); P(empty); 车轮放入箱中;V(wheel); while (1)procedure 工人3 ：do P(frame);箱中取一车架;V(empty);V(s1);P(wheel);P(wheel);箱中取二车轮;V(empty);V(empty);V(s2);V(s2);组装为一
5、台车; while (1)详细描述还应考虑对箱子单元的描述以及访问互斥问题。建议车架放在箱子的一端，车轮放在箱子的另一端，车架与车轮都采用后进先出的管理方式。Semaphore s1=N-2，s2=N-1，mutex=1;semaphore empty=N;semaphore wheel=0;semaphore frame=0;int in1=0，in2=N-1;int bufN;procedure 工人1：do加工一个车架; P(s1); P(empty); P(mutex); Bufin1=车架；in1=in1+1; V(mutex); V(frame); while (1)procedu
6、re 工人2：do加工一个车轮; P(s2); P(empty); P(mutex);Bufin2=车轮；in2=in2-1;V(mutex); V(wheel); while (1)procedure 工人3 ：do P(frame);P(mutex);Temp1=Bufin1-1；in1=in1-1;V(mutex);V(empty);V(s1);P(wheel);P(wheel);P(mutex);Temp2=Bufin2+1;in2=in2+1;Temp3=Bufin2+1;In2=in2+1;V(mutex);V(empty);V(empty);V(s2);V(s2);组装为一台车; while(1)
