java - 为什么 CAS(比较和交换)不等同于繁忙的等待循环？

Question

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

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 aCAS instruction, but the contention is in ordinary situations so lowthat 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 improvedin multiprocessor systems—where many threads constantly update someparticular shared variable—if threads that see their CAS fail useexponential backoff—in other words, wait a little before retrying theCAS.[4]

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

第二个问题:创建对 seed 的引用是否有任何特定原因，或者我们是否也可以简单地使用类作用域中的变量？

Answer 1

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

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

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

---

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

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

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

---

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

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

(在 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 新值之间出现的使用新值失败。