Добрый день

"Неблокируемый" - значит N ниток могут добавлять/удалять элементы списка не прибегая к мутексам или др. локерам
"Список" - просто список, (а не контейнер). Т.е. элемент содержит указатель на следующий, напр.

C++ (Qt)
struct CData {
 ...
 CData * mNext;  // следующий в списке
 
 static volatile CData * mDataFirst;  // указатель на первый элемент списка (голова)
 static volatile CData * mDataLast;  // указатель на последний элемент списка (хвост)
};
 

Извлечение элемента из списка продвигает голову, помещение в список - хвост. Т.е. "запросы обрабатываются в порядке поступления" (FIFO). Заметим что в случае LIFO (стек, push/pop, хвоста нет) "неблокируемость" достигается очень легко. А как сделать здесь?

Спасибо

Что расплывчатого в термине FIFO? И читатели/писатели здесь ни при чем. Если "потом удаляют" - то какие же они "читатели"?    Вернее, сначала элемент извлекается из списка, а что там дальше с ним (читается или пишется) уже дело извлекшего

"неблокируимая очередь" было бы точнее. Список ассоциируется с итерацией, сплайсами.


Непонятно, как сделать, не прокомментируете?

У меня Pop аналогично не получается Там надо почитать вперёд CData::mDataFirst->mNext, а оно к тому времени могло попасть по free и unmap.

чего тут опровергать. представленный здесь код не будет корректно работать с множеством потоков.

одновременное выполнение push из двух потоков может привести к потере помещаемых данных.
ShouldDelete() вообще непонятно что делает. проверяет указатель mStackData который изменяться в Pop()

вот это условие в pop всегда невыполняется:
если читает только один поток.
а если читают несколько - то содержимое mStackData вообще трудно предсказать и что-то с ним сделать.

"В" не может вернуть h, поскольку mStackData == h, значит не может быть др. блока h

Нигде не черпал 

Пояснения (для широкого круга читателей):

- как же так, ShouldDelete проверяет mStackData которое может меняться?
ShouldDelete работает когда элемент извлечен из стека но не удален. Поэтому если нитка поменяла свой mStackData - то только на новый, который с doomedData не совпадет

- зачем нужно сравнение (mStackData != temp) ?
При выполнении mStackData = CData::mDataFirst может быть такая подлянка

1) mDataFirst принято на регистр
2) mStackData считано из регистра

Если нитка отрубилась между 1 и 2, то mDataFirst может быть изменено др. ниткой, а указатель на регистре уже удален, (ведь mStackData еще не заряжен). Тогда вылетим на temp->mNext, пресекаем это с помощью mStackData != temp. А если mDataFirst был перезаряжен (прошло ABA),то нас это устроит, mNext читаем после

Там прозрачный намек на оптимизацию (mFreeList) - вместо бестолковой беготни с custom allocator    А вообще можно использовать и обычное new/delete. Единственное что требуется - не мочить блоки для которых ShouldDelete вернула false, а добавлять их в mDoomedList и пытаться удалить на следующем заходе. В худшем случае общее число таких элементов (в mDoomedList'ах всех ниток) будет равно числу ниток.

Есть простая и очень популярная формулировка

нельзя удалить объект если хоть одна нитка его использует

И предложенная схема ей также следует. Просто обычно подразумевается что счетчик/stamp находится в самом объекте. А здесь делаем по-другому: проверяем "снапшот" каждой нитки на используемый объект. С интерфейсом проблем нет - ведь после извлечения мы работаем в рамках одной нитки. Не ожидаем же мы что данные по shared указателю будут удалены при вызове нашего деструктора.

Насколько я понял "в теории этого нет" (и значит это плохо  ). Или я ошибаюсь?

Непонятно что значит "вернуть обратно в стек". Когда Вы напр делаете push_bаck (std::vector), то контейнер копирует в себя, эти расходы можно сократить используя указатели. То же самое и здесь, дополнительных приседаний не требуется, и никаких локов это не вызывает.

Ладно, а по FIFO есть идеи?