并发导论

感谢网友寻寒的投稿

写在前面的话
由于之前工作中的疏忽，在使用Java多线程并发的时候出了问题，遂决心全面学习并发相关知识。写作本文的意图只是希望在写作过程中把想不清楚或是一时无法掌握的地方反复揣摩记录下来。写作本文参考的各种资料较多，抱歉的是文末的参考文献中对一些叫不上名字或没有出处的资料文献并未列举出来。由于本人是初入职场的菜鸟，更是并发的门外汉，文中关于并发以及其他软硬件、程序设计语言的论据也许不够客观甚至不够正确。对于这些问题还请大家不吝指教，欢迎讨论，望共同学习进步。

1 并发

很久很久以前是没有并发这个概念的，因为那个时候操作系统并不支持多任务。现在的操作系统今非昔比，支持抢占式任务、多线程、分页、TCP/IP等现代操作系统特性。能满足用户各种各样的需求同时响应用户的不同操作，靠的是多任务系统的支持。

简单来说，多任务就是多个任务一起轮流的执行在操作系统上。这种执行方式在单处理器上给人同时执行的幻象，在多处理器上却是真正的并行。但问题是处理器的数目总是比进程数目少的多，也就是说总是有进程得不到执行。这个问题需要进程调度程序解决的。在此之前先解释下进程和线程。

在Unix时代一个进程（执行中的程序）只有一个线程，现代操作系统允许一个进程有多条线程。这里需要具体解释下线程。在Linux系统上可以将线程当做进程看待（Linux确实这么实现的，虽然有些许区别）。虽然这与Windows和Solaris等实现完全不同的是它们都有一套专门应对线程的不同于进程的调度程序。不过这样会很好理解许多问题，如：每个线程有独立栈空间、寄存器、程序计数器（存放下一条执行指令）。

操作系统调度程序调度的是线程（在本文中提到线程的地方都指的是操作系统级的线程），并非进程。也就是说线程才是调度的基本单位。那么线程是如何被调度的或者说调度程序是如何工作的？

操作系统的调度程序决定哪条线程正在使用处理器。支持抢占式多任务的操作系统采用一种时间分片的机制，也就是给每个线程一个时间段，在此期间可以使用处理器，直到用完时间片。当然这种机制欠缺灵活性，所以大多数操作系统使用两个关键因素，优先级和时间片决定调度。为了更好的的理解调度程序的具体工作屏蔽一些细节，我们笼统的称操作系统调度方式为根据时间片调度（虽然Linux系统并不采用此方法，而是采用一种特殊方式：Nice和处理器占比）。
现代操作系统可以同时运行着多个任务，表面并不互相干涉（但存在潜在的交互）。我们将此称之为并发（Concurrency）。

那么为什么需要并发呢？
如果只有一个线程的情形。首先，在单处理器系统中，一个处于运行状态的IO消耗型程序，例如一个网络读取阻塞或用户输入阻塞导致处理器出现空闲，在视处理器为昂贵资源的情形下，这是巨大的浪费。然后，在对称处理器中（SMP），因为只有一个线程，那它只能在其中一个处理器上运行，也就是说剩余的处理器被白白浪费。如果使用多线程，不仅能充分利用多处理器，还能通过线程并发解决上述IO消耗程序中处理器空闲问题。

2 同步

开始讲同步之前先帮12306设计一个抢票系统，功能简单：用户来订票，12306系统从总票中取出一张（如果票还没卖光），并且让总票数减-1，然后把票交给用户。它的实现代码如下：

int total = get_total_from_tickets();
if ( total < 1) {
    not_found("No tickets!";);
    return FAILURE;
}
/*以上为步骤一*/

ticket tk = get_ticket_from_tickets();
--total;
/*以上为步骤二*/

split_ticket2user(tk);
/*步骤三*/

