автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Планирование задач в системах автоматизации и управления при нестандартных ограничениях реального времени

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

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

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

ВРЕМЕНИ

Специальность 05 13 06 - Автоматизация и управление технологическими процессами и производствами (в промышленности)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Пермь 2007

003058935

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

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

Матушкин Николай Николаевич

Официальные оппоненты

доктор физико-математических наук, профессор Абдуллаев Абдулла Рамазанович

кандидат технических наук Федорищев Иван Федорович

Ведущая организация

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

Защита диссертации состоится 25 мая 2007 г в 15 часов на заседании диссертационного совета Д212 188 04 при Пермском государственном техническом университете по адресу 614990, г Пермь, Комсомольский пр, 29, ауд 4236

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

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

/

Ученый секретарь диссертационного совета /

доктор технических наук, профессор

Южаков А А

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

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

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

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

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

Эффективность планирования можно повысить, если планирование задач осуществлять при непосредственном применении НО вместо того, чтобы каждое НО заменять допустимым СО Известны подобные решения проблемы для некоторых целевых классов НО В частности, можно отметить работы таких исследователей, как R Dobnn, G Fohler, Р Puschner, W Wang, AK Mok, К Sandstrom, С Norstrom Однако, в случае каждого из известных решений, целевой класс не включает многие НО, характерные для САиУ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Краткое содержание работы

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

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

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

Имеется множество из п задач ЖРВ {15, ,т„}, для краткости обозначаемое {т,} Каждая задача т, формирует запросы Каждый } -й запрос, обозначаемый т, ], формируется в момент времени гг ] Для любой периодической задачи т, при V/ > 1 всегда г1] - О, + (] - 1)Г,, где 01 — начальное смещение, 7] - период Задача т, может иметь СО в виде условия / < й1] = г1} + Д, где - время завершения выполнения , с\1} — крайний срок выполнения х1], -О, - относительный крайний срок т, Каждая задача т, имеет фиксированный приоритет л,, и множеству {т,} ставится в соответствие множество {л,} Имеется квант времени б, с учетом которого выполняются задачи РВ

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

к, > o;+o-i)r/

\f,,j ^+ о- 1)т' + д' ( )

где s, - время начала выполнения xt], Ol,T¡ - параметры СО Здесь и далее считается, что условие, задающее ограничение РВ, должно соблюдаться при У/>1 Доказано утверждение 1 1, о том, что, если СО(1) соблюдается при V/ > 1 для некоторых О,, Г,, то оно будет соблюдаться и при 0,=0,, Tt = Г, Доказано утверждение 1 2 о связи СО (1) со стандартным требованием РВ

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

Известен алгоритм, предложенный N С Audsley, который всегда находит подходящее множество {тс,}, если такое существует Этот алгоритм воспроизводится в несколько иной форме без принципиальных изменений, что вызвано необходимостью согласования этого алгоритма с другими алгоритмами диссертационной работы, и он обозначается как алгоритм 1 1 Также известен метод анализа выполнимости задачи т, при наличии только СО Этот метод оформляется в виде алгоритма 1 2 Затем, в виде алгоритма 1 3 описывается алгоритм планирования при наличии только СО Корректность такого описания обосновывается доказательством соответствующего утверждения 1 4

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

Приведены два примера НО, которые накладываются на моменты времени s, j, fUJ Для этих НО даны условия допустимости СО, что формулируется как утверждения 15,16, с соответствующими доказательствами Представлен обзор исследований, связанных с НО

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

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

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

Известно, что ограничение PB может быть связано не только с s, j и fl j, но и с другими моментами времени на интервале |Предлагается на этом интервале выделить два момента времени xU], ytJ Например, xt] -это момент получения информации о параметре объекта, a ytJ - момент формирования управляющего воздействия на объект При этом может оказаться, что х, =s, j, у, j =f, j Преимущества подобного подхода и его применение были рассмотрены в работах таких авторов, как R Gerber и A Burns

Приводятся примеры НО, которые накладываются на моменты времени x,j, у, j Один из этих примеров - это НО задачи контура управления (ЗКУ), которое определяется условием

{грххтт ^.mxrmax

у^-х^Т?*" ' U

где т™тт, f хх max ^ jxy max _ консхантЫ) ПрИ этом заранее устанавливается значение х, Q Другой пример - это НО задачи контура управления с усреднением интервала (ЗКУУИ), которое основано на НО ЗКУ и определяется условием

rpXX min ^ „ ^ rpxx max

Л -Xl,)~Xi,j- \S1i

■ Г,™ ~xn УЩ <T™ (3)

