生产者消费者问题（英语：Producer-consumer problem），也称有限缓冲问题（英语：Bounded-buffer problem），是一个多线程同步问题的经典案例。
该问题描述了共享固定大小缓冲区的两个线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。
生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。
要解决该问题，就必须让生产者在缓冲区满时休眠（要么干脆就放弃数据），等到下次消费者消耗缓冲区中的数据的时候，生产者才能被唤醒，开始往缓冲区添加数据。同样，也可以让消费者在缓冲区空时进入休眠，等到生产者往缓冲区添加数据之后，再唤醒消费者。通常采用进程间通信的方法解决该问题。如果解决方法不够完善，则容易出现死锁的情况。出现死锁时，两个线程都会陷入休眠，等待对方唤醒自己。该问题也能被推广到多个生产者和消费者的情形。
该问题需要注意的几点：
- 在缓冲区为空时，消费者不能再进行消费
- 在缓冲区为满时，生产者不能再进行生产
- 消费者之间互斥，生产者之间互斥，但是生产者和消费者之间不影响
- 注意条件变量与互斥锁的顺序
假设缓冲区大小为k，生产者、消费者线程若干。生产者和消费者相互等效,只要缓冲池未满,生产者便可将消息送入缓冲池;只要缓冲池未空,消费者便可从缓冲池中取走一个消息。
items代表缓冲区已经使用的资源数，spaces代表缓冲区可用资源数
mutex min,mout代表互斥锁
Buf[k] 代表缓冲区，其内容类型为item
in、out代表第一个资源和最后一个资源
Semahore full,empty;
full.value = 0 ,empty = k;
Item Buff[k];
Mutex min,mout;
int in = 0,out = 0;
producer {
while(1) {
produce(&item);
P(empty); // 等待缓冲区有空闲位置， 在使用PV *** 作时，条件变量需要在互斥锁之前
P(min); // 保证在product时不会有其他product访问缓冲区
putitem(Buff,in,item); // 将新资源放到buf[in]位置
in = ( in + 1 ) % k;
V(min); // 唤醒的顺序可以不同
V(full); // 通知consumer缓冲区有资源可以取走
}
}
consumer {
while(1) {
P(full); // 等待缓冲区有资源可以使用
P(mout); // 保证在consume时不会有其他consumer访问缓冲区
getitem(Buff,out,&item);
out = ( out + 1 ) % 10;
V(mout); // 唤醒的顺序可以不同
V(empty); // 通知缓冲区有空闲位置
comsum(item);
}
}
读者写者问题
哲学家进餐问题
有五个哲学家围在一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和物质筷子，他们的生活方式是交替的进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕后，放下筷子继续思考。
由问题描述我们可以知道，一共有五个哲学家，也就是五个进程；五只筷子，也就是五个临界资源；因为哲学家想要进餐，必须要同时获得左边和右边的筷子，这就是要同时进入两个临界区（使用临界资源），才可以进餐。
因为是五只筷子为临界资源，因此设置五个信号量即可。
一个错误例子semaphore mutex[5] = {1,1,1,1,1}; //初始化信号量
void philosopher(int i){
do {
//thinking //思考
P(mutex[i]);//判断哲学家左边的筷子是否可用
P(mutex[(i+1)%5]);//判断哲学家右边的筷子是否可用
//...
//eat //进餐
//...
V(mutex[i]);//退出临界区，允许别的进程 *** 作缓冲池
V(mutex[(i+1)%5]);//缓冲池中非空的缓冲区数量加1，可以唤醒等待的消费者进程
}while(true);
}
我们来分析下上面的代码，首先我们从一个哲学家的角度来看问题，程序似乎是没有问题的，申请到左右两支筷子后，然后开始进餐。但是如果考虑到并发问题，五个哲学家同时拿起了左边的筷子，此时，五只筷子立刻都被占用了，没有可用的筷子了，当所有的哲学家再想拿起右边筷子的时候，因为临界资源不足，只能将自身阻塞，而所有的哲学家全部都会阻塞，并且不会释放自己手中拿着的左边的筷子，因此就会一直处于阻塞状态，无法进行进餐并思考。
因为，为了解决五个哲学家争用的资源的问题，我们可以采用以下几种解决方法：
至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用餐完毕后能释放他占用的筷子，从而使别的哲学家能够进餐；
仅当哲学家的左、右两支筷子可用时，才允许他拿起筷子；
规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。
下面我们对每种方法给出哲学家进程的伪代码。
对于方法一，至多只允许有四位哲学家同时去拿左边的筷子，我们可以简单的通过增加一个信号量实现，通过这个信号量限定哲学家并发去进餐的数量。
semaphore mutex[5] = {1,1,1,1,1}; //初始化信号量
semaphore count = 4; //控制最多允许四位哲学家同时进餐
void philosopher(int i){
do {
//thinking //思考
p(count); //判断是否超过四人准备进餐
P(mutex[i]); //判断缓冲池中是否仍有空闲的缓冲区
P(mutex[(i+1)%5]);//判断是否可以进入临界区（ *** 作缓冲池）
//...
//eat //进餐
//...
V(mutex[i]);//退出临界区，允许别的进程 *** 作缓冲池
V(mutex[(i+1)%5]);//缓冲池中非空的缓冲区数量加1，可以唤醒等待的消费者进程
V(count);//用餐完毕，别的哲学家可以开始进餐
}while(true);
}
解决哲学家进餐问题—方法二
第二种方法，也就是使用AND型信号量，同时对哲学家左右两边的筷子同时申请。下面是伪代码：
semaphore mutex[5] = {1,1,1,1,1}; //初始化信号量
void philosopher(int i){
do {
//thinking //思考
Swait(mutex[i], mutex[(i+1)%5]);//判断哲学家左边和右边的筷子是否同时可用
//...
//eat
//...
Ssignal(mutex[i], mutex[(i+1)%5]);//进餐完毕，释放哲学家占有的筷子
}while(true);
}
解决哲学家进餐问题—方法三
对于第三种，需要在代码中添加个判断，来决定获取左、右筷子的顺序，其伪代码如下：
semaphore mutex[5] = {1,1,1,1,1}; //初始化信号量
void philosopher(int i){
do {
//thinking
if(i%2 == 1){
P(mutex[i]);//判断哲学家左边的筷子是否可用
P(mutex[(i+1)%5]);//判断哲学家右边的筷子是否可用
}else{
P(mutex[(i+1)%5]);//判断哲学家右边的筷子是否可用
P(mutex[i]);//判断哲学家左边的筷子是否可用
}
//...
//eat
//...
V(mutex[i]);//退出临界区，允许别的进程 *** 作缓冲池
V(mutex[(i+1)%5]);//缓冲池中非空的缓冲区数量加1，可以唤醒等待的消费者进程
}while(true);
}
和尚打水问题(多生产者多消费者)：
问题描述：某寺庙，有小和尚和老和尚若干，有一个水缸，由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水，水取自同一口井中，由于水井口窄，每次只能容纳一个水桶取水。水桶总数为n个。每次入水、取水仅为一桶，且不可同时进行。
信号量设置：
- 1.对于水缸——以一个水桶水为单位，empty=10、full = 0两个计数信号量
- 小和尚对缸 *** 作：mutex-jar = 1二元信号量；
- 水桶个数(资源数)：bucket = n计数信号量
- 取水 *** 作(每次入水、取水仅为一桶)：互斥mutex-well = 1二元信号量；
伪代码：
吃水果问题(多生产者多消费者)：吸烟者问题-单生产者多消费者问题问题描述：桌上有一只盘子,最多可容纳一个水果,每次只能放人/取出一个水果。父亲专向盘子中放苹果(apple),母亲专向盘子中放橘子(orange),儿子专等吃盘子中的橘子,女儿专等吃盘子里的苹果。试设计信号量并使用P、V *** 作同步父,母、子、女进程。
问题描述：假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）。
可生产多种产品的单生产者以及多消费者问题。
生产者可生产的产品一共有三种：
组合一：纸+胶水；组合二：烟草+胶水；组合三：烟草+纸。
互斥关系：桌子可以看作是一个容量为1的缓冲区，其访问是互斥的；
同步关系：桌上有组合一之后第一个抽烟者取走组合一；
桌上有组合二之后第二个抽烟者取走组合二；
桌上有组合三之后第三个抽烟者取走组合三；
取走东西使用完成后供应者将下一个组合放到桌子上。
伪代码：
理发师睡觉理发问题-单生产者多消费者问题假设有一个理发店只有一个理发师，一张理发时坐的椅子，若干张普通椅子顾客供等候时坐。没有顾客时，理发师就坐在理发的椅子上睡觉。顾客一到，他不是叫醒理发师，就是离开。如果理发师没有睡觉，而在为别人理发，他就会坐下来等候。如果所有的椅子都坐满了人，最后来的顾客就会离开。
在出现竞争的情况下问题就来了，这和其它的排队问题是一样的。实际上，与哲学家就餐问题是一样的。如果没有适当的解决方案，就会导致进程之间的“饿肚子”和“死锁”。
如理发师在等一位顾客，顾客在等理发师，进而造成死锁。另外，有的顾客可能也不愿按顺序等候，会让一些在等待的顾客永远都不能理发。
解决方案：
最常见的解决方案就是使用三个信号量（Semaphore）：
一个给顾客信号量，一个理发师信号量（看他自己是不是闲着），第三个是互斥信号量（Mutual exclusion，缩写成mutex）。
一位顾客来了，他想拿到互斥信号量，他就等着直到拿到为止。顾客拿到互斥信号量后，会去查看是否有空着的椅子（可能是等候的椅子，也可能是理发时坐的那张椅子）。
如果没有一张是空着的，他就走了。如果他找到了一张椅子，就会让空椅子的数量减少一张，这位顾客接下来就使用自己的信号量叫醒理发师。
这样，互斥信号标就释放出来供其他顾客或理发师使用。如果理发师在忙，这位顾客就会等。理发师就会进入了一个永久的等候循环，等着被在等候的顾客唤醒。一旦他醒过来，他会给所有在等候的顾客发信号，让他们依次理发。
semaphore customers = 0;
semaphore barbers = 0;
semaphore mutex = 1; // 椅子是理发师和顾客进程都可以访问的临界区
int chair = N; //所有的椅子数量
cobegin
process barber(){
While(true){ //持续不断地循环
P(customers); //试图为一位顾客服务，如果没有他就睡觉（进程阻塞）
P(mutex); //如果有顾客，这时他被叫醒（理发师进程被唤醒），要修改空椅子的数量
chair--; //一张椅子空了出来
V(barbers); //现在有一个醒着的理发师，理发师准备理发.
//多个顾客可以竞争理发师互斥量，但是只有一个顾客进程被唤醒并得到服务
V(mutex); //释放椅子互斥量，使得进店的顾客可以访问椅子的数量以决定是否进店等待
cut_hair();
｝
}
process customer_i(){
P(mutex); //想坐到一张椅子上
if (chair > 0){
chair--; //顾客坐到一张椅子上了
V(customers); //通知理发师，有一位顾客来了
V(mutex); //顾客已经坐在椅子上等待了，访问椅子结束，释放互斥量
P(barbers); //该这位顾客理发了，如果理发师还在忙，那么他就等着（顾客进程阻塞）
get_haircut(); //顾客坐下剪头~
}
else
V(mutex); //不要忘记释放被锁定的椅子,没椅子，顾客跑了。
}
coend
哲学家进餐问题参考来源经典的进程同步问题-----哲学家进餐问题详解_丹丹的后花园-CSDN博客_哲学家就餐问题
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）