CH07-锁

近来对并行编程的研究中,锁总是扮演着坏人的角色。在许多论文和演讲中,锁背负着诸多质控,包括引起死锁、锁争抢、饥饿、不公平的锁、并发数据访问以及其他许多并发带来的罪恶。有趣的是,真正在产品级共享内存并行软件中承担重担的角色是——你猜对了——锁。那锁到底是英雄还是坏蛋呢?

这种认识源于以下几个原因:

  • 很多因锁产生的问题都在设计层面就可以解决,而且在大多数场合工作良好,比如:
    • 使用锁层级以避免死锁。
    • 使用死锁检测工具,比如 Linux 内核 lockdep 模块。
    • 使用对锁友好的数据结构,比如数组、哈希表、基树。
  • 有些锁的问题只在竞争程度很高时才会出现,一般只有不良的设计才会出现竞争如此激烈的锁。
  • 有些锁的问题可以通过其他同步机制配合锁来避免。包括统计计数、引用计数、危险指针、顺序锁、RCU,以及简单的非阻塞数据结构。
  • 直到不久之前,几乎所有的共享内存并行程序都是闭源的,所以多数研究者很难了解业界的实践解决方案。
  • 锁在某些软件上运行的很好,在某些软件上运行的很差。那些在锁运行良好的软件上做开发的程序员,对锁的态度往往比另一些没那么幸运的程序员更加正面。
  • 所有美好的故事都需要一个坏人,锁在研究文献中扮演坏小子的角色已经有着悠久而光荣的历史了。

努力活着

死锁

当一组线程中的每个线程都持有至少一把锁,此时又等待该组线程中的某个成员释放它持有的一把锁时,死锁就会发生。

如果缺乏外界干预,死锁会一直持续。除非持有锁的线程释放,没有线程可以获取到该锁,但是持有锁的线程在等待获取该锁的线程释放其他锁之前,又无法释放该锁。

我们可以用有向图来表示死锁,节点代表锁和线程。

NAME

如上图。从锁指向线程的箭头表示该线程持有了该锁。比如线程 B 持有锁 2 和 4。从线程到锁的箭头表示线程在等待这把锁,比如线程 B 等待锁 3 释放。死锁场景至少包含至少一个以上的死锁循环。在上图中,死锁循环是线程 B、锁 3 、线程 C、锁 4,然后又回到线程 B。

虽然有一些软件环境,比如数据库系统,可以修复已有的死锁,但是这种方式要么杀掉其中一个线程,要么强制从某个线程中偷走一把锁。杀掉线程和强制偷锁对于事务交易是可以的,但是对内核和应用程序这种层次的锁来说问题多多,处理部分更新的数据库极端复杂,非常危险,而且很容易出错。

因此,内核和应用程序要么避免死锁,而非从死锁中恢复。避免死锁的策略有很多,包括锁的层次、锁的本地层次、锁的分级层次、包含指向锁的指针的 API 的使用策略、条件锁、先获取必须的锁、一次只用一把锁的设计,以及信号/中断处理函数的使用策略。虽然没有任何一个避免死锁策略可以适用于所有情况,但是市面上有很多避免死锁的工具可供选择。

锁的层次

锁的层次是指为锁逐级编号,禁止不按顺序获取锁。在上图中我们可以用数字为锁编号,这样如果线程已经获得了编号相同的锁或者更高编号的锁,就不允许获得编号相同或者编号更低的锁。线程 B 违反这个层次,因此它在持有锁 4 时又视图获取锁 3,因此导致死锁发生。

再次强调,按层次使用锁时要为锁编号,严禁不按顺序获取锁。在大型程序中,最好用工具来检查锁的层次。

锁的本地层次

但是所的层次本质要求全局性,因此很难应用在库函数上。如果调用了某个库函数的应用程序开没开始实现,那么倒霉的库函数程序员又怎么才能遵循这个还不存在的应用程序中的锁层次呢?

一种特殊的情况是,幸运的也是普遍的情况,是库函数并不涉及任何调用者代码。这时,如果库函数持有任何库函数的锁,它绝对不会再去获取调用者的锁,这样就避免出现库函数和调用者之间互相持有锁的死循环。

但假设某个库函数确实调用了某个调用者的代码。比如,qsort() 函数调用了调用者提供的比较函数。并发版本的 qsort() 通常会使用锁,虽然可能性不大,但是如果比较函数复杂且使用了锁,那么久有可能发生死锁。这时库函数该如何避免死锁?

出现这种情况时的黄金定律是:在调用未知代码前释放所有的锁。为了遵循该定律,qsort() 函数必须在调用比较函数前释放它所持有的全部锁。

为了理解本地层次锁的好处,让我们比较一下下面的两个图:

不带本地层次锁的 qsort:

NAME

基于所的本地层次实现的 qsort():

NAME

在两幅图中,应用程序 foo()bar() 在分别持有锁 A 和锁 B 时调用了 qsort()。因为这是并行版本,所以 qsort() 内还要获取锁 C。函数 foo() 将函数 cmp() 传给 qsort(),而 cmp() 中要获取锁 B。函数 bar() 将一个简单的整数比较函数传给 qsort(),而这个简单的函数不支持任何锁。

现在假设 qsort() 在持有锁 C 时调用 cmp(),这违背了之前提过的黄金定律“释放所有锁”,那么死锁会发生。为了让读者理解,假设一个线程调用 foo(),另一个线程调用 bar()。第一个线程会获取锁 A,第二个线程会获取锁 B。如果第一个线程调用 qsort() 时获取锁 C,那么这时它在调用 cmp() 时将无法获得锁 B。但第一个线程获得了锁 C,所以第二个线程调用 qsort() 时无法获取锁 C,因此也无法释放锁 B,导致死锁。

