30

我读过很多帖子说比较和交换保证原子性，但是我仍然无法理解它是如何做到的。这是比较和交换的一般伪代码：

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 个线程同时获取互斥锁？任何指针将不胜感激。

4

3 回答 3

40

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

例如，在 gcc 中，有__sync_val_compare_and_swap()builtin - 实现特定于硬件的原子 CAS。来自 Paul E. McKenney 的新奇书 ( Is Parallel Programming Hard, And, If So, What Can You Can Do About It?, 2014)，第 4.3 节“原子操作”，第 31-32 页对此操作进行了描述。

如果您想了解更多关于在原子操作之上构建更高级别的同步以及使您的系统免于自旋锁和在主动旋转时消耗 cpu 周期的信息，您可以阅读有关futexLinux 中机制的内容。第一篇关于 futexes 的论文是 Ulrich Drepper 于 2011 年发表的Futexes are tricky；另一篇是 LWN 文章http://lwn.net/Articles/360699/（历史上的一篇是Fuss、Futexes 和 Furwocks: Fast Userland Locking in Linux , 2002）

Ulrich 描述的互斥锁仅使用原子操作来实现“快速路径”（当互斥锁未锁定并且我们的线程是唯一想要锁定它的线程时），但如果互斥锁被锁定，线程将使用 futex( FUTEX_WAIT...) （它会使用原子操作标记互斥量变量，以通知解锁线程“有人正在睡觉等待此互斥量”，因此解锁者将知道他必须使用 futex(FUTEX_WAKE, .. .)

于 2014-03-12T00:20:53.040 回答
6

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

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

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

// critical section

*mutex = 0;   // atomically

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

于 2014-03-12T00:21:01.043 回答
0

您不能在 C 中实现 CAS。它是在汇编中的硬件级别上完成的。

于 2020-12-09T11:06:00.040 回答