В параллельной декларативной модели вычислений вводится формальное понятие планировщика

МЕНЮ


Главная страница
Поиск
Регистрация на сайте
Помощь проекту
Архив новостей

ТЕМЫ


Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация



RSS


RSS новости


В параллельной декларативной модели вычислений вводится формальное понятие планировщика. Однако даже строгая форма всё равно остаётся уязвимой при реализации в классической тьюринговой модели: под катом пример, как Mars Pathfinder едва не вышел из строя из-за неуловимых багов в бортовой системе, и что полезно поизучать по теме.

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

thread - "поток" или "нить"? Вечный спор, я всё же придерживаюсь "нити", потому что наиболее полезная техника параллельного программирования в декларативной модели — это использование потоков (stream; бесконечный список сообщений) для организации связи между нитями. А если thread - "поток", то сразу начнётся путаница с потоком-стримом. Более того, есть ведь ещё dataflow-переменные (ключевая фишка для управления одновременными вычислениями и их синхронизации), где dataflow переводится обычно как ещё один "поток" (данных).

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

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

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

=

4 июля 1997-го года станция Mars Pathfinder "приземлилась" на Марс, и процесс посадки американские СМИ хвалебно превозносили как "безукоризненный". Вскоре был запущен марсоход Sojourner, и начался сбор и передача на Землю большого объёма данных, включая панорамные фотографии (которые стали хитом в зародыше интернета тех лет). Однако через несколько дней на космическом аппарате начались постоянные сбои в системе, каждый из которых приводил к потере собранных данных. Журналисты комментировали это так, что "Pathfinder пытался делать сразу много дел одновременно, но не справился с нагрузкой" )))

Помните, во втором сезоне ТБВ, про марсоход и "План Б"?

=

Про технические причины багов на симпозиуме IEEE Real-Time Systems позже рассказал David Wilner (CTO Wind River Systems) — работой аппарата управляла их ОС РВ VxWorks. Ну собственно, концептуально причина была описана выше.

В Pathfinder имелась информационная шина (условная общая память, к которой обращались разные его компоненты), и работа самой шины (загрузка и выгрузка в/из неё различных структур данных от всевозможных бортовых систем) считалась в VxWorks задачей с высоким приоритетом, которая синхронизировалась с помощью классических мьютексов, подразумевающих взаимодействие с планировщиком для переключения тредов.

"Забор метеорологических данных" :) из метеоаппаратуры выполняла нить с невысоким приоритетом, потому что это требовалось делать нечасто. Она получала мьютекс, выгружала данные в шину, и освобождала мьютекс. Соответственно, если другой нити потребовались метеоданные именно в момент их выгрузки, ей приходилось ожидать разблокировки мьютекса.

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

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

=

После длительного разбирательства с копией софта станции на Земле аварийная ситуация в итоге была смоделирована. Оказалось, что мьютекс в VxWorks имеет булев параметр, который задаёт, должен ли он наследовать приоритет. Так вот, программист закодил на сишечке соответствующую логику, просто оставив дефолтное значение этого параметра (FALSE), даже не указал его явно. А если бы он был включён (TRUE), метеорологическая нить унаследовала бы приоритет высокоприоритетной нити шины данных, заблокировавшейся на ней, пока она держала мьютекс, в результате чего она стартовала бы с более высоким приоритетом, нежели коммуникационная задача со средним приоритетом, что предотвратило бы сбойную ситуацию.

VxWorks содержала интерпретатор языка Cи, позволявший вводить выражения и функции вручную и выполнять их "на лету" во время отладки системы (ну как обычный repl). По счастливой случайности (или счастливому раздолбайству?) инженеры JPL NASA отправили космический корабль с этим включённым отладочным режимом. В соответствии с проектной спецификацией, параметр инициализации (дефолтный нолик) для того мьютекса (и для двух других, которые также могли вызвать подобную ошибку) хранился в глобальной переменной, доступ к которой через некоторые манипуляции с адресами оказался возможен через интерпретатор Си. Инженерам удалось дистанционно загрузить набор команд в этот интерпретатор, перезаписать нолик на единичку, вуаля! и нити стали корректно наследовать родительский приоритет.

