在过去几天里，我读了一些关于无锁编程的文章，发现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));
}
根据对一篇帖子的回答；Spinlock vs Busy wait"：
所谓的无锁算法倾向于使用紧忙等待CAS指令，但争用在普通情况下非常低CPU通常只需要迭代几次。
和维基百科的主题"比较和交换"：
不是在CAS操作失败后立即重试，研究人员发现，整个系统的性能可以得到改善在多处理器系统中，许多线程不断更新一些如果发现其CAS无法使用，则特定的共享可变if线程指数后退--换句话说，在重试CAS。[4]
维基百科的文章是否可以理解，它已经被发现，但还没有被使用，或者CAS指令在失败后人为后退是常见的做法。这是这样一个循环在CPU使用方面不被认为是危险的原因，还是因为CAS没有经常受到质疑？
第二个问题：创建对seed的引用有什么具体的原因吗？或者我们也可以简单地使用类范围中的变量吗？
多个线程试图CAS某个东西是无锁定的(但不是无等待的)每次尝试使用相同的old值时，其中一个线程都会取得进展。https://en.wikipedia.org/wiki/Non-blocking_algorithm.
(多个线程是否都读取相同的old值，或者一些线程是否看到另一个线程的CAS的结果取决于时间，这基本上决定了有多少争用。)
这与正常的忙等待循环不同，后者只是在等待一些未知长度的操作，如果持有锁的线程被取消调度，则可能会无限期地被阻塞。在这种情况下，如果您的CAS未能获取锁，您肯定希望退出，因为您必须等待另一个线程执行某些操作才能成功。
通常在低争用情况下使用无锁定算法，在这种情况下并不真正需要复杂的指数退避。这就是关联SO的答案。
这与Wiki文章中提到的情况有一个键的区别：许多线程不断更新某些特定的共享变量。这是一种高争用性的情况，所以最好让一个线程在一行中进行一系列更新，并在L1d缓存中保持该行的热度。(假设您使用CAS来实现硬件不直接支持的原子操作，如原子双精度FP-add，其中shared.CAS(old, old+1.0)或其他。或者作为无锁定队列或其他的一部分。)
如果您使用的是在实践中竞争激烈的CAS循环，它可能有助于总吞吐量，其中一些可以后退，例如在失败时运行x86pause指令，然后再重试，以减少在缓存线上冲击的内核。或者对于一个无锁定队列，如果你发现它是满的或空的，那么这基本上是在等待另一个线程的情况，所以你肯定应该退出。
除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。我认为英特尔的这个例子只是演示后退，而不是如何优化锁以避免延迟解锁线程的其他部分。
无论如何，请记住，这个例子是，而不是，就像我们谈论的无锁队列或原子添加或其他原语的CAS-retry实现一样。它正在等待另一个线程释放锁，而不是只是在读取旧值和尝试在新值中使用CAS之间出现的使用新值失败。