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

Question

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

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

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

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

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

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

Answer 1

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

• очередь представляет собой массив указателей на элементы
• Вы должны управлять 2 указателями (голова, хвост), которые работают над очередью так же, как циклический буфер
• если head == tailнет товаров
• если хотите enqueue(ptr), Блокировка-своп 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 своп head с head+1
    • если произошел сбой CAS - запустите всю функцию заново
    • если получилось - вернись ptr

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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