Технология программирования встроенных систем реального времени

Понятие встроенной системы

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

Многие авторы относят создание встроенных систем к числу самых трудных задач; в каком-то смысле, здесь сконцентрированы практически все проблемы системного программирования.

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

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

Компактность. Оптимизировать нужно не только время исполнения, но и объем используемой памяти. Например, в современных автомобилях карбюратором управляет микроЭВМ, в которой никакой внешней памяти нет. Если программа и данные превысят наличную память микроЭВМ на 1 байт, то нужно будет переделывать всю систему. В обычных программных системах скорость счета обычно "разменивают" на больший объем памяти, здесь же такие приемы не проходят.

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

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

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

Инструментальная и целевая ЭВМ

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

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

Будем действовать следующим образом.

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

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

Самую сложную, на моей памяти, схему отладки мы реализовали для военных заказчиков, которым нужно было разработать сложное ПО на Алголе 68 для управляющего вычислительного комплекса (УВК) "Самсон". В качестве инструментальной ЭВМ мы использовали ПЭВМ.

Сначала все программы транслировались в коды ПЭВМ и проверялись на имитационных моделях. Так была проверена правильность основных алгоритмов. Естественно, мы не могли проверить реактивность и другие временные параметры.

Затем все программы были оттранслированы кросс-транслятором в коды "Самсона" и были еще раз проверены на ПЭВМ, но с использованием интерпретатора системы команд УВК "Cамсон". Так мы получили размеры реальных объектных кодов, проверили правильность адресации и смогли подсчитать время исполнения всех фрагментов программы, не зависящих от внешних сигналов.

Наконец, на стенде, в котором несколько ПЭВМ и один "Самсон" были связаны в локальную сеть, мы получили возможность запускать программы непосредственно на "Самсоне", но с полным контролем со стороны ПЭВМ (остановка по команде, по адресу чтения и т.п.) "Самсон" в то время был всего один (это обычная ситуация, когда ПО и оборудование разрабатываются одновременно), а разработчиков – много; при этом каждый из них мог запускать программы со своего рабочего места.

Такая "трехступенчатая" схема отладки помогла разработать чрезвычайно важное ПО.

Комплекс вычислительных средств

Крупные встроенные системы реального времени обычно управляются не одним, а несколькими компьютерами, связанными сетью передачи данных. Если все компьютеры и их операционные системы одинаковы, сеть называется гомогенной, в ином случае – гетерогенной. Управлять гетерогенной сетью намного сложнее, хотя в наш век стандартных протоколов связи эти трудности успешно преодолеваются. Понятие "комплекс вычислительных средств" и связанные с этим понятием проблемы мы продемонстрируем на нескольких примерах.

Более 6 лет мы разрабатывали большую междугородную телефонную станцию. Эта АМТС предназначалась для правительственной связи, поэтому главным требованием была надежность. Именно из-за соображений надежности для управления АМТС был разработан довольно сложный комплекс вычислительных средств (КВС).

Во главе КВС стоит троированный "Самсон", его надежность во много раз превосходит надежность любого другого элемента КВС. Именно "Самсон" принимает окончательное решение во всех спорных ситуациях. Через центральный канал межмашинного обмена (ЦКМО) "Самсон" связан с периферийными управляющими устройствами (ПУУ), которых может быть до 100 штук, и ЦКМО, и ПУУ дублированы. Каждая половинка ПУУ связана с одним подканалом ЦКМО, но может быть переключена и на другой подканал. Каждое ПУУ представляет собой небольшую ЭВМ, управляющую телефонным оборудованием (абонентскими комплектами, коммутационным полем, концентраторами и т.д.)

Две половинки ПУУ работают синхронно, выполняя одну и ту же программу. Существует специальная схема, проверяющая совпадение результатов половинок, выдаваемых в ЦКМО. Если "Самсон" получит сигнал о несовпадении результатов (то, в первую очередь, проверяется корректность ЦКМО) – просто посылается контрольный запрос на соседние ПУУ: если ответ поступит, то сбилось ПУУ, если нет, то что-то случилось с ЦКМО. Если вышел из строя один из подканалов ЦКМО, он выводится из конфигурации, второй подканал переводится в другой режим работы, например, каждое сообщение повторяется или кодируется специальным кодом с избыточностью, который позволяет обнаруживать и даже исправлять ошибки передачи.

Если же с ЦКМО все в порядке то, прежде всего надо выяснить, какая из половинок ПУУ сломалась. "Самсон" запускает короткий диагностический тест в обеих половинках, затем выводит неисправную часть из конфигурации и сообщает оператору о необходимости ремонта. Ввод в конфигурацию половинки ПУУ после ремонта является весьма нетривиальной задачей. Остановить работающую половинку даже на короткое время для выравнивания данных с вводимой половинкой нельзя из-за требований надежности и готовности АМТС в целом. Нам удалось придумать хитрый алгоритм постепенного выравнивания данных, но поскольку несколько поколений студентов заваливало экзамен на этом вопросе, я отказался от мысли изложить содержание алгоритма в лекциях, хотя готов рассказать его интересующимся в индивидуальной беседе.

