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

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

ГОРШКОВ СЕРГЕЙ ЛЕОНИДОВИЧ

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

05.13.11.- Математическое и программное

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

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

МОСКВА 1946

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

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

профессор |ВА)1РАДЯН A.C. |

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

старший научный сотрудник

ЯИЦКОВ A.C.

- кандидат технических наук, доцент ЖИРОВ В.Ф.

Ведущая организация: Институт космических исследований

РАН, г. Москва Зашита диссертаци состоится " /О 1996 года

в аудитории в час. мин. на заседании

диссертационного совета Д053.03.04 в МИФИ по адресу:

115409, Москва, Каширское шоссе, д.31, тел 324-84-98: 323-91-67

С диссертацией мохно ознакомиться в библиотеке МИФИ. Автореферат разослан 1996 г.

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

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

д.т.н., профессор , В.Э.Вольфенгаген

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

Актуальность темы.

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

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

Одним из важнейших классов ошибок в программах для МСРВ является потенциальная возможность возникновения тупиков (deadlocks), т.е. ситуаций, в которых несколько параллельных процессов могут взаимно блокировать выполнение друг друга.

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

такхе методов и моделей этого анализа является актуальной.

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

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

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

Основными задачами. решаемыми .в работе, являются:

- формализация и обобщение понятия тупиков в параллельных ■ программах для МСРВ;

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

- разработка математического аппарата модифицированных сетей Петри (МСП), являющегося новым обобщением сетей Петри, предназначенного для автоматической проверки исходных кодов программ МСРВ на

отсутствне тупиков:

- разработка методов построения МСП, соответствующей исходному коду программы на языке Оккам-М;

- разработка методов анализа модифицированных сетей Петри на

UnitUIIU«

- разработка и реализация комплекса программ, предназначенного для разработки программ на языке Оккам-М и анализа тупиков в исходных кодах этих программ.

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

Научная новизна

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

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

Практическая значимость работы

Разработана и реалнзопапа на ПЭВМ типа IBM PC XT/AT система АТОККЛМ, предназначенная для автоматической проверки отсутствия тупиков в программах на языке Оккам-М.

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

методов.

Реализация результатов исследования Исследования проводились в рамках ряда научно-исследовательских работ по изучению архитектуры и программного обеспечения параллельных вычислительных систем, выполняемых на кафедре 29 МИФИ. Версии разработанной системы были внедрены на предприятиях НИИ Авиационного Оборудованияг.Жуковский, и НИИ Многопроцессорных Вычислительных Систем, г.Таганрог.

Апробация Отдельные результаты диссертационной работы докладывались на научно-технических семинарах "Проектирование и создание многомашинных и многопроцессорных систем реального времени" (Москва, 1990) и "Сетевая обработка информации" (Москва, 1990), на конференции "Информатика, телеобработка и персональные ■ компьютеры" (Москва, 1991), на республиканских семинарах "Математическое моделирование" (Бакуриани 1988) и "Моделирование, оптимизация и системный анализ" (Бакуриани 1989), на научных семинарах, проводимых на кафедре 29 МИФИ.

Научные публикации

По теме диссертации автор имет 10 печатных работ, результаты исследований отражены в 5 отчетах по НИР.

Структура и объем работы. Диссертация соостоит из введения, четырех глав, заключения, списка литературы и двух приложений. Общий объем работы 160 листов. Работа содержит 22 рисунка, 2 таблицы и 82 наименования библиографии.

СОДЕРЖАНИЕ РАБОТЫ

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

прермпанию от операционной системы не может считаться корректным выходом.

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

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

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

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

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

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

Утверждение. 1. Программа является завершенной тогда и только

тогда, когда ее замыкание является адекватной программой.

Введенные выше понятия позволяет сделать обобщение понятия тупиков программы (deadlock).

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

Для представления оспошшх соотношений между введенными множествами состояний программы для МСРВ введем следующие обозначения:

Р - множество достижимых состояний программы;

Р'2Р - множество достижимых состояний расширения программы;

ХЕР - множество дефектов программы;

D'SP' - множество дефектов расширения программы;

T=ZnD' - множество тупиков программы;

Очевидно, что если некоторое состояние программы является дефектом для ее расширения, то это состояние также является и дефектом для самой программы {PC\D'SD), следовательно, множество тупиков совпадает с множеством состояний программы, являющимися дефектами ее расширения ( 7ЬЛ*Ю' ).

Таким образом, справедливо следующее утверждение. Утверждение 3. Чистота программы является достаточным условием отсутствия в ней тупиков.

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

следующее утверждение:

