链表节点的线程安全切换，无需锁定整个列表

Question

我正在学习线程、锁等。因此，我不想使用 synchronized 关键字或除 [=14] 之外的 thread-safe 任何 class =] 和 ReentrantLock（没有原子变量）。

我想要 Node<T> 的同步 LinkedList<T>，按 T 的大小排序（假设 T 是 implements 和 interface 具有 size 和 increment 函数以及 lock、unlock 函数）。我希望能够在不锁定所有列表的情况下用它们的 T.getSize() 函数替换两个 Nodes。

例如，如果我只有一个线程，函数将是一个 "classic" 替换函数，类似于：

public void IncrementAndcheckReplace(Node<T> node)
{
    node.getData().incrementSize();
    Node nextNode = node.getNext();
    if(nextNode == null)
        return;
    while(node.getData().getSize() > nextNode.getData().getSize())
     {
        node.getPrev().setNext(nextNode);
        nextNode.setPrev(node.getPrev());
        Node nextnext = nextNode.getNext();
        nextNode.setNext(node);
        node.setPrev(nextNode);
        node.setNext(nextnext);
        nextnext.setPrev(node);

        nextNode = node.getNext();
        if(nextNode == null)
            break; 
    }

}

现在让我们来看看同步问题。

我想尝试做类似的事情来为我的 Nodes 创建一个 lock:

public void IncrementAndcheckReplace(Node<T> node)
{
    node.lock(); //using fair ReentrantLock for specific node       
    node.getData().incrementSize();
    Node nextNode = node.getNext();
    if(nextNode == null)
    {
        node.unlock();
        return;
    }
    nextNode.lock();
    while(node.getData().getSize() > nextNode.getData().getSize())
     {
        Node prev = node.getPrev();
        if(prev != null)
        {
            prev.lock();
            prev.setNext(nextNode);
        }
        nextNode.setPrev(prev);
        Node nextnext = nextNode.getNext();
        if(nextnext != null)
        {
            nextnext.lock();
            nextnext.setPrev(node);
        }
        nextNode.setNext(node);
        node.setPrev(nextNode);
        node.setNext(nextnext);
        if(prev!=null)
            prev.unlock();
        if(nextnext!=null)
            nextnext.unlock();
        nextNode.unlock();

        nextNode = node.getNext();
        if(nextNode == null)
            break;
        nextNode.lock();
    }
    node.unlock();
}

问题是这不是线程安全的，可能会发生死锁。例如，假设我们有 Node a, Node b 其中 a.next == b and b.prev==a 现在如果线程 A 试图在 a 上使用替换函数，而线程 B 试图在 b 上使用替换函数，它们都将被锁定，我将永远无处可去。

如何在没有 lock 整个列表的情况下将替换函数设为 thread safe？我想避免 dead-lock 和 starvation.

谢谢！

Answer 1

允许最大并发性的最一般的答案是锁定重新排序中涉及的所有四个节点。在它们都被锁定后，检查顺序是否没有改变——如果改变了可能会中止并重试——然后重新排序，然后以相反的顺序释放锁。

棘手的部分是，为了避免死锁，必须根据一些固定的顺序依次锁定节点。不幸的是，按列表中的位置对它们进行排序是行不通的，因为该排序可以更改。节点的 hashCode 和 identityHashCode 不能保证有效，因为可能会发生冲突。您需要提供一些您自己的顺序，例如在构造时为每个节点提供一个唯一的永久 ID，然后可以将其用于锁定顺序。

链表节点的线程安全切换，无需锁定整个列表

Thread safe switching of Linked-List nodes without locking the entire list

java

multithreading

synchronization

deadlock

starvation