锁与互斥

悲观锁(Pessimistic Locking)

悲观并发控制,又名悲观锁(Pessimistic Concurrency Control,PCC)是一种并发控制的方法。它可以阻止一个事务以影响其他用户的方式来修改数据。如果一个事务执行的操作都某行数据应用了锁,那只有当这个事务把锁释放,其他事务才能够执行与该锁冲突的操作。悲观并发控制主要用于数据争用激烈的环境,以及发生并发冲突时使用锁保护数据的成本要低于回滚事务的成本的环境中。

在编程语言中,悲观锁可能存在以下缺陷:

  • 在多线程竞争下,加锁、释放锁会导致比较多的上下文切换和调度延时,引起性能问题。

  • 一个线程持有锁会导致其它所有需要此锁的线程挂起。

  • 如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置,引起性能风险。

数据库中悲观锁主要由以下问题:悲观锁大多数情况下依靠数据库的锁机制实现,以保证操作最大程度的独占性。如果加锁的时间过长,其他用户长时间无法访问,影响了程序的并发访问性,同时这样对数据库性能开销影响也很大,特别是对长事务而言,这样的开销往往无法承受,特别是对长事务而言。如一个金融系统,当某个操作员读取用户的数据,并在读出的用户数据的基础上进行修改时(如更改用户帐户余额),如果采用悲观锁机制,也就意味着整个操作过程中(从操作员读出数据、开始修改直至提交修改结果的全过程,甚至还包括操作员中途去煮咖啡的时间),数据库记录始终处于加锁状态,可以想见,如果面对几百上千个并发,这样的情况将导致怎样的后果。

互斥锁/排他锁

互斥锁即对互斥量进行分加锁,和自旋锁类似,唯一不同的是竞争不到锁的线程会回去睡会觉,等到锁可用再来竞争,第一个切入的线程加锁后,其他竞争失败者继续回去睡觉直到再次接到通知、竞争。

互斥锁算是目前并发系统中最常用的一种锁,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 使用一种叫做重入函数的方法保证函数的线程安全,锁粒度是调用而非线程。

读写锁

支持两种模式的锁,当采用写模式上锁时与互斥锁相同,是独占模式。但读模式上锁可以被多个读线程读取。即写时使用互斥锁,读时采用共享锁,故又叫共享-独 占锁。一种常见的错误认为数据只有在写入时才需要锁,事实是即使是读操作也需要锁保护,如果不这么做的话,读写锁的读模式便毫无意义。

乐观锁(Optimistic Locking)

相对悲观锁而言,乐观锁(Optimistic Locking)机制采取了更加宽松的加锁机制。相对悲观锁而言,乐观锁假设认为数据一般情况下不会造成冲突,所以在数据进行提交更新的时候,才会正式对数据的冲突与否进行检测,如果发现冲突了,则让返回用户错误的信息,让用户决定如何去做。上面提到的乐观锁的概念中其实已经阐述了他的具体实现细节:主要就是两个步骤:冲突检测和数据更新。其实现方式有一种比较典型的就是 Compare and Swap。

CAS 与 ABA

CAS 是项乐观锁技术,当多个线程尝试使用 CAS 同时更新同一个变量时,只有其中一个线程能更新变量的值,而其它线程都失败,失败的线程并不会被挂起,而是被告知这次竞争中失败,并可以再次尝试。CAS 操作包含三个操作数 —— 内存位置(V)、预期原值(A)和新值(B)。如果内存位置的值与预期原值相匹配,那么处理器会自动将该位置值更新为新值。否则,处理器不做任何操作。无论哪种情况,它都会在 CAS 指令之前返回该位置的值。CAS 有效地说明了我认为位置 V 应该包含值 A;如果包含该值,则将 B 放到这个位置;否则,不要更改该位置,只告诉我这个位置现在的值即可。这其实和乐观锁的冲突检查+数据更新的原理是一样的。

