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

Академ1я наук УкраТни р _ ^ 1нст^т^т юбернетики ¡мет В. М. Глушкова

! '' Г\ П Н •' р Т / ¡ц,;! и».-и

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

СПАС1Т6Л6ВА Св1тлана Олекспвна

УДК 681.3.06

МЕТОДИ ТА ЗАСОБИ РОЗПОД1ЛУ РЕСУРС1В

В ОБЧИСЛЮВАЛЬНИХ СИСТЕМАХ 3 ЖОРСТКИМИ ЧАСОВИМИ ОБМЕЖЕННЯМИ

05.13.11 — математичне та програмне забезпечення обчи^лю вальних машин, комплексов, систем та мереж

Автореферат дисертащУ на здобуття ученого ступени кандидата фЬико-математичних наук

КиТв — 1993

Робота виконана в 1нституп юбернетики ¡мен! В. М. Глушко-ва АН Украши.

Науковий кер1вник: доктор техшчних наук, професор НЩ1Т1Н А. I.

Оф1ц1ин1 опоненти: доктор ф1зико-математичннх наук, професор ЛАВР1ЩЕВА К- М.,

кандидат ф13ико-математичних наук ДМИ'ГРУК Ю. В.

Провщна установа: Науково-виробниче об'еднання «Мкьксистемотехнжа».

Захист в1дбудеться « ^ » } 99 3 р 0 —1_±—

год. на заспданш спещал{зовано1 ради Д 016.45.01 при 1нсти-тут1 Юбернетики ¡меш В. М. Глушкова АН Украши за ад-ресою:

252207 Ки1в 207, проспект Академика Глушкова, 40.

3 днеертащею можна ознайомитнея в науково-техшчному арх1в1 шетитуту.

Автореферат розкланий

1993 р.

Учений секретар спещал1зовано'{ ради

синявськип в. ф.

ЗАГАЛЬНА ХАРАКТЕРНО ГИКА РОБСТИ

Актуальн1сть томи. Для широкого кола систем реального часу розробка продуктивного програмного забезпечеиня стринуеться в1дсутн1ст:а систематазованого кауково обгрунтованиго п:дходу до промислового створеняя систем, як! автоматично налагоджуються на заданий час обчисленъ.

Розб'язок порушено! проблеми мае широкий спектр важливих зас-тосуван.ь, тому будь-як! результати теоретичного та практичного характеру становлять певну ц!нн1сть. Ряд окремих питань, як1 доил ль -но використовувати при досл!дженн! даного напрямку, виргшен! в роботах Л1пасва В. В., Шнейдера Б. М., Головина Б. Л. , Гуленка В. П. , брмольева Ю.М., Чичканя I.B., Cohen i. , Gabrieiian А., McNamee L., Trawick D., Shaw А. C., Melayer D. Проте достатньс уэагальнгшч x публ1кац1й у напрямху комплексного дос.л.1дження згаданих задач немае. В1дсутн1 таксж 1нструментальн1 засоби часового акал1зу програм для керуючих систем (КС) э часозими обмеженняш

3 розЕитком pi3rax складник технхчних систем рхзко збхль-шуеться попит на згаданий 1нструментар1Я i одночасно п1двищуеться його лог!чна та структурна складн1сть. Основы! зусилля в розрсбц! даного напрямку мокна зосередити на розвитку функц!снальних можливостей систем конкретних галузей застосувань, проте программе забезпечення автоматизац11 даного процесу може стати непридатним при 3MiHi часових вимог. Тому необх1дне ц1л1сне досл1дження проб-леми з урахуванням реальних характеристик обчислсвальних систем та математичного забезпечення, яке при цьому використозуеть^я.

Актуальн1сть п1дтверджусться також тим, що дисертацгПн! досл1дження проведен! в межах НДР "Горизонт" та "Електро-ыережа-УН", як1 виконуються 1нститутом к1беркетики 1мен1 В.М. Глушкова АН Укра1ни за тематичним планом

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

Поставлена мета вимагае розв'яэку ряду основних задач:

1. Разробка моде л i автоматично! адаптацП КС до жорстких часових обмекень.

2. 0птим1зац1я розпод1лу часових pecypciB Mix фуккадональнимн блоками системи.

3. Разробка метсдлв, алгоритьив та гнструментальних эасоб!в

- г -

часового анал1зу програших комплексов.

Досягнеяня поставлено! мети породжуе кеобх1дн!сть розв 'ягзку ряду 1н!И1Х <31льш часткозих задач.

Наумова новизна проведение досл1джень та отриманих результате полягае у такому.

Впершо досл!дяека алгоритмачна схема адалтацП КС до часових обмежень, то задашься; отримако сп1вв!дношення точност1 до часу обчислень у таких системах.

Эапропонована методика рац!сналького використання алгоритм!в та засо01в часового аиал1эу програм у поеднанн1 з квал1ф:1кацШгами функц!ями МзкнеУ'1.

Запропснован1 модель та алгоритма побудови ана;цтич;шх часових вираз1в лосл!довних.та паралелъних Ада-програм.

Методика досл1джонь. Методами прикладно! 1нфсрматики, на яких в основному Грунтуються дсслХджэкня в ц!й робот!, е часовий анал1з ярограы та систем, а основннй матоматкчний апарат досл1д7.ення -теор!я оптимальиих керувань.

Практична Ц1кн1сть. Ка основ! розроблених у дисертацИ моделей 1 метод1в автором створено 1нструмэнтальний програмний•комл-лекс для побудови часових формул Ада-програм, яки** досить просто вклвчасться в пакета прикладных програм.

Результата дано! роботи модуть бути використан! при проекту ванн 1 програмного забезпечэння крйтичних систем, а отриман1 за-леуност! точиост! в!д часу обчислень та кроку стробування дозволять оптимально вибрати необх1дн! метод та характеристики.

Апробац1я роботн. ' Голоен! положения дисертацх?но1 роботи допов!далися та обгогорсваляся нз 1-й Всесоизнхй кокферешШ "Проблемы создания суперЭВМ, суперсистем и эффективность иу применения" Шнськ, 1987); ка 1-й Всесоюзна науково~техн1чн1й конферешЦI "Мэтодц анализа надежности программного обеспечения вычислительных систем реального.времени на основе моделей нечеткой . логики и качественных описаний" (Ки1в, 1937); на 2-й Всесоюзна науково-техн1чн1й кокференц1I "Практлчеокое применение современных технологий программирования, пакетов прикладных программ в вычислительных системах и сетях ЭВМ" (ДьЧпрспетровськ, 1990); на конференцП "Математические и программные методы проектирования : информационных и управляющих систем" (Пенза. 1590); на Республ!-кансыай иауково-техп1чн18 ' конференцП ■ "Функционально ориентиро-'. ванные акчислктелькы системы" (Ллуита, ¡090), на Всесовзноку

науково-техн1чному семьнар! "Программное обеспечение СМ ЭВМ" (Москва, 1990); на кснференцП "Радиофизическая информатика" (Москва, 1990); на 5-й Всесогшйй парад! "Надежность, живучесть и безопасность автоматизированных комплексен" (Москва, 1991); на Всесоюзному сем1нар1 "Программное обеспеченно новых информационных технологий"' (Твер, 1091); на 3-му Всесоюзному ое?пкар1 "Качество ПО" (Дагомис, 1991); на сек!парах Науково! ради АН Украйш з прбблеми "К1бернетикй" 'Институт клбернетики 1м. В. М. Глушкова АН Укра1ни, 1986-1993).

