Как построить очередь без блокировки?

Question

Я провел сегодня, изучая безблокировочные очереди. У меня есть несколько производителей, несколько потребителей ситуации. Для тестирования я реализовал систему, использующую Interlocked SList, под Win32, и она удвоила производительность моего многопоточного кода на основе задач. К сожалению, я хочу поддерживать несколько платформ. Блокировка на нескольких платформах сама по себе не является проблемой, и я могу с уверенностью предположить, что могу блокировать без проблем. Однако фактическая реализация теряет меня.

Большая проблема заключается в том, что вам нужно гарантировать, что push / pop для списка будет использовать только один блокированный вызов. В противном случае вы оставляете место для другой нити, чтобы затянуть и облажаться. Я не уверен, как реализация Microsoft работает скрытно, и хотел бы узнать больше.

Может кто-нибудь указать мне на полезную информацию (платформа и язык довольно не имеют значения)?

Кроме того, я хотел бы знать, возможно ли реализовать вектор без блокировки. Это было бы очень полезно для меня :) Ура!

Редактировать: Прочитав статью DDJ от травы, я вижу уменьшенную очередь блокировок, которая очень похожа на ту, что у меня уже была. Тем не менее, я заметил, что в конце есть бумаги, которые могут создать настоящую очередь без блокировки, используя операцию двойного сравнения и обмена (DCAS). Кто-нибудь реализовал очередь, используя cmpxchg8b (или cmpxchg16b в этом отношении)?

Я просто размышляю об этом (не читая статьи), но вы можете использовать эту систему для одновременного обновления указателя головы и хвоста и, таким образом, избежать проблем с другим потоком, попадающим между двумя атомарными операциями. Однако вам все еще нужно получить следующий указатель головы, чтобы проверить его относительно указателя хвоста, чтобы увидеть, изменили ли вы только что хвост. Как избежать того, чтобы другой поток изменял эту информацию, пока другой поток готовится сделать это сам? Как именно это реализовано без блокировки? Или мне лучше читать неразборчивость, которая является исследовательской работой? ;)

Answer 1

Возможно, вы могли бы реализовать очередь ограниченного размера с наименьшими трудностями ... Я думал об этом в последнее время и придумал этот дизайн, но вы, вероятно, можете найти много других интересных идей: (ВНИМАНИЕ: у него могут быть некоторые проблемы! )

• очередь представляет собой массив указателей на элементы
• вы должны управлять 2 указателями (голова, хвост), которые работают над очередью так же, как циклический буфер
• если head == tail, товаров нет
• если вы хотите enqueue(ptr), Interlocked-Swap tail с NULL (prev_tail - это поменяемое значение)
  • если prev_tail == NULL, попробуйте еще раз
  • если prev_tail + 1 (с переносом) == head, ваша очередь заполнена
  • в противном случае введите ptr в *prev_tail и присвойте prev_tail+1 tail (не обращайте внимания на обход буфера)
• для dequeue() сделайте копию tmp_head = head и проверьте tmp_head == tail
  • если это правда, вернуть, потому что очередь пуста
  • если это неверно
    • сохранить *tmp_head как ptr
    • сделать CAS: сравнить head с tmp_head swap head с head+1
    • если сбой CAS - запустить всю функцию свыше
    • если получилось - верните ptr

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

Очереди неограниченного размера "немного" сложнее;) Но вы должны быть в состоянии создать достаточно большую очередь для большинства нужд.

Answer 2

Возможно, вы захотите взглянуть на реализацию Хербом Саттерсом очереди с низким уровнем блокировки.

http://www.drdobbs.com/hpc-high-performance-computing/211601363

Он использует атомарность c ++ 0x, но это было бы (должно быть) легко реализовать с вашими атомарными операциями вашей конкретной архитектуры (__sync_ * с использованием GNU, atomic_ * на солярисе и т. Д.).

Answer 3

Я думаю, что есть несколько интересных дискуссий на эту тему здесь , в частности этой темы.

Answer 4

Эти ребята, может быть, вы могли бы найти там вдохновение. Другие интересные файлы - yqueue.hpp и atomic_ptr.hpp

Answer 5

Решение viraptor является блокировкой, я не знаю ни о каких согласованиях очереди без блокировки с несколькими производителями / несколькими потребителями.