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

МОСКОВСКИЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АЗТШАТИЖ

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

Нормарк Виктор Михайлович

МЕТОД ПЛАНИРОВАНИЯ ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ 5 НЕОДНОРОДНОЙ ВЫЧИС.ЩПЖЬНОЙ ЖШЕ О ПЕРЕСТРАИВАЕМОЙ СТРУКТУРОЙ

Специальности: 05.13.13 - Вычислительные малины, комплексы,

системы л сети; 05.13.II - Математическое и программное

обеспечение внчислятельных машин,

комплексов, систем и сетей

АВТОРЕФЕРАТ

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

Москва - 1990

Работа выполнена в Пензенском научно-исследовательском институте математических машин.

Научный руководитель - кандидат технических наук, доцент Цзетков A.A.

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

профессор ШустикоЕ 5.И. кандидат технических наук, доцент Пецко A.A.

Ведущее предприятие - Научно-исследовательский центр

электронной вычислительной техники <НЩ ЗВТ)

Защита диссертации состоятся "__1990 г.

в __ час. на заседании специализированного совета

К 063.54.03 Московского института радиотехники, электроники ж автоматики по адресу: И7454, Москва, проспект Вернадского, 78.

С диссертацией ыокно ознакомиться в библиотеке института Автореферат разослан "_££_" 1990 г.

Ученый секретарь

специализированного совета je. т.н. доцент

j'XoK^ Г.И.Хохлов

ОБЦАЯ л/ЖХГЕРКСТШ РАБОТЫ

узлъность тш. Развитие кскплексов и сетей ЭКл являет из осногных направлений ускорения каучно-техниче-зогрессэ, определенных ХШ1 съездом КПСС в "Основных направлениях зконоютесгого е соцезльного развития СССР на I985-IS90 гог'т и на период до 2С00 года", где поставлены задаче: "Вноокг:.з$ телека наракавать гзсвтаЗк прикевенгя оовреиен-кых Бысскопрэизвпдлтелькьк: злек.тронно-зычислЕтельнкл мэалн всех классов. Продатсь создание и пзвнеать эффективность работы за^гслзтеАЬнак цзятров коллективного пользования, интегрированных банков дзш-пд:, сетей обработки передата ик^орма-дне".

В насгоягеь вре;.:я функциондрувт или проектируются кс:.:л-лексд л сетл cS" раз.ллчното назначения. Огрошке штгрцзлышэ затрат": на :сс создание и эксплуатацию выдвигают нз пс-рвш: ллан необходимость пошзекня.а-^ектяшостя хх работ, создания методов управления вычкелзтеяьтш п шфордапквяшвга реезреа-г.ш« Одно? из способов повнаешгя эффективно с тз работы вычислительных систем (БС) является создание эффективных средств статистического :: д'21з:.лгчоокого плзт'ров'ния выполнения параллельно: иродессов в ВО, уштиэахяда неоднородность а дзвашч-ность язиеазкпй структуры, свойственные современным БС.

Тробозааакх, предьявляеишга к системам планирования процесссв (составлен»! расписаний решения задач - РРЗ) для современных комплексов я сетей ЭШ являются:

I) всего и огообразия характеристик задач, ресурсов и сказххваюиих влияние на особенности решения задач в кокзлекевх а сетях ?Б;.! в настоящее время. Неучет хотя 'ы одной тэко2 характернотякн приводи" .либо к большим • отерям мощностей ?3,5, либо к непригодности к выполнение составленного расписания. Расшатризае?/Гь~л: характеристиками задач г ЭЕ.5 в шекзас-ся е паотояцее время методах, составления РРЗ являются осъе."ы потребления ресурсов задгчзиг и поставка ресурсов ЭШ, допустимые нптерззлы зремзнк решения задач, связь задач до предзэот-вованго:. Учет уле зтлх характеристик делает задачу сос-звтения РРЗ HP - лолноЗ, то есть задачей, для которое непгзеепш ?сч-

ныв метода рзаеняя, более эффективные, чем полный перебор. Кроме того в современных вычислительных комплексах при составлении PPS необходимо учитывать наличие ресурсов (устройств, тсмов, информационных массивов), обдих для групп ЗНЛ и пере-:,:ещэе:ля меяду 3H.f, возможность динагшчзского изменения конфигурации ресурсов ЭВЛ:

2) обеспечение возможности рэсяироння состава учитываемых характеристик задач, ресурсов к 5Вл и методов составления PPS. Отсутствие такой возмоганост: приводит к непригодности разработанной системы составления РРЗ при появлении дополнительных возглояностей по обработка инсораацта (например, новнх операционных систем, банков данных, средств связи иеяду 53«');

3) обеспечение простоты использования средств составления РРЗ персоналом вычислительного центра как при задании исходных данных, гак и при обработке результатов, что особенно ваяно при обнаружении незозмояноегг составления РРЗ- при заданных ограничениях.

Многообразие связей меэду задачами, ресурсам! ж ЗШ и размерность задач составления РРЗ в совреиеягагх вычислительных системах (комплексах и сетях ЭВМ) ке позволяют использовать для составления РРЗ точные метода математического програыглгоо-вания, поэтому все большее внимание уделяется развитию приближенных эвристических методов. Однако отдельные эвристические методы решают только частные случаи задач составления РРЗ я не охватывакт всего комплекса требований, предъявляемых в настоящее время к РРЗ в комплексах и сетях ЭШ. Для решения достаточно широкого класса задач составления РРЗ необходимы методы, основанное на использовании ке отдельнкх эвристик, а совокупность знаний со' управлении вычислительны,; процессом, то ость "егоди искусственного иятелтекта (151) и ситуационного управления. Еслаеой вклад в развитие этих мзтодоь внесли советские ученые - Г.С,Поспелов, Д. А.Поспелов, Э.З.Попое, .".".Кузин, £3. И. К тыков, З.Х.Тыугу, 3 .И.Ескугоз, В.Н.Пузкия и др. - и зару-белше ученые - М.Мннскяй, Г.^ендрикс, д.ГосЗрсз, Е.Еппсок, ,П,,Слс"лгл, Р.Оайкс, Р.Еенк и др.

Область "й! в настоящее время бурно развивается и эхзоти-вает такие направления, как. преде таЕлекг.у -знании и роб о«;' с

ни:.:;:, лдокировзше целесообразного поведенля, обшше чь. «дека л гсзтеллектуьмыгоЛ слсгсип кз язнно, приблг'сеЕком к естоет-зенлоз-у, псдедешге т?сляскт?эльных с::отсгл. Наряду с эти:::: ЕопраЕ.кпса.'О! к з рэлклл лл: р&звхвготся подходы к раасгеш кснгрсшо: достаточно хпрокигс классов га.лрл к к. построекгл сяецгэдхг^ро'знзкя слетел рвьсязщ сгтлг сэда^ч. 3 данной работе иссдедуктоя вопроси ссстззлзяхч ??3 в кс&.ялексах л сетях ЭКЛ с лелельволсллюл ыо:-од:.з 131 в чзетл лзр:,;лпоганля мсдсл: объекта (ллллсллтеллчего цуоцэсоэ) яз основе совокузЕогтз зарзлео зелс.тлдн'дс злзн:п: и лсяодгзогения это« кодеди для цзленепрот-леллого ксцбноадя состояния объекта (составления FF2). .Кроле toi'o, в донксй роботе иголсзухгся вопросы дзг/знешл елзссй прео<;рзгуо*:ых облэктсв (состава характернее:^ вшпслгтодгчсгс лродзесэ) и ооЕолуллостч: знаний решшей czctsi®, а такле че-ловеко-лзилллые способы составлелты PFS.

Цель езботн. Цель работы состоит з разработке к нсследе-взклп метода плеилровэьлзя нжолненпя гврзлделгкьк лроцэс^о-з Е неоднородной вкч-юл:7ел5КоЗ систекз с пэресграЕвзsswü структурой, лрелуелзтрлнзллего юзмозность резриия средетз яяеняго-ванлл процессов пол совер'ленстзорглпд вычизллтолькой сксгеггн, азто:зт:1чссло; г лелезеле-'лэлллллл пелесл: плзклрсззлдзч средес-еов.

"етолы леследсвзкля. Пси разработке раздкчяш: зопег.гск лостроелпя слстеглн согтавтеюгя PPS кз основе ссзокупаол'гя злэ-:niii сб упрзелетлст кяюдателшня процессса астюдьзовалкоь истода теорлл ;.;по;::еслг, аатеистпческой логики, т«зт.катачес::ого ярогрзггшроззнля, искусственного интеллекта.

.Чаучнэя нова ста. Б диссертационной роботе задуте—: л лн-косятся па звз?:ту следулгше результаты:

I) способ формального опнсетгл дроблскаоЗ слтузктлл ссстзл-лелпя Р?3 как некоторого обьзлта (системы упрозлс-лля sut.ct.z-телылел лродосссл), яодок'зазго лерзяод? из начального сзсхол-ш:я з целевое з процессе состзллекля РРЗ, ysjrtsasrcil коуллтл-зг&а&з з диапкхлся ^етодех состг?«вгя Ь-"3 хзгт хлорке тле: зс-дач, ресурсов, 5&5 - лзлллл^ лн;ллзлдуаллнлх ресурсов д:-'.', тал л o6:?iX росугеоз дл:-: гругш Ж' л иорхгооатж ресурсол пе:;:^' ?Z:I, нлллллз у задел ле толкло котребляп^-у. ;.о :: лее-тзлллз.'лс: ресурс от;;

2) принципы построения структуры и содержания совокупности знаний od управлении вычислительны:.; процесс о:,:, используемых, дня оценки ситуации и формирования стратеги:: составления PPS;

3) метод построения модели системы управлении вычислительны:,: процессом на основе совокупности знаний как системы конфликтов, позволяющий осуществлять управление перебором вариантов составления РРЗ для широкого диапазона требований к составлению РРЗ (различных критериев составления PK, различных учитываемых характернотик вычислительного процесса):

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

