Неблокирующий стек поп

Question

Рассмотрим следующий код, который использует неблокирующую семантику для извлечения стека:

T Stack<T>::pop( ) 
{ 
    while (1) { 
        if (top == NULL) 
           throw std::string(“Cannot pop from empty stack”);
        Node* result = top;
        if (top && __sync_bool_compare_and_swap(&top, result, top->next)) { 
            return result->data;
        }
    }
}

Меня беспокоит то, что если поток, выполняющий всплывающее окно, был отменен как раз перед вторым оператором if и ко времениназад, отрезок времени, стек пуст, мой чек во 2-м цикле достаточно хорош, чтобы предотвратить сбой?Конечно, в худшем случае сразу после сравнения вершины с нулем поток может быть не запланирован.

Любые мнения приветствуются.Мне известно о проблеме ABA, которая также может возникнуть.

Answer 1

Во-первых, предполагая, что top является изменчивым и может быть изменен другим потоком в любой точке, принимайте его значение только один раз за цикл, чтобы не вытащить коврик из-под себя:

T Stack<T>::pop( )
{
    while ( 1 ) {
        Node* result = top;
        if ( result == NULL )
            throw std::string ( “Cannot pop from empty stack” );
        // you now know result isn't NULL here 
        if ( __sync_bool_compare_and_swap ( &top, result, result -> next ) ) {
            return result -> data;
        }
    }
}

Это все еще не решает проблему удаления result или иного изменения между получением значения top и его разыменованием.

Вы хотите использовать безопасный страж вместо result -> next, поэтому логика:

• Если top равен нулю, то очередь пуста
• Если top - это страж, то что-то еще вытаскивает из стека, иди делай что-нибудь еще полезное.
• Если top не равен ни одному, поместите часовой в вершину, получите значение из результата, поместите результат -> следующий сверху, удалите результат.

Считается ли это по-прежнему без ожидания & dagger; зависит от того, сможете ли вы найти что-нибудь полезное в промежуточном состоянии.

Есть много статей, которые нужно прочитать для более эффективных способов, чем использование дозорного - в действительности вы симулируете CAS из двух слов с одним CAS, так как вам нужно проверить что-то о состоянии result, а также состояние top. Они слишком сложны, чтобы воспроизвести их здесь.

Не проверено никак:

bool Stack<T>::pop ( T&out )
{
    static const Node* const empty ( 0 );
    static const Node* const sentinel ( empty + 1 );

    while ( true ) {
        Node* result = top;

        if ( result == empty )
            throw std::string ( “Cannot pop from empty stack” );

        if ( result == sentinel )
            // something else is popping, return false and allow 
            // current thread to do some work before retrying
            return false;

        if ( __sync_bool_compare_and_swap ( &top, result, sentinel ) ) {
            // only one thread can CAS from a given result to something, 
            // so we are the only thread which has this value of result
            // hence we can dereference it and delete it/return it to a pool
            //
            // no other thread will change top if top == sentinel, so this
            // CAS can't fail
            if ( !__sync_bool_compare_and_swap ( &top, sentinel, result -> next ))
                throw std::string ( "nobody's perfect" );

            out = result -> data;
            delete result;
            return true;
        }
    }
}

Поскольку вы проверяете или изменяете только результат результата в одном потоке за раз, он должен быть безопасным (я не использовал этот точный шаблон раньше, и обычно я заканчиваю думать о странных случаях через пару дней после Я что то проектирую). Стоит измерить, окажется ли это лучше, чем перенос std :: deque с помощью pthread_mutex_trylock.

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

_{& кинжал; Я в основном работаю на x86 / x64, где нет такого понятия, как код без блокировки, поскольку CMPXCHG неявно блокирует шину и требует времени, пропорционального количеству кэшей для синхронизации. Таким образом, вы можете иметь код, который не вращается и не ждет, но вы не можете иметь код, который не блокируется.}

Answer 2

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

Answer 3

Я не понимаю, как это может работать.Проблема, которую я вижу, состоит в том, что когда вы разыменовываете top в top->next, это расположение памяти может быть недействительнымКакой-то другой поток мог вытолкнуть стек и удалить или иным образом изменить элемент.

Answer 4

Тема структур данных без блокировки была модной темой для Доктора Добба, хотя она все еще была опубликована в бумажном виде.Статьи по-прежнему можно найти здесь .

Answer 5

Правильно.

Более того, вы забываете о возможности переупорядочения памяти и кэширования.Например, ваш поток может по-прежнему видеть старое значение для top, даже после того, как для другого потока установлено значение NULL.