无锁编程介绍

无锁编程

无锁编程是一种并发编程技术，旨在避免使用传统锁（如互斥锁、信号量等）来实现多线程或多进程对共享资源的安全访问。它通过原子操作和内存屏障等技术，让多个线程可以同时访问共享资源而不会产生数据竞争和死锁问题，从而提高系统的并发性能和响应速度。

无锁编程的优点

高性能：避免了锁的开销，减少了线程上下文切换，提升了系统的并发处理能力。
无死锁：由于不使用锁，也就不存在死锁问题。
响应性好：某个线程的延迟不会影响其他线程的执行。

无锁编程的缺点

实现复杂：需要深入理解原子操作和内存模型，编写正确的无锁代码难度较大。
调试困难：无锁代码中的并发问题很难复现和调试。

无锁编程的关键技术

原子操作：原子操作是不可被中断的操作，在多线程环境下能保证操作的完整性。C 语言中可以使用 <stdatomic.h> 头文件提供的原子类型和函数。
内存屏障：用于控制内存访问的顺序，确保多线程之间的内存可见性。

示例代码

下面是一个简单的无锁计数器示例：

#include <stdio.h>
#include <threads.h>
#include <stdatomic.h>// 定义一个原子整数作为计数器
atomic_int counter = ATOMIC_VAR_INIT(0);// 线程函数，对计数器进行递增操作
int increment(void *arg) {for (int i = 0; i < 100000; ++i) {// 原子递增操作atomic_fetch_add(&counter, 1);}return 0;
}int main() {thrd_t threads[4];// 创建 4 个线程for (int i = 0; i < 4; ++i) {thrd_create(&threads[i], increment, NULL);}// 等待所有线程结束for (int i = 0; i < 4; ++i) {thrd_join(threads[i], NULL);}// 输出最终的计数器值printf("Final counter value: %d\n", atomic_load(&counter));return 0;
}

代码解释
原子类型：使用 atomic_int 定义一个原子整数 counter，并初始化为 0。
原子操作：atomic_fetch_add 函数用于原子地将计数器的值加 1。
多线程操作：创建 4 个线程，每个线程对计数器进行 100000 次递增操作。
结果输出：等待所有线程结束后，使用 atomic_load 函数获取计数器的最终值并输出。
这个示例展示了如何使用原子操作实现一个简单的无锁计数器，多个线程可以安全地对计数器进行递增操作而不会产生数据竞争。

原子操作

原子操作是多线程编程中的关键概念，指在执行过程中不可被中断的操作，即在操作完成前不会被其他线程或进程干扰。原子操作在并发编程里极为重要，能保证共享数据在多线程环境下的一致性和完整性，避免数据竞争问题。

C 语言中的原子操作
C11 标准引入了 <stdatomic.h> 头文件，提供了丰富的原子类型和函数，下面详细介绍其使用方法。

1. 原子类型

<stdatomic.h> 定义了多种原子类型，常见的有 atomic_bool、atomic_char、atomic_int 等，这些类型能像普通类型一样使用，不过对它们的操作是原子的。

#include <stdatomic.h>// 定义原子整数并初始化为 0
atomic_int atomic_counter = ATOMIC_VAR_INIT(0);

2. 原子初始化

可以使用 ATOMIC_VAR_INIT 宏在定义时初始化原子变量，也能用 atomic_init 函数在运行时初始化。

#include <stdatomic.h>atomic_int counter;int main() {// 运行时初始化原子变量atomic_init(&counter, 0);return 0;
}

3. 原子读写操作

读操作：atomic_load 函数用于原子地读取原子变量的值。
写操作：atomic_store 函数用于原子地将值写入原子变量。

#include <stdatomic.h>
#include <stdio.h>atomic_int atomic_num = ATOMIC_VAR_INIT(10);int main() {// 原子读取int value = atomic_load(&atomic_num);printf("Loaded value: %d\n", value);// 原子写入atomic_store(&atomic_num, 20);printf("After store, loaded value: %d\n", atomic_load(&atomic_num));return 0;
}

4. 原子修改操作

常见的原子修改操作有 atomic_fetch_add、atomic_fetch_sub 等，这些操作会原子地修改原子变量的值并返回旧值。

