Содержание к диссертации
Введение
1. Проблема планирования задач с нестандартными ограничениями реального времени 11
1.1. Общие сведения 11
1.1.1. Функционирование в реальном масштабе времени 11
1.1.2. Планирование задач реального времени 12
1.1.3. Основные концепции планирования 14
1.1.3.1. Табличное планирование 14
1.1.3.2. Планирование с фиксированными приоритетами 14
1.1.3.3. Планирование с динамическими приоритетами 15
1.2. Базовая модель 16
1.2.1. Общие положения 16
1.2.2. Задачи жесткого реального времени 16
1.2.3. Диспетчеризация 19
1.2.4. Планирование 20
1.2.4.1. Общие положения 20
1.2.4.2. Стандартное ограничение реального времени 22
1.2.4.3. Планирование при наличии только стандартных ограничений 25
1.2.5. Эффективность планирования 30
1.3. Нестандартные ограничения реального времени в условиях планирования с фиксированными приоритетами 32
1.3.1. Исходные, допустимые, нестандартные ограничения реального времени 32
1.3.2. Примеры нестандартных ограничений 32
1.3.2.1. Ограничение задачи контура управления 32
1.3.2.2. Ограничение задачи отслеживания событий 34
1.3.3. Краткий обзор исследований, связанных с нестандартными ограничениями 35
1.3.4. Базовый подход к планированию при наличии нестандартных ограничений 37
1.3.5. Повышение эффективности планирования за счет непосредственного применения нестандартных ограничений 37
1.4. Выводы по главе 1 42
2. Выделение класса нестандартных ограничений и реализация базового подхода 43
2.1. Необходимость выделения класса нестандартных ограничений .43
2.2. Значимые моменты времени запроса 43
2.3. Дополнительные примеры нестандартных ограничений 44
2.3.1. Ограничение задачи контура управления 44
2.3.2. Ограничение задачи отслеживания событий 45
2.3.3. Ограничение задачи контура управления с усреднением интервала 46
2.4. Базовые допущения 49
2.5. Класс линейных интервальных ограничений 50
2.5.1. Определение линейного интервального ограничения 50
2.5.2. Примеры линейных интервальных ограничений 53
2.5.3. Другие примеры линейных интервальных ограничений 55
2.5.4. Стандартное ограничение периодической задачи как линейное интервальное ограничение 55
2.6. Длительности компонентов запроса с учетом значимых моментов времени 56
2.7. Преобразование нестандартного ограничения из выделенного класса в допустимое стандартное ограничение 58
2.7.1. Общие положения 58
2.7.2. Алгоритм формирования условия допустимости 58
2.7.3. Получение условий допустимости для различных примеров нестандартных ограничений 61
2.7.3.1. Условие допустимости в случае нестандартного ограничения задачи контура управления 61
2.7.3.2. Условие допустимости в случае нестандартного ограничения задачи отслеживания событий 63
2.7.3.3. Условие допустимости в случае нестандартного ограничения задачи контура управления с усреднением интервала 64
2.7.4. Формирование допустимого стандартного ограничения на основе условия допустимости 67
2.8. Базовый подход к планированию при наличии нестандартных ограничений из выделенного класса 73
2.9. Выводы по главе 2 74
3. Разработка алгоритмов планирования при непосредственном применении нестандартных ограничений из выделенного класса 75
3.1. Применение нестандартных ограничений в ходе анализа выполнимости (подход А) 75
3.2. Оценки параметров выполнения запросов 76
3.3. Вычисление оценок параметров выполнения запросов 78
3.4. Алгоритм формирования условия выполнимости 82
3.5. Получение условий выполнимости для примеров нестандартных ограничений 85
3.5.1. Условие выполнимости в случае нестандартного ограничения задачи контура управления 85
3.5.2. Условие выполнимости в случае нестандартного ограничения задачи отслеживания событий 87
3.5.3. Условие выполнимости в случае нестандартного ограничения задачи контура управления с усреднением интервала 88
3.6. Получение условия выполнимости для стандартного ограничения 91
3.7. Алгоритм А ; 93
3.8. Применение нестандартных ограничений в ходе анализа выполнимости и при формировании периода (подход АП) 96
3.9. Формирование максимально допустимого периода для каждой задачи, имеющей нестандартное ограничение 98
3.10. Алгоритм АП 100
3.11. Эффективность разработанных алгоритмов 101
3.12. Выводы по главе 3 103
4. Применение разработанных алгоритмов планирования 104
4.1. Оценка эффективности разработанных алгоритмов планирования на основе имитационного моделирования 104
4.1.1. Цель и методика имитационного моделирования ...104
4.1.2. Результаты имитационного моделирования ..106
4.1.2.1. Эксперимент 1 106
4.1.2.2. Эксперимент 2 108
4.1.2.3. Эксперимент 3 109
4.1.2.4. Эксперимент 4 111
4.1.2.5. Общие выводы по результатам экспериментов 113
4.2. Применение разработанных алгоритмов при проектировании программного обеспечения системы автоматизации испытаний 114
4.2.1. Общие сведения 114
4.2.2. Характеристика видов обеспечения системы 115
4.2.3. Проектирование программного обеспечения. 116
4.2.3.1. Общие сведения 116
4.2.3.2. Характеристики задач реального времени 117
4.2.3.3. Применение разработанного алгоритма планирования .118
4.3. Выводы по главе 4 120
Заключение 121
Библиографический список 122
Приложение А 128
- Стандартное ограничение реального времени
- Ограничение задачи контура управления с усреднением интервала
- Вычисление оценок параметров выполнения запросов
- Применение разработанного алгоритма планирования
Введение к работе
В системах автоматизации и управления (САиУ) отдельное вычислительное устройство (ВУ) часто выполняет несколько задач реального времени (РВ). Каждой такой задаче соответствует свое ограничение РВ, которое накладывается на характеристики процесса выполнения запросов, формируемых этой задачей. Необходимо осуществлять планирование множества задач, т. е. разделение процессорного времени между запросами различных задач при условии соблюдения ограничений РВ. Более эффективное планирование позволяет соблюдать более жесткие ограничения при данных аппаратно-программных средствах. Например, реализуется более строгая периодичность опроса датчиков, уменьшаются задержки при формировании управляющих воздействий. Зачастую это означает повышение качества управления. Более эффективное планирование также снижает требования к быстродействию ВУ, что обеспечивает снижение затрат и уменьшение срока окупаемости САиУ.
Широкое распространение получила концепция планирования с фиксированными приоритетами (ПФП), обеспечивающая компромисс между предсказуемостью и гибкостью планирования. В стандартной модели ПФП каждая задача жесткого реального времени (ЖРВ) имеет только стандартное ограничение (СО), которое выражается с помощью начального смещения и периода формирования запросов данной задачи, а также крайнего срока выполнения запроса относительно момента его появления. Однако известно, что многие задачи ЖРВ в составе САиУ изначально имеют ограничения, которые не являются СО, т. е. являются нестандартными ограничениями (НО). Примером задач с НО часто являются задачи, реализующие контуры управления. В ряде исследований, в частности, в работах таких авторов, как G. Fohler и М. Tongren, подчеркивается широкая распространенность задач с НО в составе САиУ.
Планирование задач РВ является сложной проблемой при наличии НО. В условиях ПФП эта проблема формулируется следующим образом. Требуется установить параметры каждой задачи РВ (а именно, начальное смещение, период и приоритет) так, чтобы гарантировать соблюдение всех СО и НО при выполнении данного множества задач. Сложность проблемы зависит от предполагаемых видов НО, т. е. от целевого класса НО.
Базовый (или традиционный) подход к решению данной проблемы состоит в том, что каждое НО преобразуется в допустимое (или вторичное) СО, т. е. такое СО, что его соблюдение означает соблюдение данного НО. Затем, планирование осуществляется известными методами, предназначенными только для СО. Однако для каждого вида НО надо уметь определять допустимое СО.
Эффективность планирования можно повысить, если планирование задач осуществлять при непосредственном применении НО вместо того, чтобы каждое НО заменять допустимым СО. Известны подобные решения проблемы для некоторых целевых классов НО. В частности, можно отметить работы таких исследователей, как R. Dobrin, G. Fohler, P. Puschner, W. Wang, A.K. Mok, К. Sandstrom, С. Norstrom. Однако, в случае каждого из известных решений, целевой класс не включает многие НО, характерные для САиУ.
Таким образом, актуальной является проблема разработки алгоритмов планирования, обеспечивающих в условиях ПФП соблюдение НО, характерных для САиУ, но не входящих в целевые классы известных подходов.
Для решения данной проблемы, очевидно, надо выделить класс таких НО. Тогда применительно к базовому подходу все сводится к проблеме разработки алгоритма преобразования любого НО из этого класса в допустимое СО. В случае же непосредственного применения НО надо уметь формировать условие выполнимости задачи РВ с любым НО из указанного класса, а также следует осуществлять планирование с использованием этих условий для гарантирования того, что все НО будут соблюдаться.
Целью работы является разработка алгоритмов планирования задач РВ применительно к концепции ПФП для класса НО, встречающихся в САиУ.
Достижение поставленной цели обеспечивается решением в диссертационной работе следующих задач:
1) выделить класс НО, встречающихся в САиУ, но не входящих в целевые классы известных подходов, при этом определение класса не должно быть слишком общим, чтобы можно было разрабатывать алгоритмы планирования, применимые для задач РВ с любыми НО из данного класса;
2) разработать алгоритм преобразования любого НО из выделенного класса в допустимое СО, что требуется для реализации базового подхода к планированию при наличии НО в условиях ПФП;
3) разработать алгоритм формирования условия выполнимости задачи РВ с любым НО из выделенного класса;
4) разработать алгоритм планирования при непосредственном применении любых НО из выделенного класса;
5) оценить эффективность разработанных алгоритмов на основе имитационного моделирования процесса планирования задач РВ.
Научная новизна работы заключается в решении проблемы планирования задач при наличии НО в условиях ПФП. При этом основные отличия настоящей работы от близких по тематике состоят в следующем.
1) Рассматривается широкий класс НО, встречающихся при разработке САиУ, и он назван классом линейных интервальных ограничений (ЛИО). Данный класс содержит многие НО, которые не входят в целевые классы НО известных подходов.
2) Снимается упрощение, состоящее в том, что действия, на которые накладывается НО, обязательно совпадают с началом или завершением выполнения запроса, формируемого задачей РВ. В результате появляется возможность более точно оценивать соблюдение ограничений РВ.
3) Разработаны алгоритмы, обеспечивающие планирование задач в условиях ПФП при любых ЛИО. При этом реализован как базовый подход к планированию задач РВ, так и подход, основанный на непосредственном применении НО в процессе планирования. 4) В ходе имитационного моделирования процесса планирования задач РВ получены оценки повышения эффективности планирования при непосредственном применении ЛИО по сравнению с базовым подходом, основанным на формировании допустимых СО.
Достоверность приводимых в работе результатов и выводов обеспечивается: формальными доказательствами справедливости утверждений, характеризующих получаемые результаты, а также корректным применением методов математической логики, теории планирования задач РВ, теории множеств, теории вычислительной сложности.
Основное содержание диссертации отражено в 11 публикациях [26,27, 64 - 72]. Результаты, полученные в ходе работы над диссертацией, докладывались на 5 конференциях, относящихся к международным, всероссийским, межвузовским.
Работа состоит из введения, четырех глав, заключения, списка литературы и приложений.
Стандартное ограничение реального времени
Важно отметить, что в ходе диспетчеризации ограничения ЖРВ непосредственно не могут учитываться при формировании запросов задач {т.,} и обслуживании этих запросов в основной очереди. Действительно, при выполнении алгоритма формирования запросов задач {т,} учитываются только значения Oh Tt для каждой периодической задачи или информация о внешних событиях для каждой спорадической задачи. При выполнении алгоритма обслужи вания основной очереди принимается во внимание только множество {я,-}. Таким образом, учитывается только множество {Оі,Ті,%і \ і є [1, л]}.
Пусть множество {Oi,Ti,nl \ie[l,n]} для краткости обозначается ОТп. Множество OTiz порождает некоторую совокупность возможных вариантов выполнения запросов задач {х,}. Различия между вариантами определяются: возможными вариациями значений С/ у-; различными последовательностями внешних событий, соответствующих спорадическим задачам; различными последовательностями апериодических запросов. Если в случае каждого из этих вариантов соблюдаются все ограничения ЖРВ задач {т,}, то при данном множестве ОТк гарантируется соблюдение всех ограничений ЖРВ задач {х,}. Определение 1.1. Задача х,- является выполнимой, если гарантируется соблюдение ограничения РВ этой задачи при диспетчеризации. Кроме обеспечения выполнимости каждой задачи, необходимо также гарантировать ограниченность размера основной очереди, что требуется для практической реализации подсистемы планирования. С учетом этого формулируется следующее определение. Определение 1.2. Множество {х,} является выполнимым, если, во-первых, обеспечивается выполнимость каждой задачи из {х,}, во-вторых, гарантируется, что размер основной очереди всегда будет меньше некоторого конечного значения. На длительность запросов нельзя повлиять средствами подсистемы планирования, поэтому очевидно, что ограниченность размера очереди можно обеспечить только выбором значений {Ті \ і є [\,п]}. Тогда понятно, что для обеспечения выполнимости {х,} достаточно сформировать подходящие значения 0У, 7} для каждой периодической задачи и сформировать подходящее множество {л:,}. Формирование запросов спорадической задачи определяется не значениями О,, Th а внешними событиями, но в дальнейшем для краткости будет упоминаться формирование значений Oh Tt для каждой х,-, в том числе и спорадической. При этом, если х,- - это спорадическая задача, то предполагается, что Oj = О, и 7} - это заранее известный минимальный период формирования запросов данной задачи. Таким образом, до начала функционирования системы надо сформировать множество ОТп, обеспечивающее выполнимость {х,}, или прийти к выводу, что ни одного такого множества найти не удается. Именно для решения этой проблемы и предназначено планирование.
Сложность проблемы зависит от возможных видов НО,- т. е. от целевого класса НО. В частности, если в качестве НО могут быть ограничения на интервалы между соседними выполнениями запросов задачи, то тогда указанная проблема является NP-трудной [56, 58]. В подобных случаях практическим решением будет эвристический алгоритм планирования. Конкретная реализация такого алгоритма зависит от целевого класса НО, т. е. от вида имеющихся ограничений РВ. Поэтому для дальнейшего рассмотрения планирования надо выделить хотя бы один вид ограничений РВ.
Ограничение задачи контура управления с усреднением интервала
Обобщение можно рассматривать как модель НО. Но любая модель имеет допущения. Предлагаются следующие допущения и их обоснования. Допущение 1. Только периодические задачи ЖРВ имеют НО, т. е. спорадические задачи имеют только СО. Обоснование допущения 1. Это допущение делается для упрощения процесса обобщения НО, так как в случае рассмотрения НО для спорадических задач возникнет необходимость указания дополнительных параметров, в частности, более сложных ограничений на внешние события. Поэтому на данном этапе предлагается рассматривать НО только для периодических задач. При этом более сложное обобщение НО для спорадических задач может быть получено в ходе будущих исследований с использованием решений, найденных в процессе изучения НО для периодических задач. Допущение 2. НО для задачи т,- не зависит от выполнения других задач. Обоснование допущения 2. Во-первых, если не принимать это допущение, то на соблюдение НО для т,- могут влиять задачи с более низким приоритетом. В этом случае теряется одно из главных преимуществ ПФП, состоящее в том, что при анализе выполнения т,- не учитываются задачи с более низкими приоритетами. Во-вторых, без этого допущения проблема планирования задач предельно усложнится, так как допустимость различных вариантов выполнения запроса т,- придется оценивать не только по отношению к НО для х(, но и по тому, как они повлияют на выполнимость ограничений РВ других задач. Допущение 3. НО накладывается только на события, связанные с действиями, которые реализуются в ходе выполнения соответствующей задачи. Обоснование допущения 3. В общем случае НО может накладываться на события, которые нельзя напрямую отождествить с действиями, реализуемыми в ходе выполнения задачи. Например, в случае регулирования параметра объекта управления такими событиями могут быть момент считывания значения регулируемого параметра и момент воздействия управляющего воздействия на объект управления. Эти события связаны с соответствующими действиями при выполнении запросов задачи, например, с командой, инициирующей считывание значения регулируемого параметра, и с командой, вызывающей формирование управляющего воздействия. Но между указанными событиями и соответствующими действиями в общем случае могут быть некоторые недетерминированные задержки, которые, в частности, отражают особенности взаимодействия с устройствами связи с объектом. Поэтому в данном примере невозможно полностью отождествить указанные события с соответствующими действиями, реализуемыми в ходе выполнения задачи. Хотя допущение 3 исключает из рассмотрения подобные ситуации, во многих случаях несложно преобразовать НО так, чтобы оно накладывалось на действия, реализуемые в ходе выполнения задачи. Такое преобразование может быть осуществлено на основе учета верхних и нижних оценок недетерминированных задержек между действиями, реализуемыми в ходе выполнения задачи, и соответствующими событиями, на которые накладывается исходное НО. Принятие допущения 3 позволяет исключить из рассмотрения особенности взаимосвязей между указанными действиями и событиями, учитывая, что эти особенности приняты во внимание при составлении НО. Это дает возможность сосредоточиться на взаимосвязи между выполнением задачи и соблюдением НО, что позволяет упростить решение проблемы планирования задач с НО. В дальнейшем, в ходе будущих исследований, на основе уточнения результатов, полученных с использованием допущения 3 может быть рассмотрено планирование задач с НО без данного допущения. Допущение 4. НО накладывается только на события, соответствующие моментам времени x{j-, ytj. Обоснование допущения 4. В общем случае с выполнением запроса т,- . может быть связано сколь угодно много событий и соответствующих моментов времени, которые могут соотноситься с НО для задачи т,. Данное допущение позволяет рассматривать не более двух таких моментов времени в течение выполнения любого запроса. Если в ходе выполнения запроса существует менее двух событий, имеющих значение для НО, то все равно можно считать, что формально с НО связано два момента времени xt и yi . Действительно, если в НО явным образом не присутствует xt или yi , то это просто означает, что НО соблюдается при любом значении jc/y или yi . Таким образом, при рассмотрении НО необходимо учитывать не более двух моментов времени при выполнении запроса. Во-первых, это обеспечивает упрощение процесса обобщения НО и последующего планирования при наличии задач с НО. Тогда более сложное обобщение НО без данного допущения может быть рассмотрено, при необходимости, в ходе будущих исследований с использованием решений, найденных в процессе изучения НО с данным допущением. Во-вторых, во многих практических примерах (например, см. п. 1.3.2) в течение выполнения одного запроса имеется не более двух моментов времени, которые связаны с НО. Более того, представляется достаточно сложным найти практические примеры, которые не соответствуют данному допущению. Проблемы возможного устранения тех или иных базовых допущений оставляются для будущих исследований.
Вычисление оценок параметров выполнения запросов
Базовый подход (см. п. 2.8) позволяет обеспечить планирование при наличии любых НО из выделенного класса. Однако ранее было показано (см. п. 1.3.5), что эффективность планирования можно существенно повысить по сравнению с базовым подходом. Это объясняется тем, что при базовом подходе после преобразования исходных НО в допустимые СО часть информации об исходных НО теряется. Если хотя бы часть этой информации восстановить, то тогда станет возможным повысить эффективность планирования. Ведь эта информация позволит найти подходящий вариант планирования, который при ее отсутствии либо считается неподходящим, либо вообще не рассматривается.
В случае примера 1.1 из п. 1.3.5 очевидно, что эффективность планирования можно повысить, если анализ выполнимости задачи т, выполнять с применением исходного НО, а не допустимого СО. В общем случае такой подход может быть распространен на любой вариант {т,} при наличии НО из выделенного класса, и его можно определить следующим образом.
Предлагаемый подход состоит в следующем. Планирование выполняется аналогично базовому подходу (см. алгоритм 2.3) за исключением того, что в качестве входных данных алгоритма 1.1 применительно к задачам, имеющим исходные НО, используются алгоритмы анализа выполнимости, учитывающие информацию об исходных НО. Для краткости данный подход и алгоритм, его реализующий, будут иметь названия «подход А» и «алгоритм А», так как информация об исходных НО используется в анализе выполнимости, при этом буква «А» соответствует первой букве слова «анализ».
Основная проблема при реализации данного подхода состоит в том, что надо уметь формировать условие выполнимости для задачи с любым НО из выделенного класса. Это позволит реализовать алгоритм анализа выполнимости, учитывающий информацию об исходных НО, и соответственно реализовать подход А.
Известно условие выполнимости (1.7), однако оно подходит только для задач, имеющих СО. Таким образом, требуется разработать алгоритм формирования условия выполнимости, который будет универсальным по отношению к выделенному классу НО, т. е. он должен формировать условие выполнимости для задачи с любым ЛИО.Выполнение условия выполнимости (см. определение 1.3) для задачи, имеющей НО, означает, что при V/ 1 значения xt ., у{ , у( - xt удовлетворяют условию вида (2.5). Учитывая (1.3), значения xtj и ytj можно представить как Оt + (j-1)7} + (хи -ritj) и О,- + (J-1)7) + (уи -rtJ). При проверке условия выполнимости предполагается, что значения Ot, 7} уже известны. Поэтому, если известны правые части неравенств условия (2.5), то тогда для данного j можно гарантировать выполнение (2.5) при условии, что известны Пусть значения Up(xn), Lo(xx) - это соответственно верхняя оценка xff и нижняя оценка xf в составе (2.5). Пусть Up(xf), Lo{xf) известны для любого j. Тогда, очевидно, что первые два неравенства в составе (2.5) будут гарантированно выполняться, если выполняются условия О и-Щ+Щхи-г ьиріх), Oi+{j-\)Ti+Up{xUj-ru) Lo{x x), где Lo(Xjj -fjj), Up(xtj ri,j) эт0 соответственно нижняя и верхняя оценки значений Xj : - Tji для V/ 1. Нетрудно заметить сходство этих оценок с оценкой Up{fi,-rij), используемой в условии выполнимости (1.7) для задачи, имеющей СО. Для вычисления Up(fij - -,) существуют различные способы [37]. Можно предположить, что для вычисления LoiXjj-rjj), UpiXjj-r j) применимы похожие способы. Если заранее вычислить оценки Lo(Xj -fjj), Up(Xj : - rl j), то тогда при известных Up(xin), Lo(xJx) можно сформировать условия, выполнение которых гарантирует выполнение первых двух неравенств в составе (2.5). Аналогичные выводы справедливы для других неравенств и соответствующих ИМ НИЖНИХ И. Остается понять, как вычислять оценки правых частей неравенств. Согласно (2.6) правую часть любого неравенства в составе (2.5) можно для данного j оценить сверху или снизу, если вычислить нижние и верхние оценки значений вида xitj_k, yij-k Для У - 1 Подобные оценки при известных Oh Tt можно получить с помощью оценок значений Xj -_к - rjj_k, ytj-k - rij-k Например, нижней оценкой Если для У/ 1 определяется единое значение Lo(Xjj-rjj), то, очевидно, Lo(Xj j_k j :_к) = Lo(Xjj - rtj). Поэтому для получения оценок правых частей неравенств также достаточно вычислить оценки значений х/;- - rtj, ytj - rtj. Таким образом, для получения условия выполнимости требуется уметь ВЫЧИСЛЯТЬ НИЖНИе И Верхние ОЦеНКИ Значений Xjj - rtj , ytj - Г;j , yifj - Xjj . Эти значения характеризуют процесс выполнения запросов, поэтому их можно считать параметрами выполнения запроса. При выполнении запроса т(, в условиях ПФП рассматривается пять моментов времени (г,-у, &[}, xtJ, у/j, fij). Тогда получается, что существует всего десять различных пар, образуемых из этих моментов времени. Для общности каждая такая пара будет считаться параметром выполнения запроса.
Применение разработанного алгоритма планирования
Недостатком подхода А является то, что значения О,, Т( для каждой за-дачи, имеющей исходное НО, определяются через параметры О,, 7} допустимого СО. Однако при формировании значений О , Т (см. алгоритм 2.1, алгоритм 2.2} никак не учитываются другие задачи множества {т,}.
Действительно, нетрудно понять, что при выполнении алгоритма 2.1 для нижних оценок значений sxtj, xf(j, sy(j, yfjj, xytj используются значения что соответствует варианту, когда задача выполняется с наивысшим приоритетом, т. е. ее выполнение не зависит от других задач. В реальности только одна задача будет иметь наивысший приоритет. Тогда для других задач указанные нижние оценки будут слишком грубыми. Все это может привести к излишней жесткости условия допустимости сочетания (ОІ ,Tt ,Dj), и, как следствие, к сообщению о невозможности формирования допустимого СО при последующем выполнении алгоритма 2.2. В результате снижается эффективность планирования. Кроме того, при выполнении алгоритма 2.2 в первой задаче линейного программирования максимизируется значение 7} + Dt для всех задач. Хотя было указано, что в зависимости от приоритета задачи целесообразней менять вид целевой функции. Аналогичная ситуация связана со второй задачей линейного программирования, где для всех задач используется одно и то же значение 0. В результате могут быть пропущены более подходящие варианты множества ОТ%, что также снижает эффективность планирования. Таким образом, можно предположить, что значения О,-, 7} для каждой задачи, имеющей исходное НО, лучше определять после назначения приоритетов. В этом случае при формировании значений Ot, Tt можно учесть задачи с более высокими приоритетами. На этом основан предлагаемый подход. Надо заметить, что, как и в случае формирования сочетания (О,- ,Tt ,Dt) по аналогии с параметром Ot предлагается не устанавливать каких-либо требований применительно к Ot (см. п. 2.7.4). Тогда основные проблемы - это назначение приоритетов и формирование значения 7} после назначения приоритетов. Пусть приоритеты каким-либо образом назначены. Пусть для каждой задачи, имеющией СО, установлены параметры О, - О і, Ti = Ti . Для задачи т,- с наиболее высоким приоритетом среди задач, имеющих НО, можно определить условие выполнимости согласно алгоритму 3.4. Делается предположение, что fij ri,j+\ для V-/ l- Тогда значения rxt , rx-/, ryt , rytp, xyt , xyt вычислить, так как параметры задач с более высокими приоритетами установлены, ведь к таким задачам относятся только задачи, имеющие СО. Например, для указанного вычисления можно использовать алгоритм 3.3, имеющий Р = 0 в качестве соответствующего компонента входных данных. Таким образом, условие выполнимости задачи т, определяется с точностью до значений Oh 7}, которые являются неизвестными в указанном условии. Для задачи т, в качестве можно установить максимальное из возможных значений 7}, удовлетворяющих этому условию, а в качестве Ot установить какое-нибудь Оп удовлетворяющее условию вместе с установленным Тг Тогда при переходе к задаче, имеющей НО, которая является следующей по порядку приоритетов, получается, что для задач с более высокими приоритетами все параметры установлены. Поэтому для этой задачи аналогичным образом можно определить условие выполнимости с точностью до значений Ot, 7}, сделать аналогичное предположение и аналогичным образом установить значения Ot, 7}. В итоге, перебирая все задачи, имеющие НО, в порядке снижения приоритетов, можно для каждой из них установить значения 0,, Tt указанным образом. Для краткости значение 7}, сформированное подобным образом для каждой задачи, имеющей НО, будет называться максимально допустимым. Надо отметить, что такое значение 7} совсем не обязательно является максимально возможным среди всех допустимых сочетаний {Oj,Tj \ і є [1,и]} при данном распределении приоритетов {л:,}. Оно является максимально допустимым при данных значениях параметров задач с более высокими приоритетами в предположении, что fjj rjj+i для У/ 1. Очевидно, что выбор для задачи, имеющей НО, максимально допустимого Tj во многих случаях повышает вероятность выполнимости задач с более низкими приоритетами, ведь такие задачи будут прерываться реже при увеличении Tj. Кроме того, выбор максимально допустимого 7} приводит к уменьшению загрузки ВУ задачами ЖРВ, что увеличивает процент свободного времени, когда ВУ может выполнять апериодические запросы. Это, в свою очередь, позволит выполнять большее количество апериодических запросов, повышая, тем самым, эффективность использования ВУ. Предположение fjj rtj+l для У/ 1 используется для того, чтобы была возможность вычислить значения rXj , rXjр, rjj , ryt р, ху\, ху{ р в случае, когда значения 0{, Tj еще не определены. Однако такое предположение может оказаться ложным. В этом случае условие выполнимости для задачи т, может не выполниться. Поэтому условие выполнимости каждой задачи т,-, имеющей НО, надо отдельно проверять после формирования значения Ot, 7}. Для каждой такой проверки можно использовать алгоритм 3.5. Теперь надо обратиться к проблеме назначения приоритетов. Приоритеты могут быть назначены на основе формирования допустимых СО и использования алгоритма назначения приоритетов при наличии только СО. Использование алгоритма 1.1 не имеет смысла, так как, очевидно, алгоритм 1.1 назначит все приоритеты, только если базовый алгоритм 2.3 обеспечивает выполнимость {Xj}. Важно обеспечить выполнимость {т,}, когда базовый алгоритм 2.3 не может это сделать. Поэтому предлагается использовать алгоритм DM (см. п. 1.2.4.3), ведь он обязательно назначит все приоритеты, если каждая задача имеет СО. В общем случае алгоритм DM не будет оптимальным. Это может привести к ситуации, когда выполнимость {т,} не обеспечивается, хотя алгоритм А обеспечивает ее, используя другой вариант назначения приоритетов.
Похожие диссертации на Планирование задач в системах автоматизации и управления при нестандартных ограничениях реального времени
