C语言 比较和交换的工作原理
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22339466/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How Compare and Swap works
提问by StackSmasher
I have read quite some posts that say compare and swap guarantees atomicity, However I am still not able to get how does it. Here is general pseudo code for compare and swap:
我读过很多帖子说比较和交换保证原子性，但是我仍然不知道它是如何做到的。下面是比较和交换的通用伪代码：
int CAS(int *ptr,int oldvalue,int newvalue)
{
int temp = *ptr;
if(*ptr == oldvalue)
*ptr = newvalue
return temp;
}
How does this guarantee atomicity? For example, if I am using this to implement a mutex,
这如何保证原子性？例如，如果我使用它来实现互斥锁，
void lock(int *mutex)
{
while(!CAS(mutex, 0 , 1));
}
how does this prevent 2 threads from acquiring the mutex at the same time? Any pointers would be really appreciated.
这如何防止 2 个线程同时获取互斥锁？任何指针将不胜感激。
回答by osgx
"general pseudo code" is not an actual code of CAS (compare and swap) implementation. Special hardware instructions are used to activate special atomic hardware in the CPU. For example, in x86 the LOCK CMPXCHGcan be used (http://en.wikipedia.org/wiki/Compare-and-swap).
“通用伪代码”不是 CAS（比较和交换）实现的实际代码。特殊硬件指令用于激活 CPU 中的特殊原子硬件。例如，在 x86 中LOCK CMPXCHG可以使用 ( http://en.wikipedia.org/wiki/Compare-and-swap)。
In gcc, for example, there is __sync_val_compare_and_swap()builtin - which implements hardware-specific atomic CAS. There is description of this operation from fresh wonderful book from Paul E. McKenney (Is Parallel Programming Hard, And, If So, What Can You Do About It?, 2014), section 4.3 "Atomic operations", pages 31-32.
例如，在 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 页对此操作进行了描述。
If you want to know more about building higher level synchronization on top of atomic operations and save your system from spinlocks and burning cpu cycles on active spinning, you can read something about futexmechanism in Linux. First paper on futexes is Futexes are trickyby Ulrich Drepper 2011; the other is LWN article http://lwn.net/Articles/360699/(and the historic one is Fuss, Futexes and Furwocks: Fast Userland Locking in Linux, 2002)
如果您想了解更多关于在原子操作之上构建更高级别同步的信息，并从自旋锁和主动自旋时燃烧 CPU 周期中拯救您的系统，您可以阅读有关futexLinux 中的机制的一些内容。关于 futexes 的第一篇论文是Ulrich Drepper 2011 年发表的Futexes 是棘手的；另一篇是 LWN 文章http://lwn.net/Articles/360699/（历史性文章是Fuss、Futexes 和 Furwocks：Fast Userland Locking in Linux，2002）
Mutex locks described by Ulrich use only atomic operations for "fast path" (when the mutex is not locked and our thread is the only who wants to lock it), but if the mutex was locked, the thread will go to sleeping using futex(FUTEX_WAIT...) (and it will mark the mutex variable using atomic operation, to inform the unlocking thread about "there are somebody sleeping waiting on this mutex", so unlocker will know that he must wake them using futex(FUTEX_WAKE, ...)
Ulrich 描述的互斥锁只使用原子操作来实现“快速路径”（当互斥锁没有被锁定并且我们的线程是唯一想要锁定它的人时），但是如果互斥锁被锁定，线程将使用 futex( FUTEX_WAIT...)（它将使用原子操作标记互斥锁变量，通知解锁线程“有人在等待这个互斥锁”，因此解锁器将知道他必须使用 futex(FUTEX_WAKE, .. .)
回答by Kerrek SB
How does it prevent two threads from acquiring the lock? Well, once any one thread succeeds, *mutexwill be 1, so any other thread's CAS will fail (because it's called with expected value 0). The lock is released by storing 0in *mutex.
它如何防止两个线程获取锁？好吧，一旦任何一个线程成功，*mutex将会是1，所以任何其他线程的 CAS 都会失败（因为它是用期望值调用的0）。通过存储0在 中来释放锁*mutex。
Note that this is an odd use of CAS, since it's essentially requiringan ABA-violation. Typically you'd just use a plain atomic exchange:
请注意，这是 CAS 的一种奇怪用法，因为它本质上需要违反 ABA。通常，您只需使用简单的原子交换：
while (exchange(mutex, 1) == 1) { /* spin */ }
// critical section
*mutex = 0; // atomically
Or if you want to be slightly more sophisticated and store information about which thread has the lock, you can do tricks with atomic-fetch-and-add (see for example the Linux kernel spinlock code).
或者，如果您想稍微复杂一些并存储有关哪个线程拥有锁的信息，您可以使用 atomic-fetch-and-add 来做一些技巧（例如参见 Linux 内核自旋锁代码）。
