На правах рукописи

КАВАЛЕРОВ Максим Владимирович

ПЛАНИРОВАНИЕ ЗАДАЧ В СИСТЕМАХ АВТОМАТИЗАЦИИ И

УПРАВЛЕНИЯ ПРИ НЕСТАНДАРТНЫХ ОГРАНИЧЕНИЯХ РЕАЛЬНОГО

ВРЕМЕНИ

Специальность: 05.13.06– Автоматизация и управление

технологическими процессами и производствами (в промышленности)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Пермь 2007 2

Работа выполнена в Пермском государственном техническом университете.

Научный руководитель: доктор технических наук, профессор Матушкин Николай Николаевич

Официальные оппоненты: доктор физико-математических наук, профессор Абдуллаев Абдулла Рамазанович кандидат технических наук Федорищев Иван Федорович

Ведущая организация: ОАО«Научно-исследовательский институт управляющих машин и систем г. Пермь.

»,

Защита диссертации состоится 25 мая 2007 г. в 1500 часов на заседании диссертационного совета Д212.188.04 при Пермском государственном техническом университете по адресу: 614990, г. Пермь, Комсомольский пр., 29, ауд. 423б.

С диссертацией можно ознакомиться в библиотеке Пермского государственного технического университета.

Автореферат разослан 24 апреля 2007 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор Южаков А.А.

Общая характеристика работы

Актуальность темы. В системах автоматизации и управления (САиУ) отдельное вычислительное устройство (ВУ) часто выполняет несколько задач реального времени (РВ). Каждой такой задаче соответствует свое ограничение РВ, которое накладывается на характеристики процесса выполнения запросов, формируемых этой задачей. Необходимо осуществлять планирование множества задач, т. е. разделение процессорного времени между запросами различных задач при условии соблюдения ограничений РВ. Более эффективное планирование позволяет соблюдать более жесткие ограничения при данных аппаратнопрограммных средствах. Например, реализуется более строгая периодичность опроса датчиков, уменьшаются задержки при формировании управляющих воздействий. Зачастую это означает повышение качества управления. Более эффективное планирование также снижает требования к быстродействию ВУ, что обеспечивает снижение затрат и уменьшение срока окупаемости САиУ.

Широкое распространение получила концепция планирования с фиксированными приоритетами (ПФП), обеспечивающая компромисс между предсказуемостью и гибкостью планирования. В стандартной модели ПФП каждая задача жесткого реального времени (ЖРВ) имеет только стандартное ограничение (СО), которое выражается с помощью начального смещения и периода формирования запросов данной задачи, а также крайнего срока выполнения запроса относительно момента его появления. Однако известно, что многие задачи ЖРВ в составе САиУ изначально имеют ограничения, которые не являются СО, т. е. являются нестандартными ограничениями (НО). Примером задач с НО часто являются задачи, реализующие контуры управления. В ряде исследований, в частности, в работах таких авторов, как G. Fohler и M. Tngren, подчеркивается широкая распространенность задач с НО в составе САиУ.

Планирование задач РВ является сложной проблемой при наличии НО.

В условиях ПФП эта проблема формулируется следующим образом. Требуется установить параметры каждой задачи РВ (а именно, начальное смещение, период и приоритет) так, чтобы гарантировать соблюдение всех СО и НО при выполнении данного множества задач. Сложность проблемы зависит от предполагаемых видов НО, т. е. от целевого класса НО.

Базовый (или традиционный) подход к решению данной проблемы состоит в том, что каждое НО преобразуется в допустимое (или вторичное) СО, т. е.

такое СО, что его соблюдение означает соблюдение данного НО. Затем, планирование осуществляется известными методами, предназначенными только для СО. Однако для каждого вида НО надо уметь определять допустимое СО.

Эффективность планирования можно повысить, если планирование задач осуществлять при непосредственном применении НО вместо того, чтобы каждое НО заменять допустимым СО. Известны подобные решения проблемы для некоторых целевых классов НО. В частности, можно отметить работы таких исследователей, как R. Dobrin, G. Fohler, P. Puschner, W. Wang, A.K. Mok, K. Sandstrm, C. Norstr m. Однако, в случае каждого из известных решений, целевой класс не включает многие НО, характерные для САиУ.

Таким образом, актуальной является проблема разработки алгоритмов планирования, обеспечивающих в условиях ПФП соблюдение НО, характерных для САиУ, но не входящих в целевые классы известных подходов.

Для решения данной проблемы, очевидно, надо выделить класс таких НО.

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

Целью работы является разработка алгоритмов планирования задач РВ применительно к концепции ПФП для класса НО, встречающихся в САиУ.

Задачи исследования. Достижение поставленной цели обеспечивается решением в диссертационной работе следующих задач:

