自旋锁的实现

发表于 更新于 分类于 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 3 分钟

自旋锁的实现

MIPS中LL/SC指令介绍

在多线程程序中，为了实现对共享变量的互斥访问，一般都会用spinlock实现，而spinlock需要一个TestAndSet的原子操作。而这种原子操作是需要专门的硬件支持才能完成的，在MIPS中，是通过特殊的Load，Store操作LL（Load Linked，链接加载）以及SC（Store Conditional，条件存储）完成的。

LL 指令的功能是从内存中读取一个字

SC 指令的功能是向内存中写入一个字

LL/SC 指令的独特之处在于，它们不是一个简单的内存读取/写入的函数，当使用 LL 指令从内存中读取一个字之后，比如 LL d, off(b)，处理器会记住 LL 指令的这次操作（会在 CPU 的寄存器中设置一个不可见的 bit 位），同时 LL 指令读取的地址 off(b) 也会保存在处理器的寄存器中。接下来的 SC 指令，比如 SC t, off(b)，会检查上次 LL 指令执行后的 RMW 操作是否是原子操作（即不存在其它对这个地址的操作），如果是原子操作，则 t 的值将会被更新至内存中，同时 t 的值也会变为1，表示操作成功；反之，如果 RMW 的操作不是原子操作（即存在其它对这个地址的访问冲突），则 t 的值不会被更新至内存中，且 t 的值也会变为0，表示操作失败。

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

  • 在 LL/SC 操作序列的过程中，发生了一个异常（或中断），这些异常（或中断）可能会打乱 RMW 操作的原子性。
  • 在多核处理器中，一个核在进行 RMW 操作时，别的核试图对同样的地址也进行操作，这会导致 SC 指令执行的失败。

简单的应用例子：

用MIPS LL/SC指令实现从内存单元100（R2)取数，把取出来的数加100并存回到100（R2)中的原子操作代码

1
2
3
4
5
1:  LL R3,100(R2)
     ADDI R3,R3,#100
     SC   R3,100(R2)
     beqz R3,1b
     NOP

CAS 原语

CAS （Compare-And-Swap） LL/SC这对CPU指令没有实现,但是实现了CAS. CAS是一组原语指令，用来实现多线程下的变量同步。 在 x86 下的指令CMPXCHG实现了CAS，前置LOCK既可以达到原子性操作。截止2013，大部分多核处理器均支持CAS。 CAS原语有三个参数，内存地址，期望值，新值。如果内存地址的值==期望值，表示该值未修改，此时可以修改成新值。否则表示修改失败，返回false，由用户决定后续操作。

简单自旋锁实现

什么是自旋锁

我们没有方法去控制对共享资源访问的有序性，但是我们有能力对共享资源采用锁的保护机制，当某个共享资源被锁住时，只有获取该锁的 CPU 核能够操作共享资源，其余试图访问共享资源的 CPU 核只能够等待这个锁的释放，这就是在 Linux 中被称为 Spinlock 的自旋锁保护机制。

Spinlock 的设计思想是基于一种被称为 Test-and-Set 的机制，它的操作分为三部分：

1）INIT

初始化 lock 值。示例如下：

1
lock := CLEAR;

2）LOCK

这个流程包括两部分：首先 CPU 核反复轮询 lock 值直到它处于空闲状态为止，然后利用 Test-and-Set 方式尝试设置该 lock 值，Test-and-Set 的操作可以描述成三步：

（a）读取 lock 值；

（b）设置 lock 值

