0

我正在学习线程、锁等。因此，我不想使用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整个列表？我想避免dead-lockand starvation。

谢谢！

4

1 回答 1

1

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

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

于 2016-05-27T03:08:39.147 回答