Назначение приоритетов

Параметры задач в нераспределенной системе управления лифтами приведе­ны в табл.1. Время ЦП для каждой задачи включает затраты на контекстное переключение (не более двух переключений на задачу). Затраты на обработку со­общений поровну разделены между задачей-отправителем и задачей-получателем. Периоды всех задач, участвующих в данной последовательности обработки собы­тий, одинаковы: они определяются поступлением внешнего события, послужив­шего началом последовательности. Задача Диспетчер Лифта рассматривается так, словно представляет собой две разные задачи, поскольку встречается в двух разных последовательностях. В первом случае ее период равен 100 мс (частота активизации Интерфейса Кнопок Лифта), а во втором – 200 мс (частота активи­зации Интерфейса Кнопок Этажа).

Заметим также, что периоды трех асинхронных задач интерфейса устройств (все они управляются прерываниями) кратны друг другу, то есть эти задачи могут быть готовы к активизации практически одновременно. Поскольку прерывания нужно обрабатывать максимально быстро, данным задачам следует назначить наивысшие приоритеты. Но тогда будет нарушено правило частотной монотонности: например, задача Интерфейс Кнопок Этажа, имея более длинный период, чем Контроллер Лифта, получит тем не менее более высокий приоритет.

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

Рассмотрим, какие приоритеты должен назначить задачам проектировщик (см. табл.1). Если не считать трех задач, управляемых прерываниями, то остальным задачам присваиваются естественные частотно-монотонные приоритеты. Задаче Интерфейс Датчиков Прибытия определяется наивысший приоритет, что, кстати, согласуется с алгоритмом частотной монотонности. Но уже задачам Интерфейс Кнопок Лифта и Интерфейс Кнопок Этажа назначаются второй и третий по порядку приоритеты, что противоречит этому алгоритму. Следующий приоритет, согласно алгоритму частотной монотонности, получает задача Кон­троллер Лифта, у которой самый короткий период. Хотя задача Диспетчер Лиф­та участвует в двух последовательностях, приоритет ей назначается в соответ­ствии с более коротким периодом.

 

 

 

Таблица 1. Параметры задач для планирования в реальном времени на примере системы управления лифтами

 

Планирование в реальном времени для нераспределенной архитектуры

Сложение коэффициентов использования ЦП для всех задач в табл.1 дает полный коэффициент 0,4, то есть намного меньше значения 0,69, полученного из теоремы о верхней границе. Но, поскольку присвоение приоритетов произведено с нарушением принципа частотной монотонности, необходим более детальный разбор.

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

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

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

14.5. Последовательность событий «Остановка Лифта на Этаже»

Задачи, входящие в последовательность событий:Интерфейс Датчиков Прибытия и Контроллер Лифта. Из табл.1 видно, что период этой последова­тельности Т_a составляет 50 мс.

Рассмотрим четыре фактора, вытекающие из обобщенной теории планирова­ния в реальном времени:

– время выполнения задач в последовательности событий. 2 мс для задачи Интерфейс Датчиков Прибытия, затем 5 мс для задачи Контроллер Лифта, что в сумме дает С_а = 7 мс. Коэффициент использования ЦП за счет выполнения U_a = С_а / Т_а = 7 / 50 = 0,14;

– время вытеснения более приоритетными задачами с меньшими периодами. Поскольку эта последовательность имеет наименьший период, таких задач нет;

– вытеснение более приоритетными задачами с большими периодами. Задачу Контроллер Лифта в состоянии вытеснять и Интерфейс Кнопок Лифта, и Интерфейс Кнопок Этажа. При этом первая из них может занять 3мс на обработку прерывания, а вторая – 4 мс. Следовательно, общее время вытес­нения Р_а = 3 + 4 = 7 мс, а соответствующий коэффициент использования U_p=Р_a /Т_a =7/50 = 0,14;

– время блокировки задачами с более низким приоритетом. Задача Планировщик способна занимать критическую секцию на 20 мс, пока работает с разделяемым объектом, и все это время задача Контроллер Лифта будет блокирована. Время блокировки В_а в худшем случае равно 20 мс, а коэффи­циент использования U_b = В_а / Т_а = 20 / 50 = 0,40.

Теперь можно определить суммарное затраченное время и полный коэффици­ент использования ЦП.

Суммарное затраченное время = время выполнения + время вытеснения + + время блокировки в худшем случае = С_а + Р_а + В_а = 7 + 7 + 20 = 34 мс, что меньше периода, равного 50 мс.

