问题描述
「生产者-消费者问题」是操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。解决好生产者-消费者问题就解决好了一类并发进程的同步问题。
有
用代码表示为
int k;
typedef anyitem item; /*item类型*/
item buffer[k];
int in=0,out=0,counter=0;
对于生产者
process producer(void) {
while (true) { /*无限循环*/
{produce an item in nextp};/*生产一个产品*/
if (counter==k) /*缓冲满时，生产者睡眠*/
sleep(producer);
buffer[in]=nextp; /*一个产品放入缓冲区*/
in=(in+1)%k; /*指针推进*/
counter++; /*缓冲内产品数加1*/
if(counter==1) /*缓冲为空，加进一件产品*/
wakeup(consumer); /*并唤醒消费者*/
}
}
对于消费者
process consumer(void) {
while (true) { /*无限循环*/
if (counter==0) /*缓冲区空，消费者睡眠*/
sleep(consumer);
nextc=buffer[out];/*取一个产品到nextc */
out=(out+1)%k; /*指针推进*/
counter--; /*取走一个产品，计数减1 */
if(counter==k-1) /*缓冲满了，取走一件产品并唤*/
wakeup(producer); /*醒生产者*/
{consume the item in nextc};/*消耗产品*/
}
}
生产者和消费者进程对 counter 的交替执行会使其结果不唯一，生产者和消费者进程的交替执行会导致进程永远等待
信号量解决
信号量可用于解决生产者-消费者问题。生产者-消费者问题本身可以分为
- 一个生产者、一个消费者共享一个缓冲区
- 多个生产者、多个消费者共享多个缓冲区
一个生产者、一个消费者共享一个缓冲区
先讨论最简单的情况，一个生产者、一个消费者共享一个缓冲区，如下图
如果生产者发现 buffer 中的产品还没有被消费者取走，则它需要等待。
如果用信号量法解决此问题，首先定义两个信号量：empty 和 full，二者均为二元变量。其中 empty 表示缓冲区内剩余的空间，full 表示缓冲区内充满的空间。由于此情况只有一个缓冲区，且初始情况缓冲区为空，因此有 empty = 1 和 full = 0
int B;
semaphore empty; /*可以使用的空缓冲区数*/
semaphore full;
empty = 1 ; /*缓冲区内允许放入一件产品*/
full = 0; /*缓冲区内没有产品*/
得到信号量的设置后，就可以分别对生产者和消费者进行定义
cobegin
process producer() {
while(true) {
produce();
P(empty);
append to B;
V(full);
}
}
coend
cobegin
process consumer() {
while(true) {
P(full);
take from B;
V(empty);
consume();
}
}
}
coend
多个生产者，多个消费者和多个缓冲区
产品是临界资源/公共资源。生产者和消费者和产品之间存在进程同步关系。
生产者需要空闲仓库产生产品仓库，消费者需要产品仓库产生空闲仓库。因此两种任务之间构成「消费者与生产者关于空仓同步，生产者与消费者关于产品同步」
临界资源总结起来有四类，产品，空闲仓库以及两个指针
多个生产者，多个消费者和多个缓冲区的情况如下图所示
此时缓冲池中有 k 个缓冲区。为了用信号量解决此问题。
- 用一个头指针
P0来指示空缓冲区的头。生产者在向缓冲区存储资源时，如果发现有空闲仓库，就会申请获得P0，然后将生产产品放入P0所指向的仓库，然后P0逆时针移动一格 - 然后另外一个指针
C0指向第一个放有产品的仓库。消费者可以同样的申请C0，取走其中的产品，然后C0逆时针移动一格
如果生产者希望写入产品时，如果没有空闲的仓库，则陷入等待状态。同理，消费者希望取出产品时，没有填满的仓库，也会陷入等待状态。
按照此思路，一共有 4 个临界资源，分别需要 4 个信号量
- 空仓，
Empty：表示空的缓冲区数，初值为k，取值为 - 产品，
Full：表示满的缓冲区数，初值为0，取值为 - 空仓头指针，
Mutex_P0：分配空仓缓冲区的互斥信号量，初值为 - 产品链头指针，
Mutex_C0：分配空产品链的互斥信号量，初值为
此初始化过程用代码表示为
item B[k];
semaphore Empty; Empty = k; /*可以使用的空缓冲区数*/
semaphore Full; Full = 0; /*缓冲区内可以使用的产品数*/
semaphore Mutex_P0; Mutex_P0 = 1; /*互斥信号量*/
semaphore Mutex_C0; Mutex_C0 = 1; /*互斥信号量*/
int in=0;
int out=0;
然后对与生产者和消费者有
cobegin
process consumer_j (){
while(true) {
P(Full);
P(Mutex_C0);
take() from B[out];
out=(out+1)%k;
V(mutex_C0);
V(Empty);
consume();
}
}
process producer_i (){
while(true) {
produce();
P(Empty);
P(Mutex_P0);
append to B[in];
in=(in+1)%k;
V(Mutex_P0);
V(Full);
}
}
coend
P 次序不能颠倒，否则会出现死锁
比如当缓冲池全满，即 Empty=0, Full=k 时，如果生产者先执行指针 P 操作，再执行 Empty 的 P 操作，会导致“明明没有空间，但是指针移到了下一个缓冲区”的现象。此时再执行 Empty 的 P 操作，会陷入等待。而其他生产者无法获取互斥访问权，其他消费者也无法消费数据。造成死锁。
同理，当缓冲池全空时，如果消费者先执行指针 P 操作，再执行 Full 的 P 操作，会导致“明明没有产品，但是指针移到了下一个缓冲区”的现象，同样导致死锁。
因此 P 操作必须先检查的是数量，而不是指针。