java - 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 行上循环。另一个正在收集数据的线程表明，线程循环所依据的变量都是真实的，但只有一个，因此线程应该有可能取得进展!
  • 在第二种情况下，除一个线程外，所有线程都在 A 行循环，另一个在 B 行循环。数据收集线程显示 qnode.next 不为空。
  • 没有线程不足，因为我检查它们正在“积极等待”插入简单的计数器(并且它们正在增加)。

测试是在一个简单的 PriorityQueue 上完成的。

Answer 1

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

继续在 A 行循环是看到陈旧值的结果，尽管 qnode.next.locked = false;来电unlock() .

类似地，继续在 B 行循环是看到陈旧值的结果，尽管 pred.next = qnode;来电lock() .

在这两种情况下都是 QNode 的字段另一个线程的突变。在前一种情况下 qnode.next , 在后者中 pred是 QNodes另一个线程。