生产流水线问题.doc

生产流水线问题
问题描述：
设自行车生产线上有一只箱子，其中有N个位置( N≥3)，每个位置可存放一个车架或一个车轮; 又设有三个工人，其活动分别为:
工人1活动：
do{
加工一个车架;
车架放入箱中;
} while (1)
工人2活动：
do{
加工一个车轮;
车轮放入箱中;
} while (1)
工人3活动：
do{
箱中取一车架;
箱中取二车轮;
组装为一台车;
} while (1)
试分别用信号灯与PV 操作实现三个工人的合作，要求解中不含死锁。

问题分析：
用信号灯与PV 操作实现三个工人的合作首先不考虑死锁问题，工人1与工人3、工人2与工人3构成生产者与消费者关系，这两对生产/消费关系通过共同的缓冲区相联系。从资源的角度来看，箱子中的空位置相当于工人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(empty);
V(empty);
组装为一台车;
} while (1)

分析上述解法易见，当工人1推进速度较快时，箱中空位置可能完全被车架占满或只留有一个存放车轮的位置，而当此时工人3同时取2个车轮时将无法得到，而工人2又无法将新加工的车轮放入箱中；当工人2推进速度较快时，箱中空位置可能完全被车轮占满，而当此时工人3同取车架时将无法得到，而工人1又无法将新加工的车架放入箱中。上述两种情况都意味着死锁。为防止死锁的发生，箱中车架的数量不可超过N-2，车轮的数量不可超过N-1，这些限制可以用两个信号灯来表达。如此，可以给出不含死锁的完整解法如下：
semaphore s1=N-2;
semaphore s2=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);
组装为一台车;
} 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 buf[N];
procedure 工人1：
do{
加工一个车架;
P(s1);
P(empty);
P(mutex);
Buf[in1]=车架；
in1=in1+1;
V(mutex);
V(frame);
} while (1)
procedure 工人2：
do{
加工一个车轮;
P(s2);
P(empty);
P(mutex);
Buf[in2]=车轮；
in2=in2-1;
V(mutex);
V(wheel);
} while (1)
procedure 工人3 ：
do {
P(frame);
P(mutex);
Temp1=Buf[in1-1]；
in1=in1-1;
V(mutex);
V(empty);
V(s1);
P(wheel);
P(wheel);
P(mutex);
Temp2=Buf[in2+1];
in2=in2+1;
Temp3=Buf[in2+1];
In2=in2+1;
V(mutex);
V(empty);
V(empty);
V(s2);
V(s2);
组装为一台车;
} while(1)