ПусМкзцП. Голсбнл результата диоертацИно! роботи опубл!ко-ван1 в 14 роботах. Кр1м того, з суы1жних питань подукузач мае 4 кауков1 роботи. Злачна частика результатов увШшла до зв1т1в-НДР, як1 виконуе 1нститут к1беркетики и' В. М. Глушкова АН Укра1ни.

Структура 1 об'ем робсти. Дисертац1я складаеться 1з вступу, чотирьох роздШв, виснозк1в, списку л1тератури (30 дгерел) та дсдатку. За обсягом робота складас 124 стор1нки, включавчи 14 рисунков, 3 таблиц!.

ЗМ1СТ ЛИСЕРТАЦ1ЙК01 РОБОТИ

У вступ1 обГрунтовусться актуальн1сть проблема створення сис-. тем, як1 автоматично адаптуються до ресурсних обмекень, обговорв-еться специфика таких систем. Характеризуемся наукова новизна та практична ц1нн!сть отриманих результате, сбгрунтовуеться необ-х!дн!сть використання математичких метод!в та метод1в прикладно! 1нформатшш.

Пераий розд1л присвячеяий опису 1 ютематичному обгрунту-ванню модел1 КС. то автоматично адаптуеться до коротких чгсових обмекень. Розд1л носить ' загалъний для вс1е! роботи характер, досл1джения в наступних розд!лах грунтуються на отриманих тут математичких залехностях та оценках.

У п1дрозд1л1 1.1 для проектування систем з коротким? обмежен-нями реального часу пропонуеться використовувати багатоверс1йний п!дх1д, який полягае в розм!щенн1 у тал! КС велико! кгльксст! аль-тернативних складсвих елемент1в з р!зкими показниками. Обгрунтову-ються переваги вибраного пхдходу для розв'язання поставлено! задачу моализост1 його реал1зацП та склад хнструментальних засосИв.

У п1дроздШ 1.2 анал1зусться та викладасться критерп розпод1лу 1нформа1айних ресурс!з. На основ1 1х анал1зу пропо-нуються алгоритми прийняття ршень про розподхл часових рееурс1в.

- А- -

Шдроздгл 1.3 Бюгсчае уьесь спектр пктань, пов'яз&чих з опти-м1эац1сп розподЬту часових ресурсов, почкносчи В1 д математично! постановки задач! до отрицания вс:к чеобх!дннх залежностей.

Розглядачтьсл процос' обробки даних в КС, який оперативно

будуеться 1з предстэвник1в N блок-фуншЦй (див. рис. 1 ),

посл1довн1оть виконання яких в:1доца. Увгсь ланцюг обчмслень

повинен ьиконуватися за обмежений час Г . Кокна 1-та блок-функц1я

включае эаьчасно вхдоме достатньо . велико число альтернативних

процедур р1у як1 функционально виконусть одн! й т1 л onepau.il 1

в1др1зняються одна в!д олно! часом обчислекь £ та' 1х тсчн1стю

* л

и"

де I - не .ер блок-функцП у лакцвгу обчислень, ]

помер

