进程的同步与互斥之生产者消费者问题:对信号量设置的理解及PV操作顺序分析

问题描述

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

问题分析

  • 生产者、消费者共享一个初始为空、大小为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)释放资源

进程的同步与互斥之生产者消费者问题:对信号量设置的理解及PV操作顺序分析

设计

进程的同步与互斥之生产者消费者问题:对信号量设置的理解及PV操作顺序分析

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. 综上:不要往临界区中添加与访问临界资源无关的操作/代码进程的同步与互斥之生产者消费者问题:对信号量设置的理解及PV操作顺序分析

上一篇:操作系统:生产者-消费者问题


下一篇:CS194 Full Stack Deep Learning(4) Machine Learning Teams