信号量与生产者消费者问题

Bertha 。 2022-07-11 07:36 188阅读 0赞

# 生产者—消费者问题 #

生产者—消费者题型在各类考试（考研、程序员证书、程序员面试笔试、期末考试）很常见，原因之一是生产者—消费者题型在实际的并发程序（多进程、多线程）设计中很常见；之二是这种题型综合性较好，涉及进程合作、互斥，有时还涉及死锁的避免。生产者—消费者题型可以全面考核你对并发程序的理解和设计能力。

生产者—消费者题型最基本的是**有界缓冲区的生产者消费者问题和无界缓冲区的生产者消费者问题**，对这两个问题的解我们应该掌握其解决方案。

对于有界缓冲区的生产者—消费者问题，两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者，将信息放入缓冲区；另一个是消费者，从缓冲区中取出信息（也可以把这个问题一般化为m个生产者和n个消费者问题，但是我们只讨论一个生产者和一个消费者的情况，这样可以简化解决方案）。

![20170119150635987][]

问题在于当缓冲区已满，而此时生产者还想向其中放入一个新的数据项的情况，其解决办法是让生产者睡眠，待消费者从缓冲区中取出一个或多个数据项时再唤醒它。同样地，当消费者试图从缓冲区取数据而发现缓冲区为空时，消费者就睡眠，直到生产者向其中放入一些数据时再将其唤醒。

这个方法听起来很简单，为了跟踪缓冲区中的数据项数，我们需要一个变量count。如果缓冲区最多存放N个数据项，则生产者代码将首先检查count是否达到N，若是，则生产者睡眠，否则生产者向缓冲区最多存放N个数据项，则生产者代码将首先检查count是否达到N，若是，则生产者睡眠；否则生产者向缓冲区放入一个数据项并增量count的值。

消费者的代码与此类似：首先测试count是否为0，若是，则睡眠；否则从中取出一个数据项并递减count的值。每个进程同时也检测另一个进程是否应该被唤醒，若是则唤醒之。生产者消费者的代码如下：

#define N 100
    int count = 0;
    void producer(void)
    {
    	int item;
    	while(TRUE)
    	{
    		item = produce_item();
    		if(count == N)					//如果缓冲区满就休眠
    		sleep();
    		insert_item(item);
    		count = count + 1;				//缓冲区数据项计数加1
    		if(count == 1)
    		wakeup(consumer);
    	}
    }
    
    void consumer(void)
    {
    	int item;
    	while(TRUE)
    	{
    		if(count == 0)				//如果缓冲区空就休眠
    			sleep();
    		item = remove_item();
    		count = count - 1;			//缓冲区数据项计数减1
    		if(count == N - 1)
    			wakeup(producer);
    		consume_item(item);
    	}
    }

这里有**可能出现竞争条件，其原因是对count的访问未作限制**。有可能出现以下情况：缓冲区为空，消费者刚刚读取count的值发现它为0，此时调度程序决定暂停消费者并启动运行生产者（进程切换）。生产者向缓冲区加入一个数据项，count加1。现在count的值变成了1，它推断认为count刚才为0，所以消费者此时一定在睡眠，于是生产者调用wakeup来唤醒消费者。

但是消费者在逻辑上并未睡眠，所以wakeup信号丢失，当消费者下次运行时，它将测试先前读取的count值，发现它为0。于是睡眠，生产者迟早会填满整个缓冲区，然后睡眠，这样一来，两个进程将永远睡眠下去。

# 信号量的引入及其操作 #

信号量是Dijkstra在1965年提出的一种方法，它使用一个整型变量来累计唤醒次数，供以后使用。在他的建议中引入了一个新的变量类型，称作信号量（semaphore）。一个信号量的取值可以为0（表示没有保存下来的唤醒操作）或者正值（表示有一个或多个唤醒操作）。

Dijkstra建议设立两种操作：**down和up（分别为一般化后的sleep和wakeup）。对一个信号量执行down操作，则是检查其值是否大于0。若该值大于0，则将其减1（即用掉一个保存的唤醒信号）并继续；若该值为0，则进程将睡眠，而且此时down操作并未结束**。**检查数值、修改变量值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作完成**。保证一旦一个信号量操作开始，则在该操作完成或阻塞之前，其他进程均不允许访问该信号量。这种原子性对于解决同步问题和避免竞争条件是绝对必要的。所谓**原子操作，是指一组相关联的操作要么都不间断地执行，要么不执行**。