Утверждение 3.. Задача поиска дефектов расширений произвольных программ, на основе их исходного кода на некотором языке для МСРВ. является алгоритмически разрешимой.

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

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

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

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

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

использования программистом операторов безусловного перехода goto. Именно эти, на первый взгляд не очень принципиальные модификации, и сделали возможным использование языка Оккам-М для разработки чистых программ. Дело о том, что явная комбинация операторов ветвления и безусловного перехода позволяет уже на этапе компиляции программы легко отделять передачи управления, связанные с командами ввода/вывода по каналам, от обычных передач управления, по срабатыванию пехоторого условия.

Напротив, в стандартном языке Оккам программист вынужден всегда использовать логические выражения даже в тех случаях, когда передачами управления синхронизированы охраной альтернативного процесса ALT. В результате программы на языке Окнам как правило не являются чистыми, а задача полного выделения передач управления, синхронизованных командами ввода/пвывода, становится практически неразрешимой.

Простой процесс изыка Оккам-М состоит из оператора вывода и(или) списка операторов присваивания.

Составные процессы языка Оккам-М аналогичны соответствующим процессам языка Оккам и могут быть трех типов: последовательными (seq-процесс), параллельными (раг-процесс) н процессами ветвления (i f-процесс).

seq-процесс является готовым, если готов первый процесс из списка. Выполнение последовательного процесса заключается в последовательной активизации его компонент.

if-процесс задает процесс, логика работы которого является обобщением:IF и ALT-процессов языка Оккам. Процесс ветвления является готовым, если готова хотя бы одна охрана процесса из списка процессов-компонент. Выполнение готового процесса-ветвления заключается в активизации произвольного готового

процесса-компоненты, по завершению которого завершается и процесс ветвления.

Охраны компонент if-процесса специфицируют дополнительные условия, необходимые для активизации процесса. Этими условиями могут быть операторы ввода и(или) операторы сравнения. Специальным

символом t обозначаются нулевые значения, которые все указатели получают при инициализации.

раг-процесс предопределяет независимое (в том числе и параллельное) выполнение процессов-компонент и аналогичен ГАН-процессу ипыка Оккам. Параллельный процесс всегда является готовым. Выполнение параллельного процесса заключается в одновременной активизации всех его процессов-компонент. Параллельный процесс завершается после завершения всех процессов-компонент.

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

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

Пример■

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

Ниже приведена программа на языке Оккам-М, решающая данную

задачу. Взаимодействие между процессом-производителем (producer), процессом-потребителем (consumer) осуществляется через каналы каналы dat и end. Канал.dat служит для передачи чисел, а канал end служит для передачи служебного сообщения о прекращении работы процесса производителя. После приема сообщения end потребитель также заканчивает свою работу.

type int &int // целочисленный тип int

proc producerfdst:out int,end:out) seq(1:labeI){

:l i<4

()seq{

; //вычислить данные

-dst = jf; //передать данные }!dst goto 1;

()!end; //передача сигнала о завершении программы

К-

h

proc consumer(sre:in int,end:in) seq(1: label)( :1 if{

(?src)seq{ //принять данные

; //обработка принятых данных

)goto 1;

(?end); //прием сигнала о запешении программы

);

}; _ proc main( )

pai(dat:chan int,end:chan ) (

cal 1:producer(dat,endI; //пронесс-производитель ca11:consumer(dat,end); //процесс-потребитель }; '

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

Моднфициропанная сеть Петри (МСП) - представляет собой набор:

п=(Г ,Р ,С ,pln,p0Ut,CA ,ТГ ,ТО ,ТР",ТР*,Т1С ,ТОС , л п п л п п п л л л л л

N ,N1 ,N0 ,NP ,NC ). n n n n n

1) T - множество переходов.

л

2) .F - множество позиций.

л

3) С - множество каналов.

n

4) p -входная позиция;

л

out

P -выходная позиция; n

in out

in out Обозначим Pl. =P \({p }vj{p }) n n n л

5) CA ЯС - подмножество каналов-параметров.

nn

Обозначим CL =C \CA an n

6) 77 £7" - подмножество переходов ввода.

nn

ТО - подмнижество переходов вывода, л л

На подмножества ТХ и ТО налагается условие: л п

TI ПТО =0; nn

Обозначим TL =Т \(TI UТО ) n n n n

7) TP e[T хР —>!N] - входная функция инциденции;

л л л

ТР «[ Т хР —»¡N ] - выходная функция инциденции. л n n

S) TIC efTI ]] - функция ввода; n n n

TOC e[ ТО —*C ] - функция вывода; n n n

9) N - множество подсетей, каждый элемент п. которого является

n i

МСП. Ни одна компонента набора пне имеет пересечений с соответствующими компонентами набора л;

