什么是并发 Part 1：硬件支持与机制

本文中将会出现使用 C 语言的代码样例用于说明概念。

本文中会出现 ARM64 汇编代码。

如果对文中使用的语法有不理解的地方，可以在Aarch64 汇编速览一文中查找对应的解释。

并发操作用在哪了？

并行与并发，都是提升计算机硬件使用效率的方式。二者在名称上接近，但是描述的行为却有较大的不同。

并行，指的是多个运算过程可以同时发生；并发，指的是不同任务的起止时间区间是否能有重叠，也就是前一个任务还没完全结束时能否开始下一任务的处理。

显然，并行执行是一种实现并发的方式。

从实践上来说，并行通常是当系统上有相对充足的资源时，如何把一个任务拆分成更多的部分，以充分利用硬件来缩短总执行时间；而并发，通常是多种计算资源中的一种因不够充足而成为瓶颈时，通过分配其它资源来使得系统整体的利用率更高。

比如单个 TCP 连接下载的速率远不能占满硬盘带宽时；比如文件读写操作效率远不如 CPU 计算的效率时；比如 CPU 处理场景信息的速率远远达不到以 60 FPS 在屏幕上呈现内容时。

当计算资源中有一方的处理速度落后时，就会出现其它资源等待落后方进行响应的情景。在出现这样的情况时，即使落后资源还没有完成当前任务，也能动用空闲的资源开始下一个任务，这就是并发。

数据同步

只要是进行任务的并发执行，程序之间不同部分的状态同步就一定会成为一个需要解决的问题。

现代大大小小的处理器中，有多核出现的硬件数量不在少数。每一个核都有自己的寄存器、缓存行——这部分硬件是其它核不可访问的。一旦程序的不同部分开始在不同的核上运行，这些属于单个核的私有数据空间就能引发问题。

我们来看一个例子。假设有一个下载器应用，它现在正把一个文件分割成两个数据块同时进行下载。在面向用户的这一侧，应用决定不展示下载方式的细节，只展示使用当前已下载数据的总量计算得到的进度百分比。

那么在两个后台进行中的数据块下载任务，就都需要对记录已下载量的变量进行更新。

void download_block(struct task_t *task, struct progress_bar *bar) {
    while (!task_is_finished(task)) {
        // 下载一部分数据，并返回本次操作中下载的数据字节数
        int count = task_get_data_piece(task);

        if (count > 0) {
            // 增加进度条的计数
            progress_bar_add(bar, count);
        } else {
            // ...
        }
    }
}

void progress_bar_add(struct progress_bar *bar, int amount) {
    bar->progress += amount;
}

如果就用这样的代码来进行两个任务下载进度的统合，最终呈现给用户的进度条是有问题的。尽管在 C 语言中，修改进度条 progress 字段的函数只花了一条语句执行，但是其汇编指令则不止一句：

