当前位置：首页 > news >正文

高效并发编程：无锁编程

news 2025/6/8 20:49:22

无锁编程是一种并发编程的技术，旨在避免使用传统的锁机制来保护共享数据。相比有锁编程，无锁编程可以提供更高的并发性能和可伸缩性。在无锁编程中，线程或进程通过使用原子操作、CAS（Compare-and-Swap）等技术来实现对共享数据的访问和修改，而不需要依赖互斥锁。

无锁编程常用于高并发场景，如网络服务器、多线程应用程序等。它可以减少线程之间的竞争和阻塞，并且能够充分利用多核处理器的计算能力。然而，由于无锁编程对开发者要求较高，在设计和实现上也更加复杂，需要考虑线程安全性、内存模型等因素。

一、无锁编程概述

1.1什么是无锁编程

无锁编程，即不使用锁的情况下实现多线程之间的变量同步，也就是在没有线程被阻塞的情况下实现变量的同步，所以也叫非阻塞同步（Non-blocking Synchronization），实现非阻塞同步的方案称为“无锁编程算法”。

为什么要非阻塞同步，使用lock实现线程同步有非常多缺点：

产生竞争时，线程被阻塞等待，无法做到线程实时响应
dead lock
live lock
优先级反转
使用不当，造成性能下降

假设在不使用 lock 的情况下，实现变量同步，那就会避免非常多问题。尽管眼下来看，无锁编程并不能替代 lock。

实现级别

非同步阻塞的实现分为三个级别：wait-free/lock-free/obstruction-free

(1)wait-free

最理想的模式，整个操作保证每一个线程在有限步骤下完毕
保证系统级吞吐（system-wide throughput）以及无线程饥饿
截止2011年，没有多少详细的实现。即使实现了，也须要依赖于详细CPU

(2)lock-free

同意个别线程饥饿，但保证系统级吞吐。
确保至少有一个线程可以继续运行。
wait-free的算法必然也是lock-free的。

(3)obstruction-free

在不论什么时间点，一个线程被隔离为一个事务进行运行（其它线程suspended），而且在有限步骤内完毕。在运行过程中，一旦发现数据被改动（採用时间戳、版本），则回滚，也叫做乐观锁，即乐观并发控制(OOC)。

事务的过程是：

读取，并写时间戳
准备写入，版本号校验
检验通过则写入，检验不通过，则回滚

lock-free必然是obstruction-free的。

1.2为什么要无锁?

首先是性能考虑。通信项目一般对性能有极致的追求，这是我们使用无锁的重要原因。当然，无锁算法如果实现的不好，性能可能还不如使用锁，所以我们选择比较擅长的数据结构和算法进行lock-free实现，比如Queue，对于比较复杂的数据结构和算法我们通过lock来控制，比如Map（虽然我们实现了无锁Hash，但是大小是限定的，而Map是大小不限定的），对于性能数据，后续文章会给出无锁和有锁的对比。

次要是避免锁的使用引起的错误和问题：

死锁(dead lock)：两个以上线程互相等待
锁护送(lock convoy)：多个同优先级的线程反复竞争同一个锁，抢占锁失败后强制上下文切换，引起性能下降
优先级反转(priority inversion)：低优先级线程拥有锁时被中优先级的线程抢占，而高优先级的线程因为申请不到锁被阻塞。

1.3如何无锁?

在现代的 CPU 处理器上，很多操作已经被设计为原子的，比如对齐读（Aligned Read）和对齐写（Aligned Write）等。Read-Modify-Write（RMW）操作的设计让执行更复杂的事务操作变成了原子操作，当有多个写入者想对相同的内存进行修改时，保证一次只执行一个操作。

RMW 操作在不同的 CPU 家族中是通过不同的方式来支持的：

x86/64 和 Itanium 架构通过 Compare-And-Swap (CAS) 方式来实现
PowerPC、MIPS 和 ARM 架构通过 Load-Link/Store-Conditional (LL/SC) 方式来实现

在x64下进行实践的，用的是CAS操作，CAS操作是lock-free技术的基础，我们可以用下面的代码来描述：

template <class T>
bool CAS(T* addr, T expected, T value)
{
if (*addr == expected)
{
*addr = value;
return true;
}
return false;
}

在GCC中，CAS操作如下所示：

bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)

