c - 比较和交换的工作原理

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(Is Parallel Programming Hard, And, If So, What Can You Do About It?，2014 年)的新书对此操作进行了描述，第 4.3 节“原子操作”，第 31-32 页。

如果您想了解更多关于在原子操作之上构建更高级别的同步并使您的系统免于自旋锁和在主动旋转时燃烧 cpu 周期的情况，您可以阅读有关 Linux 中的 futex 机制的内容。关于 futexes 的第一篇论文是 Futexes are tricky乌尔里希·德雷珀 2011 年；另一篇是LWN文章http://lwn.net/Articles/360699/ (具有历史意义的是 Fuss, Futexes and Furwocks: Fast Userland Locking in Linux，2002 年)

Ulrich 描述的互斥锁只使用“快速路径”的原子操作(当互斥锁未被锁定并且我们的线程是唯一想要锁定它的人)，但如果互斥锁被锁定，线程将进入休眠状态使用futex(FUTEX_WAIT...) , ...)