起因
并发编程最基本的问题就是:我们希望有一些指令能够原子化的执行,但是由于单处理器上的中断(或者多个线程在多处理器上并发执行),我们很难做到。接下来我们来学习锁(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,直到锁被释放后,将其唤醒。