比较和交换如何工作

Question

我已经阅读了一些帖子,说比较和交换保证原子性,但是我仍然无法得到它是怎么回事.这是比较和交换的通用伪代码:

int CAS(int *ptr,int oldvalue,int newvalue)
{
   int temp = *ptr;
   if(*ptr == oldvalue)
       *ptr = newvalue
   return temp;
}

这如何保证原子性？例如,如果我使用它来实现互斥锁,

void lock(int *mutex)
{  
    while(!CAS(mutex, 0 , 1));
}

这如何防止2个线程同时获取互斥锁？任何指针都会非常感激.

Answer 1

"通用伪代码"不是CAS(比较和交换)实现的实际代码.特殊硬件指令用于激活CPU中的特殊原子硬件.例如,在x86中LOCK CMPXCHG可以使用(http://en.wikipedia.org/wiki/Compare-and-swap).

例如,在gcc中,__sync_val_compare_and_swap()内置了 - 它实现了特定于硬件的原子CAS.这个操作的描述来自Paul E. McKenney的新书(并行编程很难,如果是这样,你能做些什么呢？,2014),第4.3节"原子操作",第31-32页.

如果您想了解更多关于在原子操作之上构建更高级别同步并在自动旋转中保存系统免受自旋锁和烧录cpu循环的更多信息,您可以futex在Linux中阅读有关机制的内容.关于futexes的第一篇论文是Ulute Drepper 2011的Futexes很棘手 ; 另一个是LWN文章http://lwn.net/Articles/360699/(历史性的文章是Fuss,Futexes和Furwocks:Linux中的Fast Userland Locking,2002)

Ulrich描述的互斥锁仅使用"快速路径"的原子操作(当互斥锁未被锁定且我们的线程是唯一想要锁定它的线程时),但如果互斥锁被锁定,线程将使用futex进入休眠状态( FUTEX_WAIT ...)(它将使用原子操作标记互斥变量,以通知解锁线程"有人在这个互斥锁上等待",因此解锁器将知道他必须使用futex唤醒它们(FUTEX_WAKE,.. .)

Answer 2

它如何防止两个线程获取锁？好吧，一旦任何一个线程成功，*mutex将会是1，所以任何其他线程的 CAS 都会失败（因为它是用期望值调用的0）。通过存储0在 中来释放锁*mutex。

请注意，这是 CAS 的一种奇怪用法，因为它本质上需要违反 ABA。通常，您只需使用简单的原子交换：

while (exchange(mutex, 1) == 1) { /* spin */ }

// critical section

*mutex = 0;   // atomically

或者，如果您想要稍微复杂一些并存储有关哪个线程拥有锁的信息，您可以使用 atomic-fetch-and-add 来做一些技巧（例如参见 Linux 内核自旋锁代码）。