Как создать незанятую очередь?

Question

Я провел сегодня, глядя в беззаботные очереди. У меня многократная продюсерская ситуация с несколькими потребителями. Я применил для тестирования систему, использующую функцию блокировки 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 = голова и проверить tmp_head == tail
  • , если это правда, потому что возвращение очереди пусто
  • , если оно ложно
    • сохранить *tmp_head в ptr
    • сделать CAS: сравнить head с tmp_head своп head с head+1
    • если CAS не удалось - начать все функции над
    • если это удалось - Возврат ptr

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

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

Answer 2

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

Answer 3

Я думаю, что есть какая-то интересная дискуссия на эту тему here, особенно this thread.

Answer 4

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

Answer 5

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

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

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