Циркулярный буфер Vs.Блокировка свободного стека для реализации свободного списка

Question

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

поток запрашивает единицу ресурса из пула памяти, обрабатывает ее и отправляет указатель наэти данные в другой поток для дальнейшей работы с использованием кольцевого буфера (случай 1R / 1W).

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

Интересно, будет ли лучше - с точки зрения производительности - реализовать этот "Freelist" в качестве другого циклического буфера - хранящего адреса свободных ресурсов - или выбрать способ стека без блокировки (реализация DCAS на x86-64).

В общем, каковы могут быть плюсы и минусы двух разных подходов?

Answer 1

Основное отличие заключается в том, что кольцевой буфер будет ограничен, а стек - нет.

Трудно оценить производительность таких вещей без тестирования.С одной стороны, кольцевой буфер поддерживается непрерывным массивом.Если индексы чтения и записи остаются «рядом» друг с другом, каждый поток будет постоянно делать недействительной строку общего кэша.

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

Я полагаю, что лучший выбор зависит от рабочей нагрузки.

Answer 2

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

С одним считывателем и одним записывающим устройством без блокировок и без ожидания кольцевой буфер FIFO является тривиальным для реализации.

Я слышал, что стек LIFO также можно сделать без ожидания, но не так уверен насчет списка FIFO.И похоже, что здесь нужна очередь, а не стек.