В системах реального времени

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

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

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

Выделим следующие группы алгоритмов планирования вычислительных процессов в системах реального времени /7,8,12,13/:

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

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

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

Динамическое планирование наилучшего результата. При этом анализ осуществимости планирования не выполняется; система пытается удовлетворить все предельные сроки и снимает те выполняющиеся процессы, предельные сроки которых нарушены.

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

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

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

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

4.2.Планирование с предельными сроками

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

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

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

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

Предельное время завершения выполнения. Время, когда задание должно быть полностью завершено. Обычно задания реального времени имеют ограниче­ние — либо по предельному времени начала выполнения, либо по предельному времени завершения выполнения, но не оба ограничения одновременно.

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

Требования к ресурсам. Множество ресурсов (отличных от процессора), тре­бующихся заданию при его выполнении.

Приоритет. Мера относительной важности задания. Задания в «жестком» ре­альном времени имеют абсолютный приоритет, нарушение временных ограничений этих заданий недопустимо, в противном случае неизбежны повреждения объекта и катастрофические последствия. В системах «мягкого» реального времени возможны редкие нарушения временных ограничений заданий, но они не приводят к фатальным последствиям и лишь ухудшают свойства систем и качество управления.

Примечание. Примером системы «жесткого» реального времени может служить система автоматического ведения поезда «Автомашинист», а системы «мягкого» реального времени – система продажи железнодорожных билетов на станции по прибытию поезда. Очевидно, что разница в последствиях событий: проезд поездом запрещающего сигнала светофора и продажа билета с технической задержкой, в результате которой пассажир не успел на поезд, огромна и даже несоизмерима.

Доказано /1,7,8,13/, что для стратегии вытеснения применение планирования, выбирающего для выполнения за­дание с наиболее ранним предельным временем завершения, минимизирует долю заданий с нарушенными временными ограничениями. Этот вывод справедлив как для однопроцессорных, так и для многопроцес­сорных систем.

Пример 4.1. В качестве примера планирования периодических заданий с предельным временем завершения рассмотрим систему, которая собирает и обрабатывает данные от двух датчиков - А и В /13/. Сроки сбора данных от датчика А – каждые 20 ms, датчика В – 50 ms. Процесс снятия данных, включая накладные расходы ОС, занимает для датчика А - 10 ms, а для датчика В – 25 ms. В табл.4.1 приведен профиль выполнения этих двух заданий, а на рис.4.1,а – времена поступления, выполнения и предельные времена для заданий А и В.

Таблица 4.1