这个文章会首先会介绍下竞争条件的定义并举例说明下竞争条件可能造成的问题，之后会说一下临界区的概念和临界区问题的解决。 最后会讨论下信号量。

同步问题(Synchronization)

*上回提到，当multi-tasks被拆成多个不同的进程/线程让他们已并行的方式(条件是多核)完成会大大的提升效率。 但是多个进程或者线程之间的同步运行并且让他们按照某种条件或顺序来完成某些任务是一个麻烦的问题。 同步问题在进程或线程同步当中都会发生， 之后每次写俩写的麻烦， 之后会统称进程同步。

1. 竞争条件(Race Condition)

1.1 定义

细致一点说, 假设我要求进程PA和PB一起改变一个共享变量的时候。PA在修改的过程中，他的timer(或者说是time quantum)时间到了必须要进行context switch并切换到了PB，但此刻PA的修改并没有完成, PB所使用的是修改前的变量.那么这种情况下将会发生错误. 

1.2 举例

写个比较经典的小代码:

#include  <stdio.h>

#include  <pthread.h>

#include  <ctype.h>
#include <stdlib.h>
int total_words ;
void *count_words(void *);
main(int ac, char *av[])
{
        pthread_t t1, t2;               /* two threads */

        if ( ac != 3 ){
                printf("usage: %s file1 file2\n", av[0]);
                exit(1);
        }
        total_words = 0;
        pthread_create(&t1, NULL, count_words, (void *) av[1]);
        pthread_create(&t2, NULL, count_words, (void *) av[2]);
        pthread_join(t1, NULL);
        pthread_join(t2, NULL);
        printf("total words: %d\n", total_words);
}
void *count_words(void *f)
{
        char *filename = (char *) f;
        FILE *fp;
        int  c, prevc = '\0';
        if ( (fp = fopen(filename, "r" )) != NULL ){
                while( ( c = getc(fp)) != EOF ){
                        if ( !isalnum(c) && isalnum(prevc) )
                                total_words++;
                                prevc = c;
                }
                fclose( fp );
        } else
                perror(filename);
        return NULL;
}

这段代码用两个不同的线程来读取两个不同文件的字数并且将他们的和加起来算出总字数. 可是由于他们可以同时的进入并改变共享变量"total_words", 就会产生错误.

测试:

先创建两个文件分别是test1.txt 和 test2.txt, 他们的字数分别是 17105 和 6748.

17105 + 6748 = 23853;

但是测试结果出来却是:

由此我们可以发现,得出的结果永远 <= 正常输出! 正如我在Non-Atomic Operation(见附注1)里面说的,t1在进行total_words++这个操作的时候, 其实他进行的操作转化成Assembler Code有多行.(我还没接触过类似汇编的代码, 但是可以用gcc -s xxx.c && cat xxx.s可以看到机器码. )

极有可能发生的情况是 1. 在单CPU并发式运行的时候, 刚进行完计算"total_words + 1"并未赋值的时候发生了上下文切换,导致t2引用了计算前的共享变量.

2. 临界区(Critical Section)

2.1 临界区定义

2.2 临界区问题

临界区问题(Critical Section Problem)可以说是进程同步的一个根本问题了。他其实就是, 如何才能在一段时间内让最多一个进程来进入并修改共享变量.

如果想要解决Critical Section Problem, 就需要三个基本条件.

3. Semaphore(信号量)

3.1 定义

信号量是用来维持进程同步的一个变量，通常可被理解为一个共享资源内(比如说一段代码内)所存在的进程数。它的范围从0~Max Number of Processes(User Design)，他的范围同时也代表着在对应代码段里面的进程个数的范围。 在实现方面，通常是由wait和signal两个函数工作。 当进程完成对semaphore对象的等待之后( wait(s) )， 信号量所统计的数会减1， 当减到0后所有进程就不会允许进入Semaphore 所对应部分的代码。 当进程通过signal之后(signal(s)), 信号量所统计的数会加1，此时在wait(s)部分所被阻挡的进程就又可以进入当前代码段了。