1) выделить класс НО, встречающихся в САиУ, но не входящих в целевые классы известных подходов, при этом определение класса не должно быть слишком общим, чтобы можно было разрабатывать алгоритмы планирования, применимые для задач РВ с любыми НО из данного класса;

2) разработать алгоритм преобразования любого НО из выделенного класса в допустимое СО, что требуется для реализации базового подхода к планированию при наличии НО в условиях ПФП;

3) разработать алгоритм формирования условия выполнимости задачи РВ с любым НО из выделенного класса;

4) разработать алгоритм планирования при непосредственном применении любых НО из выделенного класса;

5) оценить эффективность разработанных алгоритмов на основе имитационного моделирования процесса планирования задач РВ.

Методы исследования. В работе использовались методы, применяемые в теории планирования задач РВ, в частности, методы оценки времени отклика для задачи РВ и анализа выполнимости совокупности задач РВ, также использовались методы математической логики, теории множеств, теории вычислительной сложности. Для оценки полученных результатов выполнялось имитационное моделирование процесса планирования задач РВ с применением вычислительной техники и необходимого программного обеспечения.

Научная новизна. В работе получено решение проблемы планирования задач при наличии НО в условиях ПФП. При этом основные отличия настоящей работы от близких по тематике состоят в следующем.

1) Рассматривается широкий класс НО, встречающихся при разработке САиУ, и он назван классом линейных интервальных ограничений (ЛИО). Данный класс содержит многие НО, которые не входят в целевые классы НО известных подходов.

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

3) Разработаны алгоритмы, обеспечивающие планирование задач в условиях ПФП при любых ЛИО. При этом реализован как базовый подход к планированию задач РВ, так и подход, основанный на непосредственном применении НО в процессе планирования.

4) В ходе имитационного моделирования процесса планирования задач РВ получены оценки повышения эффективности планирования при непосредственном применении ЛИО по сравнению с базовым подходом, основанным на формировании допустимых СО.

Достоверность приводимых в работе результатов и выводов обеспечивается: формальными доказательствами справедливости утверждений, характеризующих получаемые результаты, а также корректным применением методов математической логики, теории планирования задач РВ, теории множеств, теории вычислительной сложности.

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

Алгоритмы, предложенные в диссертации, использовались при разработке программного обеспечения системы автоматизации испытаний авиационных агрегатов, внедренной и принятой в опытную эксплуатацию в ОАО« СТАР ».

Проблема планирования задач РВ при НО, рассмотренная в ходе диссертационного исследования, нашла отражение в лекционном курсе, читаемом автором студентам специальности 220201 «Управление и информатика в технических системах Пермского государственного технического университета.

Апробация работы. Основные результаты диссертационной работы представлялись на международной научной конференции «Методы и средства управления технологическими процессами (Саранск, 1999), международной конференции по информатике и информационным технологиями CSIT’2000 (Уфа, 2000), межвузовской научно-технической конференции « Управляющие и вычислительные системы. Новые технологии (Вологда, 2001), международной открытой научной конференции «Современные проблемы информатизации (Воронеж, 2006), Всероссийской конференции «Необратимые процессы в природе и технике (Москва, 2007).

Публикации. По теме диссертации опубликовано 11 печатных работ, в том числе опубликована статья в журнале, указанном в перечне ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора и кандидата наук.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 78 наименований, и приложений. Основная часть работы изложена на 127 страницах печатного текста и содержит 30 рисунков.

Во введении обоснована актуальность темы, содержится формулировка цели и задач исследований.

В первой главе раскрываются основные понятия, связанные с планированием задач РВ в САиУ, формулируется проблема планирования задач РВ при НО в условиях ПФП, формализуются в виде алгоритмов: известная методика планирования при наличии только СО, а также базовый подход к решению проблемы планирования при НО.

Определяется базовая модель ПФП, учитывающая специфику проблемной области, и здесь ее можно кратко описать следующим образом. Различают две стадии ПФП: планирование и диспетчеризация. В условиях ПФП стадия планирования выполняется до запуска системы. Диспетчеризация выполняется во время функционирования САиУ и предполагает обслуживание очереди запросов, формируемых задачами РВ, из которой запросы выбираются согласно фиксированным приоритетам соответствующих задач. При этом ВУ является однопроцессорным, и выполнение запросов может прерываться.

Имеется множество из n задач ЖРВ {1,..., n }, для краткости обозначаемое {i }. Каждая задача i формирует запросы. Каждый j -й запрос, обозначаемый i, j, формируется в момент времени ri, j. Для любой периодической задачи i при j 1 всегда ri, j = Oi + ( j 1)Ti, где Oi – начальное смещение; Ti – период. Задача i может иметь СО в виде условия f i, j d i, j = ri, j + Di, где f i, j – время завершения выполнения i, j ; d i, j – крайний срок выполнения i, j ; Di – относительный крайний срок i. Каждая задача i имеет фиксированный приоритет i, и множеству {i } ставится в соответствие множество {i }. Имеется квант времени, с учетом которого выполняются задачи РВ.

