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

ТОПС'СИЙ ПОЛГГЕХЬИЧЕСКИЛ У1[НБЕРСНТЕТ

!!а 1,рааау рукописи

СМИРНОВ АЛЕКСАНДР ЮРЬЕРКЧ

СПЕРАЦИЭННАЯ СИСТЕМ ДЛЯ ЖГОПРОЦЕССОРЖ ШЧИСЛИГЕ.ЧЬШХ СИСТЕМ С РАЗДЕЛЯЕМОЙ ПАШШО

05.13.II - математическое и программное обеспечение

вычислительных майки, комплексов, систем и сетеР

Чк

АВТОРЕФЕРАТ

диссерта!ии на соисклш'в учечоР ;тгч:?н;; канд'.'цатя технически--: няук

Томск-!1»':

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

Научны" руководитель: кандидат технических наук, доцент Марков Н.Г.

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

кандидат технических наук Шеренков К.П.

Ведущая организация: Институт систем информатики СО РАН (г.Новосибирск)

. о*

Защита диссертации состоится " <*< / "___** 199? г. в

15 часов на заседании специализированного Совета Д 063.t0.03 по защите диссертаций на соискание ученой степени доктора технических наук при Томском политехническом университете по адресу: 034004, г.Томск, ул.Советская,84, Кибернетический центр при ТПУ.

*

С диссертацией можно ознакомиться в научно-технической библиотеке Томского политехнического университета (634004, г.Томок, ул.Белинского,54).

Автореферат разослан 23 мая 1992 г.

Учены? секретарь ' ' ■ , ' '

епеииа чизированного Совета •->/■ ' /

кеипипат технических наук, доцент ЛИ.Л.Чудинов

/

СЕМЯ ХАРАКТЕМСТШ РАБОТЫ

Актуальность темы. В настоящее время в большинстве облаете? применение вычислительной техники (ВТ) от последней требуются как повышенная производительность, тэк я нздетшэсть. В этой связи зажнеГдеР тенденшеР развития современно? ВТ является разработка и расширенное внедрение многопроцессорных вычислительных систем 'ЛЪС), обеспечивающих паче при использовании стандартных электронных ксмполент достижение требуемо? производительности и отказоустойчивости. Новые -технологии п микроэлектронике позволяют уге геГчас иметь бкстропеРгтвувтие, надежные и дешевые относительно других компонент ВТ микропроцессоры, что значительно обостряет интерес к создании и применению ЧВС на их основе. Один из перспективных классов МВС, для которых могут быть достигнуть; к требуемая производительность, и отказоустройчивость, составляют МВС, процессоры которых имеют как локальную оперативную память.(ОП), так и доступ к обгену полю ОП.'

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

Цель диссертационно" работы состоит р создании системного математического и программного обеспечения МВС с локгльноГ и сйще{; СП. Задачи, репаемые для ее достижения, сводятся к созданию ОС для целевое МБС выделенного класса и к разработке средств поддержки программирования для МВС. При тем создаваемая ОС должна обладать такими возмолностями " характеристиками, которые позволяли бы использовать ее для различи. . при.генеяя", з т.ч. в бортовьх МВС с ограниченным набором ресурсов, но пови-.енпыми тпе-. боеангями к отказоустойчивости и реаткпвнгсти <~С.

Предмет исследования составляют системное ГЮ, принципу и особенности его структурно и АучктюнзльноР организации, способ:; и средства описания и исследования параллельного ПО.

Методы исследован и п. В работе игпольгои'Ш','

кктоды теории ОС, теории программирования параллельных процессов, элементы обшей алгебры, теории градхв и комбинаторики.

Научная новизна работы заключается в следующем:

- для выбранного класса МВС с учетом его особенностей предложен и обоснован способ структурно-функшганалъноР организации ОС, обеспечиваюгци? ее быстрое с-озиание и совместимость с базовой одно-процессорно? ОС;

- предложены способы и средства организации управления разделяемыми ресурсами, удаленного выполнения ксманд и распределенного выполнения командных файлов, перемещения локальных ядер ОС МВС по 0Г1 без перезагрузки;

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

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

