1. 引言
在多线程高并发领域,传统的互斥锁(mutex)虽然简单易用,但也会带来线程阻塞、上下文切换开销、死锁等问题。无锁编程(Lock-Free Programming)试图通过原子操作和巧妙的算法设计,在保证线程安全的前提下提高并发性能和系统响应速度。
当然,无锁编程也并非万能——设计、调试与维护都较为复杂,并且容易遇到 ABA 问题、伪失败(spurious failure)等挑战。
2. 基本概念
- 无锁保证:即使多个线程并发操作共享数据结构,也不会因为锁竞争而产生阻塞。它通常使用原子指令(atomic instruction)来确保操作的正确性。
- 原子操作:在无锁编程中,最常用的原子操作包括比较并交换(Compare-And-Swap,CAS)和原子加载/存储。比如,在 C11 标准中,通过
提供了丰富的原子类型和操作函数。 - 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 标准的
C11 引入了标准的原子类型与原子操作,使得无锁编程的写法更加规范。例如:
- 定义原子变量:
- #include
_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
#include
#include
#include
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)的主要思路是:
- 分配一个新节点,并将其 next 指向当前的栈顶;
- 利用 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:
- 读取当前栈顶,如果为空则返回失败;
- 尝试将栈顶更新为头节点的下一个节点,更新成功后返回节点数据并释放该节点。
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
#include
#include
#include
// 链表节点
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 语言无锁编程提供有效思路,也欢迎你继续探索其他无锁数据结构如无锁队列、无锁链表等应用场景,进而构建高性能的并发应用。