Mutual Exclusion 并发算法到底有多难

Mutual Exclusion 互斥#

https://en.wikipedia.org/wiki/Mutual_exclusion

在多线程并发编程时，为了防止竞态条件(race condition)，需要控制同时只有一个线程进入临界区(critical section)。

想象一下，当两个线程要同时访问并修改一个变量时：

# thread 1
.
x = x + 1
.

# thread 2
.
x = x + y
.

在并发执行的情况下，可能会导致一个线程的赋值覆盖了另一个线程的赋值，从而导致错误。(简单的对一个内存变量进行累加是线程不安全的：https://stackoverflow.com/questions/10503737/is-increment-an-integer-atomic-in-x86)

为了防止上面的问题，需要将访问变量 x 的相关代码设定为临界区，并保证同时只有一个线程进入临界区操作变量x。

有多种方式可以保证临界区的互斥性，在编程时我们通常使用编程语言提供的线程锁或信号量等其它线程间通信的机制来实现互斥。

编程语言提供的互斥机制通常也是通过操作系统内核来实现的，后者会借用一些硬件特性来实现互斥。

人们也发明了一些算法来实现互斥，通过算法实现并发控制直觉上感觉很简单，但其实有很多难点。

简单但错误的例子#

import time
from concurrent.futures import ThreadPoolExecutor

run_times = 3
count = 0
flag = -1


def mutual_exclusion(self_id):
    global count, flag
    for _ in range(0, run_times):
        while flag == -1:
            flag = self_id

        # critical section begin
        tmp = count + 1
        time.sleep(0.1)
        count = tmp
        print(f"thread {self_id} {tmp}")
        # critical section end

        flag = -1


if __name__ == "__main__":
    with ThreadPoolExecutor() as executor:
        futures = executor.map(mutual_exclusion, [0, 1])
        executor.shutdown(wait=True)
    print(f"expect count: {run_times * 2}, final count is: {count}")

由于Python本身有GIL的存在，所以这里通过 time.sleep(0.1) 来模拟触发并发情况。

上面的代码在我的电脑运行后会输出：

thread 0 1
thread 1 1
thread 1 2
thread 0 2
thread 1 3thread 0 3

expect count: 6, final count is: 3

从输出上可以看到互斥失败，线程会同时进入临界区执行代码。可以注意到，由于多线程输出，偶尔会出现两个线程的输出在同一行的情况。

对于多线程并发编程没有经验的人可能会写出上面的代码，在并发执行时，多个线程会同时判断 flag == -1 为真，从而同时进入临界区，实际效果就是没有达到互斥的作用。

Livelock#

通过增加一次判断，可以解决上面代码中无法真正互斥的问题，代码如下：

run_times = 3
count = 0
flags = [False, False]


def mutual_exclusion(self_id):
    global count, flags
    for _ in range(0, run_times):
        # 进入临界区之前的自旋
        while True:
            flags[self_id] = True
            if flags[1 - self_id]:
                flags[self_id] = False
            else:
                break

        # critical section begin
        tmp = count + 1
        time.sleep(0.01)
        count = tmp
        print(f"thread {self_id} {tmp}")
        # critical section end

        flags[self_id] = False

示例代码中使用了一个小技巧，由于只有两个线程并发，id分别设置为0和1，因为 1-0=1 而 1-1=0 所以 flags[1 - self_id] 可以用来简单的判断另一个线程设置的flag状态。

上面代码虽然解决了互斥的问题，却有一个不易察觉的缺陷，在进入临界区之前的自旋加锁过程中，有可能会出现两个线程同时设置flag，又同时判断对方设置了flag，又同时将自己的flag移除，然后同时再次循环。

在高并发环境中，这种相互等待可能会很快结束，也可能会持续一段时间，从而使系统产生意外的延迟并严重影响性能。这种情况称为livelock: https://en.wikipedia.org/wiki/Deadlock#Livelock

两个线程长时间相互等待这种情况看起来可能不太容易出现，也很难测试出来，如果在代码中增加一个sleep放大并发的可能性，会发现代码会陷入无限的循环等待中：

while True:
    flags[self_id] = True
    if flags[1 - self_id]:
        time.sleep(0.01)
        flags[self_id] = False
    else:
        break

在一些网络系统中为避免livelock的产生，会在flage[self_id] = False设置自己的状态后，等待一个随机的时间再进入下一次循环。

Starvation#

通过让线程间产生一些避让可以解决livelock的问题，例如下面的代码：

def mutual_exclusion(self_id):
  global count, flags
  for _ in range(0, run_times):
      while True:
          flags[self_id] = True
          if flags[1 - self_id]:
              time.sleep(0.01)
              if self_id == 1:
                  flags[self_id] = False
                  time.sleep(0.01)
          else:
              break

      # critical section begin
      tmp = count + 1
      time.sleep(0.01)
      count = tmp
      print(f"thread {self_id} {tmp}")
      # critical section end

      flags[self_id] = False

当1号线程发现对方线程也在进入临界区时，将自己的flag设为False并sleep一段时间，为了证明算法解决了livelock问题，代码中保留了产生livelock的sleep语句。

然而这个代码又产生了一个新的问题，通过查看执行结果可以发现，0号线程由于优先级较高，会持续抢占执行权，只有当其执行完成后，1号线程才能获得执行权。

这种情况叫做：Starvation(https://en.wikipedia.org/wiki/Starvation_(computer_science))，即某个线程持续处于饥饿状态无法获取执行所需的资源。

上一节中提到的，每个线程发现无法进入临界区后，等待随机的时间再进入下一次循环，也可以解决Starvation的问题。

下面我们将要看到一个不使用随机等待也能解决以上所有问题的算法。

Peterson’s Algorithm#

这个算法由Gary L. Peterson在1981年时提出(https://en.wikipedia.org/wiki/Peterson%27s_algorithm)。

import time
from concurrent.futures import ThreadPoolExecutor

run_times = 3
count = 0
flags = [False, False]
turn = -1


def mutual_exclusion(self_id):
    global count, flags, turn
    for _ in range(0, run_times):
        turn = 1 - self_id
        flags[self_id] = True
        while True:
            if flags[1 - self_id] and turn == 1 - self_id:
                continue
            else:
                break

        # critical section begin
        tmp = count + 1
        time.sleep(0.01)
        count = tmp
        print(f"thread {self_id} {tmp}")
        # critical section end

        flags[self_id] = False


if __name__ == "__main__":
    with ThreadPoolExecutor() as executor:
        futures = executor.map(mutual_exclusion, [0, 1])
        executor.shutdown(wait=True)
        print(f"expect count: {run_times * 2}, final count is: {count}")

运行上面的代码，从输出中可以看到0号和1号线程交替执行。

将continue语句改为time.sleep(0.01)后可以看到，算法依然可以稳定执行，没有任何问题。

这个神奇的算法满足临界区问题的三个标准：

  1. 互斥访问（即没有两个线程可以同时进入临界区）
  2. 空闲让进（即不死锁，包括livelock）
  3. 有限等待（即不饿死，Starvation Free）

这三个标准最早由迪杰斯特拉（Edsger W. Dijkstra）在1965年提出，他同时也提出了解决互斥问题的算法。

他的算法叫做：Dekker’s algorithm(https://en.wikipedia.org/wiki/Dekker%27s_algorithm)，是已知的最早正确解决互斥问题的算法。

这个故事告诉我们#

通过本文的内容，可以了解到编写正确的并发算法的复杂性，而这一类问题又具有一定的欺骗性，编程人员起初会觉得问题很简单，用自己编写的简单逻辑就能够解决，甚至简单的测试也没有发现问题。

当代码在实际的高并发环境中运行时，才会发现各种问题。

在分布式环境中的算法更是如此，在《SRE Google运维解密》这本书中写到：

很多分布式系统问题最后都归结为分布式共识问题的不同变种，包括领头人选举，小组成员信息，各种分布式锁和租约机制，可靠的分布式队列和消息传递，以及任何一种需要在多个进程中共同维护一致的关键状态的机制。 所有这些问题都应该仅仅采用经过正式的正确性证明的分布式共识算法来解决，还要确保这个算法的实现经过了大量测试。 任何一种临时解决这种问题的方法（例如心跳，以及谣言协议）在实践中都会遇到可靠性问题。

事实上科学家已经证明，在异步分布式系统中，没有任何算法可以确定的解决分布式共识问题。https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf

It is impossible to have a deterministic protocol that solves consensus in a message-passing asynchronous system in which at most one process may fail by crashing.

Formal Methods#

https://en.wikipedia.org/wiki/Formal_methods

上面《SRE Google运维解密》中提到“采用经过正式正确性证明的分布式共识算法”，形式化方法(Formal Methods)就是用严格的数学技术来设计软件或硬件。

将形式化方法用于软件和硬件设计，是期望能够像其它工程学科一样，使用适当的数学分析以提高设计的可靠性和强健性。

本文的例子就来自于PlusCal/TLA+的教程：https://lamport.azurewebsites.net/tla/tutorial/contents.html

TLA+是由Leslie Lamport发明的一种形式化语言，PlusCal是在TLA+基础上设计的一种更接近于现代编程语言的语言。

使用Formal Methods进行算法的设计和验证成本是比较高的，因此通常只适用于对正确性要求很高的场景。

对于并发/分布式这些比较难正确实现的算法，采用形式化方法来设计和验证可以更有效的保证算法的正确性。

Linux内核的锁#

Python线程库提供的Lock是使用的操作系统提供的锁机制。

“Linux的futex是否存在livelock的情况？”，下面是ChatGPT的回答：

是的，Linux的futex机制可能会出现livelock的情况。

在futex机制中，当多个进程同时竞争同一个锁时，可能会出现一种情况，称为“饥饿死锁”（starvation deadlock）。在这种情况下，某些进程始终无法获得锁，因为始终有其他进程在竞争锁。

为了解决这个问题，futex机制引入了一种称为“优先级反转”（priority inversion）的技术。具体来说，当某个低优先级的进程持有锁时，如果高优先级的进程需要竞争这个锁，那么它可以通过升高自己的优先级来避免饥饿死锁。这样，低优先级的进程就会让出锁，让高优先级的进程先执行，从而避免了饥饿死锁的情况。

然而，优先级反转技术可能会引发另一种问题，称为“优先级翻转”（priority inversion）。在这种情况下，一个中优先级的进程持有锁，并且需要与一个高优先级的进程进行通信，但是由于低优先级的进程不断地竞争锁，中优先级的进程一直无法释放锁，导致高优先级的进程无法得到执行。这种情况就是livelock，即多个进程都在等待对方释放锁，但是始终没有进展。

为了避免优先级翻转和livelock的问题，futex机制还引入了其他一些技术，如“优先级继承”（priority inheritance）和“优先级传递”（priority ceiling）。这些技术可以在一定程度上减少优先级翻转和livelock的发生，提高系统的稳定性和可靠性。

comments powered by Disqus