- предложены метод и средства отладки ОС МВС, основанные на возможности представления распределения ОП МЕС и размещения ОС МВС в ОП инструментально? однопроцессорной ЭВМ; эти средства обеспечивают существенное ускорение создания системы в целом;

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

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

Практическая ценность ра-б.оты состоит в следующем:

1. Создана'версия ОС ЫВС, совместная с ОС РЛЮС, для работы на МВС, процессоры которых имеют систему команд микропроцессора типа KIS0I, локальные СП и доступ к разделяемой об^ей ОП. Резидентные части ОС ИЗС реентерабельны и пригодны для размещения в ПЗУ. Локальные ядра ОС МВС обладают возможностью перемещения по ОП без перезагрузки. Возможна генерация различных вариантов ОС МВС применительно к конкретным особенностям аппаратной части МВС и специфике ее применения, а так же генерация ОС РАФОС с дополнительными функциями, разработанными для ОС МВС (перемещаемость, резервирование ' ВУ, восстановление вычислений и т.п.). Созданы программные средства для отладки нгуальной версии ОС МВС на инструментальной однопроцессорной ЭВМ.

2. Разработана инструментальная система моделирования, позволяющая моделировать и исследовать ПО, разрабатываемое для МВС, наполняя при этом модель реальным программным содержимым, задаваемом на одном из традиционных языков программирования. Созданная система позволяет решать' задачи,'связанные не только с разработкой ПО, но и моделировать различные системы, содержащие параллельные процессы. Инструментальная система реализована на ЭВМ типа СМ-4 и ПЭВМ IBM PC/AT.

Реализация результатов работы. Основные результаты диссертации получены в ТПУ при выполнении хоздоговорных НИР и ОКР по темам: "Разработка алгоритмического и программного обеспечения систем контроля и диагностики сейсморегистри-рую-дих комплексов"; "Разработка системных программных средств многопроцессорной вычислительной системы". Созданная автором версия ОС МВС написана на языке Макроассемблер, при этом совокупный объем написании программ составил около 12 тысяч команд. При участии автора на ЭВМ СМ-4 и на ПЭВМ IBM PC/AT была реализована инструментальная система моделирования параллельных процессов. Созданные алгоритмические и программные средства внедрены на МВС и инструментальных однопроцессорных ЭВМ Российского НИИ Космического приборостроения (г.Москва). Отдельные результаты работы внедрены в СКГБ сейсморэз-ведочной электронной техники (г,Краснодар) и в Институте физико-технических проблем РАН (г.Москва).

Апробация работы. Основные результаты работы докладывались и обсуждались на Всесоюзной научно-технической кочТе-ренпии "Актуальные проблемы информатики, управления и вычислительной техники" 'г.Москва, I9S7 г.), I Всесоюзной конференции "!!?-->гк

анализа надежности ПО на основе моделей нечеткой логики и качественных списания" (г.Киев, 1967 г.), на Ж и ХН Есесолзиьк научных студенческих конференциях по проблемам авиации и космонавтики (г.МоекЕа, 19ё7 и 19с8 г.г.), на ХХЛ Всесоюзной наушоП студенческой конференции "Студент и НТП" (г.Новосибирск, 19Ь8 г.), на Всесоюзной конференции "Моделирование систем информатики" (г.Новосибирск, 1988 г.), на Всесоюзной научно-технической конференции "Микропроцессорные комплексы для управления технологическими процессами" , (г.ГрозныР, 19с39 г.), на П Всесоюзном совещании по автоматизированному проектированию программного обеспечения систгч управления цви-г.удикися объектами (Рыбачье, 1989 г.), на Региональных совещаниях по псг.ееим вычислительным комплексам (г.Новосибирск, 1988 и 1989 гл.), на Международной конференции "Высокопроизводительные вычислительные системы в управлении и научных исследованиях" (г.Алма-Ата, 1991 г.).

Публикации; По результатам исслецотим!-! опубликовано II работ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав и заключения, изложенных за 142 страницах текста, включает 15 страниц иллюстраций, приложение нв 7 страницах и список литературы из 112 наименований. ''б!чнп объем диссертации составляет 178 страниц.

