научная статья по теме МОДЕЛЬ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ С ВРЕМЕНЕМ Математика

Текст научной статьи на тему «МОДЕЛЬ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ С ВРЕМЕНЕМ»

ПРОГРАММИРОВАНИЕ, 2013, No 5, с. 22-34

= РАСПРЕДЕЛЕННЫЕ ВСТРОЕННЫЕ СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ

•v. 'К 681.322

МОДЕЛЬ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ С ВРЕМЕНЕМ

© 2013 г. Р.Л. Смелянский

Факультет вычислительной математики и кибернетики МГУ им. М.В. Ломоносова

119899 Москва, Воробьевы, горы, МГУ E-mail: smel@lvk.cs.msu.su Поступила в редакцию 02.02.2013

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

1. ВВЕДЕНИЕ

В работе изложена математическая модель динамики функционирования распределенных вычислительных систем. Под этими словами мы будем понимать разработку системы согласованных математических понятий и взаимосвязей между ними, адекватно описывающих характерные особенности распределенных вычислительных систем, которые подробно рассмотрены в [1, 2, 3] и редакционной статье к данному выпуску.

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

Уверенность в том, что эта модель может служить такой основой, основана на двух

обстоятельствах. С одной стороны ни одна из известных на сегодня теорий Ч. Хоара [4], Р. Милнера [5], Г. Дегано и У. Монтанари [6], М. Найвта [7], Ю.В. Капитоновой и А. А. Летичевского [8], а также [9, 10, 11] не охватывают основных, фундаментальных особенностей РВС. В этих теориях либо не разделяют программу и физическую среду ее исполнения, либо физическая среда, а следовательно и время, как метрическая величина, отсутствует. Во всех указанных работах не всегда четко определена семантика параллелизма, условия ее применимости. С другой стороны, предложенная здесь модель была бы также полезна для разрешения ряда теоретических проблем, например, служить формальной основой (framework) для доказательства соблюдения определенных свойств распределенных систем, например таких, которые рассматривает САР теорема [12, 13]. Основная причина таких проблем - отсутствие четко опредленного понятия функционирования распределенной системы.

Изложенная здесь модель оказалаь полезной при решении целого ряда проблем:

1. Описание функционирования РВС (алгоритмический анализ РВС).

2. Анализ производительности РВС (количественный анализ РВС).

3. Описание влияния ФС на функционирование РВС.

4. Автоматизация реструктуризации ВС с целью повышения эффективности функционирования РВС.

5. Разработка языков спецификаций поведения программ с параллельной обработкой информации.

6. Построение теории эквивалентных оптимизирующих преобразований программ с параллельной обработкой информации.

7. Проверка корректности имитационных моделей РВС.

8. Верификация межпроцессного взаимодействия и синхронизации.

Модель, систематически описанная в этой статье, послужила теоретической основой при разработке системы имитационного моделирования [14-18], классификации алгоритмов временной синхронизации в распределенных системах имитационного моделирования [19], создании метода и средств оценки времени выполнения программ [20-21], постановке задачи синтеза РВС и разработке подходов к ее решению и [22-27], решении задач проверки правильности программ и алгоритмического анализа их поведения [28-29], методов сбалансированного выбора средств обеспечения отказоустойчивости РВС [30]. Эта модель описывает не только поведение программ, но и характеристики аппаратуры и того программного окружения, которое обеспечивает выполнение программы; она описывает влияние аппаратуры на динамику взаимодействия программ; содержит множественное время как количественную сущность; отражает иерархичность и структурность организации вычислительных систем.

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

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

Сообщение - совокупность параметров обращения. Тип сообщения - класс эквивалентности на множестве допустимых сообщений. Каждый динамический ресурс есть процесс с известным поведением.

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

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

Исполнители делятся на распределенные и

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

Везде далее мы будем предполагать:

1. Каждый последовательный исполнитель связан с определенным набором других последовательных исполнителей. Их набор ограничен, фиксирован и не изменяется в ходе работы прикладной программы.

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

3. Атомарные процессы не прерываемы.

2. ОСНОВНЫЕ ПОНЯТИЯ

Определение распределенной вычислительной системы.

Распределенной вычислительной системой (РВС) называется объект, состоящий из следующих компонентов:

1. Физическая среда (ФС), которая состоит из аппаратных средств РВС и средств связи между ними.

2. Логическая среда (J1C), которая состоит из совокупности Pl программ, обеспечивающих выполнение прикладных программ. Элементы совокупности Pl называются процессами J1C.

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

Первые два компонента РВС (т.е. компоненты ФС и ЛС) образуют объект, называемый вычислительной средой (ВС).

Функционирование РВС заключается во взаимодействии программ из совокупности Рп с ФС и ЛС.

3. ИСПОЛНИТЕЛЬ

ФС состоит из исполнителей и каналов связи между ними. Исполнители подразделяются на распределенные и последовательные. Говоря неформально, распределенный исполнитель (ОЕ) представляет собой совокупность последовательных исполнителей {БЕ^|г £ 9}, соединенных каналами связи (КС), через которые процессы на разных последовательных исполнителях БЕ^(г £ 9) обмениваются сообщениями. Строгое определение распределенного исполнителя приведено ниже. Управление в ОЕ децентрализовано, в том смысле, что некоторые последовательные исполнители БЕ^(г £ 9), входящие в ОЕ, работают автономно (по индивидуальной перезагружаемой программе). Для распределенного исполнителя ОЕ не существует понятия единого времени (каждый БЕ^(г £ 9) работает в собственной временной шкале).

3.1. Последовательный исполнитель

БЕ

зываемый также процессором) есть объект, характеризующийся следующими атрибутами:

• Носитель: это пара Сг = (1яЕ), где !яе и Ояе обозначают линейно упорядоченные конечные множества, называемые соответственно множеством входов и выходов носителя Сг. Предполагается, что 1зе П Ояе = 0.

• Арбитр: это функция Ф^Е вида

ФвЕ : Р(1вЕ) ^ 1вЕ,

где Р () обозначает операцию взятия множества-степени: для каждого множества М обозначим Р (М) множество всех подмножеств множества М. В точке 0Ф^Е не определена.

• (А^е С Рь есть совокупность атомарных процессов, сопоставленных последо-

БЕ.

• NsE - целое число, трактуемое как объем (число единиц) памяти у последовательного исполнителя БЕ.

• Pse астрономическое время одного такта SE с девиацией ±£se .

• Rse - набор параметров, характеризующих стековую, регистровую структуру, организацию кэш памяти разного уровня, конвейер-

SE.

• vse ■ Ase ^ Д, где Д - интервал на N -

число тактов выполнения соответствующего атомарного процесса.

Последнее требует пояснения. Для каждого а € Ase , vse (а) - это интервал, т.к. значени

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком