Сценарий для анализа производительности

Теперь рассмотрим показанный на рис.29 распределенный проект, в котором имеется по одному узлу на каждый лифт, по одному узлу на каждый этаж и еще один узел для Планировщика. Предположим, что используются те же самые процессоры (то есть время выполнения не меняется) и локальная сеть со ско­ростью 100 Мбит/с, характеризуемая фиксированными задержками.

Допустим, дано 12 лифтов и 40 этажей. Нагрузка на каждый узел лифта и на каждый узел этажа должна быть меньше, чем в однопроцессорной централизованной конфигурации. Предположим, однако, что частота прибытия не изменилась, - крайне маловероятный худший случай. Параметры задач приведены в табл.2. Коэффициент использования ЦП для Подсистемы Лифта равен 0,23, а для Подсистемы Этажа – 0,04. Это наводит на мысль о том, что один узел вполне мог бы обслуживать несколько этажей.

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

В более детальном анализе нуждается узел Планировщика, поскольку имен­но он представляет собой потенциальное узкое место. Число этажей в четыре раза увеличилось, значит, период задачи Планировщик Лифта пропорционально уменьшился (с 200 до 50 мс). Допустим, что Сервер Состояния и Плана Движения Лифта, который получает сообщения от нескольких экземпляров Подсистемы Лифта, имеет период 10 мс и требует 2 мс для обновления объекта Сводное Состояние и План Движения Лифта. Из табл.2 видно, что коэффи­циент использования ЦП в узле Планировщика равен 0,6 - меньше порога 0,69, который дает теорема о верхней границе.

Сетевые задержки составляют 2 мс. Время, затраченное на последовательность событий оста­новка Лифта на Этаже, равно 41 мс, что меньше 50 мс. Время, затраченное на последователь­ность событий Выбор Этажа Назначения, равно 48 мс, что меньше 100 мс. Время, затраченное на последовательность событий вызов Лифта, составляет 82 мс, что меньше 200 мс.

Рис.37. Последовательность событий в распределенной подсистеме лифта

 

Рис.38. Последовательность событий в распределенной системе управления лифтом

 

 

Рис.39. Последовательность событий для подсистемы планировщика

 

 

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

Рассмотрим три критические последовательности событий для распределенной конфигурации (см. рис.37-39).

Последовательность событий «Остановка Лифта на Этаже» (период = Т_а):

А1: Интерфейс Датчиков Прибытия получает и обрабатывает прерывание.

А2: Интерфейс Датчиков Прибытия посылает Контроллеру Лифта сооб­щение приближается к Этажу.

A3: Контроллер Лифта принимает сообщение и проверяет объект Локаль­ное Состояние и План Движения Лифта, чтобы определить, должен ли лифт сделать остановку.

А4: Контроллер Лифта вызывает операцию остановить Мотор, если лифту нужно остановиться.

А5: Контроллер Лифта отправляет по сети сообщение прибыл подсистеме Планировщик, а принимает его Сервер Состояния и Плана Движения Лифта.

А6: Сервер Состояния и Плана Движения Лифта вызывает операцию при­был объекта Сводное Состояние и План Движения Лифта.

Последовательность событий «Выбор Этажа Назначения» (период = Т_b):

Е1: Интерфейс Кнопок Лифта получает и обрабатывает прерывание.

Е2: Интерфейс Кнопок Лифта посылает Диспетчеру Лифта сообщение за­прос Лифта.

ЕЗ: Диспетчер Лифта получает сообщение и записывает этаж назначения в объект Локальное Состояние и План Движения Лифта.

Е4: Диспетчер Лифта отправляет по сети сообщение обязательство Лиф­та подсистеме Планировщик, где его принимает Сервер Состояния и Пла­на Движения Лифта.

Е5: Сервер Состояния и Плана Движения Лифта вызывает операцию об­новить План объекта Сводное Состояние и План Движения Лифта.

Последовательность событий «Вызов Лифта» (период = Т_с):

F1: Интерфейс Кнопок Этажа получает и обрабатывает прерывание.

F2: Интерфейс Кнопок Этажа посылает по сети Планировщику сообщение запрос на Обслуживание, адресуя его задаче Планировщик Лифта в подсис­теме Планировщик.

F3: Планировщик Лифта принимает сообщение и опрашивает объект Свод­ное Состояние и План Движения Лифта с целью определить, едет ли какой-нибудь лифт на данный этаж. Если не едет, то Планировщик должен выбрать лифт.

F4: Планировщик Лифта отправляет по сети сообщение запрос Планиров­щика задаче Диспетчер Лифта, размещенной в узле выбранного лифта.

F5: Диспетчер Лифта получает сообщение и записывает этаж назначения в объект Локальное Состояние и План Движения Лифта.

