为什么 CAS（比较和交换）不等同于繁忙的等待循环？

Question

在过去几天阅读了一些关于无锁编程的内容后，我发现 util.java.Random class 使用以下例程创建它的位：

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

根据this answer to a post "Spinlock vs Busy wait"：

So-called lock-free algorithms tend to use tight busy-waiting with a CAS instruction, but the contention is in ordinary situations so low that the CPU usually have to iterate only a few times.

和 Wikipedia topic "Compare-and-Swap" :

Instead of immediately retrying after a CAS operation fails, researchers have found that total system performance can be improved in multiprocessor systems—where many threads constantly update some particular shared variable—if threads that see their CAS fail use exponential backoff—in other words, wait a little before retrying the CAS.[4]

维基百科的文章能看懂吗，找到了，但是还没用，或者是CAS指令失败后人为退避的常见做法。这就是这样一个循环在 CPU 使用方面不被认为是危险的原因，还是因为 CAS 没有经常受到争议？

第二个问题：创建对 seed 的引用是否有任何特定原因，或者我们是否也可以简单地使用 class 范围内的变量？

Answer 1

尝试 CAS 的多个线程是无锁的（但不是无等待的）。 其中一个线程每次尝试使用相同的 old 值 时都会取得进展。 https://en.wikipedia.org/wiki/Non-blocking_algorithm.

（多个线程是否都读取相同的 old 值，或者某些线程是否看到另一个线程的 CAS 结果取决于时间，并且基本上决定了有多少争用。）

这与普通的忙等待循环不同，后者只是在等待一些未知长度的操作，如果持有锁的线程被取消调度，则可能会无限期地卡住。在那种情况下，如果您的 CAS 无法获取锁，您肯定想退后一步，因为您肯定必须等待另一个线程做某事才能成功。

通常，无锁算法用于真正不需要复杂的指数退避的低争用情况。这就是链接的 SO 答案所说的。

这与 Wiki 文章中提到的情况 key 不同：许多线程不断更新某些特定的共享变量。这是一种高争用情况，因此最好让一个线程连续执行一堆更新并在其 L1d 缓存中保持行热。（假设您正在使用 CAS 来实现硬件不直接支持的原子操作，例如原子双精度 FP 添加，其中您 shared.CAS(old, old+1.0) 或其他东西。或者作为无锁队列的一部分或其他东西。 )

如果您使用的是在实践中竞争激烈的 CAS 循环，它可能有助于总吞吐量的一些回退，例如运行一条 x86 pause 失败指令，然后再试一次，以减少缓存行上的核心数。或者对于无锁队列，如果你发现它已满或为空，那么这基本上是一个等待另一个线程的情况，所以你绝对应该后退。

除了 x86 之外的大多数架构都有 LL/SC as their atomic RMW primitive，而不是直接的硬件 CAS。如果在 CAS 尝试期间其他线程甚至读取缓存行，则从 LL/SC 构建 CAS 可能会虚假地失败，因此它可能不会保证至少有一个线程成功。

希望硬件设计者尝试制造 CPU，使 LL/SC 能够抵抗争用引起的虚假故障，但我不知道细节。在这种情况下，回退可能有助于避免潜在的活锁。

（在 CAS 不能因争用而虚假失败的硬件上，活锁对于 while(!shared.CAS(old, old<<1)){} 之类的东西是不可能的。）

Intel's optimization manual 有一个等待锁释放的例子，它们循环 1 << retry_count 次（达到某个最大退避因子）请注意，这不是一个正常的 CAS 循环，它是无锁算法的一部分；这是为了实现一个锁。

退避等待锁变为空闲，而不仅仅是为了争用包含锁本身的缓存行。

  /// Intel's optimization manual
  /// Example 2-2. Contended Locks with Increasing Back-off Example

  /// from section 2.2.4 Pause Latency in Skylake Microarchitecture
  /// (~140 cycles, up from ~10 in Broadwell, thus max backoff should be shorter)
/*******************/
/*Baseline Version */
/*******************/
// atomic {if (lock == free) then change lock state to busy}
while (cmpxchg(lock, free, busy) == fail)
{
   while (lock == busy)
     _mm_pause();
}


/*******************/
/*Improved Version */
/*******************/
int mask = 1;
int const max = 64; //MAX_BACKOFF
while (cmpxchg(lock, free, busy) == fail)
{
   while (lock == busy)
   {
      for (int i=mask; i; --i){
         _mm_pause();
      }
      mask = mask < max ? mask<<1 : max;    // mask <<= 1  up to a max
   }
}

我通常认为在等待锁定时，您想以只读方式旋转而不是继续尝试使用 cmpxchg。我认为来自 Intel 的这个示例仅演示退避，而不是如何优化锁以避免延迟解锁线程的其他部分。

无论如何，请记住该示例不是，就像我们谈论的无锁队列或原子添加或其他原语的 CAS 重试实现。它正在等待另一个线程释放锁， 而不是 只是在读取旧值和尝试 CAS 新值之间出现的使用新值失败。

为什么 CAS（比较和交换）不等同于繁忙的等待循环？

Why isn't CAS (Compare And Swap) equivalent to busy wait loops?

java

concurrency

lock-free

compare-and-swap