进程中线程同步的四种方式

by 夏泽民 Jan 5, 2020

三种方法：

1、互斥对象

2、事件对象

3、关键代码段

三种比较：

互斥对象和事件对象都属于内核对象，利用内核对象进行线程同步，速度较慢，但利用互斥对象和事件对象这样的内核对象，可以在多个进程中的各个线程间进行同步。

关键代码段是工作在用户方式下，同步速度较快，但在使用关键代码段时，很容易进入死锁状态，因为在等待进入关键代码段时无法设定超时值。

在构造函数中初始化临界对象，析构函数中离开，资源调用中enter，调用结束后leave。

临界区问题
为了并发访问数据的同步问题，我们介绍临界区的概念。

临界区: 一种代码段，在其中可能发生多个线程共同改变变量、读写文件等操作，其要求当一个线程进入临界区时，其他线程不能进入。从而避免出现同时读写的问题。(实际上，临界区只需保证可以有多个读者同时执行读取操作，或唯一写者执行写入操作)
进入区: 判断线程能否进入临界区的代码段。
退出区: 线程离开临界区后可能对其执行的某些操作。
剩余区: 线程完全退出临界区和退出区后的剩下全部代码。

对于上述的买票示例，买票的整个过程即为临界区代码，但我们缺失了进入区，无法保证临界区内线程的唯一，所以出现了同步问题。

临界区调度原则
所有临界区调度应当符合以下原则:

同一时间临界区内仅可有一个线程执行，如果有若干线程请求进入空闲临界区，一次进允许一个线程进入，如果临界区已有线程，则要求其他视图进入临界区的线程等待。
进入临界区的线程必须在有限时间内退出，以保证其他线程能进入该临界区。
如果线程不能进入临界区，应让出CPU，避免出现忙等现象。
从线程请求进入临界区到允许，有次数限制，避免让线程无限等待。
总结为三点: 互斥、前进、有限等待。

Tips: 在非抢占内核系统中进程会一直运行直到中断或退出，故不涉及进程同步问题。

临界区问题的解决方法
解决临界区问题，需要通过加锁的方式，类似于当一个线程进入临界区后即上锁，阻止其他线程进入，待运行完成后打开锁允许其他线程进入。

软件实现方法
解决临界区问题，主要在于保证资源的互斥访问，以及避免出现饥饿现象。

Peterson算法提供了一个合理的思路: 设置旗标数组flag标记请求进入临界区的线程，设置turn表示可以进入临界区的线程，在进入区进行双重判断，两个线程同时对turn赋值只会有一个保留下来，从而确保资源访问的互斥。
而在退出区，对flag旗标进行了false处理，从而保证了”前进”原则，避免了剩余区中的线程持续抢占造成其他线程饥饿。

硬件实现方法
Peterson算法是基于软件的实现，而从硬件层面也可以解决此问题，硬件方面的处理主要在于线程修改共享资源时是原子地，即不可被中断。比如机器提供了能够原子执行的指令，那么我们可以通过简单的修改布尔变量来实现互斥，因为加锁的过程是原子的。而对于可能造成饥饿的问题，只需在退出区对等待列表进行一定处理，保证”前进”原则即可。

简单来说，无论硬件还是软件的实现，本质都是通过加锁。只是通过硬件的特性，可以提高效率，同时也简化了临界区的实现难度。

信号量
临界区问题为我们解决线程同步提供了一种思路，而在实际使用中，要处理同一个实例有多个资源的情况，我们可以采用一种较为简单的方式——信号量，大多操作系统都提供了信号量的同步工具。

原理
简单来说，信号量是某个实例可用资源的计数，初始为该实例可用资源的数量，而每当线程需要使用，则调用wait()方法减少信号量，释放资源时调用signal()方法增加信号量，故信号量为0表示所有资源都在被使用，线程使用资源的请求不被允许。

信号量主要分为计数信号量和二进制信号量，前者主要针对一个实例有多个资源的情况，值域不受限制，而后者信号量仅为0或1，也就是说线程之间访问该资源是互斥的，也可称作互斥锁。

同临界区问题的前提: 必须保证执行信号量操作wait(),signal()是原子地。

以下是信号量的伪代码实现:

while (true) {
waiting(mutex); // 减少信号量(进入区)
// 临界区
signal(mutex); // 增加信号量(退出区)
// 剩余区
}
具体实现
由于基于临界区问题，那么信号量在具体实现中也要处理其缺点: 饥饿问题。同时其需要避免忙等问题和死锁问题。

