MCS锁实现中的问题 - JAVA

Question

我写了以下代码（摘自书籍《多处理器编程的艺术》）：

package Chapter7;

import java.util.concurrent.atomic.AtomicReference;

public class MCSLock implements Lock {

    AtomicReference<QNode> tail;
    ThreadLocal<QNode> myNode;

    public MCSLock() {
        tail = new AtomicReference<>(null);
        myNode = new ThreadLocal<QNode>() {
            @Override
            protected QNode initialValue() {
                return new QNode();
            }
        };
    }

    @Override
    @SuppressWarnings("empty-statement")
    public void lock() {
        QNode qnode = myNode.get();
        QNode pred = tail.getAndSet(qnode);
        if (pred != null) {
            qnode.locked = true;
            pred.next = qnode;
            while (qnode.locked);   // line A
        }
    }

    @Override
    @SuppressWarnings("empty-statement")
    public void unlock() {
        QNode qnode = myNode.get();
        if (qnode.next == null) {
            if (tail.compareAndSet(qnode, null)) {
                return;
            }
            while (qnode.next == null);    // line B
        }
        qnode.next.locked = false;
        qnode.next = null;
    }

    class QNode {
        boolean locked = false;
        QNode next = null;
    }
}

如果我使用少量线程和操作进行测试，似乎这个方法可以工作，但是每次我尝试使用8个线程和每个线程1000次操作时，就会发生死锁。我插入了一些打印来调试代码和另一个收集工作线程数据的线程。我发现：

• 有时死锁在A行，有时在B行。
• 在第一种情况下，所有线程都在A行循环。收集数据的其他线程显示，线程正在循环的变量全部为true，除了一个，因此线程应该有可能取得进展！
• 在第二种情况下，除了一个线程在B行循环外，所有线程都在A行循环。收集数据的线程显示qnode.next不为空。
• 没有挨饿线程，因为我检查它们是“主动等待”，插入简单计数器（并且它们逐渐增加）。

测试是在简单的优先队列上进行的。

- Luca Di Liello

Answer 1

该代码的问题在于它试图使用ThreadLocal实现线程封闭。但是，由于将QNodes链接在链表中并通过next引用和tail引用操作实例，它破坏了线程封闭，并且在没有针对QNode字段的其他同步机制的情况下，不能保证在线程之间可见性的更改。

尽管在unlock()中调用了qnode.next.locked = false;，但在行A中继续循环是看到旧值的结果。

同样，在lock()中调用了pred.next = qnode;，但在行B中继续循环是看到旧值的结果。

在这两种情况下，另一个线程的QNode字段被改变了。在前一种情况下，是qnode.next，在后一种情况下，是pred。

- bowmore

---

如果我在QNode类中使用原子变量，那么我应该解决问题吗？例如AtomicBoolean和AtomicReference。 - Luca Di Liello

因为我唯一知道的“技巧”就是使用易失变量，但在类QNode的这么多实例中使用它们会导致性能下降吗？ - Luca Di Liello

在这种情况下，使用原子变量也可以正常工作，只需将它们标记为volatile即可。volatile已经足够，因为改变值的操作不依赖于先前的值。至于性能方面，原子变量在强竞争环境下表现不佳，此时volatile可能更胜一筹。当典型使用在低竞争环境下时，原子变量可能更有效率。始终要确保并进行测量。 - bowmore

谢谢，这只是一个练习，但我会尝试检查一下在我的测试中，volatile变量是否能够胜过Atomic变量。 - Luca Di Liello

使用volatile变量的测试所需时间比原子操作少了约40％。运行更长时间的测试，差异减少到15％，但volatile变量仍然胜出。（所有测试都在我的MacBook上使用MCS锁的8个线程进行） - Luca Di Liello

Answer 2

如果你在线程1中运行pred.next，并且在没有同步的情况下在线程2中检查qnode.next，则由于内存屏障，线程2可能永远无法获得线程1中设置的值。请注意保留HTML标记。

- xingbin