Введение к работе
/', ;. {
Актуапьность^обпемы^ Почти все существующие вычислительные системы допускают возможность частичной параппепизации протекающих в них процессов. Уже в однопрессорной вычислительной системе, управляемой однозадачной операционной системой (ОС), имеет !.'есто параллельное Функционирование процессора и внешних устройств. Разнообразие допустимых видов параллельного функционирования возрастает при переходе к многозадачным ОС. В многопроцессорных системах и сетях ЭВМ параллелизм отдельных процессов становится основным способом Функционирования системы в целом.
Применительно к отдельному процессу, по ходу течения которого приходится чередовать работу процессора и необходимого периферийного оборудования, такой параллелизм может как ускорять ход реального течения процесса ("относительно гипотетического ст-. рого последовательного течения) за счет паюаппеяизации исполнения отдельных этапов, так и замедлять его из-за того,что становятся возможными простои в тех случаях,, когда необходимое дпя продолжения работы устройство (процессор, канал и тому подобное) оказывается занятым другим процессом. Все это делает достаточно сложной задачу предсказания течения системы таких процессов.Заметим, что потребность иметь представление об эволюции системы обусловлена естественным желанием оценить производительность данной системы применительно к каждому из процессов, а во многих спучаях, кроме того, и стремлением убедиться в логической состоятепьяости применяемого механизма управления взаимодействиями процессов.
Упомянутые выие системы процессов с частичной паоаппелиэаци-ей являются объектом исследования по крайней мере двух научных дисциплин: теории сетей массового обслуживания ССеНО) и теории
взаимодействующих процессов. Обе эти теории достаточно развиты, и имеется впечатпягщие примеры их применений. Например, исследования по теории взаимодействувщих процессов позволили разработать язык программирования ОККАМ, а методы теории СеМО используется при вычислении характеристик реальных сетей ЭВМ. Однако, как можно будет увидеть в обзоре раздела I, каждая из них, используя свои средства описания и анализа объектов, не охватывает многих важных для приложений ситуаций.
Изложенное выше обуславливает актуальность задачи создания средств описания, анализа и моделирования механизмов управления взаимодействием последовательных процессов применительно к тем или иным классам конкретных практических задач.
В приводимых ниже Формулировках вместо неформального понятия "процесс" используется термин "алгоритм" в значении, уточняемом при изложении содержания раздела I.
Ці2Уі:_Е!ота является описание, качественное, аналитическое и экспериментальное исспедование поведения систем взаимодействувщих алгоритмов сетевого и программно-аппаратного математического обеспечения, а также создание аппарата дпя численного моделирования поведения таких систем. Для достижения поставленной цели в диссертации решались следующие задачи:
разработка языка формального описания дискретных систем взаимодействующих алгоритмов и семантики этого языка, а также способа введения непрерывного времени в рассматриваемые семантические объекты, что в совокупности дает средства Нормального описания систем взаимодействувщих алгоритмов для последующего численного моделирования;
выделение класса математических моделей с непрерывными временами систем взаимодействующих алгоритмов, описывемых на введенном языке;
разработка алгоритмов численного моделирования класса систем взаимодействующих алгоритмов с достаточно разнообразными механизмами управления взаимодействием;
разработка программы моделирования систем взаимодействущих алгоритмов на основе упомянутых алгоритмов моделирования и языка;
качественное,аналитическое и натурное исследование поведения отдельных классов систем взаимодействующих алгоритмов в рамках предложенных моделей.
Методы^сспедования^ Для решения описанных выше задач использовались понятия и методы, заимствованные из теории языков программирования,теории взаимодействугщих процессов, теории графов, теории автоматов, теории алгоритмов, теории динамических систем,эргодической теории, алгебраической топологии.
2^УЛ.нзя_нови2М- R процессе решения поставленных задач в диссертации получены следующие основные научные результаты:
введено понятие системы кооперирующихся орграфов, формализующее понятие механизма управления взаимодействием системы последовательных алгоритмов;
разработан язык описания систем взаимодействующих алгоритмов СООЛЬ t семантикой которого являются оснащенные системы кооперирующихся орграфов с выделенным начальным состоянием;
приведена каноническая конструкция, сопоставляющая оснащенной системе кооперирующихся орграфов кубический комплекс и динамическую систему на нем, которая позволяет построить второй уровень семантики языка;
разработаны и реализованы в виде программной системы, алгоритмы вычисления характеристик траекторий динамических систем, определенных на кубическом комплексе оснащенной системы кооперирующихся орграфов;
- цпя широкого класса систем, состоящих из двух циклических
взаимодействующих последовательных алгоритмов, проанализиро
вана зависимость асимптотического поведения такой системы от
значений задающих систему параметров.
_№актическая_ценность работы состоит в следующем:
разработан язык CDOfiG, позволяющий описывать взаимодействие в квазипараппепьных системах последовательных алгоритмов;
разработаны топопого-динамические модели взаимодействия последовательных алгоритмов, согласующихся с результатами экспериментального исследования реальных вычислительных систем. Множество топопого-динамических модепей систем взаимодействующих последовательных алгоритмов является, в конечном счете, семантической областью языка;
разработана программа вычисления характеристик траекторий динамических систем, моделирующих взаимодействующие последовательные алгоритмы;
разработан алгоритм анализа асимптотического поведения траекторий упомянутых выше топопого-динамических модепей, практическая попезность которого подтверждается хорошим согласованием результатов анализа с экспериментальными данными и результатами численного моделирования;
разработана и реализована методика натурного моделирования систем взаимодействующих алгоритмов.
Все эксперименты и численное моделирование проводились для анализа мини-ОС СПОР, реализующей управление измерительно-вычислительным комппексом ИВК-І2, и сетевого математического обеспечения РАНЕТ - 2.
Апробация работы Основные результаты докладывались на следующих конференциях и семинарах:
- Семинар по теории сложности, Ленинградское отделение
Математического института (ЛОЧИ) АН СССР, Ленинград, 1985 г.
Всесоюзной конференции по применению методов математической логики, Таллин, 1986 г.
Городском семинаре по программирование, Институт социально-экономических проблем АН СССР, Ленинград, I9B7 г.
IX Всесоюзной конференции по математической логике, Ленинград, I9PR г.
Семинаре по переборным задачам, Ленинградский электротехнический институт, 1989 г.
Щбпикации^ По результатам работы опубликовано б печатных работ.
Стр_у_кту_р_а_и_объем_р_аботы. Диссертационная работа состоит из введения, пяти разделов с выводами, заключения, списка литературы, включающего 72 наименования. Работа содержит 164 страницы, 25 иллюстраций и Ч таблицы.