5) языковые средства человеко-машинного составления РРЗ и развития средств составления РРЗ.

Практическая ценность. Использование предлагаемого метода составления PPS позволяет:

1) существенно расширить класс решаемых задач составления РРЗ в комплексах и сетях ЭВМ за счет рассмотрения на учитываемых ранее сложных взаимосвязей между задачами,, ресурсами и ЭН.1 и возможности адаптации системы составления РРЗ к конкретным условиям, что позволит автоматизировать составление РРЗ на многих БЦ народного хозяйства страны;

2) автоматически определять конфликтные значения характеристик. задач, ресурсов, ЭВМ и устанавливать причины невозможности составления РРЗ в случае их наличия, что значительно облегчает принятые решения по корректировке состава и характеристик задач в процессе управления решением задач;

3) организовать ре^им диалогового решения задач составления РРЗ я управления вычислительны!.: процессом в сложны?: ситуациях .

Экспериментальное использование данного метода для плакирования транспортных операций дает основания полагать, что данный .метод г/отсет быть успешно перенесен в другие области плакирования в народной хозяйстве: сетевое планирование, календарное n.nas:ipc3sj-3ie зэтолнения р^бот.

Регстиагегя результатов portera. Метода составления РРЗ, предлога ег.гке в работе, реалпзоганп в "Прогреете планирования прохс.~:де:-:ид коуплоксоз задач s ¡.-лэго'лзякнпок вцчкслктельнсгл кс:.:пленсе":.:Т?1!, разработанной под руководства'.: л при участии эзторз. Програ:.:»а LiT^u внедрена в изделии 65с386 и ко стенде Глазного конструктора Экономический зсфект от гведре-

:с!я програм.ш составил более 40 тисяч рублен. Внедрения пгд-тзергдеку соотвстстзугг-д-лл! акта:.д.

АнтХ'этг'я Пб томе диссертационной работы сдсгзгш

доезди не следрзди нонСсренцзях: ХП71 "зучнс-техннчзскгд "он::эр:-:пх:л :Z~'CA, Позкгз, 1577г.,; ХЗУП научно-гехипческ:-я конференция ГЗРЗА; 'Лооггэ, 1?73г. ; Наjчно-гзхнзческ&я кон.Те-Р'ниия "Вопроси проектирования и ;.:ого:.:стичёокогс обеозе^счдт? пплор^зилонно-гичнзлитэлынгз: спсте:.-", Пенээ, 1?8Сг.; IÏ7 научно-техническая конференция молоди - учении и опенка лис тсв Зрован, ISSir.: научно-технические консерзн.пп: в

ЦП"'.;.:.

Дублдкзгпн. Результаты диссертант опуолгхезэнн в 7-:: печатных работах.

Структура к о^-.ду работк. Дистертаигя состоит из ¿веде-ния, пяти глав, ззклкченпз, синена л„;ерйтуpu z 3 грпл осени::, кзлог.епа на 22? листах ;.:ан:копнсного текста; содержит II рд-сукков, б таблзп;, список литература из 176 кзигенолзний и лрплонения на 60 листах.

СОдЖАШЕ РАБОТЫ

