Сразу хочу оговориться, что в этой заметке я не ставлю себе цель рассказать, о всевозможных реализациях lock-free очереди, а только об одном способе, который я использовал в ядре библиотеки acto.
MPSC (multiple producers single consumer, «много производителей один потребитель») — модель взаимодействия в многопоточной среде, когда одновременно произвольное количество потоков могут добавлять элементы в очередь (или другую структуру), но только один поток может извлекать их.
Постановка задачи
Реализация
Во-первых, стоит сказать, что реализация 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 — локальный стек, то только один поток имеет к нему доступ и для него нет необходимости использовать какие либо блокировки вообще.
Итоги
На основе теста 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»
