1. 引言

在多线程高并发领域，传统的互斥锁（mutex）虽然简单易用，但也会带来线程阻塞、上下文切换开销、死锁等问题。无锁编程（Lock-Free Programming）试图通过原子操作和巧妙的算法设计，在保证线程安全的前提下提高并发性能和系统响应速度。

当然，无锁编程也并非万能——设计、调试与维护都较为复杂，并且容易遇到 ABA 问题、伪失败（spurious failure）等挑战。

2. 基本概念

• 无锁保证：即使多个线程并发操作共享数据结构，也不会因为锁竞争而产生阻塞。它通常使用原子指令（atomic instruction）来确保操作的正确性。
• 原子操作：在无锁编程中，最常用的原子操作包括比较并交换（Compare-And-Swap，CAS）和原子加载/存储。比如，在 C11 标准中，通过 <stdatomic.h> 提供了丰富的原子类型和操作函数。
• ABA问题：在 CAS 操作中，假设你要将变量从 A 变成 B，但在检查过程中，变量经历了 A→C→A 的转变，CAS 仍然成功。可以使用带标签的指针、版本号等手段来缓解这一问题。
• 内存序（Memory Order）：对于原子操作，除了确保原子性之外，还需要考虑内存屏障和顺序问题。C11 为原子操作提供了多种内存序选项（如 memory_order_relaxed、memory_order_acquire、memory_order_release 等），帮助开发者平衡性能和正确性。

3. C语言中的无锁编程工具

3.1 使用 C11 标准的 <stdatomic.h>

C11 引入了标准的原子类型与原子操作，使得无锁编程的写法更加规范。例如：

• 定义原子变量：
• #include <stdatomic.h>
  
  _Atomic(int) counter = 0;
  atomic_store(&counter, 42);
• 比较并交换操作：
• int expected = 42;
  // 如果 counter 值为 expected，则更新为 43
  atomic_compare_exchange_weak(&counter, &expected, 43);

引用这些原子操作时要注意内存序要求，根据具体场景选择合适的内存序模型。

3.2 编译器内建原子函数

在缺乏 C11 支持的环境下，也可以使用 GCC/Clang 提供的内建函数（例如
__sync_bool_compare_and_swap 或 __atomic_compare_exchange）。不过标准化的 C11 原子操作更推荐用于新项目开发。

4. 无锁数据结构示例 —— 无锁栈

以无锁栈为例，展示如何设计一个简单的无锁数据结构。下面给出使用 C11 原子操作实现的无锁栈示例代码。

4.1 数据结构定义

我们定义一个链表节点和用于表示栈的结构，此处栈的头指针为原子变量。

 #include <stdatomic.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <stdbool.h>
 
 typedef struct node {
     int data;
     struct node *next;
 } node_t;
 
 typedef struct {
     _Atomic(node_t*) head;
 } lockfree_stack_t;

4.2 栈的初始化

将栈的头指针初始化为 NULL：

 void stack_init(lockfree_stack_t *stack) {
     atomic_store(&stack->head, NULL);
 }

4.3 无锁入栈操作

无锁入栈（push）的主要思路是：

0. 分配一个新节点，并将其 next 指向当前的栈顶；
1. 利用 CAS 操作尝试将栈顶更新为新节点，如果在此过程中栈顶发生变化，则重试。

 void stack_push(lockfree_stack_t *stack, int value) {
     node_t *new_node = malloc(sizeof(node_t));
     if (!new_node) {
         perror("malloc");
         exit(EXIT_FAILURE);
     }
     new_node->data = value;
     node_t *old_head;
 
     // 循环尝试更新栈顶
     do {
         old_head = atomic_load(&stack->head);
         new_node->next = old_head;
     } while (!atomic_compare_exchange_weak(&stack->head, &old_head, new_node));
 }

4.4 无锁出栈操作

同理，出栈（pop）操作也利用 CAS：

