Lock-free queue в модели MPSC

Сразу хочу оговориться, что в этой заметке я не ставлю себе цель рассказать, о всевозможных реализациях lock-free очереди, а только об одном способе, который я использовал в ядре библиотеки acto.

MPSC (multiple producers single consumer, «много производителей один потребитель») — модель взаимодействия в многопоточной среде, когда одновременно произвольное количество потоков могут добавлять элементы в очередь (или другую структуру), но только один поток может извлекать их.

Постановка задачи

Создать структуру данных, которая бы обеспечивала механизм FIFO (очередь) для MPSC модели взаимодействия потоков без использования блокировок. Существенное требование — реализация должна быть максимально проста и понятна.

Реализация

Во-первых, стоит сказать, что реализация lock-free очереди в общем виде ведет к необходимости решить так называемую ABA-проблему. Существуют различные способы решения данной проблемы, но следует признать, что для человека непосвященного они не являются ни простыми, ни понятными, поэтому мне хотелось найти другой способ, тем более что мне не требовалось обобщенную очередь, а достаточно, чтобы она работала в MPSC модели. Поэтому я стал искать другой способ, и нашёл, что с помощью двух стеков можно получить именно то, что требуется. Тем более, что в библиотеке acto уже была реализация lock-free стека пригодного для использования в модели MPSC.

Рассмотрим как использовать пару стеков, чтобы эмулировать поведение очереди. Допустим имеется два стека S1 и S2. Возьмем последовательность чисел A1 = [1, 2, 3, 4], помещая их в стек S1, а потом извлекая из него получим новую последовательность A2 = [4, 3, 2, 1]. Однако, если поместить A2 в стек S2 и затем извлечь её из него, то получим новую последовательность A3 = [1, 2, 3, 4]. Видно, что A3 == A1.

Нужно обратить внимание, что в реальном приложении после того, как цепочка элементов A2 будет помещена в S2 в стек S1 может прийти новая цепочка элементов B1 = [5, 6, 7]. Поэтому необходимо определить очередность добавления и извлечения элементов из обоих стеков. Очевидно, что если вынуть B1 из первого стека и добавить во второй до извлечения A2, то состояние второго стека будет следующим: S2 = [top: 5, 6, 7, 1, 2, 3, 4] и извлекая из него присутствующие элементы мы не получим исходного порядка поступления элементов. Поэтому, чтобы сохранить правильный порядок элементов необходимо всегда извлекать из S2 все элементы, прежде чем добавить новые.

Теперь рассмотрим особенности реализации стеков S1 и S2. Напомню, что в MPSC только один поток извлекает данные из стека, поэтому распределим обязанности между S1 и S2 следующим образом: S1 — разделяемый между потоками стек, использующий механизм lock-free, а S2 — локальный стек, в который будут складываться элементы, извлеченные из первого. Стоит обратить внимание, что извлечение элементов из S1 не обязательно делать по одиночке, а можно сразу же извлекать всю накопившуюся цепочку, что значительно уменьшает количество операций с разделяемой структурой данных. Так как S2 — локальный стек, то только один поток имеет к нему доступ и для него нет необходимости использовать какие либо блокировки вообще.

Итоги

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

На основе теста ping-pong в старой реализации (с использованием мьютекса для синхронизации доступа к очереди) средняя производительность была на уровне 730 тыс. сообщений в секунду (Intel Core2Duo, 4Gb RAM Windows Vista 32-bit). После того, как индивидуальная очередь сообщений объекта была переведена но lock-free реализацию производительность увеличилась до 830 тыс. сообщений в среднем. В относительных цифрах это соответствует увеличению производительности на 12%.

Однако стоит отметить, что возможна ситуация, когда данный алгоритм может оказаться медленее, чем обычный алгоритм очереди с блокировкой. Дело в том, что перекладывание элементов из S1 в S2 требует O(n) операций, где n – количество элементов в S1.

Для того, чтобы ознакомиться с исходным кодом, реализующим вышеописанный алгоритм, вы можете скачать последнюю версию библиотеки acto, но если вы читаете этот текст, когда с момента публикации прошло достаточно много времени, вам стоит обратиться к svn-репозиторию и посмотреть реализацию версии 0.2.7, которую можно найти в каталоге «tags/0.2.7»

Новая версия библиотеки acto

Давно я ничего не писал, но это не означает что всё остановилось. Вчера я выложил новую версию библиотеки acto.

Основное нововведение в данном релизе — возможность собирать библиотеку под GNU/Linux. Протестировано на Ubuntu 8.04 (32-bit) и Ubuntu 9.04 (64-bit). Также есть некоторые нововведения в функциональности.

• Когда это логически целесообразно, актер может самостоятельно завершить свою работу, вызвав метод this->terminate(), в процессе обработки поступившего сообщения. Также, хочу напомнить, что имеется функция acto::destroy(actor_ref), которая позволяет принудительно завершить работу любого актера, если у вас есть действительная ссылка на него.

• В дополнение к двум вышеприведённым функция завершения работы актера, появился функция ожидания завершения работы актера acto::join(actor_ref). Её целесообразно использовать в рамках основного потока выполнения программы. Пример использования можно посмотреть в проекте ping-pong.

• Возможность привязывать обработку сообщений актера к текущему системному потоку. Например, к главному потоку выполнения программы. Для этого необходимо указать специальный флаг во время создания актера — acto::instance_t(acto::aoBindToThread). При этом сообщения будут обрабатываться в рамках того потока, в котором актер был создан, и только при вызове функции acto::process_messages().

• Для ускорения процесса пересылки сообщений появилась возможность создавать объекты-классы сообщений, например — acto::message_class_t msg_ball_class; Дело в том, что в текущей реализации при каждом вызове функции send(msg_ball()) происходит обращение к глобальному словарю, чтобы по типу сообщения получить уникальный идентификатор. Объект-класс запоминает данный идентификатор однократно, и в дальнейшем позволяет получать его без обращения к глобальному словарю. Для этого вызов метода send должен быть сделан следующим образом send(msg_ball_class.create()).

Вроде ничего существенного не забыто. Оставайтесь на связи.