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

! В да- 9 В1

МОСКОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ШШНЕРНО-ШЗИЧЕШЙ ИНСТИТУТ

На правах рукописи МАКАРОВ ВЕКТОР ВАЛЕНТИНОВИЧ

УД{ 681.3.031

ИССЛЕДОВАНИЕ МЕТОДОВ УСТРАНЕНИЯ ПОШЛИННЫХ СИТУАЦИЙ В ШОГОШЩИОНАЛЬНОЙ ОПЕРАЦИОННОЙ СИСТЕМЕ: РЕАЛЬНОГО ВРЕШШ

05.13.13 - вычислительные машины, комплексы, системы и сети

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

Еосква 1390

Работа выполнена в Московском ордена Трудового Красного Знамени инженерно-физическом институте.

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

профессор Соловьев Г.Н.

Официальные оппоненты: доктор технических наук,

профессор Перминов О.Н.

кандидат технических наук Веретенников C.B.

Ведущая организация; Институт электронных управ-

ляющих машин (ИНЭУМ) г.Москва

Защита состоится giKûSpp 1990 г. в 1£ час. на заседании специализированного сопета KQ53.03.06 в Московском инженерно-физическом институте по адресу: 155409, Москва, Каширское шоссе, 31; тел.324-84-98.

С диссертацией можно ознакомиться в библиотеке И®И.

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

Автореферат разослан " ib " ноября 1990 г. ■

Ученый секретарь специализированного

совета А.Т.Воронин

V/

Подписано к печати3V й.^ахаэ Тира« 100 экз.

Типография ШЙ, Каширское шоссе, д.31.

общая характеристика ?шуш

дальность темы.

0,р„л"СЛеди огромного разнообразия вычислительных систем, рабо-Ь. режиме реального времени, вьделяются системы, со став-""~15яюп{Ке особый класс, которые характеризуются жесткими ограничениями на время реакции на внешние события, циклическим харак-. тером вычислительного процесса, наличием сложной аппаратуры связи ЭВМ с объектом, по объему сравнимой с аппаратурой вычислительного комплекса и являющейся нестандартными внешними устройствами (НВУ) по отношению к ЭВМ, наличием многих параллельно работающих пользователей, активной роль оператора системы. Характерными представителями такого класса являются системы управления ускорителями заряженных частиц и системы управления испытаниями больших комплексов радиоэлектронной аппаратуры. В дальнейшем такие системы условно называются системами с жесткими ограничениями на время реакции (СШВР).

Вычислительный процесс в таких СЕОВР имеет, при коллективном ее использовании черты режима реального времени, разделения времени, пакетной обработки заданий. Операционные системы однопроцессорных ЭВМ, обеспечивающие параллельное управление двумя • или более режимами вычислительного процесса, получили в литературе условное наименование многофункциональных операционных систем (10ЮС).

Многопользовательский характер работы рассматриваемых систем приводит к необходимости экономии ресурсов для повышения пропускной способности. По отношении к ресурсам ЭВМ (время процессора, памят , устройства) эта задача может быть решена наращиванием вычислительной мощности.применяемой ЭВМ, но повышения пропускной способности при такой подходе можно ожидать только по отношению к процессам, не участвующим или участвующим в незначительной степени в обмене информацией с аппаратурой объекта управления. Для процессов же реального времени фактором, препятствующим повышению пропускной способности, является разделение дорогостоящих и уникальных ресурсов 07 между многими пользователями. Естественным решением было бы объединение за. просов пользователей некоторым центральным распределителем ресурсов.

Однако такая организация находится в противоречии с принципиальным требованием обеспечения min времени реакции в СЖОВР. Как следует из анализа организации действующих систем реального времени, минимальное время реакции достигается в системах с min "программным расстоянием" (числом звеньев в цепочке прохождения запросов пользователя до получения им необходимых данных), Это "расстояние" определяется степенью централизации обработки данных и минимально при полностью децентрализованной обработке.

Из изложенного следует, что распределение ресурсов в МЗЮС для систем рассматриваемого класса не может осуществляться тра-диционныш методами, основанными на очередизации запросов процессов и буферировании ввода-вывода. Поэтому в таких системах возникают особые условия появления разноообразных конфликтных ситуаций (КС), под которыми в работе понимается наличие неудовлетворенных запросов на один и тот же ресурс со стороны более чем одного независимого процесса в один и тот не момент реального времени.

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

Методы устранения КС ь подобных системах, как следует из литературы, в настоящее время ке разработаны. В то же время имеется ряд значительных достижений в области теории конфликтов в вычислительных системах для параллельных вычислений, многомашинных и многопроцессорных систем, сетей ЭВМ, причем, как правило,. основное внимание уделяется тупиковый конфликтным ситуациям (ТС) как наиболее опасным.

Основными методами устранения КС при параллельных вычислениях являются предварительный анализ текста программ и синтез

таких программ при достаточно жестких схемах распределения ресурсов. Для такого анализа широко используется аппарат сетей Петри, однако использование отого аппарата неприемлемо для обнаружения КС в СКОВР, где требуется анализировать систему и принимать решения в режиме реального времени.

Результаты исследований в области многопроцессорных вычислительна систем, такие непосредственно не могут быть использованы а рассматриваемых системах, так как базируются на допущении о независимости развивающихся параллельных процессов, тогда пак в СЖОВР процессы реального времени взаимозависимы через общий рссурс - гремя центрального процессора ЭВМ.

Исследования по конфликтна.! ситуациям при планировании и диспетчировании п вычислительных системах не учитывают особенности временных ограничений в СЖОВР (наличие min итак директивных сроков для процессов РВ), что также не позволяет непосредственно воспользоваться результатами этих исследований. Таким образом, для М50С рассматриваемого класса является актуальной задача исследования и разработки специальных методов устранения конфликтных ситуаций, которые не могут быть устранены традиционными способами.

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

Методы исследования заключаются в моделировании вычислительного процесса в ®0С с использованием известной в теории операционных систем концепции процессов и ресурсов. Для построения и анализа моделей используется математический аппарат теории графов и теории расписаний.

Научная новизна диссертационной работы состоит в том, что исследованы факторы, приводящие к конфликтным ситуациям в многофункциональных операционных системах реального времени; впервые разработаны методы устранения КС, учитывающие жестки? временные ограничения в таких системах; предложены и реализованы оригинальные алгоритмы обнаружения и устранения КС для режима реального времени.

Практическая ценность и внедрение результатов работы.

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

Разработанные методы устранения КС использованы при проек- • тировании М50С на базе операционной системы ОС ЕС. Внедрение спроектированной операционной системы осуществлено в автоматизированной системе испытаний и управления (АСИУ) пуско наладоч- : ными работали для комплексов радиоэлектронной аппаратуры в Радиотехническом институте АН СССР, а также в аналогичной системе з Одесском политехническом институте. Внедрение подтверждено соответствующими актами. Использование разработанной ШОС позволило сократить время подготовки и исполнения испытательных программ в 1,5*2 раза.

Апробация. . •

Основные результаты работы докладывались на б научных конференциях, в том числе на У Международном совещании по пробле- • мам математического моделирования, программированию и математическим методам решения физических задач В г.Дубна в 1983 г. : и опубликованы в 6 научных статьях.

На защиту выносится

1. Анализ стратегий разделения ресурсов в операционных системах и устранения тупиковых конфликтных ситуаций.

2. Структурная схема образования виртуальных машин операционными системами,составляющими ®0С реального времени.

3. Метод устранения статических конфликтных ситуаций для прогессов реального времени на этапе планирования вычислительного процесса:

алгоритм составления бесконфликтного расписания для процессов ЕВ; ■'; ч ;

- алгоритм поиска тупиковых расписаний ддя процессов РВ.

4. Методы устранения динамических жяфиктных еитуаций в И50С реального времена: .

- алгоритм обнаружения тупиковых ситуаций в системе для процессов РВ;

- ускоренный алгоритм выхода из тупиковых ситуаций в системе . .

. 5. Реализация теоретических выводов в многофункциональной операционной системе - Диспетчерском программном обеспечении автоматизированной системы измерения и управления для комплексов радиоэлектронной аппаратуры, построенной на базе ОС ЕС ЭВМ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и двух приложений; содержит 185 страниц, в том числе 47 рисунков, 8 таблиц и 70 наименований библиографии. -

• СОДЕРКАНЙЕ РАБОТЫ

Задача устранения КС в ?<0ОС может быть представлена в виде 3-х подзадач:

- создание необходимых предпосылок для устранения КС при выборе структуры Ш>0С и общей организации вычислительного процесса;

-' устранение КС на стадии планирования процессов реального времени;

- устранение КС на стадии исполнения процессов.

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

Следствием децентрализации обработки данных является отказ от концепции набора данных для обмена информацией с ОУ в реальном времени, так как обработка наборов данных связана с длительными процедурами их открытия и закрытия и работой с буферами ввода-вывода.

Режим РВ предъявляет особые требования к алгоритмам распределения устройств, обращение к которым как к последовательно используемым ресурсам при монопольном режиме использования недопустимо- в СКОВР, так как моменты выполнения запросов на устройство - случайная величина, зависящая от ситуации в системе, в результате чего возможны нарушения режима РВ. Работа УВВ в режиме разделения (мультиплексирования) также невозможна ввиду

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

Для управления устройствами связи с ОУ должны быть разработаны специальные ускоренные методы доступа, так как эти устройства (НВУ) значительно отличаются от стандартных как по временным параметрам, так и по реакции на аварийные и сбойные ситуации.

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

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

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

Сосуществование в М$0С принципиально отличающихся друг, от друга реюшов вычислительного процесса (РВ, пакетного и др.) • дает основания рассматривать М50С на этапе логического проектирования как совокупность отдельных взаимодействующих ОС, каждая из которых обеспечивает один или несколько режимов вычислительного процесса. Причем на этом этапе несущественно, какова принятая технология проектирования ШОС (разработка в полном объеме, внесение изменений в управляющие алгоритмы некоторой серийной ОС или ее надстройка специализированными программными модулями).

Организация самостоятельного уровня планирования для каждого из режимов, которая создает предпосылки успешного устранения конфликтных ситуаций при одновременном удовлетворении нест-ких ограничений на время реакции системы, определяется принятой в МЮС схемой взаимодействия виртуальных машин, составляющих ее операционных систем, каядая из которгх образует собственную виртуальную машину для процессов одного или нескольких режимов.

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

Для выработки единого подхода к устранению КС в ШЮС проведен анализ общих принципов разделения ресурсов в операционных системах различных типов. Показано, что в ®0С для устранения КС необходимо использовать весь арсенал стратегий разделения ресурсов (статическое и динамическое приоритетное и бесприоритетное разделение в .пространстве и во времени), так как каждая из этих стратегий имеет преимущества в зависимости от режима процессов и стадии применения.

Наибольшую опасность в ШЮС представляют сложные КС, возникающие как следствие бесприоритетного разделения во времени монопольно используемых ресурсов между параллельными независи-

мыми процессами реального времени. Особые меры должны быть приняты к устранению разновидности сложных "КО - тупиковых КС. Из всех распространенньх стратегий устранения тупиковых КС в {©ОС исследуемого класса могут быть использованы "алгоритм банкира", предложенный Дейкстрой, а также автоматическое обнаружение с последующим восстановлением. Такие стратегии как глобальньй запрос ресурсов, стратегия Хавевдера, предварительный анализ запросов неприменимы в ЩОС, так как либо сводятся к жесткому статическому распределению ресурсов, либо сводят на нет преимущества ' многопользовательского режима в системе, либо жестко задают отношения" предшествования для отдельных квантов процессов РВ.

В зависимости от стадии устранения КС и связанных с этим методов, в диссертации предлагается все КС делить на 2 больших класса: статические КС, устраняемые на стадии планирования процессов РВ и динамические КС, устраняемые на стадии исполнения процессов.

На основе анализа свойств процессов и ресурсов в исследуемом классе ЩОС выявлены факторы,- влияющие на возникновение статических КС в определяющие методы их устранения:

- уровень загруженности системы процессами РВ;

- структура запросов на ресурсы в процессах РВ;

- требования к точности времени предоставления ресурсов процессам РВ; .

- изменения состава процессов и ресурсов в системе;

- полнота и.достоверность информации о потребностях каждого процесса в ресурсах;

- категория процессов (внутренний или внешний процесс).

Устранение статических КС на стадии планирования осуществляется при составлении бесконфликтного расписания для заданного интервала планирования, в качестве которого.обычно выступает цикл ОУ. Ставится задача составления бесконфликтного расписания, удовлетворяющего максимально возможное чисйо . независимых пользователей при соблоденш заданных дарективных . сроков выполнения процессов пользователей. Эта задача форьогаш-руется следующим образом; .составить расписание, максимизирующее функцию = X прк следащих значениях

ос. и ограничениях: ',1

'I ДЛЯ t¿j c-fX^Y-] Kiij^jtCX.jj.j]

О в противном случае,

где:

"XII - матрица min директивных сроков, II _ max -

11TII ~ матрица ожидаемое длительностей квантов процессов, Ш - матрица точек включения в расписании, N - число процесов-претендентов на включение в расписание,

Mi - число квантов ¿-го процесса, - число процессов в расписании.

где {у-} - заявленная последовательность квантов i -го

процесса,

i?'«-;) ~ последовательность квантов ¿ -го процесса в расписании или

{g'¿j} = 0 для процессов, не вошедших в расписание.

Задача составления расписания для процессов /?Т-типа, как показано в работе, может б.чть сведена к классической задаче линейного программирования. Рассмотрен наиболее распространенный случай, когда все ресурсы используются каждым процессом в пределах предоставленного ему кванта времени центрального процессора. В этом случае составленное расписание характеризуется числом процессов , включенных в расписание по условии непересечения всех квантов этих процессов. Требуется найти матрицу точек включения процессов, при которой w -*та% Очевидно, что V*ot-N, У/т,я = í.

Поставленная задача решается при соблюдении ограничений трех типов:

- ограничения предшествования: fy + T¿j i fy*; ограничения директивных сроков: X¿j £ ¿ fy;

^ztj+rijiKj ;;

- ограничения бесконфликтности расписания:

fu (()£■(

¿*mi для V

где функции f¿¿ отражают занятость процессора на интервале [0,TpacnJ совокупностью процессов I-* ¿ (если fu (t) =1, то в данный момент процессор занят одним из процессов, включенных в расписание).

Задача имеет достаточно большую размерность и не может быть решена в условиях жестких ограничений реального времени, так как необходимость ее решения будет возникать каждый раз при составлении нового расписания, то есть, в худшем случае, при планировании в каждом цикле ОУ. Поставленная задача отличается и от традиционно решаемых в теории расписаний задач по , исходным данным (заданы 2 вида директивных сроков для каадого кванта), по критериям для оценки расписания (требуется максимизировать число включенных в расписание процессов), по огра- . ничениям при решении задачи (недопустимо нарушение директивных сроков, требуется соблюдение ограничений предшествования дяя каждого из квантор. Поэтому не удается непосредственно воспользоваться для решения задачи известными результатами теории расписаний. '

Соотношение мевду величинами X и У определяет метод составления расписания.

I. Х-0. В этом случае расписание составляется путем упорядочения квантов процессов по возрастаний директивных сроков. Этот случай является предметом исследования в теории расписаний и для него справедливы разработанные в этой теории методы расписаний.

• 2. Х+Т=У. В этом случае исключаются любые перестановки при составлении расписания. Задача сводится к определению подмножества процессов, не включаемых в расписание по причине "пересечения" их квантов. Для решения этой задачи может"быть предложен простой эвристический алгоритм:

а) определяется подмножество процессов, кванты которых "перескаются";

б) из найденного подмножества последовательно исключаются

12

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

в) последовательное исключение процессов продолжается до тех пор, пока в подмножестве не останутся только процессы с "непересекающимися" квантами;

г) найденное подмножество объединяется с исходным подмножеством процессов с непересекающимися квантами.

3« X * У * Х+Т. Для исследования этого случая вводится понятие тупикового расписания - такого расписания,в котором хотя бы для одного из ресурсов системы потребности нескольких процессов "накладываются" друг на друга во времени. Исследование тупиковых расписаний можно свести к исследованию расписаний с ресурсами единичной емкости.

Предлагается следующий эвристический алгоритм решения этой задачи. Вводятся понятия тупикового расписания (расписания, содержащего хотя бы I КС) и характеристического графа расписания(двудольного графа, в котором присутствуют вершины 2-х типов; вершины - кванты процессов и верпшны - ресурсы; дуга от вершины-кванта к вершине-ресурсу означает распределение ресурса, от вершины-ресурса к вершине-кванту - освобождение ресурса). В характеристическом графе вершины-ресурсы связаны дугами более чем с одним процессом,вершина-ресурс входит в 2 или более циклов, вершины-кванты этих циклов принадлежат различным процессам; количество вершин в упомянутых циклах ? 3.

I. этап

• В характеристическом графе расписания б выделяются подграфы 6м' такие, что каждый из них содержит только одну вершину-ресурс.

2 этап

Для каждого подграфа составляется частичное расписание. Соответствующий подграф сокращается так, что из него ис- . ключаются все вер&ины-процессы, для которых не выполняются неравенства: , * У/ ■ или Х( £ Ум для и

где lit -min директивный срок последнего кванта К-го процесса;

Y* _ гиг?/ директивный срок первого кванта J -го процесса.

3 этап

Из частичных расписаний составляется общее расписание путем пошагового объединения полученных подграфов. Максимальное количество испытаний в тагом алгоритме где Hi - число вершин-процессов подграфа £><t} - Составленное по описанному алгоритму расписание подвержено возмущениям из-за недостоверной информации о потребностях процессов в ресурсах, ошибок реализации ti-, ошибок реализации Т-Поэтому расписание подлежит коррекции на каждый очередной цикл.

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

- простые КС, которые приводят к устойчивым нарушениям составленного расписания для процессов КТ-т;:па и могут быть устранены соответствующей коррекцией при планировании очередного цикла системы;

- простые и сложные КС, которые обусловлены случайными факторами (например, различными сбоями и отказами аппаратуры системы) и которые принципиально не могут быть устранены алгоритмическими методами;

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

Конфликтные ситуации первой категории могут быть устранены при коррекции*расписания, то есть методы их устранения совпадают с методами устранения статических КС, КС второй категории должны анализироваться при комплексном рассмотрении вопросов надежности системы и в настоящей работе не исследу-

ются. Задача устранения конфликтных ситуаций третьей категории (тупиковых КС) традиционно включает задачи обнаружения, предотвращения, обхода и выхода из 1X1, Задача обнаружения ТС должна решаться при любой из стратегий. Поэтому в настоящей работе она специально не выделяется, а присутствует как составная часть задач предотвращения и выхода из ТС. Для анализа и выработки адекватных решений вводятся понятия ЙТ-процесса (процесса, выполняющегося в РВ и жестко синхронизированного с циклом системы, квантн которого входят в расписание цикла) и NRT -процесса (процесса, не связанного жестко с расписанием, но связанного информационно с R Т-процессами). Рассмотрены стратегии обнаружения, предотвращения, обхода тупиковых ситуаций с учетом возможности взаимного перехода процессов RT-типа "и МЯТ-типа.

При решении задачи предотвращения ТС по методу "алгоритма банкира" возможны два подхода: I) учет "алгоритма банкира" при составлении расписания процессов ЯТ-тийа на стадии планирования и 2) учет уже составленного расписания в "алгоритме банкира" на стадии исполнения процессов. Первый подход приводит к дополнительному значительному усложнению алгоритма составления расписания и его применение на практике нецелесообразно. Поэтому в диссертации рассматривается только второй подход. Основной составной часть» "алгоритма банкира", моделируицего наихудший случай развития процесса,является задача обнаружения. Поэтому основное внимание уделяется решению этой задачи. Анализ возможных переходов процессов позволил сделать ряд выводов и выявить свойства графа ресурсов для процессов RT-типа и NRT -типа: V. I) циклы в графе ресурсов не могут пересекаться;