#include <stdatomic.h>
#include <stdio.h>atomic_int atomic_counter = ATOMIC_VAR_INIT(0);int main() {// 原子加 5 并返回旧值int old_value = atomic_fetch_add(&atomic_counter, 5);printf("Old value: %d, New value: %d\n", old_value, atomic_load(&atomic_counter));// 原子减 3 并返回旧值old_value = atomic_fetch_sub(&atomic_counter, 3);printf("Old value: %d, New value: %d\n", old_value, atomic_load(&atomic_counter));return 0;
}

5. 比较并交换（CAS）操作

atomic_compare_exchange_weak 和 atomic_compare_exchange_strong 是重要的原子操作，用于原子地比较原子变量的值和期望值，若相等则替换为新值。

#include <stdatomic.h>
#include <stdio.h>atomic_int atomic_num = ATOMIC_VAR_INIT(10);int main() {int expected = 10;int new_value = 20;// 比较并交换if (atomic_compare_exchange_strong(&atomic_num, &expected, new_value)) {printf("Value was successfully updated to %d\n", atomic_load(&atomic_num));} else {printf("Update failed. Current value: %d\n", atomic_load(&atomic_num));}return 0;
}

总结

原子操作借助硬件支持，在多线程环境下提供了高效且安全的共享数据访问方式。C 语言的 <stdatomic.h> 头文件提供了丰富的原子类型和函数，能帮助开发者实现无锁编程，避免数据竞争和死锁问题。不过，使用原子操作时要深入理解其语义和内存顺序，防止出现并发问题。

内存模型

在 C 语言中，内存模型是一个抽象概念，用于定义多线程程序中内存访问的规则和行为，确保不同线程对共享内存的操作能正确同步，保证程序的一致性和可预测性。下面详细介绍 C 语言的内存模型相关内容。

1. 内存顺序枚举

C11 标准的 <stdatomic.h> 引入了内存顺序枚举，用于控制原子操作的内存同步行为，主要有以下几种：

memory_order_relaxed：最宽松的内存顺序，只保证操作的原子性，不保证操作的顺序，不同线程看到的操作顺序可能不同。
memory_order_consume：保证后续依赖该原子操作结果的内存访问不会被重排到该操作之前，但对不依赖该结果的操作无顺序保证。
memory_order_acquire：保证在该原子操作之后的所有内存访问不会被重排到该操作之前，常用于读操作。
memory_order_release：保证在该原子操作之前的所有内存访问不会被重排到该操作之后，常用于写操作。
memory_order_acq_rel：同时具备 memory_order_acquire 和 memory_order_release 的特性，用于读 - 修改 - 写操作。
memory_order_seq_cst：最严格的内存顺序，保证所有线程看到的所有 memory_order_seq_cst 操作有一个全局一致的顺序。

2. 不同内存顺序示例

memory_order_relaxed

#include <stdatomic.h>
#include <threads.h>
#include <stdio.h>atomic_int x = ATOMIC_VAR_INIT(0);
atomic_int y = ATOMIC_VAR_INIT(0);int thread1(void *arg) {x.store(1, memory_order_relaxed);int r1 = y.load(memory_order_relaxed);printf("Thread 1: r1 = %d\n", r1);return 0;
}int thread2(void *arg) {y.store(1, memory_order_relaxed);int r2 = x.load(memory_order_relaxed);printf("Thread 2: r2 = %d\n", r2);return 0;
}int main() {thrd_t t1, t2;thrd_create(&t1, thread1, NULL);thrd_create(&t2, thread2, NULL);thrd_join(t1, NULL);thrd_join(t2, NULL);return 0;
}

在这个示例中，memory_order_relaxed 只保证原子性，x 和 y 的读写操作可能被重排，不同线程看到的操作顺序可能不同。

memory_order_release 和 memory_order_acquire

#include <stdatomic.h>
#include <threads.h>
#include <stdio.h>atomic_int flag = ATOMIC_VAR_INIT(0);
int data = 0;int writer(void *arg) {data = 42; // 写数据atomic_store_explicit(&flag, 1, memory_order_release); // 释放操作return 0;
}int reader(void *arg) {while (!atomic_load_explicit(&flag, memory_order_acquire)); // 获得操作printf("Data: %d\n", data);return 0;
}int main() {thrd_t t1, t2;thrd_create(&t1, writer, NULL);thrd_create(&t2, reader, NULL);thrd_join(t1, NULL);thrd_join(t2, NULL);return 0;
}