где константы ram, 7^™3:max определяют диапазон допустимых значений xl j -jc(;J_j, усредненных по ml предыдущих запросов, при этом заранее устанавливаются значения +1, ,X,-1 ,Xl0

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

Класс НО выделяется следующим определением Линейное интервальное ограничение (ЛИО) для задачи х,, обозначаемое Е,, - это ограничение PB, представимое при V/ > 1 в виде условия

V > vmm - тягГушт rram ттт ï с vmax _ f max max max -,

тш _ „ш \

(4)

mm „,„-,/•,,mm „вт „тл \

yltJ<y™=mm(y™ly™}, ,y™4)

-x,rJ >xy,7 =max{xy™,xy™, ,xy™s)

. шhi шах . min max min max

где xtJ , xhJ , yt] , yl } , xyl} , xytJ - минимальные и максимальные значения интервалов допустимых значений xtJ, yl }, yl } - xhJ соответственно, V), ,v6 определяют количество вариантов, x™", х™*, у™*,

ху™ обозначают v-й вариант соответствующих значений, и каждый из вариантов - это или - со (может быть только после ">"), или оо (может быть только после "<"), или выражение, представимое в виде

¿max кр

Z akx,,j-k + Z РкУи-к +Y7+S, (5)

к=1 к=\

где к™ах, к™* -целые неотрицательные значения; ак при V/ce[l,£™ax], ßA при V^etl^p"331], у, 5 - константы, заданные для данного варианта, при этом все xt J_k, y,j-.k для j-k<0, которые могут использоваться в выражениях вида (5), являются константами, заданными для данного Н,

Множество всех возможных ЛИО формирует класс ЛИО Доказана справедливость утверждения 2 1 об одном полезном свойстве ЛИО Также показано, что рассмотренные примеры НО относятся к классу ЛИО Например, для

и — о _min _ 71» min „min , твсс mm

¿КУУИ v1-Z, xlJil=xhJ_l+il ' xi,j,2~xi,j-m +miTi , аналогич-HO v2 = 2, = xi,j-\ + , . v3,v4,v5,v6 рав-

ны 1, J™" =-оэ, y™ = 00, =-oo, ^max =7,xvmax KpQMe П0казан0)

что CO периодической задачи является ЛИО При этом важно, что класс ЛИО не входит в целевые классы НО известных подходов

Отмечено, что обращение к моментам времени xhJ, у обуславливает необходимость уточнения временных характеристик запросов С каждым запросом связано 4 момента времени st], xhJ, yl }, fUJ, и существует 6 различных компонентов it с соответствующими длительностями На основе известных методик для каждого компонента можно определить нижнюю и верхнюю оценку его длительности выполнения Поэтому считается, что известны 12 оценок Csxf0, Csx\'p, Csy1;0, Csy"p, Csf,Lo, Csf^p, Cxy[° , CxyLp, Cxff0, Cxf^p, Cyf,Lo, Cyf^p, где Csxf0, Csx^p — нижняя и верхняя оценка длины интервала по V/>1 при отсутствии прерываний запроса другие оценки определяются аналогично

Разрабатывается алгоритм преобразования любого НО из выделенного

класса (т е любого ЛИО) в допустимое СО Сочетание (О, ,7) , DJ называется допустимым, если соответствующее СО является допустимым Предлагаемый способ преобразования состоит из двух этапов 1) получение достаточного условия допустимости (О, ,Tf ,D() (в дальнейшем, для краткости, указание на достаточность опускается), 2) выбор допустимого сочетания (О, ,Т1 ,£>,), которое и определит допустимое СО, либо сообщение о невозможности такого выбора Указанные этапы реализуются на основе соответствующих алгоритмов

Разработан алгоритм 2 1, реализующий получение условия допустимости для любого ЛИО S, Его можно кратко описать так Сначала в условии (4) данного Е, вместо xt j в 1-ми 2-м неравенствах, yt ; в 3-м и 4-м неравенствах,

уг j -х, j в 5-м и 6-м неравенствах подставляются О* + ( / -\)Т* + Csxf",

о: + и-\)т;+Dl-Cxfti0, oU(j-\)t; + CSyi°, О* + (j-1)?;*+D,~ CyftLo, Cxyf", D} - Cyf!M - Cs%l° соответственно Затем, каждое неравенство заменяется эквивалентной совокупностью неравенств, имеющих в правой части только один компонент из соответствующего шах или min Удаляются неравенства, правая часть которых - это - оо или со Пусть полученная совокупность неравенств обозначается W Определяется значение v, равное такому минимальному значению j среди Vjt 1, при котором в составе выражений вида (5) в случае всех неравенств значения х1}_к, Уи]-к Для j-k< 1 не используются или умножаются на 0 Для каждого целого числа z из интервала [l,v] выполняются следующие действия над W 1) у каждого xhJ_k, у, в составе выражений вида (5) правой части каждого неравенства индекс j -к заменяется числом z — k, 2) каждое xl z_k, yt z_k при z-k> 0 из правой части каждого неравенства заменяется своей нижней или верхней оценкой так, чтобы неравенство, полученное после указанной замены, было достаточным условием выполнения исходного неравенства При этом в качестве нижней и верхней оценки применяются О* +(j-к-1 )Т* + Csx1'0, О* + {j-к- \)Т* + D, - Cxf,Lo соответственно В качестве нижней и верхней оценки ytz-k применяются

