旋转锁是如何在引擎盖下实现的？

Question

这是一个锁,一次只能由一个执行线程持有.尝试通过另一个执行线程获取锁定使得后者循环直到锁定被释放.

当两个线程试图在同一时间获取锁时,它如何处理？

我认为这个问题也适用于其他各种互斥实现.

Answer 1

正如前面的海报所示,每个现代机器类型都有一个特殊的指令类,称为"原子",它按照前面的海报所示进行操作......它们至少针对指定的存储位置序列化执行.

在x86上,有一个LOCK汇编器前缀,它向机器指示应该以原子方式处理下一条指令.遇到指令时,x86上会发生一些有效的事情.

1. 取消挂起的读取预取(这意味着CPU不会向程序提供可能在原子上过时的数据).
2. 正在挂起的内存写入被刷新.
3. 执行操作,原子地保证并与其他CPU进行序列化.在这种情况下,"序列化"意味着"它们一次一个地发生".原子意味着"该指令的所有部分都在没有任何其他干预的情况下发生".

对于x86,有两个常用指令用于实现锁.

1. CMPXCHG.有条件的交换.伪代码:

uint32 cmpxchg(uint32 *memory_location, uint32 old_value, uint32 new_value) {
    atomically {
        if (*memory_location == old_value) 
            *memory_location = new_value;
        return old_value;
    }
}

2. XCHG.伪代码:

uint32 xchg(uint32 *memory_location, uint32 new_value) {
    atomically {
        uint32 old_value = *memory_location;
        *memory_location = new_value;
        return *old_value;
    }
}

所以,你可以像这样实现一个锁:

uint32 mylock = 0;
while (cmpxchg(&mylock, 0, 1) != 0)
    ;

我们旋转,等待锁,因此,旋转锁.

现在,解锁的指令不会表现出这些好的行为.根据您所使用的机器,通过解锁指令,可以观察到各种违反一致性的行为.例如,即使在具有非常友好的内存一致性模型的x86上,也可以观察到以下内容:

    Thread 1      Thread 2
    mov [w], 0    mov [x], 0
    mov [w], 1    mov [x], 2
    mov eax, w    mov eax, x
    mov [y], eax  mov [z], eax

在该程序结束时,y和z都可以具有值0!.

无论如何,最后一个注释:x86上的LOCK可以应用于ADD,OR和AND,以便为指令获得一致的原子读 - 修改 - 写语义.这对于设置标志变量并确保它们不会丢失很重要.没有它,你有这个问题:

   Thread 1       Thread 2
   AND [x], 0x1   AND [x], 0x2

在该程序结束时,x的可能值为1,2和0x1 | 0x2(3).为了获得正确的程序,您需要:

   Thread 1           Thread 2
   LOCK AND [x], 0x1  LOCK AND [x], 0x2

希望这可以帮助.