我们假设一次执行单元为其中一个步骤，但是这样的系统是不能使用的，因为它只能支持同时一个用户抢票。想象一下多个用户同时抢票的简单情形：系统中只剩一张票了，用户A先开始抢票，整个过程是这样的：A先看还有一张票，也就是步骤一。此时，用户B使用了抢票插件，如有神助的在A完成步骤一尚未进行步骤二的时候完成了步骤一，这个时候无论A和B谁先执行步骤二都意味只有一个人能抢到票。
导致上述事例结果的根本原因在于数据没有及时更新，即数据同步不及时。多线程下的具体情形可能是一个运行中的线程随时可能在它正在使用临界区（放置临界资源的区域）的时候被抢占，而新调度的线程紧接着进入该临界区，这个时候就会发生竞争。如果是在对称处理器多线程下，就算一个线程能完整的完成它的任务而不被抢断，但多处理器真正并行使得多条线程可以同时修改临界区，这使得及时同步数据变得非常困难。采用同步可以确保每条线程看到的数据是一致的。尤其是一条线程在修改某一个值而其他线程也需要读取或修改这个值的时候，使用同步就可以保证访问的数据有效。
这里介绍两种主要的解决同步问题的方式：一是原子操作，二是加锁。
原子即不可分割，原子操作就是中间不能停顿，一步到位。这里举一个用原子操作解决多线程下同步问题的简单例子：
C代码：++i; 的AT&T汇编如下：

movl i(%rip), %eax
addl $1, %eax
movl %eax, i(%rip)

顺便提一句，大家经常争论的i++和++i的效率问题，单条语句中出现i++和++i的情形，汇编指令是相同的，就是如上的汇编代码。而和其他赋值语句同行的情形中i++比++i少一条指令，C/C++主张偏向于++i，Java倾向于i++。
简单描述下上面的汇编操作：
1）读取当前变量i并把它赋值给一个临时寄存器;
2）给临时寄存器+1;
3）把eax的新值写回内存。
我们可以清楚看到C代码只需要一句，但编译成汇编却需要三步（这里不考虑编译器优化，实际上通过编译器优化可以将这三条汇编指令合并成一条）。和上述抢票类似，导致的问题显而易见，但是解决方案也简单。按照原子操作解决同步问题方式：依靠处理器原语支持把上述三条指令合三为一，当做一条指令来执行，保证在执行过程中不会被打断并且多线程并发也不会受到干扰。这样同步问题迎刃而解，这也就是所谓的原子操作。但事情总不会都如此简单，并且处理器没有义务为任意代码片段提供原子性操作，尤其是我们的临界区资源十分庞大甚至大小不确定，处理器没有必要或是很难提供原子性支持。这个时候加锁机制就出现了。
锁，和现实中的门把锁有相同也有不同。我们把线程看做人，屋子是临界区，里面放的是东西是临界资源。每次只允许一个人进入屋子，当某个人进入屋子后会把门锁上，当另一个人想进入屋子的时候，只能在门口等待（这里等待的方式有两种：忙等待，即循环查看是否屋子的人出来了。还有一种是先睡一觉，等屋子里的人出来叫醒自己）。直到屋子里的人解锁出来，这个时候在门口等待的人才可以进去。这里有一个关键点需要保证：锁必须是原子性操作实现，决不能中途打断，由处理器原语支持。锁的意义在于将操作做为一个执行单元以一种原子方式执行而不被打断，多线程下也不会互相干扰。但是锁会影响性能，这是因为一个加锁的临界资源在被访问前必须获取对应的锁，获取该锁的线程将以独占的方式访问临界区。如果此时有其他线程同时访问临界区，则会因为无法获取这个锁而阻塞，显然，在临界区强行通过加锁使线程执行串行化是需要牺牲一定的性能的。

3 内存模型

用原子操作和锁来保证同步的正确性看似简单，但背后的实现却非常复杂。理解同步背后的具体实现相当重要，这涉及到并发的高级话题——内存模型。
在多处理器下，多个处理器共享主存。为了效率并不要求处理器将更新立即同步到主存上。处理器拥有自己的缓存以保存这些更新，并且定期与主存同步。这种需要定期同步的方式是为了保证缓存一致性（Cache Coherence）。在缓存一致性许允许的范围内，多个处理器可以拥有同一个共享数据的不同状态。内存模型提供了一种保证：规定共享数据在不同线程间的状态总是一致的。它的复杂性在于要协调处理器和编译器在与多线程程序执行时的性能与数据同步状态之间的平衡。处理器和编译器的工作是通过优化指令执行顺序添加缓存来加快指令执行速度。内存模型采用一组屏障指令来保证存储的一致性，当然是在尽可能少的牺牲性能的前提下。具体的编译器和处理器加快指令执行的方法是代码重排、指令重排以及缓存。内存模型利用处理器提供的一组指令来保护数据一致性，这种方式称为内存屏障（Memory Barriers）。下面一一介绍。
3.1 代码重排
代码重排是指编译器对用户代码进行优化以提高代码的执行效率，优化前提是不改变代码的结果，即优化前后代码执行结果必须相同。
先来看段C代码：