О* + (j-к-Y)T* + Csyf0 и О] +(j-k-l)T* + Di-Cyf1to соответственно В результате для каждого z совокупность W преобразуется в совокупность, обозначаемую IV,(j), так как переменная j присутствует в выражениях для оценок xl z_k, у\ 7_к При этом fVy(j) сохраняется отдельно Для Vz е [l,v] выполняется преобразование W7{j) в совокупность, обозначаемую Wz, путем замены переменной j числом z Каждое неравенство из Wv(j) преобразуется к виду 4>iJ + Фг - 0» где ср1; ф2 - компоненты, которые не зависят от j Затем, каждое такое неравенство заменяется на (pj ^ 0 В итоге получается совокупность неравенств, обозначаемая ^ Алгоритм выдает условие допустимости, сформированное на основе объединения совокупностей Щ, , ^

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

Проблема выбора допустимого (О, ,Тг , Ц) сводится к задаче линейного программирования (ЛП) применительно к переменным Ot ,Tt и ограничениями, задаваемым условием допустимости Подробно рассматривается определение целевой функции Показано, что увеличение Tt и Dl с большой вероятностью облегчает планирование В итоге выбрано решение - это максимизация величины Т, + D, Может оказаться, что несколько пар (Tt ,Д) дают максимизацию 7] + D, Для выбора пары заранее устанавливается константа 9, задающая желаемое соотношение Dl / Ti для всех задач т,, имеющих НО

Разработан алгоритм 2 2, реализующий преобразование любого ЛИО в допустимое СО на основе указанных принципов Его можно кратко описать так Сначала формируется условие допустимости с помощью алгоритма 2 1 Затем, с помощью задачи ЛП определяется максимальное значение Т, +Д После этого, с помощью дополнительной задачи ЛП определяется

пара (Г,*,/),), которая минимизирует \р, /Т* среди пар, максимизирующих

Т* + Ог Если для первой задачи ЛП решения не существует, то алгоритм завершается с соответствующим сообщением Из-за наличия кванта времени е решаемые задачи ЛП являются целочисленными

Доказано утверждение 2 3^ что, если результат алгоритма 2 2- это значения 01,Т1 , £>,, то значения 01 ,Т1 ,Д определяют допустимое СО, при этом обеспечивают минимальное значение /Г,* - б| среди всех допустимых (О, ,7] ,Д), обеспечивающих максимальное значение Т* + О,

На основе алгоритмов 1 3, 2 2 строится алгоритм 2 3, реализующий базовый подход к планированию при наличии любых НО из выделенного класса, т е любых ЛИО Доказано утверждение 2 4, что при наличии только ЛИО множество {-с,} является выполнимым, если алгоритм 2 3 выдает сообщение о выполнимости {х,} Поэтому алгоритм 2 3 может использоваться для планирования {т,} при наличии любых ЛИО

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

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

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

Параметры выполнения запроса т,^ обозначаются , гх1}, гу\ }, г/1 > . я/^, хуи], , у/и], где = - , другие параметры определяются аналогично Для каждого из параметров можно определить его нижнюю и верхнюю оценку

Разработаны алгоритмы 3 1, 3 2, 3 3, обеспечивающие вычисление указанных оценок При разработке алгоритмов за основу принимались алгоритмы вычисления оценок для времени отклика из работ таких авторов, как К Ттс1е11, О Яес1е11, М БапГпс^оп Доказаны утверждения 3 1, 3 2,3 3, которые обосновывают корректность получаемых оценок

Разработан алгоритм 3 4, реализующий формирование условия выполнимости задачи с любым НО из выделенного класса, тес любым ЛИО Н, Данный алгоритм можно описать как алгоритм, получаемый из алгоритма 2 1 на основе следующих его модификаций Во-первых, в условии (4) данного Н, вместо у1 , у1} подставляются не выражения, указанные в соответствующей части описания алгоритма 2 1, а выражения 01 + (у - 1)Г, + гх''°, О1+0-т+гх?р, 01+ и-ЦТ, + ГУ?, О,+0-1)Г1+туУР, ху?, ху?, где гх?, гх^р, гу, ту?, ху?, ху^р — соответственно нижние и верхние оценки ГХ1 ¡1 ]■> ХУ, ] При этом, если затем удаляются все неравенства, то алгоритм завершается с результатом в виде условия выполнимости, тождественного значению «истина» Во-вторых, в качестве нижней и верхней оценки х к

