17-生产者与消费者问题

2022-10-27 13:05:56 浏览数 (2)

生产者与消费者问题

系统中有一组生产者进程和一组消费者进程,生产者进程每次生产一个产品就放入缓冲区,消费者进程每次从缓冲区中取出一个产品并使用(这里的产品可能是某种数据)

生产者和消费者共享一个初始为空,大小为n的缓冲区

  • 只有缓冲区没满时,生产者才能将产品放入缓冲区,否则必须等待
  • 只有缓冲区不空时,消费者才能从缓冲区取出产品,否则必须等待
  • 缓冲区是临界资源,各进程必须互斥访问

PV操作题目常见方法

信号量机制可以实现互斥,同步以及对一类资源的申请和释放

  • 互斥:一般会设置初值为1的互斥信号量
  • 同步:设置初值为0的同步信号量(实现一前一后)
  • 资源的释放和申请:设置一个信号量,初始值即为资源数量(本质还是进程同步)

PV操作题目分析步骤

  1. 关系分析,找出题目中描述的各个进程,分析它们之间的同步互斥关系
    • 本题中,涉及以下几种进程同步,互斥关系
    • 互斥关系:对于临界区的访问,必须互斥进行
    • 同步关系:缓冲区满,生产者必须开始等待,直到消费者取走产品
    • 同步关系:缓冲区空,消费者必须开始等待,直到生产者放入产品
  2. 整理思路,根据各进程的操作流程确定P,V操作的大致顺序
    • 生产者每次要消耗一个空闲缓冲区(P)并生产一个产品(V)
    • 消费者每次要消耗一个产品(P)并释放一个空闲缓冲区(V)
    • 往缓冲区收入/取走产品需要互斥
  3. 设置信号量,根据上文内容确定所需的信号量,并根据题目条件确定信号量初值
    • 互斥信号量一般为1
    • 同步信号量一般为资源初始值

解题

根据上文所述,我们需要三个信号量来解决本问题

代码语言:javascript复制
semaphore mutex=1; // 互斥信号量,实现对缓冲区的互斥访问
semaphore empty=n; // 同步信号量,表示空闲缓冲区的数量
semaphore full=0; // 同步信号量,表示产品数量,也即非空闲缓冲区的数量

//生产者
producer (){
    // 执行循环
    while(1){
        生产一个产品
        P(empty); // 消耗一个空闲缓冲区
        P(mutex); // 对缓冲区上锁
        把产品放入缓冲区;
        V(mutex); //对缓冲区解锁
        V(full); //增加一个产品数量
    }
}

//消费者
consumer (){
    while(1){
        P(full); //消耗一个产品
        P(mutex); //对缓冲区上锁
        从缓冲区取出一个产品;
        V(mutex); //释放缓冲区
        V(empty); //增加一个空闲缓冲区数量
        使用产品;
    }
}

在这个过程中相邻的两个P操作不能交换位置,例如,若将生产者中相邻的两个P操作交换位置

代码语言:javascript复制
//生产者
producer (){
    // 执行循环
    while(1){
        生产一个产品
        P(mutex); // 对缓冲区上锁
        P(empty); // 消耗一个空闲缓冲区
        把产品放入缓冲区;
        V(mutex); //对缓冲区解锁
        V(full); //增加一个产品数量
    }
}

假设此时empty=0,full=n即缓冲区中没有空闲位置,则生产者进程执行

  1. 使mutex变为0
  2. 由于没有空闲缓冲区,所以生产者被阻塞
  3. 消费者进程执行,由于mutex=0,即生产者还没有释放临界资源的“锁”,所以消费者也被阻塞
  4. 生产者等待消费者释放空闲缓冲区,消费者等待生产者释放临界区资源
  5. 造成死锁

同理,若调换消费者相邻P操作的位置,在full=0,empty=n时也会造成死锁

因此,实现互斥的P操作一定要放在实现同步的P操作之后

V操作不会导致进程阻塞,因此相邻V操作的位置可换

多生产者多消费者问题-放取水果问题

桌子上有一只盘子,每次只能向其中放入一个水果。爸爸专向盘子中放苹果,妈妈专向盘子中放橘子,儿子专等着吃盘子中的橘子,女儿专等着吃盘子中的苹果。只有盘子空时,爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时,儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。

  1. 关系分析,找出题目中各个进程以及它们之间的同步互斥关系
    • 可以看到,这个题目中父亲和母亲相当于两个生产者进程,女儿和儿子相当于两个消费者进程
    • 只不过要注意这里的两个生产者生产物品不同,消费者消费的物品也不同
  2. 整理思路,根据各个进程的操作流程确定PV操作大致顺序
    • 互斥操作要在在临界区前后分别PV,同步操作要前V后P
    • 互斥关系:对缓冲区(盘子)的访问要互斥进行
    • 同步关系:父亲将苹果放入盘子,女儿才可以取苹果
    • 同步关系:母亲将橘子放入盘子,儿子才可以取橘子
    • 同步关系:只有盘子为空时,父亲或母亲才能放入水果
  3. 设置信号量(互斥信号量一般为1,同步信号量初值取决于资源初始书目)

示例

代码语言:javascript复制
semaphore mutex=1; //实现互斥访问临界区(盘子)
semaphore apple=0; //盘子中有几个苹果
semaphore orange=0; //盘子中有几个橘子
semaphore plate=1; //盘子中还可以放几个水果

// 父亲进程
dad(){
    while(1){
        准备一个苹果;
        P(plate);  //等待一个盘子位置
        P(mutex);  //临界区上锁
        把苹果放入盘子;
        V(mutex); //临界区解锁
        V(apple); //释放苹果资源(苹果数加一,同时唤醒女儿进程执行)
    }
}

//母亲进程
mom(){
    while(1){
        准备一个橘子;
        P(plate);  //等待一个盘子位置
        P(mutex);  //临界区上锁
        把橘子放入盘子;
        V(mutex); //临界区解锁
        V(orange); //释放橘子资源(橘子数加一,同时唤醒儿子进程执行)
    }
}

//女儿进程
daughter(){
    while(1){
        P(apple); //等待苹果资源
        P(mutex); //临界区上锁
        从盘中取出苹果;
        V(mutex); //临界区解锁
        V(plate); //已经取出了苹果,所以释放盘子资源
        吃掉苹果;
    }
}

//儿子进程
son(){
    while(1){
        P(orange); //等待橘子资源
        P(mutex); //临界区上锁
        从盘中取出橘子;
        V(mutex); //临界区解锁
        V(plate); //已经取出了橘子,所以释放盘子资源
        吃掉橘子;
    }
}

0 人点赞