F6: Диспетчер Лифта передает по сети сообщение обязательство Лифта подсистеме Планировщик, где его принимает Сервер Состояния и Плана Движения Лифта.

F7: Сервер Состояния и Плана Движения Лифта вызывает операцию об­новить План объекта Сводное Состояние и План Движения Лифта.

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

В эту последовательность событий входят только задачи из Подсистемы Лиф­та и Подсистемы Планировщика (см. рис.37-39). Сначала опишем Подсистему Лифта.

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

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

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

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

– вытеснение более приоритетными задачами с большими периодами. Возмож­но вытеснение на 3 мс задачей Интерфейс Кнопок Лифта, обрабатывающей прерывание. Время вытеснения С_р = 3 мс, а соответствующий коэффициент использования U_p = 3 / 50 = 0,06;

– время блокировки задачами с более низким приоритетом. Вероятна блоки­ровка на 6 мс задачей Диспетчер Лифта. Время блокировки В_а в худшем случае равно 6 мс, а коэффициент использования U_b = В_а / Т_а = 6 / 50 = 0,12.

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

Суммарное затраченное время = время выполнения + время вытеснения + + время блокировки в худшем случае = 7 + 3 + 6= 16 мс, что меньше периода, равного 50 мс.

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

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

Подсчитаем время, необходимое для обработки сообщения (А5), поступающе­го по сети, с учетом сетевых задержек:

А5: Контроллер Лифта посылает по сети сообщение прибыл подсистеме Пла­нировщик. Предположим, что размер сообщения, включая заголовки комму­никационного протокола, равен 25 байтам, или 200 битам. При скорости пере­дачи 100 Мбит/с сетевая задержка составит D_t = 200 / 100000 = 2 мс.

Рассмотрим далее подсистему Планировщик (рис.39):

А5.1: Задача Сервер Состояния и Плана Движения Лифта получает сооб­щение. Допустим, что время на прием и обработку сообщения, посланного по сети, С_m = 1 мс.

А6: Задача Сервер Состояния и Плана Движения Лифта вызывает опера­цию прибыл объекта Сводное Состояние и План Движения Лифта, на вы­полнение которой уходит С_а = 2 мс.

Время возможной блокировки при доступе к объекту со стороны задачи Планировщик Лифта b_s = 20 мс.

Время Е_u, затраченное подсистемой Планировщик в худшем случае, составит C_m + C_s + B_s = 1 + 2 + 20 = 23 мс.

Приняв во внимание обе подсистемы и сетевые задержки, мы можем вычис­лить время Е_а, потраченное на обработку последовательности событий Остановка Лифта на Этаже в худшем случае.

Е_а = время Е_е, потраченное Подсистемой Лифта, + сетевая задержка D_t + время Е_u, потраченное подсистемой Планировщик на обновление объекта Сводное Состояние и План Движения Лифта.

Подстановка значений дает Е_а = 16 + 2 + 23 = 41 мс.

Таким образом, оценка максимального времени (41 мс) оказывается меньше требуемого времени реакции (50 мс). На самом деле время на обработку сообщения прибыл некритично. Важно лишь вовремя остановить мотор, что вполне достижимо.

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

В обработке последовательности событий Выбор Этажа Назначения также принимают участие только задачи из Подсистемы Лифта и Подсистемы Планировщика (см. рис.37-39). Сначала рассмотрим Подсистему Лифта.

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

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

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

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

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

– время блокировки задачами с более низким приоритетом. Время блокировки нулевое, так как все задачи в Подсистеме Лифта уже были учтены при рассмотрении времени вытеснения и времени выполнения.

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

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

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

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

В этой последовательности событий задача Диспетчер Лифта посылает по сети сообщение обязательство Лифта задаче Планировщик. Она рассматрива­ется так же, как сообщение прибыл в предыдущем разделе: имеется дополнительная сетевая задержка 2 мс (событие Е4), и в худшем случае для обновления объекта Сводное Состояние и План Движения Лифта задачей Сервер Состояния и Плана Движения Лифта (событие Е5) требуется Е_u = 23 мс.

Общее время Е_b, потраченное на обработку последовательности событий Выбор Этажа Назначения в худшем случае, вычисляется так:

Е_b = время Е_е, потраченное Подсистемой Лифта, + сетевая задержка D_t + вре­мя Е_u, потраченное подсистемой Планировщик на обновление объекта Сводное Состояние и План Движения Лифта.

Подстановка значений дает Е_а = 23 + 2 + 23 = 48 мс.

Таким образом, оценка максимального времени (48 мс) оказывается намного меньше требуемого времени реакции (100 мс).

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