int a = 1, b = 2, c = 3;
void test() {
    a = b + 1;
    b = c + 1;
    c = a + b;
}

在gcc下的汇编代码test函数体代码如下：
编译参数： -O0

movl b(%rip), %eax
addl $1, %eax
movl %eax, a(%rip)
movl c(%rip), %eax
addl $1, %eax
movl %eax, b(%rip)
movl a(%rip), %edx
movl b(%rip), %eax
addl %edx, %eax
movl %eax, c(%rip)

编译参数：-O3

movl b(%rip), %eax                  ;将b读入eax寄存器
leal 1(%rax), %edx                  ;将b+1写入edx寄存器
movl c(%rip), %eax                  ;将c读入eax
movl %edx, a(%rip)                  ;将edx写入a
addl $1, %eax                       ;将eax+1
movl %eax, b(%rip)                  ;将eax写入b
addl %edx, %eax                     ;将eax+edx
movl %eax, c(%rip)                  ;将eax写入c

我在-O3的汇编下做了详细的注释，参照注释和原C代码理解这两段汇编代码应该不难。当然编译器优化并没有做多少工作，这是因为并未有多少无用代码。但是如果我们的test函数体内只写了100行的a++; 那汇编指令使用-O1就会优化这100行代码成一条：

addl $100, a(%rip)

然而，上面的代码更有意义来说明编译器优化并且其中将后面可能用到的汇编指令做了清楚的注释以说明其含意，便于下文对汇编代码的理解。如果觉得上述代码的指令重排难于理解或是不够充分，接下来看这段C代码和gcc -O3下的汇编代码：

int a = 1, b = 2;
void test1() {
    a = b + 1;
    b = 39;
}

movl b(%rip), %eax ;读取b给eax
movl $39, b(%rip) ;向b写入39
addl $1, %eax ;eax+1
movl %eax, a(%rip) ;将eax写回a

很显然b先被赋值，然后才是a。也就是说在该函数中，代码的执行顺序发生了变化，但却不影响最终结果。编译器重排是根据指令之间是否有数据依赖关系来决定的，虽然看似C代码间存在依赖，但是重排却是指令级别的。顺便分析下这里为什么会把b的赋值操作提前进行呢？寄存器读入b的值时对b进行缓存，再写入的时候直接从寄存器缓存中取出赋值避免了再次从高速缓存甚至主存中取出b再赋值。可以动手写实验代码验证，很容易发现确实编译器会将相关变量的操作提取到一起执行，这是因为处理器充分利用寄存器缓存来加速指令执行。

3.2 指令重排
大多数主流的处理器为了效率可以调整读写操作的顺序，但为什么这么做呢？处理器在执行指令期间，会把指令按照自适应处理的最优情形进行重新排序，使指令执行时间变得更短（绝大多数情形下，前提是不改变程序的执行结果）。处理器的具体做法是优化其指令流水线（Instruction pipeline）以减少指令执行时间。
我们假设在一条简单的流水线中，完成一个指令可能需要5层。对于一些并不互相依赖的指令，要在最佳性能下运算，当第一个指令被运行时，这个流水线需要运行紧接着的4条独立的指令。如果有指令依赖前面已经执行的指令，那处理器就会通过某种方式延缓该条指令执行直到依赖的指令执行完毕。使用多个层执行指令，处理器可以显著提高性能从而减少指令运行所需要的周期。处理器使用这种优化Pipeline的方式一方面提高了指令执行效率，但另一方面却出现了另一个麻烦。单处理器下执行指令调整顺序在多线程并发的时候出现了困难。我们假设有两个处理器，每一个处理器执行一条线程，对于涉及到同一段代码对非局部变量赋值的顺序会因为的每一个处理器对各自指令顺序调整而变得混乱。
看下启动服务器的示例代码：
全局：bool enable = false;