这两个函数提供原子的比较和交换，如果*ptr == oldval，就将newval写入*ptr，第一个函数在相等并写入的情况下返回true，第二个函数的内置行为和第一个函数相同，只是它返回操作之前的值。

后面的可扩展参数(...)用来指出哪些变量需要memory barrier，因为目前gcc实现的是full barrier，所以可以略掉这个参数,除过CAS操作，GCC还提供了其他一些原子操作，可以在无锁算法中灵活使用：

type __sync_fetch_and_add (type *ptr, type value, ...)
type __sync_fetch_and_sub (type *ptr, type value, ...)
type __sync_fetch_and_or (type *ptr, type value, ...)
type __sync_fetch_and_and (type *ptr, type value, ...)
type __sync_fetch_and_xor (type *ptr, type value, ...)
type __sync_fetch_and_nand (type *ptr, type value, ...)

type __sync_add_and_fetch (type *ptr, type value, ...)
type __sync_sub_and_fetch (type *ptr, type value, ...)
type __sync_or_and_fetch (type *ptr, type value, ...)
type __sync_and_and_fetch (type *ptr, type value, ...)
type __sync_xor_and_fetch (type *ptr, type value, ...)
type __sync_nand_and_fetch (type *ptr, type value, ...)

_sync_*系列的built-in函数，用于提供加减和逻辑运算的原子操作。这两组函数的区别在于第一组返回更新前的值，第二组返回更新后的值。

无锁算法感触最深的是复杂度的分解，比如多线程对于一个双向链表的插入或删除操作，如何能一步一步分解成一个一个串联的原子操作，并能保证事务内存的一致性。

1.4从传统到无锁：编程范式的转变

在并发编程的世界中，传统的锁编程曾是保障数据一致性和线程安全的中流砥柱。就像在一场热闹的集市中，每个摊位是一个共享资源，而锁就是摊位的钥匙，线程则是想要使用摊位的商人。当一个商人拿到钥匙（获取锁）后，就能在摊位上自由交易（访问和修改资源），其他商人只能在一旁等待，直到钥匙被归还（锁被释放）。

这种方式虽然有效，但在多线程高并发的场景下，却逐渐暴露出诸多局限性。

线程阻塞是最直观的问题。当一个线程持有锁时，其他试图获取同一锁的线程就会被阻塞，进入等待状态。这就好比多个商人都想使用同一个摊位，但只有一个人能拿到钥匙，其他人只能干等着，白白浪费时间。在高并发系统中，大量线程的阻塞会导致上下文切换频繁，极大地消耗系统资源，降低了程序的执行效率。

死锁隐患更是让人头疼。想象一下，两个商人 A 和 B，A 拿着摊位 1 的钥匙，却想要使用摊位 2；B 拿着摊位 2 的钥匙，却想要使用摊位 1。双方都不愿意放弃自己手中的钥匙，又都在等待对方释放钥匙，结果就陷入了僵局，谁也无法继续。在编程中，死锁一旦发生，程序就会陷入停滞，无法正常运行，严重影响系统的稳定性。

传统锁编程还会带来较大的资源开销。锁的获取、释放以及维护锁的状态都需要消耗系统资源。随着线程数量的增加，这种开销会愈发明显，成为系统性能提升的瓶颈。

为了解决这些问题，无锁编程应运而生，开启了并发编程的新篇章。它就像是一场创新的集市改革，不再依赖钥匙（锁）来分配摊位，而是通过一种更巧妙的方式，让商人们能够更高效地使用摊位资源。无锁编程摒弃了传统的锁机制，采用原子操作、CAS（Compare-And-Swap）算法等技术，实现了多线程对共享资源的无阻塞访问，让线程在访问共享资源时无需等待锁的释放，大大提高了并发性能。

二、无锁编程的底层原理剖析

无锁编程具体使用和考虑到的技术方法包括：原子操作（atomic operations）, 内存栅栏（memory barriers）, 内存顺序冲突（memory order），指令序列一致性（sequential consistency）和顺ABA现象等等。

在这其中最基础最重要的是操作的原子性或说原子操作。原子操作可以理解为在执行完毕之前不会被任何其它任务或事件中断的一系列操作。原子操作是非阻塞编程最核心基本的部分，没有原子操作的话，操作会因为中断异常等各种原因引起数据状态的不一致从而影响到程序的正确。

2.1原子操作：无锁的基石

