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

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

Что такое Inversion of Control?

Согласно этимологической справке, данной Мартином Фаулером, термин Inversion of Control (IoC) впервые был употреблен в статье Ральфа Джонсона и Брайана Фута «Designing reusable classes» в 1988 году. К сожалению, ни Фаулер, ни авторы упомянутой статьи не дают строгого определения этого термина, а предлагают его выводить из описания различия между такими понятиями как «библиотека» и «фреймворк». Вот что пишет Фаулер:

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

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

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

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

Формальное определение IoC

Условия: Даны две сущности A и B, такие, что A зависит от B, но B не зависит от A. Такая зависимость означает, что сущность B может быть использована независимо от A, но A не может быть использована независимо от B. Рассматриваемыми сущностями могут быть классы, модули, библиотеки и любые другие программные сущности, которые экспортирую некоторое множество функций. Назовем экспортируемые множества функций Fa и Fb соответственно.

Определение IoC: Для данных в условии сущностей A и B, определяющих программу, существует обратный поток управления, если для некоторого набора входных параметров выполняются следующие условия.

1. Выполнение программы начинается с некоторой функции x принадлежащей Fa .
2. Существуют функции x и z принадл. Fa и некоторая функция y принадл. Fb, такие, что вызов функции x ведет к вызову функции y, которая, в свою очередь, вызывает функцию z. При этом функции x и z могут быть одной и той же функцией.

Пояснения и следствия

Необходимым условием наличия IoC является односторонняя зависимость сущности A от B, и соответственно множества функций Fa от Fb. Ведь только при наличии такой зависимости невозможен явный (прямой) вызов функции z принадл. Fa из функции y принадл. Fb. А так как прямой вызов невозможен, то такой вызов возможно осуществить только косвенно, каким-то образом передав адрес функции z в функцию y.

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

Также не в каждом множестве функций может возникнуть ситуация обратной передачи управления. Рассмотрим полное множество Fb из определения, состоящее более чем из одной функции. И хотя возможен случай, когда данное множество возможно разделить на несколько непересекающихся подмножеств с односторонней зависимостью, я утверждаю, что ни одна – ни прямая, ни косвенная последовательность вызова этих функций не образует IoC. Так как множество функций заранее известно, то все косвенные вызовы всегда можно переписать в прямые. И только тогда, когда сущность B описывается так, что впоследствии ее может использовать некоторая сущность А, то невозможно переписать все косвенные вызовы в прямые, так как множество функций Fa в момент создания сущности B может быть неизвестно.

Невозможно также пройти стороной следующие два вопроса. А что, если множество Fb будет сконфигурировано так, что y будет вызывать не функцию z принадл. Fa, а некую функцию v принадл. Fb, либо w принадл. Fc? Можно ли такую ситуацию тоже назвать Inversion of Control? Я считаю, что если так поступить, то мы опять вернемся к тому, с чего начали – с вопроса о том, чем IoC отличается от косвенного вызова. Чтобы этого не произошло, будем считать, что IoC – это только такая ситуация, когда управление переходит в то множество, из которого был первоначальный вызов.

И так, можно говорить, что IoC образуется при связывании двух непересекающихся множеств функций Fa и Fb таким образом, что выполнение начинается с некоторой функции x принадл. Fa, передается в функцию y принадл. Fb из которой потом возвращается обратно в функцию z принадл. Fa. Реализуется посредством косвенного вызова или позднего связывания. При этом множество функций Fb специально реализовано так, чтобы быть впоследствии связанно с некоторым другим множеством функций.

В заключении хочу отметить, что согласно данному мной определению, такая стандартная и всем известная С-шная функция, как qsort реализована в полном соответствии с принципом Inversion of Control.