применяются О, + (у - к -1 )Т, + гх, 01 + (у - к -1)7} + гх^р соответственно, а в качестве нижней и верхней оценки у: 2_к применяются соответственно

Ot +{j - к-1)7*, + ryf°, 0,+{j-k-Щ + ry^p В-третьих, результатом алгоритма будет не условие допустимости, а условие выполнимости

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

На основе алгоритма 3 4, а также алгоритма 3 3, использующего алгоритмы 3 1,3 2, реализуется алгоритм 3 5, обеспечивающий анализ выполнимости задачи с любым ЛИО

Разработан алгоритм 3 6, реализующий планирование при непосредственном применении любых ЛИО Его можно кратко описать так С помощью алгоритма 2 2 каждое имеющееся ЛИ О преобразуются в допустимое СО Для каждой периодической задачи х, устанавливается Ot = О*, Tt = Т* Если не выполняется условие ограниченности очереди запросов, а именно условие

" CsfUp

(6)

1=1

то алгоритм завершается с сообщением о невозможности обеспечить выполнимость {х,} Вызывается алгоритм 1 1, при этом в качестве его входных данных используются множество {т,}, алгоритм 1 2 для каждой задачи из {х,}, имеющей исходное СО, алгоритм 3 5 для каждой задачи из {т,}, имеющей ЛИО Если в результате этого выполнения оказывается, что множество {л,} сформировано, и множество {т,} является выполнимым, то тогда алгоритм завершается с результатом, содержащим множество {х,} с определенными значениям {О,,Тпп1 |ге[1,л]} и сообщение о выполнимости {х,}, иначе алгоритм завершается с сообщением о невозможности обеспечить выполнимость {х,}

Для удобства алгоритм 3 6 называется алгоритмом А, так как применение ЛИО происходит при анализе (А) выполнимости Доказано утверждение 3 5 о том, что при наличии только ЛИО множество {х,} является выполнимым, если алгоритм А выдает сообщение о выполнимости {х,} Поэтому алгоритм А может использоваться для планирования {х,} при наличии любых ЛИО Показано, что эффективность планирования можно повысить, если О,, 7j

для каждой задачи, имеющей ЛИО, задавать после назначения приоритетов

С этой целью сначала разработан алгоритм 3 7, который формирует максимально допустимое значение Тг для каждой задачи, имеющей ЛИО, среди задач с приоритетами в заданном диапазоне Его можно кратко описать так Выбирается очередная задача х,, при этом для каждой задачи с более высоким приоритетом уже известны значения Ol,Tl,nl. С помощью алгоритма 3 4 для т, формируется условие выполнимости С помощью алгоритма 3 3 вычисляются те оценки параметров выполнения запросов, которые встречаются в условии выполнимости для х, При этом предполагается, что fUJ <rt J+l для V/ >1 Решается целочисленная задача ЛП для переменных О,, Tt и ограничений в виде всех неравенств условия выполнимости для х,, при этом максимизируется 7\ Если задача ЛП не имеет решения, то алгоритм досрочно завершается Иначе О,, Г,, полученные после решения задачи ЛП, устанавливаются как парамет-

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

В итоге, разработан алгоритм 3 8, который реализует планирование при непосредственном применении любых ЛИО Его можно кратко описать так С помощью алгоритма 2 2 выполняется преобразование имеющихся ЛИО в допустимые СО Задачи сортируются по возрастанию значений 25,, и приоритеты назначаются согласно номеру задачи в отсортированном списке Так, задача с наименьшим Д получает наивысший приоритет Выполняется алгоритм 3 7 Если он завершается досрочно, то делается переход к последнему шагу алгоритма 3 8 Если не выполняется условие (б), то также делается переход к последнему шагу алгоритма 3 8 Производится анализ выполнимости каждой задачи из {т,}, для этого в случае задачи, имеющей СО, вызывается алгоритм 1 2, а в случае задачи, имеющей ЛИО, вызывается алгоритм 3 5 Если в случае хотя бы одной задачи выдается сообщение о том, что выполнимость этой задачи не гарантируется, тогда делается переход к последнему шагу алгоритма 3 8 Алгоритм завершается с результатом, содержащим множество {т,} с определенными \01,Т1,п[ |г е[1,я]} и сообщение о выполнимости {т,} Последний шаг алгоритма состоит в вызове алгоритма А для планирования {т,}, так как переход к этому шагу означает, что не удается обеспечить выполнимость {т,} Поэтому алгоритм А вызывается, чтобы попробовать обеспечить выполнимость {т,} другим способом В этом случае алгоритм 3 8 завершается с результатом выполнения алгоритма А

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

Доказано утверждение 3 7 о том, что алгоритм АП более эффективен, чем алгоритм А, и алгоритм А более эффективен, чем базовый алгоритм 2 3 Здесь применяется понятие сравнительной эффективности, введенное в первой главе Тогда алгоритм АП следует считать результатом решения 4-й задачи исследования, так как он эффективнее алгоритма А Тем не менее, алгоритм А играет важную роль в качестве составной части алгоритма АП

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

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

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

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

В целом, при различных способах генерирования {-с,} результаты моделирования показывают преимущество алгоритмов А и АП на средних загрузках, и значительное преимущество алгоритма АП на больших загрузках по сравнению с базовым алгоритмом 2 3 Это означает, что при разработке алгоритмов Айв особенности алгоритма АП, удалось реализовать значительное повышение эффективности планирования при непосредственном применении НО по сравнению с базовым подходом Кроме того, результаты моделирования показали, что переход от алгоритма А к алгоритму АП является оправданным, так как при этом эффективность планирования повышается существенно, и одновременно уменьшается загрузка задачами ЖРВ, что оставляет больше свободного времени для выполнения задач мягкого РВ Таким образом, решена 5-я задача исследований

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

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

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

-о— Базовый алгоритм —о— Алгоритм А —л— Алгоритм АП

Опорное значение загрузки, %

Рисунок Пример результатов имитационного моделирования

Основные результаты и выводы

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

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

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

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

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

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

1 Kavalerov М V Soft Real-Time Tasks Scheduling Based on Dynamic Tim-mg Constramts in Fixed Pnority Preemptive Systems // CSIT'2000, Proceedmgs of 2nd International Workshop on Computer Sciencc and Information Technologies, September 18-23, 2000, Ufa, Russia -P 319-322

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

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

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

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

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

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

8 Кавалеров M В , Матушкин H H Планирование задач с нестандартными ограничениям реального времени в системах автоматизации и управления // Современные проблемы информатизации в прикладных задачах сб трудов Вып 11 -Воронеж Издательство «Научная книга», 2006 - С 84-86

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

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

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

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

Подписано в печать 23 04 07 Формат 60X90/16 Набор компьютерный Тираж 100 экз Объем 1,0 уч изд п л Заказ № 641/2007

Издательство

Пермского государственного технического университета 614600, г Пермь, Комсомольский пр , 29, к 113 тел (342)219-80-33

Список используемых сокращений.

Список используемых обозначений.

Список используемых ссылок.

Введение.

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

1.1. Общие сведения.

1.1.1. Функционирование в реальном масштабе времени.

1.1.2. Планирование задач реального времени.

1.1.3. Основные концепции планирования.

1.1.3.1. Табличное планирование.

1.1.3.2. Планирование с фиксированными приоритетами.

1.1.3.3. Планирование с динамическими приоритетами.

1.2. Базовая модель.

1.2.1. Общие положения.

1.2.2. Задачи жесткого реального времени.

1.2.3. Диспетчеризация.

1.2.4. Планирование.

1.2.4.1. Общие положения.

1.2.4.2. Стандартное ограничение реального времени.

1.2.4.3. Планирование при наличии только стандартных ограничений

1.2.5. Эффективность планирования.

1.3. Нестандартные ограничения реального времени в условиях планирования с фиксированными приоритетами.

1.3.1. Исходные, допустимые, нестандартные ограничения реального времени.

1.3.2. Примеры нестандартных ограничений.

1.3.2.1. Ограничение задачи контура управления.

1.3.2.2. Ограничение задачи отслеживания событий.

1.3.3. Краткий обзор исследований, связанных с нестандартными ограничениями.

1.3.4. Базовый подход к планированию при наличии нестандартных ограничений.

1.3.5. Повышение эффективности планирования за счет непосредственного применения нестандартных ограничений.

1.4. Выводы по главе 1.

2. Выделение класса нестандартных ограничений и реализация базового подхода.

2.1. Необходимость выделения класса нестандартных ограничений

2.2. Значимые моменты времени запроса.

2.3. Дополнительные примеры нестандартных ограничений.

2.3.1. Ограничение задачи контура управления.

2.3.2. Ограничение задачи отслеживания событий.

2.3.3. Ограничение задачи контура управления с усреднением интервала

2.4. Базовые допущения.

2.5. Класс линейных интервальных ограничений.

2.5.1. Определение линейного интервального ограничения.

2.5.2. Примеры линейных интервальных ограничений.

2.5.3. Другие примеры линейных интервальных ограничений.

2.5.4. Стандартное ограничение периодической задачи как линейное интервальное ограничение.

2.6. Длительности компонентов запроса с учетом значимых моментов времени.

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

2.7.1. Общие положения.

2.7.2. Алгоритм формирования условия допустимости.

2.7.3. Получение условий допустимости для различных примеров нестандартных ограничений.

2.7.3.1. Условие допустимости в случае нестандартного ограничения задачи контура управления.

2.7.3.2. Условие допустимости в случае нестандартного ограничения задачи отслеживания событий.

2.7.3.3. Условие допустимости в случае нестандартного ограничения задачи контура управления с усреднением интервала.

2.7.4. Формирование допустимого стандартного ограничения на основе условия допустимости.

2.8. Базовый подход к планированию при наличии нестандартных ограничений из выделенного класса.

2.9. Выводы по главе 2.

3. Разработка алгоритмов планирования при непосредственном применении нестандартных ограничений из выделенного класса.

3.1. Применение нестандартных ограничений в ходе анализа выполнимости (подход А).

3.2. Оценки параметров выполнения запросов.

3.3. Вычисление оценок параметров выполнения запросов.

3.4. Алгоритм формирования условия выполнимости.

3.5. Получение условий выполнимости для примеров нестандартных ограничений.

3.5.1. Условие выполнимости в случае нестандартного ограничения задачи контура управления.

3.5.2. Условие выполнимости в случае нестандартного ограничения задачи отслеживания событий.

3.5.3. Условие выполнимости в случае нестандартного ограничения задачи контура управления с усреднением интервала.

3.6. Получение условия выполнимости для стандартного ограничения.

3.7. Алгоритм А.;.

3.8. Применение нестандартных ограничений в ходе анализа выполнимости и при формировании периода (подход АП).

3.9. Формирование максимально допустимого периода для каждой задачи, имеющей нестандартное ограничение.

ЗЛО. Алгоритм АП.

3.11. Эффективность разработанных алгоритмов.

3.12. Выводы по главе 3.

4. Применение разработанных алгоритмов планирования.

4.1. Оценка эффективности разработанных алгоритмов планирования на основе имитационного моделирования.

4.1.1. Цель и методика имитационного моделирования.

4.1.2. Результаты имитационного моделирования.

4.1.2.1. Эксперимент 1.

4.1.2.2. Эксперимент 2.

4.1.2.3. Эксперимент 3.

4.1.2.4. Эксперимент 4.

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

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

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

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

Эффективность планирования можно повысить, если планирование задач осуществлять при непосредственном применении НО вместо того, чтобы каждое НО заменять допустимым СО. Известны подобные решения проблемы для некоторых целевых классов НО. В частности, можно отметить работы таких исследователей, как Я. БоЬпп, в. БоЫег, Р. РивсИпег, \Vang, А.К. Мок,

К. Запс^гот, С. Могейгот. Однако, в случае каждого из известных решений, целевой класс не включает многие НО, характерные для САиУ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основное содержание диссертации отражено в 11 публикациях [26,27, 64 - 72]. Результаты, полученные в ходе работы над диссертацией, докладывались на 5 конференциях, относящихся к международным, всероссийским, межвузовским.

Работа состоит из введения, четырех глав, заключения, списка литературы и приложений.

Основные результаты данной работы состоят в следующем.

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

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

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

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

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

Заключение

1. Работы располагаются в алфавитном порядке по фамилии первого автора (сначала латиница, потом кириллица), а при одинаковом первом авторе сортируются по году.

2. Abeni L., Buttazzo G. Integrating Multimedia Applications in Hard RealTime Systems // Proceedings of 19th IEEE Real-Time Systems Symposium. Madrid, Spain, 1998.-P. 4-13.

3. Audsley N. C. Deadline Monotonic Scheduling, September 1990, Technical Report YCS146, Department of Computer Science, University of York. 38 p.

4. Audsley N.C., Burns A., Richardson M.F., Wellings A. J. Incorporating Unbounded Algorithms Into Predictable Real-Time Systems. Department of Computer Science, University of York, UK September 1991.

5. Audsley N.C. Optimal Priority Assignment and Feasibility of Static Priority Tasks with Arbitrary Start Times. Technical Report YCS164, Department of Computer Science, University of York, UK, 1991. 31 p.

6. Audsley N., Tindell K., Burns A. The End of the Line for Static Cyclic Scheduling. Technical Report, University of York, England, 1993.

7. Bate I, Burns A. An Approach to Task Attribute Assignment for Uniprocessor Systems // Proceedings of 11th Euromicro Conference on Real-Time Systems, 1999.-P. 46-53.

8. Bate I., Burns A. A Framework for Scheduling in Safety-Critical Embedded Control Systems // Proceedings of the 6th International Conference on Real-Time Computing Systems and Applications (RTCSA'99), 1999.

9. Bernat G. Specification and Analysis of Weakly Hard Real-Time Systems, PhD thesis, 1998

10. Burns A. Preemptive Priority Based Scheduling: An Appropriate Engineering Approach. Technical Report YCS-93-214, University of York, 1993. 19 p.

11. Burns A., Bernat G. Jorvik: A Framework for Effective Scheduling. Department of Computer Science, University of York, York, 2001.

12. Caccamo M., LipariG., Buttazzo G. Sharing Resources among Periodic and Aperiodic Tasks with Dynamic Deadlines // Proceedings of the IEEE Real-Time Systems Symposium, Phoenix, Arizona, December 1999.

13. Cervin A., Eker J. The Control Server: A Computational Model for RealTime Control Tasks // Proceedings of 15th Euromicro Conference on Real-Time Systems. Porto, Portugal, 2003. - P. 113-120.

14. Choi S., Agrawala A.K., Dynamic Dispatching of Cyclic Real-Time Tasks with Relative Timing Constraints // Real-Time Systems, 19(1), 2000.

15. Davis R.I. Approximate Slack Stealing Algorithms for Fixed Priority Preemptive Systems // Technical Report YCS-93-216 / University of York. York, 1993.-28 p.

16. Davis R.I. Scheduling Slack Time in Fixed Priority Pre-emptive Systems. Technical Report YCS-93-217, University of York,York, 1993. 24 p.

17. Davis R.I. On Exploiting Spare Capacity in Hard Real-Time Systems, PhD Thesis, University of York, 1995. 283 p.

18. Davis R.I., Burns A. Hierarchical Fixed Priority Pre-emptive Scheduling. Technical Report YCS-2005-385, Department of Computer Science, University of York, UK, 2005. 58 p.

19. Dobrin R., Fohler G., Puschner P. Translating Off-line Schedules into Task Attributes for Fixed Priority Scheduling // Proceedings of 22nd IEEE Real-Time Systems Symposium. London, 2001. - P. 225-234.

20. FohlerG., Flexibility in Statically Scheduled Hard Real-Time Systems. Dissertation, Eingereicht an der Technischen Universität Wien, TechnischNaturwissenschaftliche Fakultat, Wien, 1994. -101p.

21. FohlerG. Dynamic Timing Constraints Relaxing Over-constraining Specifications of Real-Time Systems // Proceedings of Work-in-Progress Session, 18th IEEE Real-Time Systems Symposium, 1997. - P. 27-30.

22. Gardner M.K., LiuJ.W.S. Performance of algorithms for scheduling realtime systems with overrun and overload //1 Ith Euromicro Conference on Real-Time Systems. June 1999.

23. Gerber R., Hong S. Semantics-Based Compiler Transformations for Enhanced Schedulability // Proceedings of 14th IEEE Real-Time Systems Symposium, 1993.-P. 232-242.

24. Gerber R., Pugh W., SaksenaM. Parametric dispatching of hard real-time tasks // IEEE Transactions on Computers, 44(3), 1995.

25. Gutierrez J. P., Harbour M. G. Schedulability Analysis for Tasks with Static and Dynamic Offsets // Proceedings 19th IEEE Real-Time Systems Symposium, 1998.

26. Isovic D., FohlerG. Efficient Scheduling of Sporadic, Aperiodic, and Periodic Tasks with Complex Constraints // Proceedings of the 21st IEEE Real-Time Systems Symposium, USA, November, 2000.

27. 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.

28. KopetzH., Zainlinger R., FohlerG., KantzH., Puschner P., Schutz W. An Engineering Approach to Hard Real-Time System Design // Institut fur Technische Informatik Technische Universität Wien Treitlstr. 3/182, Austria, 1998.

29. Lehoczky J. P., Sha L., Strosnider J. K. Enhanced Aperiodic Responsiveness in Hard Real-Time Environments // Proceedings IEEE Real-Time System Symposium, San Jose, 1987. P. 261-270.

30. Lehoczky J. P., Ramos-Thuel S. An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks Fixed Priority Pre-emptive systems // Proceedings IEEE Real-Time Systems Symposium, 1992. P. 110-123.

31. Liu C. L., Layland J. W. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment // Journal of the Association for Computing Machinery, Vol. 20, No. 1, January 1973. P. 46-61.

32. Liu J.,Lin K., Shih W., Yu A., Chung J., Zhao W. Algorithms for Scheduling Imprecise Computations // IEEE Computer, May 1991.

33. Marti P., Villa R., Fuertes J.M., Fohler G. On Real-Time Control Tasks Schedulability. Dep. of Automatic Control, Universität Politécnica de Catalunya, 2000.

34. Marti P., Fohler G., Ramamritham K., Fuertes J. M. Jitter Compensation for Real-Time Control Systems // Proceedings of 22nd IEEE Real-Time Systems Symposium, 2001. P. 39-48.

35. Marti P., Villa R., Fuertes J. M., Fohler G. Stability Of On-Line Compensated Real-Time Scheduled Control Task. Technical Report, Dept. of Automatic Control Technical University of Catalonia, 2001

36. Mäki-Turja J., Nolin M. Faster Response Time Analysis of Tasks With Offsets // Proceedings 10th IEEE Real-Time Technology and Applications Symposium, 2004.

37. Mäki-Turja J., Nolin M. Fast and Tight Response-Times for Tasks with Offsets // Proceedings of 17th Euromicro Conference on Real-Time Systems. 2005.

38. Ramamritham K., Stankovic J. Scheduling Algorithms and Operating Systems Support for Real-Time Systems // Proceedings of the IEEE, Vol. 82, No. 1, January 1994. P. 55-67.

39. Redell O., Sanfridson M. Exact Best-Case Response Time Analysis of Fixed Priority Scheduled Tasks // Proceedings of 14th Euromicro Conference on Real-Time Systems. Vienna, 2002.

40. Sandström K., Norström C. Managing Complex Temporal Requirements in Real-Time Control Systems // Proceedings of 9th IEEE Conference on Engineering of Computer-Based Systems. Lund, 2002. - P. 103-109.

41. Sha L., LehoczkyJ. P., RajkumarR. Solutions For Some Practical Problems in Prioritised Preemptive Scheduling // Proceedings IEEE Real-Time Systems Symposium, 1986.-P. 181-191.

42. Sha L., Sprunt B., Lehoczky J. P. Aperiodic Task Scheduling for Hard Real-Time Systems // Real-Time Systems 1(1), 1989. P. 27-69.

43. Sha L., Abdelzaher T., ÁrzénK. E., CervinA., Baker T., Burns A., But-tazzo G., Caccamo M., Lehoczky J., Mok A. K. Real-Time Scheduling Theory: A Historical Perspective // Real-Time Systems 28, 2004. P. 101-155.

44. Sprunt B., Lehoczky J., Sha L. Exploiting Unused Periodic Time For Aperiodic Service Using the Extended Priority Exchange Algorithm // Proceedings of IEEE Real-Time Systems Symposium, December 1988. P. 251-258.

45. SpuriM., ButtazzoG. Scheduling Aperiodic Tasks in Dynamic Priority Systems //Real-Time Systems, vol. 10,1996.-P. 179-210.

46. Stankovic J. Real-Time Computing // BYTE, invited paper, August 1992. -P. 155-160.

47. Stankovic J., Spuri M., Di Natale M., Buttazzo G. Implications of Classical Scheduling Results for Real-Time Systems // IEEE Computer, Vol. 28, No. 6, June 1995.-P. 16-25.

48. Sun J., Liu J. W. S. Bounding completion times of jobs with arbitraiy release times and variable execution times //Proceedings of the IEEE Real-Time Systems Symposium, Washington D.C., 1996. P. 164-173.

49. Thomadakis T.M.E., Liu J.C.S. Linear Time On-Line Feasibility Testing Algorithms for Fixed-Priority Hard Real-Time Systems. Technical Report CS-TR-00-006, Dept. of Computer Science, Texas A&M University, 2000.

50. Tia T.-S., Liu J.W.S., Shankar M. Aperiodic Request Scheduling in Fixed-Priority Preemptive Systems. Technical Report UIUCDCS-R-94-1859, University of Illinois at Urbana-Champaign, 1994.

51. Tia T.-S. Utilizing Slack Time for Aperiodic and Sporadic Requests Scheduling in Real-Time Systems. PhD thesis, University of Illinois at Urbana-Champaign, April 1995.- 104 p.

52. Tindell K. Using Offset Information to Analyse Static Priority Preemptively Scheduled Task Sets. Technical Report YCS-182, Dept. of Computer Science, University of York, England, 1992. 17 p.

53. Tindell K.W. An Extendible Approach for Analysing Fixed Priority Hard Real-Time Tasks. Technical Report YCS-92-189, University of York, 1992. 16 p.

54. Tindell K., Burns A., WellingsA. Allocating Hard Real-Time Tasks (An NP-Hard Problem Made Easy). Technical Report, University of York, 1995.

55. Wang W., Мок A.K., Fohler G. Generalized Pre-Scheduler // Proceedings of 16th Euromicro Conference on Real-Time Systems. Catania, 2004. - P. 127-134.

56. Wittenmark В., Nilsson J., Torngren M. Timing Problems in Real-Time Control Systems: Problem Formulation // Proceedings of the American Control Conference. Seattle, 1995. - 9 p.

57. Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. - 416 с.

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

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

60. Кавалеров М.В., Матушкин H.H. Об уточнении ограничений реального времени на основе анализа физических процессов // Необратимые процессы в природе и технике: Труды Четвертой Всероссийской конференции.-М.: МГТУ им. Н.Э. Баумана, ФИАН, 2007.

61. Олссон Г., Пиани Д. Цифровые системы автоматизации и управления. СПб.: Невский Диалект, 2001. - 557 с.

62. Сушков Б.Г. ЭВМ управляет экспериментом (вычислительные системы реального времени). М.: Знание, 1987. - 32 с.

63. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984. - 381 с.

64. Теория расписаний и вычислительные машины / Под ред. Коффма-на Э.Г. М.: Наука, 1984. - 334 с.