В. Столлингс - Операционные системы (1114679), страница 99
Текст из файла (страница 99)
Планировщик пытается разработать такой план работы, который бы удовлетворял всем временным требованиям заданий. Такой подход является предсказуемым, но абсолютно не гибким, поскольку любое изменение требований любого задания приводит к необходимости пересмотра всего расписания. Типичными представителями зтой категории алгоритмов планирования являются планирование наиболее раннего предельного срока и другие„рассматриваемые далее, алгоритмы планирования периодических заданий.
Статическое вытесняющее планирование на основе приоритетов использует тот же вытесняющий механизм планирования с приоритетами, что и большинство обычных многозадачных операционных систем. В таких системах для определения приоритетов могут использоваться самые различные Факторы, Например, в системе с разделением времени приоритет процесса изменяется в зависимости от того, ориентирован ли этот процесс на вычисления или на операции ввода- вывода. В системах реального времени назначение приоритетов связано с временными ограничениями каждого из заданий.
Примером такого подхода может служить частотно-монотонное планирование, рассматриваемое несколько позже в данной главе, которое назначает заданиям статические приоритеты на основе инФормации об их периоде. В случае использования динамического планирования на основе расписания после поступления задания в систему (но до начала его выполнения) делается попытка создать расписание, которое содержит как все имеющиеся в системе задания, так и вновь поступившее. Если удается создать такое расписание, что при выполнении удовлетворяются временные ограничения как нового задания, так и уже имеющихся в системе заданий, оно принимается планировщиком.
Динамическое ила пмрование наилучшего результата используется во многих современных коммерческих системах реального времени. При поступлении нового задания система назначает ему приоритет на основе характерастик етого задания. При этом подходе обычно используется планирование, учитывающее предельные сроки, — наподобие планирования наиболее раннего предельного срока. Как правило, поступающие задания непериодические, а потому неприменим статический анализ планирования, При таком типе планиРования мы не знаем, будут ли удовлетворены временные ограничения задания ло тех пор, пока задание не будет полностью выполнено (или пока не буду1 нарушены временные ограничения).
Именно зто и является основным недос. таткам данной схемы; достоинство же динамического планирования наилуч. шего результата — в простоте реализации. "аан Время планирования г) Планирование с немедленным вытеснением Рис. 10,е. Плвнировакие процессов реального времегги Часть 4. Плани Планирование с предельными сроками Большинство современных операционных систем реального времени Разра ботаны таким образом, чтобы задания реального времени начинали работу ко можно быстрее, а следовательно, особое внимание уделяют вопросам быстрой об Работки прерываний и диспетчеризации заданий.
На самом деле зто не очен1 пРактичный критерий оценки операционной системы реального времени. Обыч но приложения реального времени не так интересует абсолютная скорость вы кок Глава 10. Многопроцессорное планирование и планирование... 52. полнения заданий, как их своевременное завершение (или н чал ) или начало) — не слишком рано и не слишком поздно, несмотря на любые требован ия к ресурсам и мо-ущие возникать конфликты, перегрузку процессора или аппаратные или проРаммные сбои.
Отсюда следует, что система приоритетов — довольно слабый инструмент, который не может обеспечить гарантированное выполнение заданий ~ необходимые сроки. За последние годы появился ряд интересных подходов к планированию, бо1ее мощных и лучше приспособленных для работы с заданиями реального времени, чем их предшественники. Все они основаны на до лни на дополнительной информа~ии о заданиях„которая может включать следующее. е Время готовности.
Время, когда задание становится доступным для выполнения. В повторяющемся или периодическом задании время готовности представляет собой последовательность заранее изве тнь естных времен. В непериодическом задании это время может быть известно заранее, но может быть и так, что операционная система узнает его только в тот момент, когда задание станет действительно готовым к выполнению.
а Предельное время начала выполнения. Время, когда должно начаться выполнение задания. ° Предельное время завершения выполнения. Время, когда задание должно быть полностью завершено. Обычно задания реального времени имеют ограничение — либо по предельному времени начала выполнения, либо по предельному времени завершения выполнения, но не оба ограничения одновременно. е Время выполнения. В Ре . Время, требующееся заданию для полного выполнения. В некоторых случаях это время известно, а в некоторых — система сама оценивает взвешенное среднее значение. В других системах планирования эта величина не используется. Требования к ресурсам.
Множество ресурсов (отличных от процессора), требующихся заданию при его выполнении. е Приоритет. Мера относительной важности задания. Жесткие задания реального времени имеют '"абсолютный" приоритет, приводя к сбою системы при нарушении временных ограничений этих заданий. Если система продолжает або н р ту есмотря ни на что, то как жесткие, так и мягкие задания получают относительные приоритеты, использующиеся в качестве указаний планировщику. ° Ст т ап рук УР одзадач.
Задача может быть разбита на обязательные и необязательные подзадачи. Жесткие предельные сроки при таком разделении ', имеют только обязательные подзадачи. Можно показать что то для заданной стратегии вытеснения и использовая либо предельного в времени начала выполнения, либо предельного време- завершения п им р енение планирования, выбирающего для выполнения з»- ние с наиболее анни р нним предельным временем, минимизирует долю заданий нарушенными Рушенными временными ограничениями (В1)ТТ99, НОг)О89, РАЖЖ88). эт вывод сп аве ли р д ив как для однопроцессорных, так и для многопроцессных систем.
Таблица 10.2. Профиль выполнения двух периодических заданий Процесс Время поступления Время выполнення Предельное время окончания 10 А(Ц А(2) А(3) А(4) А(5) 40 20 10 60 10 100 10 ВО 50 Компьютер может принимать решение о планировании каждые 10 ша ПРедположим, что при этих условиях мы используем схему планирования ~ приоритетами. Результат показан на первых двух временных диаграммах мах н~ Рис. 10.5. Если А имеет более высокий приоритет, задание В1 получит тольк( 20 пм процессорного времени в двух смежных интервалах по 10 тз; после это ле этог~ будет достигнуто предельное время его выполнения, и задание выполнено н у но не бу дет.
Если более высокий приоритет получит задание В, то выполниться в срок н~ сможет задание А1. Третья временная диаграмма показывает применение в дан ной ситуации планирования с наиболее ранним предельным сроком. В момен' времени ~ = О поступают задания А1 и В1. Поскольку предельный срок А1 на ступает раньше предельного срока В1, сперва выполняется задание А1. Посл Еще одним критическим вопросом является вытеснение. Если опуезввяа~ предельное время начала работы, то имеет смысл прйменение невытесняющего планирования. В этом случае желательно, чтобы задания реального времени по сле завершения обязательной или критической части самостоятельно блокирова лись, позволяя выполняться другим заданиям реального времени с предельным временем начала работы (см.
Рис. 10.4,б). Для системы с предельным временем завершения более подходит вытесняющая стратегия (рис. 10.4,е, г). Например если выполняется задание Х, а задание У находится в состоянии готовности, то может возникнуть ситуация, когда единственным путем для удовлетворения ог раничений обоих заданий будет вытеснение Х, выполнение У до завершения, и затем возобновление выполнения Х.
В качестве примера планирования периодических заданий с предельным временем завершения рассмотрим систему, которая собирает и обрабатывает данные от двух датчиков, А и В. Сроки сбора данных от датчика А — каждые 20 пм, датчика  — каждые 50 пм. Процесс снятия данных, включая накладные расходы операционной системы„занимает для датчика А 10 тз, а для датчика  — 25 газ.
В табл. 10.2 приведен профиль выполнения этих двух заданий. Часть 4. Планирование:" н21 Глава 10. Многопроцессорное планирование и планирование... 62 Время поступления А В С О Е уребование Предвльные сроки Наиболее ранний предельный срок В2 Предельное время начала работы Время поступления В (опоздание) С Е 0 А А В С 0 Е йаиболее ранний предельный срок со свободным временем простоя Выполнение Время поступления, выполнения и предельное время Предельное время начала работы Время поступления В С Е 0 А В С 0 Е 40 50 ВО гО 80 90 100 Время, пв Выполнение 1ланированив с фиксированными приоритетами; приоритет А выше А2 В1 АЗ (Опоздание) 1ланирование с фиксированными |риоритетами; приоритет В выше Ат А2 В1 АЗ (Опоздание) А4 АБ, В2 (Опоздание) 110 20 50 90 гО 20 10 20 20 20 20 20 1ланнрование наиболее раннего цельного срока с использованием предельныхсрокоа завершения 40 50 60 'Часть 4,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