在此之前我们先看一下其基本功能实现。

实现信号量需要维护一个信号量值和一个等待进程链表。
当信号量为0时，将请求进入临界区的进程放入等待列表中，并阻塞自己(避免出现频繁循环请求的忙等问题)。待其他临界区退出时，从等待列表中取出并唤醒。以下为实现的伪代码:

// 信号量定义
typedef struct {
int value;
struct process *list;
} semaphore;

// 减少信号量
void wait(semaphore *mutex) {
mutex->value–; // 减少信号量值
if (mutex->value < 0) {
addToList(list, mutex); // 将该进程添加至等待进程链表
block(); // 阻塞自己等待唤醒
}
}

// 增加信号量
void signal(semaphore *mutex) {
mutex->value++; // 增加信号量

if (mutex->value <= 0) {
process *p = removeFromList(list ,mutex); // 同等待链表中取出一个进程
wakeup(P); // 唤醒等待中的进程
}
}
饥饿问题
在信号量大于0时从队列中取出哪个进程是需要讨论的问题，选择合适的调度方式很重要。FIFO(先进先出)可以解决，但如果LIFO(后进先出)调度则可能会造成部分进程无限期阻塞，也就是饥饿问题。

忙等问题
当进程请求进入临界区而没有被允许时，如果此进程开始在进入区连续循环请求，则会消耗大量性能，浪费了部分CPU时间片。这种加锁方式称为自旋锁，即进程在等待锁时仍然在运行，此方法会造成忙等的性能浪费，但同时也比阻塞-唤醒机制效率更高，避免了阻塞到唤醒的上下文切换。

如果要克服忙等问题，可以在进入区增加当信号量小于0时，进程阻塞自己，进入等待队列；当临界区内的线程执行完毕后，唤醒等待队列中的进程。同时要保证等待队列调度的算法合理性，避免某进程无限期等待。

死锁问题
死锁问题就是多个进程无限等待某个事件，而该事件是由这些进程来产生的，这样就会造成”第二十二条军规”中的问题，进程之间互相等待，无法前进。在此不讨论死锁问题，只介绍可能出现的死锁情况。如下图所示:

信号量死锁的情况
解决死锁问题主要可以从死锁预防、死锁避免、死锁检测、死锁恢复四个方面入手，后面会专门写文章讲解。

不同处理器的解决方案
单个处理器: 单处理器时无须担心并行运算造成的同步问题，所以简单在wait()和signal()中禁止临界区中进程的中断即可。

多处理器: 操作系统对于多处理器调度分为SMP和非SMP的情况(SMP为对称多处理，处理器各自控制各自的调度，而非SMP为某一个处理器作为中控，管理其他处理器的调度)。

非对称多处理: 对于非对称多处理，由于有中央处理器来调度，可以简单使用自旋锁来进行忙等，系统来决策等待锁的进程的调度问题。
对称多处理: 对于对称多处理系统，就要自行实现上述的信号量等待列表，以及等待锁时的阻塞——唤醒机制。

经典同步问题
涉及到同步问题，有几种经典的问题，主要的有读者——写者问题和哲学家进餐问题，前者关注互斥问题，后者关注死锁问题。

读者——写者问题
仅进行读取操作的为读者，而读写操作均需要的为写者。仍然以刚才的买票问题为例，我们不难发现，当同时读取时，不会出现问题，当唯一写入时，也不会出现问题，但是当同时进行读写时，则发生了数据错误问题。

所以读者——写者问题应当保证同一时间写者的唯一性及读者要等待写者完成后再执行。

同时，在实际实现中，要着重处理读者或写者的饥饿问题，读者/写者优先的方案很可能造成对方的饥饿。

哲学家进餐问题
哲学家问题是一个经典的死锁问题，n个哲学家围坐在圆桌上，圆桌上放着n支筷子，也就是没人左右都有1支筷子。只有同时拥有两支筷子才能吃饭，吃完饭后会放下筷子。若同一时间每个哲学家都先拿起右手边的筷子再拿起左手的，那么就造成了死锁问题，每个人都在等待左手的筷子。

哲学家进餐问题
解决办法多种多样，可以限制哲学家的数量为n-1，也可以要求拿起筷子前判断是否左右手的筷子均空闲。而本质上，解决方法就是死锁的四种解决方法: 死锁预防、死锁避免、死锁检测、死锁恢复。

