生产者—消费者问题
生产者—消费者题型在各类考试（考研、程序员证书、程序员面试口试、期末考试）很常见，起因之一是生产者—消费者题型在理论的并发程序（多过程、多线程）设计中很常见；之二是这种题型综合性较好，波及过程单干、互斥，有时还波及死锁的防止。生产者—消费者题型能够全面考核你对并发程序的了解和设计能力。
生产者—消费者题型最根本的是有界缓冲区的生产者消费者问题和无界缓冲区的生产者消费者问题，对这两个问题的解咱们应该把握其解决方案。
对于有界缓冲区的生产者—消费者问题，两个过程共享一个公共的固定大小的缓冲区。其中一个是生产者，将信息放入缓冲区；另一个是消费者，从缓冲区中取出信息（也能够把这个问题个别化为 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; // 缓冲区数据项计数加 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 才会被唤醒。
过程互斥是过程之间的间接制约关系。当一个过程进入临界区应用临界资源时，另一个过程必须期待。只有当应用临界资源的过程退出临界区后，这个过程才会解除阻塞状态。比方过程 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