5分钟了解并发编程中的锁

疫情期间我完成了『PHP非侵入式监控平台』的重构与开源,请点击这里获取项目。

计算机中有一门经典的课程叫『操作系统』,里面花很少的篇幅讲了『锁』,锁是在执行多线程时用于强行限制资源访问的同步机制,即用于在并发控制中保证对互斥要求的满足。虽然字不多,但事大,特别是在人人都要懂高并发的今天,『锁』变成了高级程序员的必备技能。

一. 为什么需要锁?

早期的CPU只有单核,同一时间只能做一件事,我们称为顺序执行。虽然操作系统在软件层通过时间片划分能模拟出多线程,但本质上还是串行,此时锁的应用场景非常少。当CPU发展成多核之后真正的并发执行开始出现,计算机真正意义上实现同一时间做多件事。

相比顺序执行,并发执行让计算机的计算能力再次飞跃,比如『天河一号』就是利用多核CPU的并行计算能力。并发执行虽然快但首先要解决的问题是资源同步。比如我们使用2个CPU线程并行去计算1000个耗时的算法题,如何分配资源?我们将2个CPU线程用A,B字母代替,算法题总数用V代替。

因为不希望AB计算同一题,所以当A拿到第一题后,B就不能再拿到第一题。于是在A准备拿第一题时先将总数V锁住,拿完题后将V减一,最后释放锁。B拿题时发现V被锁住,于是阻塞或者轮询,直到V被解锁后再重复A的操作。这样做能解决AB不计算同一题的问题,但也带来了一系列隐患,下文将展开讨论。

并行计算场景中有无数资源需要同步给各个CPU线程,锁无处不在。

二. 使用锁时的常见问题

上文说了AB线程如何利用『锁』解决资源V同步的问题,但有些隐患。这些隐患无论是在线程之间,还是分布式架构下都客观存在,是程序员们要努力解决的问题,也是面试官要学习的问题。

  1. A锁住V后,A线程崩溃导致V的锁无法释放,B永远拿不到资源V;
    这个问题非常难解决,近几十年科学家们都没给出一个完美方案,但给了一系列折中办法。常见办法之一就是使用『CAS+自旋』乐观锁,它利用CPU提供的硬件级指令让A线程对V资源的变更变成一个原子操作,原子操作的好处就是要么成功要么失败,不会被中断。另一种常见办法是给锁加时间限制,比如每个线程只能锁住资源1秒。还有一种办法是给B线程加权,比如B线程尝试10次后系统直接让B线程获取资源V。这些办法都非常经典,下文会具体讨论。

  2. A给V加的锁是互斥锁,它保证了资源被独占。这种锁用在频繁更新的资源上会造成大量的阻塞唤醒和资源浪费。
    优化此类问题有两点技巧,一是减少锁资源的时间(不要将执行耗时的代码放到数据临界区),二是减少更新资源的次数(读锁不会阻塞)。对于V这种资源使用消息队列更合适,提前将1000个算法题按编号存入消息队列,AB线程只需要调用队列的读接口获取数据,不用触发更新操作,也就不会加互斥锁。当然消息队列也需要考虑锁的问题,但无锁消息队列的技术实现已经非常成熟。

为了解决锁带来的CPU资源浪费/死锁/饥饿等问题,下面列举了常见的解决方案和使用场景。

乐观锁

乐观锁很乐观,对其他线程毫无防备之心,不会锁资源,是个老好人。技术上一般通过CAS自旋实现。CAS是CPU提供的原子操作,指令大致如下cmpxchg B V A B是新值,V是内存位置,A是预期原值(比如要把变量V从90改为100,对应的指令为cmpxchg 100 &V 90)。如果V内存位置的值与预期原值90相匹配,那么处理器会自动将该位置值更新为新值100,否则处理器不做任何操作。一般我们不希望CAS失败,所以会不停的重试直到成功,这种方式就叫自旋。

我们经常听到无锁版队列、无锁版链表、无锁版数据结构和算法等,他们的名字都很响亮但技术并没有多高深,基本上都通过CAS实现。内存屏障也可用来实现无锁技术,感兴趣的朋友请自行Google。

乐观锁是一个深藏功与名的技术,因为世界上最厉害的锁就是无锁胜有锁。CAS虽然高效,但也存在三大问题(当前这三大问题都有很成熟的解决方案)。

  1. ABA问题。

CAS需要在操作值的时候检查内存值是否发生变化,没有发生变化才会更新内存值。但是如果内存值原来是A,后来变成了B,然后又变成了A,那么CAS进行检查时会发现值没有发生变化,但是实际上是有变化的。ABA问题的解决思路就是在变量前面添加版本号,每次变量更新的时候都把版本号加一,这样变化过程就从“A-B-A”变成了“1A-2B-3A”。

  1. 循环时间长开销大。