总结
进程/线程同步问题是操作系统在数据共享方面的一大问题，其不仅需要硬件及系统级的实现，同时还需要程序员在开发时避免死锁，同步问题与死锁问题密不可分，后面将会讨论死锁问题。

进程中线程同步的四种常用方式：

互斥量：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。

信号量：它允许同一时刻多个线程来访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。

事件（信号）：通过通知操作的方式来保持多线程同步，还可以方便实现多线程优先级的比较作。

4.临界区：临界区对象和互斥对象非常相似，只是互斥量允许在进程间使用，而临界区只限制与同一进程的各个线程之间使用，但是更节省资源，更有效率。

临界区：当多个线程访问一个独占性共享资源时，可以使用临界区对象。拥有临界区的线程可以访问被保护起来的资源或代码段，其他线程若想访问，则被挂起，直到拥有临界区的线程放弃临界区为止。

1、临界区（CCriticalSection）

当多个线程访问一个独占性共享资源时，可以使用临界区对象。拥有临界区的线程可以访问被保护起来的资源或代码段，其他线程若想访问，则被挂起，直到拥有临界区的线程放弃临界区为止。具体应用方式：

            1、 定义临界区对象CcriticalSection g_CriticalSection;

            2、 在访问共享资源（代码或变量）之前，先获得临界区对象，g_CriticalSection.Lock（）；

            3、 访问共享资源后，则放弃临界区对象，g_CriticalSection.Unlock（）；

2、事件（CEvent）

事件机制，则允许一个线程在处理完一个任务后，主动唤醒另外一个线程执行任务。比如在某些网络应用程序中，一个线程如A负责侦听通信端口，另外一个线程B负责更新用户数据，利用事件机制，则线程A可以通知线程B何时更新用户数据。每个Cevent对象可以有两种状态：有信号状态和无信号状态。Cevent类对象有两种类型：人工事件和自动事件。

自动事件对象，在被至少一个线程释放后自动返回到无信号状态；

人工事件对象，获得信号后，释放可利用线程，但直到调用成员函数ReSet()才将其设置为无信号状态。在创建Cevent对象时，默认创建的是自动事件。

1、
1

CEvent(BOOL bInitiallyOwn=FALSE,

      BOOL bManualReset=FALSE,

      LPCTSTR lpszName=NULL,

      LPSECURITY_ATTRIBUTES lpsaAttribute=NULL);

bInitiallyOwn:指定事件对象初始化状态，TRUE为有信号，FALSE为无信号；
bManualReset：指定要创建的事件是属于人工事件还是自动事件。TRUE为人工事件，FALSE为自动事件；
后两个参数一般设为NULL，在此不作过多说明。
2、BOOL CEvent：：SetEvent();
将Cevent类对象的状态设置为有信号状态。如果事件是人工事件，则Cevent类对象保持为有信号状态，直到调用成员函数ResetEvent()将其重新设为无信号状态时为止。如果为自动事件，则在SetEvent（）后将事件设置为有信号状态，由系统自动重置为无信号状态。

3、BOOL CEvent：：ResetEvent();
将事件的状态设置为无信号状态，并保持该状态直至SetEvent（）被调用为止。由于自动事件是由系统自动重置，故自动事件不需要调用该函数。

一般通过调用WaitForSingleObject（）函数来监视事件状态。

3、互斥量（CMutex）

互斥对象和临界区对象非常相似，只是其允许在进程间使用，而临界区只限制与同一进程的各个线程之间使用，

但是更节省资源，更有效率。

4、信号量（CSemphore）

当需要一个计数器来限制可以使用某共享资源的线程数目时，可以使用“信号量”对象。CSemaphore类对象保存了对当前访问某一个指定资源的线程的计数值，该计数值是当前还可以使用该资源的线程数目。如果这个计数达到了零，则所有对这个CSemaphore类对象所控制的资源的访问尝试都被放入到一个队列中等待，直到超时或计数值不为零为止。

CSemaphore 类的构造函数原型及参数说明如下：

CSemaphore(

LONG lInitialCount = 1,

LONG lMaxCount = 1,

LPCTSTR pstrName = NULL,

LPSECURITY_ATTRIBUTES lpsaAttributes = NULL

);