相反,如果 qsort() 在调用比较函数之前释放锁 C,就可以避免死锁。

如果每个模块在调用未知代码前释放全部锁,那么每个模块自身都避免了死锁,这样整个系统也就避免发生死锁了。这个定律极大的简化了死锁分析,增强了代码的模块化。

锁的分级层次

不幸的是,有时 qsort() 无法在调用比较函数前释放全部锁。这时,我们无法通过以调用未知代码之前释放全部锁的方式来构建锁的本地层次。可是我们可以构建一种分级层次,如下图:

NAME

在这张图上,cmp() 函数在获取了锁 A、B、C 后再获取新的锁 D,这就避免了死锁。这样我们把全局层次锁分成了三级,第一级是锁 A 和锁 B,第二级是锁 C,第三级是锁 D。

请注意,让 cmp() 使用分级的层次锁 D 并不容易。恰恰相反,这种改动需要在设计层面进行大量更改。然而,这种变动往往是避免死锁时需要付出的点小小代价。

锁的层次和指向锁的指针

虽然有些例外情况,一般来说设计一个包含着指向锁的指针的 API 意味着这个设计本身就存在问题。将内部的锁传递给其他软件组件违反了信息隐藏原则,而信息隐藏恰恰是一个关键的设计准则。

比如两个函数要返回某个对象,而在对象成功返回之前必须持有调用者提供的锁。再比如 POSIX 的 pthread_cond_wait() 函数,要传递一个指向 pthread_mutex_t 的指针来放置错过唤醒而导致的挂起。

长话短说,如果你发现 API 需要将一个指向锁的指针作为参数或者返回值,请慎重考虑一下是否需要修改这个设计。有可能这是正确的做法,但是经验告诉我们这种可能性很低。

条件锁

假如某个场景设计不出合理的层次锁。这在现实生活中是可能发生的,比如,在分层网络协议栈里,报文流是双向的。当报文从一个层传向另一个层时,有可能需要在两层中同时获取锁。因为报文可以从协议栈上层往下层传,也可能相反,这简直是死锁的天然温床。

在这个例子中,当报文在协议栈中从上往下发送时,必须逆序获取下一层锁。反之则需要顺序获得锁。解决办法是强加一套锁的层次,但在必要时又可以有条件地乱序获取锁。

先获取必要的锁

条件锁有一个重要的特例,在执行真正的处理工作之前,已经拿到了所有必须的锁。在这种情况下,处理不需要是幂等的:如果这时不能在不释放锁的情况下拿到某把锁,那么释放所有持有的锁,重新获取。只有在持有所有必要的锁以后才开始处理工作。但是这样又可能导致活锁,后续将会讨论这一点。

两阶段加锁在事务数据库系统中已经存在很长时间了,它就应用了这个策略。两阶段加锁事务的第一个阶段,只获取锁但不释放锁。一旦所有必须的锁全部获得,事务进入第二阶段,只释放锁但不获取锁。这种加锁方法使得数据库可以对执行的事务提供串行化保护,换句话说,保证事务看到和产生的数据在全局范围内顺序一致。很多数据库系统都依靠这种能力来终止事务,不过两阶段加锁也可以简化这种方法,在持有所有必要的锁之前,避免修改共享数据。虽然使用两阶段锁仍然会出现活锁或死锁,但是在现有的大量数据库类教科书中已经有很多实用的解决办法。

一次只用一把锁

在某些情况下,可以避免嵌套加锁,从而避免死锁。比如,如果有一个可以完美分割的问题,每个分片拥有一把锁。然后处理任何特定分片的线程只需获取对应该分片的锁。因为没有任何线程在同一时刻持有一把以上的锁,死锁就不可能发生。但是必须有一些机制来保证在没有持锁的情况下所需数据结构依然存在。

信号/中断处理函数

涉及信号处理函数的死锁通常可以很快解决:在信号处理函数中调用 pthread_mutex_lock() 是非法的。可是,精心构造一种可以在信号处理函数中使用的锁是有可能的。除此之外,基本所有的操作系统内核都允许在中断处理函数里获取锁,中断处理函数可以说是内核对信号处理函数的模拟。

其中的诀窍是在任何可能中断的处理函数里获取锁的时候阻塞信号(或者屏蔽中断)。不仅如此,如果已经获取了锁,那么在不阻塞信号的情况下,尝试去获取任何可能中断处理函数之外被持有的锁,都是非法操作。

假如处理函数获取锁是为了处理多个信号,那么无论是否获得了锁,甚至无论锁是否是在信号处理函数之内获取的,每个信号也都必须被阻塞。

不幸的是,在一些操作系统里阻塞和解除阻塞信号都属于代价昂贵的操作,这里包括 Linux,所以出于性能上的考虑,能在信号处理函数内持有的锁仅能在信号处理函数内获取,应用程序和信号处理函数之间的通信通常使用无锁同步机制。

或者除非处理致命异常,否则完全禁用信号处理函数。

本节讨论

对于基于内存共享的并行程序员来说,有大量避免死锁的策略可用,但是如果遇到这些策略都不适用的场景,总还是可以用串行代码来实现的。这也是为什么专家级程序员的工具箱里总是有好几样工具的原因之一,但是别忘了总有些活适合用其他工具处理。不过,本节描述的这些策略在很多场合都被证明非常有用。

活锁与饥饿