原子操作是无锁编程的基石，它确保了指令执行的不可分割性。就像在建造高楼时，每一块基石都必须坚实稳固，原子操作对于无锁编程也是如此，是构建整个体系的基础。在现代处理器中，简单类型的对齐读写操作通常是原子的，这意味着这些操作要么完全执行，要么完全不执行，不会出现部分执行的情况。比如对一个int类型变量的赋值操作int a = 10;，在多线程环境下，这个赋值操作要么成功完成，将10赋值给a，要么就没有执行，不会出现只赋了一半值的情况。

而 Read-Modify-Write 操作则更进一步，允许进行更复杂的原子事务性操作。以经典的i++操作为例，它实际上包含了读取i的值、对值进行加 1 修改、再将修改后的值写回这三个步骤。在传统的非原子操作中，这三个步骤可能会被线程调度打断，导致数据不一致。但在无锁编程中，通过原子的 Read-Modify-Write 操作，这三个步骤被视为一个整体，不可分割，从而保证了操作的原子性和数据的一致性。

假设线程 A 和线程 B 都要对共享变量i执行i++操作，如果没有原子操作的保证，可能会出现线程 A 读取i的值后，还没来得及写回，线程 B 就读取了相同的值，最终导致i只增加了 1，而不是 2。但有了原子操作，就能确保两个线程的i++操作都能正确执行，i最终会增加 2 。

2.2CAS 算法：核心机制解析

CAS（Compare-And-Swap）算法是无锁编程的核心机制，它如同无锁编程的 “大脑”，指挥着各个线程有序地访问共享资源。CAS 算法包含三个参数：V（要更新的变量）、E（预期值）、N（新值）。其工作原理是：当且仅当变量 V 的值等于预期值 E 时，才会将变量 V 的值更新为新值 N；如果 V 的值和 E 的值不同，那就说明已经有其他线程对 V 进行了更新，当前线程则什么都不做，最后 CAS 返回当前 V 的真实值。

在一个多线程的计数器场景中，假设有多个线程都要对计数器count进行加 1 操作。每个线程在执行加 1 操作时，会先读取count的当前值作为预期值 E，然后计算新值 N（即 E + 1），接着使用 CAS 算法尝试将count的值更新为 N 。如果此时count的值仍然等于预期值 E，说明在读取和尝试更新的过程中没有其他线程修改过count，那么更新操作就会成功；反之，如果count的值已经被其他线程修改，不等于预期值 E，更新操作就会失败，线程会重新读取count的当前值，再次尝试。通过这种不断比较和交换的方式，CAS 算法实现了无锁同步，避免了传统锁机制带来的线程阻塞和性能开销。

2.3内存屏障与顺序一致性

在多线程环境中，由于处理器的优化和指令重排序等原因，可能会导致内存操作的顺序与程序代码中编写的顺序不一致，从而引发数据一致性问题。内存屏障就像是一个 “交通警察”，负责维护内存操作的顺序，确保不同线程对内存操作的顺序可见性。内存屏障通过阻止处理器对其前后的内存操作进行重排序，使得在内存屏障之前的操作一定先于屏障之后的操作完成，从而维持了程序的顺序一致性。

在一个简单的多线程赋值和读取场景中，线程 A 先对共享变量x进行赋值操作x = 10;，然后对另一个共享变量y进行赋值操作y = 20;；线程 B 则先读取y的值，再读取x的值。如果没有内存屏障的保证，由于指令重排序，线程 A 的x = 10;和y = 20;操作可能会被重新排序，导致线程 B 读取到的y的值是 20，但读取到的x的值却还是初始值 0，这就破坏了程序的顺序一致性。但通过在适当的位置插入内存屏障，就可以保证线程 A 的赋值操作按照代码顺序执行，线程 B 读取到的x和y的值也是符合预期的，从而确保了程序的正确性。

三、无锁队列

无锁队列是lock-free中最基本的数据结构，一般应用场景是资源分配，比如TimerId的分配，WorkerId的分配，上电内存初始块数的申请等等。对于多线程用户来说，无锁队列的入队和出队操作是线程安全的，不用再加锁控制。

3.1无锁队列API

ErrCode initQueue(void** queue, U32 unitSize, U32 maxUnitNum);
ErrCode enQueue(void* queue, void* unit);
ErrCode deQueue(void* queue, void* unit);
U32 getQueueSize(void* queue);
BOOL isQueueEmpty(void* queue);