2) в одном тупиковом множестве не может быть более одного процесса ЯТ-типа;

; 3) вершины-процессы Я Т-типа и типа в одном цикле

■тупикового множества должны чередоваться.

Из анализа свойств графа ресурсов вытекает алгоритм обна- . руления тупика для графа единичных ресурсов:

1. Определяются связныо части графа.

2. Дня яазвдой связной части:

а) проверяется каждая вершина-процесс КТ-типа на вхождение в цикл;

б) определяется для данного связного подграфа его цикл (в каждом подграфе может быть не более одного цикла);

в) испытывается каждая вершина в идкке на "сток";

г) 'Определяется для каждой вершины - "стока" цепочкар-»К в результате чего окончательно устанавливается множество вершин-процессов и вершш-ресурсов, составляющих цикл.

Для выхода из ТС предлагается быстрый оригинальный алгоритм выхода путем частичного приостанова процессов (перехвата ресурсов). Смысл этого алгоритма,, условно названного алгоритмом последовательного перебора, заключается в том, ггго . граф ресурсов представляется в виде 5 векторов:

ВТ - вектора цен процессов (с учетом всех факторов), , В2 - вектора связи процессов с ресурсами (запросы), ВЗ -- вектора связи ресурсов с процессами (распределения), В4 - вектора перехвата ресурсов, В5 - вектора регистрации циклов в графе ресурсов. Вектор В5 используется как маска для определения подмножества процессов', входящих в цикл; из этих процессов выбирается процесс с наименьшей ценой. Результат перехвата отображается в векторе В4. Собственно выход осуществляется последовательным испытанием'результатов удалений разных комплексов процессов методом полной релукции графа ресурсов. Составление комплектов осуществляется на стадии планирования, чем достигается естественная экономия времени'непосредственно при выходе из ТС. Время выхода по предложенному алгоритму ~2"п-т , где п - число процессов, го - число ресурсов в системе.