虽然条件锁是一种有效避免死锁的机制,但是有可能被滥用。考虑下面的例子:

1 void thread1(void) 
2 { 
3   retry:
4   spin_lock(&lock1); 
5   do_one_thing(); 
6   if (!spin_trylock(&lock2)) { 
7     spin_unlock(&lock1); 
8     goto retry; 
9   } 
10  do_another_thing(); 
11  spin_unlock(&lock2); 
12  spin_unlock(&lock1); 
13 } 
14 
15 void thread2(void) 
16 { 
17   retry:
18   spin_lock(&lock2); 
19   do_a_third_thing(); 
20   if (!spin_trylock(&lock1)) { 
21     spin_unlock(&lock2); 
22     goto retry; 
23   } 
24   do_a_fourth_thing(); 
25   spin_unlock(&lock1); 
26   spin_unlock(&lock2); 
27 }

考虑以下事件顺序:

  • 4:线程 1 获取 lock1,然后调用 do_one_thing()
  • 18:线程 2 获取 lock2,然后调用 do_a_third_thing()
  • 6:线程 1 试图获取 lock2,由于线程 2 已经持有而失败
  • 20:线程 2 试图后去 lock1,由于线程 1 已经持有而失败
  • 7:线程 1 释放 lock1,然后跳转到第 3 行的 retry
  • 21:线程 2 释放 lock2,然后跳转到 17 行的 retry
  • 以上过程不断重复,活锁将华丽登场

活锁可以被看做是饥饿的一种极端形式,此时不再是一个线程,而是所有线程都饥饿了。活锁和饥饿都属于事务内存软件实现中的严重问题,所以现在引入了竞争管理器这样的概念来封装这些问题。以锁为例,通常简单的指数级退避就能解决活锁和饥饿。指数级退避是指在每次重试之前增加按指数级增长的延迟。不过,为了获取更好的性能,退避应该有个上限,如果使用排队锁甚至可以在高竞争时获取更好的性能。当然,更好的办法还是通过良好的并行设计使锁的竞争程度变低。

不公平的锁

不公平的锁被看成是饥饿的一种不太严重的表现形式,当某些线程争抢同一把锁时,其中一部分线程在绝大多数时间都可以获取到锁,另一部分线程则遭遇不公平对待。这在带有道速共享缓存或者 NUMA 内存的机器上可能出现。

NAME

如上图。如果 CPU0 释放了一把其他 CPU 都想获得的锁,因为 CPU0 与 CPU1 共享内部链接,所以 CPU1 相较于 CPU2~7 则更易抢到锁。反之亦然,如果一段时间后 CPU0 又开始争抢该锁,那么 CPU1 释放时 CPU0 则更易获得锁,导致锁绕过 CPU2~7,只在 CPU0 和 CPU1 之间换手。

低效率的锁

锁是由原子操作和内存屏障实现的,并且常常带有高速缓存未命中。正如我们第三章所见,这些指令代价都是十分昂贵的,粗略地说开销比简单指令要高出两个数量级。这可能是锁的一个严重问题,如果用锁来保护一条指令,你很可能在以百倍的速度带来开销。对于相同的代码,即使假设扩展性非常完美,也需要 100 个 CPU 才能跟上一个执行不加锁版本的 CPU。

这种情况强调了“同步粒度”一节中的权衡,粒度太粗会限制扩展性,粒度太小会导致巨大的同步开销。

不过一旦持有了锁,持有者可以不受干扰的访问被锁保护的代码。获取锁可能代价高昂,但是一旦持有,特别是对较大的临界区来说,CPU 高速缓存反而是高效的性能加速器。

锁的类型

互斥锁

互斥锁正如其名,一次只能被一个线程持有。持锁者对受锁保护的代码享有排他性的访问权。当然,这是在假设该锁保护了所有应当受保护的数据的前提下。虽然有些工具可以帮你检查,但最终的责任还是落在开发者身上,一定要保证所有需要的路径都受互斥锁的保护。

读写锁

读写锁一方面允许任意数量的读者同时持有锁,另一方面允许最多一个写者持有锁。理论上,读写锁对读侧重的数据来说拥有极佳的扩展性。在实践中的扩展性则取决于具体的实现方式。

经典的读写锁实现使用一组只能以原子操作方式修改的计数和标志。这种实现和互斥锁一样,对于很小的临界区来说开销太大,获取和释放锁的开销比一条简单指令的开销要高出两个数量级。当然,如果临界区足够长,获取和释放锁的开销与之相比就可以忽略不计了。可是因为一次只有一个线程能操作锁,随着 CPU 数目的增加,临界区的代价也需要增加才能平衡掉开销。

另一个设计读写锁的方式是使用每线程互斥锁,这种读写锁对读者非常有利。线程在读的时候只需要获取本线程的锁即可,而在写的时候需要获取所有线程的锁。在没有写者的情况下,每个读锁的开销相当于一条原子操作和一个内存屏障的开销之和,而且不会有高速缓存未命中,这点对于锁来说非常不错。不过,写锁的开销包括高速缓存未命中,再加上原子操作和内存屏障的开销之和——再乘以线程的个数。

简单的说,读写锁在有些场景非常有用,但各种实现方式都有各自的缺点。读写锁的正统用法是用于非常长的只读临界区,临界区耗时几百微秒或者毫秒甚至更多则最好。

读写锁之外

读写锁和互斥锁允许的规则大不相同:互斥锁只允许一个持有者,读写锁允许任意多个持有者持有读锁(但只能有一个持有写锁)。锁可能的允许规则有很多,VAX/VMS 分布式锁管理器就是其中一个例子。下图是各种状态之间的兼容性:

规则类型空(未持锁)并发读并发写受保护读受保护写互斥访问
空(未持锁)
并发读N
并发写NNN
受保护读NNN
受保护写NNNN
互斥访问NNNNN

N 表示不兼容,空值表示兼容。

VAX/VMS 分布式锁管理器有 6 个状态。为了更好的比较,互斥锁有 2 个状态(持锁和未持锁),而读写锁有 3 个状态(未持锁、持读锁、持写锁)。

这里第一个状态是空状态,也就是未持锁。这个状态与其他任何状态兼容,这也是我们期待的,如果没有线程持有锁,那么也不会阻止其他获取了锁的线程执行。

第二个状态是并发读,该状态与除了排他状态之外的所有状态兼容。并发读状态可用于对数据结构进行粗略的累加统计,同时允许并发写的操作。

第三个状态是并发写,与空状态、并发读、并发写兼容。并发写状态可以用于近似统计计数的更新,同时允许并发的读操作和写操作。

第四个状态是受保护读,与空状态、并发读、受保护兼容。受保护状态可用于读取数据结构的准确结果,同时允许并发的读操作,但是不允许并发的写操作。

第五个状态是受保护写,与空状态、并发读兼容。受保护写状态可用于在可能会受到受保护读干扰的情况下写数据结构,允许并发的读操作。

第六个状态是互斥访问,仅与空状态兼容。互斥访问状态可用于需要排他访问的场合。

有趣的是,互斥锁和读写锁可以用 VAX/VMS 分布式锁管理器来模拟。互斥锁仅使用空状态和互斥访问状态,读写锁仅使用空状态、受保护的读/写状态。

虽然 VAX/VMS 分布式锁管理器广泛用于分布式数据库领域,但是在共享内存的应用程序中却很少见。其中一个可能的原因是分布式数据库中的通信开销在一定程度上可以抵消 VAX/VMS 分布式锁管理器带来的复杂性。

然而,VAX/VMS 分布式锁管理器只是一个例子,用来说明锁背后的概念和灵活性。同时这个例子也是对现代数据库管理系统所使用的锁机制的简单介绍,相对于 VAX/VMS 分布式锁管理器的 6 个状态,有些数据库中使用的锁甚至可以有 30 多个状态。

范围锁

到目前为止我们讨论的加锁原语都需要明确的获取和释放函数,比如 spin_lock()spin_unlock()。另一种方式是使用面向对象的“资源分配即初始化”(RAII)模式。该设计模式常见于支持自动变量的语言,如 C++,当进入对象的范围时调用构造函数,当退出对象的范围时调用析构函数。同理,加锁可以让构造函数去获取锁、析构函数来释放锁。

这种方法十分有用,事实上 1991 年本书作者曾认为这是唯一有用的加锁方法。RAII 式加锁有一个非常好的特性,你不需要精心思考在每个会退出对象范围的代码路径上释放锁,该特性避免了一系列 BUG 的出现。

但是,RAII 式加锁也有其黑暗面。RAII 使得对获取和释放锁的封装极其困难,比如在迭代器内。在很多迭代器的实现中,你需要在迭代器的开始函数内获取锁,在结束函数内释放锁。相反 RAII 式加锁要求获取和释放锁都发生在相同的对象范围,这使得对它们的封装变得困难,甚至无法实现。

因为范围只能嵌套,所以 RAII 式加锁不允许重叠的临界区。这让锁的很多有用的用法变得不可能,比如,对于协调对并发访问某事件的树状锁。对于任意规模的并发访问,只允许其中一个成功,其余请求最好是让他们越早失败越好。否则在大型系统上(几百个 CPU)对锁的竞争会称为大的问题。

NAME

上图是一个示例数据结构(来自 Linux 内核的 RCU 实现)。在这里,每个 CPU 都分配一个 rcu_node 的叶子节点,每个 rcu_node 节点都拥有一个指向父节点的指针 ->parent,直到根节点的 rcu_node 节点,它的 ->parent 指针为 NULL。每个父节点可以拥有的子节点数目可以不同,但是一般是 32 或 64。每个 rcu_node 节点都有一把名为 ->fqslock 的锁。

这里使用的是一种通用策略——锦标赛,任意指定 CPU 有条件地获取它对应的 rcu_node 叶子节点的锁 ->fqslock,如果成功,尝试获取其父节点的锁,如成功再释放子节点的锁。除此之外,CPU 在每一层检查全局变量 gp_flags,如果每个变量表明其他 CPU 已经访问过这个事件,该 CPU 被淘汰出锦标赛。这种先获取——再释放顺序一直持续到要么 gp_flags 变量表明已经有人赢得锦标赛,某一层获取 ->fqslock 锁失败,要么拿到了根节点 rcu_node 结构的锁 ->fqslock

锁在实现中的问题

系统总是给开发者提供最好的加、解锁原语,例如 POSIX pthread 互斥锁。然而,学习范例实现总是有点用的,因为这样读者可以考虑极端工作负载和环境带来的挑战。

基于原子交换的互斥锁实现示例

1 typedefintxchglock_t;
2 #define DEFINE_XCHG_LOCK(n) xchglock_t n = 0
3
4 void xchg_lock(xchglock_t *xp)
5 {
6   while (xchg(xp, 1) ==1) {
7     while(*xp == 1)
8       continue;
9   }
10 }
11
12 void xchg_unlock(xchglock_t *xp)
13 {
14   (void)xchg(xp, 0);
15 }

这个锁的结构只是一个 int,如第 1 行所示,这里可以是任何整数类型。这个锁的初始值为 0,代表锁已释放,即第二行代码。

通过 4~10 行上的 xchg_lock() 函数执行锁的获取。此函数使用嵌套循环,外部循环重复地将锁的值与 1 做原子交换(即加锁)。如果旧值已经是 1(即该锁已经被别人持有),那么内部循环(7~8)持续自旋直到锁可用,那么到时候外部循环再一次尝试获取锁。

锁的释放由 12~15 行的 xchg_unlock() 函数执行。第 14 行将值 0(即解锁)原子地交换到锁中,从而标记锁已经释放。

虽然这是一个测试并设置(test-and-set)的例子,但是在生产环境中广泛采用一种非常类似的机制来实现纯自旋锁。

互斥锁的其他实现

基于原子指令的锁有很多可能的实现,Mellor-Crummey 和 Scott 综述了其中很多种。这些实现代表着设计权衡多个维度中的不同顶点。例如,上一节提到的基于原子交换的测试并设置锁,在低度锁竞争时性能良好,并且具有内存占用小的有点。它避免了给不能使用它的线程提供锁,但作为结果可能会导致不公平或甚至在高度锁竞争时出现饥饿。

相比之下,在 Linux 内核中使用的门票锁(ticket-lock)避免了在高度锁竞争时的不公平,但后果是其先入先出的准则可以将锁授予给当前无法使用它的线程,例如,线程由于被抢占、中断或其他方式而失去 CPU。然而,避免太过担心抢占和中断的可能性同样重要,因为抢占和中断也有可能在线程刚获取锁后发生。

只要是等待者在某个内存地址自旋以等待锁的各种实现,包括测试并设置锁和门票锁,都在高度锁竞争时存在性能问题。原因是释放锁的线程必须更新对应的内存地址。在低度竞争时,这不是问题:相对的缓存行很可能仍然属于本地 CPU 并且仍然可以由持有锁的线程来更改。相反,在高度竞争时,每个尝试获取锁的线程将拥有高速缓存行的只读副本,因此锁的持有者将需要使所有此类副本无效,然后才能更新内存地址来释放锁。通常,CPU 和线程越多,在高度竞争条件下释放锁时所产生的开销就约大。

这种负可扩展性已经引发了许多种不同的排队锁(queued-lock)实现。排队锁通过为每个线程分配一个队列元素,避免了高昂的缓存无效化开销。这些队列元素链接在一起构成了一个队列,控制着等待线程获取锁的顺序。这里的关键点在于每个线程只在自己的队列元素上自旋,使得锁持有者只需要使下一个线程的 CPU 缓存中的第一个元素无效即可。这种安排大大减少了在高度锁竞争时交换锁的开销。

最近的排队锁实现也将系统的架构纳入到考虑之中,优先在本地予锁,同时采取措施避免饥饿。这些实现可以看成是传统上用在调度磁盘 IO 时使用的电梯算法的模拟。

不幸的是,相同的调度逻辑虽然提高了排队锁在高度竞争时的时效率,也增加了其在低度竞争时的开销。因此,Beng-hong Lim 和 AnantAgarwal 将简单的测试并设置锁与排队锁结合,在低度竞争时使用测试并设置锁,在高度竞争时切换到排队锁,因此得以在低度竞争时获得低开销,并在高度竞争时获得公平的高吞吐量。Browning 等人采取了类似的方法,但避免了单独标志的使用,这样测试并设置锁的快速路径可以使用简单测试和设置锁实现所用的代码。这种方法已经用于生产环境。

在高度锁竞争中出现的另一个问题是当锁的持有者受到延迟,特别是当延迟的原因是抢占时,这可能导致优先级翻转,其中低优先级的线程持有锁,但是被中等优先级且绑定在某 CPU 上的线程抢占,这导致高优先级线程在尝试获取锁时阻塞。结果是绑定在某 CPU 的中优先级进程阻止高优先级进程运行。一种解决方案是优先级继承,这已被广泛用于实时计算,尽管这种做法仍有一些持续的争议。

避免优先级翻转的另一种做法是在持有锁时防止抢占。由于在持有锁的同时防止抢占也提高了吞吐量,因此大多数私有的 UNIX 内核都提供某种形式的调度器同步机制,当然这主要是由于某家大型数据库供应商的努力。这些机制通常采取提示的形式,即此时不应当抢占。这些提示通过在特定寄存器中设置某个比特位的形式实现,这使得提示机制拥有极低的锁获取开销。作为对比,Linux 没有使用提示机制,而是用一种称为 futexes 的机制来获得类似的效果。

有趣的是,在锁的实现中原子指令并不是不可或缺的部分。在 Herlihy 和 Shavit 的教科书中可以找到一种锁的漂亮实现,只使用简单的加载和存储,提到这点的目的是,虽然这个实现没有什么实际应用,但是详细的研究这个实现将非常具有娱乐性和启发性。不过,除了下面描述的一个例外,这样的研究将留下作为读者的练习。

Gamsa 等人描述了一种基于令牌的机制,其中令牌在 CPU 之间循环,当令牌到达给定的 CPU 时,它可以排他性的访问由该令牌保护的任何内容。很多方案可以实现这种基于令牌的机制,例如:

  1. 维护一个每 CPU 标志,对于除一个 CPU 之外的所有 CPU,其标志始终为 0。当某个 CPU 的标志非 0 时,它持有令牌。当它不需要令牌时,将令牌置 0,并将下一个 CPU 的标志设置为 1 或其他任何非 0 标志值。
  2. 维护每 CPU 计数器,其初始值设置为对应 CPU 的编号,我们假定其范围值为 0 到 N-1,其中 N 是 CPU 的数目。当某个 CPU 的计数大于下一个 CPU 的计数时(要考虑计数的溢出),这个 CPU 持有令牌。当它不需要令牌时,它将下一个 CPU 的计数器设置为一个比自己的计数更大的值。

这种锁不太常见,因为即使没有其他 CPU 正在持有令牌,给定的 CPU 也不一定能立即获得令牌。相反,CPU 必须等待直到令牌到来。当 CPU 需要定期访问临界区的情况下这种方法很有用,但是必须要容忍不确定的令牌传递速率。Gamas 等人使用它来实现一种 RCU 的变体,但是这种方法也可以用于保护周期性的每 CPU 操作,例如冲刷内存分配器使用的每 CPU 缓存,或者垃圾收集的每 CPU 数据结构,又或者是将每 CPU 数据写入共享内存(或大容量存储)。

随着越来越多的人熟悉并行硬件及并且越来越多的并行化代码,我们可以期望出现更多的专用加解锁原语。不过,你应该仔细考虑这个重要的安全提示,只要可能,尽量使用标准同步原语。标准同步原语与自己开发的原语相比,最大的优点就是标准原语通常更不容易出现 BUG。

基于所的存在保证

并行编程一个关键挑战是提供存在保证,使得在整个访问尝试过程中,可以在保证该对象存在的前提下访问给定对象。在某些情况下,存在保证是隐式的。

  1. 基本模块中的全局变量和静态局部变量在应用程序正在运行时存在。
  2. 加载模块中的全局和静态局部变量在该模块保持加载时存在。
  3. 只要存在至少一个函数还在被使用,包括将保持加载状态。
  4. 给定的函数实例的堆栈变量,在该实例返回前一直存在。
  5. 如果你正在某个函数中执行,或者正在被这个函数调用(直接或间接),那么这个函数一定有一个获得实例。

虽然这些隐式存在保证非常直白,但是设计隐式存在保证的故障真的发生过。

但更有趣也更麻烦的涉及堆内存的存在保证,动态分配的数据结构将存在到它被释放为止。这里要解决的问题是如何将结构的释放和对其的并发访问同步起来。一种方法是使用显式保证,例如加锁。如果给定结构只能在持有一个给定的锁时被释放,那么持有锁就保证那个结构的存在。

但这种保证取决于锁本身的存在。一种保证锁存在的简单方式是把锁放在一个全局变量内,但全局锁具有可扩展性受限的特点。有种可以让可扩展性随着数据结构的大小增加而改进的方法,是在每个元素中放置锁的结构。不幸的是,把锁放在一个数据元素中以保护这个数据元素本身的做法会导致微秒的竟态条件。

解决该问题的方式是使用一个全局锁的哈希集合,使得每个哈希桶都有自己的锁。该方法允许在获取指向数据元素的指针之前获取合适的锁。虽然这种方式对于只存放单个数据结构中的元素非常有效,比如哈希表,但是如果有某个数据元素可以是多个哈希表成员,或者更复杂的数据结构,比如树或图时,就会有问题了。不过这些问题还是可以解决的,事实上,这些解决办法形成了基于锁的软件事务性内存实现。后续将介绍如何简单快速地提供存在保证。

锁:英雄还是恶棍

如现实生活中的情况一样,锁可以是英雄也可以是恶棍,既取决于如何使用它,也取决于要解决的问题。以作者的经验,那些写应用程序的家伙很喜欢锁,那些写并行库的同行不那么开心,那些需啊哟并行化现有顺序库的人则非常不爽。

应用程序中的锁:英雄

当编写整个应用程序时(或整个内核)时,开发人员可以完全控制设计,包括同步设计,假设设计中能够良好地使用分割,锁可以是非常有效的同步机制,锁在生产环境级别的高质量并行软件中大量使用已经说明了一切。

然而,尽管通常其大部分同步设计是基于锁,这些软件也几乎总还是利用了其他一些同步机制,包括特殊计数算法、数据所有权、引用计数、顺序锁和 RCU。此外,业界也使用死锁检测工具。获取/释放锁平衡工具、高速缓存未命中分析和基于计数器的性能剖析等等。

通过仔细设计、使用良好的同步机制和良好的工具,锁在应用程序和内核领域工作的相当出色。

并行库中的锁:只是一个工具

与应用程序和内核不同,库的设计者不知道与库函数交互的代码中锁是如何设计的。事实上,那段代码可能在几年后才会出现。因此,库函数设计者对锁的控制力较弱,必须在思考同步设计时更加小心。

死锁当然是需要特别关注的,这里需要运用前面介绍死锁时提到的技术。一个流行的死锁避免策略是确保库函数中的锁是整个程序的锁层次中的独立子树。然而,这个策略实现起来可能比他看起来更难。

前面死锁一节中讨论了一种复杂情况,即库函数调用应用程序代码,qsort() 的比较函数的参数是切入点。另一个复杂情况是与信号处理程序的交互。如果库函数接收的信号调用了应用程序的信号处理函数,几乎可以肯定这会导致死锁,就像库函数直接调用了应用程序的信号处理程序一样。最后一种复杂情况发生在那些可以在 fork()exec() 之间使用的库函数,例如,由于使用了 system() 函数。在这种情况下,如果你的库函数在 fork() 的时候持有锁,那么子进程就在持有该锁的情况下出生。因为会释放锁的线程在父进程运行,而不是子进程,如果子进程调用你的库函数,死锁会随之而来。

在这些情况下,可以使用一下策略来避免死锁问题:

  1. 不要使用回调或信号。
  2. 不要从回调或信号处理函数中获取锁。
  3. 让调用者控制同步。
  4. 将库 API 参数化,以便让调用者处理锁。
  5. 显式地避免回调死锁。
  6. 显式地避免信号处理程序死锁。

既不使用回调,也不使用信号

如果库函数避免使用回调,并且应用程序作为一个整体也避免使用信号,那么由该库函数获得的任何锁将是锁层次中的叶子节点。这种安排避免了死锁。虽然这个策略在其适用时工作的非常好,但是有一些应用程序必须使用信号处理程序,并且有一些库函数必须使用回调。这时可以使用下一个策略。

避免在回调和信号处理函数中用锁

如果回调和处理函数都不获取锁,他们就不会出现在死锁循环中,这使得库函数只能成为锁层次树上的叶子节点。这个策略对于 qsort 的大多数使用情况非常有效,它的回调通常只是比较两个传递给回调的值。这个策略也奇妙地适合许多信号处理函数,通常来说在信号处理函数内获取锁是不明智的行为,但如果应用程序需要处理来自信号处理函数的复杂数据结构,这种策略可能会行不通。

这里有一些方法,即便必须操作复杂的数据结构也可以避免在信号处理函数中获取锁。

  1. 使用基于非阻塞同步的简单数据结构。
  2. 如果数据结构太复杂,无法合理使用非阻塞同步,那么创建一个允许非阻塞入队操作的队列。在信号处理函数中,而不是在复杂的数据结构中,添加一个元素到队列,描述所需的更改。然后一个单独的线程在队列中将元素删除,并执行需要使用锁的更改。关于并发队列已经有很多现成的实现。

这种策略应当在偶尔的人工或(最好是)自动的检查回调和信号处理函数时强制使用。当进行这些检查时要小心警惕,防止那些聪明的开发者(不明智地)自制一些使用原子操作的加锁原语。

调用者控制的同步

让调用者控制同步。当调用者可控数据结构的不同实例调用库函数时,这招非常管用,这时每个实例都可以单独同步。例如,如果库函数要操作一个搜索树,并且如果应用程序需要大量的独立搜索树,那么应用程序可以将锁与每个树关联。然后应用程序获取并根据需要来释放锁,使得库函数完全不需要知道并行性。

但是,如果库函数实现的数据结构需要内部并发执行,则此策略将失败。例如,哈希表或并行排序。在这种情况下,库绝对必须控制自己的同步。

参数化的库函数同步

这里的想法是向库的 API 添加参数以指定要获取的锁、如何获取和释放锁。该策略允许应用程序通过指定要获取的锁(通过传入指向所的指针等)以及如何获取它们(通过传递指针来加锁和解锁),来全局避免死锁。而且还允许线程给定的库函数通过决定加锁和解锁的位置,来控制自己的并发性。

特别的,该策略允许加锁和解锁函数根据需要来阻塞信号,而不需要库函数代码关心那些信号需要被哪些锁阻塞。这种策略使用的分离关注点的方式十分有效,不过在某些情况下,后续介绍的策略将会表现的更好。

也就是说,如果需要明确的将指向所的指针传递给外部 API,必须非常小心考虑。虽然这种做法有时在所难免,但你总应该试着寻找一种替代设计。

明确地避免回调死锁

前面已经讨论了此策略的基本规则:在调用未知代码之前释放所有锁。这通常是最好的办法,因为它允许应用程序忽略库函数的锁层次结构,库函数仍然是应用程序锁层次结构中的一个叶子节点或孤立子树。

若在调用未知代码之前不能释放所有的锁,死锁一节介绍的分层锁层级就适合这种情况。例如,如果未知代码是一个信号处理函数,这意味着库函数要在所有持有锁的情况屏蔽信号,这种做法复杂且缓慢。因此,在信号处理函数(可能不明智地)获取锁的情况,可以使用下一种策略。

明确地避免信号处理函数死锁

信号处理函数的死锁可以按如下方式明确避免:

  1. 如果应用程序从信号处理函数中调用库函数,那么每次在除信号处理函数以外的地方调用库函数时,必须阻塞该信号。
  2. 如果应用程序在持有从某个信号处理函数中获取的锁时调用库函数,那么每次在除信号处理函数之外的地方调用库函数时,必须阻塞该信号。

这些规则可以通过使用类似 Linux 内核的 lockdep 锁依赖关系检测工具来检查。lockdep 的一大优点就是它从不受人类直觉的影响。

在 fork() 和 exec() 之间使用的库函数

如前所述,如果执行库函数的线程在其他线程调用 fork 时持有锁,父进程的内存会被复制到子进程,这个事实意味着子进程从被创建的那一刻就持有该锁。负责释放锁的线程运行在父进程的上下文,而不是在子进程,这意味着子进程中这个锁的副本永远不会被释放。因此,任何在子进程中调用相同库函数的尝试都将会导致死锁。

这个问题的解决方法是让库函数检查是否锁的持有者仍在运行,若不是,则通过重新初始化来“撬开”锁并再次获取它。然而,这种方法有几个漏洞:

  1. 受该锁保护的数据结构可能在某些中间状态,所以简单的“撬开”锁可能会导致任意内存被更改。
  2. 如果子进程创建了额外的线程,则两个线程可能会同时“撬开”锁,结果是两个线程都相信自己拥有锁。从而再次导致任意内存被更改。