乐观锁也不是万能的,乐观并发控制相信事务之间的数据竞争(Data Race)的概率是比较小的,因此尽可能直接做下去,直到提交的时候才去锁定,所以不会产生任何锁和死锁。但如果直接简单这么做,还是有可能会遇到不可预期的结果,例如两个事务都读取了数据库的某一行,经过修改以后写回数据库,这时就遇到了问题。

  • 乐观锁只能保证一个共享变量的原子操作。如上例子,自旋过程中只能保证 value 变量的原子性,这时如果多一个或几个变量,乐观锁将变得力不从心,但互斥锁能轻易解决,不管对象数量多少及对象颗粒度大小。

  • 长时间自旋可能导致开销大。假如 CAS 长时间不成功而一直自旋,会给 CPU 带来很大的开销。

  • ABA 问题。

CAS 的核心思想是通过比对内存值与预期值是否一样而判断内存值是否被改过,但这个判断逻辑不严谨,假如内存值原来是 A,后来被 一条线程改为 B,最后又被改成了 A,则 CAS 认为此内存值并没有发生改变,但实际上是有被其他线程改过的,这种情况对依赖过程值的情景的运算结果影响很大。解决的思路是引入版本号,每次变量更新都把版本号加一。部分乐观锁的实现是通过版本号(version)的方式来解决 ABA 问题,乐观锁每次在执行数据的修改操作时,都会带上一个版本号,一旦版本号和数据的版本号一致就可以执行修改操作并对版本号执行 +1 操作,否则就执行失败。因为每次操作的版本号都会随之增加,所以不会出现 ABA 问题,因为版本号只会增加不会减少。

自旋锁

Linux 内核中最常见的锁,作用是在多核处理器间同步数据。这里的自旋是忙等待的意思。如果一个线程(这里指的是内核线程)已经持有了一个自旋锁,而另一条线程也想要获取该锁,它就不停地循环等待,或者叫做自旋等待直到锁可用。可以想象这种锁不能被某个线程长时间持有,这会导致其他线程一直自旋,消耗处理器。所以,自旋锁使用范围很窄,只允许短期内加锁。

其实还有一种方式就是让等待线程睡眠直到锁可用,这样就可以消除忙等待。很明显后者优于前者的实现,但是却不适用于此,如果我们使用第二种方式,我们要做几步操作:把该等待线程换出、等到锁可用在换入,有两次上下文切换的代价。这个代价和短时间内自旋(实现起来也简单)相比,后者更能适应实际情况的需要。还有一点需要注意,试图获取一个已经持有自旋锁的线程再去获取这个自旋锁或导致死锁,但其他操作系统并非如此。

自旋锁与互斥锁有点类似,只是自旋锁不会引起调用者睡眠,如果自旋锁已经被别的执行单元保持,调用者就一直循环在那里看是 否该自旋锁的保持者已经释放了锁,"自旋"一词就是因此而得名。其作用是为了解决某项资源的互斥使用。因为自旋锁不会引起调用者睡眠,所以自旋锁的效率远 高于互斥锁。虽然它的效率比互斥锁高,但是它也有些不足之处:

  • 自旋锁一直占用 CPU,他在未获得锁的情况下,一直运行--自旋,所以占用着 CPU,如果不能在很短的时 间内获得锁,这无疑会使 CPU 效率降低。

  • 在用自旋锁时有可能造成死锁,当递归调用时有可能造成死锁,调用有些其他函数也可能造成死锁,如 copy_to_user()、copy_from_user()、kmalloc()等。