АМТС управляется операторами, сидящими за рабочими местами операторов (РМО), которых может быть до 30 штук. Каждое РМО — это две обычных персональных ЭВМ (основная и резервная). Никаких аппаратных средств резервирования ПЭВМ не имела, поэтому пришлось изобретать программную реализацию. И основная, и резервная ПЭВМ связана с "Самсоном" отдельным, сравнительно медленным последовательным каналом. В "Самсоне" для каждого РМО предусмотрен специальный драйвер, который "знает", какая ПЭВМ в данный момент основная, а какая – резервная. Любая информация для РМО из "Самсона" посылается в обе ПЭВМ, все действия оператора разбиты на короткие транзакции по базе данных конкретного РМО. Если основная ПЭВМ отказала, что видно по тестам, таймерным событиям или просто визуально, оператору достаточно пересесть на резервную ПЭВМ. При этом гарантируется, что все транзакции, завершенные на основной ПЭВМ, закончены и на резервной, поэтому оператору не придется заново вводить более одной команды.

В 1996 году мы успешно прошли государственные испытания этой АМТС, накопили бесценный опыт разработки и комплексной отладки сложных программно-аппаратных средств, отработали технологию программирования RTST на базе SDL, в общем, все было хорошо. Мы были уверены в скором и успешном продолжении работ, но в этот момент государственное финансирование окончательно прекратилось, и наш отдел разработки средств телекоммуникаций остался без работы.

Поэтому как нельзя кстати оказалось предложение ЛНПО "Красная Заря" переделать или написать заново программное обеспечение для уже существующей сельской АТС "Бета". Станция была разработана в ЛНПО "Красная Заря", сертифицирована и уже серийно выпускалась. Но оказалось, что ПО, сделанное "на коленках", без всякой технологии, очень дорого в сопровождении – трудно исправить ошибку, сложно добавить новую функцию. В результате каждая АТС после полугода эксплуатации обладала индивидуальным ПО, а если после этого исправлялась какая-то незамеченная ранее ошибка или добавлялась новая функция, то приходилось переделывать все версии ПО.

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

Для начала нас познакомили с общей архитектурой АТС "Бета".

МАЛ — модуль абонентских линий, к которому подключаются до 180 телефонов.

СЛ — соединительная линия к другой АТС.

МГО – модуль группового оборудования.

Каждый из этих модулей управлялся контроллером i8086 и имел

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

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

Наш специалист Н.Ф. Фоминых тут же подсчитал, что тогда каждый контроллер будет тратить больше половины своего времени только на обработку прерываний (известно, что при тактовой частоте 4,67 Мгц этот процессор имеет чуть больше 1 млн. операций в секунду).

В результате часа разговоров с разработчиками АТС мы нашли

несколько способов уменьшить нагрузку на общую шину:

Уже первые два предложения снизили нагрузку на шину более чем в 2 раза. Но мы пошли еще дальше. Разработчики АТС "Бета" предполагали, что МАЛ (модуль абонентских линий) будет очень простым, например, он будет принимать номер вызываемого абонента по одной цифре и пересылать ее в МГО.

Самое забавное и поучительное событие произошло через несколько месяцев после того как мы начали разрабатывать новое ПО для АТС "Бета". Наша операционная система теряла отдельные сообщения, хотя по всем расчетам производительности процессора должно было хватать. После долгих мучительных поисков ошибки в ПО Н.Ф. Фоминых решил проверить правильность работы аппаратуры и обнаружил ошибку в разводке платы процессора. Вместо тактовой частоты 4,67 МГц на вход clock процессора подавалась частота 1 МГц, предназначавшаяся совсем для других целей. Таким образом, все 30 АТС, выпущенные до нас, управлялись в 5 раз более медленными ЭВМ, чем могли бы. Потому и все проблемы были связаны с шиной, т.к. любая работа с ней связана c обработкой прерываний, где производительность процессора критична. Боюсь, если бы разработчики АТС "Бета" обнаружили эту ошибку сами, к нам бы вообще не обратились и тогда бы история нашего коллектива сложилась совсем иначе.

Параллельные процессы

Вообще-то, про параллельные процессы принято рассказывать в других курсах, чаще всего в курсе "Операционные системы" [23]. Но поскольку мы хотим изложить придуманную в нашем коллективе эффективную организацию вычислительного процесса во встроенных системах реального времени, нужно, чтобы читатель понимал "что почем" в мире параллельных процессов.

Можно предложить следующую иерархию разбиения сложной системы на взаимодействующие куски:

