| 【操作系统】生产者消费者问题讲解 | 您所在的位置：网站首页 › 生产者消费者模式的特点 › 【操作系统】生产者消费者问题讲解 |
【操作系统】生产者消费者问题讲解
|
生产者消费者问题是经典的进程同步问题，也是考试最常考的问题。 之前讲过了使用信号量机制实现进程控制，请确保已经掌握了相关知识：信号量机制实现进程控制 。 问题描述——生产者消费者问题系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者每次从缓冲区中取出一个产品并使用。生产者、消费者共享一个初始为空、大小为 n 的缓冲区。 分析： 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待；只有缓冲区不为空时，消费者才能从中取出产品，否则必须等待；缓冲区是临界资源，各进程必须互斥的访问；PV 操作题目分析步骤： 关系分析。找出题目中的各个进程，分析它们之间的同步、互斥关系； 在这个题目中，进程有生产者和消费者，由于共享一个缓冲区，所以是互斥的，同时我们上面分析的，两个 等待 ，很关键，一般只要看到等待，就说明有同步关系，这里有两个同步关系。 整理思路。根据各进程的操作流程确定 P、V 操作的大致顺序。 生产者每次要消耗（P）一个空闲缓冲区，并生产（V）一个产品；消费者每次要消耗（P）一个产品，并释放（V）一个空闲缓冲区。同时往缓冲区中放入取走产品需要互斥。 设置信号量。设置需要的信号量，并根据题目条件确定信号量初始值。（互斥信号量一般为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 操作实现上述过程。
分析： 可以将盘子看作是缓冲区，它的容量是1，所以是互斥信号量；同步关系： 父亲将苹果放入盘子后，女儿才可以取苹果，否则必须等待；母亲将橘子放入盘子后，儿子才可以取橘子，否则必须等待；只有盘子为空时，父亲或母亲才能放入水果，否则必须等待。 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); } |
【本文地址】