Особенности функционирования рассматриваемого класса систем (циклический характер ОУ) позволяют для процессов, отвергнутых при разрешении конфликтных ситуаций, производить отсроченный запуск в системе..Такой отсроченный старт особенно эффективен при небольших уровнях загрузки системы и относительно небольшом (по отношению к длительности цикла) времени жизни процессов. Для оценки числа шагов (циклов), на которые могут задерживаться процессы при перехват? ресурсов, предлагается воспользоваться известной моделью" II -системы". Пусть т число шагов, на которое необходимо возвратить процесс в резуяь-

тате выхода из ТС. Это число определяется логиков развития самого процесса, а не выбранной стратегией выхода из ТС. Один шаг соответствует изменению состояния одного ресурса. Тогда максимальное число шагов Kml? можно оценить по формуле: х'т'аг =• n(mi-J) -1

Полученные на имитационной модели зависимости %сд -fin) и Tyct^f(m) и соотношение: (Ти_ /и - ±) ■ Кmat <Туа-6> где К majt - максимальное число шагов, необходимых для выхода из ТС в наихудшем случае при заданных .пит

L - среднее число квантов рассматриваемого процесса в цикле,

£" - средняя длительность одного кванта, ТВсА - общее время выхода в условных единицах , '6 - цена условной единицы, позволяют оценить применимость выбранной стратегии выхода из ТС.

Устранение КС разработанными методами показано на примере автоматизированной системы испытаний комплексов радиоэлектронной аппаратуры (АСИУ), построенной на базе ЭВМ ЕС-1033 в Радиотехническом институте АН СССР. ЩОС этог системы включает серийную операционную систему ОС ЕС и специализированное Диспетчерское программное обеспечение (ДПО), которое организует резким реального времени с заданными временными ограничениями при сохранении возможностей СС ЕС. Реализованы 3 основных ( ON-LINE, OFF-line t фоновый) режима и I вспомогатель-

ный (отладочный). Управление режимами ON-иШЕ (ЯТ-процессы) и OFF-LINE ( NRТ -процессы) осуществляется средствами ДПО, фоновым - средствами ОС ЕС.

Задача устранения КС в МФОС системы АСИУ решается на этапах проектирования, генерации и загрузки ДПО, подготовки и ввода в эксплуатацию функциональных рабочих программ пользователей, планирования и развития процессов.

При проектировании ДПО реализована предложенная в работе асимметричная схейа образования виртуальных машин, создающая предпосылки для устранения на последующих этапах КС. При этом используется абсолютно приоритетное статическое разделение части ресурсов между операционной системой ОС ЕЮ и ДПО на эта-

• Г7 - .

пах генерации и ьагрузки. Основной ресурс совместного пользования - время центрального процессора - разделяется между ОС ЕС и ДНО на приоритетной основе с помощью специальной програм- -мы - Гипервизора, активизируемого по прерываниям ввода-вывода и внешним прерываниям ¿VC -программой, включаемой в состав ОС ЕС на этапе генерации.