Бо введении отражена З1ртуальнооть темы диссзртащюкго;: работы, дана (гор.'.г/ляровка деда работы к излопены наиб-лее еу-Еествзякне положения, зшоокиые на защиту.

В главе I приводится крапай обзор нетодоз составления РРЗ в комплекса:: и сетях 3XÎ, дается ^орхалыюо определение сестс-мы улрявяетм вачЕслггелкшм процессом (СЗ"ВП> как ппсб-лег/нои ситуации составления РРЗ и модели системы управления ви-числительнит.? процессе:,: (ХУЗП) как описания стратегии составления РРЗ, пригодится постановка задачи разработка осетсма составления РРЗ.

Еа основе обзора пр:злсно:п1я рзздачзак кезодоз для cocvsr-леиия РРЗ делается яиьод о то:.?, что для построения систе..'-.:

ссссь-лэя^я ?РЗ в комплексе л сети S3.!, удовлетворяйте:! требо-занзягл возмознэ более полного учета характеристик задач, ресурсов з 32..;, обеспечения Еог:ло;л:остп ргсагрекия сгстава учп-сд-сгелзх ;шрах:тзрпстлк вычислительного процесса и обеспечения простоты пспользодакдя средств составления РРЗ наиболее подхо-дяджа явладтся методы тскусственксго кнтеллекза (1-Е), соче-' танлиэ в себе достоинства эвристических методов по í-S¿e::T/¿iZQ-щ резеншз задач в частнпх случаях а возмогкостльп адаптации к различный условиям прижгенпя и развитом. Для примэнения глото— дов 2П к составлении РРЗ определяется проблемная ситуация составления РРЗ в виде СУЗП л стратегия ссстааявггя РРЗ в виде

:.:сузп.

Системы х управления вычислительным цроцессси и задач;-' составления РРЗ определим па основе следулгиш шоизете и отно-аекяи:

Зд(х), Р2С(д), Э(х) - множество задач, ресурсов, c5.".¡;

П(х) - глю-тество процессов. Цроцэссаш: язлялэтся задачи и эа,1, то есть П(х) = ЗД(х)иЭ(х);

ПЩЩ1(2,р) - множество задач, предшествующи задаче р;

ЗРЕД(х,р,с) - продолжительность времзт: реаэяпя задач;: р на ЭВМ с;

ЗРН(х,р), ВГК(х,р) - директивные сроки начала и конца решения задач»: р;

CEj70G(х,р,е), 0Епо„(х,р,е) - объеш ресурса е, поставляемо и потребляемые процессом р;

РЕСос(х) - шожество обтеокстомшк ресурсов, хзрактерд-зувднися те:.-, что онк ¿гагут использоваться ззлачагд', вшолкж-д.л.глсл в различных связаших по сбдсспсте.-ллш ресурса:.* 351!. PLC с(;с) явлгэтся лод-..нолество:.;. ?,:по::;езтва F

LCT:(x,c) - ¡.лозсство 5Л, сгязаяша с 3LI.¡ с по об^еопстод-ресурса-,:, c?cLCS(x,Ct) означает, что осли в СДЛ ст находится ;:олоторь.И обцесисте:лн1и1 ресурс, то в 02Л с о ыо:::ст кгхс— ;лть:л лреиеос, пстреблякщи": "тот ресурс.

¿Злектчппосгь РРЗ суде:.! определять гг;о:,:онз;; ведения Lccx SU384 при огрзпгчшсга, н.-.клгп.'Т'гси.зл 7V¿?:mmsz: ви-

ло -

Рр:ипг:г:изл;нгл ог.л:тпш:л псст:-.-х~ л в сдачи состав-

о

■ Л"::-: 173 ст изос.:о зрели лс в ллгерзгурз "лл:-::- ноли-из у

задач не только потребляемых ресурсов, но и поставляемых, что резко усложняет зэдсчу составления PF3, накладывая дополнительные ограничения из мнопост2п одновременно регаомых задач. 3 тс ме гремя рассмотрение указанны:: взаимосвязей ыежд!/ процесса:.:!: позволяет учесть арактячео.-шо требования :сруян иадач к операционной обстановка ь отдельных частях вычислительной слстеш л реалазоззгь в Р?3 динамическое перераспределение мемду СЗ" различных ресурсов.

3 соответствии с вымеизломенным згдачз дзнкей работы состоит в следута:.:.

Требуется разработать систему составления ?РЗ для планирования реаения зйдзч в комплексе а сети C-S.I, удоз-летгоря"".'". требованиям: '

1) учета характернст':::: задач, ресурссз и ЗЕЯ, пр^.-дс:-ннх в подразделе 1.2. В качество критерия эу! активности расписания V для СУБП х - ci3 (x,v ) - будем рассматривать дт.пту расписания v или максимальное врем^ ззверагния задач для расписания v ;

2) обеспечения зозмомности рзелпрения осогзза у-дпквзепде характеристик Eil и введения дополнительны:': показателе; эйс:-:-тиенссти PPS;

3) сбзипэчсыпл зозмомности гшедкепкя кат. автомапг-тзексгс, ток и чзловско-:.аЕкнного решало в составление Р?'.

Для построения системы составления РРЗ на основе сопокуп-ностп знании необходимо расработать: структуру и содержание совокупности знаний по управлению вычислительным процессом: структуру и способы построения модели СУБП, способы выбора не основе коде® СУБП зр^ок-тивикх варппнтоз рлеяр^дол-^ыхт irpcicsc-сов. Исследованию п разработке метода пдэкирови-шя преде о с с:;-в БС по указанны:.! направлениям и посвящены зсол>здущЕв глздй.

Б главе 2 рассг.атрлЕаются обенэ критерии и показатели ошпе: г.елеори-знгирева иного изапг.:сцо:'етш'я процессов, структура и содержание соиокутшостл знаний об управления лзагмоделот-вием процессов (ЗНУВЯ).

•Э&аз критерии и показатели одели з&годаКиЛсзс&зг промессой предназначены для использования их в определении:; слом.-ы-тое SITOH. Б начестве cc'iiкритериев проц-эссгс

используется кос^щи?а?а aarpysjcn ЭР.'.' по раатргои ресурсам ::

по приведенной ресурсоеккостп, коэллшпекты не:.:облЛы:ост:: про-деооев в пространстве г во рреленл. Бледен следуотпе обозначения :

ЗНг.1ШТ(х,р,е), 0НС(Поа(л,с,е) - потребляемая задачей л поставляемая сВЫ с ресурсое;,5:остп по ресурсу в СУШ х, определяются соотношения,®::

ЭНр>П0Т(х.р,е) = ОБвот(х,р,е) • БРВПср(;;,р)

ЭН^псс(х,с,е) = ОБпоси,с,е) - (Б?К(х,с) - БН1(х,с)),