0. 读取当前栈顶，如果为空则返回失败；
1. 尝试将栈顶更新为头节点的下一个节点，更新成功后返回节点数据并释放该节点。

 bool stack_pop(lockfree_stack_t *stack, int *result) {
     node_t *old_head;
     // 重复尝试直到成功或者发现栈为 NULL
     do {
         old_head = atomic_load(&stack->head);
         if (old_head == NULL)
             return false;  // 栈为空
     } while (!atomic_compare_exchange_weak(&stack->head, &old_head, old_head->next));
     
     *result = old_head->data;
     free(old_head);
     return true;
 }

4.5 完整示例

下面是一份完整示例代码，可编译并运行，演示无锁栈的基本用法：

 #include <stdatomic.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <stdbool.h>
 
 // 链表节点
 typedef struct node {
     int data;
     struct node *next;
 } node_t;
 
 // 无锁栈结构，头指针为原子变量
 typedef struct {
     _Atomic(node_t*) head;
 } lockfree_stack_t;
 
 // 初始化栈
 void stack_init(lockfree_stack_t *stack) {
     atomic_store(&stack->head, NULL);
 }
 
 // 入栈操作
 void stack_push(lockfree_stack_t *stack, int value) {
     node_t *new_node = malloc(sizeof(node_t));
     if (!new_node) {
         perror("malloc");
         exit(EXIT_FAILURE);
     }
     new_node->data = value;
     node_t *old_head;
     do {
         old_head = atomic_load(&stack->head);
         new_node->next = old_head;
     } while (!atomic_compare_exchange_weak(&stack->head, &old_head, new_node));
 }
 
 // 出栈操作
 bool stack_pop(lockfree_stack_t *stack, int *result) {
     node_t *old_head;
     do {
         old_head = atomic_load(&stack->head);
         if (old_head == NULL)
             return false;
     } while (!atomic_compare_exchange_weak(&stack->head, &old_head, old_head->next));
     
     *result = old_head->data;
     free(old_head);
     return true;
 }
 
 // 测试程序
 int main(void) {
     lockfree_stack_t stack;
     stack_init(&stack);
 
     // 入栈测试
     for (int i = 0; i < 10; i++) {
         stack_push(&stack, i);
         printf("Push: %d\n", i);
     }
 
     // 出栈测试
     int value;
     while (stack_pop(&stack, &value)) {
         printf("Pop: %d\n", value);
     }
 
     return 0;
 }

编译时确保支持 C11 标准，例如使用 GCC 编译命令：

 gcc -std=c11 -O2 -pthread lockfree_stack.c -o lockfree_stack

5. 内存序与同步

在无锁编程中，内存序（memory order）的合理设置非常重要。上面示例中使用的函数（例如 atomic_load 和
atomic_compare_exchange_weak）默认使用的内存序可以满足一般需求，但在更复杂的情形下，可能需要显式指定内存序，例如：

• memory_order_relaxed：仅保证原子性，不设定顺序；
• memory_order_acquire / memory_order_release：分别用于加载和存储操作，确保读写的先后顺序；
• memory_order_seq_cst：提供最强内存序顺序。

选择恰当的内存序往往能在不牺牲正确性的前提下提升性能。

6. 常见问题与注意事项

• ABA问题：上述示例中未采用额外措施防止 ABA 问题。在更严格的场景下，可以引入“版本号”或“标签指针”（tagged pointer）来缓解此问题。
• 内存回收：无锁数据结构中，当节点被删除后，其他线程可能仍在访问该节点，必须谨慎设计内存回收机制，如使用 Hazard Pointers 或 Read-Copy-Update (RCU) 技术。
• 算法复杂度：无锁算法通常涉及大量循环重试（CAS 循环），在高竞争环境下可能导致性能下降，设计时需权衡并发性与重试代价。
• 调试困难：无锁程序的并发行为往往难以重现，建议增加日志、使用并发测试工具或专用的无锁调试工具辅助发现问题。

7. 扩展阅读

• C11 原子操作标准
• 关于 ABA 问题的研究与解决方案（版本号、双宽 CAS 等）
• 论文《The Art of Multiprocessor Programming》，深入探讨无锁数据结构

希望能为你探索 C 语言无锁编程提供有效思路，也欢迎你继续探索其他无锁数据结构如无锁队列、无锁链表等应用场景，进而构建高性能的并发应用。