操作系统基础15-生产者消费者问题

2020-11-11 11:37·重学IT的老猫

在上一篇操作系统基础14提到通过信号量解决生产者消费者问题。本篇来详细说说操作系统中的经典问题-生成者消费者问题

生产者消费者问题 (Producer-consumer problem)

该问题是一个著名的同步问题。通俗的描述是：一群生产者进程正在生产产品，并将这些产品提供给消费者进程去消费。为使生产者和消费者能够并发执行。在两者之间设置了一个公共区域，生产者进入公共区域生产产品并放入其中。消费者进入公共区域并取走产品进行消费。

当一个生产者进入公共区域生产产品时，其他生产者和消费者不能同时进入公共区域生产产品或消费产品。当一个消费者进入公共区域消费产品的时候，其它消费者和生产者不能同时进入该区域消费产品或生产产品。也就是说，任意时刻，最多只允许一个生产者或一个消费者进入公共区域。即生产者和消费者必须互斥的访问公共区域。

当产品放满公共区域时，生产者必须等待，使消费者先消费。当公共区域为空时，消费者必须等待，使生产者先生产。即在公共区域为空或为满时，生产者或消费者在执行时要满足一定的先后顺序。即生产者与消费者对公共区域的访问必须同步。

根据以上描述，可以得出如下结论：

（1）生产者与生产者之间存在竞争即互斥关系

（2）消费者与消费者之间存在竞争即互斥关系

（3）生产者与消费者之间存在互斥与同步关系

以上三个结论可以概括为：三种关系，两种角色，一个临界区。即**“三二一”**规则

生产者消费者问题也称有限缓冲问题（Bounded-buffer problem），从多线程同步来看，该问题描述了共享固定大小缓冲区的两个线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。 . 要解决该问题，就必须让生产者在缓冲区满时休眠（要么干脆就放弃数据），等到下次消费者消耗缓冲区中的数据的时候，生产者才能被唤醒，开始往缓冲区添加数据。同样，也可以让消费者在缓冲区空时进入休眠，等到生产者往缓冲区添加数据之后，再唤醒消费者。通常采用进程间通信的方法解决该问题。缓冲区是临界资源，必须互斥的访问，所以如果解决方法不够完善，则容易出现死锁的情况。出现死锁时，两个线程都会陷入休眠，等待对方唤醒自己。该问题也能被推广到多个生产者和消费者的情形。

有限缓冲问题

问题分析

该问题需要注意的几点：

在缓冲区为空时，消费者不能再进行消费
在缓冲区为满时，生产者不能再进行生产
在一个线程进行生产或消费时，其余线程不能再进行生产或消费等操作，即保持线程间的同步
注意条件变量与互斥锁的顺序

资源可以使用

由于前两点原因，因此需要保持线程间的同步，即一个线程消费（或生产）完，其他线程才能进行竞争CPU，获得消费（或生产）的机会。对于这一点，可以使用条件变量进行线程间的同步：生产者线程在product之前，需要wait直至获取自己所需的信号量之后，才会进行product的操作；同样，对于消费者线程，在consume之前需要wait直到没有线程在访问共享资源（缓冲区），再进行consume的操作，之后再解锁并唤醒其他可用阻塞线程。

等待使用资源

通用实现

也就是上一篇中的通过信号量机制（P、V操作）解决

生产者和消费者进程共享以下数据结构：

int n;                   //缓冲池有n个缓冲区，每个缓冲区可存一个数据项
semaphore  mutex = 1;    //信号量 mutex 提供缓冲池访问的互斥要求，并初始化为1
semaphone  empty = n;    //信号量 empty 表示空的缓冲区数量
semaphone  full = 0      //信号量 full 表示满的缓冲区数量

**生产者(producer)和消费者(consumer)**进程结构：

producer(){
    while(1){
      生成一个产品;
      P(empty); //消耗一个空闲缓冲区
      P(mutex);
      把产品放入缓冲区;
      V(mutex);
      V(full)   //增加一个产品
    }
}
consumer(){
    while(1){
      P(full);   //消耗一个产品
      P(mutex);
      从缓冲区取出一个产品;
      V(mutex);
      V(empty);  //增加一个空闲缓冲区
      使用产品;
    }
}

生产者消费者进程结构

互斥的实现是在同一个进程中进行的一对PV操作。

同步的实现是在两个进程中进行的，在一个进程中执行P操作，在另一个进程中执行V操作。

能否改变P、V操作的顺序

若此时缓冲区内已经放满产品，则 empty = 0，full = 0

则生产者进程执行① 使mutex变为0，再执行②，由于已没有空闲缓冲区，因此生产者被阻塞。由于生产者被阻塞，因此切换回消费者进程。消费者进程执行③，由于mutex为0，即生产者还没释放对临界资源的“锁”，因此消费者也被阻塞。这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”。

同样的，如何缓冲区中没有产品，即 empty = n，full = 0

按③④①的顺序执行也会发生死锁。

因此，实现互斥的P操作一定要在实现同步的P操作之后。V操作不会导致进程阻塞，因此两个V操作顺序可以交换。

小结

生成者和消费者问题是一个互斥、同步的综合问题。隐含着两对同步关系。有时候是消费者需要等待生产者生成，有时候是生成者等待消费者消费，这是两个不同的“一前一后问题”，因此也需要设置两个同步信号量。