ОСНОВШЕ ПОЛОЖЕНИЯ, ЕШОСИШЕ НА ЗАЩИТУ

I. Предлагаемые способ организации ОС, алгоритмические и программные реиения позволяют создать ОС МВС на основе базовой оцнопро-цсссорноР ОС РА50С, При зтом организация вычислительного гропесса 1: поддержка отказоустойчивых вычисления может выполняться ОС МВС как при ее использовании в качестве инструментально? ОС, так и в "словнях реального времени,и ограниченности ресурсов МВС.

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

3, Средства подпер'.! и лрогг"'-!Мировенич МВС позволяют модели-рсветь и исследовать парплтельное ПО, что обеспечивает ускорение °го разработки при одновременном повышении качества.

; ОСНОВНОЕ СОДЕРЖАНИЕ РАБСИ

Во введении обосновывается актуальность разработки системного программного обеспечения МВС.

В главе I анализируются предпосылки создания, современное состояние и тенденции развития МВС. Делается быр^п о то«', что все более доступным становится создание недорогих, но достаточно производительных и/или отказоустойчив;:.: МЗС на основе мркеимэль-ного использования как стандартных электронгах компонент, так и П0° однопроцессорных ЭВМ. Приводится классификация МВС по типу разделения ОП и ВУ мекцу процессорам. При ртом п качестве перспективного класса МВС обосновывается выбор ЮС, имениях как локальные, ток и общие ОП и ВУ. Показано, что в качестве целевой МВС из выбрагчого класса целесообразно выделить МВС с системой команд микропроцессора типа К1801.

Анализируются .основные вопросы организации вычислительного про -цесса в МВС, параллельного программирования и организации отказоустойчивы:: вычислений.

Исходя из приводимого анализа формулируются цель и основные задачи работы, включающие разработку способа организации и создание ОС для ЫВС выбранного класса, разработку средств подперт-::-:! про-грамттарования для МВС.