自旋锁比较适用于锁使用者保持锁时间比较短的情况。正是由于自旋锁使用者一般保持锁时间非常短,因此选择自旋而不是睡眠是非常必要的,自旋锁的效率远高于互斥锁。信号量和读写信号量适合于保持时间较长的情况,它们会导致调用者睡眠,因此只能在进程上下文使用,而自旋锁适合于保持时间非常短的情况,它可以在任何上下文使用。如果被保护的共享资源只在进程上下文访问,使用信号量保护该共享资源非常合适,如果对共享资源的访问时间非常短,自旋锁也可以。但是如果被保护的共享资源需要在中断上下文访问(包括底半部即中断处理句柄和顶半部即软中断),就必须使用自旋锁。自旋锁保持期间是抢占失效的,而信号量和读写信号量保持期间是可以被抢占的。自旋锁只有在内核可抢占或 SMP(多处理器)的情况下才真正需要,在单 CPU 且不可抢占的内核下,自旋锁的所有操作都是空操作。另外格外注意一点:自旋锁不能递归使用。

MVCC

为了实现可串行化,同时避免锁机制存在的各种问题,我们可以采用基于多版本并发控制(Multiversion concurrency control,MVCC)思想的无锁事务机制。人们一般把基于锁的并发控制机制称成为悲观机制,而把 MVCC 机制称为乐观机制。这是因为锁机制是一种预防性的,读会阻塞写,写也会阻塞读,当锁定粒度较大,时间较长时并发性能就不会太好;而 MVCC 是一种后验性的,读不阻塞写,写也不阻塞读,等到提交的时候才检验是否有冲突,由于没有锁,所以读写不会相互阻塞,从而大大提升了并发性能。我们可以借用源代码版本控制来理解 MVCC,每个人都可以自由地阅读和修改本地的代码,相互之间不会阻塞,只在提交的时候版本控制器会检查冲突,并提示 merge。目前,Oracle、PostgreSQL 和 MySQL 都已支持基于 MVCC 的并发机制,但具体实现各有不同。

MVCC 的一种简单实现是基于 CAS(Compare-and-swap)思想的有条件更新(Conditional Update)。普通的 update 参数只包含了一个 keyValueSet’,Conditional Update 在此基础上加上了一组更新条件 conditionSet { … data[keyx]=valuex, … },即只有在 D 满足更新条件的情况下才将数据更新为 keyValueSet’;否则,返回错误信息。这样,L 就形成了如下图所示的 Try/Conditional Update/(Try again) 的处理模式:

对于常见的修改用户帐户信息的例子而言,假设数据库中帐户信息表中有一个 version 字段,当前值为 1 ;而当前帐户余额字段(balance)为 100。

  • 操作员 A 此时将其读出(version=1),并从其帐户余额中扣除 50 (100-50)。

  • 在操作员 A 操作的过程中,操作员 B 也读入此用户信息(version=1),并从其帐户余额中扣除 20 (100-20)。

  • 操作员 A 完成了修改工作,将数据版本号加一(version=2),连同帐户扣除后余额(balance=50),提交至数据库更新,此时由于提交数据版本大于数据库记录当前版本,数据被更新,数据库记录 version 更新为 2 。

  • 操作员 B 完成了操作,也将版本号加一(version=2)试图向数据库提交数据(balance=80),但此时比对数据库记录版本时发现,操作员 B 提交的数据版本号为 2 ,数据库记录当前版本也为 2 ,不满足提交版本必须大于记录当前版本才能执行更新的乐观锁策略,因此,操作员 B 的提交被驳回。这样,就避免了操作员 B 用基于 version=1 的旧数据修改的结果覆盖操作员 A 的操作结果的可能。

从上面的例子可以看出,乐观锁机制避免了长事务中的数据库加锁开销(操作员 A 和操作员 B 操作过程中,都没有对数据库数据加锁),大大提升了大并发量下的系统整体性能表现。需要注意的是,乐观锁机制往往基于系统中的数据存储逻辑,因此也具备一定的局限性,如在上例中,由于乐观锁机制是在我们的系统中实现,来自外部系统的用户余额更新操作不受我们系统的控制,因此可能会造成脏数据被更新到数据库中。

链接