lInitialCount:信号量对象的初始计数值，即可访问线程数目的初始值；
lMaxCount：信号量对象计数值的最大值，该参数决定了同一时刻可访问由信号量保护的资源的线程最大数目；
后两个参数在同一进程中使用一般为NULL，不作过多讨论；
一般是将当前可用资源计数设置为最大资源计数，每增加一个线程对共享资源的访问，当前可用资源计数就减1，只要当前可用资源计数大于0，就可以发出信号量信号。如果为0，则放入一个队列中等待。线程在处理完共享资源后，应在离开的同时通过ReleaseSemaphore（）函数将当前可用资源数加1。

BOOL ReleaseSemaphore( HANDLE hSemaphore, // hSemaphore:信号量句柄

　　　　　　　　　　　　　　LONG lReleaseCount, // lReleaseCount：信号量计数值

　　　　　　　　　　　　　　LPLONG lpPreviousCount // 参数一般为NULL);

进程同步：

多进程的系统中避免不了进程间的相互关系。本讲将介绍进程间的两种主要关系——同步与互斥，然后着重讲解解决进程同步的几种机制。
进程互斥是进程之间发生的一种间接性作用，一般是程序不希望的。通常的情况是两个或两个以上的进程需要同时访问某个共享变量。我们一般将发生能够问共享变量的程序段称为临界区。两个进程不能同时进入临界区，否则就会导致数据的不一致，产生与时间有关的错误。解决互斥问题应该满足互斥和公平两个原则，即任意时刻只能允许一个进程处于同一共享变量的临界区，而且不能让任一进程无限期地等待。互斥问题可以用硬件方法解决，我们不作展开；也可以用软件方法，这将会在本讲详细介绍。
进程同步是进程之间直接的相互作用，是合作进程间有意识的行为，典型的例子是公共汽车上司机与售票员的合作。只有当售票员关门之后司机才能启动车辆，只有司机停车之后售票员才能开车门。司机和售票员的行动需要一定的协调。同样地，两个进程之间有时也有这样的依赖关系，因此我们也要有一定的同步机制保证它们的执行次序。
本讲主要介绍以下四种同步和互斥机制：信号量、管程、会合、分布式系统。

一，信号量

参考自http://blog.csdn.net/leves1989/article/details/3305609

理解PV：

PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：
P（S）：①将信号量S的值减1，即S=S-1；
②如果S³0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。
V（S）：①将信号量S的值加1，即S=S+1；
②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。
PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。

什么是信号量？信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。
一般来说，信号量S³0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S£0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。

利用信号量和PV操作实现进程互斥的一般模型是：
进程P1 进程P2 …… 进程Pn
…… …… ……
P（S）； P（S）； P（S）；
临界区；临界区；临界区；
V（S）； V（S）； V（S）；
…… …… …… ……

其中信号量S用于互斥，初值为1。

使用PV操作实现进程互斥时应该注意的是：

（1）每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。

（2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。    （3）互斥信号量的初值一般为1。

利用信号量和PV操作实现进程同步
PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。
使用PV操作实现进程同步时应该注意的是：

（1）分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量。

（2）信号量的初值与相应资源的数量有关，也与P、V操作在程序代码中出现的位置有关。

（3）同一信号量的P、V操作要成对出现，但它们分别在不同的进程代码中。

【例1】生产者-消费者问题
在多道程序环境下，进程同步是一个十分重要又令人感兴趣的问题，而生产者-消费者问题是其中一个有代表性的进程同步问题。下面我们给出了各种情况下的生产者-消费者问题，深入地分析和透彻地理解这个例子，对于全面解决操作系统内的同步、互斥问题将有很大帮助。

（1）一个生产者，一个消费者，公用一个缓冲区。
定义两个同步信号量：
empty——表示缓冲区是否为空，初值为1。
full——表示缓冲区中是否为满，初值为0。
生产者进程
while(TRUE){
生产一个产品;
P(empty);
产品送往Buffer;
V(full);
}
消费者进程
while(True){
P(full);
从Buffer取出一个产品;
V(empty);
消费该产品;
}
（2）一个生产者，一个消费者，公用n个环形缓冲区。
定义两个同步信号量：
empty——表示缓冲区是否为空，初值为n。
full——表示缓冲区中是否为满，初值为0。

设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指 ，指向下一个可用的缓冲区。 生产者进程 while(TRUE){

 生产一个产品;

 P(empty);

 产品送往buffer（in）；

 in=(in+1)mod n；

 V(full); }

消费者进程
while(TRUE){
P(full);
从buffer（out）中取出产品；
out=(out+1)mod n；
V(empty);
消费该产品;
}
（3）一组生产者，一组消费者，公用n个环形缓冲区
在这个问题中，不仅生产者与消费者之间要同步，而且各个生产者之间、各个消费者之间还必须互斥地访问缓冲区。
定义四个信号量：
empty——表示缓冲区是否为空，初值为n。
full——表示缓冲区中是否为满，初值为0。
mutex1——生产者之间的互斥信号量，初值为1。
mutex2——消费者之间的互斥信号量，初值为1。

设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。 生产者进程 while(TRUE){

 生产一个产品;

 P(empty);

 P(mutex1)；

 产品送往buffer（in）；

 in=(in+1)mod n；

 V(mutex1);

 V(full); } 消费者进程 while(TRUE){  P(full)    P(mutex2)；    从buffer（out）中取出产品；    out=(out+1)mod n；    V（mutex2）；    V(empty);    消费该产品;    }   需要注意的是无论在生产者进程中还是在消费者进程中，两个P操作的次序不能颠倒。应先执行同步信号量的P操作，然后再执行互斥信号量的P操作，否则可能造成进程死锁。

【例2】桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。

分析在本题中，爸爸、儿子、女儿共用一个盘子，盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。本题实际上是生产者-消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。

解：在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值为l；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。同步描述如下： int S＝1; int Sa＝0; int So＝0;

  main()

  {

    cobegin

        father();      /*父亲进程*/

        son();        /*儿子进程*/

        daughter();    /*女儿进程*/

    coend

｝

father()

{

    while(1)

      {

        P(S);

        将水果放入盘中;

        if（放入的是桔子）V(So);

        else  V(Sa);

       }

 }

son()

{

    while(1)

      {

         P(So);

         从盘中取出桔子;

         V(S);

         吃桔子;

        ｝

}

daughter()

{

     while(1)

        {

          P(Sa);

          从盘中取出苹果;

          V(S);

          吃苹果;

        ｝ ｝

思考题：

四个进程A、B、C、D都要读一个共享文件F，系统允许多个进程同时读文件F。但限制是进程A和进程C不能同时读文件F，进程B和进程D也不能同时读文件F。为了使这四个进程并发执行时能按系统要求使用文件，现用PV操作进行管理，请回答下面的问题：
（1）应定义的信号量及初值：。
（2）在下列的程序中填上适当的P、V操作，以保证它们能正确并发工作：
A() B() C() D()
{ { { {
[1]; [3]; [5]; [7];
read F; read F; read F; read F;
[2]; [4]; [6]; [8];
} } } }

思考题解答： （1）定义二个信号量S1、S2，初值均为1，即：S1=1，S2=1。其中进程A和C使用信号量S1，进程B和D使用信号量S2。 （2）从[1]到[8]分别为：P(S1) V(S1) P(S2) V(S2) P(S1) V(S1) P(S2) V(S2)

二，管程：参考自http://hi.baidu.com/zucenaa/blog/item/e63d22277c9d9c09918f9de2.html

信号量机制功能强大，但使用时对信号量的操作分散，而且难以控制，读写和维护都很困难。因此后来又提出了一种集中式同步进程——管程。其基本思想是将共享变量和对它们的操作集中在一个模块中，操作系统或并发程序就由这样的模块构成。这样模块之间联系清晰，便于维护和修改，易于保证正确性。

管程作为一个模块，它的类型定义如下：
monitor_name = MoNITOR;
共享变量说明;
define 本管程内部定义、外部可调用的函数名表;
use 本管程外部定义、内部可调用的函数名表;
内部定义的函数说明和函数体
{
共享变量初始化语句;
}

从语言的角度看，管程主要有以下特性：
（1）模块化。管程是一个基本程序单位，可以单独编译;
（2）抽象数据类型。管程是中不仅有数据，而且有对数据的操作;
（3）信息掩蔽。管程外可以调用管程内部定义的一些函数，但函数的具体实现外部不可见;
对于管程中定义的共享变量的所有操作都局限在管程中，外部只能通过调用管程的某些函数来间接访问这些变量。因此管程有很好的封装性。
为了保证共享变量的数据一致性，管程应互斥使用。管程通常是用于管理资源的，因此管程中有进程等待队列和相应的等待和唤醒操作。在管程入口有一个等待队列，称为入口等待队列。当一个已进入管程的进程等待时，就释放管程的互斥使用权；当已进入管程的一个进程唤醒另一个进程时，两者必须有一个退出或停止使用管程。在管程内部，由于执行唤醒操作，可能存在多个等待进程（等待使用管程），称为紧急等待队列，它的优先级高于入口等待队列。
因此，一个进程进入管程之前要先申请，一般由管程提供一个enter过程；离开时释放使用权，如果紧急等待队列不空，则唤醒第一个等待者，一般也由管程提供外部过程leave。
管程内部有自己的等待机制。管程可以说明一种特殊的条件型变量：var c:condition；实际上是一个指针，指向一个等待该条件的PCB队列。对条件型变量可执行wait和signal操作：（联系P和V； take和give）
wait(c):若紧急等待队列不空，唤醒第一个等待者，否则释放管程使用权。执行本操作的进程进入C队列尾部；
signal(c):若C队列为空，继续原进程，否则唤醒队列第一个等待者，自己进入紧急等待队列尾部。

【示例】

生产者-消费者问题（有buffer）

问题描述：(一个仓库可以存放K件物品。生产者每生产一件产品，将产品放入仓库，仓库满了就停止生产。消费者每次从仓库中去一件物品，然后进行消费，仓库空时就停止消费。
解答：
管程：buffer=MODULE;
（假设已实现一基本管程monitor，提供enter,leave,signal,wait等操作）

notfull,notempty:condition; // notfull控制缓冲区不满,notempty控制缓冲区不空；
count,in,out: integer; 　　 // count记录共有几件物品，in记录第一个空缓冲区，out记录第一个不空的缓冲区
buf:array [0..k-1] of item_type;
define deposit,fetch;
use monitor.enter,monitor.leave,monitor.wait,monitor.signal;

procedure deposit(item);
{
　　if(count=k) monitor.wait(notfull);
　　buf[in]=item;
　　in:=(in+1) mod k;
　　count++;
　　monitor.signal(notempty);
}
procedure fetch:Item_type;
{
　　if(count=0) monitor.wait(notempty);
　　item=buf[out];
　　in:=(in+1) mod k;
　　count–;
　　monitor.signal(notfull);
　　return(item);
}
{
count=0;
in=0;
out=0;
}

进程：producer,consumer;
producer（生产者进程）：
Item_Type item;
{
　　while (true)
　　{
　　　　produce(&item);
　　　　buffer.enter();
　　　　buffer.deposit(item);
　　　　buffer.leave();
　　}
}

consumer（消费者进程）：
Item_Type item;
{
　　while (true)
　　{
　　　　buffer.enter();
　　　　item=buffer.fetch();
　　　　buffer.leave();
　　　　consume(&item);
　　}
}

【附】有关wait和signal的语言表示

信号量结构使用C语言表示如下：

typedef struct {
int value;//记录了这个信号量的值
struct process *list;//储存正在等待这个信号量的进程
} semaphore;
wait()信号量部分代码如下：

wait(semaphore *S) {
S->value–;
if(S->value < 0) {
add this process to S->list;
block();
}
}
signal()信号量部分代码如下：

signal(semaphore *S) {
S->value++;
if(S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
一、The Bounded-Buffer Problem：

full初始化为0，empty初始化为n，mutex为1

do{
wait(full);
wait(mutex);
…
//remove an item from buffer to nextc
…
signal(mutex);
signal(empty);
…
//consume the item in nextc
…
} while(TRUE);
二、The Readers-Writers Problem：

wrt初始化为1，readcount初始化为0，mutex为1

写者操作：

do{
wait(wrt);
…
//writing is performed
…
signal(wrt);
} while(TRUE);

读者操作：

do{
wait(mutex);//确保与signal(mutex)之间的操作不会被其他读者打断
readcount++;
if(readcount == 1)
wait(wrt);
signal(mutex);
…
//reading is performed
…
wait(mutex);
readcount–;
if(readcount == 0)
signal(wrt);
signal(mutex);
} while(TRUE);

三、The Dining-Philosophers Problem：

所有的chopstick[5]全部初始化为1

do{
wait(chopstick[i]);
wait(chopstick[(i+1)%5]);
…
//eating
…
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
…
//thinking
…
} while(TRUE);
但是这个解决方案的最大问题在于它会出现死锁。所以我认为应该增加一个信号量mutex，并初始化为1：

do{
wait(mutex);
wait(chopstick[i]);
wait(chopstick[(i+1)%5]);
signal(mutex);
…
//eating

…
wait(mutex);
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
signal(mutex);
…
//thinking

…
} while(TRUE);
这样由于确保了一位哲学家在拿起两只筷子的时间内其他哲学家不可以拿起任何一支筷子，从而破坏了死锁出现需要的四个特征中的Hold And Wait特征，从而避免了死锁的发生

进程中线程同步的四种常用方式：
一、临界区（CCriticalSection）
当多个线程访问一个独占性共享资源时，可以使用临界区对象。拥有临界区的线程可以访问被保护起来的资源或代码段，其他线程若想访问，则被挂起，直到拥有临界区的线程放弃临界区为止。具体应用方式：
1、定义临界区对象CcriticalSection g_CriticalSection;
2、在访问共享资源（代码或变量）之前，先获得临界区对象，g_CriticalSection.Lock（）；
3、访问共享资源后，则放弃临界区对象，g_CriticalSection.Unlock（）；

二、事件（CEvent）
事件机制，则允许一个线程在处理完一个任务后，主动唤醒另外一个线程执行任务。比如在某些网络应用程序中，一个线程如A负责侦听通信端口，另外一个线程B负责更新用户数据，利用事件机制，则线程A可以通知线程B何时更新用户数据。每个Cevent对象可以有两种状态：有信号状态和无信号状态。Cevent类对象有两种类型：人工事件和自动事件。
自动事件对象，在被至少一个线程释放后自动返回到无信号状态；
人工事件对象，获得信号后，释放可利用线程，但直到调用成员函数ReSet()才将其设置为无信号状态。在创建Cevent对象时，默认创建的是自动事件。
1、
1
2
3
4
CEvent(BOOL bInitiallyOwn=FALSE,
BOOL bManualReset=FALSE,
LPCTSTR lpszName=NULL,
LPSECURITY_ATTRIBUTES lpsaAttribute=NULL);
bInitiallyOwn:指定事件对象初始化状态，TRUE为有信号，FALSE为无信号；
bManualReset：指定要创建的事件是属于人工事件还是自动事件。TRUE为人工事件，FALSE为自动事件；
后两个参数一般设为NULL，在此不作过多说明。
2、BOOL CEvent：：SetEvent();
将Cevent类对象的状态设置为有信号状态。如果事件是人工事件，则Cevent类对象保持为有信号状态，直到调用成员函数ResetEvent()将其重新设为无信号状态时为止。如果为自动事件，则在SetEvent（）后将事件设置为有信号状态，由系统自动重置为无信号状态。

3、BOOL CEvent：：ResetEvent();
将事件的状态设置为无信号状态，并保持该状态直至SetEvent（）被调用为止。由于自动事件是由系统自动重置，故自动事件不需要调用该函数。
一般通过调用WaitForSingleObject（）函数来监视事件状态。

三、互斥量（CMutex）
互斥对象和临界区对象非常相似，只是其允许在进程间使用，而临界区只限制与同一进程的各个线程之间使用，
但是更节省资源，更有效率。
四、信号量（CSemphore）
当需要一个计数器来限制可以使用某共享资源的线程数目时，可以使用“信号量”对象。CSemaphore类对象保存了对当前访问某一个指定资源的线程的计数值，该计数值是当前还可以使用该资源的线程数目。如果这个计数达到了零，则所有对这个CSemaphore类对象所控制的资源的访问尝试都被放入到一个队列中等待，直到超时或计数值不为零为止。
CSemaphore 类的构造函数原型及参数说明如下：
CSemaphore(
LONG lInitialCount = 1,
LONG lMaxCount = 1,
LPCTSTR pstrName = NULL,
LPSECURITY_ATTRIBUTES lpsaAttributes = NULL
);
lInitialCount:信号量对象的初始计数值，即可访问线程数目的初始值；
lMaxCount：信号量对象计数值的最大值，该参数决定了同一时刻可访问由信号量保护的资源的线程最大数目；
后两个参数在同一进程中使用一般为NULL，不作过多讨论；
一般是将当前可用资源计数设置为最大资源计数，每增加一个线程对共享资源的访问，当前可用资源计数就减1，只要当前可用资源计数大于0，就可以发出信号量信号。如果为0，则放入一个队列中等待。线程在处理完共享资源后，应在离开的同时通过ReleaseSemaphore（）函数将当前可用资源数加1。

Category linux