Глава 2 посвясеьа разработке способа структурно-Функциональной организации ОС для выбранного класса МВС с учетом его особенностей. ОС МВС будет состоять из размещенных в локальных СП (ЖЛГ копий базовой однопроцессорной ОС, расширенных мультппроцесгорнкма функциями. В общей ОП (ООП) эти копии буду^ пересекаться, т.к. там б; дут размещены используемые гаи общесистемные структуры пгнныу, необходимые для выполнения указанных фунтгий.

Показано, что к основным функциям ОС МВС откосятся управление разделяе№ми ресурсами, взаимоисключение и синхронизация процессор, борьба с тупиками, распределение работ по процессорам, педдертка отказоустойчивых вычислений. Некоторые из них изначально присутствуют в базовой ОС и при создании на ее основе ОС МВС должны быть модифицированы с учетом реального параллелизма и конкуренции пг"1-цессов, выполняемых разными процессорами МВС. Другие до.тчны б!'ть разработаны заново. Каждая функция рассматривается отдельно и гл нее формулируется подзадача либо модификации, лиЗо разработки. При водятся и анр чизируются некоторые существующие решения. • ччг

прьйлодлмого. сш.соба организации ОС МВС обеспечивает ее совместимость с шбираеыоГ. базовой ОС и наследований ею основных характеристик и параметров последней.

Обосновывается выбор ОС РАФОС в качестве базовой компоненты цлл создании иС. целевой МВС.

В I' л а ь е 3 предлагаются конкретные алгоритмические и г.ро-грамшне решения, реализация которых позволила создать СС МВС на основе базовой ОС PAiOC. Предварительно анализируются принцип! функционирования и конкуренции процессов в ОС PAäOC, выделяются три основных типа ресурсов: системные структуры данных, БУ и каталоги. Каждое лекальное ядро (ЛЯ) ОС МВС'управляет конкуренцией процессов, растолченных в той же ЛОП, обычными средствами базовой ОС. Этих средств недостаточно для управления конкуренцией процессов, расположенных б пазпых ЛОП, т.е. б случае реального параллелизма и конкуренции. Поэтому дополнительно были разработаны средства СС МЕС, позволяющие объявлять, захватывать и освобождать так называемые абстрактные разделяемые ресурсы. Для последних б их статусе может быть задана привязка к конкретным физически.« ресурсам, которые, б . таким случае, считаются объявленными в качестве разделяемых ресурсов ЙВС. Torna в ЛЛ после захвата ресурса обычными средсгьй^и базовой ОС проверяется: не связан лк данник рес^зс с спнкм из обьяь^ен-hl'x абстрактных ресурсов, т.е. не является ли он рг„>пеляемш ресурсом ИБС. Гогив, ест такая связь есть, то соотоетгг&уигиР абстрактный ресурс aavsamtcieTCH указанными средствами СС 1'ЕС, иначе впс происходит как обычно, т.е. как в базовой СС fAtX. Т.о. кошс>рс.п-цил за разделяемые {иэичегкяе ресурсы МЕС сводится к конкуренции за соочЕе;ству.сл:е им абстрактнее ресурс.:, а фактически за дескрипторы

последние, pnsi»3öH:ii;e б С< И. 'Гота б ............ любому осп ei мог.но

; .ставить в соответствие абстрактный j.«'cypt и упраеюль к(игт. •-'»«•«-' е.'' за ото? сбьек1, использул сгег.ства захвата и освсСс bcrcicyemei'o абстрактного i есурса. Пргчем, если с:0ь*.гт су".ес:руе:, то мм просто jiv.-vi ; шйгое средстве азан:.:: chhvj.: гмпации процесса2 с n^'.'C '.L : .4/. p>.ui"' иол. т. i;.--: сами, т.е !ичаскн над их дескриптор:.:!-;. ■■■ 'м-средств ОС »1-е гран.ч::ОТ доступом к тики." супсам М'г.С уч„ ЬУ, г?.га.;ггч и ;!ы н;;ь

гри доступе у. селе?№тем<: :• пмШ'-и к Г;'!, ' >. -.v:~.xw ,->6-пт,4:ктн!" рек;,р:'-.:г-, »••.•го.лзустсь

чен ре

с."от-

г. не я и

V Р-

и

и»

'р;п.; и тре

'бующий при отсутствии конкуренции всего 7 обращений к ООП. Для МНС, имеющих аппаратную поддержку операций типа "пр.^верить-и-устано^ить". этот алгоритм при генерации ОС МВС может быть легко заменен использованием указанной аппаратной поддержки.

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

Предлагается средства, позволяющие .и;бую строку, вводимую каким-либо образом в клавишный монитор ЛЯ, различными способами перР давать для вывода на экран и интерпретации в качестве командной строки на один или несколько задаваемых процессоров. Командные Файл перед выполнением просматривается системой и его строки, заданные для выполнения на других процессорах, извлекаются и пересылается на эти процессоры. Т.о. обеспечивается удаленное выполнение команд и распределенное выполнение командных Файлов, что позволяет легко управлять распределением работ по процессорам.

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

где Д/ - количество подмножеств процессов, просматриваемых на предмет снятия (число повторений основного цикла алгоритма); КС -количество простых циклов, выявленных в структуре тупика при его обнаружении; п. - общее количество процессов во всех КС циклах; 4 Sj - количество процессов, образующих /-й цикл. Приводится пример применения разработанного алгоритма.

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

предоставляются ерецстьа образования и сравнения контрольной инФор-маши) (точек контроля!, и г,ля восстановления вычислений - средства установки точек восстановления и отката к ним. В качестве примера применения указанных средств предлагается один из возможных способов организации ОУй в двухпроцессорной системе, предполагающий дублированные вычисления с откатом при рассогласовании результатов и сравнен;:-; как новых, так и ранее полученных точек контроля.

Предлагается оригинальный способ резервирования ВУ, позеоляю-Ч1ий назначать кок ВУ цзликом, так и их -отдельные участки нескольким другим, в некоторых случаях дане разнотипным ВУ илч их участкам для резервирования на уровне операций веода-вывода. При этом некоторые назн'а'^еше ВУ или их участки могут быть помечены как буферные. Любая запись нч ВУ-оригинэл или его участок сразу дублируется на со-отьетствующ'-и резервных. Чтение яе может выполняться не с ВУ-ориги-нала, а с одного из ре- тррных ВУ, помеченных как буферные. При сшибке чтение повторяется с остальных буферных ВУ либо до правильного пополнения, либо до выполнения на самом ЕУ-оригинали, если ни на одном буферном ВУ операция не прошла успешно. Т.о., гели медленному ВУ 1,ли его участку назначить в качестве буферного резервного более быстрое ВУ, то повысится не только надежность работы с ВУ и данными, но,и скорость доступа по чтению.

Рассматривается така^ оригинальная Функция ОС МВС как возможность быстрого перемещения ЛЯ по ОП без перезагрузки. Приводится алгоритм такого перемещения.

Практически значимой особенностью ОС МВС является реентерабельное!! ее ОЗУ-резидентных компонент и возможность 1« размещения в ПЗУ

-'врабатываются вопросы модификации системы генерации базовой ОС. !!"-•■ченнчя система генерации позволяем легко получать различив •"•1:"«1(тм ОС для МВС с учетом конкретных особенностей аппаратной ччпц: и счешф'ки применения: от инструментальных систем с полным •-"!'''унтий до небольт-тх бортовых систем с ог раниченным наборе/; V •."•л,'г, предназначенных дли размещения в ПЗУ. Модифицированная системе '".".ррпнии позволяет так же получать однопроцессорные вари-""ть- ОС РАФОС с некоторыми включенными в них Функциями, раз-

Р»Зо|»№1">т при создании ПС МВС 'резервирование ВУ,-перемещаемость, ■с"стчн'!нлени^ вычислений " т.п.).

Пручодитср общая структура СС МВС с указанном как коогеТигофо-•«•!•>• к'1нпон»т' ОС РА-ЮС-, так и новн> подсистем.

Для от.-®п"и ОС 1,!ВС предлагается оригинальны" метод и рсчлизую-

дне его доструненхвлыке средства, аклйчавше ь ОС РА*СС, сснонэн-ше на возможности представлять распределение 011 Ж1 »fft онного класс«, в СП инструментально? однопроцессорной ЭВ'.', vwwoe* аппаратуру диспетчера памяти. Torna псзгабатгвае-.яй вэричнт ОС L5C будет размещаться в Со! однопроцессорной ЕМ т-лече, как в СП SCI, что,з принципе, позволяет для отладки мюгопр'ч.'ессор'й'х 'Т.ункчи' ovoro варианта создать среду, близкую к среде реально? иБС. Это сбве<-ечквЕ-ет разработку начально,'' в°рсии 00 ¡VBC гр*»!:ти'»ескк до по'¡учения реального образца аппаратуру 1*ВО, "т'' 1 ?**ср*"?г создание скстлкз-: б целом.

В главе 4 Фогмулируетсл и 9нялиэкр>ет?ч пвухурсгпевь:" подход к созданию ПО для IffiC, при кетогом структур улраагэнкк ПО описывается на специальном языке отдельно от описашп внутренних , деталей вычислений, эидр.»аеиь>х на одном из традиционно яз'-'кср программирования. Выделяются две стадии реализации отого подхода. На первой из них сперва разрабатывается ФормэлътГ: аппарат описания и исследования программного параллелизма, а ттем на его основе создаются язык и инструментальная систрмэ моделирования параллельных программных процессов. По ходу моделирования структура ПО уточняется и наполняется "непараллельным" программным содержимым. Основным результатом моделирования и анализа ПО будет получение диаграммы выполнения ПО, уковлетроряше!! всем заданным при составлении модели и уточненным при ее исследовании ресурсным, синхронизационным и другим особег-'остям разрабатываемого ПО. На второр стадии реализации подходя для конкретное. КВС следует разработать исполняю:!,ую систему, которая будет обеспечивать выполнение образца ПО, наполненного исполняемыми программными компонентами з соответствии с его диаграммой, полученной при моделировании. При этом детали вычислений могут уточняться, но диаграмма выполнения считается отлаженной при моделировании.

Рассматриваются попреем реализации первоГ из укаэетпуч стпеий. Сначала анализируются судествугдие Нормальные модели параллельных вычислений. Среди них выделяется наиболее популярны!' на сегодня аппарат сети Петри (CHI. Из енелиза делается вывод о том, что няиос-лее характерную прикладную направленность на спяшгЬтппто и готли-роранне параллельного и распределенного ПО им«ет тякоо расширение СП как ПРОТ-сети (СП, транслируемые в процессы). Огнзко, ПРОТ-гети как и классические Щ но допускают наличия нескольких активисте« в ед-нипу времени. С учетом зтого предлагается, новы?» ппмря? моделирования, со-.-рснс котпр-му структура г"огракигоР скстемч птеита-«-

ляегся в вип5 ориентированного графа, Наличие Фкаки как программно-' го счетчика процесса в го? или иной вершине определяет текущую стадию раэвгтин процесса. Прогш-гление Финки по графу определяется сра--батынанием дуг, гредставлктаих фрагменты процесса. Каждой цуге сопоставлены логические условия ее срабатывания. Эти условия определяются наличием фиакл во входной вершине и значением придаваемых дугам атрибутов. Атрибуты. можно рассматривать как разделяемые ресурсы различных типов. Выделяются дьа основных типа ресурсов. Ресурсы Е-типй используются со взаимоисключением, а С-типа - без та-гопого. При переходе фижки по цуге значения атрибутов могут изменяться. Дугам могут быть приданы длительности срабатывания переходов. В модели в явном виде могут задаваться три отношения: альтернатива - взаимоисключение для переходов по цугам, которым приданы одни и те же ресурсы Е-тила; параллелизм - одновременное срабатывание переходов по заданным дугам; предшествование - срабатывание переходов по одним дугам всякий раз после срабатывания переходов по другим. Т.о. в целом Формальная модель параллельного ПО есть кортеж вида

G - < r,f:fí,rU.P,I,B,^>

где V - ыьояество событий (пераин графа); X) - множество действий (дуг графа); - отношение, сопоставляющее каждому элементу d.i£ Ю рлеканта из V ; Т - множество времен, в течении ко-

торых выполняется действия из ¿Oí - отношение, задающее

время z~; е 7" действия d¡ е. X) (время перехода Фишки по духе); R - Е ÍJ С - множество ресурсов, состоящее из двух непересекающихся подмножеств ресурсов Е- и С-типов; - отображение множества ду! на множество ресурсов и целых чисел, сопоставляющее каждой дуге векторы потребления 'восстановления) ресурсов; S ~ отнесение одновременности; Р - отнсаение предаествования; J -отношение, задающее критические интервалы по использованию ресурсен Е-типа; В - множества начальных времег порождения фишек в вер-кинах графа; - функция, сопоставляющая времена из В заданным лер&инам из 3 .

Даются определения 'и правила Функционирования этой модели. Сор).г/л"пустея одно из условий ее корректности, состоящее в отсутствии тупиков определенного типа. Этот тип тупиков связан с недо-г ■:twv.v ?^спольооьанием в модели отношений предшествования и одно-nf."r-V!V'jCTX. Призер такого использования этих отношений приведен пп фрчгкент? модели, изображенного на рисунке.

/ /

О

О - —

л.

N

\

О 01

и

4

О

Зрйсь !.шои!ет:-. прелпрецдгсз аосаиил обозначены опнонаправленкы-ии пугаегирниаш стре тг.н;, & о г:/ ¡зния одновременгости - двунаправ- . леышми. Из г-то.-с простого «¡.-.¡нсг-а ышно, что переход по любой из четырех цуг нга:с! л а и* будет выполнен, т.н. в соответствии с наложенными уелоы'.'Ш',! синхронизации он должен был бы выполняться как раньше, так н псзее самого себя и каждого из остальных, что фигпчзс-ки невозможно. Формулируется необходимое и достаточное условие существования тупиков такого типа. Предлагается алгоритм га обнаружения в статике, т.е. по описанию подели без ее прогона. При построении алгоритма используется известная.чз обшей алгебры теорема о том, что любому отношения эквивалентности, заданному на каком-либо множестве, взаимно-однозначно соответствует разбиение этого множества. Поэтому и отношение одновременности в силу своей симметричности, рефлексивности и транзитивности есть отнесение оквивалентностч. определяющее разбиение множества дуг на классы эквивалентности ,

Бг «.... 5т . Алгоритм сводится к построения на базе отношений предиествоЕ ¡ни] Р и одновременности 5 » заданных не множестве дуг £0 = С ,..., с10 } > нового отнопешн предшествования Р5 , но ухе на множеств« ( $г ,..., } классов экяотчлептнос-ти. Правило построения -имеет вид