Отмечено, что на стадии диспетчеризации не учитываются ограничения РВ, а учитывается только множество {Oi, Ti, i | i [1, n]}, для краткости обозначаемое OTр. Это множество порождает совокупность возможных вариантов выполнения запросов задач {i }. Существование разных вариантов определяется наличием недетерминированных событий в системе. Если в случае каждого из вариантов соблюдается ограничение РВ задачи i, то при данном множестве OTр гарантируется соблюдение этого ограничения, и задача i называется выполнимой. Множество {i } называется выполнимым, если, во-первых, обеспечивается выполнимость каждой задачи из {i }, во-вторых, гарантируется, что размер очереди запросов, формируемых задачами из {i }, всегда ограничен сверху некоторым конечным числом. Множество OTр, обеспечивающее выполнимость {i }, называется допустимым. Тогда основная проблема планирования формулируется следующим образом. До запуска системы надо сформировать допустимое множество OTр или указать, что ни одного такого множества найти не удается. Именно эта проблема решается на стадии планирования.

Обосновывается, что СО периодической задачи i при общем подходе к ограничениям РВ удобнее представлять в виде условия где si, j – время начала выполнения i, j ; Oi*, Ti* – параметры СО. Здесь и далее считается, что условие, задающее ограничение РВ, должно соблюдаться при j 1. Доказано утверждение 1.1, о том, что, если СО (1) соблюдается при j 1 для некоторых Oi, Ti, то оно будет соблюдаться и при Oi = Oi*, Ti = Ti*.

Доказано утверждение 1.2 о связи СО (1) со стандартным требованием РВ.

Показано, что при наличии только СО (1) планирование существенно упрощается, а именно проблема формирования допустимого множества OTр сводится к нахождению подходящего множества {i }. Для обоснования этого используется утверждение 1.1 и утверждение 1.3, состоящее в том, что, если все ограничения РВ являются СО, то для выполнимости {i } достаточно, чтобы гарантировалось соблюдение всех СО, и для каждой периодической задачи i было установлено Oi = Oi*, Ti = Ti*. Доказана справедливость утверждения 1.3.

Известен алгоритм, предложенный N.C. Audsley, который всегда находит подходящее множество {i }, если такое существует. Этот алгоритм воспроизводится в несколько иной форме без принципиальных изменений, что вызвано необходимостью согласования этого алгоритма с другими алгоритмами диссертационной работы, и он обозначается как алгоритм 1.1. Также известен метод анализа выполнимости задачи i при наличии только СО. Этот метод оформляется в виде алгоритма 1.2. Затем, в виде алгоритма 1.3 описывается алгоритм планирования при наличии только СО. Корректность такого описания обосновывается доказательством соответствующего утверждения 1.4.

Определяются понятия сравнительной эффективности алгоритмов планирования, а также планирования в целом. Алгоритм планирования считается более эффективным, чем алгоритм планирования, если, во-первых, обязательно формирует допустимое множество OTр, когда формирует допустимое множество OTр в тех же условиях, и, во-вторых, существует хотя бы один случай, когда формирует допустимое множество OTр, а выдает сообщение о невозможности сформировать допустимое множество OTр в этих же условиях. Планирование считается более эффективным, чем планирование, если при прочих равных условиях реализуется с помощью алгоритма планирования, который более эффективен, чем соответствующий алгоритм, относящийся к. Показано, что более эффективное планирование дает больше возможностей, во-первых, избежать дополнительных затрат в ходе построения САиУ, во-вторых, гарантировать более жесткие ограничения РВ, тем самым, повысить эффективность САиУ применительно к временным характеристикам.

Приведены два примера НО, которые накладываются на моменты времени si, j, f i, j. Для этих НО даны условия допустимости СО, что формулируется как утверждения 1.5, 1.6, с соответствующими доказательствами.

Представлен обзор исследований, связанных с НО.

Сформулирован базовый подход к решению проблемы планирования при наличии НО в условиях ПФП. Для этого используется алгоритм 1.3.

Даны примеры, иллюстрирующие возможность повышения эффективности планирования по сравнению с базовым подходом.

Во второй главе выделяется целевой класс НО, формулируются необходимые для этого понятия и разрабатывается алгоритм преобразования любого НО из выделенного класса в допустимое СО.

Известно, что ограничение РВ может быть связано не только с si, j и f i, j, но и с другими моментами времени на интервале [ si, j, f i, j ]. Предлагается на этом интервале выделить два момента времени xi, j, y i, j. Например, xi, j – это момент получения информации о параметре объекта, а y i, j – момент формирования управляющего воздействия на объект. При этом может оказаться, что xi, j = si, j, yi, j = f i, j. Преимущества подобного подхода и его применение были рассмотрены в работах таких авторов, как R. Gerber и A. Burns.