Все программы ОС ЕС имеют низший по отношению к ДПО при- . * -оритет. Для устранения КС, возникающих гезду процессами фонового режима, средств, кроме имеющихся в составе ОС ЕС, в составе ®0С системы АСИУ не предусмотрено. Все КС между процессами режимов ON-une и OFF-UNE устраняются специальными программными модулями, входящими в состав ДПО.

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

Устранение статических КС ка этапе.планирования осуществляется по предложенному эвристическому алгоритму для ресурса времени центрального процессора и составляющих с ним неделимую.пару ресурсов ОУ. При этом на каздый цикл составляется предварительный и исполнительный план. Дяя составления бесконфликтного -плана определяется базовый процесс, обладающий mir) подвижностью и являклцийся деррм претевдэнтом на исключение из плана ... цикла при возникновении конфликта. Исследования на модели показали, что полученное в результате расписание (план цикла) отли- , чается от оптимального не более чем на ICfé по критерию плох числа включаемых в расписание процессов.

Устранение динамических КС в М£0С системы АСИУ, возника- . 'гацих между процессами в результате изменения их режима, самостоятельного порождения процессами других процессов, претендующих на занятые ресурсы, а также из-за изменения состава процессов и ресурсов в системе, достигается коррекцией расписания по алгоритму, аналогичному алгоритму составления расписания.