void start_server() {
    open_server();
    enable = true;
}

void http_server() {
    if(enable) handle_request();
}

我们使用两条线程在多处理器下并发，一条线程A负责启动服务器start_server(),另一条线程B负责处理http请求。由于上述所说的处理器会将互不依赖的两条指令调换顺序（这里暂且忽略编译器优化），我们有理由相信会出现这样的情形：A线程：enable = true;已经执行，但open_server();还未调用。此时另一条线程B执行http_server();发现服务可用，直接使用未打开的服务器来处理请求。
同样的我们如果在此忽略处理器重排，只使用编译器的代码重排也会导致上述问题。问题的复杂性在于编译器和处理器同时作用下，指令的执行顺序更加神秘莫测。但更糟糕的是还有一种为了效率缓存指令执行结果使数据不能及时更新的因素影响数据同步，这个因素就是CPU Cache。
3.3 CPU Cache（高速缓存）
A trip to main memory costs hundreds of clock cycles on commodity hardware. Processors use caching to decrease the costs of memory latency by orders of magnitude.
——Dennis Byrne
上面这句话的大体意思是说对内存的一次访问需要花费数百个时钟周期，处理器使用缓存减少内存延迟的成本。这就是引入缓存的原因。CPU内部结构根据物理距离依次是：处理器、寄存器、CPU Cache。我根据自己机器上的CPU Cache的信息用cacoo画了一个简单版本的CPU内部结构图：

参照上图，由于既要满足存储容量需求又要满足CPU的高速存取需求，目前的缓存被设计为多级L1, L2 。。。。。。Ln。每一级的访问周期比上一级多一个数量级（并不绝对）。L1靠近处理器，用以满足高速存取的需求，Ln靠近主存，容积随之变大。目前主流是三级缓存。Linux下查看CPU Cache可以进入/sys/devices/system/cpu/cpu0/cache，例如我的机器下查看高速缓存类型的结果：

lunatic@ubuntu:/sys/devices/system/cpu/cpu0/cache$ cat -n index0/type index1/type index2/type index3/type
• 1 Data //L1, Data Cache
• 2 Instruction //L1, instruction Cache
• 3 Unified //L2，代表不共享
• 4 Unified //L3，代表不共享

处理器缓存执行指令结果于自己的cache上，等满足一定条件如遇到请求刷新的指令，再将缓存结果一并输出。
用一段挂起服务器的代码就可以看出缓存对数据同步的影响：
全局：Bool enable = true;

void halt_server() {
    enable = false;
    close_server();
}

void http_server() {
    if(enable) handle_request();
}