Приводятся примеры НО, которые накладываются на моменты времени xi, j, y i, j. Один из этих примеров– это НО задачи контура управления (ЗКУ), которое определяется условием где Ti xx min, Ti xx max, Ti xy max – константы; при этом заранее устанавливается значение xi,0. Другой пример – это НО задачи контура управления с усреднением интервала (ЗКУУИ), которое основано на НО ЗКУ и определяется условием где константы Ti mxx min, Ti mxx max определяют диапазон допустимых значений xi, j xi, j 1, усредненных по mi предыдущих запросов; при этом заранее устанавливаются значения xi, mi +1,..., xi, 1, xi,0.

Выделение класса НО осуществляется на основе следующих допущений:

1) только периодические задачи ЖРВ имеют НО; 2) НО данной задачи не зависит от выполнения других задач; 3) НО накладывается только на события, связанные с действиями, которые реализуются в ходе выполнения соответствующей задачи; 4) НО накладывается только на события, соответствующие моментам времени xi, j, y i, j. Для каждого допущения приводится обоснование.

Класс НО выделяется следующим определением. Линейное интервальное ограничение (ЛИО) для задачи i, обозначаемое i,–это ограничение РВ, представимое при j 1 в виде условия ния интервалов допустимых значений xi, j, y i, j, y i, j xi, j соответственно;

v1,..., v6 определяют количество вариантов; ximinv, ximax, yiminv, yimax, xyiminv, xyi, j, v обозначают v -й вариант соответствующих значений, и каждый из вариантов – это или (может быть только после "" ), или (может быть только после "" ), или выражение, представимое в виде где k, k –целые неотрицательные значения; k при k [1, k ], k при k [1, k ],, – константы, заданные для данного варианта; при этом все xi, j k, yi, j k для j k 0, которые могут использоваться в выражениях вида (5), являются константами, заданными для данного i.

Множество всех возможных ЛИО формирует класс ЛИО. Доказана справедливость утверждения 2.1 об одном полезном свойстве ЛИО. Также показано, что рассмотренные примеры НО относятся к классу ЛИО. Например, для но v2 = 2, ximax = xi, j 1 + Ti xx max, ximax = xi, j mi + miTi mxx max ; v3, v4, v5, v6 равj, ны 1; yi, j =, yi, j =, xyi, j =, xyimax = Ti xy max. Кроме того, показано, что СО периодической задачи является ЛИО. При этом важно, что класс ЛИО не входит в целевые классы НО известных подходов.

Отмечено, что обращение к моментам времени xi, j, y i, j обуславливает необходимость уточнения временных характеристик запросов. С каждым запросом i, j связано 4 момента времени si, j, xi, j, yi, j, f i, j, и существует 6 различных компонентов i, j с соответствующими длительностями. На основе известных методик для каждого компонента можно определить нижнюю и верхнюю оценку его длительности выполнения. Поэтому считается, что известны 12 оценок: CsxiLo, CsxiUp, CsyiLo, CsyiUp, Csf i Lo, Csf iUp, CxyiLo, CxyiUp, Cxf i Lo, Cxf iUp, Cyf i Lo, Cyf iUp, где CsxiLo, CsxiUp – нижняя и верхняя оценка длины интервала [ si, j, xi, j ] по j 1 при отсутствии прерываний запроса i, j ; другие оценки определяются аналогично.

Разрабатывается алгоритм преобразования любого НО из выделенного класса (т. е. любого ЛИО) в допустимое СО. Сочетание (Oi*, Ti*, Di ) называется допустимым, если соответствующее СО является допустимым. Предлагаемый способ преобразования состоит из двух этапов: 1) получение достаточного условия допустимости (Oi*, Ti*, Di ) (в дальнейшем, для краткости, указание на достаточность опускается); 2) выбор допустимого сочетания (Oi*, Ti*, Di ), которое и определит допустимое СО, либо сообщение о невозможности такого выбора. Указанные этапы реализуются на основе соответствующих алгоритмов.

Разработан алгоритм 2.1, реализующий получение условия допустимости для любого ЛИО i. Его можно кратко описать так. Сначала в условии (4) данного i вместо xi, j в 1-м и 2-м неравенствах, yi, j в 3-м и 4-м неравенствах, yi, j xi, j в 5-м и 6-м неравенствах подставляются: Oi* + ( j 1)Ti* + CsxiLo, Oi* + ( j 1)Ti* + Di Cxf i Lo, Oi* + ( j 1)Ti* + CsyiLo, Oi* + ( j 1)Ti* + Di Cyf i Lo, CxyiLo, Di Cyf i Lo CsxiLo соответственно. Затем, каждое неравенство заменяется эквивалентной совокупностью неравенств, имеющих в правой части только один компонент из соответствующего max или min. Удаляются неравенства, правая часть которых – это или. Пусть полученная совокупность неравенств обозначается W. Определяется значение v, равное такому минимальному значению j среди j 1, при котором в составе выражений вида (5) в случае всех неравенств значения xi, j k, yi, j k для j k < 1 не используются или умножаются на 0. Для каждого целого числа z из интервала [1, v] выполняются следующие действия над W : 1) у каждого xi, j k, yi, j k в составе выражений вида (5) правой части каждого неравенства индекс j k заменяется числом z k ; 2) каждое xi, z k, yi, z k при z k > 0 из правой части каждого неравенства заменяется своей нижней или верхней оценкой так, чтобы неравенство, полученное после указанной замены, было достаточным условием выполнения исходного неравенства. При этом в качестве нижней и верхней оценки xi, z k применяются Oi* + ( j k 1)Ti* + CsxiLo, Oi* + ( j k 1)Ti* + Di Cxf i Lo соответственно. В качестве нижней и верхней оценки yi, z k применяются Oi* + ( j k 1)Ti* + CsyiLo и Oi* + ( j k 1)Ti* + Di Cyf i Lo соответственно. В результате для каждого z совокупность W преобразуется в совокупность, обозначаемую Wz ( j ), так как переменная j присутствует в выражениях для оценок xi, z k, yi, z k. При этом Wv ( j ) сохраняется отдельно. Для z [1, v] выполняется преобразование Wz ( j ) в совокупность, обозначаемую Wz, путем замены переменной j числом z. Каждое неравенство из Wv ( j ) преобразуется к виду 1 j + 2 0, где 1, 2 – компоненты, которые не зависят от j. Затем, каждое такое неравенство заменяется на 1 0. В итоге получается совокупность неравенств, обозначаемая W[ v, ). Алгоритм выдает условие допустимости, сформированное на основе объединения совокупностей W1,..., Wv,W[v, ).

Доказано утверждение 2.2, что алгоритм 2.1 действительно формирует условие допустимости сочетания (Oi*, Ti*, Di ). Также приводятся подробные примеры, иллюстрирующие применение алгоритма 2.1 в случае разных ЛИО.

Проблема выбора допустимого (Oi*, Ti*, Di ) сводится к задаче линейного программирования (ЛП) применительно к переменным Oi*, Ti*, Di и ограничениями, задаваемым условием допустимости. Подробно рассматривается определение целевой функции. Показано, что увеличение Ti* и Di с большой вероятностью облегчает планирование. В итоге выбрано решение – это максимизация величины Ti* + Di. Может оказаться, что несколько пар (Ti*, Di ) дают максимизацию Ti* + Di. Для выбора пары заранее устанавливается константа, задающая желаемое соотношение Di / Ti* для всех задач i, имеющих НО.

Разработан алгоритм 2.2, реализующий преобразование любого ЛИО в допустимое СО на основе указанных принципов. Его можно кратко описать так. Сначала формируется условие допустимости с помощью алгоритма 2.1. Затем, с помощью задачи ЛП определяется максимальное значение Ti* + Di. После этого, с помощью дополнительной задачи ЛП определяется пара (Ti*, Di ), которая минимизирует Di / Ti*, среди пар, максимизирующих Ti* + Di. Если для первой задачи ЛП решения не существует, то алгоритм завершается с соответствующим сообщением. Из-за наличия кванта времени решаемые задачи ЛП являются целочисленными.

Доказано утверждение 2.3, что, если результат алгоритма 2.2 – это значения Oi*, Ti*, Di, то значения Oi*, Ti*, Di определяют допустимое СО, при этом обеспечивают минимальное значение Di / Ti* среди всех допустимых (Oi*, Ti*, Di ), обеспечивающих максимальное значение Ti* + Di.

На основе алгоритмов 1.3, 2.2 строится алгоритм 2.3, реализующий базовый подход к планированию при наличии любых НО из выделенного класса, т. е. любых ЛИО. Доказано утверждение 2.4, что при наличии только ЛИО множество {i } является выполнимым, если алгоритм 2.3 выдает сообщение о выполнимости {i }. Поэтому алгоритм 2.3 может использоваться для планирования {i } при наличии любых ЛИО.

Таким образом, решены 1-я и 2-я задачи исследования: выделен класс ЛИО; разработан алгоритм 2.2, который используется алгоритмом 2.3.

В третьей главе разрабатывается алгоритм формирования условия выполнимости задачи с любым НО из выделенного класса, разрабатывается алгоритм планирования при непосредственном применении НО из выделенного класса.

Показана необходимость получения условия выполнимости задачи с любым НО из выделенного класса, т. е. с любым ЛИО. Отмечено, что для получения этого условия надо оценивать параметры выполнения запросов.