■ ял." <„/•£« , 6С.1И « А;е ,5„, 4

Заметим, что, если найдутся и , для которых имеем £^, (¿; £ 5К и сУ; ё о«- > то это рте свидетельствует о грубой ошибке р. использовании отношений р и $ , т.к. переходы но могут быть выполнены сразу как одновременно, так и с предшествованием. Показан", "то'обнаружение тупика будет состоять в поиске всех простых {уклон я построенном отношении Р% . Приведен пр|!м<->р применения рчзрчйс-

тайного алгоритма.

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

Ь заключении приведены основные результаты работы.

Б приложение вынесены акты о внедрении результатов работы.

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

1. ¿ля выбранного класса ЮС с учетом его особенностей пред-лолен и обоснован способ организации ОС, предполагающий использование одной Из однопроцессорных ОС в качество основы для создания ОС \Т)С. При этом ОС ЖС остается совместимой с выбираемой базовой ОС

к наследует ее основные параметры и характеристики.

2. Для ОС РЛЗСС, выбранной в качестве базовой, в соответствии с предложенным способом организации ОС МБС определен набор необходимых изменений и дополнении, внесение которых позволит получить ОС НЕС.

3. Предложены реализована в ОС ?,ЬС средства управления раз-доляем>::гл ресурсами МВС как абстрактными ресурсами, при птом возможно использование такта средств как для взаимоисключения, так и для' синхронизации процессов.

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