Тупиковые КС в №>0С системы АСИУ могу: возникать в результате перехода процессов'га режима ON-LME в режим OFF-UUF.. Алгоритм обнаружения включается каждый раз при выдаче запроса * процесса OFF-utëна ресурс, и в случае обнаружения опасного

■18

состояния запрос но удовлетворяется. В случае попадания в ТС (при вь^аче запроса от процесса ОИ-ЦНЕ) включается быстрый алгоритм выхода из ТС с Л7/Л ценой выхода. Цена выхода для равно-приоритетных процессов назначается пропорционально времени пребывания их в системе. При выходе из ТС используется метод перехвата ресурсов, позволяющий, в условиях цикличности процессов, задержать процесс на один цикл, не удаляя его из системы, если процесс позволяет такую задержку.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Обобщен и проанализирован опыт разработок системного программного обеспечения АСУ сложным экспериментальным оборудованием. Сформулированы общие требования к организации вычислительного процесса в многофункциональной операционной системе ШЮС) реального времени с жесткими ограничениями на время реакции.

2. Предложена и обоснована классификация конфликтных ситуаций (КС) в ОС реального времени. Проведен анализ стратегий устранения КС и определена применимость их для рассматриваемого класса систем.

3. Предложена и обоснована структура !©0С, создающая предпосылки для устранения КС при заданных временных ограничениях.