Параметры выполнения запроса i, j обозначаются rsi, j, rxi, j, ry i, j, rf i, j, sxi, j, sy i, j, sf i, j, xyi, j, xf i, j, yf i, j, где rsi, j = si, j ri, j ; другие параметры определяются аналогично. Для каждого из параметров можно определить его нижнюю и верхнюю оценку.

Разработаны алгоритмы 3.1, 3.2, 3.3, обеспечивающие вычисление указанных оценок. При разработке алгоритмов за основу принимались алгоритмы вычисления оценок для времени отклика из работ таких авторов, как K.W. Tindell, O. Redell, M. Sanfridson. Доказаны утверждения 3.1, 3.2, 3.3, которые обосновывают корректность получаемых оценок.

Разработан алгоритм 3.4, реализующий формирование условия выполнимости задачи с любым НО из выделенного класса, т. е. с любым ЛИО i.

Данный алгоритм можно описать как алгоритм, получаемый из алгоритма 2. на основе следующих его модификаций. Во-первых, в условии (4) данного i вместо xi, j, yi, j, yi, j xi, j подставляются не выражения, указанные в соответствующей части описания алгоритма 2.1, а выражения Oi + ( j 1)Ti + rxiLo, Oi + ( j 1)Ti + rxiUp, Oi + ( j 1)Ti + ryiLo, Oi + ( j 1)Ti + ryiUp, xyiLo, xyiUp, где rxiLo, rxiUp, ryiLo, ryiUp, xyiLo, xyiUp – соответственно нижние и верхние оценки rxi, j, ry i, j, xyi, j. При этом, если затем удаляются все неравенства, то алгоритм завершается с результатом в виде условия выполнимости, тождественного значению «истина Во-вторых, в качестве нижней и верхней оценки xi, z k применяются Oi + ( j k 1)Ti + rxiLo, Oi + ( j k 1)Ti + rxiUp соответственно, а в качестве нижней и верхней оценки yi, z k применяются соответственно Oi + ( j k 1)Ti + ryiLo, Oi + ( j k 1)Ti + ryiUp. В-третьих, результатом алгоритма будет не условие допустимости, а условие выполнимости.

Доказано утверждение 3.4 о том, что алгоритм 3.4 действительно всегда формирует условие выполнимости задачи с любым ЛИО. Также приводятся примеры, иллюстрирующие применение алгоритма 3.4 в случае разных ЛИО.

На основе алгоритма 3.4, а также алгоритма 3.3, использующего алгоритмы 3.1, 3.2, реализуется алгоритм 3.5, обеспечивающий анализ выполнимости задачи с любым ЛИО.

Разработан алгоритм 3.6, реализующий планирование при непосредственном применении любых ЛИО. Его можно кратко описать так. С помощью алгоритма 2.2 каждое имеющееся ЛИО преобразуются в допустимое СО. Для каждой периодической задачи i устанавливается Oi = Oi*, Ti = Ti*. Если не выполняется условие ограниченности очереди запросов, а именно условие то алгоритм завершается с сообщением о невозможности обеспечить выполнимость {i }. Вызывается алгоритм 1.1, при этом в качестве его входных данных используются: множество {i }, алгоритм 1.2 для каждой задачи из {i }, имеющей исходное СО, алгоритм 3.5 для каждой задачи из {i }, имеющей ЛИО. Если в результате этого выполнения оказывается, что множество {i } сформировано, и множество {i } является выполнимым, то тогда алгоритм завершается с результатом, содержащим множество {i } с определенными значениями {Oi, Ti, i | i [1, n]} и сообщение о выполнимости {i }, иначе алгоритм завершается с сообщением о невозможности обеспечить выполнимость {i }.

Для удобства алгоритм 3.6 называется алгоритмом А, так как применение ЛИО происходит при анализе (А) выполнимости. Доказано утверждение 3.5 о том, что при наличии только ЛИО множество {i } является выполнимым, если алгоритм А выдает сообщение о выполнимости {i }. Поэтому алгоритм А может использоваться для планирования {i } при наличии любых ЛИО.

Показано, что эффективность планирования можно повысить, если Oi, Ti для каждой задачи, имеющей ЛИО, задавать после назначения приоритетов.

С этой целью сначала разработан алгоритм 3.7, который формирует максимально допустимое значение Ti для каждой задачи, имеющей ЛИО, среди задач с приоритетами в заданном диапазоне. Его можно кратко описать так. Выбирается очередная задача i, при этом для каждой задачи с более высоким приоритетом уже известны значения Oi, Ti, i. С помощью алгоритма 3.4 для i формируется условие выполнимости. С помощью алгоритма 3.3 вычисляются те оценки параметров выполнения запросов, которые встречаются в условии выполнимости для i. При этом предполагается, что f i, j < ri, j +1 для j 1. Решается целочисленная задача ЛП для переменных Oi, Ti и ограничений в виде всех неравенств условия выполнимости для i, при этом максимизируется Ti.