progress_bar_add:
    // ...
    ldr x2, [x0, #4] // 步骤 1，大致对应 `->`，将字段旧值加载到寄存器
    add x2, x2, x1   // 步骤 2，对应 `+`，增加进度值
    str x2, [x0, #4] // 步骤 3，对应 `=`，将新进度存回字段
    // ...

不同核之间的数据共享，是通过对内存地址的访问实现的，但是处理器的核计算时几乎都在使用寄存器这样的私有数据空间。

这里说“私有”，指的是在核心 1 上有一个 x2 寄存器，在核心上也有一个名为 x2 的寄存器。两个寄存器是完全不同的硬件，每个核心只能各自访问属于自己的 x2。

我们就把两个数据块下载任务分别称为 A 与 B 吧。假设 A 接收到了新的数据，并且已经进行到了进度条更新操作的步骤 1，这时系统的线程调度由于 A 已经占用 CPU 达到了限额，中断了 A 的运行。

A 任务就保持着 x2 寄存器中留有旧进度值的状态，进入到了休眠。

这时 B 也收到了新数据，并开始了进度值的更新。此时内存中的数据，对于 B 来说是新数据，但是对于 A 来说已经是过期数据了。B 完成进度更新后进入了下一组数据的下载等待。

A 恢复执行后，从步骤 2 继续进行进度的更新，此时 A 所在的核心上，x2 里的数据对于 B 来说已经是过期数据了——因为这个值没有反映 B 进行更新的结果。A 就这样把步骤 3 执行完后，B 所进行过的进度更新就被吞掉了。

这就是所谓的数据竞争。

为了在不同的核心之间共享数据，我们需要一种能够让一个核心告知其它核心避开与自己的读写操作重叠的机制。

数据锁

最简单的方式，是使用一个内存中的标记变量来标识某个特定的读写操作是否正在进行。每一个核心在开始进行目标读写操作前，先检查“操作中”标记是否已经激活，如果标记处于激活状态就等待至标记取消激活。

这个标记就是数据锁。而处于锁定、解锁两个操作之间的代码段称为是关键区域。

void lock(int *lock_flag);

void progress_bar_add(struct progress_bar *bar, int amount, int *lock_flag) {
    // 开始执行操作前先激活数据锁。
    lock(lock_flag);
    bar->progress += amount;
    unlock(lock_flag);
}

void lock(int *lock_flag) {
    // 在成功激活之前都不结束该函数
    // 如果现在数据锁正好处于锁定状态，则 try_lock 失败。
    while (!try_lock(lock)) {
        ;
    }
}

但是这其中有一个问题。对锁标记的值修改，本身也是可以发生在不同核上的多指令操作。修改锁标记的过程中也是有可能发生数据竞争的。

接下来介绍 lock 函数应该如何进行实现。

数据锁的纯软件实现

接下来介绍的方法叫 Lamport 算法，该算法是使用纯软件形式实现的确保不会有多个核同时执行关键区域代码的手段。

这一方法使用面包店作为类比：所有的客人来到面包店时都要领取一个排队号，店员按号码每一次叫一个人进店里购物。当客人结账出店时，会把号码还给店员，店员便叫下一个号码进店消费。出店后，顾客想要再进行购物则要重新取号。

算法首先需要两个数组：一个用于记录各个任务的队列编号，另一个是记录哪些任务正在取号的标记数组。

#define NUM_THREAD 16

bool entering[NUM_THREAD] = {0};
int number[NUM_THREAD] = {0};

每一个并发任务各自持有自己的编号作为识别码。这个识别码将会与队列编号共同决定任务的优先级。

新的任务需要进行数据访问时，会把编号数组中最大数加上 1 作为自己的编号存入数组中，编号越小的任务处理优先级越高。这个过程涉及到分成数步的读与写，是很有可能在中途被打断的。只要任务 A 在任务 B 检查最大数的过程中修改了自己的排队编号，B 任务就很有可能拿到与 A 相同的编号。

  sequenceDiagram
    participant A
    participant 编号数组
    participant B
    participant 操作系统
    A->>编号数组: 离开队列，编号归零
    编号数组->>编号数组: 队列中不再有活跃任务
    B->>编号数组: 寻找最大现有编号
    B->>编号数组: 发现所有任务编号都是 0
    B->>B: 准备将 1 作为自己的编号
    操作系统-->>B: 运行时长达到上限，中断任务执行
    A->>编号数组: 新任务到达，再次取号
    A->>A: 准备将 1 作为自己的编号
    A->>编号数组: 将编号 1 写入编号数组中
    操作系统-->>B: 重新开始执行
    B->>编号数组: 将编号 1 写入编号数组中

该算法允许不同任务持有相同的队列编号，队列编号相同时，任务 ID 较小者优先执行。

想要保证任务 ID 不重复很简单。开始并发之前，在 CPU 上只有单任务在运行的阶段就进行任务 ID 的发放，就不会因为数据竞争出现相同 ID 的任务了。

在领取到队列编号之后，各个任务需要检查编号数组之中是否有优先级高于自己的任务存在。若有，则需要等待其完成执行，再进行后续操作；若没有，则可以立即开始关键数据的读写。

但是在这个过程中还有一个需要注意的问题。如果任务 1 在对队列编号数组进行写入操作之前，被操作系统中断了执行。而任务 2 在 1 被中断的间隙里，不仅取得了和 1 将要使用的队列编号一样的编号，还进入到了筛查是否有优先级高于自己的任务的阶段。

  sequenceDiagram
    participant 操作系统
    participant 任务 1
    participant 任务 2
    participant 编号数组
    participant 关键区域
    任务 1->>编号数组: 准备使用队列编号 1
    操作系统-->>任务 1: 中断执行
    任务 2->>编号数组: 准备使用队列编号 1
    任务 2->>编号数组: 更新编号数组
    任务 2->>任务 2: 自身拥有队列中最小编号
    任务 2->>关键区域: 开始数据读写
    操作系统-->>任务 1: 重新开始执行
    任务 1->>编号数组: 将编号 1 写入编号数组中
    任务 1->>任务 1: 自身是最小队列编号中，任务 ID 最小的
    任务 1->>关键区域: 开始数据读写

这样就有可能有两个任务同时开始关键区域的执行。

entering 标记就是防止出现一个任务在别的任务还在取号时，就抢先开始关键区域的执行的情况。

entering[task_id] = true; // 标记开始取号
// 取号操作
entering[task_id] = false; // 标记取号结束

当一个任务正在进行取号时，其它任务能够通过 entering 中的值知晓取号行为正在发生，进而停止自己的行为。

因为对 entering 修改只涉及到一条写入指令，不会被中途打断，所以对 entering 的修改不需要数据保护。

使用该算法的 lock 与 unlock 函数实现如下。

void lock(int task_id) {
    // 开始取号
    entering[task_id] = true;

    // number[task_id] = 1 + max(number);
    int max = 0;
    for (int i = 0; i < NUM_THREAD; i++) {
        if (number[i] > max) {
            max = number[i];
        }
    }
    number[task_id] = 1 + max;

    // 取号结束
    entering[task_id] = false;

    for (int i = 0; i < NUM_THREAD; i++) {
        while (entering[i]) {
            // 等待线程 i 完成其取号流程
            ;
        }

        int n_i = number[i], n_thread = number[task_id];
        bool is_valid = n_i != 0;
        bool is_higher_priority = n_i < n_thread || ((n_i == n_thread) && (i < task_id));
        while (is_valid && is_higher_priority) {
            // 等待优先级高于自身的线程完成操作
            ;
        }
    }
}

void unlock(int task_id) {
    number[task_id] = 0;
}

硬件辅助实现的数据锁

相信经过上面的讨论读者已经能够感觉到，数据竞争出现的原因，就是数据的读取、修改、写入的过程必须使用多条指令完成，而任务的分步的执行有可能在执行到任何一步时被挂起。

那么只需要在 CPU 的架构中提供可以同时进行数据的读与写的命令不就能解决问题了？

如果锁标记使用一个数字值来实现。比如在其是 1 时，表示锁被激活；在其是 0 时，表示锁处于开放状态。我们的程序需要一条能够在检查当前锁是否开放的同时，对开放的锁进行激活的指令。

本节中，将会使用 ARM64 汇编来进行 lock 函数的编写，但是各部分中新定义的指令都不是实际的 ARM64 指令，只是用于方便进行概念说明而定义的名称。

至于 unlock 函数，因为多个核心中，至多只会有一个核心能够成功调用 lock 函数并进入关键区，unlock 作为关键区域的结尾，执行时是不会发生数据竞争的，直接以常规形式将锁标记修改为 0 即可。

Test-and-Set

将该命令名称记为 TAS，则指令形式为：

TAS R_NEW, address

其中 address 是需要进行修改的内存地址， R_NEW 寄存器提供需要写入到内存地址的新数值。

TAS 指令在将 R_NEW 提供的值写入到 address 的同时，会将 address 处在写入发生之前所储存的数值写入到 R_NEW 中。

使用该方式实现的数据锁如下：

// void lock
// x0 - int *lock_flag
lock:
try_lock_loop:                // int x1 = 1;
    mov x1, #1                // while (x1 != 0) {
    tas x1, [x0]              //     x1 = tas(x1, x0);
    cbnz x1, try_lock_loop    // }

在 lock 函数中，将 1 与内存中的数据锁标记值进行交换，如果当前锁处于激活状态，那么交换到寄存器中的值也是 1，锁的状态完全没有发生变化；如果当前锁处于开放状态，交换到寄存器中的值就是 0，此时锁会变为激活状态，执行指令的核心可通过交换得到的 0 值知道锁被激活，可以进行下一步操作。

但是这种方式有一个缺点，就是核心不论是否能成功进行锁的激活操作，都会进行内存的写入。

在现代的处理器上，核心都会有属于自己的缓存行。这些缓存行中储存的是该核心最近进行过数据访问的内存数据块。当 CPU 要进行内存访问时，会先尝试从缓存中获取数据，只有缓存中没有目标地址的数据时，才会真正向内存进行数据请求。

从缓存中获取数据，是要比从内存中搬运数据快得多的。

而每一次向内存地址上写入数据，就会将所有核心中关于这一地址的缓存条目作废。

当一个核心成功激活数据锁后，其它所有核心都会被阻塞在重复进行 TAS 检查的一步。每进行一次 TAS 写入，所有核心上数据锁所在内存地址对应的缓存就会失效。故而其它核心每次想要检查数据锁状态时，都会被迫进行一次内存的读取操作。

数据锁的状态在这段时间里完全没有发生过改变，这些作为副作用产生的缓存作废完全是性能的浪费。

Compare-and-Swap

将该命令的名称记为 CAS，该指令的形式为：

CAS R_NEW, R_OLD, address

其中 R_OLD 寄存器中的值，是参考值。是当前处理器核心认为内存在 address 处应该储存的值。而 R_NEW 是将要写入到 address 的新值。

该指令会在写入之前检查内存位置上的值是否与 R_OLD 中储存的值相同，如果两值相等就将 R_NEW 的值写入到内存中，并将 R_NEW 的值改成 1；如果两值不等，则不进行内存的修改，将 R_NEW 的值改为 0。

该指令是要求在执行该指令前，进行 address 处的值的读取，并将其保留到 CAS 命令执行时， CAS 命令发现内存中的实际值与作为命令参数的参考值不同时，就认为在读取 address 与 CAS 命令执行之间，发生过数据的修改。

核心接收到 CAS 的数据过期反馈后，应该重新执行读取、修改、写入的步骤。

用在数据锁中，我们可以总是用 0 来作为命令的参考值，因为内存中锁定标记的值只要不是 0，核心就必须等待内存中的数值变回 0，再进行后续的操作。

// void lock
// x0 - int *lock_flag
lock:
try_lock_loop:               // int x1 = 1;
    mov x1, 1                // while (!cas(x1, 0, x0)) {
    cas x1, xzr, [x0]        //     x1 = 1;
    cbz x1, try_lock_loop    // }

Load-Link 与 Store-Conditional

Load-Link/Store-Conditional 通常简写为 LL/SC，是两条共同发挥作用的两条指令。

LL D, address
SC R, address

LL 与 SC 指令的使用方式，与一般的读取、写入内存指令相同。该指令利用核心对内存总线上其它核心的写入操作信号监听，提供指令的原子化服务。

如果在 LL 之后，SC 指令之前发生过对 address 的写入，则不允许 SC 指令执行，此时 SC 指令不仅不会对内存进行写入，还会在寄存器 R 中写入 0；反之，SC 会将 R 中的数值写入到目标地址，并在 R 中写入 1。

使用该方式实现的数据锁如下：

// void lock
// x0 - int *lock_flag
lock:
try_lock:               // while (true) {
    mov x1, 1           //     if (*lock_flag) {  continue;  }
    ll x2, [x0]         //     *lock_flag = 1;
    cbnz x2, try_lock   //     break;
    sc x1, [x0]         //
    cbz x1, try_lock    // }

专门设计两条指令来模拟原子操作是为什么呢？答案是为了 CPU 的指令集并行优化。

CPU 通常将一条指令的执行流程分割成不同的流水线步骤，通过保持流水线上所有的环节都处于活跃状态来提高 CPU 整体的指令执行效率。

比如第一条指令完成了流水线的第一步后，第一步所对应的硬件重新回到空闲状态，就可以分配给第二条指令使用。第一条指令在进行流水线第二步时，第二指令就进行流水线上的第一步。

典型的 CPU 流水线步骤有：读取指令、指令解码并获取寄存器值、执行、内存访问、寄存器返写。

如果一条指令中，同时有内存读取与内存写入两次内存操作的话，流水线上本来的一个内存访问阶段就不足以完成指令的执行了。

但是如果向指令集中添加多个内存操作阶段，受到影响的不仅仅是用于实现数据锁的指令—— CPU 上所有指令的执行步骤中都必须经过多个内存访问步骤，即使它们根本不需要。

如果不希望产生性能损失，就必须对 CPU 进行更加复杂的设计。

然而，如果使用 LL/SC 方案，原子化操作就可以通过符合一般流水线的两条指令完成。

尾声

并发，是在计算资源陷入任务推进必须等待另一资源响应时，将空闲的资源要转到另一任务的推进上的调度方式。

一旦程序的不同部分，开始分头进行各自任务的处理，就必须提供各个部分之间数据与状态交流的方式，或者说同步机制（synchronization）。

对于 CPU 的不同核心来说，核心与核心之间的通用的数据定位方式是内存地址。程序各成分的状态同步，是通过向共享内存地址上更新数据来实现的。

为了避免多个核心同时从自己的私有数据硬件，向内存中写入数据，导致内存中储存的数据变得不准确，需要设计一种保证一个共享内存地址上，决不会同时有两个核心进行写入操作的机制。

针对在核心上发生的读取、修改、写入操作可能在执行中途被打断的问题，本文介绍了两种使用单一指令进行的原子化操作应对，以及一种使用两条指令模拟的原子化操作。

至于 Lamport 算法，虽然不需要硬件提供支持，但是实现起来需要数十条指令的时间，效率很低。Lamport 算法在当下还有存在的意义吗？

有的，并不是所有的处理器都提供了原子化操作指令，在像硬盘、洗衣机这样的硬件里，主控未必使用的是设计有原子化操作的复杂 CPU；又或是分布式系统，由多个需要主控机进行并发协调的子机组成，并非单一硬件，但也需要数据锁保护共享数据。在这些时候，就可以使用 Lamport 算法及其推广来应对。

希望读完本文后，读者能对互斥锁的实现方式有一定的理解。

参考

Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau. Operating Systems: Three Easy Pieces. Arpaci-Dusseau Books, Inc. 2014
作者不明. "Lamport's bakery algorithm", https://en.wikipedia.org/wiki/Lamport's_bakery_algorithm.
作者不明. "Compare-and-swap", https://en.wikipedia.org/wiki/Compare-and-swap.
作者不明. "Test-and-set", https://en.wikipedia.org/wiki/Test-and-set.
作者不明. "Load-link/store-conditional", https://en.wikipedia.org/wiki/Load-link/store-conditional.

目录