memory_order_release 保证在它之前的 data = 42 操作不会被重排到它之后，memory_order_acquire 保证在它之后的 printf 操作不会被重排到它之前，确保 reader 线程能看到 writer 线程写入的数据。

memory_order_seq_cst

#include <stdatomic.h>
#include <threads.h>
#include <stdio.h>atomic_int a = ATOMIC_VAR_INIT(0);
atomic_int b = ATOMIC_VAR_INIT(0);int t1(void *arg) {a.store(1, memory_order_seq_cst);int r1 = b.load(memory_order_seq_cst);printf("Thread 1: r1 = %d\n", r1);return 0;
}int t2(void *arg) {b.store(1, memory_order_seq_cst);int r2 = a.load(memory_order_seq_cst);printf("Thread 2: r2 = %d\n", r2);return 0;
}int main() {thrd_t th1, th2;thrd_create(&th1, t1, NULL);thrd_create(&th2, t2, NULL);thrd_join(th1, NULL);thrd_join(th2, NULL);return 0;
}

memory_order_seq_cst 保证所有线程看到的操作有一个全局一致的顺序，虽然性能可能不如宽松的内存顺序，但能简化编程逻辑。

3. 内存模型的作用

保证数据一致性：通过规定内存操作的顺序，确保多线程对共享数据的读写操作能正确同步，避免数据竞争。
优化性能：允许开发者根据实际需求选择合适的内存顺序，在保证正确性的前提下，减少不必要的内存屏障，提高程序性能。

4. 注意事项

内存模型比较复杂，使用时要根据具体场景选择合适的内存顺序。
宽松的内存顺序虽然能提高性能，但会增加编程和调试的难度。
测试并发程序时，不同的硬件平台和编译器可能对内存模型有不同的实现，需要进行充分测试。

内存顺序

在多线程编程里，内存顺序是 C 语言内存模型的核心概念，它规定了原子操作在不同线程间的内存可见性和操作顺序，直接影响程序的正确性与性能。下面详细介绍 C 语言中不同的内存顺序及其使用场景。

1. memory_order_relaxed

memory_order_relaxed 是最宽松的内存顺序，仅保证原子操作本身的原子性，不保证操作的顺序，不同线程看到的操作顺序可能不同。常用于对顺序要求不高，仅需保证原子性的场景。

#include <stdatomic.h>
#include <threads.h>
#include <stdio.h>atomic_int x = ATOMIC_VAR_INIT(0);
atomic_int y = ATOMIC_VAR_INIT(0);int thread1(void *arg) {// 原子写操作，使用 relaxed 内存顺序atomic_store_explicit(&x, 1, memory_order_relaxed); // 原子读操作，使用 relaxed 内存顺序int r1 = atomic_load_explicit(&y, memory_order_relaxed); printf("Thread 1: r1 = %d\n", r1);return 0;
}int thread2(void *arg) {atomic_store_explicit(&y, 1, memory_order_relaxed);int r2 = atomic_load_explicit(&x, memory_order_relaxed);printf("Thread 2: r2 = %d\n", r2);return 0;
}int main() {thrd_t t1, t2;thrd_create(&t1, thread1, NULL);thrd_create(&t2, thread2, NULL);thrd_join(t1, NULL);thrd_join(t2, NULL);return 0;
}

在这个例子中，x 和 y 的读写操作可能被重排，r1 和 r2 都可能为 0。

2. memory_order_consume

memory_order_consume 保证后续依赖该原子操作结果的内存访问不会被重排到该操作之前，但对不依赖该结果的操作无顺序保证。不过在实际使用中，由于其语义复杂且硬件支持有限，常被 memory_order_acquire 替代。

#include <stdatomic.h>
#include <threads.h>
#include <stdio.h>atomic_int *p = ATOMIC_VAR_INIT(NULL);
int data = 0;int writer(void *arg) {data = 42;atomic_store_explicit(&p, &data, memory_order_release);return 0;
}int reader(void *arg) {atomic_int *local_p;while (!(local_p = atomic_load_explicit(&p, memory_order_consume)));printf("Data: %d\n", *local_p);return 0;
}int main() {thrd_t t1, t2;thrd_create(&t1, writer, NULL);thrd_create(&t2, reader, NULL);thrd_join(t1, NULL);thrd_join(t2, NULL);return 0;
}

