分布式初探——面包店算法与多线程锁
- 2020 年 3 月 5 日
- 筆記
点击上方蓝字，和我一起学技术。
今天的文章我们介绍面包店算法。
这个算法是由分布式系统大佬lamport提出的，用来解决多线程抢占资源的锁控制问题。在之前介绍数据库事务原则的时候，曾经介绍过隔离性。不仅在数据库当中，在并发系统当中，只要出现多个线程抢占一个资源的情况，就必然需要引入锁来实现隔离。保证一次只能有一个线程占有资源，防止线程之间的读写操作混乱，导致数据错误。今天讲的面包店算法，就是针对这个场景，实现线程之间隔离的。
算法的原理并不难，我们日常生活当中就经常用到。我们应该都有这样的经历，当我们去商场的餐馆吃饭的时候。由于用餐的人太多，所以需要排队。
但是商场不可能真的让顾客排成一队，不仅可能会影响通道畅通，而且也不方便顾客。万一顾客还想去买点东西或者是上个厕所，都不方便。所以为了解决这个问题，商场有了叫号的机制。每个排队的顾客都会拿一个号码，当商场里有了空位之后，会让号码最小的顾客进去用餐。这个过程就是面包店算法了，只不过Lamport大神当时可能还没有叫号机，所以他想的场景是面包店买面包，买什么不重要，原理大同小异。
我们对叫号的原理进行一点变形，我们假设这个餐厅只有一个位置，一次只能允许一个客人进去用餐。并且我们假设所有的顾客都会一直排队，不会中途走开。做完了这两个假设之后，我们将问题的场景做一个映射。我们把餐厅当成是内存里的一块抢占资源，排队的客人映射成等待资源的线程，用餐的过程映射成线程读写资源。那么，只要线程像是顾客一样会取号排队，不就可以保证线程之间不会出现抢占以及同时读写的问题了吗？的确如此，我们的直观感受是对的，并且整个算法的代码非常简单，我们很容易就可以用Python实现：
import threading import time # 全体线程取的号，存放在公共区域 number = [0 for _ in range(5)] # 表示线程i是否还没有号码，True表示还没有号码，False表示已经获得号码 entering = [False for _ in range(5)] # 获取资源，打印出当前获取资源的线程id def achieve_resource(num): print('Now is no.{} thread achieve the resource'.format(num)) time.sleep(1) def lock(num): # True表示还没有拿到号码 entering[num] = True # 取号，等于当前最大号码的下一位 number[num] = max(number) + 1 # 修改状态，表示已经取过号了 entering[num] = False for i in range(5): # 一直等待到i线程取号为止 while entering[i]: pass # 如果i线程的号码比自己小，则等待 # 如果号码一样，则线程id小的优先 while ((number[i] != 0) and (number[num], num) < (number[i], i)): pass # 解锁，即将号码销毁 def unlock(num): number[num] = 0 # 发起一个抢占资源的请求 def start_request(num): while True: lock(num) achieve_resource(num) unlock(num) if __name__ == "__main__": threads = [] for i in range(5): t = threading.Thread(target=start_request, args=(i,)) t.start()
我们运行代码，可以得到如下结果：
线程之间保持顺序，并且抢占的顺序不是固定的存在随机性，说明我们的算法生效，起到了效果。但如果了解一点Python当中GIL机制，会发现在Python当中，即使我们起多线程去获取一个资源，一般也不会导致线程不安全。这是因为Python是解释型语言，同一时刻，同一个Python解释执行的进程，只会执行一个线程。就好像Python是run在一个单核的CPU上，我们起再多线程，同时也只能执行一个。
面包店算法本身理解起来并不算难，在操作系统的课本里就有相关内容。反而是它背后涉及到的知识更加困难一些，我们试着简单来了解一下。
首先，面包店算法究竟起到什么作用呢？我们通过加锁也可以实现多个线程抢占引发的问题，相比之下，它有什么特点呢，我们为什么要了解这样一个算法呢？
按照维基百科里的说法是：它最大的特点是可以不需要依赖硬件的原子操作，也就是说可以纯软件实现。
这一句话虽然简单，但是理解起来并不容易。首先，什么是原子操作呢，它和硬件又有什么关联呢？
这里的原子和数据库事务原则里的原子性是一个意思，指的是某个指令或者是某些指令要么不做，要么全做，不允许出现中间状态。我们先来看最简单的单CPU的情况，对于单CPU，一次只能执行一个线程，单条指令的执行天然就是原子的。因为同一时刻只会有一个线程在执行，不会存在抢占的情况。我们只需要保证指令的执行顺序，就可以保证原子操作的正确性。
总线锁
对于多CPU的场景而言，就无法保证了，因为可能会出现多个线程或进程同时读写同一块内存的情况。这种情况下显然没有办法保证操作的正确性。为了解决这个问题，一个解决方案是加上硬件锁。所谓的硬件锁就是当某个线程读写内存的时候，将总线的电平拉低，从而锁住系统总线，防止其他线程读写内存。
这种方式显然太简单粗暴了，并且极端情况下会丧失大量性能，我们想要通过多线程或多进程来提升系统并发能力的初衷就达不到了。
缓存锁
针对这种情况，又提出了缓存锁。
因为在CPU当中除了内存之外，还会好几块缓存。我们可以将CPU的原子操作挪到CPU中的某一块缓存当中执行，这样我们就只需要锁住某一块缓存就行了，就可以不用锁住整块内存了。
当然由于缓存和内存存在数据交互，所以实际的操作要复杂得多，我们不需要探究那么深入，只需要在原理上了解即可。
上面说的总线索和缓存锁都需要CPU硬件角度提供支持才行，硬件支持的锁相比之下使用起来要复杂一些，而且限制较多，并不是所有系统都能够支持。因此，通过软件实现的锁更加普遍，下面再介绍一种通过软件实现的多线程锁——自旋锁。
自旋锁
自旋锁看着名字新奇，但是含义很简单。意思是在多线程的场景当中，当一个线程无法获取到临界区资源的时候，不是挂起等待，而是会一直保持执行，反复查询锁变量是否可用。也就是说是一种忙等待。
这样做的好处是线程不需要被挂起，可以减少操作系统执行过程当中的上下文切换带来的开销。
在Java当中，自旋锁有一个非常著名的实现算法，叫做CAS(compare and swap)。翻译过来的意思是比较和替换，在Java很多并发场景当中都用到了CAS的技术，也是Java程序员经常问的问题之一。
CAS的原理很简单，我们会对于每一个操作的对象设置一个期望值，当我们从内存中读取到的结果和期望值不一致的时候，我们会自旋再次读取。如果和期望值一致，说明此时其他线程没有造成干扰，那么就进行修改。
我们直接来看Java内部的实现代码：
public final int getAndAddInt(Object o, Long offset, int delta) { int v; do { v = getIntVolatile(o, offset); } while (!compareAndSwapInt(o, offset, v, v+delta)); return v; }
在上面这段代码当中，v是之前读取的值，也就是期望值。我们会传入内存的位置，在赋值之前再次读取。只有两者吻合才会进行赋值操作，否则会返回失败，程序继续循环。
无论是代码还是原理，我们都看得出来，CAS的实现并不难，在一些问题上的表现也很好。因此在Java并发场景以及操作系统的很多领域，CAS大量使用。但CAS并不是万能的，它也存在缺陷。比如循环的时间不可控，可能会很长，再比如CAS只能控制一个变量的原子性。如果存在多个变量需要维护，CAS就不能保证了。
最关键的一点是ABA问题，ABA问题很简单，比如某一次读取某个变量的时候它的值是A，当我们准备赋值检查它的时候，它还是A，这能说明它没有发生过改变吗？
最简单的一个例子，一个人买东西准备扣款，扣款之前可能他又买了别的东西，并且获取了一笔收入。两者的价格刚好相等，所以当检查的时候，余额并没有发生变化。但是显然这中间发生过修改，在一些特殊情况下可能会导致严重的问题。
身为分布式系统的奠基人之一，面包店算法只不过是Lamport大佬随手而做的作品（很有可能就是在买面包的时候想出来的），但对我们学习者来说，依然非常有参考和学习意义，希望大家都能体会到其中的精髓和美感。
本文到这里就结束了，如果觉得有所收获，就请点个”在看“或者转发吧。
