Содержание к диссертации
Введение
1. Выполнение стохастических задач в режимах перегрузки 9
1.1 Обзор существующих моделей задач и алгоритмов планирования 9
1.2 Модель стохастических задач 22
1.3 Режим перегрузки 23
1.4 Алгоритм cu s 27
1.5 Алгоритм cbs 31
выводы 36
2. Эффективность выполнения стохастических задач 38
2.1 Схема задержанных работ 38
2.2 Показатели качества выполнения задачи 43
2.3 Критерии оптимизации 51
2.4 Оптимизация в режиме энергосбережения 60
2.5 Алгоритм численного решения задачи оптимизации 66
3. Моделирование работы алгоритма планирования 73
3.1 Схема без балансировки загрузки процессора 74
3.2 Пропорциональная балансировка задач 80
3.3 Оптимизация по критерию q]mm 89
3.4 Сравнение алгоритмов cus и cbs 92
3.5 Режим энергосбережения 94
выводы 97
4. Диспетчер операционной системы реального времени 99
4.1 Средства диспетчеризации современных операционных систем 99
4.2 Модульная структура диспетчера 102
4.3 Временные параметры диспетчеризации 103
4.4 Оценка накладных расходов 109
Выводы 110
Заключение 112
Список литературы
- Модель стохастических задач
- Показатели качества выполнения задачи
- Пропорциональная балансировка задач
- Временные параметры диспетчеризации
Введение к работе
Диссертационная работа посвящена разработке аналитических моделей и оптимизации выполнения системы стохастических задач в режимах перегрузки.
Актуальность проблемы
Современные системы управления осуществляют преобразование входной информации от объекта управления и выдачу ее обратно в виде управляющих воздействий. Наиболее распространенной моделью задач, используемой в системах управления, является модель периодических задач. Модель оперирует с задачами, выполняющимися в цикле с заданным значением периода и постоянным временем выполнения. Для модели периодических задач разработан ряд алгоритмов планирования, позволяющих оптимально выполнять задачи в системе.
Существует класс задач, время работы которых не является постоянным, а распределено по вероятностному закону. В рамках диссертационной работы они названы стохастическими. На основе анализа существующих подходов к выполнению стохастических задач можно сделать вывод о существовании потребности в новых методах планирования выполнения стохастических задач в режимах перегрузки. Режим перегрузки характеризуется невозможностью выполнять вес задачи в системе без задержек. В качестве причин возникновения режима можно выделить следующие: добавление новых задач в систему, перерасход задачей отведенного ей времени, снижение тактовой частоты процессора. Добавление новых задач может быть следствием изменения режима работы системы. При этом появление перегрузки в случае стохастических задач более вероятно, нежели при работе задач с постоянным временем выполнения. В отказоустойчивых системах, при отказе части оборудования, возможны ситуации превышения штатной величины загрузки процессора во много раз. Существует необходимость в оптимизации планирования выполнения задач в целях повышения эффективности функционирования системы управления. Перегрузка также может возникнуть как следствие режима энергосбережения. При этом необходимо решать задачи оптимального использования процессорного ресурса. Разработка
аналитических моделей функционирования системы стохастических задач в режимах перегрузки позволит решать практические задачи анализа и синтеза отказоустойчивых систем управления/
Цель диссертационной работы заключалась в разработке аналитических моделей и оптимизации выполнения системы стохастических задач в режимах перегрузки.
Методы исследования
Решение поставленных задач основывается на использовании методов оценки производительности вычислительных структур, теории расписаний, математического аппарата функционального анализа, теории массового обслуживания, основных положений вычислительной математики, теории вероятности и математической статистики, теории построения и анализа аналитических и имитационных моделей.
На зашиту выносятся:
Показатели качества выполнения системы стохастических задач, представляющие степенные средние показателей качества выполнения отдельных задач системы, учитывающие как величину средней задержки выдачи результатов задач, так и разброс значений показателей качества для отдельных задач.
Метод планирования выполнения стохастических задач с оптимизацией по разработанным показателям качества, проводимой в процессе выполнения системы задач на основе учета распределения случайной величины времени выполнения каждой задачи.
Подход к проведению оптимизации по предложенным показателям качества выполнения системы стохастических задач в режиме пониженной тактовой частоты исполняющего процессора.
Концепция сокращения времени реакции на изменение распределений времени выполнения отдельных задач в процессе выполнения системы задач.
5. Результаты моделирования выполнения системы стохастических задач с оптимизацией по разработанным показателям в сравнении с результатами, полученными с использованием альтернативных методов планирования задач.
Научная новизна работы
Научная новизна работы состоит в разработке аналитических моделей и оптимизации выполнения системы стохастических задач в режимах перегрузки на основе разработанных показателей качества выполнения системы задач, имеющих возможность учитывать неравноправность задач и использовать функцию штрафа за задержку результатов выполнения для каждой задачи.
Практическая ценность и реализация результатов работы Разработанная аналитическая модель, предложенные показатели качества и критерии оптимизации выполнения системы стохастических задач позволяют организовывать эффективное выполнение системы задач в режимах перегрузки. Модель открывает новые возможности в проведении практического анализа и синтеза вычислительных систем, функционирующих в режиме перегрузки. Разработанный метод планирования выполнения стохастических задач с оптимизацией по предложенным критериям позволяет повысить качество решения задач управления в режиме перегрузки.
Внедрение результатов работы
Результаты диссертационной работы использовались при выполнении ряда работ, что подтверждается соответствующими актами.
Апробация работы
Результаты диссертационной работы докладывались и обсуждались на научно-технических конференциях и семинарах:
Международная конференция «Информационные средства и технологии», (Москва, 2004),
на научных семинарах каф. 304 "Вычислительные машины и системы", МАИ (Москва, 2001-2005).
Публикации
По материалам диссертационной работы опубликовано 5 работ.
Структура диссертации
Диссертация состоит из 4 глав, введения и заключения. Общий объем работы - 121 страница, в том числе 75 рисунков и 6 таблиц. Список литературы включает 89 наименований.
Во введении обосновывается актуальность темы диссертационной работы, определяются цель и основные рассматриваемые вопросы, описываются новизна, практическая значимость и реализация результатов работы.
В первой главе приведены основные требования к системам управления, сделан обзор наиболее часто используемых моделей задач и методов планирования выполнения задач. Наибольшее распространение получила модель периодических задач, оперирующая с задачами, время выполнения которых является постоянной величиной. Для модели периодических задач с постоянным временем выполнения существуют оптимальные алгоритмы выполнения на основе приоритетов. Для ряда систем величина времени выполнения задач не является постоянной и представляет собой случайную величину, которая может быть описана законом вероятностного распределения. Такие задачи названы стохастическими. В качестве примера рассмотрены задачи обработки видео информации. Приведена модель стохастических задач и сделан обзор существующих методов планирования выполнения задач.
Показано, что в современных системах управления существуют, по меньшей мере, два класса задач: критические и информационные. Критические задачи должны всегда выполняться с заданной частотой, в то время как для
информационных задач частота выполнения может быть уменьшена в режиме перегрузки.
Режим перегрузки характеризуется недостаточностью процессорного ресурса для выполнения задач без опозданий. Показана необходимость дополнительных исследований эффективности выполнения стохастических задач в режимах перегрузки. В режиме перегрузки задержки задач носят неконтролируемый характер, что может приводить к неконтролируемому качеству выполнения задач. Предлагается контролировать качество выполнения задач путем контроля задержек задач.
Во второй главе на основе схемы задержанных работ рассмотрены относительные и абсолютные показатели качества выполнения стохастических задач. Показатели качества выполнения задачи характеризуют удаление задачи от номинального режима, который в рассматриваемой системе задач состоит в завершении всех работ задачи за один период. На основе введенных показателей качества выполнения отдельных задач предложены показатели качества выполнения системы стохастических задач. Предложены критерии оптимизации выполнения системы стохастических задач по введенным показателям качества. Показано, что оптимизация в режиме энергосбережения, по предложенным критериям может быть произведена с изменением только одного входного параметра оптимизации. Это позволяет использовать предложенные критерии в существующем виде также и в режиме энергосбережения.
Рассмотрено использование алгоритма координатного спуска для численного решения задачи оптимизации по предложенным критериям. Алгоритм может быть реализован в средствах планирования операционной системы.
Рассмотрены способы получения распределения времени выполнения задачи в режиме функционирования системы. Предложены методы адаптации к изменению распределения времени выполнения задачи.
В третьей главе представлены результаты моделирования выполнения системы стохастических задач. Сравнивалось выполнение с использованием
предложенных критериев оптимизации и альтернативные подходы к выполнению стохастических задач. В качестве альтернативных подходов использовались схемы:
без балансировки загрузки процессора;
с пропорциональной балансировкой задач;
с использованием существующего критерия оптимизации {?,шач.
В процессе моделирования предложенный метод выполнения продемонстрировал преимущество над альтернативными подходами. Сделан вывод о целесообразности реализации предложенных методов планирования выполнения задач в виде диспетчера-надстройки операционной системы.
В четвертой главе приведена реализация диспетчера - надстройки операционной системы VxWorks. Диспетчер - надстройка выполняет систему стохастических задач с оптимизацией по предложенным критериям.
Модель стохастических задач
Будем рассматривать систему из N стохастических задач Т,, \ i N. Задачи выполняются периодически. Период выполнения /-и задачи равен Р, (Рис. 7). Выполнение і-й задачи в j-м периоде названо работой и обозначается Ти. Число задач в системе Сможет варьироваться.
Каждая J-я работа і-й задачи имеет момент поступления ги и момент готовности результатов atj. ci}- время выполнения у-й работы і-й задачи распределено по вероятностному закону с функцией распределения F((t), [Е t E ]. Е и Е минимальное и максимальное время выполнения j-й задачи. j-я работа і-й задачи имеет директивный срок di} - момент времени, к которому работа должна выдать результаты. Директивный срок у-й работы /-й задачи совпадает по времени с окончанием J-ro периода і-й задачи, т.е. работа должна выдать результаты до окончания своего периода.
В штатном режиме работы (без перегрузки) для планирования стохастических задач может быть использован алгоритм EDF. В каждом периоде работы /-й задаче резервируется для выполнения Е единиц времени. Работы будут завершаться в срок, т.е. до директивного срока, при выполнении условия: 1=1 ч где Е - максимальное время выполнения задачи, а Ру - период і-й задачи. Предполагается, что распределение величины времени выполнения запроса неизменно или слабо меняется на заданном временном отрезке. Случай адаптации к изменяющемуся распределению рассмотрен далее в работе в разделе 2.6. Задачи являются независимыми, т.е. моменты запросов одной задачи не зависят от моментов запросов и моментов окончания запросов других задач. В системе рассматриваются только стохастические задачи. Каждая задача имеет свое собственное распределение времени выполнения. Вид функции распределения может быть произвольным, например показанным на рис. 8. I I Е.- Е t
В диссертационной работе основное внимание уделено случаю, когда разброс случайной величины времени выполнения достаточно широк. При условии Е —Е « Е система может быть преобразована к периодической модели задач с постоянным временем выполнения и проанализирована при помощи методов, применимых к таким системам. В периодической системе задач режим перегрузки может быть определен как режим, при котором производительности процессора не хватает для выполнения « всех задач без пропусков. В качестве причин возникновения режима перегрузки могут выступать: - добавление в систему новой задачи, при условии, что потребность в ресурсах задачи превышает величину свободных ресурсов системы, т.е. с добавлением новой задачи система задач перестает отвечать критерию выполнимости плана; - превышение задачей расчетного времени выполнения; - изменение тактовой частоты процессора, так что система не в состоянии выполнять задачи без пропусков.
Добавление в систему новой задачи может нарушить условие выполнимости плана, и в системе могут появиться пропуски. Современные методы планирования содержат тест выполнимости плана, который проверяет, будет ли новая система выполняться без опозданий. Ряд алгоритмов [32] включают в себя тест допустимости, который проверяет выполнимость плана. Если при добавлении новой задачи диагностируется режим перегрузки, то задача отбрасывается. Если задача отброшена, она не может быть принята, даже если одна из других задач завершилась ранее.
В других алгоритмах проверяется выполнимость плана в зависимости от показателя важности задачи. Если при поступлении задачи наблюдается перегрузка, то менее важные задачи временно помечаются приостановленными, впоследствии они могут быть восстановлены в случае раннего завершения одной из других задач.
Перерасход задачей расчетного времени может также привести к возникновению пропусков в других задачах. На Рис. 9 задачи Г/ и Тг выполняются согласно алгоритму RM без пропусков. Перерасход процессорного времени задачей Т} (Рис. 10) привел к появлению пропуска у задачи Т2.
Показатели качества выполнения задачи
Под качеством функционирования системы будем понимать близость ее к номинальному режиму работы. Для системы стохастических задач номинальный режим работы соответствует отсутствию пропусков. Наличие пропусков задач будет уводить систему от оптимального режима. В режиме перегруженности система вынуждена ухудшать качество выполнения задач. В задачу планировщика в режиме деградации входит выполнение задач с максимальным качеством.
Для рассматриваемой системы с задержанными работами номинальный режим, соответствующий максимальному качеству, будет выражаться как режим, когда каждая работа будет завершаться за один период. Моменты готовности результатов а-ц будут лежать в интервалах между моментами поступления работ на выполнение Гц и моментами директивных сроков d-ц (Рис. 19).
Будем считать, что результаты работ не могут быть использованы раньше наступления их директивного срока сіц. В этом случае будем принимать в рассмотрение моменты времени Ац, совпадающие с моментами времени директивных сроков, и будем считать их моментами выдачи результатов задач.
Номинальный режим работы системы будет соответствовать ситуации, когда моменты времени Ац будут следовать с периодом Р,- (Рис. 20). В режиме деградации, моменты выдачи результатов будут следовать с интервалом, превышающим Р,- (Рис. 21).
В качестве показателя качества, характеризующего качество выполнения задачи Th примем величину среднего интервала выдачи результатов задачи, измеренную в величинах периода этой задачи: р}" = M[ktJ], где М- математическое ожидание.
Будем называть показатель р]"" базовым показателем качества, в силу того, что остальные показатели будут функционально выражаться через показатель p]fe , Показатель p]ns характеризует близость задачи к номинальному режиму работы, который будет соответствовать значению показателя:
Значения показателя больше единицы будет соответствовать отклонению задачи от номинального режима. Базовый показатель качества выполнения задач имеет физическую интерпретацию и равен среднему значению интервала выдачи результатов задачи, выраженному в периодах этой задачи.
Показатель р, может быть выражен через величину С, и рассчитан через данные задачи как: РІ№(С,)=1 [ ;( -С,)- ((Л:-1).С,)Ь JUI где Ft- функция распределения времени выполнения задачи Tf, С, - время» предоставляемое задаче в каждом периоде или бюджет сервера, в рамках которого исполняется задача, Е - максимальное время выполнения задачи.
Выражение для показателя может быть преобразовано к более простому виду:
Характер зависимости р]ге5(С от величины С, показан на Рис. 22. При значениях С, близких к 0, функция стремится к бесконечности, при значениях С-, Е , функция равна 1. ft""(C()" 1 - щ Рис. 22. Вид хараісгеристики77,1геї(С;)
В случае если моменты выдачи результатов задачи Ац равноотстоят друг от друга, то величина р]г" численно равна интервалу времени между выдачей результатов ARt, деленному на период работы задачи PL.
Демонстрация выдачи результатов каждый второй период Показатель/? , как было сказано выше, будем называть базовым показателем выполнения задачи, так как другие показатели могут быть выражены через этот показатель. Влияние вида распределения времени выполнения работ на вид р \С() показан на Рис. 24. л"" (О і 1 - /«A Е: Рис. 24.Влияние вида распределения времени выполнения работ на вид / т(С,) Базовый показатель качества обладает следующими особенностями: - показатель имеет физическую интерпретацию: значение показателя численно равно среднему интервалу выдачи результатов задачи; - показатель может быть аналитически выражен через параметры задачи; - показатель - относительный, т.е. выражается в периодах задачи. Кроме базового показателя рассмотрим группы относительных и абсолютных показателей. Относительные показатели
В группу относительных показателей качества входят показатели выполнения задач, определенные в величинах значений периодов задач. Благодаря этому анализ, проводимый на основе данных характеристик, позволяет не учитывать длительность периодов задач во временных единицах, тем самым удается рассматривать высокочастотные и низкочастотные задачи совместно друг с другом. Группа включает следующие показатели (Табл. 4).
Пропорциональная балансировка задач
Специфика применения большинства систем управления требует поддержки режима реального времени. Операционная система для того, чтобы отвечать условиям реального времени должна удовлетворять ряду требований: - постоянная готовность к получению данных от объекта управления; - детерминированное время обработки входных воздействий; - надежность.
Для решения задач реального времени операционная система должна поддерживать следующие функции: - поддержка диспетчеризации на основе директивных сроков или, по крайней мере, на основе приоритетов; - быстрое переключение задач с ограничением на время переключения; - конечное время вызова системных функций; - время реакции на прерывание должно быть ограниченным; - должна быть предусмотрена защита от тупиковых ситуаций; - должен быть реализован механизм инверсии приоритетов для предотвращения взаимных блокировок задач.
Рассмотрим распространенные современные операционные системы реального времени. Операционная система реального времени VxWorks[86] поддерживает два типа диспетчеризации: вытесняющую и круговую. Вытесняющая диспетчеризация выполняет задачи согласно приоритетам. В каждый момент времени выполняется задача с максимальным приоритетом. Более низкоприоритетная задача может получить управление только после окончания выполнения высокоприоритетной задачи. Операционная система VxWorks поддерживает 256 уровней приоритетов задач. Второй тип диспетчеризации -круговая - также выполняет задачи согласно приоритетам, кроме того, задачи с одинаковым приоритетом разделяют процессорное время между собой при помощи механизма квантования времени. Значение кванта времени переключения задач с одинаковыми приоритетами может быть установлен. Операционная система VxWorks успешно применяется в задачах управления реального времени. Архитектура операционной системы позволяет реализовывать дополнительные алгоритмы планирования задач в виде надстройки над базовыми средствами диспетчеризации. ОСРВ OS-9000[65] поддерживает четыре типа диспетчеризации: - автоматическую; - диспетчеризацию с блокировкой по приоритету; - диспетчеризацию с блокировкой по группам; - монопольного управления.
Автоматическая диспетчеризация предоставляет задачам процессорное время при помощи квантования времени и назначения задачам приоритетов. Диспетчеризация с блокировкой по приоритету позволяет блокировать задача с приоритетом ниже заданного уровня.
Диспетчеризация с блокировкой по группам устанавливает значение приоритета, который разделяет задачи по группам в соответствии с приоритетами. В высокоприоритетной группе задачи выполняются согласно приоритетам. Пока есть активная задача из высокоприоритетной группы, ни одна задача из другой группы не может получить выполнение.
При монопольном управлении задачи могут монопольно захватывать управление процессором. предоставляет задачам FIFO, круговую и адаптивную диспетчеризацию. FIFO диспетчеризация выполняет задачи согласно последовательности их поступления на выполнение. Более высокоприоритетные задачи могут вытеснять низкоприоритетные. Круговая диспетчеризация выполняет задачи по кругу с использованием механизма временного квантования. При адаптивной диспетчеризации выполнение задач происходит согласно приоритетам, изменяемым по заданным правилам. Приоритет задачи уменьшается каждый квант на 1 при использовании задачей этого кванта, и увеличиваются на 1, если в течение одной секунды времени работы процессора задача не выполнялась.
Кроме рассмотренных операционных существуют также способы выполнения задач реального времени с применением операционных систем общего назначения. Расширение реального времени RTX для операционной системы Windows позволяет организовать выполнение задач реального времени за счет модификации ядра операционной системы.
Также существуют способы организации работы сразу двух операционных систем на одном компьютере. Система LP-VxWin[57] позволяет выполнять задачи реального времени с использованием операционной системы VxWorks, активизируемой по немаскируемому прерыванию процессора. Во время отсутствия задач реального времени процессор предоставляется операционной системе Windows.
Временные параметры диспетчеризации
Для грубой оценки накладных расходов примем следующее допущение: частота вызова ДН равна сумме частот вызова отдельных задач. При практических опытах была получена частота вызова ДН 50 Гц. Тогда среднее значение интервала между вызовами ДН равно обратной величине частоты его вызова и составляет: С = 1/50 = 20 мс. Величина относительных накладных расходов Оге1 может быть подсчитана по формуле: -\ где Он С - усредненные оценки величин ОиС соответственно. Для случая прерывания по таймеру: О = 85.9 мкс. В случае прерывания по оператору окончания: О = 90.9 мкс. В случае, если во время вызова ДН происходит решение задачи оптимизации, полученные величины принимают значения 1330.9 мкс. и 1335.9 мкс. соответственно. Окончательно получаем, для прерывания по таймеру: Oret=0A%, для прерывания по оператору окончания Orel = 0.5 %.
В случае выполнения оптимизации эти величины принимают значения 6% и 6.7% соответственно. Учитывая, что реконфигурация происходит только при добавлении, удалении задач или при изменении распределения времени выполнения задачи процессорное время большей частью тратиться на нее не будет. Например, если реконфигурация будет происходить один раз в секунду, то средняя величина накладных расходов будет равна 0.62%.
Выводы
Проведен анализ существующих коммерческих операционных систем реального времени и сделан вывод о том, что существующие операционные системы реализуют только базовый набор алгоритмов планирования задач.
Для реализации предложенного метода выполнения стохастических задач использован диспетчер-надстройка, представляющий надстройку над существующими средствами планирования операционной системы.
Рассмотрены временные параметры функционирования диспетчера-надстройки и описаны основные алгоритмы его работы.
В процессе моделирования получены оценки накладных расходов функционирования диспетчера, которые составили 0.5 % в случае без проведения оптимизации выполнения задач и 6.7% в случае проведения оптимизации. В среднем при проведении оптимизации один раз в секунду величина накладных расходов составила менее 1%.
Каждая задача в системе состоит из следующих модулей; - Модуль инициализации. Осуществляет подготовительные действия, такие как распределение памяти, инициализация структур данных. Вызывается при запуске системы до начала выполнения задачи. - Модуль обработки. Содержит бесконечный цикл выполнения программы. Каждый цикл состоит из последовательности действий, составляющих работу задачи. - Модуль завершения. Освобождает занятые задачей ресурсы. Вызывается при завершении функционирования системы. Модуль обработки имеет структуру, показанную на рис. 70. Начало цикла Выполнение задачи Оператор Конец цикла окончания Рис. 70. Структура модуля обработки задачи В конце цикла выполнения задачи стоит оператор окончания, сигнализирующий диспетчеру об окончании цикла выполнения задачи. На Рис. 71 показан пример выполнения двух задач при помощи диспетчера-надстройки: Т}{Р=700, С=300}; Т2{Р=500, С=100}, где Р - период задачи, а С - время, предоставляемое задаче в каждом периоде. Вся временная ось t разделена на участки двух типов: занятые задачей и свободные. Границами участков являются моменты вызова диспетчера-надстройки, показанные на рис. 71 вертикальными стрелками. , St і t-M . М - АА . t - Mi ргтг 500 1000 І І І І І І І І І І I 1500 2000 Рис 71. Пример выполнения двух задач при помощи диспетчера-надстройки Вызовы диспетчера-надстройки могут иметь место в следующих случаях: - по сигналу таймера; — по вызову оператора окончания, что соответствует завершению задачи. 104 Временные диаграммы работы диспетчера в случае прерывания по таймеру и оператору окончания показаны на рис. 72 и рис. 73. Си тай нал иера Команда на запуск ДН Старт задачи Сигнал таймера і [ г\ V к tsi \ ч tid % ъ Работа задачи или простой (tt) к t а а W Старт обработчика Старт ДН IRQ о сЕ С Рис. 72. Временная диаграмма работы диспетчера-надстройки: случай прерывания выполнения по таймеру На рисунках приняты следующие обозначения: О - абсолютная величина накладных расходов за один вызов диспетчера, СЕ - величина времени, затраченного на выполнение задачи, С - интервал времени между вызовами диспетчера. Длительности составляющих участков приведены в табл. 6. Величина относительных накладных расходов Огс1 может быть подсчитана по формуле: Оге1 ==, где Ои С - усредненные оценки величин О и С соответственно. 105 Сигнал окончания счета Команда на запуск ДН Старт задачи Сигнал таймера ldt Работа задачи или простой (t,) Старт ДН Рис. 73. Временная диаграмма работы диспетчера-надстройки: случай прерывании выполнения по завершению задачи Табл. 6. Значения временных параметров функционирования диспетчера-надстройки Составляющие участка Описание Значение,МКС. h Интервал времени между моментом срабатывания таймера и моментом определения прерывания процессором. Имеет значение порядка процессорного такта. -0.00 Ґ hi Интервал времени с момента определения прерывания процессором до начала выполнения обработчика прерывания. max 5.0 и Время выполнения обработчика прерывания. max 6.6 tk Квант времени, предоставляемый ядру VxWorks (функция TickAnnounceO). max 5.6 td Время работы диспетчера. max1275/30.0 hd Время переключения из обработчика прерывания max J 9.0 Эксперименты проводились с частотой процессора —600МГц. 106 на высокоприоритетную задачу диспетчера-надстройки. Ut Время переключения из диспетчера-надстройки назадачу max 38.9 и Время работы задачи или время простоя. и Время работы оператора окончания счета до подачи команды на запуск диспетчера-надстройки, включая время переключения на оператор окончания. max I.I и Время переключения исполнения с оператора окончания на диспетчер - надстройку. max 20.9 Данные табл. б были получены на машине с процессором 600 МГц. Измерения проводились при помощи встроенного в процессор Intel Pentium счетчика реального времени (RTC), имеющего разрешающую способность в 1 машинный такт. Алгоритм планирования EDF предполагает, что переключение между задачами осуществляется мгновенно, т.е. накладные расходы равны 0. В действительности, мы сталкиваемся с совершенно противоположной ситуацией, когда накладные расходы отличны от 0. Рассмотрим следующий пример (Рис. 74). Ш ШШ а) ж б) "ГТ і і і і і і і і і і і і і 1000 1500 Расчетное время начала выполнения задачи 0 500 ДН Е5Э Задача Щ. Рис. 74. Пример изменения последовательности выполнения задач 107
На рисунке а) изображено выполнение двух задач Г/ и 7 Время работы задач 450 и 400 соответственно. Директивные сроки задач: Dj = 1600, Di=900. Рассмотрим работу планировщика в момент времени 200. Момент поступления работы задачи 7 произойдет только в момент времени 300, поэтому в качестве кандидата на выполнение выбирается задача Г/. Таймер устанавливается на момент прихода запроса от задачи 7 , равный 300, так как в данный момент времени задача Тг будет иметь наиболее близкий директивный срок Z ? = 900. Предположим, что ДН потратит на свое выполнение 200 единиц времени и закончит работу только в момент времени 400, когда срок срабатывания таймера уже будет пропущен. Такая ситуация является следствием конечного, отличного от 0 времени работы ДН. Для предотвращения таких ситуаций предлагается вводить понятие расчетного времени запуска задачи, которое будет использоваться при определении планировщиком задачи - кандидата на выполнение и момента следующего вызова ДН. Расчетное время устанавливается равным прогнозируемому моменту начала работы следующей задачи (Рис. 74 (б)). В результате такого переноса будет наблюдаться изменение порядка задач: в момент времени 400 запустится уже другая задача Тг.