reader 线程能保证在获取 p 指针后，访问 *local_p 时看到 writer 线程写入的 data 值。

3. memory_order_acquire

memory_order_acquire 保证在该原子操作之后的所有内存访问不会被重排到该操作之前，常用于读操作。通常和 memory_order_release 配合使用，确保数据的可见性。

4. memory_order_release

memory_order_release 保证在该原子操作之前的所有内存访问不会被重排到该操作之后，常用于写操作。

#include <stdatomic.h>
#include <threads.h>
#include <stdio.h>atomic_int flag = ATOMIC_VAR_INIT(0);
int data = 0;int writer(void *arg) {data = 42; // 写数据// 释放操作，保证前面的写操作不会被重排到之后atomic_store_explicit(&flag, 1, memory_order_release); return 0;
}int reader(void *arg) {int local_flag;// 获得操作，保证后面的读操作不会被重排到之前while (!(local_flag = atomic_load_explicit(&flag, memory_order_acquire))); printf("Data: %d\n", data);return 0;
}int main() {thrd_t t1, t2;thrd_create(&t1, writer, NULL);thrd_create(&t2, reader, NULL);thrd_join(t1, NULL);thrd_join(t2, NULL);return 0;
}

reader 线程在看到 flag 为 1 时，能确保看到 writer 线程写入的 data 值。

5. memory_order_acq_rel

memory_order_acq_rel 同时具备 memory_order_acquire 和 memory_order_release 的特性，用于读 - 修改 - 写操作。

#include <stdatomic.h>
#include <threads.h>
#include <stdio.h>atomic_int counter = ATOMIC_VAR_INIT(0);int incrementer(void *arg) {// 原子递增操作，使用 acq_rel 内存顺序atomic_fetch_add_explicit(&counter, 1, memory_order_acq_rel); return 0;
}int main() {thrd_t threads[4];for (int i = 0; i < 4; ++i) {thrd_create(&threads[i], incrementer, NULL);}for (int i = 0; i < 4; ++i) {thrd_join(threads[i], NULL);}printf("Final counter value: %d\n", atomic_load_explicit(&counter, memory_order_seq_cst));return 0;
}

在这个例子中，atomic_fetch_add_explicit 使用 memory_order_acq_rel 确保递增操作的原子性，同时保证操作前后的内存顺序。

6. memory_order_seq_cst

memory_order_seq_cst 是最严格的内存顺序，保证所有线程看到的所有 memory_order_seq_cst 操作有一个全局一致的顺序。虽然性能可能不如宽松的内存顺序，但能简化编程逻辑。

#include <stdatomic.h>
#include <threads.h>
#include <stdio.h>atomic_int a = ATOMIC_VAR_INIT(0);
atomic_int b = ATOMIC_VAR_INIT(0);int t1(void *arg) {atomic_store_explicit(&a, 1, memory_order_seq_cst);int r1 = atomic_load_explicit(&b, memory_order_seq_cst);printf("Thread 1: r1 = %d\n", r1);return 0;
}int t2(void *arg) {atomic_store_explicit(&b, 1, memory_order_seq_cst);int r2 = atomic_load_explicit(&a, memory_order_seq_cst);printf("Thread 2: r2 = %d\n", r2);return 0;
}int main() {thrd_t th1, th2;thrd_create(&th1, t1, NULL);thrd_create(&th2, t2, NULL);thrd_join(th1, NULL);thrd_join(th2, NULL);return 0;
}

所有 memory_order_seq_cst 操作在全局有一致的顺序，能避免一些复杂的并发问题。

总结

性能与复杂度平衡：宽松的内存顺序（如 memory_order_relaxed）性能较高，但编程和调试复杂度大；严格的内存顺序（如 memory_order_seq_cst）能简化逻辑，但性能可能受影响。
配对使用：memory_order_release 常和 memory_order_acquire 配对，确保线程间的数据可见性。
选择原则：根据实际需求选择合适的内存顺序，在保证程序正确性的前提下追求高性能。

原子操作硬件支持原理

原子操作是并发编程中保证操作不可被中断的关键机制，现代硬件通过多种技术来支持原子操作，下面从不同架构的硬件层面介绍原子操作的支持原理。