还是双核双线程模拟执行的情形：线程A执行服务器挂起操作，但因为CPU缓存影响，服务器已经挂起，但并未同步更新到全局enable。而另一条线程B检测到enable可用时，就继续提供请求处理服务导致出现一个已经关闭的服务器还提供服务的情形。
对于处理器使用高速缓存以追求效率的解释可以通过对C语言标准库的IO缓冲分析来解释。C语言的IO输出默认有三种缓冲方式：无缓冲、行缓冲和块缓冲。我们以printf（默认行缓冲）说明，printf函数的作用是将格式化后的字符逐个发送到输出缓冲区，缓冲区被刷新直到遇到换行符。这样做无疑能提高效率，并且延迟了写输出。再来看输入scanf，从键盘缓冲区读取非空白字符数据，而把换行符’/n’遗留在缓冲区，引发的问题是如果同时用getchar、gets等不会忽略’/n’的函数读取，就只能读取到无意义的’/n’。C语言IO系统的读入写出和处理器缓存非常类似。因此，解决C语言缓冲区导致数据不一致的方案可以帮助理解处理器的缓存处理。C语言使用fflush函数或其他类似功能函数在必要的时候刷新或者清空缓冲区。处理器在缓存处理上采取类似的做法，但远比其复杂的是处理器要同时兼顾指令缓存以及指令排序还有其他影响到数据同步的各方面软硬件因素，这种多方兼顾的方式就叫做内存屏障。
3.4 内存屏障（Memory Barriers）
现在我们来谈下多处理器下的共享内存数据同步问题。多处理器同时访问共享主存，每个处理器都要对读写进行重新排序，一旦数据更新，就需要同步更新到主存上（这里并不要求处理器缓存更新之后立刻更新主存）。在这种情况下，代码和指令重排，再加上缓存延迟指令结果输出导致共享变量被修改的顺序发生了变化，使得程序的行为变得无法预测。为了解决这种不可预测的行为，处理器提供一组机器指令来确保指令的顺序要求，它告诉处理器在继续执行前提交所有尚未处理的载入和存储指令。同样的也可以要求编译器不要对给定点以及周围指令序列进行重排。这些确保顺序的指令称为内存屏障。具体的确保措施在程序语言级别的体现就是内存模型的定义。POSIX、C++、Java都有各自的共享内存模型，实现上并没有什么差异，只是在一些细节上稍有不同。这里所说的内存模型并非是指内存布局，特指内存、Cache、CPU、写缓冲区、寄存器以及其他的硬件和编译器优化的交互时对读写指令操作提供保护手段以确保读写序。将这些繁杂因素可以笼统的归纳为两个方面：重排和缓存，即上文所说的代码重排、指令重排和CPU Cache。简单的说内存屏障做了两件事情：拒绝重排，更新缓存。
C++11提供一组用户API std::memory_order来指导处理器读写顺序。Java使用happens-before规则来屏蔽具体细节保证，指导JVM在指令生成的过程中穿插屏障指令。
内存屏障也可以在编译期间指示对指令或者包括周围指令序列不进行优化，称之为编译器屏障，相当于轻量级内存屏障，它的工作同样重要，因为它在编译期指导编译器优化。屏障的实现稍微复杂一些，我们使用一组抽象的假想指令来描述内存屏障的工作原理。
使用MB_R、MB_W、MB来抽象处理器指令为宏：
MB_R代表读内存屏障，它保证读取操作不会重排到该指令调用之后。
MB_W代表写内存屏障，它保证写入操作不会重排到该指令调用之后。
MB代表读写内存屏障，可保证之前的指令不会重排到该指令调用之后。
这里用一个例子描述在多线程并发中使用内存屏障的意义：
全局变量：bool has = false, Ticket t = NULL;

Thread A                                                                Thread B
has = has_remain_ticket();/*有票*/             -------------------
mb();/*表示在该处插入MB指令 */               if(has) {;
--------------- --------------- --------------- ------  t = get_a_ticket();
--------------- --------------- --------------- ------  to_user(t);
--------------- --------------- --------------- -------------- }

用两条线程A、B执行，A中加入的内存屏障有票，再通知用户，不会发生先通知用户，再去看有票。B中的内存屏障保证必须取到票再交给用户，防止尚未取票，就交给用户。
这些屏障指令在单核处理器上同样有效，因为单处理器虽不涉及多处理器间数据同步问题，但指令重排和缓存仍然影响数据的正确同步。指令重排是非常底层的且实现效果差异非常大，尤其是不同体系架构对内存屏障的支持程度，甚至在不支持指令重排的体系架构中根本不必使用屏障指令。具体如何使用这些屏障指令是支持的平台、编译器或虚拟机要实现的，我们只需要使用这些实现的API（指的是各种并发关键字、锁、以及重入性等，下节详细介绍）。这里的目的只是为了帮助更好的理解内存屏障的工作原理。
内存屏障的意义重大，是确保正确并发的关键。通过正确的设置内存屏障可以确保指令按照我们期望的顺序执行。这里需要注意的是内存屏蔽只应该作用于需要同步的指令或者还可以包含周围指令的片段。如果用来同步所有指令，目前绝大多数处理器架构的设计就会毫无意义。

4 并发中的名词和锁