При возврате нужно восстановить регистры, освободить память и восстановить контекст вызывающей процедуры. Для ЭВМ без аппаратной поддержки вызов процедуры может потребовать от 30 до 150 команд. Когда-то мы очень гордились, что сумели для архитектуры IBM/360 придумать реализацию вызова процедуры за 11 команд.

Заметим, что описанная реализация вызова допускает рекурсию, когда процедура вызывает саму себя, а основное направление оптимизации вызовов – сведение вызова процедуры к вызову подпрограммы.

Пусть два процесса р1 и р2 используют общую переменную S вида struct (int a,b), т.е. S является структурой с двумя целыми полями. Предположим, процесс р1 решил прочитать значение структуры S, успел прочитать первое поле a, но был по какой-то причине прерван. Процесс р2 записал в структуру S новое значение, потом процесс р1 был возобновлен и продолжил чтение со второго поля b. В результате р1 получит значения полей а и b из разных фаз обработки.

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

Еще в конце 50-х годов ХХ века известный ученый Э. Дейкстра придумал принципиально новую конструкцию – семафор [5]. Семафор – это структура с одним целым полем, но имя поля неизвестно, поэтому обычными способами ни прочитать, ни изменить это поле нельзя. Семафор допускает только три операции – установить значение семафора ( level ), увеличить ( up ) значение на 1 и уменьшить ( down ) на 1. Если во время исполнения операции down значение семафора стало отрицательным, текущий процесс приостанавливается ( suspend ), если при выполнении операции up значение семафора из отрицательного становится нулем, один из процессов, приостановленных из-за этого семафора, возобновляется ( resume ). Считается, что в операционной системе есть очередь готовых к исполнению процессов и очередь процессов, ожидающих неотрицательного значения какого-то семафора, но никакого определенного порядка исполнения не подразумевается. Принципиально новой идеей в семафорах является их неделимость. В операции down между вычитанием единицы и проверкой на неотрицательность никакое прерывание процесса невозможно. В наше время любая память ЭВМ обеспечивает, кроме обычных операций чтения и записи, специальную операцию "семафорное чтение", в которой в одном такте выдается значение байта, а в байт пишется 1. Нетрудно сообразить, как, используя эту операцию, корректно реализовать операции up и down.

Рассмотрим пример:

sema s = level 1;
par  begin 
    do НАЧАЛО1;
      down s; ДЕЙСТВИЯ1; up s;
      КОНЕЦ1
    od ,
    do НАЧАЛО2;
      down s; ДЕЙСТВИЯ2; up s;
    КОНЕЦ2
    od
  end

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

Действия НАЧАЛО1 и НАЧАЛО2 выполняются параллельно, допустим, второй процесс раньше достигает своего оператора down s. Тогда s получит значение 0, начнется выполнение последовательности ДЕЙСТВИЯ2. Пусть теперь и первый процесс достигнет оператора down s. Так как текущее значение s равно 0, первый процесс приостановится и будет ждать, пока второй процесс не выполнит оператор up s. Кстати, никто не гарантирует, что после этого возобновится первый процесс – если второй процесс выполняется быстрее первого, то вполне возможно, что раньше снова сработает оператор down s второго процесса.

Я хотел показать на этом примере, что ДЕЙСТВИЯ1 никогда не будут выполняться параллельно последовательности ДЕЙСТВИЯ2 – или ДЕЙСТВИЯ1, или ДЕЙСТВИЯ2, но не вместе. Такие фрагменты параллельных процессов называются критическими интервалами.

На практике столь простая и фундаментальная конструкция, как семафор, оказалась очень опасной. Два семантически связанных действия разнесены по тексту. Кто-то забудет открыть семафор, а кто-то – закрыть.

Позже Т. Хоар предложил более безопасную конструкцию для синхронизации параллельных процессоров – монитор[26]. Представьте себе дверь в комнату, в замок которой вставлен ключ. Вы открываете дверь, вынимаете ключ, входите в комнату и закрываетесь в ней. Следующий, кто захочет войти в комнату, не найдет ключа и вынужден будет ждать, пока вы не выйдете. В языки программирования ввели оператор seize m (схватить ресурс m ). Если ресурс занят, процесс зависает прямо на этом операторе seize – никакого "парного" оператора не надо. Вроде бы пустяк, но оказалось, что этот оператор значительно технологичнее.

Значительно позже появились почтовые ящики, "рандеву" и многие другие средства. Математически они все эквивалентны, т.е. выражаются друг через друга, но с точки зрения технологичности, выразительности, эффективности реализации — существенно различаются.

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

По оператору receive процесс просматривает свою очередь входных сообщений. Если она пуста, то процесс "зависает", иначе берется очередное сообщение и обрабатывается.

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

Иногда требуется более жесткая схема синхронизации, тогда вместо send используется оператор ask m, после которого процесс приостанавливается и ждет ответа.