首页 > 代码库 > 无锁编程

无锁编程

    无锁编程,即不使用锁的情况下实现多线程之间的变量同步,也就是在没有线程被阻塞的情况下实现变量的同步,所以也叫非阻塞同步(Non-blocking Synchronization)。
实现非阻塞同步的方案称为“无锁编程算法”( Non-blocking algorithm)。
    多线程编程条件下,多个线程需要对同一共享变量写操作时,一般使用互斥锁来解决竞争问题,如下:
1 extern int g_var;
2 
3 mutex_lock;
4 g_var ++;
5 mutex_unlock;

使用锁会导致其他线程block,使用不当还有可能造成死锁,以下介绍无锁编程相关概念。

1、LL/SC操作

MIPS等RISC cpu支持LL(Load Link)/SC(Store Conditional)操作,主要原理为:

1. LL t0, lock_key
# LL从内存中读取数据到寄存器中,实现接下来的 RMW(Read-Modify-Write) 操作中的Read。处理器会记住 LL 指令的这次操作(会在 CPU 的寄存器中设置一个不可见的 bit 位),同时 LL 指令读取的地址lock_key也会保存在处理器的寄存器中。

2. SC t0, lock_key
# SC 指令的功能是向内存中写入一个字,以完成前面的 RMW 操作中Write。会检查上次 LL 指令执行后的 RMW 操作是否是原子操作(即不存在其它对这个地址的操作),如果是原子操作,则 t0 的值将会被更新至内存中,同时 t0 的值也会变为1,表示操作成功;反之,如果 RMW 的操作不是原子操作(即存在其它对这个地址的访问冲突),则 t 的值不会被更新至内存中,且 t 的值也会变为0,表示操作失败。

SC 指令执行失败的原因有两种:

(1)在 LL/SC 操作序列的过程中,发生了一个异常(或中断),这些异常(或中断)可能会打乱 RMW 操作的原子性。

(2)在多核处理器中,一个核在进行 RMW 操作时,别的核试图对同样的地址也进行操作,这会导致 SC 指令执行的失败。

通过CPU支持的LL/SC操作,可以实现无锁对变量进行修改。

 

2、CAS操作

CAS(Compare And Swap): It compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value.

在 x86 下的指令CMPXCHG实现了CAS,前置LOCK既可以达到原子性操作, CAS 伪代码:

1 int compare_and_swap(int* reg, int oldval, int newval)
2 {
3   ATOMIC();
4   int old_reg_val = *reg;
5   if (old_reg_val == oldval)
6      *reg = newval;
7   END_ATOMIC();
8   return old_reg_val;
9 }

当寄存器中的值old_reg_val等于oldval时,才更新寄存器的值。

 

无锁编程