Введение к работе
Актуальность темы.
Поиски путей увеличения быстродействия систем реального вреценн привели к появлению идеи параллельной обработки информации на многопроцессорных системах реального времени (МСРВ). Ношли импульс это направление получило в связи с последними достижениями в технологии аппаратных средств, которые сделали возможным разработку МСРВ общего назначения, состоящих из множества узловых микропроцессоров (транспьютеров). Каждый узловой микропроцессор имеет локальную память и соязан с Другими узлами посредством каналов передачи данных. Обмен данными между параллельными процессами, выполняющимися в различных узлах МСРВ, может производиться либо непосредственно по каналам передачи данных, либо через разделяемые запоминающие устройства.
Процесс разработки и отладки паралллельных программ для МСРВ является задачей значительно более сложной, чем программирование на универсальных языках высокого уровня для ЭВМ с последовательной архитектурой, так как в этом случае к "традиционной" сложности логики последовательного программирования добавляется сложность недетерминированного взаимодействия параллельных взаимодействующих процессов. Это приводит к тому, что процесс отладки таких параллельных програми иногда напоминает лотерею, поскольку нужно отыскивать ошибки, возникающие при случайных, невоспроизводимых временных ситуациях.
Одним из важнейших классов ошибок в программах для МСРВ является потенциальная возможность возникновения тупиков (deadlocks), т.е. ситуаций, в которых несколько параллельных процессов могут взаимно блокировать выполнение друг друга.
Таким образом, задача разработки спецификаций языка высокого уровня для программирования МСРВ, поддерживающего автоматический анализ исходного кода программ на этом языке на наличие тупиков, а
такхе методов и моделей этого анализа является актуальной.
Поскольку, в общем случае, сложность программ эквивалентна сложности машин Тьюринга, задача поиска тупиков в произвольной программе для МСРВ на основе анализа ее исходного кода является алгоритмически неразрешимой. С другой стороны, в настоящее время известен ряд методов анализа тупиков, ориентированных на такие более простые модели параллельных программ, как управляющие выражения, сети переходов, сети Петри и другие модели. Однако, данные методы пока принесли мало практической пользы разработчикам параллельных программ для МСРВ, несмотря на свою интуитивную привлекательность, поскольку соответствующие модели не могли быть построены автоматически по исходным кодам анализируемых программ.
Предлагаемый в данной работе подход к решению задачи поиска тупиков состоит в формулировке достаточных условий отсутствия тупиков, поддающихся алгоритмической проверке. Автором разработан язык программирования Оккам-М, являющийся модификацией языка Оккам. Язык Оккам-М позеоляст для широкого класса практических задач разрабатывать исходный код, для которого достаточные условия отсутствия тупиков выполняются. Варианты кода, для которых эти условия не выполняются, считаются некорректными.
Целью диссертационной раСоты является разработка спецификаций языка параллельного программирования для МСРВ, допускающего автоматическую проверку исходных кодов программ на отсутствие тупиков, а также методов и моделей этого анализа.
Основными задачами. решаемыми в работе, являются:
формализация и обобщение понятия тупиков в параллельных программах для МСРВ;
исследование принципов построения и разработка спецификаций языка параллельного программирования (Оккам-М) для МСРВ, допускающего автоматическую проверку исходных кодов программ на-отсутствие тупиков:
разработка математического аппарата модифицированных сетей Петри (МСП). являющегося новым обобщением сетей Петри, предназначенного для автоматической проверки исходных кодов программ МСРВ на
отсутствне тупиков:
-разработка методов построения МСП, соответствующей исходному коау
программы на языке Оккам-М;
- разработка методов анализа модифицированных сетей Петри на
trnmiiiun Twn!!!CCS ї
- разработка и реализация комплекса программ, предназначенного для
разработки программ на языке Оккаи-М и анализа тупиков в исходных
кодах этих программ.
Методы исследования. В диссертации используются методы параллельного программирования, математической логики, теорий множеств, теории графов, теории сетей Петри и теории языков программирования.
Научная новизна
Формализованы v обобщены понятия тупиков в параллельных программах для МСРВ. Предложен и исследован язык Оккам-М параллельного программирования для МСРВ. допускающий автоматический анализ исходного кода программы на отсутствие тупиков.
Разработан математический аппарат модифицированных сетей Петри (МСП), являющийся обобщением сетей Петри и предназначенный для исследования тупиков в параллельных программах на языке О.ккам-М. Для МСП вводится свойство завершенности, которое является достаточным условием для того, чтобы соответствующая программа на языке Оккам-М не имела тупиков.
Практическая значимость работы
Разработана и реалнзопапа на ПЭВМ типа IBM PC XT/AT система АТОККЛМ, предназначенная для автоматической проверки отсутствия тупиков в программах на языке Оккам-М.
Степень обоснованности и достоверность научных положений, выеодов и рекомендации. сформулированных в диссертации, подтверждена исследованием применимости предлагаемых математических моделей и методов анализа тупиков для ряда практических примеров организации взаимодействия парарллельных процессов МСРВ, а также практической реализацией предложенных
методов.
Реализация результатов исследования Исследования проводились в рамках ряда научно-исследовательских работ по изучению архитектуры и програминого обеспечения параллельных вычислительных систем, выполняемых на кафедре 29 МИФИ. Версии разработанной системы были внедрены на предприятиях НИИ Авиационного Оборудования, г.Жуковский, и НИИ Многопроцессорных Вычислительных Систем, г.Таганрог.
Апробация Отдельные результаты диссертационной работы докладывались на научно-технических семинарах "Проектирование и создание многомашинных и многопроцессорных систем реального времени" (Москва, 1990) и "Сетевая обработка информации" (Москва, 1990), на конференции "Информатика, телеобработка и персональные компьютеры" (Москва, 1991), на республиканских семинарах "Математическое моделирование" (Бакуриани 1988) и "Моделирование, оптимизация и системный анализ" (Бакуриани 1989), на научных семинарах, проводимых на хафедре 29 МИФИ.
Научные пуСликации
По теме диссертации автор имет 10 печатных работ, результаты исследований отражены в 5 отчетах по НИР.
Структура и оОгем работы. Диссертация соостоит из введения, четырех глав, заключения, списка литературы и двух приложений. Общий объем работы 160 листов. Работа содержит 22 рисунка, 2 таблицы и 82 наименования библиографии.