=

Официальные выводы комиссии были такие:

1) Диагностика этой ошибки в режиме "чёрного ящика" была невозможна. Только детальное отслеживание фактического поведения системы позволило выявить и идентифицировать ошибочный сценарий работы.

2) Cпасло ситуацию сохранение в системе режима "отладки". Без возможности модифицировать систему в полевых условиях проблема не была бы устранена.

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

Кстати, некоторые инженеры JPL позже раскололись: да, была зафиксирована пара непонятных сбросов системы во время многомесячного предполётного тестирования. Их так и не удалось ни воспроизвести, ни тем более объяснить, и поэтому инженеры, как часто бывает, решили, что эти сбросы системы, вероятно, не были особо важны, и вероятно, были вызваны аппаратным сбоем (сколько раз вы сами грешили по своим ошибкам на компилятор, или ОС, или материнку?). Они были очень плотно заняты отладкой системы посадки аппарата, поэтому до менее критичных подсистем просто руки не доходили.

=

Забавно, что во время своего выступления David Wilner упомянул классическую работу "Priority Inheritance Protocols: An Approach to Real-Time Synchronization" IEEE Transactions on Computers, 1990

https://ieeexplore.ieee.org/document/57058

и заочно похвалил её авторов L. Sha, R. Rajkumar, J. P. Lehoczky из университета Карнеги-Меллона: эта работа помогла VxWorks в целом корректно справиться с проблемой инверсии приоритетов. Так вот, оказалось, что в том зале случайно присутствовали все эти три человека! :)

=

Как понять в подобных случаях, как поступать? Ну, таких ключевых моментов не так много в параллельных вычислениях, и все они достаточно хорошо известны; вот как раз в курсе, который сейчас делаю, в параллельной декларативной модели важность наследования приоритетов нитей отмечается особо. Так совпало тоже забавно, что я добавил в курс этот момент, а через несколько дней наткнулся на историю про Mars Pathfinder.

Что поизучать?

https://habr.com/ru/post/452094/

https://habr.com/ru/post/459514/

По задумке вот неплохой учебный проект по решению задачек в параллельной модели

https://github.com/santiontanon/Parallel

Национальный научный фонд США грант на это выделил, а получилась какая-то хрень :) примитив уровня первокурсника, дизайн ужасающий ...

написано в Unity3D на C# + Java! + Python! сразу видно, учоные делали )))

А вот это очень рекомендую:

http://deadlockempire.github.io/

шикарная игра по мультитредовому (ну и в целом, одновременному) программированию, кто знаком с синтаксисом C# Java C++ ...

там небольшие задачки на 5-10 строк, но иногда надо как следует подумать. Про мьютексы есть неплохая задачка.

Один из авторов DeadlockEmpire кстати в 17 лет написал пошаговую стратегию (тогда был очень хороший игровой фреймворк XNA от Microsoft):

https://hudecekpetr.cz/sacculus-the-wargame/

И обязательно конечно вечная классика

https://store.steampowered.com/app/370360/TIS100/

=

P. S. Ещё интересный архитектурный момент: ровер Sojourner ввиду 11-минутной временной задержки между Землёй и Марсом очевидно должен быть достаточно автономным, но при этом понятно также, что и энергии, и размеров для какой-то внушительной бортовой компьютерной мощности крайне мало. Sojourner — довольно маленькое существо, и его миниатюрная солнечная батарея в пиковое время производила всего около 16 Ватт.

Так вот, управлялся он 8-разрядным процессором Intel 80C856 (военный чип в архитектуре 8080) с ОЗУ 64 Кб и частотой около 2 МГц, который был выпущен 20 (!!!) лет назад до реализации миссии на Марс. Причины такого выбора? Прежде всего радиационная стойкость, а также низкое энергопотребление и высокая надёжность, проверенная богатым опытом эксплуатации.


Источник: store.steampowered.com

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