Full Text

На однопроцессорном вычислительном устройстве может выполняться несколько задач реального времени (РВ). Каждой задаче соответствует свое ограничение РВ, которое накладывается на характеристики процесса выполнения этой задачи. Тогда проблема планирования задач РВ состоит в том, чтобы разделить процессорное время между этими задачами, обеспечив гарантированное соблюдение ограничений жесткого РВ и требуемый уровень качества по критериям мягкого РВ. Основные классические методы планирования задач РВ основаны на простой модели, в которой периодические задачи РВ имеют стандартные ограничения (СО) в виде смещения, периода и крайнего срока [1, 2]. Но получаемое СО несет в себе излишнюю жесткость за счет такого упрощенного подхода [3, 4, 5]. Например, ограничение на строгую периодичность опроса датчика в ряде случаев может быть существенным образом ослаблено без особого ущерба для качества управления. А это, в свою очередь, ведет к более эффективному использованию вычислительного устройства (можно больше задач выполнить на нем). Поэтому большое значение приобретают исследования, связанные с расширением классической модели ограничений РВ и выходом за пределы класса СО, то есть с переходом к нестандартным ограничениям реального времени. В работе [6] с учетом ряда допущений дано определение обобщенного нестандартного ограничения. В классе таких ограничений был выделен более узкий класс линейных интервальных ограничений (ЛИО), для которого становится возможным разрабатывать универсальные и достаточно эффективные алгоритмы планирования. Так, в работах [7, 8] были предложены решения, позволяющие осуществлять планирование задач РВ для класса ЛИО. Этот класс является расширением класса СО и позволяет реализовать более свободное распределение выполнения задач по шкале времени (в отличие от жесткой привязки в случае СО). В частности, в работе [7] предложен алгоритм, преобразующий заданное исходное ограничение из класса ЛИО в допустимое СО или сообщающий о невозможности такого преобразования. В данном случае СО называется допустимым, если его соблюдение гарантирует соблюдение исходного ЛИО. Предложенный алгоритм состоит из этапов: 1) получение достаточного условия допустимости СО (в дальнейшем для краткости указание на достаточность опускается); 2) выбор допустимого СО либо сообщение о невозможности такого выбора. Данные этапы реализованы на основе соответствующих алгоритмов. Предлагается более подробно рассмотреть алгоритм получения условия допустимости СО, что важно для эффективной программной реализации данного алгоритма в составе инструментальных средств, обеспечивающих планирование задач РВ. С этой целью будет реализован пошаговый разбор выполнения этого алгоритма для примеров ограничений из класса ЛИО. При этом сначала вводятся модель планирования и определение ЛИО, а также воспроизводится указанный алгоритм из работы [7]. Модель планирования Планирование выполняется для одного процессора. Есть множество из n задач жесткого РВ {t1, ..., tn}. Каждая задача ti формирует запросы. Каждый v-й запрос, обозначаемый ti,v, формируется в момент времени ri,v. Для любой периодической задачи ti при "v ³ 1 всегда выполняется соотношение ri,v = Oi + (v - 1)Ti, где Oi – начальное смещение; Ti – период. Задача ti может иметь СО в виде условия fi,v £ ri,v + Di, где fi,v – время завершения выполнения ti,v; Di – крайний срок ti. СО периодической задачи ti удобнее представлять в виде условия (1) где si,v – время начала выполнения ti,v; Oi*, Ti* – параметры СО, и Oi* ³ 0, Ti* > 0. Здесь и далее предполагается, что условие, задающее ограничение РВ, должно соблюдаться при "v ³ 1. В случае СО периодической задачи предполагается установка параметров Oi, Ti согласно очевидным соотношениям Oi = Oi*, Ti = Ti*. При выполнении ti,v кроме si,v, fi,v можно выделить еще два значимых момента времени xi,v, yi,v, при этом si,v £ xi,v < yi,v £ fi,v. Например, в момент xi,v происходит получение информации, а в момент yi,v – формирование управляющего воздействия. Тогда с ti,v связано 4 момента времени: si,v, xi,v, yi,v, fi,v, и существует 6 различных компонентов ti,v с соответствующими длительностями. Для каждого компонента определяется нижняя и верхняя оценка длительности его выполнения. Поэтому считается, что известны 12 оценок: CsxiLo, CsxiUp, CsyiLo, CsyiUp, CsfiLo, CsfiUp, CxyiLo, CxyiUp, CxfiLo, CxfiUp, CyfiLo, CyfiUp, где CsxiLo, CsxiUp – нижняя и верхняя оценки длины интервала [si,v, xi,v] по "v ³ 1 при отсутствии прерываний ti,v; другие оценки определяются аналогично. Преимущества разделения запроса на подобные компоненты указаны в работе [9]. Класс линейных интервальных ограничений Линейное интервальное ограничение (ЛИО) для задачи ti, обозначаемое Xi, – это ограничение, представимое при "v ³ 1 в виде условия (2) где xyi,v – длина интервала [xi,v, yi,v]; – минимальные и максимальные значения интервалов допустимых значений xi,v, yi,v, xyi,v соответственно; w1, ..., w6 задают число вариантов; , , , , , обозначают w-й вариант соответствующих значений, и каждый из вариантов – это или –¥ (может быть только после «³»), или ¥ (может быть только после “£”), или выражение, представимое в виде , (3) где kamax, kbmax – целые неотрицательные значения; ak при "k Î [1, kamax], bk при "k Î [1, kbmax], g, d – константы, заданные для данного варианта; при этом все xi,v-k, yi,v-k для v – k £ 0, встречающиеся в выражениях вида (3), являются константами, заданными для данного Xi. Множество всех возможных ЛИО формирует одноименный класс. Алгоритм получения условия допустимости Здесь для удобства читателя приводится алгоритм 1 из работы [7]. Алгоритм 1. Получение условия допустимости СО для любого ЛИО. Шаг 1. В условие (2) данного ЛИО Xi вместо xi,v в 1-м и 2-м неравенствах, yi,v в 3-м и 4-м неравенствах, xyi,v в 5-м и 6-м неравенствах соответственно подставляются следующие выражения: Oi* + (v - 1)Ti* + CsxiLo, Oi* + (v - 1)Ti* + Di - CxfiLo, Oi* + (v - 1)Ti* + CsyiLo, Oi* + (v - 1)Ti* + Di - CyfiLo, CxyiLo, Di - CyfiLo - CsxiLo. Каждое полученное неравенство заменяется эквивалентной совокупностью неравенств, имеющих в правой части только один компонент из соответствующего оператора max или min согласно принципу: неравенство a ³ max(b1, ..., bw) заменяется неравенствами a ³ b1, ..., a ³ bw, а неравенство a £ min(b1, ..., bw) заменяется неравенствами a £ b1, ..., a £ bw. Затем удаляются неравенства, правая часть которых представляет собой -¥ или ¥. Шаг 2. Переменная v* делается равной такому минимальному значению v среди "v ³ 1, при котором в составе выражений вида (3) всех неравенств значения xi,v-k, yi,v-k для v – k < 1 не используются или умножаются на 0. Шаг 3. Устанавливается z = 1, где z – вспомогательная переменная. Шаг 4. В каждом из неравенств совокупности, полученной в результате шага 1, у каждого значения xi,v-k, yi,v-k в составе выражений вида (3) правой части неравенства индекс v - k заменяется числом z - k. Все значения xi,z-k, yi,z-k при z - k £ 0 известны заранее согласно определению ЛИО. Поэтому вместо них подставляются соответствующие значения. В каждом неравенстве, полученном в результате шага 1, каждое xi,z-k, yi,z-k при z - k > 0 из правой части неравенства заменяется своей нижней или верхней оценкой. Выбор в пользу нижней или верхней оценки делается так, чтобы неравенство, полученное после подстановки оценки, было достаточным условием выполнения исходного неравенства. В качестве нижней и верхней оценки xi,z-k соответственно применяются выражения Oi* + (v - k - 1)Ti* + CsxiLo, Oi* + (v - k - 1)Ti* + Di - CxfiLo. В качестве нижней и верхней оценки yi,z-k соответственно применяются выражения Oi* + (v - k - 1)Ti* + CsyiLo и Oi* + (v - k - 1)Ti* + Di - CyfiLo. Шаг 5. Вместо переменной v в каждом из неравенств совокупности, полученной на предыдущем шаге, подставляется значение z. Шаг 6. Если z < v*, то устанавливается z = z + 1 и делается переход к шагу 4. Шаг 7. Каждое неравенство совокупности, полученной в результате шага 4 для z = v*, за счет перегруппировки слагаемых преобразуется к виду j1v + j2 ³ 0, где j1, j2 – компоненты, которые не зависят от v. Затем каждое такое неравенство заменяется неравенством j1 ³ 0. Шаг 8. Формируется условие допустимости в виде системы неравенств на основе объединения совокупностей неравенств, полученных в результате всех выполнений шага 5, а также совокупности неравенств, полученной в результате шага 7. Алгоритм завершается. Примеры исходных линейных интервальных ограничений К классу ЛИО относится ограничение задачи контура управления (ЗКУ), определяемое условием (4) где Tixx min, Tixx max, Tixy max – константы; при этом заранее устанавливается значение xi,0. Это ограничение является обобщением ограничения, определенного в п. 5.2 работы [10], при условии, что измерение и управляющее воздействие осуществляются одной задачей. Обобщение состоит в использовании xi,v, yi,v вместо si,v, fi,v, естественно, после перехода к обозначениям, применяемым здесь. В ограничении ЗКУ (4) также можно добавить условие, ограничивающее , где mi – константа, и mi > 1. Тогда ограничение на xi,v - xi,v-1 может быть ослаблено за счет надлежащего подбора допустимого диапазона для , что ограничит интервал между соседними моментами xi,v, усредненный по mi интервалам. Такое уточнение способствует повышению эффективности планирования. Полученное ограничение будет называться ограничением задачи контура управления с усреднением интервала (ЗКУУИ), при этом оно принадлежит классу ЛИО и задается условием (5) где , , , , – константы; при этом заранее устанавливаются значения . Получение условия допустимости СО для ограничения ЗКУ Ограничение ЗКУ (4), будучи ЛИО, представимо в виде (2), т.е. в виде условия (6) В результате шага 1 алгоритма 1 на основе (6) формируется условие В правых частях неравенств в качестве xi,v-k, yi,v-k используется только xi,v-1, поэтому в результате шага 2 устанавливается v* = 2. При z = 1 в результате шага 4 формируется совокупность неравенств При z = 1 в результате шага 5 формируется совокупность неравенств (7) При z = v* = 2 по итогам шага 4 формируется совокупность неравенств При z = v* = 2 по итогам шага 5 формируется совокупность неравенств (8) Шаги 4 и 5 будут выполнены только по 2 раза, так как v*=2. В результате шага 7 формируется совокупность неравенств, каждое из которых – это неравенство 0≥0, очевидно, всегда выполняемое. Поэтому в ходе выполнения шага 8 данная совокупность может не учитываться. В результате шага 8 происходит объединение совокупностей неравенств (7), (8), что приводит к формированию системы неравенств (9) которая и будет условием допустимости СО для ограничения ЗКУ (4). Получение условия допустимости СО для ограничения ЗКУУИ Ограничение ЗКУУИ (5), будучи ЛИО, представимо в виде (2), т.е. в виде условия (10) В результате шага 1 алгоритма 1 на основе (10) формируется условие В правых частях неравенств в качестве xi,v-k, yi,v-k используются только и , поэтому в результате шага 2 устанавливается v*=mi +1. При z = 1 в результате шага 4 формируется совокупность неравенств При z = 1 в результате шага 5 формируется совокупность неравенств (11) Нетрудно убедиться, что при каждом z от 2 до mi в результате шага 5 формируется совокупность неравенств вида (12) где при – это константы в составе ограничения ЗКУУИ (5). При z = v* = mi + 1 после шага 4 формируется совокупность неравенств При z=v*=mi +1 после шага 5 формируется совокупность неравенств (13) Шаг 4 и шаг 5 будут выполнены mi + 1 раз, так как v*=mi + 1. В результате шага 7 формируется совокупность неравенств, каждое из которых – это неравенство 0 ≥ 0, очевидно, всегда выполняемое. Поэтому в ходе выполнения шага 8 данная совокупность может не учитываться. По итогам шага 8 происходит объединение совокупностей неравенств (11), (13) и всех совокупностей неравенств вида (12) для "zÎ[2, mi]. При этом для краткости записи результата схожие неравенства объединяются с помощью min и max. Поэтому можно считать, что в результате шага 8 формируется система неравенств (14) которая и будет условием допустимости СО для ограничения ЗКУУИ (5). Заключение В статье подробно рассмотрены особенности применения алгоритма 1 из работы [7] для двух примеров ЛИО. Этот алгоритм формирует условие допустимости СО для заданного ЛИО, и он является одной из двух составных частей алгоритма, преобразующего исходное ЛИО в допустимое СО. В результате разбора примеров получены условия допустимости (9), (14) для примеров ЛИО (4), (5) соответственно. Рассмотренные примеры важны для исследования возможностей эффективной программной реализации указанного алгоритма в составе инструментальных средств, обеспечивающих планирование задач РВ.

About the authors

Maksim Vladimirovich Kavalerov

Email: mkavalerov@gmail.com

Nikolay Nikolaevich Matushkin

Email: uz@at.pstu.ru

References

Statistics

Views

Abstract - 49

PDF (Russian) - 15

Refbacks

• There are currently no refbacks.