Если задача ЛП не имеет решения, то алгоритм досрочно завершается. Иначе Oi, Ti, полученные после решения задачи ЛП, устанавливаются как параметры i. Выбирается следующая задача в порядке снижения приоритетов, и действия повторяются, если такая задача еще есть. Иначе алгоритм завершается.

В итоге, разработан алгоритм 3.8, который реализует планирование при непосредственном применении любых ЛИО. Его можно кратко описать так. С помощью алгоритма 2.2 выполняется преобразование имеющихся ЛИО в допустимые СО. Задачи сортируются по возрастанию значений Di, и приоритеты назначаются согласно номеру задачи в отсортированном списке. Так, задача с наименьшим Di получает наивысший приоритет. Выполняется алгоритм 3.7.

Если он завершается досрочно, то делается переход к последнему шагу алгоритма 3.8. Если не выполняется условие (6), то также делается переход к последнему шагу алгоритма 3.8. Производится анализ выполнимости каждой задачи из {i }, для этого в случае задачи, имеющей СО, вызывается алгоритм 1.2, а в случае задачи, имеющей ЛИО, вызывается алгоритм 3.5. Если в случае хотя бы одной задачи выдается сообщение о том, что выполнимость этой задачи не гарантируется, тогда делается переход к последнему шагу алгоритма 3.8. Алгоритм завершается с результатом, содержащим множество {i } с определенными {Oi, Ti, i | i [1, n]} и сообщение о выполнимости {i }.

Последний шаг алгоритма состоит в вызове алгоритма А для планирования {i }, так как переход к этому шагу означает, что не удается обеспечить выполнимость {i }. Поэтому алгоритм А вызывается, чтобы попробовать обеспечить выполнимость {i } другим способом. В этом случае алгоритм 3.8 завершается с результатом выполнения алгоритма А.

Для удобства алгоритм 3.8 называется алгоритмом АП, так как непосредственное применение ЛИО происходит при анализе (А) выполнимости и при определении Ti, т. е. периода (П). Доказано утверждение 3.6 о том, что при наличии только ЛИО множество {i } является выполнимым, если алгоритм АП выдает сообщение о выполнимости {i }. Поэтому алгоритм АП может использоваться для планирования {i } при наличии любых ЛИО.

Доказано утверждение 3.7 о том, что алгоритм АП более эффективен, чем алгоритм А, и алгоритм А более эффективен, чем базовый алгоритм 2.3. Здесь применяется понятие сравнительной эффективности, введенное в первой главе.

Тогда алгоритм АП следует считать результатом решения 4-й задачи исследования, так как он эффективнее алгоритма А. Тем не менее, алгоритм А играет важную роль в качестве составной части алгоритма АП.

Таким образом, решены 3-я и 4-я задачи исследования: разработан алгоритм 3.4; разработан алгоритм АП.

В четвертой главе оценивается эффективность разработанных алгоритмов на основе имитационного моделирования процесса планирования задач РВ, приводятся сведения о практическом применении разработанных алгоритмов.

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

Приводятся наиболее характерные результаты моделирования, остальные результаты приводятся в приложении. На рисунке приведен пример результатов имитационного моделирования. При этом случайным образом генерируются множества {i }, состоящие из 5-ти ЗКУ и 5-ти задач, имеющих СО. Генерирование выполняется для различных опорных значений загрузки задачами из {i }. Количественный показатель эффективности – это процент успеха алгоритма, т. е. процент случаев, когда алгоритм обеспечивает выполнимость {i }. Из рисунка видно, что при больших загрузках преимущество алгоритма АП Базовый алгоритм становится существенным по отношеАлгоритм АП составляет около 30%. При этом на Процент средних и малых загрузках алгоритмы успеха, тивности, и они являются заметно более эффективными, чем базовый алго- ритм.

щество алгоритмов А и АП на средних загрузках, и значительное преРисунок. Пример результатов имущество алгоритма АП на больших загрузках по сравнению с базовым алгоритмом 2.3. Это означает, что при разработке алгоритмов А и в особенности алгоритма АП, удалось реализовать значительное повышение эффективности планирования при непосредственном применении НО по сравнению с базовым подходом. Кроме того, результаты моделирования показали, что переход от алгоритма А к алгоритму АП является оправданным, так как при этом эффективность планирования повышается существенно, и одновременно уменьшается загрузка задачами ЖРВ, что оставляет больше свободного времени для выполнения задач мягкого РВ.

Таким образом, решена 5-я задача исследований.

Также в данной главе приводятся сведения о практическом применении разработанных алгоритмов при реализации программного обеспечения системы автоматизации испытаний авиационных агрегатов, внедренной и принятой в опытную эксплуатацию. Использование указанных алгоритмов позволило избежать дополнительных затрат на приобретение более быстродействующих аппаратных средств и доработку программного обеспечения.

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