5. Рг.зработаны алгоритмы и программы ОС КВС для обнаружения и

ликвидации тупиков. Алгоритм устранения туг.:--; ;-ч;ггньает не только стоимости снятия процессов, но и такие и\ ^¡иц-имости, при которых снятие одних процессов может потребовать снятия дпугих.

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

7. Разработан и.реализован в ОС '.ВО оригинальны» способ резервирования ВУ на уровне операций ввода-вывода, гсзволчю'лпй. резервировать ВУ как целиком, так и отдельными участками на других, в некоторых случаях возможно разнотипных 'ВУ или их участках. При атом чтение может быть задано нз с ВУ-оригинзла, а, например, с самого быстрого из резервных ВУ. Т.о., мо^.ет быть псвышена нз только надежность работы с БУ и данными, но и скорость доступа к ним по чтенгс.

Ь. Предложен и реализован алгоритм перемещения локальных ядер ГС ?ВС по СП без перезагрузки.

9. Для отладки начального варианта ОС ИЗО разработан оригинальный метод и реализующие его инструментальные средства, позволяющие представлять распределение ОП Еыбранного класса МВС и размещение ОС МВС в СП инструментальной однопроцессорной ЭВМ. Использование этих средств позволяет значительно ускорить создание системы в целом.

10. Для создания средств поддержки параллельного программирования на основе анализа суцеств;шщ1гх моделей параллельных вычислений предложен новый аппарат моделирования параллелыдах процессов. В терминах зтого аппарата сформулировано одно из условий корректности моделей, состоящее в отсутствии тупиков определенного типа, для выявления которых предложен соответствующий алгоритм.

