Параллельная связанная очередь использует CAS

Question

Я нашел этот фрагмент кода о параллельной связанной очереди в IBM Developer.

Но я не могу понять часть из них.Что

while(true){
    ...
    if(curTail == Tail.get()){
        if(residue == null){
            ...
        }
    }
}

---

В соответствии с определением curTail и остаток, я думаю, что curTail является копией Tail, а curTail является указателем, равным Tail.next.

Я считаю, чтоФункция compareAndSet будет определять, равен ли объект вызывающего объекта первому параметру, почему они должны оцениваться перед вызовом этой функции?Я думаю, что код ниже может так же хорошо.

        while (true) {
            Node<E> curTail = tail.get();
            Node<E> residue = curTail.next.get();
                if (curTail.next.compareAndSet(null, newNode)) /* C */ {
                    tail.compareAndSet(curTail, newNode) /* D */ ;
                    return true;
                } else {
                    tail.compareAndSet(curTail, residue) /* B */;
                }
            }
        }

Любая помощь будет оценена.Спасибо.

public class LinkedQueue <E> {
    private static class Node <E> {
        final E item;
        final AtomicReference<Node<E>> next;
        Node(E item, Node<E> next) {
            this.item = item;
            this.next = new AtomicReference<Node<E>>(next);
        }
    }
    private AtomicReference<Node<E>> head
        = new AtomicReference<Node<E>>(new Node<E>(null, null));
    private AtomicReference<Node<E>> tail = head;
    public boolean put(E item) {
        Node<E> newNode = new Node<E>(item, null);
        while (true) {
            Node<E> curTail = tail.get();
            Node<E> residue = curTail.next.get();
            if (curTail == tail.get()) {
                if (residue == null) /* A */ {
                    if (curTail.next.compareAndSet(null, newNode)) /* C */ {
                        tail.compareAndSet(curTail, newNode) /* D */ ;
                        return true;
                    }
                } else {
                    tail.compareAndSet(curTail, residue) /* B */;
                }
            }
        }
    }
}

Answer 1

Для справки: пример, пояснения к коду алгоритма доступны на на этой странице с сайта IBM Developer .

На странице, указанной выше, будут указаны цели каждой операции A , B , C и D и почему они должны разрешать то, что в них упоминается как конструктивное вмешательство между потоками, одновременно обновляющими хвост очереди.

Ваше изменение повреждает алгоритм.Предложение else должно не выполняться, если C неуспешен.Вместо этого он играет роль D , когда поток перехватывает незавершенное [*] обновление хвоста из другого потока.

[*]: то есть после C , но до D .

Чтобы понять, почему и когда это не удается, рассмотрите следующий сценарий.

while (true) {
   Node<E> curTail = tail.get();
   Node<E> residue = curTail.next.get();

   /* (i) */

   if (curTail.next.compareAndSet(null, newNode)) /* C */ {
     tail.compareAndSet(curTail, newNode) /* D */ ;
     return true;
   } else {
      tail.compareAndSet(curTail, residue) /* B */;
   }
}

• Два потока T1 и T2 начинаются одновременно в позиции (i) .Их стек содержит те же ссылки для curTail и residue.residue предполагается null (т.е. очередь должна находиться в состоянии покоя).

• T1 завершает первый CAS C успешно.Не выполняется D .

• T2 Сбой CAS C , ввод else, выполнениеCAS B успешно, поскольку ссылка tail не изменилась.

• T1 не удается выполнить CAS D поскольку ссылка, присвоенная tail, была установлена ​​на null на C .Нет отступления, и метод завершается.Элемент из T2 не вставлен.

• Вторая попытка для T1 , ссылка на tail равна null и curTail.next бросает NullPointerException.Структура данных повреждена.

Подводя итог, A и B работают в парах.Они существуют для того, чтобы мешающие потоки могли помочь сближению очереди с нормальным состоянием и восстановлению из очереди, оставшейся в промежуточном состоянии.Представьте себе, что поток выполняет C , но его убивают, прежде чем он сможет запустить D .Без A и B очередь была бы навсегда повреждена. A и B обеспечивает восстановление состояния и завершение незавершенной вставки.