总线锁定

在早期的多处理器系统中，总线锁定是实现原子操作的基础方法。当一个处理器需要执行原子操作时，它会向总线发送一个锁定信号，其他处理器收到该信号后，会暂停对共享内存的访问，直到锁定信号撤销。这样就能保证在锁定期间，该处理器对内存的操作是原子的。

例如，在 x86 架构中，LOCK 前缀指令可以实现总线锁定。以下是一个简单的汇编示例：

; 假设 eax 寄存器的值加 1 是一个原子操作
LOCK INC eax

在执行 LOCK INC eax 指令时，处理器会锁定总线，确保 eax 寄存器的值加 1 的操作不会被其他处理器干扰。不过，总线锁定会阻止其他处理器访问内存，开销较大，现代处理器已对其进行了优化。

缓存锁定

随着缓存技术的发展，现代处理器大多采用缓存锁定来实现原子操作，以减少总线锁定带来的性能开销。缓存锁定利用了处理器的缓存一致性协议（如 MESI 协议），当一个处理器要执行原子操作时，它会先检查操作的数据是否在自己的缓存中。如果在，且处于独占（Exclusive）或修改（Modified）状态，处理器可以直接在缓存中执行原子操作，而无需锁定总线。

MESI 协议简介

MESI 协议是一种常用的缓存一致性协议，它将缓存行的状态分为以下四种：

Modified（M）：缓存行已被修改，与主存中的数据不一致，且该缓存行只存在于当前处理器的缓存中。
Exclusive（E）：缓存行与主存中的数据一致，且只存在于当前处理器的缓存中。
Shared（S）：缓存行与主存中的数据一致，且可能存在于多个处理器的缓存中。
Invalid（I）：缓存行无效，需要从主存或其他处理器的缓存中重新获取数据。

基于 MESI 协议的原子操作示例
假设两个处理器 P1 和 P2 都有对共享变量 x 的缓存。当 P1 要对 x 执行原子加 1 操作时：

P1 检查自己缓存中 x 的状态，如果是 E 或 M 状态，直接在缓存中执行加 1 操作，并将缓存行状态保持为 M。
如果 x 的状态是 S 状态，P1 会向其他处理器发送消息，要求它们将自己缓存中 x 的缓存行状态置为 I，然后 P1 将自己缓存中 x 的状态更新为 E，再执行加 1 操作。
如果 x 的状态是 I 状态，P1 会从主存或其他处理器的缓存中获取 x 的最新值，更新自己的缓存行状态，然后执行加 1 操作。

特殊指令

不同的硬件架构提供了专门用于原子操作的指令，以高效实现原子操作。

x86 架构

x86 架构提供了一系列原子操作指令，如 XADD（交换并相加）、CMPXCHG（比较并交换）等。

; 比较并交换指令示例
; eax 是期望值，ebx 是新值，ecx 是指向共享变量的指针
CMPXCHG [ecx], ebx

CMPXCHG 指令会比较 [ecx] 中的值和 eax 中的期望值，如果相等，则将 ebx 中的新值写入 [ecx]，并将 ZF 标志位置 1；否则，将 [ecx] 中的实际值存入 eax，并将 ZF 标志位置 0。

ARM 架构

ARM 架构通过 LDREX（加载独占）和 STREX（存储独占）指令实现原子操作。

; 原子加 1 操作示例
; r0 是指向共享变量的指针
LDREX r1, [r0]   ; 加载独占
ADD r1, r1, #1   ; 加 1
STREX r2, r1, [r0] ; 存储独占
CMP r2, #0       ; 检查存储是否成功
BNE retry        ; 失败则重试

LDREX 指令会将内存中的值加载到寄存器，并标记该内存地址为独占访问；STREX 指令会尝试将寄存器中的值存储到标记的内存地址，如果该内存地址在 LDREX 之后没有被其他处理器修改，则存储成功，返回 0；否则，存储失败，返回 1。

总结

现代硬件通过总线锁定、缓存锁定和特殊指令等多种技术支持原子操作。总线锁定能确保操作的原子性，但性能开销大；缓存锁定利用缓存一致性协议，减少了总线锁定的使用，提高了性能；特殊指令则为原子操作提供了高效的实现方式，不同架构的硬件有各自的原子操作指令集。