CAS操作如果长时间不成功,会导致其一直自旋,给CPU带来非常大的开销。所以需要根据实际需求选择要不要用乐观锁。

  1. 只能保证一个共享变量的原子操作。

对一个共享变量执行操作时,CAS能够保证原子操作,但是对多个共享变量操作时,CAS是无法保证操作的原子性的。

悲观锁

悲观锁很悲观,因为不想被其他线程打扰所以会对资源加锁,是个孤独的王者。悲观锁能解决很多难题,相比乐观锁他的扩展性极强。上文AB线程中的『互斥锁』就是悲观锁的一种。悲观锁虽然功能强大但很容易导致大量CPU切换,资源死锁等问题。操作难度MAX,常用来鉴别高级程序员与普通程序员。下面说说悲观如何解决阻塞线程与造成死锁的问题。

使用自旋锁优化CPU上下文切换 - 线程被阻塞或唤醒需要操作系统切换CPU状态来完成,这种状态转换需要耗费处理器时间。但大多数情况下线程进入阻塞然后再唤醒的时间比资源被锁住后释放的时间长的多。为了让当前线程“稍等一下”,我们需让当前线程进行自旋,如果在自旋完成后前面锁定同步资源的线程已经释放了锁,那么当前线程就可以不必阻塞直接获取同步资源,从而避免切换线程的开销。这就是自旋锁,合理的引入自旋锁能帮助我们优化线程切换的开销。

使用公平锁与非公平锁来平衡饥饿与CPU上下文切换问题:

  1. 公平锁- 当多个线程抢占同一个资源时,大家按先后顺序排队获取,符合核心价值观。带来的好处是等待锁的线程不会饿死,总会排到资源。缺点是整体吞吐效率相对非公平锁要低,等待队列中除第一个线程以外的所有线程都会阻塞,CPU唤醒阻塞线程的开销比非公平锁大。

  2. 非公平锁 - 当多个线程抢占同一个资源时,资源释放时哪个线程发起了抢占就给哪个线程,可以理解为插队,但程序员允许他插队。这样做可以减少唤起线程的开销,整体的吞吐效率高,因为线程有几率不阻塞直接获得锁,CPU不必唤醒所有线程。缺点是处于等待队列中的线程可能会饿死,或者等很久才会获得锁。

智能锁

文章写到这里会发现锁对程序员很不友好,小明只想实现一个简单的并发功能,结果考虑用什么锁就耗费了几天。好在程序员都喜欢封装代码,比如JAVA官方就封装了一套好用的”智能锁”,不用考虑过多细节,直接用。他的实现原理大致如下:

  1. 偏向锁 - 当线程A访问临界资源时,系统会为线程A加上偏向锁,”偏向于第一个获得它的线程”的锁。执行数据更新之后,线程并不会释放偏向锁,第二次再访问该临界资源时就不用加锁了,可以理解为超级通行证,如果至始至终都没有其他线程来抢占资源,偏向锁性能极高。

  2. 轻量级锁 - 当有其他线程B来抢占资源时,偏向锁就升级为轻量级锁。B会通过自旋去判断A线程是否释放了资源。此时有两种可能,一是A线程被销毁了,那么B自动成为偏向锁。二是A线程还存在,那么A线程会升级为轻量级锁,B线程等待A线程释放资源。

  3. 重量级锁 - B线程的等待是有限度的,不能一直自旋。系统会判断B线程的自旋次数,如果大于10次会将B线程升级为重量级锁。其他线程必须释放锁然后挂起,等B线程更新完数据并释放锁后再继续执行。

通过这种智能锁,程序员几句代码就能享受安全,高效的锁。

最后

锁的原理并不难,但实现起来不容易。主要原因是程序员多年培养的编程思维都是基于顺序执行的,如果用顺序执行的思维方式去写并发执行的代码很容易踩坑。

说下并发编程的三个概念和对应的挑战:

  1. 原子性问题 - 即一个操作或者多个操作要么全部执行,要么就都不执行,并且执行的过程不会被任何因素打断,通常原子性问题要通过硬件来实现,比如CAS。需要对硬件指令了解。

  2. 可见性问题 - 当多个线程访问同一个变量时,一个线程修改了这个变量的值,其他线程能够立即看得到修改的值。比如执行100-1后其他线程看到的是不是99?大部分情况下是99,但在某些极端情况下会出问题,比如CPU多级缓存中的某一级缓存返回的缓存值为100。需要对CPU的缓存机制熟悉。

  3. 有序性问题 - 通常程序会按顺序执行,但原始程序通过编译器优化或者CPU指令重排后可能不会按照我们代码的顺序执行,特别是在并发执行的代码下。需要对编译器和CPU指令重排熟悉。

那些精通并发编程的大神,真的可以封神。

打赏时请留下微信号