10) tVI €(JV—>Р J - функция начала подсети;

л л л

f/O e{N —*Р J - функция завершения подсети; л л л

И) Vn .gN , NC (n ,)е[СА —»С ] - функция подстановки каналов. 1 Л Л i п. п

1

Введем также ряд дополнительных обозначений:

- Vt<=7* , t~ = {p\pcP л ТР*( t, р)>0} ;

л л л

' t=( р| реР Л rp"(t,p)>0)i л л

- VpeP , 'p=lt\teT Л г/|(,р)>0);

п л л

p* = {iji€r л тр" ( t, р)>0} ; л п

Сеть л мы будем называть элементарной, если ЛГ =0 и СХ =0.

л л

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

Для МСП можно определить преобразования развертки, конечная последовательность которых позволяет преобразовать произвольную МСП и элементарную МСП. Преобразования развертки подразделяются на два класса: преобразования развертки подсетей и преобразования развертки каналов.

Каждому процессу на языка Оккам-М мы поставим в соответствие некоторую МСП.

Простым процессам языка Оккам-М соответствуют элементарные MCII. Если простой процесс не содержит ни оператора ввода, ни

оператора вывода, ни оператора перехода, то МСП содержит три out +„

позиции р , р и р и два перехода int.

Если простой процесс содержит оператор ввода, то МСП

дополнительно имеет канал с', такой, что TI (Г') = с'.

л

Если простой процесс содержит оператор вывода, то МСП

дополнительно имеет канал с", такой, что ТО (£")=с".

п

Если простой процесс содержит оператор goto, то дополнительно

вводятся позиция pg, переход и канал с^, такие, что: ТО =

, п

' tg={pS). tB' =0. .

МСП, соответствующая последовательному процессу, состоящему

из к компонент содержит цепочку переходов t*, t", позиций

in out Р ,Р i

р^ р^ и подсетей л такую, что:

' ^. г ' л. .' * ' » . , ., • , out, t'-{F i, t* =lp }, £"= {p^} , Г ={p }.

Для каждой подсети n .<=ЛГ , J41 (л.) = р. , NO (л.) = p. .

in n i i-i nil

Если 1-ая компонента последовательного процесса имеет метку,

то вводится дополнительный переход t. и канал с. такие, что:

1 1

ГО ( С .) = с . , ' i .=0, t .' = {р .}. nil 1 1 1

МСП, соответствующая параллельному процессу, состоящему из к

, in out ,

компонент содержит переходы t ,t , позиции р , р

р" ..... р" , и подсети п такие, что:

1 к 1 к

= f'={P; ..... рр, ' Г=\р"± ..... р^}, t"'={p Ь

Для каждой подсети л .еЛГ , N1 (л .) = р'. , NО (п.)=р". .

Д П П 1 П 11

МС11, соответствующая процессу ветвления, состоящему из компонент содержит переходы Г',Г", позиции р,П,р°ир', р", и подсети л , . .., п^. такие, что:

