起因
并发编程最基本的问题就是：我们希望有一些指令能够原子化的执行，但是由于单处理器上的中断(或者多个线程在多处理器上并发执行)，我们很难做到。接下来我们来学习锁(lock)，直接解决这个问题。
最基本的锁
举个例子，假设我们的临界区只是为了更新一个共享变量
balance = balance + 1，当然也可以是别的操作，如给链表加一个元素等。为了给我们的临界区加上锁，我们需要增加一些代码锁就是一个变量，我们需要先声明某种类型的锁变量(lock variable，如上一章的mutex)才能使用。这个锁变量会保存锁的状态。
锁的状态只有两种
- 可用(available/unlocked/free)
- 不可用(acquired/locked/held)
锁变量可能还会记录一些其它信息，如持有锁的进程，请求获取锁的线程队列，但是这些信息会隐藏起来，锁的使用者不会发现。
lock()和 unlock()函数的语义很简单。调用 lock()尝试获取锁，如果没有其他线程持有锁(即它是可用的)，该线程会获得锁，进入临界区。这个线程有时被称为锁的持有者(owner)。 如果另外一个线程对相同的锁变量(本例中的 mutex)调用 lock()，因为锁被另一线程持有，该调用不会返回。这样，当持有锁的线程在临界区时，其他线程就无法进入临界区。
锁的持有者一旦调用 unlock()，锁就变成可用了。如果没有其他等待线程(即没有其他线程调用过 lock()并卡在那里)，锁的状态就变成可用了。如果有等待线程(卡在 lock()里)， 其中一个会(最终)注意到(或收到通知)锁状态的变化，获取该锁，进入临界区。
锁为程序员提供了最小程度的调度控制。我们把线程视为程序员创建的实体，但是由操作系统调度，具体方式由操作系统选择。
锁的出现让程序员获得一些控制权。通过给临界区加锁，可以保证临界区内只有一个线程活跃。锁让原本由操作系统调度的混乱状态变得更为可控。
Pthread锁
POSIX库将锁称为互斥量(mutex)，因为它被用来提供线程之间的互斥。POSIX的lock和unlock函数都需要传一个变量，因为我们可以用不同的锁来保护不同的变量。这样可以增加并发，通常我们会用不同的锁来保护不同的数据和结构，从而允许更多的线程进入临界区。
实现一个锁
目前我们已经对锁有了一定的了解，那我们该如何实现一个锁呢？需要什么硬件支持？需要什么操作系统支持？
现在，各种计算机系统结构的指令集都增加了一些不同的硬件原语，我们不研究这些指令是如何实现的(这属于计算机体系结构课程的主题)，只研究如何用它们实现像锁这样的互斥原语。
在实现锁之前，我们先明确目标，怎样的锁才能达到标准，我们可以先设立一些标准
- 提供互斥(mutual exclusion)。最基本的，锁需要能够阻止多个线程进入临界区。
- 公平性(fairness)。当锁可用时，是否所有竞争的线程都有相同的机会抢到锁，是否有些线程会饿死(starve)，一直无法获得锁？
- 性能(performance)。使用锁之后增加的时间开销。有多种情况要考虑。
- 没有竞争的时候，只有一个线程抢锁，释放锁的开支如何？
- 多个线程在一个CPU上竞争，性能如何
- 多个线程在多个CPU上竞争，性能又如何
控制中断方式
这是最早的互斥解决方案之一，就是在临界区关闭中断(很简单粗暴)，这种方案只是为单处理器系统上开发的。如下:
这种方案通过在进入临界区之前关闭中断(使用特殊的硬件指令)，可以保证在临界区执行时不会被中断，从而实现原子化。在结束之后，再将中断打开。
这个方案的优点是简单，易理解，中断不会被发生，线程可以确信它的代码会一直执行，不会被其它线程干扰。
缺点：
- 所有的线程都有权执行特权操作(打开关闭中断)，这是很危险的。这可能会被有些程序滥用。有些恶意程序可能会在它开始时就调用lock()，从而一直独占处理器，而且它还不会去调用unlock。如果程序还出现死循环，那就更加难受了。出现死循环的话就只能重启系统，因为操作系统没法重新获取掌控权了。
- 这种方案不支持多核处理器。当多个线程进入到多个不同的CPU时，那么每个线程都会进入到同一个临界区，关闭中断不起作用(只会关闭当前CPU核心的中断)。目前多核CPU应用广泛，因此这个方案不是最优解。
- 关闭中断可能会导致CPU丢失一些信息。如磁盘设备完成了I/O读取，但是CPU却错过了这条消息，那么操作系统就永远不会去唤醒等待读取的进程。
- 效率低，关闭中断和打开中断会比常规的指令执行的更慢。
基于这些原因，只有在极少数情况下才会使用关闭中断的方式来实现互斥原语。如操作系统自身可能会用这种方式来屏蔽中断，保证访问自己数据结构的原子性，或避免一些复杂情况下的中断处理情况。
测试并设置指令(原子交换 TAS)自旋锁
有些操作系统提供了一些指令，可以来实现互斥原语，这个指令有不同的名字，在SPARC上，叫做ldstub(load/store unsigned byte，加载/保存无符号字节)；在x86上，叫xchg (atomic exchange，原子交换)指令。但是它们都是做相同的事情，一般叫做测试并设置指令(
test-and-set)。如下代码这段代码实现的很巧妙，它主要是将锁设置为新的值，并将旧的值返回。且这些代码是原子性(atomically)的执行。这段代码既可以测试旧值(旧值返回给调用者做判断)，同时还会设置新值，所以这条指令叫做”测试并设置”。通过这条指令我们就可以实现一个简单的自旋锁(spin lock)了，如下代码所示
我们理解下为什么这个锁可行，现在假设一个线程正在运行，调用lock()，没有其它线程在执行，所以flag是0，当调用
TestAndSet(flag, 1)时，返回0，线程会跳出while循环，且原子性的将flag设置成1，表示锁已经被占用了。当线程将锁释放时，调用unlock()将flag设置成0。还有一种情况是这个锁已经被占用了(即flag为1)，那么当前线程调用lock，接着调用
TestAndSet(flag, 1)会返回1，那么就会进入while循环，当前线程会自旋，只要锁一直被占用，那么就会一直返回1。当flag变成0时，当前线程会调用TestAndSet(flag, 1)将其原子性的设置成1，从而拿到锁，进入临界区。将测试(test 旧的锁值)和设置(set 新的值)合并为一个原子操作之后，我们保证了只有一个线程能获取锁。这就实现了一个有效的互斥原语!
这种锁就叫做自旋锁(spin lock)，这是最简单的一种锁，一直自旋，通过CPU的周期判断，直到锁可用。在单处理器上，需要抢占式调度器(preemptive scheduler, 即不断通过时钟中断一个线程，运行其它线程)。否则，自旋锁在单CPU上无法使用，因为这个自旋线程会一直占用CPU。
当我们实现完这个自旋锁之后，我们再来用之前的规则来评价一下这个自旋锁，首先是正确性(correctness)；需要保证同一时间只有一个线程进入临界区。
下一个标准是公平性(fairness)。自旋锁没办法保证等待线程的公平性。自选的线程在竞争条件下可能会永远自旋。因此自旋锁没有公平性，可能会导致饿死。
最后一个是性能(performance)。关于自旋锁的成本，我们要在在单处理器和多核处理器上分开考虑。
自旋锁在单CPU上，性能开销相当大。假设现在有一个持有锁的进程在进入临界区之后，调度程序调度了其它线程，那么在一个时间片内调度的线程就会一直竞争这把锁，浪费CPU周期。
但是在多核CPU上，自旋锁的性能很不错(线程数和CPU核心数差不太多的情况)。假设线程A在CPU1，线程B在CPU2上。当线程A持有锁的时候，线程B就会一直自旋(在CPU2上)。而且，临界区一般都会很短，所以锁很快就会可用，线程B就获得锁。当一个线程在其中一个CPU上自旋等待其它处理器上的锁，并没有浪费太多CPU周期，因此效果不错。
比较并交换 (CAS)
还有些操作系统提供了一些硬件原语，即比较并交换指令(SPARC系统中是
compare-and-swap, x86系统是compare-and-exchange)。下面是这条指令的c语言伪代码比较交换的基本思路是检测ptr指向的值是否和expected(预期值)相等。如果是，则更新ptr所指向的值为新值。如果不是，则什么都不做。而无论是哪种情况，都会将ptr原来的值返回给调用者判断。
通过这个比较并交换指令，我们也可以实现一个锁，类似测试并设置那样，如下：
我们只需要修改lock函数的代码，其它的代码和测试并设置一样。我们可以发现比较并交换比测试并设置更强大，后续在学习无等待同步(wait-free synchronization)时可以体现。但是如果只是用它来实现一个简单的自旋锁，它的行为和上面的(测试并设置)等价。
链接加载和条件存储指令
有些平台提供了临界区的一对指令。例如MIPS架构中，链接的加载(load-linked)和条件式存储(store-conditional)它是配套使用的，可以实现其它方式的并发结构。Alpha、PowerPC和ARM都有类似的指令，如下是这些指令的c语言伪代码
这对指令，刚开始有些难以理解，只需要记住，这两个指令是为了解决这两指令中间出现了中断，然后其它线程又去修改了锁。
通过这对指令，我们又可以实现一个自旋锁，如下是对应的代码：
现在我们来理解一下，StoreConditional失败的场景是怎样的，假设现在有两个线程A和B，A线程进入lock代码执行了链接加载指令LoadLinked()返回0。
此时，发生了中断，B线程也进入了lock代码执行链接加载指令LoadLinked()也返回0，接着B线程去执行条件更新StoreConditional()获取这把锁，此时自然是成功的，因为B线程在执行LoadLinked后一直到StoreConditional都没有其它线程去修改这个锁。
随后又发生了中断，调度程序选中了A线程，A线程继续执行条件存储StoreConditional()，这个时候会失败(因为B线程已经执行过条件更新)，因此A线程则又会去尝试获取这把锁。
在几年前的课上，一个本科学生David Capel写了个更简洁的实现
获取并增加
这种方案可以保证所有线程都能够被调度到，这个硬件原语叫获取并增加(fetch-and-add)，它可以原子性的返回特定地址的旧值，并且让该值自增1。
我们会用获取并增加指令，实现一个更有趣的ticket锁，这个是Mellor-Crummey 和 Michael Scott提出的，如下是对应的c语言伪代码
这个方案用了两个变量，
ticket和turn来构建锁，它的想法也很简单，举一个好理解的例子，临界区类似于公共服务窗口，线程类似于排队办理业务的人。如果一个线程想要获取锁，它会调用fetchAndAdd获取ticket并将其原子性的加1。它会返回一个旧值(这个旧值就类似于当前线程排队的号码牌(turn，顺位))。而全局的&lock->turn类似于服务窗口当前叫到的号，当这两个号相等时(myturn == turn)，则表示轮到当前线程了，这个线程就可以进入临界区了。
当前线程在临界区结束后需要调用unlock()，它会将全局的turn加1，类似于手动将全局的号码牌加1，那么下一个等待线程就可以进入临界区了。
简单方法：将CPU让出来
基于硬件的锁很简单(上述的互斥原语)，但是在某些场景下，这些解决方案会效率低下。试想一下，A和B两个线程都运行在单处理器上，当A线程持有锁的时候，出现了中断，调度程序选中了B线程，B线程去尝试获取锁，发现锁已经被占用了。因此B线程会开始自旋，一直自旋，直到下一个时钟中断产生。
因此，在这种场景下，一个线程会一直自旋检查一个不会改变得值，浪费掉一整个时间片！这个现象叫做忙等(busy-waiting)，所以我们希望能有更好的方法，让锁不会造成不必要的自旋，避免浪费CPU时间。
有一种简单且友好的方式就是，在需要自旋的时候，线程主动放弃CPU。我们假定操作系统会提供原语”
yield()“，当线程调用它时会主动让出CPU给其它线程。如下代码线程可以处于3种状态(运行、就绪和阻塞)。
yield()系统调用可以让运行(running)态变成就绪(ready)态，从而将CPU让出给其它线程。在单个CPU上运行两个线程。对于这样的例子，基于yield()的方式效率会很高，当一个线程调用lock时发现锁已经被占用了，那么他就会调用yield()，让出CPU。
接着，我们再来考虑一下很多个线程(100个线程)竞争同一把锁的情况。当一个线程持有锁时，其它线程来抢锁，这99个线程会分别调用lock()，然后它们都会发现锁被占，接着让出CPU。
假设调度策略是采用的轮转的方式(即所有线程都会调度一次)，这99个线程会一直处于运行-让出这种模式，一直到持有锁的线程再次运行。虽然这以及比浪费99个时间片的自旋方案好很多了，但是上下文切换的成本依旧是不可避免的，因此也存在浪费的情况。
其次，我们也没有考虑饿死的问题，即一个线程可以一直处于让出的循环，而其它线程反复的进入临界区。所以我们还需要寻找更好的方式来解决这个问题。
使用队列：休眠替代自旋
Solaris提供了两个调用，可以让线程进入休眠，
park()和unpark(threadID)，这两个调用可以让线程抢不到锁时进入睡眠，当锁可用时将它唤醒，如下代码：这个解决方案也没有完全避免自旋，
while(TestAndSet(&m->guard, 1) == 1)也会进行自旋，但是这里的自旋时间不会很长，因为guard锁的加锁和解锁的代码很短(指令很少)，这个锁会很快就能够释放。这里在unlock的时候，我们可能会产生一些疑问。
为什么在加锁和解锁的时候要去获取guard，是否可以去掉这个guard？
为什么在唤醒线程的时候没有把flag设置为0？
这个方案其实也有一个问题，即在抢锁失败时，在准备调用park()时，突然发生中断，切换到了其它线程。这下就有意思了，当切换到了另一个线程后，运行一段时间后，这个线程也在抢锁，而且抢成功了，随后把锁释放，并且唤醒了刚刚被中断的线程，线程被唤醒后接着继续执行，执行刚刚还没有来得及执行的
park()准备睡眠，这下就完了，它这一睡可能再也没有人叫醒他了，因为此次唤醒就是让它来抢锁的。如果后续没有其它线程去唤醒它，那它可能会一睡不醒，也有人把这种叫做睡美人现象。为了解决这个问题，Solaris增加一个系统调用separk()，表示一个线程准备睡眠了，如果在调用separk()之后，切换到了另一线程，这个线程随后unpark了，那么后续的park则不会睡眠，而是直接返回(类似执行空函数)。lock只需要做如下修改。
不同操作系统，不同实现
目前我们会发现，不同的操作系统，会提供不同的接口来实现相同的功能，只是细节会有所不同。
如Linux提供了
futex，它有点类似于Solaris的接口，它有两个调用，调用futex_wait(address, expected)，如果address的值和expected相等，线程则会休眠，否则，调用会立即返回(相同于执行了一个空函数)。调用futex_wake(address)会唤醒等待队列中的一个线程。如下是Linux中的futex雷子。它通过一个整数，同时记录锁(整数的二进制最高位)，以及等待线程的个数(整数二进制的其它位)。而且这个锁在没有线程占用锁时，只会做很少的操作(抢锁时的测试并设置，以及释放锁的原子加法)。
我们来看一下加锁的时候这部分代码，首先它再次获取了锁的值，然后判断是否大于等于0，如果是的话，表示锁刚刚被释放了，那么当前线程又会去抢锁，否则进入睡眠。
当线程被唤醒时，又会进入
while循环，但是它不一定能百分百抢到锁，因为有可能锁又被其它线程抢走了(虽然叫到了你的号，但是在你收到叫号前，已经有人插队了)。原因是在
unlock时，在将锁释放掉后，在唤醒队首线程前的这段时间，其它线程已经把锁抢走了。那么被唤醒的线程去抢锁的时候又发现锁被抢走了，这次它又会自旋一会，如果自旋没抢到就进入睡眠。这样的话，被唤醒的线程就会从队首变成队尾，这其实是一个问题。二段(two-phase)锁
还有一种历史悠久的锁方案，且多年来不断被采用，现在也被称为二阶段锁。这个锁的思想是，它认为自旋很有用，尤其是锁即将要被释放的场景。因此，二段锁的第一阶段会先自旋一段时间，希望它能够获取到锁。
如果第一阶段自旋没有获取到锁，则第二阶段调用者会睡眠，直到被唤醒。上述代码的Liunx就是这种锁，不过上述代码只自旋一次；更常见的方式是在循环中会有自旋的固定次数，超过这个次数就会睡眠。
这个二段锁又是一个杂合方案的例子，即结合两个好想法得到更好的想法。当然，硬件环境、线程数、其他负载等这些因素，都会影响锁的效果。事情总是这样，让单个通用目标的锁，在所有可能的场景下都很好，这是巨大的挑战。
扩充
对于更上层的应用，还有一些锁，如java语言中的synchronized锁，它是可以升级的：偏向锁→轻量级锁→重量级锁
当一个线程去抢锁的时候，加锁与解锁的时候不会直接使用CAS(CompareAndSet)，当这个线程再次去获取锁的时候也能够很快的将锁拿到，而不会消耗太多时间。
如果B线程同时来竞争这把锁时，如果当前线程(A)没有死亡，则会将A暂停，并将这把锁升级为轻量级锁，接着A线程再运行，B线程自旋等待。空旋是需要消耗时间片的，这个现象叫做忙等(busy-waiting)，忙等是有限制次数的(默认10次)。如果当前线程(A)死亡了，则会取到这把锁，且是偏向锁。
当有某个线程触发到了忙等上限，那么这个锁就会升级成为重量级锁，重量级锁在获取锁时如果发现锁被占用，则会将当前线程休眠，让出CPU，直到锁被释放后，将其唤醒。