进程同步的几个经典题目-生产者消费者-哲学家进餐-读者写者

1. 生产者消费者

    生产者线程生产物品，然后将物品放置在一个空缓冲区*消费者线程消费。消费者线程从缓冲区中获得物品，然后释放缓冲区。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来。

 
  // 
   假设缓冲队列长度为n 
  
 
  semaphore produce_count  
  = 
   n;
semaphore consume_count  
  = 
    
  0 
  ;
semaphore buffer_mutex  
  = 
    
  1 
  ;
Producer() {
   
  while 
  ( 
  true 
  ) {
    生产一个产品
    P(produce_count);    
    P(buffer_mutex);
    将产品放入缓冲区
    V(buffer_mutex);
    V(consume_count);
  }  
}
Consumer() {
   
  while 
  ( 
  true 
  ) {
    P(consume_count);
    P(buffer_mutex);
    从缓冲区中取出一个产品
    V(buffer_mutex);
    V(produce_count);
    消费这个产品
  }
} 
 

2. 哲学家进餐

    假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。哲学家从来不交谈，这就很危险，可能产生死锁，每个哲学家都拿着左手的餐叉，永远都在等右边的餐叉（或者相反）。
    参考中的一篇文章，给出了四种实现方式的说明，相对很全了。这里说明的方法其文中有说明，我给出进一步说明：当该哲学家左边和右边都有餐叉可以使用时，才使用两个餐叉。文中的方法是使用信号量，使得拿起左右两个叉子成为一个原子操作，即1起互斥作用的信号量，和5个叉子的信号量，我这里给出的一个实现是每次检查左右叉子是否可以拿起，如果可以拿起两个，使用1个起互斥作用的信号量，和5个int。   

 
  semaphore fork_mutex  
  = 
    
  1 
  ;
 
  int 
   fork_count[ 
  5 
  ]  
  = 
   { 
  1 
  , 
  1 
  , 
  1 
  , 
  1 
  , 
  1 
  };

 
  void 
   have_dinner( 
  int 
   id) {  
  // 
   哲学家ID号0-4 
  
 
     
  while 
  ( 
  true 
  ) {
    P(fork_mutex);
     
  if 
  ( 
  1 
    
  == 
   fork_count[id]  
  && 
    
  1 
    
  == 
   fork_count[(id 
  + 
  1 
  ) 
  % 
  4 
  ]) {
      fork_count[id]  
  = 
   0 
  ; // 拿起左边的餐叉
      fork_count[(id 
  + 
  1 
  ) 
  % 
  4 
  ]  
  = 
   0 
  ; // 拿起右边的餐叉
    }
    V(fork_mutex);
    使用左边右边的餐叉吃东西
    P(fork_mutex);
    fork_count[id]  
  = 
   1 
  ; // 放下左边的餐叉 
    fork_count[(id 
  + 
  1 
  ) 
  % 
  4 
  ]  
  = 
   1 
  ; // 放下右边的餐叉 
    V(fork_mutex);
    思考一会玩CS还是dota好
  }
} 
 

3. 读者写者

    细分起来有三种情况，读者优先（默认情况），弱写者优先（实际上，可理解为读者与写者公平），强写者优先。详细情况可见参考中的文中。现在我对这个问题还不是很熟悉，这里主要给出读者优先的实现。
    读者优先的要求如下：可以有多个读者同时工作，不能既有读者和写者通过工作，不能有多个写者同时工作。
    可以看出，只要当前有一个以上的读者在工作，那么后面再来的读者与写者，写者肯定被挂起，但是读者却可以工作，所以是读者优先。

 
  semaphore read_mutex  
  = 
    
  1 
  ;
 
  int 
   read_count  
  = 
    
  0 
  ;
semaphore write_mutex  
  = 
    
  1 
  ;

 
  void 
   reader() {
   
  while 
  ( 
  true 
  ) {
    P(read_mutex);
     
  if 
  ( 
  0 
    
  == 
   read_count) { // 只有当前没有读者在工作时，申请的读者才和申请的写者公平比较
　　　P(write_mutex)      
    }
    read_count 
  ++ 
  ;
    V(read_mutex);
    读文件
    P(read_mutex);
    read_count 
  -- 
  ;
     
  if 
  ( 
  0 
    
  == 
   read_count)
      V(write_mutex);
    V(read_mutex);
  }
}
 
  void 
   writer() {
   
  while 
  ( 
  true 
  ) {
    P(write_mutex);
    写文件
    V(write_mutex);
  }
} 
 

5. 参考

    哲学家就餐问题    http://zh.wikipedia.org/wiki/%E5%93%B2%E5%AD%A6%E5%AE%B6%E5%B0%B1%E9%A4%90%E9%97%AE%E9%A2%98
    操作系统并发和互斥：哲学家进餐问题    http://www.tangblog.info/2010/03/24/philosopher-eating-problem-operting-system.html
    读者写者问题解答    http://wenku.baidu.com/view/67626efafab069dc50220109.html