По ссылке http://www.ibm.com/developerworks/ru/library/j-jtp04186/ есть учебный пример реализации неблокирующего стека при помощи AtomicReference:

Листинг 3. Неблокирующий стек, использующий алгоритм Трайбера (Treiber)

public class ConcurrentStack<E> {
    AtomicReference<Node<E>> head = new AtomicReference<Node<E>>();

    public void push(E item) {
        Node<E> newHead = new Node<E>(item);
        Node<E> oldHead;
        do {
            oldHead = head.get();
            newHead.next = oldHead;
        } while (!head.compareAndSet(oldHead, newHead));
    }

    public E pop() {
        Node<E> oldHead;
        Node<E> newHead;
        do {
            oldHead = head.get();
            if (oldHead == null) 
                return null;
            newHead = oldHead.next;
        } while (!head.compareAndSet(oldHead,newHead));
        return oldHead.item;
    }

    static class Node<E> {
        final E item;
        Node<E> next;

        public Node(E item) { this.item = item; }
    }
}

Возник вопрос по поводу куска кода в методе pop

if (oldHead == null) return null;

Разве после проверки условия и до возвращения из метода в стек не могут положить новый объект?
Понимаю, что пример учебный, но хочется разобраться. Есть ли ошибка в данном листинге? Где можно почитать про этот алгоритм (алгоритм Трайбера)? Является ли это ошибкой в реализации или допущением?
Помогите, пожалуйста.

От критики данного стека отойду, предположим что он не блокирующийся и правильно реализован.

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

Возвращаясь к вашему вопросу: добавлю, что что-то будет добавлено после return null — и так будет — и вообще в любом месте может быть добавлено, ибо неблокирующийся. Выборка из стека будет давать то, что есть на данный момент.

Здравствуйте, UDI, Вы писали:

UDI>От критики данного стека отойду, предположим что он не блокирующийся и правильно реализован.

Как по вашему будет лучше реализовать такой стек?

Здравствуйте, trupanka, Вы писали:

T>Здравствуйте, UDI, Вы писали:

UDI>>От критики данного стека отойду, предположим что он не блокирующийся и правильно реализован.

T>Как по вашему будет лучше реализовать такой стек?

Сейчас прочитал статью, реализация по-моему отличная, по крайней мере ошибки (или непонятное поведение) в многопоточной среде при использовании не должны возникнуть. Единственное что мне не понятно — почему в счетчике они использовали compareAndSet, а не incrementAndGet? Наверное, таким образом подводили ко второму примеру.

UDI>Единственное что мне не понятно — почему в счетчике они использовали compareAndSet, а не incrementAndGet? Наверное, таким образом подводили ко второму примеру.

Здесь размышляют, зачем там два раза вычисляют v + 1

Здравствуйте, trupanka, Вы писали:

UDI>>Единственное что мне не понятно — почему в счетчике они использовали compareAndSet, а не incrementAndGet? Наверное, таким образом подводили ко второму примеру.

T>Здесь размышляют, зачем там два раза вычисляют v + 1

Хм, да. Но, тем не менее, правильно. Происходит два вычисления выражения v+1, но не v+1+1. На производительности не сильно скажется, но я считаю, что автор статьи просто красиво подводил читателя к использованию compareAndSet во втором примере. Просто, чтобы идея подхода к реализации была аналогичной — с while и compareAndSet.

UDI>>От критики данного стека отойду, предположим что он не блокирующийся и правильно реализован.
T>Как по вашему будет лучше реализовать такой стек?
неблокирующий — elimination backoff stack получшее вроде будет.
идея и проблемы трейберовского хорошо(т.е. наглядно) изложены здесь

T>Разве после проверки условия и до возвращения из метода в стек не могут положить новый объект?
могут
T>Понимаю, что пример учебный, но хочется разобраться. Есть ли ошибка в данном листинге?
нет
T>Где можно почитать про этот алгоритм (алгоритм Трайбера)?
ну, в гугле. или в The Art of Multiprocessor Programming.
оригинал трейберовского алгоритма считается,что здесь :24-25 страница (20-21 в скане)

abch-98-ru, большое спасибо.