= = {р'}, Г = {р"}, г' = {р°и'>.

Для каждой подсети л .еЛГ , Л/ (л.)=р' , да (п ,)-р" .

1 л п 1 0 1

Если составные процессы содержат операторы'ввода, вывода и

перхода, то соответствующие модификации МСП полностью аналогичны

модификациям для простых процессов.

Графом достижимости элементарной МСП будем называть пару

Р 2 П

в =( V , Е ) такую, что V £2 , а Е XV хГ , вершинам которого л л л п п п п п

соответствуют достижимые состояния МСП, а дугам - допустимые срабатывания переходов.

Элементы множества V будем называть разметками МСП л,

о , ¡п. _ . е , ои{.

разметку V ={р ) будем называть начальной, а разметку V ={р }

будем называть конечной.

Граф достижимости позволяет определить ряд динамических

свойств элементарных МСП.

Перход £ будем называть мертвым, если V»-' , ,

л

( V*, г", ПеЯ .

л

Будем говорить, что разметка V" достижима из разметки г', если в графе достижимости существует путь (возможно нулевой) между вершиной, соответствующий разметке V', и вершиной, соответствующей разметке V".

Разметку г будем называть постоянно достижимой, если она

достижима из каждой разметки V

л

Элементарную МСП л будем называть завершенной, если ее конечная Vе является постоянно достижимой.

Множеству достижимых состояний расширения программы на языке Оккам-М соответствует множество вершин графа достижимости соответствующей МСП.

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

Утверждение 3.1.

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

Следствие 3.1.

Для того, чтобы программа на языке Оккам-М не имела тупиков, достаточно, чтобы соответствущая МСП являлась завершенной.

Для анализа свойства завершенности МСП введем понятие

замыкания графа достижимости. Замыканием графа достижимости

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

< е ° »Л ( V .V- , г >.

Утверждение 3.2.

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

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

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

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

компонетами системы АТОККАМ являются лексический анализатор, синтаксический анализатор и структурный анализатор.

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

а выходом - последовательность синтаксических объектов, называемые лексхемами.

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

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

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

Процедура-экспандер производит преобразование набора МСП, каждая из которых соответствует некоторому именованному процессу в одну МСП. При этом каждому вызову одного и того же именованного процесса ставится в соответствие отдельная страница МСП. Поскольку в языке Оккам-М отсутствует рекурсия, то процедура-экспандер сходится.

Процедура развертки преобразует неэлементарную МСП в элементарную МСП. Преобразования развертки описаны в'разделе 3.3.

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ 1) Введено понятие "чистой программы" и показано, что для автоматического анализа тупиков в исходных кодах программ на некотором яэыкг программирования для МСРВ необходимо, чтобы этот язык поддерживал разработку чистых программ.

2) В работе приведен обзор и дан сравнительный анализ механизмов организации взаимодейстиия параллельных процессов в МСРВ. Показано, что наиболее перспективным механизмом являются операторы ввода/вывода языка Оккам.

3) Показано, что язык Оккам не поддерживает разработку чистых программ и, поэтому его необходимо модифицировать.

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

-1951 На конкретных примерах продемонстрированы возможности языка Оккам-М по решению широкого спектра задач организации взаимодействия параллельных процессов.

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

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

8) Описаны методы автоматической проверки свойства завершенности МСП.

9) Дано описание системы АТОККАМ, которая позволяет производить автоматический анализ тупиков в исходных кодах программ, разработанных на языке Оккам-М.

10) На конкретных примерах показано, что система АТОККАМ может быть использована для разработки и отладки прототипов широкого класса систем реального времени, содержащих взаимодействующие параллельные компоненты.

По материалам диссертации опубликованы следующие работы:

1. [Вайрадян A.C."], Горшков C.JI. Многоуровневое моделирование многопроцессорных вычислительных систем реального времени //Материалы семинара "Сетевая обработка информации".- М., 1990.-С.85-88.

2. [Вайрадян A.C. | , Горшков С.Л.', Цапко О.Н. , Чучкин В.И. . Шувалов В.Б. Выбор рациональной структуры высокопроизводительного графического процессора //Тезисы докладов международной конференции "Высокопроизводительные вычислительные системы в управлении и научных исследованиях".- Алма-Ата, 1991.- С.10.

3. [Вайрадян A.C.") , Горшков C.JI. , Генералова C.B. Анализ корректности взаимодействий последовательных процессов языыка CSPM с помощью сетей Петри //Материалы семинара "Вычислительные системы на базе транспьютеров и параллельные вычисления.- М., 1992.-

С. 108-113-

4. |Вайрадян A.C. j, Горшков С.Л. Язык распределенного программирования, не допускающий блокировки и зацихливяния между последовательными процессами //Материалы семинара "Вычислительные системы на базе транспьютеров и параллельные вычисления.- М., 1992.- С.113-119.

5. Генералова C.B., Горшков С.Л. Отладка параллельных алгоритмов машинной графики с помощью раскрашенных сетей Петри //Материалы конференции "Информатика, телеобработка и персональные компьютеры (ИНФОР-91).- М. , 1991,- С.37-42.

6. Горшков С.Л. Надежность функционирования неоднородных многопроцессорных вычислительных систем реального времени //Теория и практика проектирования управляющих вычислительных систем.- М.: Энергоатомиздат, 1989.- С.3-7.

7. Горшков С.Л. Быстрые сети Петри - практичный инструмент для моделирования систем реального времени //Материалы семинара "Проектирование и создание многомашинных и многопроцессорных систем реального времени".- М. , 1990,- С.50-54.

8. Горшков С.Л., Лавренов М.Ю. Моделирование системы реального времени, использующей локальную сеть //Материалы семинара "Сетевая обработка информации".- М., 1990.- С.76-80.

9. Горшков С.Л. Моделирование сообщений в распределенных системах с помощью модифицированных сетей Петри //Материалы семинара "Сетевая обработка информации".- М., 1990.- С.80-84.

10. Горшков С.Л, Быстрые сети Петри - сети Петри с повышенной скоростью интерпретации //Проектирование и эксплуатация управляющих вычислительных комплексов.- М.¡Энергоатомиздат, 1991.-С.13-20.

Подписано в печать

Заказ Тираж

Типография МИФИ, Каширское шоссе, 31