Re[3]: Lock-free array-based stack
От: remark Россия http://www.1024cores.net/
Дата: 01.03.10 15:16
Оценка: 4 (1)
Здравствуйте, remark, Вы писали:

JR>>По-моему, SafeStackItem<T> логичнее было-бы сделать структурой.

JR>>Посмотрите это и это(pdf)
JR>>Возможно, будет любопытно.


Только если ради любопытства, там та же ABA. Это то, что я имел в виду касательно самопального кода в интернет. Сделать *почти* работающий алгоритм легко, сделать же надёжно работающий, да ещё и быстрый, алгоритм крайне сложно.
Автор решил ABA для основного стека с помощью вспомогательного, но вот во вспомогательном та же самая ABA, которая никак не решена (ввести третьий стек? ).
Более конкретно.

    void FreeMemory()
    {
        for(;;) {
            TNode *current = FreePtr;
            if (!current)
                break;
            if (atomic_add(DequeueCount, 0) == 0) {
                // node current is in free list, no dequeus were active at least once since then
                if (cas(&FreePtr, (TNode*)0, current))
                    EraseList(current);
            } else
                break;
        }
    }

    void EraseList(TNode * volatile p)
    {
        while (p) {
            TNode *next = p->Next;
            delete p;
            p = next;
        }
    }


Первый поток приходит в FreeMemory(), считывает какой-то current, потом успешно проверяет, что DequeueCount==0, потом засыпает.
Приходит второй поток и освобождает все элементы из freelist.
Далее эти же элементы выделяются повторно, добавляются в стек, удаляются из стека, и попадает опять во freelist.
Далее просыпается первый поток и успешно делает cas(&FreePtr, (TNode*)0, current), и удаляет все элементы, хотя DequeueCount сейчас может быть != 0. Возвращаемся к нашему разбитому корыту.



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.