概念
通过对并发的介绍，咱们看到了并发编程的一个最根本问题：因为单处理器上的中断（或者多个线程在多处理器上并发执行），一些咱们心愿能原子执行的指令并不能正确运行。锁（lock）就是用来解决这一问题最根本的办法。程序员在源代码中加锁，放在临界区四周，保障临界区可能像单条原子指令一样执行。
锁的根本思维
上面是应用锁的一个简略示例：
1 pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
2
3 Pthread_mutex_lock(&lock); // wrapper for pthread_mutex_lock()
4 balance = balance + 1;
5 Pthread_mutex_unlock(&lock);锁就是一个变量，这个锁变量保留了锁在某一时刻的状态。它要么是可用的（available，或 unlocked，或 free），示意没有线程持有锁；要么是被占用的（acquired，或 locked，或 held），示意有一个线程持有锁，正处于临界区。 咱们也能够保留其余的信息，比方持有锁的线程，或申请获取锁的线程队列，但这些信息会暗藏起来，锁的使用者不会发现。
锁个别只反对两个操作：lock() 和 unlock()。调用 lock() 尝试获取锁，如果没有其余线程持有锁，该线程会取得锁，进入临界区，这个线程被称为锁的持有者（owner）。如果另外一个线程对雷同的锁变量调用 lock()，因为锁被另一线程持有，该调用不会返回。这样，当持有锁的线程在临界区时，其余线程就无奈进入临界区。
锁的持有者一旦调用 unlock()，锁就变成可用了。如果没有其余期待线程（即没有其余线程调用过 lock() 并卡在那里），锁的状态就变成可用了。如果有期待线程，其中一个会（最终）留神到（或收到告诉）锁状态的变动，获取该锁，进入临界区。
如何实现锁
显然，咱们须要硬件和操作系统的帮忙来实现一个可用的锁。近些年来，各种计算机体系结构的指令集都减少了一些不同的硬件原语，咱们能够应用它们来实现像锁这样的互斥原语。
在实现锁之前，对于锁是否能工作良好，应该当时设立一些规范。首先是锁是否能实现它的根本工作，即提供互斥（mutual exclusion），是否可能阻止多个线程进入临界区。
第二是公平性（fairness）。当锁可用时，是否每一个竞争线程有偏心的机会抢到锁？是否有竞争锁的线程会饿死（starve），始终无奈取得锁？
最初是性能（performance），也即应用锁之后减少的工夫开销。有几种场景须要思考：一种是只有一个线程抢锁、开释锁的开销如何？另外一种是一个 CPU 上多个线程竞争，最初一种是多个 CPU、多个线程竞争时的性能。
切入点一：管制中断
最早提供的互斥解决方案之一，就是在临界区敞开中断。 这个解决方案是为单处理器零碎开发的。通过在进入临界区之前敞开中断（应用非凡的硬件指令），能够保障临界区的代码不会被中断，从而原子地执行。完结之后，咱们从新关上中断，程序失常运行。
这个办法的次要长处就是简略，然而毛病很多。首先，这种办法要求咱们容许所有调用线程执行特权操作（关上敞开中断），然而恶意程序可能会利用这点。例如一个恶意程序可能在它开始时就调用 lock()，从而独占处理器。零碎无奈从新取得管制，只能重启零碎。
第二，这种计划不反对多处理器。如果多个线程运行在不同的 CPU 上，每个线程都试图进入同一个临界区，敞开中断也没有作用。
第三，敞开中断导致中断失落，可能会导致重大的零碎问题。如果磁盘设施实现了读取申请，但 CPU 因为敞开了中断错失了这一信号，操作系统如何晓得去唤醒期待的过程？
最初一个不太重要的起因就是效率低。与失常指令执行相比，古代 CPU 对于敞开和关上中断的代码执行得较慢。
基于以上起因，只在很无限的状况下用敞开中断来实现互斥原语。
切入点二：测试并设置指令
因为敞开中断的办法无奈工作在多处理器上，所以零碎设计者开始让硬件反对锁。 最简略的硬件反对是测试并设置指令（test-and-set instruction），也叫作原子替换（atomic exchange）。 测试并设置指令的工作大抵能够用上面的 C 代码来定义：
1 int TestAndSet(int *old_ptr, int new) {
2 int old = *old_ptr; // fetch old value at old_ptr
3 *old_ptr = new; // store 'new' into old_ptr
4 return old; // return the old value
5 }它返回 old_ptr 指向的旧值，同时更新为 new 的新值。当然，要害是这些代码是原子地（atomically）执行。 因为既能够测试旧值，又能够设置新值，所以咱们把这条指令叫作“测试并设置”。
为了了解该指令如何结构一个可用的锁，咱们首先尝试实现一个不依赖它的锁。
失败的尝试
在第一次尝试中，想法很简略：用一个变量来标记锁是否被某些线程占用。第一个线程进入临界区，调用 lock()，查看标记是否为 1，而后设置标记为 1，表明线程持有该锁。完结临界区时，线程调用 unlock()，革除标记，示意锁未被持有。
当第一个线程正处于临界区时，如果另一个线程调用 lock()，它会在 while 循环中自旋期待（spin-wait)，直到第一个线程调用 unlock() 清空标记。而后期待的线程会退出 while 循环，设置标记，执行临界区代码。
1 typedef struct lock_t {int flag;} lock_t;
2
3 void init(lock_t *mutex) {
4 // 0 -> lock is available, 1 -> held
5 mutex->flag = 0;
6 }
7
8 void lock(lock_t *mutex) {9 while (mutex->flag == 1) // TEST the flag
10 ; // spin-wait (do nothing)
11 mutex->flag = 1; // now SET it!
12 }
13
14 void unlock(lock_t *mutex) {
15 mutex->flag = 0;
16 }遗憾的是，这段代码并不能正确工作。假如代码依照下表执行，开始时 flag=0。
从这种交替执行能够看出，通过适时的中断，咱们很容易结构出两个线程都将标记设置为 1，都能进入临界区的场景。
应用测试并设置指令改良
应用测试并设置指令改良后的代码如下：
1 typedef struct lock_t {
2 int flag;
3 } lock_t;
4
5 void init(lock_t *lock) {
6 // 0 indicates that lock is available, 1 that it is held
7 lock->flag = 0;
8 }
9
10 void lock(lock_t *lock) {11 while (TestAndSet(&lock->flag, 1) == 1)
12 ; // spin-wait (do nothing)
13 }
14
15 void unlock(lock_t *lock) {
16 lock->flag = 0;
17 }咱们了解一下这个锁的工作原理。首先假如一个线程在运行，调用 lock()，没有其余线程持有锁，所以 flag 是 0。当调用 TestAndSet(flag, 1) 办法，返回 0，线程会跳出 while 循环，获取锁。同时也会原子地设置 flag 为 1，标记锁曾经被持有。当线程来到临界区，调用 unlock() 将 flag 清理为 0。
当某一个线程曾经持有锁时。工作线程调用 lock()，而后调用 TestAndSet(flag, 1)，这一次返回 1。只有另一个线程始终持有锁，TestAndSet() 会反复返回 1，本线程会始终自旋。当 flag 终于被改为 0，本线程会调用 TestAndSet()，返回 0 并且原子地设置为 1，从而取得锁，进入临界区。
这种锁被称为自旋锁（spin lock）。 这是最简略的一种锁，始终自旋，利用 CPU 周期，直到锁可用。 在单处理器上，须要抢占式的调度器。否则，自旋锁在单 CPU 上无奈应用，因为一个自旋的线程永远不会放弃 CPU。
评估自旋锁
咱们依照之前的规范来评估一下咱们实现的自旋锁。首先是正确性：自旋锁一次只容许一个线程进入临界区，因而能够正确运行。
下一个规范是公平性： 答案是自旋锁不提供任何公平性保障。实际上，自旋的线程在竞争条件下可能会永远自旋。自旋锁没有公平性，可能会导致饿死。
最初一个规范是性能。 对于自旋锁，在单 CPU 的状况下，性能开销相当大。 假如一个线程持有锁进入临界区时被抢占。调度器可能会运行其余每一个线程（假如有 N−1 个这种线程）。而其余线程都在竞争锁，都会在放弃 CPU 之前，自旋一个工夫片，节约 CPU 周期。
然而，在多 CPU 上，自旋锁性能不错（如果线程数大抵等于 CPU 数）。假如线程 A 在 CPU 1，线程 B 在 CPU 2 竞争同一个锁。线程 A 占有锁时，线程 B 竞争锁就会自旋。然而，临界区个别都很短，因而很快锁就可用，而后线程 B 取得锁。自旋期待其余处理器上的锁，并没有节约很多 CPU 周期，因而成果不错。
切入点三：比拟并替换指令
某些零碎提供了另一个硬件原语，即比拟并替换指令（compare-and-swap）。下图是这条指令的 C 语言伪代码。
1 int CompareAndSwap(int *ptr, int expected, int new) {
2 int actual = *ptr;
3 if (actual == expected)
4 *ptr = new;
5 return actual;
6 }比拟并替换的基本思路是检测 ptr 指向的值是否和 expected 相等；如果是，更新 ptr 所指的值为新值。否则，什么也不做。不管哪种状况，都返回该内存地址的理论值，让调用者可能晓得执行是否胜利。
有了比拟并替换指令，就能够实现一个锁，相似于用测试并设置指令那样。例如，咱们只有用上面的代码替换下面例子中的 lock() 函数：
1 void lock(lock_t *lock) {2 while (CompareAndSwap(&lock->flag, 0, 1) == 1)
3 ; // spin
4 }它的行为以及对其的评估等价于下面剖析的自旋锁。
切入点四：获取并减少指令
最初一个硬件原语是获取并减少（fetch-and-add）指令，它能原子地返回特定地址的旧值，并且让该值自增一。获取并减少的 C 语言伪代码如下：
1 int FetchAndAdd(int *ptr) {
2 int old = *ptr;
3 *ptr = old + 1;
4 return old;
5 }咱们能够应用获取并减少指令，实现一个更乏味的 ticket 锁：
1 typedef struct lock_t {
2 int ticket;
3 int turn;
4 } lock_t;
5
6 void init(lock_t *lock) {
7 lock->ticket = 0;
8 lock->turn = 0;
9 }
10
11 void lock(lock_t *lock) {12 int myturn = FetchAndAdd(&lock->ticket);
13 while (lock->turn != myturn)
14 ; // spin
15 }
16
17 void unlock(lock_t *lock) {18 FetchAndAdd(&lock->turn);
19 }这里不是用一个值，而是应用了 ticket 和 turn 变量来构建锁。基本操作也很简略：如果线程心愿获取锁，首先对一个 ticket 值执行一个原子的获取并相加指令。这个值作为该线程的“turn”（顺位，即 myturn）。依据全局共享的 lock->turn 变量，当某一个线程的（myturn == turn）时，则轮到这个线程进入临界区。unlock 则是减少 turn，从而下一个期待线程能够进入临界区。
不同于之前的办法： 本办法可能保障所有线程都能抢到锁。只有一个线程取得了 ticket 值，它最终会被调度。 比方基于测试并设置的办法，一个线程有可能始终自旋，即便其余线程在获取和开释锁。
如何防止过多自旋
基于硬件的锁简略而且无效，然而在某些场景下，这些解决方案会效率低下。以两个线程运行在单处理器上为例，当一个线程（线程 1）持有锁时，被中断。第二个线程（线程 2）去获取锁，发现锁曾经被持有。因而，它就始终自旋。最初，时钟中断产生，线程 1 从新运行，它开释锁。最初，线程 2 不须要持续自旋了，它获取了锁。
相似的场景下，一个线程会始终自旋查看一个不会扭转的值，节约掉整个工夫片。如果有 N 个线程去竞争一个锁，状况会更蹩脚。同样的场景下，会节约 N−1 个工夫片，只是自旋并期待一个线程开释该锁。因而，咱们的下一个关键问题是：怎么防止不必要的自旋，节约 CPU 工夫？
简略办法：让出工夫片
第一种简略的办法就是，在要自旋的时候，放弃 CPU。下图展现了这种办法。
1 void init() {
2 flag = 0;
3 }
4
5 void lock() {6 while (TestAndSet(&flag, 1) == 1)
7 yield(); // give up the CPU
8 }
9
10 void unlock() {
11 flag = 0;
12 }在这种办法中，咱们假设操作系统提供原语 yield()，线程能够调用它被动放弃 CPU，让其余线程运行。yield() 零碎调用可能让线程由运行（running）态变为就绪（ready）态，从而容许其余线程运行。因而，让出线程实质上勾销调度（deschedules）了它本人。
思考在单 CPU 上运行两个线程，基于 yield 的办法非常无效。一个线程调用 lock()，发现锁被占用时，让出 CPU，另外一个线程运行，实现临界区。在这个简略的例子中，让出办法工作得十分好。
当初来思考许多线程（例如 100 个）重复竞争一把锁的状况。在这种状况下，一个线程持有锁，在开释锁之前被抢占。其余 99 个线程别离调用 lock()，发现锁被抢占，而后让出 CPU。假设采纳某种轮转调度程序，这 99 个线程会始终处于运行—让出这种模式，直到持有锁的线程再次运行。 尽管比原来的节约 99 个工夫片的自旋计划要好，但这种办法依然老本很高，上下文切换的老本是实实在在的，因而节约很大。
更糟的是，咱们还没有思考饥饿的问题。 一个线程可能始终处于让出的循环，而其余线程重复进出临界区。 很显然，咱们须要一种办法来解决这个问题。
应用队列：休眠代替自旋
后面一些办法的真正问题是存在太多的必然性：调度程序决定如何调度线程。如果调度不合理，线程或者始终自旋，或者立即让出 CPU。无论哪种办法，都可能造成节约，也不能避免饥饿。
因而，咱们必须显式地施加某种管制，决定锁开释时，谁能抢到锁。为了做到这一点，咱们须要操作系统的更多反对，并须要一个队列来保留期待锁的线程。
简略起见，咱们利用 Solaris 提供的反对，它提供了两个调用：park() 可能让调用线程休眠，unpark(threadID) 则会唤醒 threadID 标识的线程。能够用这两个调用来实现锁，让调用者在获取不到锁时睡眠，在锁可用时被唤醒。
1 typedef struct lock_t {
2 int flag;
3 int guard;
4 queue_t *q;
5 } lock_t;
6
7 void lock_init(lock_t *m) {
8 m->flag = 0;
9 m->guard = 0;
10 queue_init(m->q);
11 }
12
13 void lock(lock_t *m) {14 while (TestAndSet(&m->guard, 1) == 1)
15 ; //acquire guard lock by spinning
16 if (m->flag == 0) {
17 m->flag = 1; // lock is acquired
18 m->guard = 0;
19 } else {20 queue_add(m->q, gettid());
21 m->guard = 0;
22 park();
23 }
24 }
25
26 void unlock(lock_t *m) {27 while (TestAndSet(&m->guard, 1) == 1)
28 ; //acquire guard lock by spinning
29 if (queue_empty(m->q))
30 m->flag = 0; // let go of lock; no one wants it
31 else
32 unpark(queue_remove(m->q)); // hold lock (for next thread!)
33 m->guard = 0;
34 }在这个例子中，咱们做了两件事。首先，咱们将之前的测试并设置和期待队列联合，实现了一个更高性能的锁。其次，咱们通过队列来管制谁会取得锁，防止饿死。
你可能留神到，guard 基本上起到了自旋锁的作用，围绕着 flag 和队列操作。因而，这个办法并没有完全避免自旋期待。线程在获取锁或者开释锁时可能被中断，从而导致其余线程自旋期待。然而，这个自旋等待时间是很无限的（不是用户定义的临界区，只是在 lock 和 unlock 代码中的几个指令）。
当要唤醒另一个线程时，flag 并没有设置为 0。为什么呢？因为当线程被唤醒时，就像是从 park() 调用返回。此时它没有持有 guard，所以也不能将 flag 设置为 1。因而，咱们就间接把锁从开释的线程传递给下一个取得锁的线程，期间 flag 不用设置为 0。
不过，代码中还是存在一点瑕疵。假如一个线程将要调用 park 休眠，然而不凑巧，零碎切换到了正在持有锁的线程。如果该线程随后开释了锁，后面的线程调用 park 后可能会永远休眠上来。为了防止这种状况，咱们须要额定的工作。
Solaris 通过减少了第三个零碎调用 setpark() 来解决这一问题。通过 setpark()，一个线程表明本人马上要调用 park。如果刚好另一个线程被调度，并且调用了 unpark，那么后续的 park 调用就会间接返回，而不是始终睡眠。因而，示例代码中失去 lock() 调用能够做一点小批改：
1 queue_add(m->q, gettid());
2 setpark(); // new code
3 m->guard = 0;另一种计划就是将 guard 传入内核。在这种状况下，内核可能采取预防措施，保障原子地开释锁，把运行线程移出队列。
两阶段锁
两阶段锁（two-phase lock）是一种古老的锁计划，多年来一直被采纳。两阶段锁意识到自旋可能很有用，尤其是在很快就要开释锁的场景。因而，两阶段锁的第一阶段会先自旋一段时间，心愿它能够获取锁。
然而，如果第一个自旋阶段没有取得锁，第二阶段调用者会睡眠，直到锁可用。常见的形式是在循环中自旋固定的次数，而后睡眠。