一个通用的无锁同步

Question

无锁数据结构的实现有时并不容易实现。以下方法可能看起来很通用和简单，但我认为我们在这里遇到了一些问题：

private AtomicBoolean lock = new AtomicBoolean(false);

    public void func(...) {
        while !lock.compareAndSet(false,true);
        // Some code goes here...
        ...
        ...
        ...
        lock.set(false); 
    }
}

我认为上面的代码并不是真正的“无锁”，因为它将等待线程锁定在忙-等待模式下的while循环中。

因此，只有当“正确的”无锁同步是不可能的时候，代码才适用。

我的问题是-有没有可能用一些不同的方法实现一个通用的无锁的，并且它可以工作，这样线程就不会处于阻塞(如同步)或繁忙模式状态，代码将并行运行，因此我们可以提高性能？

我的目标是让线程保持运行。我知道如果代码很长，最好使用同步机制而不是无锁实现，所以让我们假设我们讨论的是短代码。

例如，下面是Linkedlist的例子，我认为这是一种很好的方法，但它不适用于常见的数据结构。如果我们在这里与AtomicBoolean一起使用，就不会是真正的“无锁”。

public class LinkedList<T> {

    private AtomicReference<Link<T>> head = new AtomicReference(null);

    public  void add(T data) {
      Link<T> localHead;
      Link<T> newHead = new Link<>(null, data);

      do {
        localHead = head.get();
        newHead.next = localHead;        
      } while (!head.compareAndSet(localHead, newHead));
    }
}

Answer 1

对于无锁甚至无等待的算法，确实有通用的构造方案。例如：

• A Methodology for Implementing Highly Concurrent Data Structures
• A highly-efficient wait-free universal construction
• A Wait-Free Universal Construct for Large Objects

然而，这些通常从理论的角度而不是实际的角度更有趣。在实践中，专门的无锁算法通常比从这些通用构造派生的算法性能更好。

如果你对无锁编程感兴趣，我建议你从The Art of Multiprocessor Programming这本书开始。