алгоритму в блок-функ II. . 1шшши словака:, в задач! розпод!лу часових ресурс1в при вибор! "бажаних" вуеться вплив тальки значень £,, га б

процедур Р^о,^ врахо-

Ч

t¡

1

П

□V

« •

• О 'иски) ^Нт < N)

Ркс. 1

При Б1цом1'Х значениях I 1 о^ (1-1 .Н, ] ~ 1,п»(Н)) необ-хшго побудувати такий ланцюг обчислекь р о, —► р ,о —>...

1j <1 > rгJ <а )

— РНл°(М)> '1° схяадаеться 1э иредстав1шю'.в N о'лок-функц!й, сумаряий час виконаняя якого не перевищув Т . При цьому 1з коасно! олок-фуикцП обоь'лзкор.о вибираеться одна 1 ?1льки одна 1з допустимих альтернативних процедур р о. 1з даох ланцвгХв обчис-лень б1льш висохий приоритет мае той, який забезпечус сНльш точний кгнцеьий результат.

У п1лрозд!л1 1,5.1 задача розпо/илу часових ресурсов сведена до задэч1 оптимального квруьаккя.

Я^ма 1,1 покб-зуе, яким чином задачу розлоддлу часових ресурс у системах а жорсткиж "сх^о-и-нями йога:-. задждй ввости до зчлач! опт.'мальпсго юруьанк.«: з форьа:

м1н1м1зуватй

Д(Ю . (1)

при обмеженнях _

Г(К*1) = ТСЮ + К6Ш), к = О.Й: Л(Л+1) = Д(Л> + <5Ш.

ГСО) = 0. ДСО) = 0; (2)

6(к) е к «'<МНГ; (3)

ГСЮ < Г , (4)

о

