生产者--消费者题型(共9页).doc

精选优质文档-倾情为你奉上三、生产者消费者题型 生产者-消费者题型在各类考试（考研、程序员证书、程序员面试笔试、期末考试）很常见，原因之一是生产者-消费者题型在实际的并发程序（多进程、多线程）设计中很常见；之二是这种题型综合性较好，涉及进程合作、互斥，有时还涉及死锁的避免。生产者-消费者题型可以全面考核你对并发程序的理解和设计能力。生产者-消费者题型最基本的是有界缓冲区的生产者-消费者问题和无界缓冲区的生产者-消费者问题，对这两个问题的解我们应该背下来，就像我们念高中时背一些题型一样。1 有界缓冲区生产者-消费者问题的解前面的课程已多次讲过。假设缓冲区是无界的，试用信号灯 与 PV 操作给出解法。 答：由于是无界缓冲区，所以生产者不会因得不到缓冲区而被阻塞。所以只需在前面的有界缓冲区解中去掉信号量empty及有关的PV操作即可。2. 设有一个可以装A,B两种物品的仓库，其容量无限大，但要求仓库中A,B两种物品的数量满足下述不等式：-MA物品的数量-B物品的数量N，其中M和N为正整数。试用信号灯和PV操作描述A, B两种物品的入库过程。（这是北大1991年研究生入学试题，原题不允许使用条件表达式，解法1虽正确，但不符合原题要求）解1：不等式 -MA物品的数量-B物品的数量N 意味着：A物品的数量-B物品的数量NB物品的数量-A物品的数量M为防止缓冲区存入物品可能发生共享变量错误，A、B入库时需要互斥。解法1ItemType *buffer; /仓库空间semaphore mutex=1; int countA=0, countB=0; /A，B物品初值void putA while(1) P(mutex);if (countA - countB)<N *buffer=A; /A入库buffer+; countA+; V(mutex); void putB while(1) P(mutex);if (countB - countA)<M *buffer=B; /B入库buffer+; countB+;V(mutex); 解法1借助条件表达式，用简单的互斥解题，与生产者-消费者题型毫无关系。解法2：不使用条件表达式的解法。对于下面表达式A物品的数量-B物品的数量NB物品的数量-A物品的数量M可以这样理解：（1）若只放A而不放B，则A最多放N次便被阻塞，即假定有一个初值为N的信号量S1，A进程每操作一次就相当将信号量S1减1。当S<0时，A不能再放，此时每放入一个B（相当于B消费了一件产品），可令S1的信号量加1，此时A有再放的机会。此时A是生产者B是消费者。（2）对B同理。即假定有一个初值为M的信号量S2。此时B是生产者A是消费者。 用这种解题思路，这道题就可归类于生产者-消费者问题。下面我们用思路（1）解这道题。可以认为有一个有界缓冲区，大小为abs(N-M)，A是生产者，缓冲区下界是M，其信号量S1=MB是消费者，缓冲区上界是N，其信号量S2=N下面是生产者进程AItemType *buffer; semaphore s1=N, s2=M, mutex=1; void putA while(1) P(s1) /生产一件AP(mutex); *buffer=A; buffer+; V(mutex); V(s2) /通知B进程下面是消费者进程Bvoid putB while(1) P(s2) /生产一件BP(mutex); *buffer=B; buffer+; V(mutex); V(s1) /通知A进程对这道题，我是从生产者-消费者题型来理解的，同学们可能有不同思路。这道题的解与生产者-消费者标准解法的差别在于信号量初值的设定上。后面这个解，把信号量mutex和buffer+去掉也可以，因为这个题只要主要考点不在于互斥。3. 设自行车生产线上有一只箱子，其中有 N 个位置 ( N 3)，每个位置可存放一个车架或一个车轮; 又设有三个工人，其活动分别为: 工人 1活动： do 加工一个车架 ; 车架放入箱中 ; while (1) 工人 2活动： do 加工一个车轮 ; 车轮放入箱中 ; while (1) 工人 3活动： do 箱中取一个车架 ; 箱中取二个车轮 ; 组装为一台车 ; while (1) 试分别用信号灯与 PV 操作实现三个工人的合作，要求解中不含死锁。 这是三进程同步问题，属于生产者-消费者题型。首先不考虑死锁问题，显然工人 1与工人3、工人2与工人3构成生产者与消费者关系，这两对生产/消费关系通过共同的缓冲区相联系。从资源的角度来看，箱子中的空位置相当于工人1和工人2的资源，而车架和车轮相当于工人3的资源。定义三个信号灯如下： semaphore empty=N; semaphore wheel=0;semaphore frame=0;三位工人的活动分别为： 工人 1活动： do 加工一个车架 ; P(empty); 车架放入箱中 ; V(frame); while (1) 工人 2活动： do 加工一个车轮 ; P(empty); 车轮放入箱中 ; V(wheel); while (1) 工人 3活动： do P(frame); 箱中取一车架 ; V(empty); P(wheel); P(wheel); 箱中取二车轮 ; V(empty); V(empty); 组装为一台车 ; while (1) 分析上述解法易见，当工人 1推进速度较快时，箱中空位置可能完全被车架占满或只留有一个存放车轮的位置，而当此时工人3同时取2个车轮时将无法得到，而工人2又无法将新加工的车轮放入箱中；当工人2推进速度较快时，箱中空位置可能完全被车轮占满，而当此时工人3取车架时将无法得到，而工人1又无法将新加工的车架放入箱中。上述两种情况都意味着死锁，请比较死锁的四个必要条件。 为防止死锁的发生，箱中车架的数量不可超过 N-2，车轮的数量不可超过N-1，这些限制可以用两个信号灯来表达。 semaphore s1=N-2;/至少要给车轮留两个空位 semaphore s2=N-1;/至少要给车架留一个空位如此，对前面的解做补充，可以给出不含死锁的完整解法如下： 工人 1活动： do 加工一个车架 ; P(s1); P(empty); 车架放入箱中 ; V(frame); while (1) 工人 2活动： do 加工一个车轮 ; P(s2); P(empty); 车轮放入箱中 ; V(wheel); while (1) 工人 3活动： do P(frame); 箱中取一车架 ; V(empty); V(s1);P(wheel); P(wheel); 箱中取二车轮 ; V(empty); V(empty); V(s2); V(s2); 组装为一台车 ; while (1) 这个答案不算完善（但较容易理解），现有的信号量还有简化的余地。 4. 某寺庙，有小和尚、老和尚若干庙内有一水缸，由小和尚提水入缸，供老和尚饮用水缸可容纳 30 桶水，每次入水、取水仅为1桶，不可同时进行。水取自同一井中，水井径窄，每次只能容纳一个水桶取水。设水桶个数为5个，试用信号灯和 PV 操作给出老和尚和小和尚的活动。（这是北邮98年的考研题） 题意分析：显而易见这道题是生产者-消费者问题的变种，但它比较复杂，我们用“各个击破”的方法解这道题。我们能很容易地发现一个缓冲区：水缸（大小为30），小和尚们是生产者（用桶提水入缸，每次仅限一桶，要互斥），老和尚们是消费者（用桶从缸中取水，每次仅限一桶，要互斥）。照抄有界缓冲区生产者-消费者问题的解，如下：semaphore empty=30; / 表示缸中目前还能装多少桶水，初始时能装 30 桶水 semaphore full=0; / 表示缸中有多少桶水，初始时缸中没有水semaphore mutex_bigjar=1; / 用于实现对缸的互斥操作young_monk() while(1) P(empty); P(mutex_bigjar); pure the water into the big jar; V(mutex_bigjar); V(full); old_monk() while() P(full); P(mutex_bigjar); get water from big jar; V(mutex_bigjar); V(empty); 下面考虑水井，水井是无界缓冲区（产品（水）总是满的，不用考虑产品（水）为空），而且只有小和尚们是消费者而无生产者，只需考虑小和尚们从水井取水时互斥就行了。semaphore empty=30; / 表示缸中目前还能装多少桶水，初始时能装 30 桶水 semaphore full=0; / 表示缸中有多少桶水，初始时缸中没有水semaphore mutex_bigjar=1; / 用于实现对缸的互斥操作semaphore mutex_well=1; / 用于实现对井的互斥操作young_monk() while(1) P(empty); /缸里有空位P(mutex_well);/才能取水get water from well; V(mutex_well); P(mutex_bigjar); pure the water into the big jar; V(mutex_bigjar); V(full); old_monk() while() P(full); P(mutex_bigjar); get water from big jar; V(mutex_bigjar); V(empty); 下面考虑5只水桶，我们把它简单的看成5个共享资源就可以了，设一初值为5的信号量，和尚们（无论老小）要使用桶，就用信号量P操作申请一个，用完后用V操作释放，我们以前讲过，信号量可以用于资源的申请-释放。semaphore empty=30; / 表示缸中目前还能装多少桶水，初始时能装 30 桶水 semaphore full=0; / 表示缸中有多少桶水，初始时缸中没有水semaphore mutex_bigjar=1; / 用于实现对缸的互斥操作semaphore mutex_well=1; / 用于实现对井的互斥操作semaphore buckets=5; / 表示有多少只空桶可用，初始时有 5 只桶可用young_monk() while(1) P(empty); /缸里有空位P(buckets); /且有空桶可用 P(mutex_well);/才能取水get water from well; V(mutex_well); P(mutex_bigjar); pure the water into the big jar; V(mutex_bigjar); V(buckets); /用完桶后释放 V(full); old_monk() while() P(full); /缸里有水P(buckets); /且有空桶可用P(mutex_bigjar); /才能取水get water from big jar; V(mutex_bigjar); V(buckets);/用完桶后释放V(empty); 加上桶的处理后，意味着小和尚们最多可占用5只桶排队从井里取水或向缸里倒水，老和尚们最多可占用5只桶排队从缸里取水。用5个桶可以增加系统并发性。这道题的解只能说基本正确，即不能说是最佳的，也不是没有遗漏的。专心-专注-专业