где БРВПс0(л,р) - среднее арифыогяческоа времен в-лголненля задачи на рззлтганцх ЗВМ в СУЕП :■:;

КНАГ?р(х,е) - коэ№ицлент нагрузи. 5ВГЛ СУЗП х до ресурсу е, определяется соотношение:.?:

се 3(5:5

ШЩд^х.р), МЩП0С(х,с) - потребляемая задачей с г, поставляемая ЭЕМ с удельнпе приведенное ресурсоо.лкостп, определяется соотношениями:

ЩЧцодСх.г) =10Бпо1(х,р,з) • Кг1СРПр(х,е) • КНАГРр(х,е) ееРЕС(х).

ЩЧП0С (х.о) =Z 0Блос (л, с, е) • КНОВ.'р (х,з) • Ш1АГРр (х, е), ее РЕС(х)

где: КНОШ(х,е) - коэффициент нормирования (стандартизации) еддницы измерения осъеш ресурса, определяется соотношением:

= ЙОТШ^с^У); сеЗ(х)

сН,0Ф(х,р), ЭНпсс(х,с) - потребляемая задачей р и поставляемая ЗВ;,1 с приведенные реоурсоегнссти, определяются ссстно-еэзпже:

гкДОГ(х,р) - :,15;шт(х,р) • врвпср(х,р)

ЭНЕОС(х,с) = ЩН^0(,(Х,о) • (БРК(х,с) - ВРЩХ,с)>

Б сгязи с те:т, что прлвсдентзя ресурс ос;,зшетъ характеризует способность ЗР.'Л ¿шм&ярь косогорий об;.е:.т в::члсллтелъ-

рэбог, & краподешал ресурсоемкоетъ задач хоралте-рллует объел гыс:ел:л'елз"лх робот, поддег-ацк? ызтоллз*:::;:, нлеето

терминов, "приведенная рееурсоемкость", "удечьная приведенная рссурсое:,кость" и "рееурсоглсосгь по ресурсу" будем употреблять термины "обдая энергоемкость", "модность" и "онергоепсость по росурсу";

¡•л/УГ?(х) - коз-Кгакент нагрузки СНД по общей онергоем-кости, оппеделяется соотношением: £ сНП0Г(и,р)

КИАГгЫ = ^¡¿кл)-

^ ЭР а,с) се о'сЙУ

КН;.Ю13Р(у ,р) - козйрпциент немобплъности во времени задачи р з С7БП к, определяется отношением среднего по ЭВМ-времени выполнения процесса р к длине допустимого ниюрвала времени выполнения процесса р;

КЕ.;0ЕЗ?со(х) - срэдневзвеаенный козт(|жсаент нецоопльнос-ти во времен!* задач в СУВП и, определяется соотношением: 2£НГ10?(х,р) КИ0ЕЗ?(х,р)

:е:.;оБВ? -

£ ЗЕ^Сх.р)

ре ЗД(х)

КНЕЗ(х,р) - коэйрзцпс-нт кенобильнэстк процессов р в пространстве для 037)11 х, определяется отнеаенлеи количества ЭВМ, на ксторнх неьозпокно решение задачи р, к общему количеству ЭВМ в СУБД х;

КМБПР(х) - средневзвепеЕннй коэффициент немобильности задач СУВП х в пространстве, определяется соотношением: 2 3Р^0Г(х,р) • КЛРИВ(х.р)

ККЛОБЛРСх) = ре5Д(х)-

2 ЗН^х.р)

реЗД(х)

Рассматриваемая ЗНТБП представляет собой шов.есгвэ описании конфликтов взаимодействия процессов, ориентированных на представленное СУБП некоторых подобластей предметной области взаимодействия процессов.

Подобласти предметней сбласти рассматриваемой совокупности знании разбиты па 4 уровня. Номера уровней соотБетотзуат числу неедкигчных множеств элементов СУЗП, относящихся к дан-ног».™ уровню.

На перло:.? уроаао 2Н75П расоигиркваются СУБП, ссдерпзщне ¿кстество задач, одну ЭШ, один ресурс и одан интервал зре:,тени.

