生产者—消费者问题

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

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

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

 

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

        这个方法听起来很简单，为了跟踪缓冲区中的数据项数，我们需要一个变量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;				//缓冲区数据项计数加1if(count == 1)wakeup(consumer);}
}void consumer(void)
{int item;while(TRUE){if(count == 0)				//如果缓冲区空就休眠sleep();item = remove_item();count = count - 1;			//缓冲区数据项计数减1if(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);			//等待已用缓冲区的数目非0P(mutex);			//进入临界区item = Buffer(out);		//新生产的数据项放入缓冲区out = out + 1;			//因无界，无需考虑输出指针越界V(mutex);			//离开临界区consume_item(item);		//处理取出的数据项}
}

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

进程同步与互斥

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

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

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

 

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

 

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

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

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

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