Рандеву – концепция параллельного программирования

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

Коль скоро рандеву – это основная концепция организации межпроцессного взаимодействия в языке Ada, то в поисках ответ о том, что такое рандеву, я решил обратиться, что называется, к первоисточникам. В ru-нете есть сайт по языку Ada, где я обнаружил книгу, в которой излагается суть механизма рандеву и принципы его описания в языке. Книга называется «Адское программирование» и в «главе 15: Многозадачность» описывается идея рандеву. Процитирую ту часть, в которой описывается суть термина, а за подробностями и разъяснениями предлагаю обратиться к самой книге.

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

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

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

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

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

В следующий раз расскажу о том, как я, пытаясь реализовать взаимодействие между потоками в ядре библиотеки act-o, естественным путем пришел к точно такой же идее взаимодействия как рандеву, еще до того, как познакомился с вышеизложенным материалом.
Оставайтесь на связи… :-)

И все-таки она необходима

Стоило только мне вынести предыдущую заметку на один форум, как оказалось, что:

1. Сборка мусора необходима не только в многопоточных программах, но и в компонентном программировании.
   
2. Существует статья, в которой предпринята попытка доказать необходимость автоматического управления памятью в компонентных программах.

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

Необходимость «сборки мусора» в многопоточных программах

Те из вас, кто следит за событиями в мире языков программирования, наверное, неоднократно сталкивались с заявлениями, что мы стоим на пороге новой революции, и имя этой революции – параллельность. Началась она несколько лет назад, но сейчас, когда 2-х и 4-х ядерные процессоры доступны любому в ближайшем магазине, она стала актуальна. И дело конечно не в том, что такие процессоры существуют, а в том, что, если мы хотим и дальше получать все большую производительность от наших компьютеров, нам необходимо использовать эти ядра, так как мощность одного ядра достигла некоторого придела. Тем же, кто еще только начинает знакомиться с этой темой, я бы предложил начать с хорошей и очень известной статьи Герба Шаттера (Herb Sutter) «The Free Lunch Is Over».

Многоядерные процессоры стали реальностью, и сбежать от них нам не удастся, но легко сказать: «Необходимо использовать имеющиеся ядра», – гораздо сложнее сказать, как именно это сделать. Большинство сходятся во мнении, что для этого необходим новый язык программирования. Возможно, что такой язык уже есть, возможно, его еще предстоит создать, но одно известно точно – в коммерческом программировании (mainstream) его еще не используют. Не буду сейчас пытаться анализировать этот язык вообще, а акцентирую внимание только на одной характеристики нового языка, без которой, на мой взгляд, невозможно качественное создание программ с множественным параллелизмом.

Разрабатывая библиотеку act-o и ее продолжение, я все время сталкиваюсь с ситуацией, когда мне необходимо удалить объект, но в многопоточном приложении неизвестно работают ли другие потоки с этим объектом, или с объектами, на которые он ссылается, или которые ссылаются на него. В текущей публичной версии библиотеки act-o есть такой пример:

// Создать актера
act_o::actor_t wall = act_o::instance_t <> ( act_o::aoExclusive );
// Начать игру: инициализировать объект, запустить мячи
wall.send( msg_start( BALLS, console ) );
// Остановить игру
wall.send( msg_finish() );
// Уничтожить объект
act_o::destroy( wall );

В первой строке кода происходит создание объекта класса Wall, который является актером. Однако в программе программист оперирует не указателями на объект класса Wall, а специальным объектом-оберткой класса act_o::actor_t (в контексте данной заметки я буду называть такой объект «ссылкой»). Объект-ссылка сделан для того, чтобы управлять указателем на объект класса Wall (в данном случае).

Зачем мне понадобилось использовать объекты, управляющие указателями? Помимо очевидной защиты от утечки памяти, есть и более серьезное основание для этого. Связано оно с тем, что в программе можно не только оперировать ссылкой на актера, созданного в текущем блоке, но и передать ее другому актеру в качестве параметра сообщения. Я уже писал об этом в своей предыдущей заметке «О моделях актеров», где излагал суть модели:

Получатель сообщения определяется только по адресу. Иногда такой адрес называется «почтовый адрес». Таким образом, актер может взаимодействовать только с теми актерами, адреса которых ему известны. Сам же актер может получить адреса других только из пришедших сообщений, также он по определению знает адреса тех актеров, которые были созданы им самим.

В данном случае адреса – это ссылки, которые в библиотеке act-o представлены классом act_o::actor_t. В приведенной цитате видно, что ссылки на данного актера теоретически могут находиться где угодно: у других актеров, в очереди сообщений. И возникает вопрос: можно ли в асинхронной многопоточной модели синхронизировать состояние всех объектов так, чтобы некоторый объект мог удалить другой объект, будучи уверенный, что на удаляемый объект более нет ссылок? Нужно ли это делать, ведь подобная синхронизация замедляет работу всей системы?

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

Но допустим, что многопоточность в языке организована не на основе асинхронного обмена сообщениями, а на основе синхронного взаимодействия. Необходимо ли системе и тогда использовать алгоритмы отслеживания ссылок? По моему мнению – да. Ведь если требуется явно удалить объект в указанной точке, необходимо гарантировать, что удаляемый объект не будет в этот момент взаимодействовать с какими-либо другими. В многопоточной среде для этого необходимо использовать синхронизацию и удаляющий процесс должен ждать, когда удаляемый объект завершит все взаимодействия. К чему могут привести подобные ожидания? Допустим, что удаляемый объект a взаимодействует с некоторым объектом b, который взаимодействует с удаляющим объектом c. Так как приложение многопоточное, то существует вероятность того, что c начнет удалять a тогда, когда a уже соединился с b, но b еще не обратился к c. Объект b не может взаимодействовать с c, так как c ждет а и именно поэтому объект c не может перейти в необходимое состояние для взаимодействия с объектом b. Классический пример взаимной блокировки… Конечно удаление объектов – это не единственный случай, где может произойти взаимоблокировка при синхронизации, но если благодаря автоматическому слежению за ссылками на объекты можно избежать некоторого количества подобных ситуаций, то не лучше ли так и поступить?

Исторически так сложилось, что механизм отслеживания ссылок (автоматического управления памятью) называется «Garbage collection» (сборка мусора). Из-за этого даже разгораются споры относительно того, что если программа написана правильно, то ей нет необходимости использовать «сборку мусора» так как этого самого «мусора» не должно оставаться. Но сейчас другая ситуация – «сборка мусора» не просто удобный механизм, который облегчает создание программ, или позволяет избежать некоторых ошибок – этот механизм просто необходим для возможности написания многопоточных программ.

Остался только один вопрос. Почему я, столько говоря об автоматическом отслеживании ссылок на объект, в последней строке кода явно вызываю функцию удаления объекта, ведь в соответствии с правилами C++ для объекта wall будет вызван деструктор при выходе из текущего блока? С одной стороны это связано с тем, что сам C++ не предоставляет встроенных алгоритмов сборки мусора, а с другой – в текущей реализации библиотеки act-o используется алгоритм подсчета ссылок, который не может определять циклы в графе зависимости. В настоящее время я исследую вопрос о возможности улучшить этот алгоритм, либо заменить его каким-либо альтернативным алгоритмом управления памятью.