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

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

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

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

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

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

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

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

根据以上描述,可以得出如下结论:

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

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

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

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

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

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

有限缓冲问题

问题分析

该问题需要注意的几点:

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

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

资源可以使用

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

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

等待使用资源

通用实现

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

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

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

生产者(producer)消费者(consumer)进程结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
producer(){
while(1){
生成一个产品;
P(empty); //消耗一个空闲缓冲区
P(mutex);
把产品放入缓冲区;
V(mutex);
V(full) //增加一个产品
}
}
consumer(){
while(1){
P(full); //消耗一个产品
P(mutex);
从缓冲区取出一个产品;
V(mutex);
V(empty); //增加一个空闲缓冲区
使用产品;
}
}

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

生产者消费者进程结构

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

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

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

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

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

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

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

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

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

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

小结

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

-------------本文结束 感谢阅读-------------