(c）检查 lock 值是否设置成功，如果在步骤 （a） 之后还存在别的对 lock 值的操作，说明存在有并发访问 lock 值的情况，则步骤 （b） 的 lock 值将不能设置成功，还需要回到步骤 （a） 重新执行这个流程。

示例如下：

1
while ((lock == BUSY) || (TestAndSet(lock) == BUSY));

（3）UNLOCK

释放 lock 值。示例如下：

1
lock := CLEAR;

MIPS实现（基于LL/SC原语实现）

传统的 C 语言是无法实现 Test-and-Set 的机制的，因为它无法在多核之间建立一个交互的机制，因此 Test-and-Set 需要处理器给以相应的支持。以 MIPS 为例，它提供了 LL（Load Linked Word） 和 SC（Store Conditional Word） 这两个汇编指令来实现对共享资源的保护。

简单的自旋锁

1
2
3
4
5
6
7
Lock： 
 1： LL t0, 0x0(a0) //取回锁值，0 表示未被锁，1 表示有人持有锁 
 BNEZ t0, 1b //如果已经被锁，则自旋等待 
 ADDIU t0, t0, 0x1 //将 t0 改为已持有 
 SC t0, 0x0(a0) //存回 
 BEQZ t0, 1b //检查是否成功，否则重做 
 NOP 
1
2
3
4
Unlock： 
//mem fence 
SW $0, 0x0(a0) //解锁时写 0 
//mem fence

基于排队的公平的自旋锁

简单自旋排队锁 设 a0 为锁的地址。按请求顺序来 service。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Lock: (锁值为高低各 2 字节组成，高位为 tickets, 低位为 serve) 
 1: LL v0, 0x0(a0) //同时取回高低位 
 LI t0, 0x10000 //将高位 tickets 加一 
 ADDU t0, t0, v0 
 SC t0, 0x0(a0) //存回去 
 BEQZ t0, 1b //检查是否 LLSC 成功，失败则重试 
 NOP 
 SRL v0, v0, 16 //取出此时已经确定拿到的 tickets，放到低位 
 2: LHU t0, 0x0(a0) //检查当前 serve 值 
 BNE t0, v0, 2b //如果当前 serve 不是自己，则循环等待 
 NOP 
Unlock： 
 //mem fence 
 LHU t0, 0x0(a0) //取出当前 serve 
 ADDIU t0, t0, 0x1 
 SH t0, 0x0(a0) //加 1 存回去 
 //mem fence

解释：

  • LL 指令是 Load Linked，用于原子地将内存中的值加载到寄存器 v0。
  • LI 指令是 Load Immediate，将立即数 0x10000 加载到寄存器 t0。
  • ADDU 指令是无符号整数相加。
  • SC 指令是 Store Conditional，尝试将 t0 存储回内存，如果存储成功，则返回 1，否则返回 0。
  • BEQZ 指令是 Branch on Equal to Zero，如果 t0 为零（存储失败），则跳转到标号 1b，即重新尝试获取锁。
  • SRL 指令是 Shift Right Logical，将 v0 寄存器右移 16 位，得到高位 tickets。
  • LHU 指令是 Load Halfword Unsigned，将内存中的半字加载到寄存器 t0。
  • BNE 指令是 Branch on Not Equal，如果 t0 不等于 v0，则跳转到标号 2b，即循环等待，直到拿到锁。
  • LHU 指令是 Load Halfword Unsigned，将内存中的半字加载到寄存器 t0。
  • ADDIU 指令是 Add Immediate Unsigned，将 t0 寄存器的值加 1。
  • SH 指令是 Store Halfword，将 t0 寄存器的值存储回内存。

CAS 实现自旋锁

CAS：指令定义 cas r1, r2, Mem；r1 存放期望值，r2 存放更新值，

1
2
3
4
5
6
7
8
9
10
11
12
获得锁：//锁初始化为 0 
la t0, sem 
TryAgain: 
li t1, 0 
li t2, 1 
cas t1, t2, 0x0(t0) 
bnez t1, TryAgain 
nop 
relLOCK: 
la t0, sem 
li t1, 0 
sw t1, 0x0(t0)

CAS/ LL/SC原语

Compare_And_Swap(CAS)和 Load-Linked and Store-Conditional(LL/SC)是两种比较常见的 硬件同步原语。例如，Intel、AMD 的 x86 指令集和 Oracle/SUN 的 Sparc 指令集实现了 CAS指令；Alpha、PowerPC、MIPS、ARM 均实现了 LL/SC 指令。

（2）CAS 指令硬件实现比 LL/SC 的硬件实现复杂。使用 CAS 指令会碰到 ABA 问题，但是 LL/SC指令不会碰到该问题。LL/SC 指令中由于 SC 是尝试去写，因此在某些情况下，SC 执行成功 率很低，导致用 LL/SC 实现的锁执行开销变得很大。