Многопроцессорное программирование: стеки без блокировки

Question

В рамках подготовки к предстоящему экзамену по Concurrent Systems я пытаюсь завершить некоторые вопросы из учебника "Искусство многопроцессорного программирования". Меня беспокоит один вопрос:

Упражнение 129: Имеет ли смысл использовать один и тот же общий объект BackOff для push и pop в нашем объекте LockFreeStack? Как еще мы можем структурировать откат в пространстве и времени в ElventionBackOffStack?.

Этот вопрос меня беспокоит, потому что первое, что приходит мне в голову, это то, что он не имеет смысла, потому что все объекты отката - это заставляют процесс ждать, так почему бы не поделиться им? Вторая часть вопроса полностью ускользает от меня, и любая помощь приветствуется.

Код для LockFreeStack:

public class LockFreeStack<T> {

    AtomicReference<Node> top = new AtomicReference<Node>(null);

    static final int MIN_DELAY = ...;
    static final int MAX_DELAY = ...;
    Backoff backoff = new Backoff(MIN_DELAY, MAX_DELAY);

    protected boolean tryPush(Node node) {
        Node oldTop = top.get();
        node.next = oldTop;
        return(top.compareAndSet(oldTop, node));
    }

    public void push(T value) {
        Node node = new Node(value);
        while (true) {
            if (tryPush(node)) {
                return;
            } else {
                backoff.backoff();
            }
        }
    }

Answer 1

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

Answer 2

Не уверен, поможет ли какая-либо из моих болтовней, но я все равно нажму кнопку "Опубликовать".

Ответ зависит от реализации backoff().Поскольку цель здесь состоит в том, чтобы избежать синхронизации, локального хранилища не будет - может быть, какое-то в ThreadLocal.Если алгоритм отката использует рандомизатор, он также должен быть реентерабельным.Так что, скорее всего, вы способны поделиться им между pop и push - теперь вы этого хотите.Так как push и pop пытаются изменить ссылку top, было бы хорошо, если бы откат дал последовательным потокам совершенно разные числа.Есть больше разногласий вокруг толчка или популярности?Нужно ли нам более агрессивно отступать тем или иным способом?Если это общий стек, то вы не будете знать.

С точки зрения того, как откат может быть «реструктурирован», я также не уверен.Можете ли вы использовать успешный толчок или поп как возможность уменьшить время отсрочки?Как насчет разницы между случайным ожиданием отката и простыми числами в последовательности, присвоенной ThreadLocal?

Answer 3

Использование отката в этой ситуации является чрезмерным убийством.

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

public void push(T value) { 
   Node node = new Node(value); 
   while (!tryPush(node)) 
       backoff.backoff(); 
 } 

ИМХО: можно сократить до

public void push(T value) { 
   Node node = new Node(value); 
   while (!tryPush(node));
}