为什么不认为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));
}

根据这个 SO答案：

所谓的无锁算法倾向于对CAS指令使用严格的忙等待，但是在通常情况下竞争很低，以至于CPU通常只需要迭代几次。

和维基百科：

研究人员发现，在CAS处理失败后，无需立即重试，而是可以提高多处理器系统的整体系统性能，在多处理器系统中，如果看到CAS失败的线程使用指数退避，则许多线程会不断更新某些特定的共享变量，换句话说，请等待重试CAS之前需要一点时间。[4]

维基百科文章是否可以理解，已经找到但尚未使用，或者CAS指令在失败后人为地退缩是常见的做法。这是因为这样的循环对于cpu的使用不被认为是危险的，还是因为CAS一直没有引起争议？

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

Answer 1

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

（是否多个线程都读取相同的old值，或者是否某些线程看到另一个线程的CAS的结果取决于时序，而从根本上讲，这是确定有多少竞争的原因。）

这与普通的忙等待循环不同，后者仅等待一些未知长度的操作，如果对持有锁的线程进行了调度，则可能无限期地陷入困境。在这种情况下，如果您的CAS无法获得锁，您肯定要退后，因为您肯定必须等待另一个线程执行某些操作才能成功。

通常，在真正不需要复杂的指数补偿的低竞争情况下使用无锁算法。这就是链接的答案。

与Wiki文章中提到的情况相比，这是一个关键区别：许多线程不断更新某些特定的共享变量。这是一个竞争激烈的情况，因此最好让一个线程连续执行一堆更新，并将该行保持在其L1d高速缓存中，这可能更好。（假设您正在使用CAS来实现硬件不直接支持的原子操作，例如原子双精度FP添加，您shared.CAS(old, old+1.0)或某处。或者作为无锁队列或某些内容的一部分。）

如果您使用的CAS循环在实践中非常有争议，那么这可能会帮助减少总吞吐量，例如pause在失败之前运行x86 指令，然后再试一次，以使更少的内核重载到缓存行中。或者对于无锁队列，如果发现队列已满或为空，则基本上是等待另一个线程的情况，因此您绝对应该退后一步。

除x86以外的大多数体系结构都将LL / SC作为其原子RMW原语，而不是直接的硬件CAS。如果在CAS尝试期间其他线程甚至正在读取高速缓存行，则从LL / SC中构建CAS可能会虚假失败，因此可能无法保证至少有一个线程成功。

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

（在CAS不会因争用而虚假失败的硬件上，无法对诸如之类的东西进行活锁while(!shared.CAS(old, old<<1)){}。）

英特尔的优化手册中有一个等待锁释放的示例，其中锁循环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之间出现新值时失败。