【操作系统】生产者消费者问题讲解

一时失言乱红尘 2022-12-23 03:58 184阅读 0赞

生产者消费者问题是经典的进程同步问题，也是考试最常考的问题。

之前讲过了使用信号量机制实现进程控制，请确保已经掌握了相关知识：[信号量机制实现进程控制][Link 1] 。

## 问题描述——生产者消费者问题 ##

> 系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者每次从缓冲区中取出一个产品并使用。生产者、消费者共享一个初始为空、大小为 `n` 的缓冲区。

--------------------

分析：

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

PV 操作题目分析步骤：

1.  关系分析。找出题目中的各个进程，分析它们之间的同步、互斥关系；
    
    在这个题目中，进程有生产者和消费者，由于共享一个缓冲区，所以是互斥的，同时我们上面分析的，两个 `等待` ，很关键，一般只要看到等待，就说明有同步关系，这里有两个同步关系。
2.  整理思路。根据各进程的操作流程确定 P、V 操作的大致顺序。
    
    生产者每次要消耗（P）一个空闲缓冲区，并生产（V）一个产品；消费者每次要消耗（P）一个产品，并释放（V）一个空闲缓冲区。同时往缓冲区中放入取走产品需要互斥。
3.  设置信号量。设置需要的信号量，并根据题目条件确定信号量初始值。（互斥信号量一般为1，同步信号量的初始值要看对应资源的初始值是多少）
    
    所以在这一题当中，我们设置的信号量如下：
    
        semaphore mutex = 1;	//互斥信号量,实现对缓冲区的互斥访问;
        semaphore empty = n;	//同步信号量,表示空闲缓冲区的数量;
        semaphore full = 0;		//同步信号量,表示产品的数量,也即非空缓冲区的数量.

综上所述，本题的代码如下：

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);//增加一个空闲缓冲区
    		使用产品;
    	}
    }

观察上面的代码可以发现，如果我们要实现的是互斥操作，是在同一进程中进行的 `PV` 操作；如果实现的同步操作，是在其中一个进程中执行 `P`，另一个中执行 `V`。

## 问题扩展——多生产者多消费者问题 ##

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center][]

分析：

*  可以将盘子看作是缓冲区，它的容量是1，所以是互斥信号量；
 *  同步关系：
    
    1.  父亲将苹果放入盘子后，女儿才可以取苹果，否则必须等待；
    2.  母亲将橘子放入盘子后，儿子才可以取橘子，否则必须等待；
    3.  只有盘子为空时，父亲或母亲才能放入水果，否则必须等待。

semaphore mutex = 1;	//实现互斥访问盘子
    semaphore apple = 0;	//盘子中有几个苹果
    semaphore orange = 0;	//盘子中有几个橘子
    semaphore plate = 1;	//盘子中还能放几个苹果

互斥：在临界区前后分别 PV
    同步：前V后P

完整代码如下：

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);
    		吃掉橘子;
    	}
    }

## 练习题 ##

下面有两道练习题，就算你上面的没听懂，做完下面两道题目也能总结出规律了，所以一定要认真做。

**例一**：某工厂有两个生产车间和一个装配车间，两个生产车间分别生产 A、B 两种零件，装配车间的任务是把 A、B 两种零件组装成产品。两个生产车间每生产一个零件后，都要分别把它们送到装配车间的货架 F1、F2上。F1 存放零件 A，F2 存放零件 B，F1 和 F2 的容量均可存放 10 个零件。装配工人每次从货架上取一个零件 A 和 一个零件 B 后组装成产品。请用 P、V 操作进行正确管理。

--------------------

> 请先自己作答，再查看解析

分析：

*  车间 A 和装配车间共享 货架F1，所以 F1 是临界资源；
 *  车间 B 和装配车间共享 货架F2，所以 F2 是临界资源；
 *  其余逻辑和生产者消费者模型一样。

完整代码如下：

semaphore empty1 = 10;	//货架 F1 上的空余空间
    semaphore empty2 = 10;	//货架 F2 上的空余空间
    semaphore full1 = 0;	//货架 F1 上的 A 产品
    semaphore full2 = 0;	//货架 F2 上的 B 产品
    semaphore mutex1 = 1;	//互斥的访问 F1
    semaphore mutex2 = 1;	//互斥的访问 F2
    
    A车间() { 
    	while(1){ 
    		生产一个产品A;
    		P(empty1);	//判断货架 F1 是否为空
    		P(mutex1);	//互斥访问货架 F1
    		将产品 A 存放到货架 F1 上;
    		V(mutex1);	//释放货架 F1
    		V(full1);	//货架 F1 上的零件 A 的个数加 1
    	}
    }
    
    A车间() { 
    	while(1){ 
    		生产一个产品B;
    		P(empty2);	//判断货架 F2 是否为空
    		P(mutex2);	//互斥访问货架 F2
    		将产品 B 存放到货架 F2 上;
    		V(mutex2);	//释放货架 F2
    		V(full2);	//货架 F2 上的零件 B 的个数加 1
    	}
    }
    
    装配车间(){ 
    	while(1){ 
    		P(full1);	//判断货架 F1 上是否有产品 A;
    		P(mutex1);	//互斥访问货架 F1;
    		从货架 F1 上取一个 A 产品;
    		V(mutex1);	//释放货架 F1
    		V(empty1);	//货架 F1 上的空闲空间数加1
    		P(full2);	//判断货架 F2 上是否有产品 B
    		P(mutex2);	//互斥访问货架 F2
    		从货架 F2 上取一个 B 产品;
    		V(mutex2);	//释放货架 F2
    		V(empty2);	//货架 F2 上的空闲空间数加1
    		将取得的 A 产品和 B 产品组装成产品;
    	}
    }

**例二**：某寺庙有小和尚、老和尚若干，有一水缸，由小和尚提水入缸供老和尚引用。水缸可容 10 桶水，水桶自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为 3 个。每次入缸取水仅为 1 桶水，且不可同时进行。试给出有关从缸取水、入水的算法描述。

--------------------

> 请先自己作答，再查看解析

分析：

*  从井中取水并放入水缸课视为一个进程，从缸中取水可视为另一个进程；
 *  设水井和水缸为临界资源，引入 well 和 vat；
 *  只有 3 个水桶可以使用，所以设置一个信号量 pail ，表示目前可用的水桶数量；
 *  水缸满时不能再放水，所以设置 empty 信号量控制入水；
 *  水缸空是不能取水，所以设置 full 信号量控制取水。

代码如下：

semaphore well = 1;		//用于互斥地访问水井;
    semaphore vat = 1;		//用于互斥的访问水缸;
    semaphore empty = 10;	//用于表示水缸中剩余空间;
    semaphore full = 0;		//表示水缸中水的桶数;
    semaphore pail = 3;		//表示有多少个水桶可以用,初始值为3;
    
    // 老和尚
    while(1){ 
    	P(full);
    	P(pail);	
    	P(vat);
    	从水缸中打一桶水;
    	V(vat);
    	V(empty);
    	喝水;
    	V(pail);
    }
    
    // 小和尚
    while(1){ 
    	P(empty);
    	P(pail);
    	P(well);
    	从井中打一桶水;
    	V(well);
    	P(vat);
    	将水倒入水缸中;
    	V(vat);
    	V(full);
    	V(pail);
    }

[Link 1]: https://blog.csdn.net/weixin_43941364/article/details/109864926
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/cb1bfea08a8244edb0ff015028728342.png