11. Разработана и реэлизована на ЭВМ СМ-4 и ПЭВМ IBM ГС/AT инструментальная система, позволяющая использовать предложенный 'ср-мальинй аппграт для спецификации, моделирования и анализа параллельного и распределенного ПО и других различных систем, содер-мчи? параллельные процессы.

1?. Ссзцена версия ОС, совместимая с СО PAiOC, для работы пг. МВС, Процессоры которых имеют систему команд микропроцессора типе КШ01, локрльные ОП-и доступ к общей СП. Резидентные в СП части ОС МВС реентерабельгч и пригодны дли размещения в ПЗУ. Лскчлънки ядро . ОС ¡'ВС обладает возможностью перемещения по ОП без персзр.гругчн. Кодифицированная система генерации позволяет ползать различные варианты ОС МВС применит?льно к конкретным особенностям пппоратясГ части МВС и снега"!ике ее приложения. Можно генерировать и вярч<>нту ОС РАФОС с дополнительными 'J-ункпиями, разработанными при создании ОС.

МВС (перемещаемость, резервирование ВУ и т.п.).

\

ПО ТЕМЕ ДИССЕРТАНТ!! ОПУБЛИКОВАНЫ СЛЕДУЮЩИЕ РАБОТУ

1. Марков Н.Г., Маркова Т.Н., Смирнов А.Ю. Унифицированная операционная система реального времени семейства бортовых вычислительных комг,.-;ексов//Теэ.докл. I Всесоюзно?? конф. "Методы анализа надежности ПО на основе моделей нечеткой логики и качественных описаний". - Кие б: ЮМГА, 1987. - C.7I.