由于开发这个玩意儿的人是Dijkstra，他是个荷兰人。 在荷兰语中，Probeer代表着try的含义，Verhoog代表着increment的意思。因此在某些代码中可以见到用wait(s) P(s) 和signal(s) V(s)。需要特别注意的一点事，这两个函数的CPU运算过程都是原子的，不然没有意义。下文会细细说。

信号量大致分为两种不同的形式(见附注2)， 我们可以通过这两种不同形式的信号量的灵活应用来解决目前所有的进程同步问题进而保证race condition的结果与预期相同。

3.2 Busy Waiting VS Blocking 信号量的两种工作方式

1. Busy Waiting(忙碌等待，又被称为自旋锁):  

在Busy waiting中，进程会不停的检查当前的锁是否可以进入(i.e.在mutex情况下，锁中的对象也就是计数器的参数是否为真)。他的实现函数的伪代码为:

wait(s){

while( s < = 0);

s --;

}

Do_Something!!

signal(s){

s++;

}

假设我们设置semaphore的初始值为3(Semaphore s = 3)， 有5个进程尝试运行这段代码。那么当有三个进程通过wait(s)之后，s下降到0。 之后的所有进程都会被卡在"while(s < = 0)"的这个真循环里面。因此假设CPU进行上下文切换(Context switch)之后运行了这三个进程之外的第四个或第五个尝试进入这段代码的进程，那么这两个进程就会不停的在这个真循环里面打转(不停地问CPU"变量s大于0了没？""妈的我转的好累啊！""还没好啊还没好啊还没好啊？")。直到里面的进程工作完出来了，那个打转的进程才能进来。

2. Blocking(阻塞):

在Blocking中，当对应资源内的进程个数达到上限时，任何其他尝试进入的进程都会被扔进Blocking Queue(就是Waiting Queue)里面，注意这个扔进是物理意义上的扔进去，等于说如果进程的访问超过上限，那么这些进程就会通过Medium-term Scheduling被转移到硬盘里面。他的实现函数的伪代码为:

wait(s){

s -> value --;

if ( s -> value < 0 ){

add this process to s -> list;

block();

}

}

Do_Something!!

signal(s){

s -> value ++;

if( s -> value <= 0 ){

remove the process from s -> list;

WakeUp();

}

}

相比于第一种，这种方法的工作原理就一目了然了。 当计数器小于0了，说明达到上限了，所有进程被扔进硬盘也就是Blocking Queue，被阻塞住。 当工作进程通过signal离开那段代码的时候， kernel就从Waiting Queue里面拎出来一个。

3. 对比

首先从代码部分来看，这两种方法所控制的信号量的变量在正常工作的情况下一个是永远大于或者等于0的(自旋锁)，一个是永远小于等于0的(阻塞)。

然后，我们通过单核与多核来对比下两者的优缺点。

在单CPU并发性运行的情况下，Busy Waiting的方式可能会让CPU不停的运行无效线程，进行无效操作。 

举个极端的例子: 假设我现在只有PA和

PB

两个进程跑一段代码。 外部有一个Mutex来控制代码段内的进程数最多为1，完成这段代码需要CPU花100 milliseconds的时间。PA的时间片是20 ms，PB的时间片是100 ms，而PA先进入了这个Critical Section(进入前所花时间不计)。那么每当PA运行了20 ms的时候就会进行一次Context Switch(上下文切换所花时间不计)把CPU使用权转换给PB。 问:PA需要话多少时间来跑完这段代码?

会花整整: 100 + 4 * 100 = 500 milliseconds; 而其中400 ms是不必要的， 由此我们可以看出在单CPU无超线程的情况下，运用busy waiting并不好，会浪费太多的CPU这个资源。 

但是如果这个例子在多核的情况下我们就可以发现， busy waiting并没有太大的影响。 因为我们可以用一个CPU来处理PA另外一个CPU处理PB。因为PA并不需要等待PB，所以依然可以在可接受范围内完成任务。