В приложениях приведены доказательства некоторых утверждений, а также результаты имитационного моделирования.

1) Повышение эффективности САиУ применительно к временным характеристикам и уменьшение затрат на построение САиУ можно достичь за счет более эффективного планирования задач РВ при наличии НО. Для этого разработаны алгоритмы, обеспечивающие планирование задач в условиях ПФП при наличии НО. При этом реализован как базовый подход к планированию задач РВ, так и подход, основанный на непосредственном применении НО.

2) Разработанные алгоритмы применимы не для отдельных видов НО, а для широкого класса ЛИО, который содержит многие НО, характерные для САиУ. При этом используется более реалистичная модель, чем при известных подходах. В частности, учитываются задержки между началом выполнения запроса и моментом получения информации с объекта, а также между моментом формирования воздействия на объект и завершением выполнения запроса.

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

4) Разработанные алгоритмы могут быть реализованы в составе инструментальных средств, которые используются для планирования задач в современных САиУ, характеризуемых сложным набором задач и ограничений РВ.

5) Рекомендуется использовать разработанные алгоритмы планирования при проектировании САиУ применительно к концепции ПФП. Это позволит повысить эффективность САиУ по отношению к временным характеристикам, а также уменьшить затраты и сократить срок окупаемости САиУ.

Публикации. Работа нашла отражение в следующих публикациях.

1. Kavalerov M.V. Soft Real-Time Tasks Scheduling Based on Dynamic Timing Constraints in Fixed Priority Preemptive Systems // CSIT'2000, Proceedings of 2nd International Workshop on Computer Science and Information Technologies, September 18-23, 2000, Ufa, Russia.– P. 319-322.

2. Кавалеров М.В., Матушкин Н.Н. Повышение эффективности систем реального времени при планировании с фиксированными приоритетами с учетом относительных ограничений // Информационно-управляющие системы: сб.

науч. тр. / Перм. гос. техн. ун-т.– Пермь, 2001.– С. 151-157.

3. Кавалеров М.В., Матушкин Н.Н. Новые способы планирования задач с нестандартными ограничениями жесткого реального времени в концепции планирования с фиксированными приоритетами // Информационно-управляющие системы: сб. науч. тр. / Перм. гос. техн. ун-т.– Пермь, 2003.–С. 152-162.

4. Кавалеров М.В., Матушкин Н.Н. Расширение класса нестандартных ограничений, применимых для планирования с фиксированными приоритетами в системах реального времени // Современная миссия технических университетов в развитии инновационных территорий: материалы международного семинара / ТУ Варна, Болгария.– Варна, 2004.– С. 125-134.

5. Кавалеров М.В., Матушкин Н.Н. Решение проблемы планирования задач с нестандартными ограничениями жесткого реального времени в концепции планирования с фиксированными приоритетами // Информационноуправляющие системы: сб. науч. тр. / Перм. гос. техн. ун-т. – Пермь, 2004. – С. 168-177.

6. Кавалеров М.В., Матушкин Н.Н. Применение интервальных нестандартных ограничений реального времени в условиях планирования с фиксированными приоритетами // Информационно-управляющие системы: сб. науч. тр.

/ Перм. гос. техн. ун-т.– Пермь, 2005.– С. 199-208.

7. Кавалеров М.В., Матушкин Н.Н. Применение обобщенных нестандартных ограничений реального времени в условиях планирования с фиксированными приоритетами // Информационные технологии моделирования и управления: научно-технический журнал, № 6(24). – Воронеж: Издательство « Научная книга 2005.–С. 842-848.

8. Кавалеров М.В., Матушкин Н.Н. Планирование задач с нестандартными ограничениям реального времени в системах автоматизации и управления // Современные проблемы информатизации в прикладных задачах: сб. трудов.

Вып. 11.–Воронеж: Издательство«Научная книга 2006.– С. 84-86.

9. Кавалеров М.В. Вычисление оценок параметров выполнения запросов, формируемых задачами реального времени, в условиях планирования с фиксированными приоритетами // Современные проблемы информатизации в моделировании и программировании: сб. трудов. Вып. 11. – Воронеж: Издательство «Научная книга 2006.– С. 183-184.

10. Kavalerov M., Matushkin N. A Formal Representation of Standard Timing Constraints for Periodic Real-Time Tasks // Acta Universitatis Pontica Euxinus, Vol. VI, No. 7, 2006.– P. 20-22.

В том числе публикация в журнале, указанном в перечне ВАК:

11. Кавалеров М.В. Преобразование линейных интервальных ограничений реального времени в стандартные ограничения // Системы управления и информационные технологии, №4.2(26), 2006.– С. 228-233.