问题描述
系统中有一组生产者进程和一组消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者进程每次从缓冲区取出一个产品并使用;缓冲区在同一时刻只能允许一个进程访问。
问题分析
- 生产者、消费者共享一个初始为空、大小为n的缓冲区,我们把缓冲区中未存放数据的一个块,当作一个“空位”;把其中按块存放的数据当作“产品”。
- 同步关系:生产者与消费者
- 只有缓冲区有空位时,生产者才能把产品放入缓冲区
-
生产者把“空位”当作资源,缓冲区初始为空,即空位数量为n(n:空的缓冲区大小)
- 所以可以设置信号量empty,初始n
- empty>0时,有空位,生产者可以消耗“空位”这种资源即P(empty);
- empty<=0时,生产者无“空位”资源可用,便会挂起到阻塞队列等待。
- 所以可以设置信号量empty,初始n
-
生产者把“空位”当作资源,缓冲区初始为空,即空位数量为n(n:空的缓冲区大小)
- 只有缓冲区有产品时,消费者才能从缓冲区中取出产品
-
消费者把“产品”当作资源,缓冲区初始为空,即产品数量为0
- 所以可以设置信号量full,初始为0
- full<=0,消费者无“产品”这种资源可用,便会挂起到阻塞队列
- full>0,有产品,消费者可以消耗“产品”这种资源即P(full)
- 所以可以设置信号量full,初始为0
-
消费者把“产品”当作资源,缓冲区初始为空,即产品数量为0
- 进一步:
- empty>0时,有空位,生产者可以消耗“空位”这种资源即P(empty)的同时:生产了“产品这种资源”,即V(full);
- full>0时,有产品,消费者可以消耗“产品”这种资源即P(full)的同时:生产了“空位”这种资源,即V(empty);
- 只有缓冲区有空位时,生产者才能把产品放入缓冲区
- 互斥关系:所有进程之间
- 缓冲区是临界资源,各个进程必须互斥地访问
- 设置信号零mutex,初始为1
- 在进入区P(mutex)申请资源
- 在退出区V(mutex)释放资源
- 设置信号零mutex,初始为1
- 缓冲区是临界资源,各个进程必须互斥地访问
设计
typedef struct{
int value;
Struct process *L; //等待序列
}semaphore;
semaphore full;
semaphore empty;
semaphore mutex;
//某进程需要使用资源时,通过wait原语申请:P操作
void wait(semaphore S){
S.value--;
if(S.value < 0){
block(S.L);//阻塞原语,将当前进程挂载到当前semaphore的阻塞队列
}
}
//进程使用完资源后,通过signal原语释放:V操作
void signal(semaphore S){
S.value++;
if(S.value <= 0){
wakeup(S.L);//唤醒原语,将当前semaphore的阻塞队列中的第一个进程唤醒
}
}
full.value=0; //缓冲区 “产品”资源数(初始为0),用于实现生产者与消费者进程的同步
empty.value=n; //缓冲区 “空位”资源数(初始为n),用于实现生产者与消费者进程的同步
mutex.value=1; //互斥信号量,用于实现所有进程之间互斥地访问缓冲区
//生产者
producer(){
while(1){
Produce(); //生产“产品”
P(empty); //“空位”数-1
P(mutex); //临界区上锁
Storage(); //摆放产品
V(mutex); //临界区解锁
V(full); //“产品”数+1
}
}
//消费者
consumer(){
while(1){
P(full); //“产品”数-1
P(mutex); //临界区上锁
TakeOut(); //拿走产品
V(mutex); //临界区解锁
V(empty); //“空位”数+1
Use(); //使用“产品”
}
}
对于各个操作顺序的理解:
-
对于一部分操作的顺序,我们很好理解,符合我们的认知:
-
//生产者 Produce(); //生产产品 P(empty); //“空位”数-1,可能有人在这里会问这个操作为什么不可以放在“Storage甚至是V(full)”后面,考虑一种情况:当空位数为0时,我们是不能摆放产品的,而这个操作正是在检查是否还有“空位”这种资源;所以它一定在Storage前面。 Storage(); //摆放产品 V(full); //“产品”数+1,可能有人在这里会问这个操作为什么不可以放在“Storage甚至是P(empty)”前面,考虑一种情况:当产品数为n时,我们是不能再摆放产品的,因为缓冲区已满,再向其中添加数据(执行Storage)是要出问题的;所以它一定在Storage后面。
-
//消费者 P(full); //“产品”数-1,同上面一样,可能有人在这里会问这个操作为什么不可以放在“TakeOut甚至是V(empty)”后面,考虑一种情况:当产品数为0时,我们是不能拿走产品的,而这个操作正是在检查是否还有“产品”这种资源;所以它一定在TakeOut前面。 TakeOut(); //拿走产品 V(empty); //“空位”数+1,同上面一样,可能有人在这里会问这个操作为什么不可以放在“TakeOut甚至是P(full)”前面,考虑一种情况:当空位数为n时,我们是不能拿走产品的,因为缓冲区已经空了,再拿走(执行TakeOut)拿走个寂寞;所以它一定在TakeOut前面。 Use(); //使用“产品”
-
-
对于其他操作:实现同步的P操作一定要在实现互斥的P操作之前,为什么呢?
-
反向分析:我们考虑若调换生产者上述两个P操作的顺序:
//生产者 producer(){ while(1){ Produce(); //生产产品 P(mutex); //临界区上锁 P(empty); //“空位”数-1 Storage(); //摆放产品 V(mutex); //临界区解锁 V(full); //“产品”数+1 } } //消费者 consumer(){ while(1){ P(full); //“产品”数-1 P(mutex); //临界区上锁 TakeOut(); //拿走产品 V(mutex); //临界区解锁 V(empty); //“空位”数+1 Use(); //使用“产品” } }
- 若此时缓冲区已经放满产品,则empty=0,full=n
- 生产者进程执行P(mutex),mutex变为0,由于empty为0即没有“空位”了,需要生产者进程阻塞,等待消费者拿走产品
- 切换至消费者进程,消费者进程执行到P(mutex),由于mutex为0即生产者未释放临界资源,需要生产者释放临界资源,消费者进程阻塞
- 互相等待,进入死锁
-
结论:不要让因同步引起的进程阻塞(P操作可能产生结果)发生在为临界区上锁之后,因为:
- 临界区上锁,表示临界资源已被占用;若对临界区未解锁之前,发生了因同步引起的进程阻塞(上例中即需要生产者进程阻塞,等待消费者拿走产品)。
- 那么紧接着切换到另一个和此进程有同步和互斥关系的进程运行,且该进程也要对临界区访问:由于临界区已被上锁,则两进程进入死锁状态。
- 若此时缓冲区已经放满产品,则empty=0,full=n
-
说白了,对于进程来说,阻塞前对临界资源上锁,就是占着茅坑不拉屎(粗俗的讲:死锁就是两个人都占着茅坑不拉屎,还都等着对方离开然后在别人茅坑里才能拉)。
-
-
Produce和Use可以放在临界区吗?
- 为了进程快速交替使用临界资源,要让临界区代码尽量短,所以不把生产和使用产品的代码放在临界区代码中
-
V操作不会使进程阻塞,故互斥和同步的V操作顺序从理论上来说可以调换,但同3一样,为了进程快速交替使用临界资源,要让临界区代码尽量短,所以不把同步的V操作放在临界区代码中
-
综上:不要往临界区中添加与访问临界资源无关的操作/代码