да <5(Ю е ИСЮ - скалярна дискретна зм!нна значень похибки обчис-лень альтернативних процедур на к-му кроЩ;

исм = { 6. Л = 0~1;

к+1 ,1 к+« ,т(к+1 > 1С_1 .

ДСЮ - З1лнна стану похибки обчислень на к-иу кроц1:

^бСЮ) - дискретна зм!нна значень часу виконання альтернативних процедур у к-й блок-функц!!; к(

ГСМ) - змшга стан1в часу на к-му крсшД'. Г(Ю = ^ 1(5(0).

У п!дрозд1л1 1.3.2 для розв'язку задач! оптимального розпо-д!лу часових ресурс!в застосовусться метод "стробування" фазог >го простору. В!н Грунтуеться на дискретизацП фазово! координати точност! результата Д з кроком Н. На кояному кроц! !з ус.!х стан!в, цо потрапляпть до зони розгляду Ь, вибираеться тЬтьки один.

При розв'язанн! задач! розподьчу часових ресурс:в з викорио-таняям методу "стробування" одна !з ключовнх задач полягае у вибор! кроку квантування Л залежно в!д точност! обчислень, яка за-даеться користувачем. Розв'язок ц!с! задач! грунтуеться на теорем! 1.1.

Теорема 1.1. Для забезпечення нескМдно! точност! г. розв'язку задач! розпод!лу часових ресурс!в эа'фушнЦев мети (1) крок квантування за точности досять взяти рхвним Ь - с/н.

При дсюягненн! необх1дно! точност! за фушпиею мети (1) час, отримаяий на остаиньому кроц! за методом "стробування", мож-з в!др!знятися в1д оптимального на величину, яка ке задовольняс користувача. Тому в робот: отримаиа така оц!нка.

Теорена 1.2. Сума розпод!лених часових ресурс!в Л1) в1дхиляетьсл в1д абсолютно оптимального значения часу Г(Ю ка величину, яка не перебхльшув 1е; IТЛЮ - ГШ1 < 1с,

де L - максимальна !з констант Л!пшиця функц1й Кб(к)).

м = о Т^Т.

Висиовок. Для отрицания П0Тр1бК01 ТСЧКООТ! с розв'язку задач! 1.3 за функц1ею ие'ги (1) фазове обыеження (4) повинна при в1дс!ванн1 недопустимих вар1антав ыати вигляд

Т(Ю < Г + 1с.

£ ° При цьому И = -|т-.

Теорема 1.3. Для забезпечення потр1<Зио! точности с

розв'язку задач! за функцасо мети (1) та потр!бно! точност!

с1 уловлсвання фазового обмеження Т(Н) < Т' крок квантування за

точн!стю досить взяти р1вним Л =-^-

3 метоп мокливост! оц!нки ззаженсго суыарного критер!р з урахуванням порушешш фазових обмежень пропонуеться застосувати метод итрафних функц!й.

У п1дрозд1п1 1.3.3 розглядасться при попередп!х обдаяеннях (2), (3) нова функц1я мети вигляду

&1Ю - д сю , '

«(« « МЮ + --- /(тш - -о), (5)

де не диференц!йована функцхя f{j{N) - Г ) =

О, якцо T(N)-T < О

о

T(N)-T у протилея-Ä ° ному випадку,

Л (Ю - значения функцП мети (1) для допустимого розв'язку задач1 (1) - (4), AratnW - оц1нка знмзу мШмуму функцП (i) при в1дсутност1 обмеження (4); с - точность викснання обмеження (4). Значения Д*(//) i Д (ti) находиться таким чином:

к. mln »J

N-l Я-1

Д*Ш - ) may . <5, , Д (Ю = У in in 6 .

ISJÍ.U<1> íj min / . Iijiuim tj

Оптимальний розв'язок задач! (2), (3). (4) ^означаемо $ (//),

i

Дс (W), а отримане при цьому с ума р не значения часу - Г (//). < i Мають Micue так! твердхекня.

Теорема 1.4. Отриманий оптимальний розв'язок задач! (2), (3), (5) не r.ipiue за фушшею мети розв'язку початково! задач! (2) ■■ (4), tocto i". (W) < ДШ, а фазове обмекекня (4) буде

виконано э точности до с , тобто Т. (N) - Tq i е^.

■

Теорема 1.3. Якад в розв'язку задач! задана ц1на К одиницД простроченого чаоу, то оптимально кроки квантування за фазовими ЗМ1НКИМИ Л(М) 1 П&). к = О, е е1длов1дно

лд = нт ' ТОГ ' (s)

Бисноаок 1. Похибка с задовольняння HepisnocTi Г(М) < Го

A*(N) - Amln(W) при цьому сц! меться так: - -$——-.

Висновок 2. Д1апазонами фазових зм1вних йота, взят/

Дд«А*(Ю.

Автоматична адаптац1я КС до зорстких часових обмехень передбачаз наявн1сть засоб1в автоматизацП часогого анал1'у дов!льних програм, як! написан1 мовами високого р1вня. Тому в другому роздШ досл1джуються питания, пов'язан! з часоЕими характеристиками програм.

У п1дрозд1и1 2.1 узагальнветься досв1д визначення часових характеристик 1 властивостей програм, вивчасться ьохлив!сть та досл1дхуоться Шдходи до автоматизацП часового анализу програм. Формусться систематизована ыэтодолог1я отримання часових характеристик програм з мотов автоматизацП розпод1лу часового ресурсу м1а блок-функи1ями при горстких обыекеннях.

У п1дрозд1<11 2.1.1 проведено анал1з в1домих метод1в та автоматизованих засо<31в прогкозування часових характеристик виконання програм. Анал1зупться системи METRIC, OFAii, АСЕ, АГ-GUS, SDS, SADAT, що М1стять ззсоби опису чассво! повед1нки програм.

1снують два шляхи часового анал1зу програм - експерименталь-ний i аяал1тичний. Експериментальний анализ полягае у nporoni програм на ЕСМ з р1зними допустамими наборами вх!дних даннх i встановленн1 контрольних точок Счасово! рсзмИки) часу И виконання. Анал1тичний п1дх1д можна под1лити на дв1 категорП: м1кроанал!з i макроанализ.

При пор1вкянн1 метод!в макро- i микроанализу програм, в1дм1-чаеться, цо м!кроанал1з забезпечуе Лльш точний часовий прогноз, Hii макроанализ. Какроанал1з дзе Т)лькн залеюисть Спсрлдок росту) часу виконання в1д об'ему вхиних даних. а м1кроанал1з дозьоляе отримати числсв1 значения часу виконання програм у пиглдд1 параметр! в: максимального, м!н1мального, середнього часу виконання

- с -

г.рограми та середньоквадратичного в!дхилекня в1д середньо! величи-ни. Причому на першему етап! аная1зу при побудов! часових формул межна не враховувати об'ем вх1двих даних 1 тиг» ЕОМ, на як!й буде викснуваткся програма. 'до *л!ддаеться анал!зу. 1 т1льки на другому етап! часов! зм!нн! пов'язуються о д!йсними числовими величинами.

Автоматиза1Ця м!кроанал!зу з отриманням ус!х чотирьох часових характеристик в грок!здкоя ! часто не може бути реал!зованоп, тому ш.о обчислення середнього значения часу виконання програм 1 середньокьадратичкого вЦхилекня ь!д середньо! величина зимагавть знания функцИ "типового" розпод!лу вх!дних даних ! обчислення в!дпов!дних 1мов'рних значень. До того г иездалий виб!р розшшлу мохе суттево викривити результат аиал!зу.

У зв'язку з вищевикладеним реалхэаидл часового анал!зу . вдавалася т!лыси для простих посл!довних програм. На программ, як! анал!зузалися, накладалося ряд обиехень в!дноско форьш зобрашаня 1 структур"»! програм. 1снусч! походи. до реал!зацП систем часового анал!зу програм передбачакть участь спец!ал!ота (крапе всього автора програми), який добре анае програмн! ¡додул!, бо йэыу несбх1дно задавати множину параметр!в блоков програш, . 1к взаемозв'яэки; !ыов1риост! виконання г!лок програм? ! т.п. Яя!сть отриманих оц1нок розрахунку часу виконання програм пролорц!йно и а ле жить в!д компетвнт1."эст1 спец!ал1ста." .

У п!дроздШ 2.1.2 автор вкходячи з результат!в досл1дкекня у галуз! часоеого анал!зу програм пропонуе шляхи подальшого розвитку метод 1 в прогнозуванк.т часу виконання преграшшх систем та стЕорення на Ух основ! часових алгоритмов для роботи у системах з короткими часозими обмег^ннямп. Обмеаеае використання у таких системах в! доки х метод!в та автоматизованих засоб!а прогнозувакна часовиу характеристик ьиконакпл програм пояснссться тим, то до тепер!шиього часу не ьир!шэко ряд проблем, оокрема пов'яоаних з розрахункоы часу функц1онування програмних систем, як! ихстять як . 4посл1дсвно, так ! паралеяьно викснуван! мо.\ул!. До програм з 'паралельними процесата ставляться виыоги, пов 'язак! з прогнозу-ванням часу виконання не тьчыси 1х фушоЦональних компонент, але й процес!в синхрон!зад!1 та сбм!ну !н$ормац!св. У зз'язку з циы влникла необх1дк!сть аналогу оператор!в 1 алгоритма, як!ысли-чають оемафори, рандеву, эасойч блокування, передачу по»1домленъ. Для доопть шгрокого ксла застосурзнь, вклочдючи КС з жорсткими

часовикш обмеженнями, необхШо розробити эасеби для формального опису часово! повед1нки програмних систем, "напксаних мсвами високого р!вня, 1 побудови часових формул 1х зиконання.

У п1дрозд1л! 2.2 описана сиотематжювана методолог!л отримзн-ня часових характеристик програм, запропоновак! алгоритмы побудови часозих формул програм, написания мовси високого р1вня. В основу розроблених алгоритм!в покладено лоеднання метод!в часового мхкро-анал!зу по визиачешт граиичних часових зкачень викокання програм 1 формальних мэтод!в анал!зу поведхнки систем реального часу, як! використсвувть квал!ф1кац!йн! фуккцП Макнейки. Для зручкого зобрахэння часу викоиання оператора 5 та псв'язааих з ним пегет-ворень вектора зм!шйзх X программ вводиться форкалъний нехан!зм, яхиЯ Груитусться па трансфор>лац!йних I часових функц!ях -спец!альноыу вигляд! квал!ф1кац1йних йупкийй. Часова футсаЗл визначаеться таким чином.

Озпачошга. Нехай 5 - оператор программ, / - скХнченна множила, X - вектор змХвних до виконания оператора 5. Тод! 7(5: X) -часова функц!я виконания оператора 5 з вх!дними змшнимя Х-

Г(*Х) - {(В|. П5<:Х))}^.

де - мнохина лог1чнизс умов, як1 визначапть наступи! г!гт у

граф! виконання складного оператора 5 (рис.2), Г(5,:Х) часова функц!я, пов'язана з виконанням оператора е 5.

Спос!б о счисления Г(.$:Х') для отрямання результату 5*(Б ;-Х)

задаться формулою X) = ) У^:*).