2. Марков Н.Г., Маркова F.H., Смирнов А.Ю. Программное обеспечение отказоустойчивого бортового вычислительного комплекса/Дам же. - С.72.

3. Смирнов А.Ю.'Базовый резидентный монитор реального времени для бортовых вычислительных систем//Тез.цокл.Х1У Всесоюзной научной студ.конф. по проблемам авиации и космонавтики. - М.: МАТИ, 1968. - С.31.

4. Смирнов А.Ю. Ядро операционной системы для* двухпроцессорного вычислительного комплекса//Доклады ХХУ1 Всесоюзной научной студ. конф. "Студент и 1ГОГ, секция Математика. - Новосибирск: МГУ, 1988. 0.68-73.

5. Богдан A.C., Марков Н.Г., Смирнов А.Ю. Об однсм подходе к имитационному моделированию вычислительных систем//Тез.цокл. Всесоюзной конф. "Моделирование систем информатики". - Новосибирск:

[ . ВЦ СО АН СССР, 1968. - С.7-9.

6. Марков Н.Г., Смирнов А.Ю. Операционная система реального времени для мультимикропроцессорных управляющих вычислительных ком-плексов/УТез.докл.Всесоюзн.научно-техн.конф. "Микропроцессорные комплексы для управления технологическими процессами" (Грозный сентябрь 1989),-М.: ИН50РМПРИБ0Р, 1989. - С.54-55.

7. Марков Н.Г., Смирнов A.C. Операционная система для мультипроцессорных вычислительных комплексов/Лез.докл. П Всесоюзн.сове-

• щанип по автоматизированному проектированию ПО систем .управления двик^анмися объектами (Влбачье, октябрь 1989) - Харьков: ХАИ, 1989.

. С .192-193.

8. Марков П.Г., Смирнов А.Ю. Операционная система многопроцессорного вычислительного комплекса//Сб.научн.трудов "Проблемно-ориентированные вычислительные комплексы". - Новосибирск: ВЦ СО АН СССР, 1989. - С.79-32.

9. Бурлаков D.H., Марков Н.Г., Смирнов А.Ю. Организация пар-л-

лелыюй обработки информации на многопроцессорной вычислительной системе/Дел.докл. Международной конф. "Высокопроизводительные вычислительные системы в управлении и научных исследованиях (Алма-Ата, сентябрь 1991). - М.: ИЛУ АН СССР, 1991. - C.I3.

10. Мчрчов Н. Г., Смирнов A.B. Операционная система реального времени цл;1 многопроцессорных вычислительных систем//Сб.научи,трудов "Проблемно-ориентированные вычислительные комплексы". - Новосибирск: ЗЦ СО АН СССР, 1991. - C.R0-P6.

11. Богдан A.C., .Марков И.Г., Смирнов А.Ю. Система моделирования параллельных лропессс!з//Управлл!сси1е системы и машины. - 1991,

I? 8. - С.87-94.

I

Подписано к печати 2I.0P.92. Заказ зо. . Тираж 100 экз. 634004, Томск, пр.Ленина,30. Ротапринт ТПУ