up操作对信号量的值增1。如果一个或多个进程在该信号量上睡眠，无法完成一个先前的down操作，则由系统选择其中的一个（如随机挑选）并允许该进程完成它的down操作。于是，对一个有进程在其上睡眠的信号量执行一次up操作后，该信号量的值仍旧是0，但在其上睡眠的进程却少了一个。信号量的值增加1和唤醒一个进程同样也是不可分割的，不会有某个进程因执行up而阻塞，正如前面的模型中不会有进程因执行wakeup而阻塞一样。

在Dijkstra原来的论文中，他分别使用名称P和V而不是down和up，荷兰语中，Proberen的意思是尝试，Verhogen的含义是增加或升高。

从物理上说明信号量的P、V操作的含义。 **P(S)表示申请一个资源，S.value>0表示有资源可用，其值为资源的数目；S.value=0表示无资源可用；S.value<0, 则|S.value|表示S等待队列中的进程个数**。V(S)表示释放一个资源，信号量的初值应该大于等于0。P操作相当于“等待一个信号”，而V操作相当于“发送一个信号”，**在实现同步过程中，V操作相当于发送一个信号说合作者已经完成了某项任务，在实现互斥过程中，V操作相当于发送一个信号说临界资源可用了**。实际上，在**实现互斥时，P、V操作相当于申请资源和释放资源**。

该解决方案使用了三个信号量：一个称为full，用来记录充满缓冲槽数目，一个称为empty，记录空的缓冲槽总数；一个称为mutex，用来确保生产者和消费者不会同时访问缓冲区。full的初值为0，empty的初值为缓冲区中槽的数目，mutex的初值为1。供两个或多个进程使用的信号量，其初值为1，保证同时只有一个进程可以进入临界区，称作二元信号量。如果每个进程在进入临界区前都执行down操作，并在刚刚退出时执行一个up操作，就能够实现互斥。

在下面的例子中，我们实际上是通过两种不同的方式来使用信号量，两者之间的区别是很重要的，信号量mutex用于互斥，它用于保证任一时刻只有一个进程读写缓冲区和相关的变量。互斥是避免混乱所必需的操作。

#define N 100
    typedef int semaphore;
    semaphore mutex = 1;
    semaphore empty = N;
    semaphore full = 0;
    void producer(void)
    {
    	int item;
    	while(TRUE)
    	{
    		item = produce_item();
    		down(&empty);				//空槽数目减1，相当于P(empty)
    		down(&mutex);				//进入临界区，相当于P(mutex)
    		insert_item(item);			//将新数据放到缓冲区中
    		up(&mutex);				//离开临界区，相当于V(mutex)
    		up(&full);				//满槽数目加1，相当于V(full)
    	}
    }
    void consumer(void)
    {
    	int item;
    	while(TRUE)
    	{
    		down(&full);				//将满槽数目减1，相当于P(full)
    		down(&mutex);				//进入临界区，相当于P(mutex)
    		item = remove_item();	   		 //从缓冲区中取出数据
    		up(&mutex);				//离开临界区，相当于V(mutex)		
    		up(&empty);				//将空槽数目加1 ，相当于V(empty)
    		consume_item(item);			//处理取出的数据项
    	}
    }

信号量的另一种用途是**用于实现同步**，信号量full和empty用来保证某种事件的顺序发生或不发生。在本例中，它们保证当缓冲区满的时候生产者停止运行，以及当缓冲区空的时候消费者停止运行。

对于无界缓冲区的生产者—消费者问题，两个进程共享一个不限大小的公共缓冲区。由于是无界缓冲区（仓库是无界限制的），即生产者不用关心仓库是否满，只管往里面生产东西，但是消费者还是要关心仓库是否空。所以生产者不会因得不到缓冲区而被阻塞，不需要对空缓冲区进行管理，可以去掉在有界缓冲区中用来管理空缓冲区的信号量及其PV操作。

Semaphore mutex = 1; 
    Semaphore full = 0; 
    int in = 0，out = 0;
    void producer(void)
    {
    	while(TRUE)
    	{
    		item = produce_item();
    		P(mutex);				//进入临界区
    		Buffer(in) = item;			//新生产的数据项放入缓冲区
    		in = in + 1;				//因无界，无需考虑输入指针越界
    		V(mutex);				//离开临界区
    		V(full);				//增加已用缓冲区的数目
    	}
    }
    void consumer(void)
    {
    	int item;
    	while(TRUE)
    	{
    		P(full);			//等待已用缓冲区的数目非0
    		P(mutex);			//进入临界区
    		item = Buffer(out);		//新生产的数据项放入缓冲区
    		out = out + 1;			//因无界，无需考虑输出指针越界
    		V(mutex);			//离开临界区
    		consume_item(item);		//处理取出的数据项
    	}
    }

