Шаблон проектирования Producer-Consumer

Шаблон проектирования producer-consumer, предыстория

Год тому назад, когда я учился на 3-ем курсе университета, у нас появился предмет, который вел “big-boss” одной из местных фирм, занимающихся разработкой программного обеспечения. Этот предмет назывался “Операционные системы”, а речь на нем шла о современном строении, функционировании компьютерных систем в общем. На практических занятиях требовалось реализовать простую задачу: подобрать пароль по хэшу, зашифрованному стандартной функцией crypt() из POSIX. Написав простую программу, вы получите новое задание - реализовать это многопоточно, а потом опять новое - реализовать распределенно и так далее.

Но мы остановимся на многопоточном решении этой задачи, и на примере ее разберем тему нашего разговора - шаблон проектирования “producer-consumer”. Я замечу, что для чтения требуется понимание основ и базовых приемов параллельного программирования, например, нужно знать, что такое синхронизация потоков, мьютексы, семафоры, а также понимать типичные ошибки в проектировании решения параллельных задач.

Анатомия нашего шаблона

Шаблон “producer-consumer” устроен по следующей схеме:

Producer (изготовитель) - это некоторый поток, который генерирует “задания” и складывает их в очередь Queue.

Consumer (исполнитель) - это поток, который берет задания из очереди, выполняет и отправляет результаты туда, куда нужно.

Очередь Queue - это ограниченный буфер заданий с заранее заданной вместимостью.

В общем случае, как “продюсеров”, так и “консьюмеров” может быть много, но важно соблюдать баланс, чтобы рационально расходовать ресурсы. Идеальный режим функционирования очереди достигается, когда задания по ней движутся непрерывно, то есть скорость добавления заданий равно скорости, с которой “консьюмеры” их выполняют, а иначе часть потоков ожидает пока остальные сделают свою часть работы.

Применение шаблона в нашей задаче

Самое простое решение будет перебирать все строки длиной не более L, с буквами из определенного алфавита (например, большие и маленькие латинские буквы и цифры) вызывать функцию crypt(), и полученный хэш сравнивать с исходным.

Можно легко протестировать и понять, что самая ресурсоемкая часть программы - это вызов функции crypt() для всех перебранных строк, в то время как сам перебор работает 1-2 процента от общего времени исполнения. Понятно, что нужно параллелить именно эту часть программы.

Основные части шаблона в нашей задаче устроены следующим образом:

task = (s, len), где s - это строка длиной len.

queue = (data[], head, tail, mutex). Задания хранятся в массиве data[], используются указатели head и tail для работы с очередью, а также обязательно нужен mutex, чтобы обеспечить синхронизацию потоков, работающих с очередью.

result = (found, s, mutex), где found - булева переменная, указывающая найден уже ответ или нет.

 

Схема:

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

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

Вариант второй, улучшенный. теперь задание - это строка, которую перебрали “наполовину”, то есть task = (s, len, l, r), l и r означают, что консьюмер должен еще перебрать кусок строки с l по r, а только потом проверять хэш. В данной задаче, подобная идея - это основа оптимального решения, нужно лишь подобрать пропорцию, в которой продюсер и консьюмер делят процесс перебора строк.

Зачем это все нужно

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

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

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

Зачем я написал эту статью в рамках конкурса Aceller8? Как знать... :)

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