经典进程同步问题-生产者消费者问题

一、生产者-消费者问题

生产者-消费者问题是一个著名的进程同步问题。
它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。

用一个数组来表示上述的具有n个（0,1,...,n-1）缓冲区的缓冲池；
用输入指针in来指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针加1；
用一个输出指针out来知识下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针就加1；

注意，由于这里的缓冲池是组织成循环缓冲的（就是数据结构中的循环队列），故应把输入指针加1表示成in:=(in+1)mod n；
输出指针加1表示成out:=(out+1)mod n。
当(in+1)mod n=out时表示缓冲池满；而in=out则表示缓冲池空。

此外，还引入了一个整型变量counter，其初始值为0。每当生产者进程向缓冲池中投放一个产品后，count+1;反之，每当消费者进程虫中取走一个产品时，使counter-1.

1.利用记录型信号量解决生产者-消费者问题
假定在生产者和消费者之间的公用缓冲池中，具有n个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥利用。利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。
伪码描述如下：
Var mutex,empty,full:semaphore:=1,n,0;
buffer:array[0,...,n-1] of item;
in,out:integer:=0,0;
begin
 parbegin
  producer: begin
   repeat
   produce an item nextp;
   wait(empty); //分配空缓冲区，如果没有缓冲区可分配，则阻塞生产者进程
   wait(mutex);  //互斥信号量，初始值为1，如果mutex小于0，则无可分配资源，阻塞当前进程
   buffer(in):=nextp;  //缓冲区，nextp暂存当前生产的产品
   in:=(in+1)mod n;  //因为是缓冲区是循环队列，所以in指针进行取模运算来判断队列是否已满
   signal(mutex);  //释放临界资源，并唤醒请求资源的阻塞进程
   signal(full);   //唤醒因wait(full)而阻塞的进程
   until false;
end

  consumer:begin
   repeat
   wait(full); //可分配的有产品的缓冲区数量，如果没有缓冲区可分配，则阻塞消费者进程
   wait(mutex); //互斥信号量，初始值为1，如果mutex小于0，则无可分配资源，阻塞当前进程
   nextc:=buffer(out); //缓冲区，nextc暂存当前要消费的产品
   out:=(out+1)mod n;  //因为是缓冲区是循环队列，所以out指针进行取模运算
   signal(mutex);  //释放临界资源，并唤醒请求资源的阻塞进程
   signal(empty);  //唤醒因wait(empty)而阻塞的进程
   consumer the item in nextc;
   until false;
   end
  parend
end
            
2.利用AND信号量解决生产者-消费者问题

对于生产者-消费者问题，也可利用AND信号量来解决，即用Swait(empty,mutex)来代替wait(empty)和wait(mutex);用Ssignal(empty,mutex)来代替signal(mutex)和signal(full);用Swait(full,mutex)来代替wait(full)和wait(mutex),以及用Ssignal(mutex,empty)代替Signal(mutex)和Signal(empty)。利用AND信号量来解决生产者-消费者的算法描述如下：
 Var mutex,empty,full:semaphore:=1,n,0;
buffer:array[0,...,n-1] of item;
in,out:integer:=0,0;
begin
 parbegin
  producer: begin
   repeat
   produce an item nextp;
   Swait(empty,mutex); //当empty小于等于0，也就是没有空缓冲区时，或者信号量小于0，则阻塞当前进程
   buffer(in):=nextp;  //缓冲区，nextp暂存当前生产的产品
   in:=(in+1)mod n;  //因为是缓冲区是循环队列，所以in指针进行取模运算来判断队列是否已满
   Ssignal(mutex,full);  //唤醒等待队列中因wait(mutex,full)阻塞的进程
   until false;
end

  consumer:begin
   repeat
   Swait(full,mutex);   //如果缓冲区中没有产品可分配，或者信号量小于0，则阻塞当前进程
   nextc:=buffer(out); //缓冲区，nextc暂存当前要消费的产品
   out:=(out+1)mod n;  //因为是缓冲区是循环队列，所以out指针进行取模运算
   Ssignal(mutex,empty);
   consumer the item in nextc;
   until false;
   end
   
  parend
end

3.利用管程解决生产者-消费者问题
在利用管程方法来解决生产者-消费者问题时，首先便是为它们建立一个管程，并命名为ProclucerConsumer，或简称PC。其中包括两个过程：
（1）put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中已有的产品数目，当count>=n时，表示缓冲池已满，生产者须等待。
（2）get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当count<=0时，表示缓冲池中已无可取用的产品，消费者应等待。
PC管程可描述如下：
type producer-consumer=monitor
 Var in,out,count:integer;
  buffer:array[0,...,n-1] of item;
  notfull,notempty:condition;  //定义条件变量notfull，notempty
  procedure entry put(item)
     begin
       if count>=n then notfull.wait;  //如果缓冲池已满，则阻塞生产者进程
         buffer(in):=nextp;
         in:=(in+1) mod n;
         count:=count+1;
         if notempty.queue then notempty.signal;  //如果消费者等待队列中有等待的进程，唤醒进程
     end
  procedure entry get(item)
     begin
       if count<=0 then notempty.wait; //如果缓冲池中没有产品，则阻塞消费者进程
       nextc:=buffer(out);
       out:=(out+1)mod n;
       count:=count-1;
       if notfull.queue then notfull.signal;
     end
  begin in:=out:=0;
  count:=0
end

在利用管程解决生产者-消费者问题时，其中的生产者和消费者可描述为：
producer:
 begin
 repeat
   produce an item in nextp;
   PC.put(item);
 until false;
 end  

consumer:
 begin
 repeat
   PC.get(item);
   consume the item in nextc;
 until false;
 end