并发程序依然非常复杂，虽然有众多平台和语言的支持。它们提供一组并发的API来简化并发，并在编译或者运行期根据这些API或者规则穿插屏障指令来正确同步代码以保证程序的执行与预想的一致。接下来我们介绍并发程序在众多平台和语言上比较通用的几个概念。
Volatile
原意是易变的。在计算机领域意思相同，指由该关键字修饰的变量的值易变，因此具有可见性。可见性是指当一个线程对临界资源进行修改后，在其他线程中可以看到发生的变化。为了实现这种可见性，处理器和编译器忽略对该关键字修饰变量的优化，也就是不对它进行重排，也不会缓存。但该变量的使用却是非常危险的，因为它的行为总是违反我们的直觉。具体原因有以下几方面：
虽然编译器不去对它进行优化，并且阻止volatile变量之间的重排（如C/C++和Java）。但是，它们可能和非volatile变量一起被重排序。在C/C++和早期Java内存模型中确实是这么实现的。Java在新的内存模型下，不仅volatile变量不能彼此重排序，而且volatile周围的普通字段的也不再能够随便的重排序了（和旧模型不同），但是C/C++的volatile却并未支持。还有一点容易让人误解的是它并不具有原子性这也是最容易犯错的地方。最后一点也是最能让使用者谨慎使用的理由是某些编译器或者是陈旧的Java虚拟机对该关键字的支持不完整。也许使用volatile最安全的方式是严格限制到只是一个boolean值并且是在完全与周围变量或操作无关的场合。但不能放弃使用volatile的原因是在如今的处理器架构下，内存模型强大到处理器对volatile的操作性能和非volatile相差无几。
自旋锁
Linux内核中最常见的锁，作用是在多核处理器间同步数据。这里的自旋是忙等待的意思。如果一个线程（这里指的是内核线程）已经持有了一个自旋锁，而另一条线程也想要获取该锁，它就不停地循环等待，或者叫做自旋等待直到锁可用。可以想象这种锁不能被某个线程长时间持有，这会导致其他线程一直自旋，消耗处理器。所以，自旋锁使用范围很窄，只允许短期内加锁。其实还有一种方式就是让等待线程睡眠直到锁可用，这样就可以消除忙等待。很明显后者优于前者的实现，但是却不适用于此。我们来详细分析。如果我们使用第二种方式，我们要做几步操作：把该等待线程换出、等到锁可用在换入，有两次上下文切换的代价。这个代价和短时间内自旋（实现起来也简单）相比，后者更能适应实际情况的需要。还有一点需要注意，试图获取一个已经持有自旋锁的线程再去获取这个自旋锁或导致死锁，但其他操作系统并非如此。
互斥锁
即对互斥量进行分加锁，和自旋锁类似，唯一不同的是竞争不到锁的线程会回去睡会觉，等到锁可用再来竞争，第一个切入的线程加锁后，其他竞争失败者继续回去睡觉直到再次接到通知、竞争。互斥锁算是目前并发系统中最常用的一种锁，POSIX、C++11、Java等均支持。处理POSIX的加锁比较普通外，C++和Java的加锁方式很有意思。C++中可以使用一种AutoLock（常见于chromium等开源项目中）工作方式类似auto_ptr智能指针，在C++11中官方将其标准化为std::lock_guard和std::unique_lock。Java中使用synchronized紧跟同步代码块（也可修饰方法）的方式同步代码，非常灵活。这两种实现都巧妙的利用各自语言特性实现了非常优雅的加锁方式。当然除此之外他们也支持传统的类似于POSIX的加锁模式。
读写锁
支持两种模式的锁，当采用写模式上锁时与互斥锁相同，是独占模式。但读模式上锁可以被多个读线程读取。即写时使用互斥锁，读时采用共享锁，故又叫共享-独占锁。一种常见的错误认为数据只有在写入时才需要锁，事实是即使是读操作也需要锁保护，如果不这么做的话，读写锁的读模式便毫无意义。
重入
也叫做锁递归，就是获取一个已经获取的锁。不支持线程获取它已经获取且尚未解锁的方式叫做不可递归或不支持重入。带重入特性的锁在重入时会判断是否同一个线程，如果是，则使持锁计数器+1（0代表没有被线程获取，又或者是锁被释放）。C++11中同时支持两种锁，递归锁std::recursive_mutex和非递归std::mutex。Java的两种互斥锁实现以及读写锁实现均支持重入。POSIX使用一种叫做重入函数的方法保证函数的线程安全，锁粒度是调用而非线程。
死锁
线程在执行过程中等待锁释放，如果存在多个线程相互等待已经被加锁的资源，就会造成死锁。大多数语言的锁实现都支持重入的一个重要原因是一个函数体内加锁的代码段中经常会调用其他函数，而其他函数内部同样加了相同的锁，在不支持重入的情况下，执行线程总是要获取自己尚未释放的锁。也就是说该条线程试图获取一个自己已经获取而尚未释放的锁。死锁就此产生。还有最经典的哲学家就餐问题。
线程饥饿
互斥锁中提到获取不到锁的线程回去睡眠等待下一次竞争锁，如果下一次仍然得不到，就继续睡眠，这种持续得不到锁的情况我们称之为饥饿。一个很有意思的例子是关于小米手机饥饿营销的。将小米手机比作竞争资源，抢手机的用户就是线程，每次开抢都抢不到的用户就是线程饥饿。和饥饿相对的是公平，操作系统调度程序负责这种公平，使用分片或nice或执行比等方式避免得不到调度的线程活活饿死。Java默认采用非公平的互斥锁（synchronized是强制的，Lock是可选的。关于Java内置锁和Lock锁的公平性讨论参见：Java中的ReentrantLock和synchronized两种锁定机制的对比），但是公平锁因为要防止饥饿需要根据线程调度策略做调整，所以性能会受到影响，而且一般情况下某条线程饿死的情况鲜有发生（因为调度本来就是不公平的），因此默认都是非公平的。
CAS（Compare – And – Swap）
中译名比较交换。目前有一种特殊的并发方式叫做无锁并发，通过上文的说明大家应该马上清楚要使用CAS达到正确同步须由处理其提供支持。有一个叫做Lock_Free的算法提出了一种方案：确保执行它的所有线程中至少有一个能够继续往下执行。实现这个算法的技术叫做比较并交换，即CAS。CAS使用乐观技术来更新值，如果在另一条线程更新了这个值，CAS可以检测到这个错误。现在大多数处理器架构（包括IA32和Sparc）都支持比较并交换CAS的原子操作，X86下对应的是 CMPXCHG 汇编指令。CAS 原语负责将某处内存地址的值（1 个字节）与一个期望值进行比较，如果相等，则将该内存地址处的值替换为新值，CAS 操作用一行C代码描述如下：
return *add == old_val ? (*add = new_val) ? false;
目前windows内置、Gcc内置、C++11定义头文件和Java通过java.util.concurrent.atomic包提供对CAS操作的支持。

