锁的硬件实现

3,002 阅读4分钟

锁是什么

在多线程(协程)系统中,锁是实现互斥访问的同步机制。

具体来说,锁控制同一时刻只有一个线程(协程)访问临界区(critical section),避免竞争条件(race condition)的发生,从而保证并发的准确性。

具体的做法是在进入临界区之前先加锁,在离开临界区之后马上释放锁。

锁的硬件实现

锁是如何保证同一时刻只有一个线程(协程)访问临界区的,这涉及到锁的具体实现。

一般来说,锁的实现依赖底层的硬件指令,TAS(Test And Set)和 CAS(Compare And Set)是其中两个被广泛使用的硬件指令。

Test And Set

TAS指令的语义是:向某个内存地址写入值1,并且返回这块内存地址存的原始值。TAS指令是原子的,这是由实现TAS指令的硬件保证的(这里的硬件可以是CPU,也可以是实现了TAS的其他硬件)。

在x86架构中,TAS对应的汇编指令是bts(bit test and set),在多核CPU中,需要在前面加lock前缀,也就是lock bts

为了便于理解把TAS翻译成伪代码

function TestAndSet(boolean_ref lock) {
    boolean initial = lock;
    lock = true;
    return initial;
}

注意TestAndSet函数的执行要是原子的。

那么怎么在TAS的基础上实现锁呢?下面的case在TAS的基础上实现一个简单的自旋锁,这个锁虽然简单,在功能上是完备的,关于锁的效率和公平性问题后面再讨论。

volatile int lock = 0;

void Critical() {
    while (TestAndSet(&lock) == 1);
    critical section // only one process can be in this section at a time
    lock = 0 // release lock when finished with the critical section
}

注意上面的volatile关键字,volatile的语义是直接从内存中读取变量值。 对于实现了memory barriers的编译器来说,每次读取变量值之前,都会把之前对变量的写操作全部刷入内存,对于没有实现memory barriers的编译器来说则不一定,这种情况下,上述释放锁的操作lock=0,不会立即生效,虽然上个线程已经释放了锁,但是lock=0并不会马上刷到内存,下个线程也就不能马上获得锁,对锁的效率有一定影响。

Compare And Swap

同TAS一样,CAS也是由硬件支持的原子操作。在x86架构中,CAS对应的汇编指令是CMPXCHG。

CAS的语义是:比较某个内存地址的值与一个给定值(这个给定值是上一刻从此内存地址读出来的),如果相等,则把一个新值写入到此内存地址,有点抽象,翻译成代码如下

int compare_and_swap(int* reg, int oldval, int newval)
{
  ATOMIC();
  int old_reg_val = *reg;
  if (old_reg_val == oldval)
     *reg = newval;
  END_ATOMIC();
  return old_reg_val;
}

与TAS不同的是,TAS只操作一个bit,CAS可以操作32(64)个bit。

在多核CPU环境下,在CMPXCHG指令前加LOCK前缀,LOCK CMPXCHG才能保证操作是原子的。

ABA问题

ABA问题也叫做调包问题,其含义是:在多核CPU中,如果在读旧值和CAS操作之间,另外一个或者多个核对旧值就行了两次或多次修改,且修改的最终结果与旧值相同(从A到B再到A),那么在执行CAS操作的核看来,CAS操作成功了,但是正确的行为应该是此次CAS操作失败,因为旧值已经被修改多次。

解决ABA问题的一个思路是使用double-length CAS,一半字节用来存储一个counter,一半字节存储value,每次对value进行修改,counter都会+1。这样在发生ABA时,虽然value是一样的,但是counter大概率(思考什么情况下counter也会一致)不一致,从而解决ABA问题。

需要注意的是,发生ABA问题的根本原因是一个核在执行CAS操作时(假设使用内存地址X),其他核是可以读写内存地址X的,也就是说,在单核CPU中,不会发生ABA问题。在多核CPU中,除了double-length CAS之外,还有其他方式防止ABA。比如前面说的,在CMPXCHG指令前加LOCK前缀,也能防止ABA出现。LOCK CMPXCHG中LOCK的语义是保证LOCK后续指令访问对应内存是排他的,都不允许其他核访问对应的内存了,自然也就不存在ABA问题了。

最后需要说明的是,也存在不依赖于TAS和CAS实现的锁,比如说下面的case。

; Intel syntax

locked:                      ; The lock variable. 1 = locked, 0 = unlocked.
     dd      0

spin_lock:
     mov     eax, 1          ; Set the EAX register to 1.

     xchg    eax, [locked]   ; Atomically swap the EAX register with
                             ;  the lock variable.
                             ; This will always store 1 to the lock, leaving
                             ;  the previous value in the EAX register.

     test    eax, eax        ; Test EAX with itself. Among other things, this will
                             ;  set the processor's Zero Flag if EAX is 0.
                             ; If EAX is 0, then the lock was unlocked and
                             ;  we just locked it.
                             ; Otherwise, EAX is 1 and we didn't acquire the lock.

     jnz     spin_lock       ; Jump back to the MOV instruction if the Zero Flag is
                             ;  not set; the lock was previously locked, and so
                             ; we need to spin until it becomes unlocked.

     ret                     ; The lock has been acquired, return to the calling
                             ;  function.

spin_unlock:
     xor     eax, eax        ; Set the EAX register to 0.

     xchg    eax, [locked]   ; Atomically swap the EAX register with
                             ;  the lock variable.

     ret                     ; The lock has been released.