Управление памятью в очереди без блокировок

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

Например, производитель выглядит так:

queue.Add( new WorkUnit(...) );

А потребитель выглядит так:

WorkUnit* unit = queue.RemoveFront();
unit->Execute();
delete unit;

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

На данный момент я думаю, что у нас есть следующие варианты:

  • Реализуйте свободный от блокировок пул памяти.
  • Выгрузите пул памяти и положитесь на поточно-безопасный распределитель.

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

Спасибо.


c++ lock-free
person lhumongous    schedule 23.06.2011    source источник
comment
Это меняет вашу семантику, но вы можете попробовать поставить в очередь объекты вместо указателей.   -  person Robᵩ    schedule 24.06.2011

Ответы (5)


arrow_upward
4
arrow_downward

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

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

person Stas    schedule 23.06.2011
comment
Как ясно показывает продолжение Херба Саттера, в этой статье так много ошибок параллелизма, что это даже не смешно; drdobbs.com/cpp/210600279 - person Aaron Klotz; 24.06.2011
comment
@ Аарон Клотц: Хм. Эта статья - просто иллюстрация блестящего решения проблемы памяти. Вопрос был именно об этом. Конечно, мы должны использовать атомарные итераторы (насколько я помню, он использует собственную реализацию списка в исходном коде, приложенном к статье) и барьеры памяти, чтобы избежать переупорядочения. Я согласен, это непростая тема, но с хорошо известными проблемами, с которыми нужно столкнуться при реализации lock-free вещей. - person Stas; 24.06.2011
comment
Несмотря на то, что исходная статья содержит ошибки, продолжение и последующая реализация Саттера действительно иллюстрируют то, что я ищу. Я изучу это еще немного. - person lhumongous; 25.06.2011

arrow_upward
1
arrow_downward

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

Это оставляет вам управление функцией блокировки, чтобы освободить блок. К счастью, этим довольно легко управлять: вы ведете связанный список свободных блоков для каждой кучи. Вы помещаете собственный адрес блока в (память, которую вы будете использовать как) поле ссылки для связанного списка, а затем выполняете атомарный обмен с указателем, содержащим заголовок связанного списка.

person Jerry Coffin    schedule 23.06.2011

arrow_upward
0
arrow_downward

Вы должны посмотреть на TBB от Intel. Я не знаю, сколько это стоит для коммерческих проектов, но у них уже есть параллельные очереди, параллельные распределители памяти и тому подобное.

Ваш интерфейс очереди также выглядит серьезно изворотливым - например, ваш вызов RemoveFront () - что, если очередь пуста? Вызовы new и delete также выглядят довольно избыточными. TBB от Intel и PPL от Microsoft (включенный в VS2010) не страдают от этих проблем.

person Puppy    schedule 23.06.2011
comment
это не настоящий код, он просто предназначен для иллюстрации того, как работает распределение памяти. TBB и PPL не являются допустимыми вариантами. Мы застряли здесь, придумывая домашнее решение. - person lhumongous; 24.06.2011

arrow_upward
0
arrow_downward

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

  • создать элемент списка
  • добавить данные в элемент списка
  • изменить указатель следующего элемента с нуля на элемент списка (или эквивалент на других языках)

Потребитель может быть реализован любым способом, и большинство связанных списков по умолчанию безопасны для такого рода операций (но проверьте эту реализацию)

В этом сценарии потребитель должен освободить эту память, или он может вернуть ее таким же образом обратно в производитель, установив предопределенный флаг. Производителю не нужно проверять все флаги (если их больше 1000), чтобы определить, какая корзина свободна, но эти флаги могут быть реализованы как дерево, позволяя log (n) искать доступный пул. Я уверен, что это можно сделать за O (1) раз без блокировки, но понятия не имею, как

person Luka Rahne    schedule 23.06.2011

arrow_upward
0
arrow_downward

У меня была такая же проблема, поэтому я написал свою собственную очередь без блокировок (с одним производителем, с одним потребителем), которая управляет выделением памяти для вас (она выделяет серию смежных блоков, вроде как std::vector).

Недавно я опубликовал код на GitHub. (Кроме того, я писал в своем блоге о Это.)

Если вы создаете узел в стеке, ставите его в очередь, а затем выводите из очереди на другой узел в стеке, вам вообще не нужно будет использовать указатели / ручное выделение. Кроме того, если ваш узел реализует семантику перемещения для построения и назначения, он будет автоматически перемещен, а не скопирован :-)

person Cameron    schedule 08.02.2013