生产者—消费者问题
生产者—消费者题型在各类考试（考研、程序员证书、程序员面试口试、期末考试）很常见，起因之一是生产者—消费者题型在理论的并发程序（多过程、多线程）设计中很常见；之二是这种题型综合性较好，波及过程单干、互斥，有时还波及死锁的防止。生产者—消费者题型能够全面考核你对并发程序的了解和设计能力。
生产者—消费者题型最根本的是有界缓冲区的生产者消费者问题和无界缓冲区的生产者消费者问题，对这两个问题的解咱们应该把握其解决方案。
对于有界缓冲区的生产者—消费者问题，两个过程共享一个公共的固定大小的缓冲区。其中一个是生产者，将信息放入缓冲区；另一个是消费者，从缓冲区中取出信息（也能够把这个问题个别化为m个生产者和n个消费者问题，然而咱们只探讨一个生产者和一个消费者的状况，这样能够简化解决方案）。
问题在于当缓冲区已满，而此时生产者还想向其中放入一个新的数据项的状况，其解决办法是让生产者睡眠，待消费者从缓冲区中取出一个或多个数据项时再唤醒它。同样地，当消费者试图从缓冲区取数据而发现缓冲区为空时，消费者就睡眠，直到生产者向其中放入一些数据时再将其唤醒。
这个办法听起来很简略，为了跟踪缓冲区中的数据项数，咱们须要一个变量count。如果缓冲区最多寄存N个数据项，则生产者代码将首先查看count是否达到N，若是，则生产者睡眠，否则生产者向缓冲区最多寄存N个数据项，则生产者代码将首先查看count是否达到N，若是，则生产者睡眠；否则生产者向缓冲区放入一个数据项并增量count的值。
消费者的代码与此相似：首先测试count是否为0，若是，则睡眠；否则从中取出一个数据项并递加count的值。每个过程同时也检测另一个过程是否应该被唤醒，若是则唤醒之。生产者消费者的代码如下：
#define N 100int 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 100typedef 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才会被唤醒。
过程互斥是过程之间的间接制约关系。当一个过程进入临界区应用临界资源时，另一个过程必须期待。只有当应用临界资源的过程退出临界区后，这个过程才会解除阻塞状态。比方过程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资源的其它过程。后面的生产者—消费者问题就是典型的利用信号量解决的进程同步问题。
起源：blog.csdn.net/fuzhongmin05/article/details/54616344