В обработке последовательности событий Вызов Лифта принимают участие задачи из нескольких распределенных подсистем (см. рис.37-39). Хотя, как показано выше, полный коэффициент использования ЦП в каждом узле не выходит за допустимые пределы, необходимо удостовериться, что затраченное время не превышает заданного предельного значения. Нужно применить теорию планирования в реальном времени к каждому узлу, учитывая параметры, приведенные в табл.2. Период последовательности событий Т_с = 200 мс.

Сначала рассмотрим Подсистему Этажа:

F1: Задача Интерфейс Кнопок Этажа получает и обрабатывает прерывания. В своей подсистеме эта задача имеет наивысший приоритет, так что вытеснить ее никто не в состоянии. Блокировка также не может произойти. Время вы­полнения C_f = 4 мс.

F2: Задача Интерфейс Кнопок Этажа посылает сообщения. Накладные расходы на подготовку сообщения к отправке С_m = 1 мс.

Полное время, потраченное Подсистемой Этажа, E_f = C_f + C_m = 4 + 1 = 5мс. Далее учтем сетевые задержки:

F2.1: Сообщение запрос на Обслуживание посылается по сети подсистеме Планировщик. Предположим, что размер сообщения, включая заголовки протокола, равен 25 байтам, или 200 битам. При скорости передачи 100 Мбит/с сетевая задержка составит D_t = 200 / 100000 = 2 мс.

Теперь разберем подсистему Планировщик:

F2.2: Задача Планировщик Лифта получает сообщение. Допустим, что время на прием и обработку сообщения, посланного по сети, С = 1 мс.

F3: Планировщик Лифта спрашивает у объекта Сводное Состояние и План Движения Лифта, едет ли на данный этаж какой-нибудь лифт. Если нет, то Планировщик Лифта выбирает лифт и посылает Диспетчеру Лифта сооб­щение запрос Планировщика, на что уходит C_s = 20 мс. Предположим, что для подготовки сообщения к отправке требуется С_m = 1 мс.

Время возможной блокировки при доступе к объекту со стороны задачи Сер­вер Состояния и Плана Движения Лифта b_s = 2 мс.

Время E_s, затраченное подсистемой Планировщик в худшем случае, равно C_m + C_s + C_m+ B_s = 1 + 20 + 1 + 2 = 24 мс.

Учтем сетевые задержки:

F3.1: Сообщение запрос на Обслуживание посылается по сети подсистеме Планировщик. Как и раньше, сетевая задержка D_t = 2 мс.

Проанализируем подсистему Лифт (рис.37):

F4: Задача Диспетчер Лифта получает и обрабатывает сообщение запрос Планировщика, С_m = 1 мс.

F5: Диспетчер Лифта сохраняет этаж назначения в объекте Локальное Состояние и План Движения Лифта. Время ЦП С_е, потраченное на выполнение шагов F4 и F5, равно 6 мс.

F6: Диспетчер Лифта посылает сообщение обязательство Лифта подсис­теме Планировщик. Время на подготовку сообщения С_m = 1 мс.

Итак, на выполнение задачи Диспетчер Лифта уходит С_m + С_е + С_m = 1 + 6 + 1 = 8 мс.

В Подсистеме Лифта возможны следующие задержки:

– время вытеснения. Каждая из задач Интерфейс Датчиков Прибытия и Кон­троллер Лифта может выполняться по одному разу, но не более 7 мс. Задачи Интерфейс Кнопок Лифта и Диспетчер Лифта (обработка сообщений от кнопок лифта) способны выполняться по одному разу, но не более 9 мс;

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

Время Е_e, потраченное Подсистемой Лифта в худшем случае, равно сумме времени выполнения и полного времени вытеснения, то есть 16 + 8 = 24мс.

Еще 2 мс уходит на сетевые задержки (событие F6.1). Как и раньше, в худшем случае для обновления объекта Сводное Состояние и План Движения Лифта задачей Сервер Состояния и Плана Движения Лифта (событие F7) требуется Е =23мс.

С учетом всех трех подсистем и сетевых задержек на обработку последовательности событий Вызов Лифта в худшем случае нужно:

E_t = время Е_р потраченное Подсистемой Этажа, + сетевая задержка D_t + время, потраченное подсистемой Планировщик на выбор лифта, + сетевая задержка D_t + время Е_е, потраченное Подсистемой Лифта, + сетевая задержка D_t + время Е_u, потраченное подсистемой Планировщик на обновление объекта Сводное Состояние и План Движения Лифта.

Подстановка значений дает E_t = 5 + 2 + 24 + 2 + 24 + 2 + 23 = 82 мс.

Таким образом, оценка максимального времени (82 мс) на обработку последо­вательности событий Вызов Лифта оказывается намного меньше требуемого времени реакции (200 мс). Даже если бы сетевая задержка при передаче каждого сообщения равнялась 10, а не 2 мс, общее затраченное время составило бы всего 106 мс.