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

Question

我正在学习线程、锁等。因此，我不想使用 synchronized关键字或任何类 thread-safe其他semaphore和ReentrantLock (没有原子变量)。

我想要某种同步 LinkedList<T>的Node<T> ，按 T 的大小排序(假设 T 是 implements 具有 interface 和 size 函数以及 increment 、 lock 函数的 unlock )。我希望能够替换两个Nodes通过他们T.getSize()功能无需锁定所有列表。

例如，如果我只有一个线程，该函数将是一个“经典”替换函数，如下所示:

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; 
    }

}

现在让我们来讨论同步问题。

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

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 上使用替换函数，它们都将被锁定，我将一事无成。

如何使替换功能成为thread safe没有lock整个 list ？我想避免dead-lock和starvation .

谢谢!

Answer 1

允许最大并发性的最通用答案是锁定参与重新排序的所有四个节点。当它们都被锁定后，检查顺序是否没有改变 - 如果改变的话可能会中止并重试 - 然后重新排序，然后以相反的顺序释放锁。

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