PV经典问题之生产者消费者问题
基本问题
问题描述：
⼀组⽣产者进程和⼀组消费者进程共享⼀个初始为空、固定⼤⼩为n的缓冲区。只有缓冲区没满时，⽣产者 才能把消息放⼊到缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。 由于缓冲区是临界资源，它只允许⼀个⽣产者放⼊消息，或者⼀个消费者从中取出消息。
问题的核⼼在于：
1、⽣产者：满则等待，空则填充；
2、消费者：空则等待，有则获取；
3、⽣产者和消费者不允许同时进⼊缓冲区。
问题分析:
1)关系分析。⽣产者和消费者对缓冲区互斥访问是互斥关系，同时⽣产者和消费者又是⼀个相互协作的关系，只有 ⽣产者⽣产之后，消费者才能消费，他们也是同步关系。
2)整理思路。只有⽣产者和消费者两个进程，正好是这两个进程存在着互斥关系和同步关系。那么需要解决的是互 斥和同步PV操作的位置。
故问题完整解答如下：
设置信号量mutex作为互斥信号量，它⽤于控制互斥访问缓冲池，互斥信号量初值为1；
设置信号量full⽤于记录当前缓冲池中“满”缓冲区数，初值为0。
设置信号量empty⽤于记录当前缓冲池中“空”缓冲区数，初值为n。
解决该问题的代码如下：
semaphore mutex = 1; //临界区互斥信号量量
semaphore empty = n; //“空”缓冲区数量量
semaphore full = 0; //“满”缓冲区数量量
producer () { //⽣生产者进程
while (1) {
produce an item in nextp; //或者写⽣生产数据也可以
P(empty); (要⽤用什什么，P⼀一下) //获取空缓冲区单元
P(mutex); (互斥夹紧) //进⼊入临界区
add nextp to buffer; (⾏行行为) //或者写将数据放⼊入缓冲区也可以
V(mutex); (互斥夹紧) //离开临界区,释放互斥信号量量
V(full); (提供什什么，V⼀一下) //“满”缓冲区数加1 }
}
consumer () { //消费者进程
while (1) {
P(full); //获取满缓冲区单元
P(mutex); // 进⼊入临界区
remove an item from buffer; //或者写从缓冲区中取出数据也可以
V (mutex); //离开临界区，释放互斥信号量量
V (empty) ; //空缓冲区数加1
consume the item; //或者写消费数据也可以 }
}
变体形式
一、有3个进程PA，PB和PC合作解决⽂件打印问题；
1、PA将⽂件记录从磁盘读⼊主存的缓冲区1，每执⾏⼀次读⼀个记录;
2、PB将缓冲区1的内容复制到缓冲区2，每执⾏⼀次复制⼀个记录；
3、PC将缓冲区2的内容打印出来，每执⾏⼀次打印⼀个记录。缓冲区的⼤⼩等于⼀个记录⼤⼩。 请⽤P，V操作来保证⽂件的正确打印。
问题分析：
这是典型的双缓冲区问题，两个缓冲区⼤⼩均为1，其中PA为⽣产者，PB既是⽣产者又是消费者，PC为消费者， 故按照⽣产消费者问题的思路解决该题即可。但是需要注意的问题是：如果PA将数据放⼊缓冲区之后，PB没有及 时取的话，如果此时PA进程继续执⾏，那么会将之前的数据覆盖掉，缓冲区2也⼀样，因此这⾥还需要设置两个 信号量以限制缓冲区1和缓冲区2中记录的数量。
问题完整解答如下：
设置信号量full1，full2分别表⽰缓冲区1及缓冲区2是否有记录可供处理，初值均为0；
设置信号量empty1，empty2分别表⽰缓冲区1及缓冲区2是否还有空位可放记录，初值均为1；
设置互斥信号量mutex1，mutex2分别表⽰缓冲区1及缓冲区2的访问控制，初值均为1。
解决该问题的代码如下：
semaphore full1 = 0;
semaphore full2 = 0;
semaphore empty1 = 1;
semaphore empty2 = 1;
semaphore mutex1 = 1;
semaphore mutex2 = 1;
PA() {
while (1) {
从磁盘读⼀一个记录；
P(empty1);
P(mutex1);
将记录存⼊入缓冲区1；
V(mutex1);
V(full1);
}
}
PB() {
while(1) {
P(full1);
P(mutex1);
从缓冲区1中读出⼀一个⽂文件记录；
V(mutex1);
V(empty1);
P(empty2);
P(mutex2);
将⼀一个记录读⼊入缓冲区2；
V(mutex2);
V(full2);
}
}
PC() {
while (1) {
P(full2);
P(mutex2);
从缓冲区2取⼀一个记录；
V(mutex2);
V(empty2);
打印记录;
}
}
二、 有⼀个仓库，可以存放A和B两种产品，要求：
1、每次只能存⼊⼀种产品（A或B）
2、-N＜A产品数量－B产品数量＜M。
3、 其中，N和M是正整数
试⽤PV操作描述产品A与B的⼊库过程。
问题完整解答如下：
设置普通信号量Sa表⽰允许A产品⽐B产品多⼊库的数量，初值为M-1；
设置普通信号量Sb表⽰允许B产品⽐A产品多⼊库的数量，初值为N-1；
设置互斥信号量mutex表⽰仓库的互斥使⽤，初值为1
代码如下：
semaphore Sa = M - 1, Sb = N - 1;
semaphore mutex = 1;
// A产品⼊入库过程
Process_A() {
while (1) {
⽣生产A;
P(Sa);
P(mutex);
A产品⼊入库
V(mutex);
V(Sb);
}
}
// B产品⼊入库进程
Process_B() {
while (1) {
⽣生产B；
P(Sb);
P(mutex);
B产品⼊入库
V(mutex);
V(Sa);
}
}
三、老和尚与小和尚
某寺庙有⼩和尚和⽼和尚各若⼲⼈，⽔缸⼀只，由⼩和尚提⽔⼊缸给⽼和尚饮⽤。⽔缸可容⽔m桶，⽔取⾃同⼀ ⼜⽔井中。⽔井径窄，每次仅能容⼀只⽔桶取⽔，⽔桶总数为n个。若每次提⽔、取⽔仅为1桶，试⽤PV操作描述 ⼩和尚和⽼和尚提⽔、取⽔的活动过程。
问题分析：
互斥资源有⽔井和⽔缸，可分别设置⼀个互斥信号量来控制。⽔桶总数为n个，因此可设置资源信号量来记录⽔桶 的数量。⽔缸可容⽔m桶，在这⾥⽔缸可以看作⽣产消费者问题中的缓冲区，因此可设置两个资源信号量表⽰⽔缸 中已经有多少桶⽔以及还能放多少桶⽔。
问题完整解答如下：
设置资源信号量empty表⽰⽔缸中还能放多少桶⽔，初值为m；
设置资源信号量full表⽰⽔缸中已经放了多少桶⽔，初值为0；
设置资源信号量count表⽰⽔桶的数量，初值为n；
设置互斥信号量mutex1表⽰⽔井的互斥使⽤，初值为1；
设置互斥信号量mutex2表⽰⽔缸的互斥使⽤，初值为1。
代码如下：
semaphore mutex1 = 1, mutex2 = 1;
semaphore empty = m, full = 0; s
emaphore count = n;
//⼩小和尚从井中取⽔水并倒⽔水⼊入缸的过程
// (i = 1, 2, ...)
little_monk_i() {
while (1) {
P(empty); //⽔水缸是否满了了
P(count); //取得⽔水桶
P(mutex1); //互斥从井中取⽔水
从井中取⽔水;
V(mutex1);
P(mutex2); //互斥使⽤用⽔水缸
倒⽔水⼊入缸;
V(mutex2);
V(count); //归还⽔水桶
V(full); //多了了⼀一桶⽔水
}
}
//⽼老老和尚从缸中取⽔水的过程
// (j = 1, 2, ...)
old_monk_j() {
while (1) {
P(full); //缸中是否有⽔水
P(count); //申请⽔水桶
P(mutex2); //互斥取⽔水
从缸中取⽔水;
V(mutex2);
V(count); //归还⽔水桶
V(empty); //⽔水缸中可以多放⼀一桶⽔水
}
}
四、N个⽣产者进程和M个消费者进程共享⼤⼩为K的缓冲区，遵循规则如下：
1、进程之间必须以互斥⽅式访问缓冲区；
2、对每1条放⼊缓冲区的数据，所有消费者都必须接收1次；
3、 缓冲区满时，⽣产者必须阻塞；
4、缓冲区空时，消费者必须阻塞。
请⽤P、V操作实现其同步过程，须说明信号量含义
问题分析：
该问题的关键点在于：对每1条放⼊缓冲区的数据，所有消费者都必须接收1次。 换⾔之，由于总共有M个消费者进程，也就是说每条放⼊缓冲区的数据要消费M次才结束⽣命周期，针对M个消费者的消费过程都要设置各⾃的信号量，⽽这⾥为了⽅便，因此我们设定信号量数组。另外这道题还有⼀个需要注意的地⽅，就是缓冲区的⼤⼩为K，因此我们设置的empty信号量数组中 的元素初值均为K即可。
问题完整解答如下：
设置互斥信号量mutex⽤于⽣产者和消费者互斥访问缓冲区，初值为1；
设置资源信号量数组empty[M]，⽤于记录缓冲区的空位数，数组中元素的初值均为K；
设置资源信号量数组full[M]，⽤于记录缓冲区的资源数，数组中元素的初值均为0。
代码如下：
semaphore mutex = 1; //互斥信号量量，实现对缓冲区的互斥访问
semaphore empty[M] = {K, K, ... , K}; //M组空缓冲区
semaphore full[M] = {0, 0, ... , 0}; //M组填满数据的缓冲区
//1 <= i <= N
Producer_i() {
int j;
while (1) { //⽣生产⼀一条数据
for (j = 0; j < M;j++) {
P(empty[j]);
}
P(mutex);
将数据放⼊入缓冲区；
V(mutex);
for (j = 0; j < M; j++) {
V(full[j]);
}
}
}
//1 <= i <= M
Consumer_i() {
while(1) {
P(full[i]);
P(mutex);
从缓冲区取出数据；
V(mutex);
V(empty[i]);
}
}
五、系统有多个⽣产者进程和多个消费者进程，共享⼀个能存放1000件产品的环形缓冲区（初始为空）。
1、当缓冲区未满时，⽣产者进程可以放⼊其⽣产的⼀件产品，否则等待；
2、当缓冲区未空时，消费者进程可以从缓冲区取⾛⼀件产品，否则等待。3、 要求⼀个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品。
请使⽤信号量P，V操作实现进程间的互斥与同步，要求写出完整的过程，并说明所⽤信号量的含义和初值。
问题分析：
这是典型的⽣产者和消费者问题，并且只对典型问题加了⼀个条件，因此只需在⽣产消费者问题标准模型上新增加 ⼀个信号量，⽤于控制消费者进程从缓冲区连续取出10件产品的操作，即可完成指定要求。
问题完整解答如下：
设置互斥信号量mutex1⽤于⼀个控制⼀个消费者进程⼀个周期(10次)内对于缓冲区的控制；
设置互斥信号量mutex2⽤于进程单次互斥的访问缓冲区，初值为1；
设置资源信号量empty代表缓冲区的空位数，初值为1000；
设置资源信号量full代表缓冲区的产品数，初值为0。
代码如下：
semaphore mutex1 = 1;
semaphore mutex2 = 1;
semaphore empty = 1000;
semaphore full = 0;
producer () { //⽣生产者进程
while(1) {
⽣生产⼀一个产品；
P(empty);
P(mutex2);
将产品放⼊入缓冲区；
V(mutex2);
V(full);
}
}
consumer () { //消费者进程
while (1) {
P(mutex1); // 进⼊入临界区
for (int i = 0;i < 10;i++) {
P(full);
P(mutex2);
从缓冲区取出⼀一件产品；
V(mutex2);
消费这件产品；
}
V (mutex1); //离开临界区，释放互斥信号量量
}
}
下一篇： 读写者问题