54г1ггииа

де Т'с:X) г Г(5{:Х), якщо 7(5 " арифмегичний вираз.

Рис.2. Граф зиконання окладного оператора 5

У гидроздШ 2.2.1 запропонован! метода визначення часу виконання посл!довних програм. Описана побудова часових функц1й i граничних значень часу виконання лШйно! програии, яка Mi стать оператори присвосвання, виклккя процедур, а таков програми, що м1стять типов! yuoBHi оператори {if, case), оператори цикл1в (for, while). Як приклад наведено побудову часово! функцП умовкого оператора if з припущенням, що ,..., S^ - прост1 оператори. X - вектор зм1нних:

S 2 if 8 then S (X); tf i t

elsi/ 8 then S (X);

n n

elsif S (X); endif;

Тод! r(S.f:X) = |(1стина, Г(£ ) VTCelst/))] U ^, T(S :X>), (-iS , r(.Su) + T(elsif)), r(Sa:X)),

(-Й , T(S ) + T(elsif)), .. , (-& .. л-тВ . ICS :X))],

\ t 2 S / \ t П П*» /J

до Heist/.) - накладн! часоь1 витратм, пов'язан1 а пароходам: всоредин.1 оператора, 7(5^) - часова футоЦя для обчисленпя та переварки булево! умови .

При нШмалыюму об'еыг 1нформацП про BxiflHi дан1, контекст программ, коып1лятор, вереin машинного часу не завхди мохливо anpiopi визначкти час виконання програми S. Проте ыожна отрнмати граничн! значения часу 1! виконання: I (S) i t (S). У цьому

[-1 mm max

I (S), I (S) . rpamrai часоЫ значения при

mm max j r

виконанн! умовних операторов знаходяться таким чином:

п

Tk(Su) = T(SJ + * Heist/) + . [t . tk ].

«г> » г

То T(sif) = n « T(elsif) ♦ ¿>(*t)). ^'(t^)].

це T(e 1st/) - граничнi значения часу, пов'язат з переходами в оператора

У niflf»o3flidi 2.2.2 запропонован! методи отриманил оц1нок часу ьикснанкя паралельних обчкелень. Проведений часовий анал1з

оператор!в обл1ку часу, оператор!в затримки delay, пер1одичиих процес!в. Розглядасться способи отримання граничних значекь часу встановлення рандеву для паралельних лрсцео!в.

Трет!й розд!л присвячений i нструкентальним засобам та моделям часового прогнозу робота програнких систем.

У п1дрозд!л1 3.1 запропонована структура шструменталышх засоб1в (див. рис. 3), яка розробяена з урахуванням принципу розыежування процесу побудови часових формул програы i отримання часових ouíiiok Ix виконання. 1нструментальн! зассби забезпечувть для дов1 лыю взято! програмно! систеки, написано! mobcd високого р!впя типу Ада, автокатичну генерац!п в1дпов!етих !й часових формул. Taita генеращя грунтуеться на aaanisi графа керування i застосування розглянутих у 2-му роздал! алгоритм1в часового аиал!зу програм, П!сля вводу i акал!зу вх!дних даних визначаоться оц1нки часу роботн дано! програшю! системи, вклвчавчи модул!, як! м1стяться у Hifl, ! вядасться в1дпоп!д1г1 часов! значения.

