问题描述

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区取出一个产品并使用；缓冲区在同一时刻只能允许一个进程访问。

问题分析

• 生产者、消费者共享一个初始为空、大小为n的缓冲区，我们把缓冲区中未存放数据的一个块，当作一个“空位”；把其中按块存放的数据当作“产品”。
• 同步关系：生产者与消费者
  • 只有缓冲区有空位时，生产者才能把产品放入缓冲区
    • 生产者把“空位”当作资源，缓冲区初始为空，即空位数量为n（n：空的缓冲区大小）
      • 所以可以设置信号量empty，初始n
        • empty>0时，有空位，生产者可以消耗“空位”这种资源即P(empty)；
        • empty<=0时，生产者无“空位”资源可用，便会挂起到阻塞队列等待。
  • 只有缓冲区有产品时，消费者才能从缓冲区中取出产品
    • 消费者把“产品”当作资源，缓冲区初始为空，即产品数量为0
      • 所以可以设置信号量full，初始为0
        • full<=0，消费者无“产品”这种资源可用，便会挂起到阻塞队列
        • full>0，有产品，消费者可以消耗“产品”这种资源即P(full)
  • 进一步：
    • empty>0时，有空位，生产者可以消耗“空位”这种资源即P(empty)的同时：生产了“产品这种资源”，即V(full)；
    • full>0时，有产品，消费者可以消耗“产品”这种资源即P(full)的同时：生产了“空位”这种资源，即V(empty);
• 互斥关系：所有进程之间
  • 缓冲区是临界资源，各个进程必须互斥地访问
    • 设置信号零mutex，初始为1
      • 在进入区P(mutex)申请资源
      • 在退出区V(mutex)释放资源

设计

typedef struct{
    int value;	
    Struct process *L;	//等待序列
}semaphore;

semaphore full;
semaphore empty;
semaphore mutex;

//某进程需要使用资源时，通过wait原语申请:P操作
void wait(semaphore S){
    S.value--;
    if(S.value < 0){
        block(S.L);//阻塞原语，将当前进程挂载到当前semaphore的阻塞队列
    }
}
//进程使用完资源后，通过signal原语释放:V操作
void signal(semaphore S){
	S.value++;
    if(S.value <= 0){
        wakeup(S.L);//唤醒原语，将当前semaphore的阻塞队列中的第一个进程唤醒
    }
}
full.value=0;	//缓冲区 “产品”资源数（初始为0），用于实现生产者与消费者进程的同步
empty.value=n;	//缓冲区 “空位”资源数（初始为n），用于实现生产者与消费者进程的同步
mutex.value=1;	//互斥信号量，用于实现所有进程之间互斥地访问缓冲区
//生产者
producer(){
    while(1){
       	Produce();	//生产“产品”
        
        P(empty);	//“空位”数-1
        P(mutex);	//临界区上锁        
        Storage();	//摆放产品    
        V(mutex);	//临界区解锁
        V(full);	//“产品”数+1
    }
}
//消费者
consumer(){
    while(1){
        P(full);	//“产品”数-1 
        P(mutex);	//临界区上锁
		TakeOut();	//拿走产品
        V(mutex);	//临界区解锁
        V(empty);	//“空位”数+1
        
        Use();		//使用“产品”
    }
}

对于各个操作顺序的理解：

1. 对于一部分操作的顺序，我们很好理解，符合我们的认知：

   •  //生产者
      Produce();	//生产产品
      P(empty);	//“空位”数-1，可能有人在这里会问这个操作为什么不可以放在“Storage甚至是V(full)”后面，考虑一种情况：当空位数为0时，我们是不能摆放产品的，而这个操作正是在检查是否还有“空位”这种资源；所以它一定在Storage前面。
      Storage();	//摆放产品
      V(full);	//“产品”数+1，可能有人在这里会问这个操作为什么不可以放在“Storage甚至是P(empty)”前面，考虑一种情况：当产品数为n时，我们是不能再摆放产品的，因为缓冲区已满，再向其中添加数据（执行Storage）是要出问题的；所以它一定在Storage后面。
     

   •  //消费者
      P(full);	//“产品”数-1，同上面一样，可能有人在这里会问这个操作为什么不可以放在“TakeOut甚至是V(empty)”后面，考虑一种情况：当产品数为0时，我们是不能拿走产品的，而这个操作正是在检查是否还有“产品”这种资源；所以它一定在TakeOut前面。
      TakeOut();	//拿走产品
      V(empty);	//“空位”数+1，同上面一样，可能有人在这里会问这个操作为什么不可以放在“TakeOut甚至是P(full)”前面，考虑一种情况：当空位数为n时，我们是不能拿走产品的，因为缓冲区已经空了，再拿走（执行TakeOut）拿走个寂寞；所以它一定在TakeOut前面。
      Use();		//使用“产品”
     

2. 对于其他操作：实现同步的P操作一定要在实现互斥的P操作之前，为什么呢？

   • 反向分析：我们考虑若调换生产者上述两个P操作的顺序：

     //生产者
     producer(){
         while(1){
            	Produce();	//生产产品
             P(mutex);	//临界区上锁
             P(empty);	//“空位”数-1
             Storage();	//摆放产品
             V(mutex);	//临界区解锁
             V(full);	//“产品”数+1
         }
     }
     //消费者
     consumer(){
         while(1){
             P(full);	//“产品”数-1
             P(mutex);	//临界区上锁
     		TakeOut();	//拿走产品
             V(mutex);	//临界区解锁
             V(empty);	//“空位”数+1
             Use();		//使用“产品”
         }
     }
     

     • 若此时缓冲区已经放满产品，则empty=0，full=n
       • 生产者进程执行P(mutex)，mutex变为0，由于empty为0即没有“空位”了，需要生产者进程阻塞，等待消费者拿走产品
       • 切换至消费者进程，消费者进程执行到P(mutex)，由于mutex为0即生产者未释放临界资源，需要生产者释放临界资源，消费者进程阻塞
       • 互相等待，进入死锁
     • 结论：不要让因同步引起的进程阻塞（P操作可能产生结果）发生在为临界区上锁之后，因为：
       1. 临界区上锁，表示临界资源已被占用；若对临界区未解锁之前，发生了因同步引起的进程阻塞（上例中即需要生产者进程阻塞，等待消费者拿走产品）。
       2. 那么紧接着切换到另一个和此进程有同步和互斥关系的进程运行，且该进程也要对临界区访问：由于临界区已被上锁，则两进程进入死锁状态。

   • 说白了，对于进程来说，阻塞前对临界资源上锁，就是占着茅坑不拉屎（粗俗的讲：死锁就是两个人都占着茅坑不拉屎，还都等着对方离开然后在别人茅坑里才能拉）。

3. Produce和Use可以放在临界区吗？

   • 为了进程快速交替使用临界资源，要让临界区代码尽量短，所以不把生产和使用产品的代码放在临界区代码中

4. V操作不会使进程阻塞，故互斥和同步的V操作顺序从理论上来说可以调换，但同3一样，为了进程快速交替使用临界资源，要让临界区代码尽量短，所以不把同步的V操作放在临界区代码中

5. 综上：不要往临界区中添加与访问临界资源无关的操作/代码