Здравствуйте, 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. Возвращаемся к нашему разбитому корыту.