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

Те из вас, кто следит за событиями в мире языков программирования, наверное, неоднократно сталкивались с заявлениями, что мы стоим на пороге новой революции, и имя этой революции – параллельность. Началась она несколько лет назад, но сейчас, когда 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 используется алгоритм подсчета ссылок, который не может определять циклы в графе зависимости. В настоящее время я исследую вопрос о возможности улучшить этот алгоритм, либо заменить его каким-либо альтернативным алгоритмом управления памятью.

О моделях актеров

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


Модель актеров

Впервые модель актеров была предложена в работе «A Universal Modular ACTOR Formalism for Artificial Intelligence» тремя соавторами – Carl Hewitt, Peter Bishop, and Richard Steiger в 1973 году.

Модель актеров следует философии, что все есть актеры. Это очень близко к идее Smalltalk и других объектно-ориентированных (ОО) языков, что все есть объекты. Однако, в то время как, программы на большинстве ОО языках выполняются последовательно, в модели актеров все выполняется полностью параллельно.

Актер – это вычислительная единица, которая в ответ на принятое сообщение может сделать следующее:

• послать ограниченное количество сообщений другим актерам;
  
• создать ограниченное количество новых актеров;
• изменить способ реакции на последующие обрабатываемые сообщения.

Актер не должен делать никаких предположений относительно того, в какой последовательности поступают сообщения от других актеров.

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

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

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


Распределенная модель актеров (модель активных устройств)

С физической точки зрения распределенную сеть образуют устройства – персональные компьютеры, КПК, смартфоны, датчики, сенсоры и т.д. и т.п. Однако чтобы эти устройства могли взаимодействовать, необходимо ввести некоторую логическую модель. Назовем каждое устройство – узлом сети. В свою очередь каждый узел представляется единичным актером. Если одно устройство выставляет в сеть два и более актера, то оно считается за два и более узла соответственно. Важное ограничение для этого – внутреннее состояние одного актера никак не должно сказываться на внутреннем состоянии другого. Иначе это нарушит модель и приведет к труднопрогнозируемым побочным эффектам, так как модель постулирует, что влияние одного актера на другой может осуществляться только с помощью посылки сообщений. Конечно, никакими средствами из внешней среды невозможно гарантировать, что устройство предоставит два абсолютно независимых актера, но оно должно придерживаться данного правила, если необходима корректная работа всей системы.

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

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

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

Классическое ООП моделировало объекты реального мира внутри программы, сейчас же стоит задача взаимодействие программы (актера) с объектами реального мира. Но не просто одиночного взаимодействия, а организации и управления множеством объектов реального мира – экосистемами актеров.

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

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


Локальная модель

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

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

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

Хочу подчеркнуть, что библиотека act-o реализует именно локальную модель актеров.


Направления исследований

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

• Распределенная модель множества взаимодействующих актеров. Имеются в виду классы системы, где взаимодействующие элементы могут быть как независимыми, так и группироваться в кластеры, для осуществления общего и согласованного функционирования экосистемы этих элементов.
• Распределенная модель взаимодействия на основе сообщений. Построение вычислительных алгоритмов на основе асинхронной недетерминированной модели обмена сообщениями. Также необходимо определить границы применимости этой модели и альтернативы для организации распределенных вычислений.
• Языки описания взаимодействия актеров. Очень большая область, которая включает в себя языки описания локальных актеров, языки описания распределенных экосистем устройств, языки описания распределенных алгоритмов, а также языки описания взаимодействия всех этих актеров и экосистем как единого целого.
• Самоорганизация и централизованное управление. Модели организации экосистемы устройств. Самоорганизующиеся модели актеров, модели с централизованным, управлением, и их смеси.

Оставайтесь на связи... :-)

«The act-o Library»

Это мой первый пост, и я рад, что это связанно с очень хорошей новостью. Мой проект «The act-o Library» наконец-то увидел свет. Сегодня я загрузил ее по адресу официального размещения http://sourceforge.net/projects/act-o Там же будут появляться и все последующие релизы пакетов.

«The act-o Library» или просто act-o – это библиотека классов на языке C++ и для программистов на языке C++, которая призвана помочь им в нелегком труде создания многопоточных приложений, с целью максимально задействовать потенциал современных многоядерных процессоров. В основу библиотеки положена модель актеров. Так как в ядро не закладывался функционал взаимодействия актеров на разных компьютерах или в разных процессах, то нет ни работы с сокетами, ни сериализации ни других подобных вещей. Поэтому, все получилось очезнь просто, компактно и быстро. А главное надежно, гарантированно и типобезопасно…

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

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