多生产者单消费者捆绑消费问题

1. 问题描述

某商店有两种食品A和B,最大数量各为m个。该商店将A,B两种食品搭配出售，每次各取一个。为避免食品变质，遵循先到食品先出售的原则，有两个食品公司分别不断地供应AB两种食品（每次一个）。为保证正常销售，当某种食品的数量比另种的数量超过k(k<m)个时，暂停对数量大的食品进货，补充数量少的食品，请回答：

(1) 共需设置几个进程？
(2) 试用P,V操作解决上述问题中的同步和互斥关系

2. 问题分析

首先，我们对问题进行抽象：可以看作是多生产者，单消费者问题。两个生产者A，B产生两类商品，供消费者进程消费，可以用3个进程表示。下面我们对问题中的互斥和同步关系进行抽象：

互斥关系

• 两个生产商对商店商品的供应应该是互斥的，即：两个厂商不能同时访问（添加）商品队列
• 为保证安全，生产商与消费者也不能同时访问商品队列

同步关系

• 只有当商品队列未满时，生产者才可供货
• 只有当商品队列同时存在A，B两种商品时，消费者才可以销售
• 由于当某种食品的数量比另种的数量超过k(k<m)个时，要暂停对数量大的食品进货，所以此条件的判断应在生产之前。同时，由于商品数量的差值这一变量是“动态的”，且需要互斥访问，故设置信号量动态表示比较方便

注意：由于题目中存在捆绑销售的关系，即：购买一个A商品，一定要同时购买一个B商品

程序关系图

由上述同步关系可知，程序关系图如下：

3. 问题解决

变量说明

• store信号量用于表示商店货架的空位，初始值为m
• mutex信号量用于控制商店队列的互斥访问，初值为1
• a_number信号量用于表示商店队列中A商品的数目
• b_number信号量用于表示商店队列中B商品的数目
• a_buffer信号量用于表示A商品还可以生产的数量，初值为k
• b_buffer信号量用于表示B商品还可以生产的数量，初值为k

伪代码实现

semaphore store=m,mutex=1,a_b=0,b_a=0;
void ProducerA():
{
	do{
        // produce product A
        
        wait(store);
        wait(a_buffer);
        wait(mutex);
       
        // add product A to the shop list
        
        signal(mutex);
        signal(b_buffer);
        signal(a_number);
            
    }while(ture);
}

void ProducerB():
{
	do{
        // produce product B
        
        wait(store);
        wait(b_buffer);
        wait(mutex);
       
        // add product B to the shop list
        
        signal(mutex);
        signal(a_buffer);
        signal(b_number);
            
    }while(ture);
}

void Consumer():
{
	do{
        
        wait(a_number);
        wait(b_number);
        wait(mutex);
       
        // remove product A and B from the shop list
        
        signal(mutex);
        signal(store);
        
        // use product A and B
            
    }while(ture);
}