Полный коэффициент использования = коэффициент использования за счет выполнения + коэффициент использования за счет вытеснения + коэффициент использования за счет блокировки = U_e + U_p + U_b = 0,14 + 0,14 + 0,40 = 0,68, что меньше верхней границы 0,69.

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

 

Примечание. На этом рисунке используется расширенная нотация UML.для временных диаграмм.

Рис.36. Система управления лифтами: диаграмма последовательности с временными метками

14.6. Последовательность событий «Выбор Этажа Назначения»

Задачи, входящие в последовательность событий: Интерфейс Кнопок Лиф­та и Диспетчер Лифта. Из табл.1 видно, что период этой последовательности Т_b равен 100 мс.

Рассмотрим те же четыре фактора, что и выше:

– время выполнения задач в последовательности событий. 3 мс для задачи Интерфейс Кнопок Лифта, затем 6 мс для задачи Диспетчер Лифта, что в сумме дает С_b = 9 мс. Коэффициент использования ЦП за счет выполнения U_b = С_b / Т_b = 0,09;

– время вытеснения более приоритетными задачами с меньшими периодами. В течение 100 мс по два раза могут выполниться задачи Интерфейс Датчи­ков Прибытия и Контроллер Лифта, что приведет к вытеснению на 14 мс;

– вытеснение более приоритетными задачами с большими периодами. 4 мс способна занять задача Интерфейс Кнопок Этажа на обработку прерыва­ния (она вытесняет Диспетчера Лифта). Следовательно, общее время вы­теснения более приоритетными задачами С_p =14 + 4 = 18 мс, а соответству­ющий коэффициент использования U_p = С_p / Т_p = 18 / 100 = 0,18;

– время блокировки задачами с более низким приоритетом. Задача Планировщик может занимать критическую секцию на 20 мс, блокируя задачу Диспетчер Лифта. Время блокировки В_b в худшем случае равно 20 мс, а коэффициент использования U_b = В_b / Т_b = 20 / 50 = 0,20.

Таким образом, получаем:

Суммарное затраченное время = время выполнения + время вытеснения + + время блокировки в худшем случае = 9 + 18 + 20 = 47 мс, что меньше периода, равного 100 мс.

Полный коэффициент использования = коэффициент использования за счет выполнения + коэффициент использования за счет вытеснения + коэффициент использования за счет блокировки = U_p + U_e + U_b = 0,09 + 0,18 + 0,20 = 0,47, что меньше верхней границы 0,69.

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

14.7. Последовательность событий «Вызов Лифта»

Задачи, входящие в последовательность событий:Интерфейс Кнопок Этажа, Планировщик и Диспетчер Лифта (участвует сразу в двух последовательностях событий). Из табл.1 видно, что период этой последовательности Т_с равен 200 мс.

Рассмотрим все те же четыре фактора:

– время выполнения задач в последовательности событий. 4 мс для задачи Интерфейс Кнопок Этажа, затем 20 мс для задачи Планировщик. После этого в течение 6 мс выполняется Диспетчер Лифта, что в сумме дает С_с = 4 + + 20 + 6 = 30 мс. Коэффициент использования ЦП за счет выполнения U_c = С_с / Т_с= = 0,15;

– время вытеснения более приоритетными задачами с меньшими периодами. По четыре раза могут выполниться задачи Интерфейс Датчиков Прибы­тия и Контроллер Лифта (вытесняют Диспетчера Лифта и Планиров­щика), что в сумме дает 28 мс.

Задачи Интерфейс Кнопок Лифта и Диспетчер Лифта (вытесняют Пла­нировщика) в состоянии выполниться по два раза, на что уйдет еще 18 мс. Следовательно, общее время вытеснения более приоритетными задачами С_p = 28+ + 18 = 46 мс, а соответствующий коэффициент использования U_p = C_p/T_p =0,23;

– вытеснение более приоритетными задачами с большими периодами. Поскольку эта последовательность имеет наибольший период, таких задач нет;

– время блокировки. Блокировка из-за доступа к разделяемому объекту другими задачами уже принята во внимание, дополнительных затрат на блокировку нет.

Таким образом, получаем:

Суммарное затраченное время = время выполнения + время вытеснения + + время блокировки в худшем случае = 30 + 46 + 0 = 76 мс, что меньше периода, равного 200 мс.

Полный коэффициент использования = коэффициент использования за счет выполнения + коэффициент использования за счет вытеснения + коэффициент использования за счет блокировки = U_p + U_e = 0,15 + 0,23 = 0,38, что меньше верхней границы 0,69.

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