1нтерфейс ксристувача

Вих!дн! дан!

програш

Список

базових

операц!й

Процесор анал!тнчних

вираз1ь ¡5

Г

Анал!затор потоку данях л. и £

f

Генератор часових А CJ

формул & о

Т ДЕ

Побудовник графа

керування

ПрограюшЯ вир!б, •«—написаний

mobod

эисокого

р1вня

Рис. 3. Структура програшгах засоб!в часового прогнозу виконання програм

У п^роздШ 3.2 пропонуються модель та "спадний." алгоритм "оберненого проектування" для отримання прямо !з тексту програми його структурного графа, який розп!знас модул! програми ! показуе 1х керусч1 взаемодП.

Алгоритм побудови структурного графа е !терац!йним. Для колено! 1терац!1 будуеться !тера;ийна множина (q¡,...,

де

i ~ номер 1терац.П, Qt,..., Qk - tcoplHHi иодул!. Ha nepaiift iTepauil KopiKHHMM програмнкми модулями e кошплююч! модул!, як! ыохуть бути або процедурою бея параметр!в або пакетом.

Модель MI програми на 1-й iTepauil окресльеться такими значениями (st, Q, Нй(, ИТ1', f , /ЕТ), дей- множина програмних ыодул1в, як! osracaHi у программ HQ1 - множина !мен програмних модул!в, aKi викликавться кор1нними модулями на t-й iTepau! I; НТ1, - множима активних задач, як! описан! у кордному модул!: /MQ - функция, яка воображая кокний кор!нний програмний модуль Ha.i-й iTepauil у множину MQi; / - функц!я, яка Bicoöpa-хае козший пакет q ^ е Q у множину описаних у ньому вход!в EV; /Ет~ Функция, яка BiÄoopaias кожну задачу q е Q у Шохину описания в хй вход is. Ml можна предстаяити графом G(W7) = (W, А), де К - мнозмка вузл1в, N = {S U Ш4 и ИГ*>; А - множина bcix иеипших пар ребер (Ч^). % е Si 1 fj 6 ) ado

e!/Evk) ado ъ е/ытк)-

Пронес эакгнчуеться тод!, коли для ес!х кор!нних програмних

модул!в k-l iTepauil множина Mit пуста, тобто годен кор!нний програмний модуль не мостить у codi виклик!в iimiux програмних модул1в.

У п!дроздШ 3.3 описано генератор часових формул, що приз-начекий для нобудови часових формул для кожного фунюЦонального блоку КС. Б результат! анал1зу графа керуьання генератор виэначае nporpaMHi засоби для побудови часових формул складних ыовних конструкций та посл!довно ! паралельно виконуваних програмних модул!в.

Для анал!зу тексту програми пропонуеться "висхадний" алгоритм побудови часаьих формул. Якцс побудова структурного графа програми, яка аиал!зуеться, зак!нчилась на к-иу Kpoui, то розглядает-ься !терац!йна множина = { q^,..., q^ }. 1з тексту програми поел! доено вибираються програмиi модул! q ...., q i для кожного ia них будуються часов! формули у в!дпов1дност! з алгоритмами .часового а»ал!зу. .При цьому . програмним блокам "begin ... encl;" i складням операторам мови присвоюються порядков! •номери, як! дозволять згодом при HeodxiflHOCTi звертатися до кожного is них за i м' ям програмного модуля ! в!дпов!дним номером для моделсванпя ix часовох повел;ики. Таким чином Еиконуича частика косного 1-го, т.. програмкого модуля перег.нсуетьсл у вигля-

д! часових формул i залам'ятовуеться як процедура з в1дпоь!дкш 1м'ям i вх!дними параметрами. Кохиий програкний модуль такса метить 1нформац1ю про 3MiHHi, 1:с тип i зону дП, а також список блокiв i складних програмних конструкций.

На наступному (й-1)-му Kpoui рэзгяядаються 1терац1Яна множина Sfc i = ,... , qfn> i фушаЦя / . Так само як i на попередньому кроц!, будувться часов! формула для кожного программного модуля ijt е S , i = 1,п. Якщо програмнай модуль q{ е f м1стить виклик програмного модуля q е Sk, виклккавться проце-дури отркмання часоьо! формули q^, у яке! форма лыи параметры зам1нюютъся на фактичн!. Таким чином. з!дбувазться побудова ча'ових формул, починапчи з k-ro i эак1нчуючи 1-м «сроком, ка. якому отри-муемо часову формулу для BcisI програми.

У п1дрозд1л! 3.4 описано процесор анал1тичних вираз1в, який дозволяе на ochobI вку1дних данях генератора часових формул i вх!дних даних анал1зуючо! программ (блок-функцИ) отримуваги оц!нку часу ii роботи у вигляд! числовых значень чи граф!к!в.

Анал1затср потоку даних у в1дпов1дност1. is списком задних эм1нних программ дозволяе процесору обчислити час T(S;X) виконан-ня програми 5 ■ з вектором вх!дни.ч зм!нних X аба оцхнку часу T(S) = It , t , якщо sifiOMi д1апазони змпш вх1дких даних.

L И In n&xJ

Ц1 оц1нкп nisHimo використозуотьея при розпод1л1. часу .miя блок-функцХями КС. Часов! характеристики picwnx алгоритм^ обрубки даних залекать мд типу даних, як1 обробляються. Час обробки даних динамхчних пронесi з мохе суттево аалеяати в!д одного параметра, який в подаяьшому казиватамемо голозним, наприклад з1д к!лъкост1 об'ект1в обрсбки, в1д обмеженого числа типJ в об'ект'в оброблр, po3MipnocTi обчислпзальких сперац!й. У такому випа.пку при заданому

взноситься до гшонтоьаних систем зняття i обрсбки 1нфсрмацН з апарэтури i «рийняття ке-руючкх piuient.

У четвертому т)озг.1л1 розгллнут! пктачня peajii3<iiui затрачено-

у pjriori э"орг;<:в 1:обу;.-,ог>и v-coiinx 'формул Ада ирогрэм ;

промодельовано процес розпод!лу часових ресурс1в Mix фушаЦональ-зшки блоками системи.

Л ля автоматичного отримання часових формул Ада-програм у середовищ! PORLAND PASCAL реализовано !нструменталышй комплекс. що являе собою наб1р програм для отримання граничних значень часу виконання' i побудови часових функц!й програм. Розроблений комплекс досить просто шже вклочатися в пакета пршгладних програм, тону що е реентерабельном. Ка вхи повинен подаваглся файл а текстом програми, ка виход! видаеться результат у випгяд1 файлу часових формул, який моле в подалыиому використовуватися будь-яким чином. Поб/дова часових формул зд!8снссться на ochobI тексту програми i списку базоЕИХ олерацШ.

Биклэдено процес отримання граничних значень часу виконання програм. Описан! питания використання розробленого !нструменталь-ногс комплексу за допоксгоп програмного посэредника 77 НЕ J'.

У п1драэд1л1 4,1 на приклад1 програмно! системи, що визначае час ьиробництва готових вироб!в i3 napTii заготовок, показано процес отримання чассвих формул. При цьому використовуються "спадний" аягоритм отримання структурного графа програмно! системи i "вис-х1дний" алгоритм побудови часових формул систеш на основ! розглянутих вище 3acodin часового анал!зу програм.

У niflpcoflini 4.2 на приклад! промодельована робота алгоритму розпод1лу часу м!ж функц!ональними блоками системи.

Результати моделювання п!дтвердили правильность теоретично отриманих у робот! оц1нок результате обчислень за точн!стю i отримання найкращого !з можлквих розпод!л:в часового ресурсу.

У висновку наведен! головн1 результати робота.

У додатку подан! тексти програм, результати експеримент1в i мсде/гсвакня та документи про Еикористання резуньтат!в дисерта-Ц1йно! робсти.

ГОЛОВН1 РЕЗУЛЬТАТИ РОБОТИ

1. Розроблека алгоритм!чна схема адаптаци керуючих систем до часових обмекеаь, як1 задаться ззовн1. Запропонована схема грунтуеться нз багатоверс1йн!й архитектур! системи та на можлиьост! оперативного вибору в1дпов!дних .альтернативних програ^них одиииць з крааими is можлиаих показник1в точност1 залежно в!д часу, ш.о ьис!пяеться користувачем.

2. Запропоновано п!дх1д до розв'язку задач! розпсд1лу -гасових pecypciB м!ж функц 1 онаяьними блоками системи як дискретно! задач] оптимального керувания. При аьому всгаковлено крок квантуракнл

иЛп { -f-, s }

фазового простору h = -j,--та с'Лнка в!дхилення

розпод1леного часу*; Г( Ю з!д задано го значения Г :• |Г(/0 - Г I < Le, де N - к!лыисть функцоопаяьних блоков у лакцсгу

о

ибчислень; е - допустима похибка уловлюваняя сумарно! точности обчислен:.; в - точн1сть виконання фазового обмеяоння Г(М) ь Т ;

1 о

L ~ максимальна is констант Л1гшиця функцой часу виконання альтер-йатлвних процедур t(ô(k}), к = ОРГ. При заданий uîhî 5 одиншп простроченого- часу папропоновгно застосовувати метод втрафних функШЙ ! встановити кроки квантування фазових зм1нних

h я ~Ж • \ * ■

3. Проведений анал!з в1дс!.гах методов прох'нсзування часовня характеристик виконання програм показав 1х обмехене яастосувакня у системах з короткими часовими обмежекнями. £апропонован1 методика та алгоритма рац!онального використання ы>?тод!в, яка посднуе застссування к^ал1ф1кац1йних фунгаШ Макпейм1 з апаратсм часового анал!зу. Описан! уыови та широкий клас задач, для якаго мохтиве застосування методики.

4. Розроблвн1 "спадиий" алгоритм отримання 1з' тексту программ И структурного графа, який зизначае программ! модул)' та показуе 1х керупч! взаемодП, i "висх1дний" алгоритм .цобудоьи часових формул програм.

- 5. Розроблен! алгоритм!«. часово! сц!шси посл!довних i парале-льних прбграм, написании мовани аисокого р1ьия. Запоопоковян! методи побудови часовни формул програм.

6. Розроблен! модель генератора чао.ових формул та модель процесора аналотичних вкразов, як1 забезнэчують отримання чаеових характеристик програм, иаписаних швами висского р1вкя.

7. На основ! отриманих результатов у середовипЦ BORLAND PASCAL на IBM PC реал!зова!ю 1нструментальний програмний комплекс

для. побудови чаеових формул Ада-програм.

* # *

Гсловн! положения дисертацП опухло кован! в таких роботах:

.1. Чнчиапь И. С., Сп?сителева С. А. О прогнозе работоспособности ЭВМ на заданное р;:емя: вперед // Проблемы создания супер-ЭБМ.

супер-систем и эффективность их применения: Тез. докл. 1-й В^сосз. конф. - Минск: ИМ АН БССР. - 1987. - 4.2. - С. 198-199.

2. Чичкань И. В., Спасителеьа С.А. Оценка качества функционирования программного обеспечения в условиях временных ограничений // Методы анализа надежности программного обеспечения вычислительных систем реального времени на основе моделей нечеткой логики и качественных описаний: Тез. докл. 1-й Всесоюз. науч.-техн. конф.

- Киев: КНИГА, 1987. - С. 73.

"3. Спасителева С. А. , Чичкань И. В. Разработка систем моделирования внешней обстановки и критерии эффективности работы комплекса // Исследование зопросоБ оперативного управления комплексом и взаимодействие средств комплекса в условиях противодействия.

- Киев: Ик-т кибернетики им. 3.М.Глушккова АН УССР. - 1988.

- С. 48-79.

4. Спасителева С.А., Чичкань И. В. Обработка особых ситуаций в реальном масштабе времени // Практическое применение современных технологий программирования, пакетов прикладных программ в вычислительных системах и сетях ■ ЭВМ: Тез. докл. 2-й Всесоюз. науч.-техк. конф. - Днепропетровск: НПО "Орбита", 1990. - С. 20-22.

Б. Спасителева С. А. , Чичкань И.В. Средства оценки по времени выполнения . программ заданного типа // Математические и программные методы проектирования информационных и управлявших систем. -Пенза: ПДНТП, 1990. - С. 64-69.

6. Спасителева С. А., Чичкань И. В. Алгоритмы распределения времени и временного контроля в информационно-управляющих системах радиофизических комплексов /V Функционально ориентированные вычислительные системы: Тез. докл. респ. науч.-техк. конф. - Харьков: ХПИ, 1990.-Ч. 1. Теория и программные средства. - С. 123-124.

7. Спасителева С.А., Чичкань И. В. Компромиссные решения при распределенной оораоотке данных динамического процесса в условиях временных ограничений // Программное обеспечение СМ ЭВМ: Тез. докл. Боесоюз. науч.-техн. семинара. - М.: ИНЭУМ, 1990. - С. 97-98.

8. Спасителева С. А., Чичкань И.В. Оперативное планирование структур систехы обработки данных динамического процесса при ограниченном времени // Радиофизическая информатика: Тез. докл. конф. - М.: РТИ АН СССР, 1990. - С. 46-47.

9. Спасителева С. А. Критерии распределения ресурсов в системах с жесткими ьремэнными ограничениями // Практическое применение сооъемэкных технологий программирования, пакетов прикладных прог-

рамм в вычислительных системах и сетях ЭВМ: Тез. докл. 2-й Всесоюз. науч.-техн. конф. — Днепропетровск : НПО «Орбита», 1990. — С. 127

— 130.

10. Чичкань И. В., Спасителева С. А. Проблема временной адаптации автоматпзнропанных комплексов для обеспечения надежности обработки данных // Надежность, живучесть и безопасность автоматизированных комплексов: Тез. докл. V Всесоюз. совещ. — М. : ИПУ АН СССР, 1991.

— С. 69—71.

11. Чичкань И. В., Спасителева С. А. Инструментальные средства для автоматической адаптации сложных систем к жестким временным ограничениям // Программное обеспечение новых информационных технологий: Тез. докл. Всесоюз. семинара. — Тверь : НТО «Центрпрограмм-спстем», 1991. — С. 165—166.

12. Спасителева С. А. Методы прогнозирования времени вычислений в инструментальном комплексе Технопоос-Т // Качество ПО: Тр. Всесоюз. семинара. — М. : СНПО «Алгоритм», 1991. — С. 38—41..

13. Чичкань И. В., Спасителева С. А. Автоматическая адаптация информационно-управляющих систем к жестким временным ограничениям // УСиМ. — 1992. — №7/8. -- С. 41—49.

14. Чичкань И. В., Спасителева С. А. Программно-технические средства для ввода информации из УПДМЛ в графопостроитель // УСиМ. — 1987. — Л«3. — С. 118—121.

ГПдп. до друку 10.06.93. Формат 60X84/10. Патр друк. Л!> 2. Офс. друк. Ум. друк. арк. 0,93. Ум. фарбо-вЦб. 1,05. Обл.-вид. арк. 1,0. Тираж 100 прим. Зам. 1018.

Редакцшно-видавипчий В|'дд1л з пол1граф1чною д1льницею 1нстнтуту кибернетики ¡меш В. М. Глушкова АН УкраГнн 252207 Ки1в 207, проспект Академп<а Глушкова, 40