понедельник, 25 ноября 2013 г.

[prog.multithreading] Сломавшийся тест показал на просчет в моих предположениях

Многопоточное программирование -- это сложная штука. К этому утверждению можно относиться по-разному. Можно думать, что это преувеличение. И что тщательное отношение к делу, а так же использование "правильных" инструментов (будь то Haskell, Erlang или SObjectizer) полностью снимает сложность разработки многопоточных программ. Или, напротив, можно считать, что это слишком оптимистичное отношение к проблеме и, на самом-то деле, многопоточность -- это архисложно и практически никто не может делать это правильно. Каждая точка зрения имеет право на жизнь, ибо зависит от сложности задач, условий, в которых приходится искать решение, а так же профессионального уровня и величины собственного самомнения ;) Лично я уверен в том, что многопоточность -- это сложная штука. С ней можно справится, но легкой ее уж точно называть не следует.

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

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

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

Изъятие агентов из SObjectizer проводится посредством дерегистрации кооперации. Эта операция состоит из нескольких фаз. Сначала SObjectizer помечает агентов дерегистрируемой кооперации специальным образом. Доставка новых сообщений таким агентам прекращается. Агентам дается возможность обработать те сообщения, которые уже находятся в очередях агентов. После чего каждый агент сообщает своей кооперации, что он завершил свою работу. Когда кооперация получит уведомления от всех своих агентов, она проинформирует об этом SObjectizer. После чего SObjectizer уничтожает кооперацию, а это приводит к уничтожению всех входивших в нее агентов.

В версии 5.2.3 в SObjectizer была добавлена поддержка взаимоотношений "родитель-потомок" между кооперациями. Эта функциональность была в SObjectizer-4, но в первые версии SObjectizer-5 она не попала. Сейчас пришло время ее реализовать. Реализация оказалось не сложной, была сделана за несколько дней, после чего было написано несколько unit-тестов для ее проверки. Эти unit-тесты успешно выполнялись под Win64 и MSVC++. Но два из трех тестов внезапно сломались под Linux с GCC 4.8.2, будучи запущенными под VirtualBox.

В обоих этих тестах поведение SObjectizer контролировалось следующим образом: создавались кооперации с агентами, каждая следующая кооперация была дочерней для предыдущей кооперации. Порядок их создания и уничтожения фиксировался в конструкторах и деструкторах агентов: в конструкторе агент фиксировал свой номер в последовательности инициализации, в деструкторе агент фиксировал свой номер в последовательности деинициализации. При правильной работе SObjectizer вторая последовательность должна была стать "зеркальным" отражением первой последовательности. Так и было, когда тесты запускались на реальном железе под Windows. Но последовательность деинициализации оказывалось несколько другой под виртуалкой. Т.е. под виртуальной машиной агенты уничтожались не в том порядке, что на "голом" железе.

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

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

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

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

В идеальных условиях дерегистрация выполняется следующим образом:

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

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

  • каждый агент в начале дерегистрации ставит к себе в очередь сообщение finishing_demand;
  • во время обработки finishing_demand агент сообщает кооперации, что он закончил свою работу внутри SObjectizer;
  • кооперация обнаруживает, что это ее последний агент и ставит специальную заявку нити дерегистрации коопераций;
  • после того, как заявка была передана нити дерегистрации коопераций, текущая рабочая нить была приостановлена. Это означает, что последний агент не закончил обработку finishing_demand. Это означает, что на этого агента сейчас сылаются две сущности: кооперация, которой принадлежал агент, и рабочая нить, на контексте которой работал метод агента. Т.е. счетчик ссылок на агента имеет значение 2, а не 1, как должно было бы быть в идеальном сценарии;
  • получив заявку нить дерегистрации коопераций "просыпается", выполняет окончательное вычеркивание из SObjectizer агентов кооперации, после чего уничтожает описание кооперации. Кооперация уменьшает счетчики ссылок на своих агентов. Но для одного из них этот счетчик уменьшился с 2 до 1, а сам агент остался жив;
  • через какое-то время рабочая нить "проснулась" (получила очередной квант процессорного времени от диспетчера ОС), агент завершил на ней обработку своего finishing_demand, после чего рабочая нить декрементировала счетчик ссылок на агента и агент был уничтожен.

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

Агент №5 начал обработку finishing_demand, сказал своей кооперации, что он завершил работу, кооперация поставила заявку на окончательную дерегистрацию. Тут рабочую нить прервали. В дело вступила специальная нить дерегистрации. Она выполнила завку этой кооперации. Тут же выяснилось, что можно дерегистрировать предка этой кооперации, кооперацию №4. Что и было сделано сразу же (процессорное время не было передано рабочей нити агента №5). Следом выяснилось, что можно дерегистрировать и предка предка, кооперацию №3. Что так же было сразу же проделано. А так как счетчики ссылок у агентов этих коопераций имели значение 1 (они свои finishing_demand уже обработали), то агенты №4 и №3 сразу же были уничтожены. В то время, пока агент №5 оставался живым.

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

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

Посему рекомендация: если есть возможность использовать специально предназначенные для вашей прикладной области высокоуровневые инструменты (будь то OpenMP, готовые реализации механизмов fork/join и map/reduce, или средства для работы с агентами вроде Erlang, Akka или SObjectizer), то пользуйтесь ими, не изобретайте велосипеды. Пусть шишки набивают разработчики этих инструментов: им это либо очень интересно, либо же они за это зарплату получают ;) Конечно, высокоуровневые инструменты не спасут вас от всех проблем. Но это будут уже несколько другие проблемы, более приближенные к вашей предметной области. С большой степени вероятности вам проще и приятнее будет разбираться с ними, а не с выяснением причин эпизодических дедлоков десятка вручную запущенных нитей на пятнадцати мутексах, захватываемых и освобождаемых в разных частях программы. Или, как в данном случае, разбираясь с непонятным порядком разрушения объектов (освобождения ресурсов).

PS. Речь в данном примере шла об уничтожении объектов на основе счетчика ссылок. Может показаться, что данная проблема не имеет отношения к языкам с GC. Это слишком узкая точка зрения. В языках с GC может потребоваться управление другими формами ресурсов: подключениями к БД, блоками разделяемой между процессами памяти, каналам IPC (сокетам, пайпам, мейлслотам), внешним устройствам (криптодейвайсам, кард-ридерами, ...) и т.д. Помощи от GC здесь не будет, нужно будет городить собственный огород с подсчетом ссылок или чем-то другим. Что в условиях многопоточности чревато подобным вышеописанному просчетам.

PPS. Касательно конкретно SObjectizer. Частной деталью реализации версий 5.0, 5.1 и 5.2 является то, что объект agent_coop_t может быть разрушен до уничтожения принадлежащих ему agent_t. Не исключено, что если жизнь покажет настоятельную небходимость, то в последующих версия это будет изменено. И SObjectizer будет предоставлять более строгие гарантии, в частности, разрушение agent_coop_t только после физического разрушения всех принадлежавших кооперации agent_t.

Комментариев нет: