如何在汇编语言级别实现线程同步？

Question

虽然我熟悉并发编程概念,如互斥和信号量,但我从未理解它们是如何在汇编语言级别实现的.

我想有一组内存"标志"说:

• 锁A由线程1保持
• 锁B由螺纹3保持
• 锁C不被任何线程保持
• 等等

但是如何在线程之间同步访问这些标志呢？像这个天真的例子只会产生竞争条件:

  mov edx, [myThreadId]
wait:
  cmp [lock], 0
  jne wait
  mov [lock], edx
  ; I wanted an exclusive lock but the above 
  ; three instructions are not an atomic operation :(

Answer 1

• 实际上,这些往往是用CAS和LL/SC实现的.(......在放弃线程的时间片之前旋转一些 - 通常是通过调用切换上下文的内核函数.)
• 如果你只需要一个自旋锁,那么维基百科给你一个xchg在x86/x64上以CAS为前缀锁定CAS的例子.因此从严格意义上说,制作自旋锁不需要CAS - 但仍然需要某种原子性.在这种情况下,它使用原子操作,该操作可以将寄存器写入存储器并在一个步骤中返回该存储器槽的先前内容.(为了澄清一点:锁定前缀断言#LOCK信号,确保当前CPU具有对存储器的独占访问权.在今天的CPU上,它不一定以这种方式执行,但效果是相同的.通过使用xchg我们确保我们不会在读取和写入之间的某个地方被抢占,因为指令不会中途中断.所以如果我们有一个假想的锁定mov reg0,mem/lock mov mem,reg1 pair(我们没有),这可能不会完全相同 - 它可能会在两个mov之间被抢占.)
• 在当前的体系结构中,正如评论中所指出的,您最终会使用CPU的原子基元和内存子系统提供的一致性协议.
• 因此,您不仅要使用这些原语,还要考虑架构保证的缓存/内存一致性.
• 也可能存在实施细微差别.考虑例如自旋锁:
  • 而不是一个天真的实现,你应该使用例如TTAS自旋锁与一些指数退避,
  • 在超线程CPU上,你应该发出一些pause指令,作为你正在旋转的提示 - 这样你运行的核心可以在这期间做一些有用的事情.
  • 你应该在一段时间之后真的放弃旋转和屈服控制到其他线程
  • 等等...
• 这仍然是用户模式 ​​- 如果您正在编写内核,您可能还可以使用其他一些工具(因为您是调度线程并处理/启用/禁用中断的工具).

Answer 2

x86架构长期以来都有一条指令xchg,它将寄存器的内容与存储位置进行交换.xchg一直是原子的.

始终有一个lock前缀可以应用于任何单个指令以使该指令成为原子.在有多处理器系统之前,所有这一切确实是为了防止在锁定指令中间传递中断.(xchg被隐式锁定).

本文有一些使用xchg实现自旋锁http://en.wikipedia.org/wiki/Spinlock的示例代码

当开始构建多CPU和后来的多核系统时,需要更复杂的系统来确保锁和xchg同步所有内存子系统,包括所有处理器上的l1缓存.大约在这个时候,对锁定和无锁算法的新研究表明原子CompareAndSet是一个更灵活的原语,所以更现代的CPU有这个作为指令.

附录:在评论安德拉什提供的允许指令的"尘封已久的"列表lock前缀. http://pdos.csail.mit.edu/6.828/2007/readings/i386/LOCK.htm