На игорсм уровне бегщ рассматриваются тили моделей С7ВП, у которых негдинпчны множества задач и одно из множеств - ресурсов (тип р), интерзалоз апохеки (тип Ш или 3£л (тип 5).

На третьем уровне 2ПУЕП рэссмэтриззьтся тале моделей СУБП, у котор:?: единичны мпеззетао задач и пари шолеств ресурсов и хктервалов времени (тип ?И), ресурсов и ЭЗУ (тип Рс), интервалов времени и 5Бл! (тип Ег).

Нз четвертом уровне ЗНУЕП рзсскатрпваэтся тшг моделей СУБП, у которых неедиикчнн шогоства задач, ресурсов, интервалов времени и 23.1 (тип РдЗ).

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

К конфликтам, входящим в данный, относятся конфликты одноименных тшюв низааго уровня.

Предает конфликта задается функцией, определяющей отклонение требуемых характеристик взаимодействия процессов от хчеыцихся, интервал допустимых значении которой находится в отрезке 0 * I. Нулевое значение функции, определяющей предает конфликта, означает, что конйиикт разрепеы. Стороны конфликта задаются ^уккцияж приоритетности процессов к предпочтительности £бй для процессов, интервал значений которых находится 2 отрезка 0*1, то есть здесь совмещено задание сторон конфликта и стратегии разрешения конфликта.

Конфликты первого ранга определит возмомлость оостг-вде-кия ??2 в СУБП, сткеся:;лхея к соответствуг.деи подобласти. Предметы данных конфликтов задаются ког^аяюеятзш нагрузки по обмз£ энергоемкости (для конфликтов первого уровня) или по от-г.елылг.: роеурезм в интервалах вречевг и 33.1, то есть спргделя-

зтся показателя® KHÄTP с индзксагли, ссразоззглппгл комслнзп:;-:.:и символов "Р", "И", "S", определявши: т:ш соответствуггсл подобласти. Оудкция приоритетности процзссзз для данных т'энф-ликтов задается относительным (приведенным к интервалу G -г 2] вкладо?,: процесса в нагрузку, определяем?» предыэток хокфлакга.

Кснфяхилты1 второго ранга как и показатели, на основе который определяются ид олеллентк, разбита на 3 группы, характери-ззщее влняназ трех факторов, прстизодонствуыдас составлен:" РРЗ: неравномерность поставки и потребления энергоемкости, связанность процессов, дискретность значении объемно-временных характеристик задач.

3 группу конфликтов, вызванных неравномерностью поставки и потребления энергоемкости входят конфликты неиобигьностя процессов во времени (ЖОЕВР) п з пространстве (ГЕМОБПР), а тэкге конфллплты нагрузки по общей энергоемхостл д~я процессов, использукциг перемешаемые ресурсы (KIKîPEC).

В группу кодфлшгтсв, вызванных связанностью процессов, входят конфликты выполнения процессов, ключевых до предшествовании СКПРЗД), выполнения групп задач, связанных по ресурса:.:, (КРЗД), выполнения центральных задач (idlSHTP), взаимоблокировки пспользования ресурсов (КБЛКР).

В группу конфликтов, вызванных дискретностью значении объемно-временных характерно ял задач и ЗЗГЛ, относятся конфликты выполнения громоздкие процессов (KTîTvî).

В глазе 3 доследуются структура недели системы управления вычислительным процессом (Ш7БП), торгсгоозалпле МСУБП па основе CiljiiH, составление РРЗ на основе »MC733, зСсзктизность различных алгоритмов перебора вариантов составления РРЗ.

;.;СУВП здесь рассматривается как система конфликтов взад-коде2с5вта процессов, им&нппх кэсто в обрабатываемой CiЗП. Конфликты 1ЮУВП определллзтея как екзеюлярв типов кенфллт.тоз, рассмотрение в ЗНУВП. Поскольку б различных созтоялпллх СУРГ конфликты кот?? находиться з состояниях неактивно:.:, выполнения, отработанном, невыполнимом, конфликта будем рассматривать как специального рода процессы, a LÎ37LJJ ra:t специального рода СУБД.

Ра основе выделенных кзнлл:п:тод ZZ7KÎ осуществляется формирование сбдои стргтспя составления РРЗ, спрздадяицс^ся

¿7нкцк»л приоритетности процессов и предпочтительности ЗНЛ для процессов.

Функция приоритетности процессов относительно ¿¡СУБД ы -П?лОР(ы,р) - додана учитывать привязку процессов к допустима интервалам времена; и величины приоритетности процессов по различным конфликтам. В соответствии с згил определим (функцию П?П0Р(м,с) следующим выражением:

ПРИОР С г, р) = ПР;Ю?3р(:.:,р) +1ВЕСК(ы,к) • ДРИ0Р-.(ы,::,р),

неКСШИи)

где HPHO?3Q(iM,p) - характеристика приоритетности, процесса р с точки зрения привязки к допустимому интервалу времени, определяется расстоянием от середины допустимого интервала времени до «окна планируемого периода;

Я0:йЛ(:л) - множество конфликтов ¡ЛСУБ11 и;

БЗСК(м,к), ПРИОР, (:л,к,р) - вес ъхжфликто к, определякл:!;-сл значением йулкиии, задающей предает конфликта к, и приоритетность процесса р, определяющаяся значением функции приоритетности процессов в стратегии разрешения конфликта к ¡.¡СУБП гл.

Функция предпочтительности £Ш для процессов относительно ЖУВП, - ПРЕДП(м,р,с) - долина учитывать допустимую область распределения процессов по ЗШ, определенную в МСУВП м, и величины предпочтительности ЭВ1Л для ирсцвссов, определенные в конфликтах МСУВП м. В соответствии с зтзм определим функцию ЦРКИП(м,р,с) следующим выражением:

£ВЕСК(м,к) • ПРЕДЕЦ(м,к,р,с) кеКСШД(м) ПРЕДП(м,р,с) если се ДИСЛд(м,р)

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