在计算机领域，**同步就是指一个进程在执行某个请求的时候，若该请求需要一段时间才能返回信息，那么这个进程会一直等待下去**。直到收到返回信息才继续执行下去。异步是指进程不需要一直等待下去，而是继续执行下面的操作，不管其他进程的状态，当有消息返回时，系统会通知进程进行处理，这样可以提高效率。

# 进程同步与互斥 #

在操作系统中，进程是占有资源的最小单位（线程可以访问其所在进程内的所有资源，但线程本身并不占有资源或仅仅占有一点必须资源）。但对于某些资源来说，其在同一时间只能被一个进程所占用。这些**一次只能被一个进程所占用的资源就是所谓的临界资源**。典型的临界资源比如物理上的打印机，或是存在硬盘或内存中被多个进程所共享的一些变量和数据等（如果这类资源不被看成临界资源加以保护，那么很有可能造成丢数据的问题）。

对临界资源的访问，必须是互斥地进行。也就是当临界资源被占用时，另一个申请临界资源的进程会被阻塞，直到其所申请的临界资源被释放。而进程内访问临界资源的代码被成为临界区。

进程同步也是进程之间直接的制约关系，是为完成某种任务而建立的两个或多个进程，这些进程需要**在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系**。进程间的直接制约关系**来源于他们之间的合作**。比如说进程A需要从缓冲区读取进程B产生的信息，当缓冲区为空时，进程B因为读取不到信息而被阻塞。而当进程A**产生信息放入缓冲区时，进程B才会被唤醒**。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z1emhvbmdtaW4wNQ_size_16_color_FFFFFF_t_70][]

进程互斥是进程之间的间接制约关系。**当一个进程进入临界区使用临界资源时，另一个进程必须等待**。只有**当使用临界资源的进程退出临界区后，这个进程才会解除阻塞状态。**比如进程B需要访问打印机，但此时进程A占有了打印机，进程B会被阻塞，直到进程A释放了打印机资源，进程B才可以继续执行，概念如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z1emhvbmdtaW4wNQ_size_16_color_FFFFFF_t_70 1][]

进程的同步和互斥是指进程在推进时的相互制约关系。 **进程同步源于进程合作，是进程间共同完成一项任务是直接发生相互作用的关系**。**进程互斥源于对临界资源的竞争**，是进程之间的间接制约关系。

实现临界区互斥访问的基本方法有**硬件实现方法和信号量**方法。

通过**硬件实现临界区最简单的办法就是关****CPU****的中断**。从计算机原理我们知道，**CPU****进行进程切换是需要通过中断来进行**。如果**屏蔽了中断**那么就可以**保证当前进程顺利的将临界区代码执行完**，从而实现了互斥。这个办法的步骤就是：屏蔽中断—执行临界区操作—开中断。但这样做并不好，这大大限制了处理器交替执行任务的能力。并且将关中断的权限交给用户代码，那么如果用户代码屏蔽了中断后不再开，那系统岂不是跪了？

信号量实现方式，这也是我们比较熟悉P/V操作。通过设置一个表示资源个数的信号量S，通过对信号量S的P和V操作来实现进程的的互斥。P/V操作是操作系统的原语，意味着具有原子性。**P****操作首先减少信号量****S****，表示有一个进程将占用或等待资源**，然后**检测****S****是否小于****0****，如果小于****0****则阻塞，如果大于****0****则占有资源进行执行**。V操作是和P操作相反的操作，**首先增加信号量****S****，表示占用或等待资源的进程减少了****1****个**,然后检测S是否小于0，如果**大于****0****则唤醒等待使用****S****资源的其它进程**。前面的生产者—消费者问题就是典型的应用信号量解决的进程同步问题。

[20170119150635987]: /images/20220711/b3bad2acf3b14127b300446c7c261e18.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z1emhvbmdtaW4wNQ_size_16_color_FFFFFF_t_70]: /images/20220711/6e86a4dd645b4210900030ebab52219a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z1emhvbmdtaW4wNQ_size_16_color_FFFFFF_t_70 1]: /images/20220711/667ff9848836473ea82cbd5d93eb00a1.png