4. Поставлена и решена задача устранения статических КС

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

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

6. Результаты проведенных исследований были использованы, при разработке Диспетчерского программного обеспечения (ДПО), построенного на базе операционной системы ОС ЕС для Автоматизированной системы измерения и управления (АСИУ) пуско-наладочны-ми работами для комплекса радиоэлектронной аппаратуры в РШ

АН СССР и в аналогичной системе з Одесском политехническом ин-

; •-:.?•. ' .; ту ' ' : •

ституте. Система АСИУ успешно эксплуатируется в настоящее время.

Основные результаты диссертационной работы отражены в следующих публикациях.

1. Демидов М.А., Макаров В.В., Титов A.C. Программное обеспечение нестандартной аппаратуры связи с объектом в автоматизированной системе измерения и управления на базе ЕС ЭВМ. // Цифровые и аналоговые вычислительные машины 8 ядерной физике и технике. Выпуск 8. - М.: Атомиздат, 1978, с.18-22.

2. Демидов И.А., Макаров В.В., Лукинов Н.И. и др. Опыт организации пуско-наладоодых работ систем реального времени с использованием диспетчерского программного обеспечения. // Труды Радиотехнического института АН СССР. Обработка информации. - М., 1980, с.62-70.

3. Демидов U.A., Макаров В.В., Дворецкий В.А., Смелова Г.И. Принципы построения диспетчерского, программного обеспечения для организации работ с нестандартной аппаратурой в реальном времени. Там же, с.56-62. i

4. Демидов М.А., Забродин Л.Д., Макаров В.В. и др. Методология проектирования операционных систем реального времени для систем автоматизации сложных физических объектов. // Автоматизация физических исследований /Под ред.Колобашкина В.М. -

М.: Энергоатомиздат, 1984, с.177-182.

5. Демидов М.А., Забродин Л.Д., Макаров В.В. Многофункциональ- . ная операционная система на базе ОС ЕС для использования в • АСУ сложны:® физическими объектами. // Автоматизация научных '. исследований в экспериментальной физике. /Под ред.Чигиря С.Д. - М.: Энергоатомиздат, 1987, с.145-148.

6. Демидов М.А., Макаров B.B.4 Соловьев Т.Н. Расширение операционных систем ЭВМ общего назначения для использования в системах управления экспериментальным оборудованием. // Математическое моделирование. Программирование и математические, методы решения физических задач. - Труды У Международного совещания по проблемам математического моделирования, програм-

■ мированию и математическим Методам решения физических задач. -Дубна, 1985, с.372-375.

j