Потокобезопасное переключение узлов Linked-List без блокировки всего списка

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 весь список? Я хочу избежать dead-lock а также starvation,

Спасибо!

Answer 1

Наиболее общий ответ, допускающий наибольшее количество одновременных действий, заключается в блокировке всех четырех узлов, участвующих в переупорядочении. После того, как они все заблокированы, убедитесь, что порядок не изменился - возможно, прерывание и повторная попытка, если это произошло - затем выполните переупорядочение, затем снимите блокировки в обратном порядке.

Сложность заключается в том, что во избежание тупиковых ситуаций узлы должны быть заблокированы по порядку в соответствии с некоторым фиксированным порядком. К сожалению, упорядочение их по позиции в списке не будет работать, так как это может измениться. Не гарантируется работа узлов hashCode и identityHashCode, поскольку могут быть конфликты. Вам нужно будет обеспечить свое собственное упорядочение, например, предоставив каждому узлу уникальный постоянный идентификатор при создании, который затем можно будет использовать для порядка блокировки.