我们再看Blocking这个法子，在单核的情况下，当一个Process访问进程数已经达到上限的代码段时，这个Process会被放入Blocking Queue(硬盘)中。 因为CPU只会调用Ready Queue(主内存)里面的进程，所以这个Process不会被CPU处理，进而CPU的工作效率不会受到影响。

在多核的角度思考这两种办法，由于将进程从 Ready Queue放进Blocking Queue同样会花费不少资源与时间(设计到Medium-term scheduling，下篇文章会讲到)，所浪费的东西甚至可能大于busy waiting这种办法。所以Blocking这个法子并不是十全十美的。

最后做个小结，在单核的情况下，由于busy waiting浪费大量CPU资源，Blocking这种方法完爆他。虽然Busy waiting属于浪费资源大多数情况下应该避免让CPU在那凭空瞎B转，但是在多核的情况下， Busy Waiting处理某些任务的效率确实会比用Blocking这种办法的效率要高。所以现在在某些情况下，有的系统就会使用busy waiting，比如说Windows， 不过他会调用YieldProcessor的机制来降低CPU的损耗。

附注2:

1.为什么wait和signal这两个方程必须是原子性操作？

假设wait和signal两个操作为非原子性。两个进程需要通过一个Binary Semaphore(二元信号量)， 假设在第一个Process通过"while(s <= 0)"的时候发生了Context Switch切换到了另外一个Process，这时他们的信号量变量s还是1，因此第二个进程也可以顺利通过"while(s <= 0)"这个阶段。在这种情况下两个进程同时进入了互斥锁， 而本身互斥锁的意义就是只允许一个进程进入Critical Section。 同样的道理，Signal的计算可能由于Race Condition而导致最后的结果<=用户所设定的结果。

所以如果当Wait和Signal为非原子性操作的时候， 信号量就会失去存在的意义。

还需要注意的一点是，Semaphore本身就是需要硬件支持(hardware support)的。 比方说如果没有Intel 32位IA-32处理器的缓存加锁和总线加锁，Semaphore的wait和signal这两个函数是根本无法实现的。

2. 两种不同形式的信号量：

Binary Semaphore(二元信号): 在Linux中，二元信号其实就是在之前的Section 1 和 Section 2 所提到的Mutex(互斥锁)。在这种形式的信号量中，他所统计的数只能是0~1。 意味着当我们使用二元信号的时候，进入当前代码段的进程只有一个。 这种信号量通常用来锁住Critical Section来保证多进程状态下共享变量的正常修改。

Counting Semaphore(计数信号): 与二元信号不同的地方就是， 计数信号可以用来控制多个进程同时进入一段代码， 需要注意的是这段代码里面不能有Critical Section，如果有的话必须再加一个二元信号把Critical Section锁住。 这种锁儿大多数用来控制一段资源的最多能够承载的进程个数，但是注意，这种方法不能明确的说明进程们的运行顺序。

自己的小见解：我其实最开始觉得counting semaphore挺难理解的。 但是那天门口儿原味拉面吃饭的时候打开Quora查了查发现了一个挺有意思的小例子。就好比说一段资源就是个公共厕所。 在这公共厕所门口儿有个大妈搬个小板凳拿个小本本给那坐着。 老大妈知道厕所里面有几个马桶， 所以每当有人想进去的时候她要先想想里面的坑位还有没有。如果坑位是0了，那所有人就算再急也要门口等着。等到里面的人该搞的都搞完了，外面的人才能进去。 在这个例子里面， 老大妈就是semaphore， 马桶就是资源， 进去的人就是process。 

本来打算把几个同步的模型也贴上来，发现东西有点太多了。 所以在下篇文章打算介绍下4个经典的同步模型，Peterson's Solution, Producer&Consumer, Reader&Writer and Dining Phylosopher。 然后再说下死锁。