где ДКСЛд(м,р) - множество ЭКЛ, допуспелых длш процесса р, определенное с учетом распределения групп задач по ЭШ;

!ШЕДГ1,:(м,к,р,с) - величина предпочтительности 32,1 с для процесса п, заданная в стратегии разреаения конфликта :: . :ЛС7Ш к. При переборе вариантов составления РРЗ на основе ру:-шх1л П?1'ЮР(п,р) и П?йДП(н,р,с) осуществляется внбср процессов для включения и распределения процессов по 33!,1; на основе анализа значении . функции, определяющих предметы конфликтов лСУБП, осуществляется огенкз состояний составления РРЗ и от-

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

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

В главе 4 представлены структура и язшюЕые средства реализации системы составления РРЗ на основе системы продукции, достоинствами систеын продукций, определизлпп.п Екбор ее тля реализации систем составления РРЗ, является сочетание возможностей декларативного и процедурального представления знаний, универсальность метода программирования, естественная модулг-ность организации знаний, простота их модификации и саслирзнце, возиояность организации иэрзллельких вычзедега*. Основных структурннмп нсг.шонентаки слстеаа, базирующейся на системе продукшй, ЯВ1ЯЕТСЛ три тестно связанные неаку собой полекете-ка - глобальная база дзнэах - IS2BI1, совокупность продукционных модулей - 15ЯЗД и систола управления - УГЕП.

Сзлзь с оператором по соста2леки;з РРЗ в интзрзкзппном ре-лолле осуществляется с попе газ к<х.аад язккз диалогового планирования (JH-LFXI). С иоуоцьп комета дпписгс, ягггг ос;, к отеляется егсд синеc::viu ;:грзмсн:п:х Г&ЗЛ и проеме:енн;л: модулей; ввод исходили л.энню: и злдол'; результатов рзц--:™.-:; задание послелог плог е.. лылолнонлл лролул^.енллх г ..::.:; лплзлз l

режа» диалога ирокезу точных результатов и аьед дирек-глв ис дэльне&зему реаеназ задачи. Особенностями лзехз Д}ЕлА:1, направленная! на обеспечение простоты его использования, язля-:отся наличие в нем средств пользователя, администратора слотами и программиста; ориентация на табличное представление перз.меннкх, упоокноцее задание и модификацию их значений; воз-мс.—х.сть как процедурного, так и непроцедурного задания алгоритм;; плакирования процессов.

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

Целями ;непегпмекта. по оценке ойфек'лхзности предлагаемых методов сосгззлэеел РРЗ являпгся определение экспериментальных: оценок:

эффективности различная стрэтетни! лланирсва:к:я процессов;

эффективности различных алгоркгмов перебора вариантов распределения иропеоооз;

ззвзсгмоста врегленкых затрат на планирование -процессов от у.оличестЕЗ задач, ресурсов и ЭШ; .

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

Для оценки эффективности предлагаемых методов осуцестЕлл-лось реиекиэ достаточно слокных задач планирования процессов с варьированием стратегий и алгоритмов перебора вариантов распределения процессов. Рассматриваемая здесь задача при заданное для задач директивных срсках начало и конпа реаенин и от-нопении предшествования алеет рледуюдпе количественные характеристики: количество задач, ЗВ1.1 и ресурсов - соответственно 200, 5, 6.

Результаты скокериментов дтя да»шой задачи, для предлагаемого алгоритма перебора вариантов распределения процессов приведены в табл. I. Гакскмальное время планирования процессов здась 30 минут, гшшмзльное - 7, в то время как при алгоритме полного перебора вариантов за приемлемое время и количество вариантов, иреьшювщое 1000, задача распределения процессов не була репопа.

Га блина I

ЗаСлица результатов гнсзернлсктот

:лол-вс : .илина

Задание Задания пред- :вариан- :рэсднсэ- : состав-

приоритет кости • почтительности : тон :,. ний ления

зэлзч :Э2й для задач :(:л:н. )

Произвольное Предлагаемое Обратное иредлзга емо.мз'

Пре.длзга еглое По ПРИОР,

По ПРИОР. По ДРЫОР'

'зр лр

гр;-л

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

Предлагаемое

Обратное предлагаешь Предлагаемое Предлагаемое Предлагаемое

J4& 18

165

15 ч 13 ч

16 ч

2? 14 ч 1С

24 13ч. 53:,ins. 7

22 13Ч.5С!лк. ?

34 14 ч 10

Из анализа табл. I мояно сделать следунние выводи: наибодьаую эффективность по сравкаваешж характеристика:." качеству РРЗ и времени его состе&тй имеет преглзгаз.'лл:: ке-тод, наиг.теньшуз - с задакиеь: приоритетности, осзрэтньк предлагаемому ;

наибольший эффект в определении приоритетности задач та::; составляя®» Ш0Рвр и ПШО?^;

предлагаемое определение*предпочтительности CEÎ для s V-", эффективнее произвольного и обратного;

предлагаемое дшгашческое изгленение прнорлтетов задач д;г составлении РРЗ, киреваш сЗрззоа убыстряет нрздесс еоетзвле-пня FP3 без зэ:.:гтнсго ухудшения качества составленного РРЗ.

