java - 通用的无锁同步

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 .