atfork() 函数就是专门用来帮助处理这些情况的。这里的想法是注册一个三元组函数,一个由父进程在 fork 之前调用,一个由父进程在 fork 之后调用,一个由子进程在 fork 之后调用。然后可以在这三个点进行适当的清理工作。

但是要注意,atfork 处理函数的代码通常十分微秒。atfork 最适合的情况是锁保护的数据结构可以简单的由子进程重新初始化。

讨论

无论使用何种策略,对库 API 的描述都必须包含该策略和调用者如何使用该策略的清晰描述。简而言之,设计并行库时使用锁是完全可能的,但没有像设计并行应用程序那样简单。

并行化串行库时的锁:恶棍

随着到处可见的低成本多核系统的出现,常见的任务往往是并行化已有的库,这些库的设计仅考虑了单线程使用的情况。从并行编程的角度看,这种对于并行性的全面忽视可能导致库函数 API 的严重缺陷。比如:

  • 隐式的禁止分割。
  • 需要锁的回调函数。
  • 面向对象的意大利面条式代码。

禁止分割

假设你正在编写一个单线程哈希表实现。可以很容易并且快速地得到哈希表中元素总数的精确计数,同时也可以很容易并且快速地在每次添加和删除操作后返回此计数。所以为什么在实际中不这么做呢?

一个原因是精确计数器在多核系统上要么执行错误,要么扩展性不佳。因此,并行化这个哈希表的实现将会出现错误或者扩展性不佳的情况。

那么我们能做什么呢?一种方式是返回近似计数,另一种方式是完全不用元素计数。无论哪种方式,都有必要检查哈希表的使用,看看为什么添加和删除操作需要元素的精确计数。这里有几种可能性:

  1. 确定何时调整哈希表的大小。这时,近似计数应该工作得很好。调整大小的操作也可以由哈希桶中最长链的长度触发,如果合理分割每个哈希桶的话,那么很容易得出每个链的长度。
  2. 得到遍历整个哈希表所需的大概时间。这时,使用近似计数也不错。
  3. 处于诊断的目的。例如,检查传入哈希表和从哈希表传出时丢失的元素。然而,鉴于这种用法是诊断性目的,分别维护每个哈希链的长度也可以满足要求,然后偶尔再锁住添加删除操作时将各个长度求和输出。

现在有一些理论基础研究,阐述了并行库 API 在性能和扩展性上受到的约束。任何设计并行库的人都需要密切注意这些约束。

虽然对于一个对并发不友好的 API 来说,人们很容易去职责锁是罪魁祸首,但这并没有用。另一方面,人们除了同情当年写下这段代码的倒霉程序员之外,也没有什么更好的办法。如果程序员能在 1985 年就能遇见未来对并行性的需求,那简直是稀罕和高瞻远瞩,如果那时就能设计出一个对并行友好的 API,那真是运气和荣耀的罕见巧合了。

随着时间的变化,代码必须随之改变。也就是说,如果某个受欢迎的库拥有大量用户,在这种情况下对 API 进行不兼容的更改将是相当愚蠢的。添加一个对并行友好的 API 来补充现有的串行 API,可能是这种情况下的最佳行动方案。

然而,出于人类的本性,不行的开发者们更可能抱怨的是锁带来的问题,而不是他们自身对糟糕(虽然可以理解) API 的设计选择。

容易死锁的回调

前面已经描述了对回调的无规律使用将提高加锁的难度,同时还描述了如何设计库函数来避免这些问题,但是期望一个 20 世纪 90 年代的程序员在没有并行编程经验时就能遵循这些设计,是不是有点不切实际?因此,尝试并行化拥有大量回调的已有单线程程序库的程序员,很可能会相当憎恨锁。

如果有一个库使用了大量回调,可能明智的举动是向库函数中添加一个并行友好的 API,以允许现有用户逐步进行代码的切换。或者,一些人主张在这种情况下使用事务内存。有一点需要注意,硬件事务内存无助于解决上述情景,除非硬件事务内存实现提供了前进保证(forward-progress guarantee),不过很少有事务内存做到这一点。

面向对象的意大利面条式代码

从 20 世纪 80 年代末或 90 年代初的某个时候,面向对象编程变得流行起来,因此在生产环境中出现了大量面向对象式的代码,大部分是单线程的。虽然 OO 是一种很有价值的软件技术,但是毫无节制的使用对象可以很容易写出面向对象式的意大利面条代码。在面向对象式的意大利面条代码中,执行流基本上是以随机的方式从一个对象走到另一个对象,使得代码难以理解,甚至无法加入锁层次结构。

虽然很多人可能会认为,不管在任何情况下这样的代码都应该清理,说着容易做着难。如果你的任务是并行化这样的野兽,通过对前面描述的技巧的运用,以及后续将继续讨论的技术,你对人生(还有锁)感到绝望的机会会大大减少。这种场景似乎是事务性内存出现的原因,所以事务内存也值得一试。也就是说,应该根据前面讨论的硬件习惯来选择同步机制,如果同步机制的开销大于那些被保护的操作一个数量级,结果必然不会漂亮。

这些情况下有一个问题值得提出,代码是否应该继续保持串行执行?例如,或许在进程级别而不是线程级别引入并行性。一般来说,如果任务证明是非常困难,确实值得花一些时间思考并通过其他方法来完成任务,或者通过其他任务来解决手头的问题。

总结

锁也许是最广泛也最常用的同步工具。然而,最好是在一开始设计应用程序或库时就把锁考虑进去。考虑可能要花一整天的时间,才能让很多已有的单线程代码并行运行,因此锁不应该是并行编程工具箱里的唯一工具。