Система составления РРЗ, разлпзулпал укззснлле вид: лр::г-ппкл, разработана лз;л:е ¡НА, имеет оСд-еы £ тис;;-: cr.îj-- -ров, треоует для своего выполнения 233-^73 КбаЗ" оззедг.:.'. гт-

:..лт:: и :ло:"ет бнгь использована д. из со-сззлелил ГТЗ л :.:..... -

пни плстелигельлого процесса но злллз.пте."нлх л а

тли зл,;.

1Б

ЗДШЯЕлЗ

Основной результат работы оосто:г: е то:,;, что рг.зрзоотзк. метод плакирования процессов в комплексе л сети ЕЬ:,! на основе совокупности знании об управлении вшнсллтвльнни процессом, расииряпллия всзмокиости в&гасшхся «зтодов планирования процессов по сфзге их применимости, сложности резаеюзх задач, оперативно:?;; л комплексности резения задач.

2 процессе разработки данного метода разработаны и исслз-л л;:

'¿} епсоос ^орлзлъного опдссныг задача управления зычлоли-;зльн:х: процессом, позволяющий, благодаря зазчдхв.л.-коку раслк-

оестз.33 учитываемых характеристик процессов, белее пол-н;, ""ем з имзлздхея методах планирования процессов, учесть .ссб.-::ш:-стз и ггяд.тсжа рззвитш современных ВС - распрелелен-

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

С) совокупность знаний об управлении процессами в БС, лгепстаыллхцся собой систематизацию, обобцение и дсиолненпе .ю пользуемых з кастсяпеэ время эвристически:; дравал планирования процессов, позволявшая вырабатывать решения по раепределе-;::н-з процессов, более аде:затныс* требованиям к планировании, процессов н совоемерганх 30;

3} нзтод перебора вариантов распределения процессов в ВС, поззоляхцин повисеть.оперативность планирования процессов за счет большей полнота и комплексности учета факторов сокращения перебора вариантов;

4) способ реализации системы планирования процессов в ВС на основе системы продукций, обеспечивающие возмскность развития средств плакирования процессов к адаптация их к »талоняк':;-.;-ся составу характеристик процессов и критериям эффективности планирования процессов;

5) языковые средства человет.з-злашщЕОй системы планирования процессов, сочетающие простоту использования их полъзэвэ-•теллмп-непрогрЕгялистзми с эссективнсстьн и зозмо.нностъп расширения путам зхлэчення дололнзтелкпк пользовательских икформа-:пюн1плс и программных средств.

Предлагаемые т.^тоде позьолдпт строить глзлде, здзгддру— мне д кояяретпш условиям, способна« к рггвптгк. ссгггг'к рзвания прспзссев е ЗС.

Зти методы с успехом цсгут сеть пспользсвзпы ;; z-Ji psrr-дия задач д друг:д: областил человеческой деятельности: согева" планировании л управлении:, плакировании трзнсдсртпыд сверен::::, планировании: тсагадолггесиэ: опс-рвпсй обработки деталей л др.

ОГВЖАЩЕ

1. ¡Лотин Л.Ы., Нзрмзрк 3.,V¡., ¿углллов A.C. Построение дел: управления вычислительным процессом /7 Вопросы радиоэлектроники, сер. ЭВС. - IS76. - Был. £. - C.S5-I0Q.

2. Нормзрк 3.2., Еумилов A.C. О системе дкспетчиродания прспессов в АСУ // Вопросы радкоглеатрсаига, Сер. сЗТ. -1280. - Вып.13. - С.55-55.

3. Нор.'.гзрк Б.;:., Шугл:лоз A.C. Составление 'рзспгсашгд- podo? для шгагсмапшкнсго вычислительного комплекса // Запросы радиоэлектроники, Сер. ЭЗТ. - 1931. - Вып. II, - С.П2-Ш..

4. Нормарк 3.I.Í., Щуиялов A.C. С построении диалоговой системы составления расписании репенпя задач на вцчислитель-нсм дог.даексе //. Вопросы радиоэлектроники. Сер. ЗВТ. - 1ЭЕ2.-Вып. 8. - С.51-55.

5. Пормзрп З..У. Пришили яостроенкя д результаты экспериментального исследования одной системы составления расписаний ресения задач // Ззпросп рздиослектронигл. Сер. SB1, -1285. - Вып. 5. - С.54-8Е.

5. Нормзрк З.М. Есдользсвакие систем кокс.ди:тньп: сидении для ссстазлепия расписании реаения задач в комплексе :: соти ЭБм // 1езиеы докладов ГУ научно-технической кон^ерен-цкк молодых ученый и специалист л; ИрТ-ИЕГ.!«. - лревок. - IEC.7.-С. 15-15.

7. Нсрмярк В.:... Плакирование транспортных провесное ;;; основе моделирования // Ъовусс:: гадисолоктрон:-;:;, Сер. Г™. - 1355. - Бил. 8. - C.IF-IS.