5 并发总结

并发相关的知识概念已经介绍完了，涉及的面非常广，从多任务到操作系统调度，从处理器到CPU架构，从多级缓存到内存共享，从编译器优化到指令重排，从内存模型到内存屏障，最后对并发在Linux Kernel、C/C++（POSIX）以及Java等支持并发的平台或高级程序设计语言中涉及到的关键字以及各种锁做了具体介绍。
并发编程非常复杂，就仅仅是构建正确的并发程序而言。因为它涉及到操作系统、处理器等各种软硬件在正确的前提下进行复杂的协作的工作。现在的高级程序设计语言都提供成熟的并发API来减轻这项复杂的工作，代价是在背后做更多的事情。我无意于过程与面向对象之争，但不得不说面向对象可以简化并发，抽象出更简单的API。C++11版加入了线程支持，这是他们的宿愿（这里指把boost库中的对于线程的支持部分纳入语言标准），却花了十年的时间，但他们仍然这么做就足以证明使用OO思想来更好的实现并发是值得的。Java一开始就支持线程，它对线程的发展远快于C++，并且正不断把并发框架化以支持更多处理器以及更复杂并发模型（Java 7的Fork/Join框架希望将来能够支撑数百个CPU，并试图挑战1000核）。按照并行计算专家Doug Lea的话来说，这已经不只是技术问题，而是艺术问题了。对于艺术的讨论当然遥不可及，对于Doug Lea大师只能高山仰止了。然，终究初涉并发，水平有限，尚不能寻到艺术之门，行文就止于此吧。

参考文献：

• 《操作系统:精髓与设计原理》
• 《Linux Kernel Development》第三版
• 《Java并发编程实战》
• 《Unix环境高级编程》
• 《深度探索C++对象模型》
• CPU Cache: http://en.wikipedia.org/wiki/CPU_cache
• 上下文切换：http://en.wikipedia.org/wiki/Context_switch