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

г« 'н =

I) >

МОСКОВСКИЙ ордена ЛЕНИНА и ордена ОКТЯБРЬСКОЙ РЕЮЖШ ЭНЕРГКгаЧЕСН'Л ИНСТИТУТ

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

Дариуш ТУРЛЕИ

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

Сб. 13.13 - Вычислительные машшш. комплексы, системы и сети

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

Москва 1930

/

Робота выполнена на кафедре Системотехники Московского ордена Ленина и ордена Октябрьской Революции энергетического института.

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

- кандидат технических наук.

доцект Л. И. АБРОСИМОВ

Официальные опокенты:

- доктор технических наук, профессор Г. И. ПРАНЯЕИЧУС

- кандидат технических наук.

доцект В. П. Ю1ШАН0В

Ведущая организация

ВЦ АН ССЕР

специализированного совета К. 053.16. 09 Московского энергетического института в ауд. Г- 3 / о в час ОО мин.

Отзыв, заверенный печатью, просим направлять по адресу: 105833. ГСП, Москва, Е-250, Красноказарменная 14, Ученый совет МЭИ.

С диссертацией можно ознакомиться в библиотеке Московского энергетического института.

Автореферат разослан' ноября 1990 г.

Ученый секретарь

Специализированного совета К. 033.16.09 А. ф. ВЭЧК0В

ftSJVitH«SHI& ; v.rj

: ; , \ ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

! мт■'■ AktVuI:ьност ь работы. Для обеспечения совместимости ''^распределенных вычислительных систем (.PEC) Международная организация по стандартизащгн СМОС) о 1978 года начала разработку базовой эталонной модели взаимодействия открытых систем (.ВЗС) и стандартов, регламентирующих архитектуру и протоколы РВС-

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

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

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

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

ЙЭУгЛШаЛ0Ш<ШЗ диссертация заключается в разработке аналитической модели. расширяющей область применения сетей массового обслул-лвання (СеМО) для анализа архитектуры РВС и разработке метода итеративного расчета СеМО, для выбранных реализаций архитектуры РЕС. Для этого:

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

-разработана методика анализа моделей ДеСеМО. в стационарном режиме, основанная на равновесии отдельных контуров обработки запросов и рассматривающая при анализе Процессоры модели как системы массового обслуживания m^g/i с различными классами запросов;

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

-проведены исследования погрешности метода контуров при расчете параметров ДеСеМО;

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

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

также на XV Всесоюзной школе-семинаре по вычислительным сетям (г. Ленинград, 1950 г. ).

Публикации. Основное содержание диссертации отражено в двух печатных работах и трех научно-исследовательских отчетах.

Структура и объем работы. Диссертация состоит иэ введения, шести глав и заключения, изложенных на 134 страницах машинного текста, содержит список литературы из 101 наименований, 47 рисунков. 7 таблиц и приложения.

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

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

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

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

Основной режим взаимодействия - это режим с установлением соединения для передачи данных. Блоки данных службы т о.

блоки данных, которые остаются неизменными от одной стороны соединения до другой, отображаются в протокольные блоки данных (ЕДШ. которыми обмениваются одноуровневые объекты, используя

соединения нижних уровней (каядый объект может одновременно иметь несколько соединений), при этом нижние уровни могут выполнять следукх^е функции:

^мультиплексирование - когда одно соединение нижнего уровня используется для поддержка! более чем одного соединения верхних уровней;

2. демультиплексирование - когда идентифицируются ВДП. относящиеся к нескольким соединениям верхних уровней, принятые по некоторому единственному соединению нижнего уровня (функция обратная мулътиплскскрсванию);

3. расщепление - когда несколько соединешШ нижних уровней используются для поддержки одного соединения верхнего уровня:

4. объединение - когда идентифицируются ВД1 для некоторого соединения верхнего уровня, принятые по нескольким соединениям нижних уровней (функция обратная расщеплению).

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

1. сегментация - отображение одного БДО в несколько ВД11; 'И. сборка - отображение нескольких ВДП в один БДС того же уровня (функция обратная сегментации);

3. укрупнение - отображение, нескольких ЕДЗ в один ЦДЛ;

4. расшивка - идентификация нескольких ВДС. содержащихся в одном ЦЦП (функция обратная укрупнению);

5. сцепление - отображение несколько ЕЩП в один ВДС шдагего уровня;

6. выделение - идентификация нескольких ЕД1, содержащихся в одном ВДЗ (функция обратная сцеплению).

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

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

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

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

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

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

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

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

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

Обзор существующих методов анализа СеМО. точных и приближенных методов расчета СеМО позволяет зделать вывод, что для анализа ДеС'еМО наиболее перспективным является подход, основанный на идее полиномиальной аппроксимации, а для расчета - метод, основанный на методе контуров.

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

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

Архитектура сети ДеСеМО определяется следующей пятеркой: а = <1. о, м, р. х> , где: I - множество пунктов обслуживания.

а - Функция определяющая контуры. 0:1—»ы. Пусть о «-ае!: -

ч-й контур.

По пунктам 1 «-<2 обслуживания контура перемещаются запросы.

В каждом контуре О определена функция задающая

коэффициенты изменения количества запросов при передаче между пунктами обслуживания. м=<мч>, м гс^уо^—»1? . Функция описывается матрицей, т.о. м = (т:.1оесг (т <1 или л >1).

В каждом контуре О определена функция рч. задающая вероятности передачи запросов между пунктами обслуживания, р»<р > • р^: о ха^—»с 0;1). Функция рч таое описывается матрицей. рч=срч:> Необходимо, чтобы функция рч удовлетворяла трем следующим условиям.

Вэ-первкх. вероятность передачи запросов из любого пункта

Е

"ч ^еО

ч

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

у о Н1-" Р ~ с-! Ч1->

Пункт J обслуживания достижим ^ >—пунктом 1 обслуживания, если он непосредственно достижим ь—О, т.е. если вероятность передачи запросов между отими пунктами ненулевая сь—*о:>, или если существует промежуточный пункт к, достижимый *-м. и —Г{ пункт непосредственно достижимый к -м пунктом, т. е.

а >-{-. р с3 к С1 ю л ск >—► ,р;> V- с 1 >—> .р.

В-третьих, функция рч вместе с функцией ма должнн обеспечивать уравновешенность контура. Контур сг является уравновешенна*, если независима следующая система линейных уравнений: X = У X -т ,-р . . еС .

я

где х . Х1 - интенсивности потоков запросов. передавало»: соответственно в 3 -й и ± -й пункты обслуживания.

Предполагаем, ' что запрос, переданный ^ -му пункту обслуживания, обрабатывается некоторое время, а затем передается с

вероятностью р J-му пункту обслуживания (непосредственно достижимому i-м). Если коэффициент m изменения количества запросов отл!гчен от едшпщн. то J-му пункту обслуживания передается не один. a запросов. Кроме того, предполагаем, что обрабатываются только целые запросы. Это означает, чтс если, например. J -му пункту обслуживания передается часть запроса (" <1). то эта часть ждет передачи следующих частей до тех пор. пока сумма частей запросов (передаваемых J-му пункту обслуживания) будет но менее единицы. Тогда один, целый запрос принимается на обработку, а в ожидании остается, возможно, нецелый запрос. Контур окажется в тупике, если в нем не будет ни одного целого запроса, х - функция, определяющая процессоры, x.-i—►«. Пусть x„=<iisl: х с i э =х> - х-й процессор.

Пусть <о> - множество индексов контуров, <*> - множество индексов процессоров. Пересечения контуров Q . qe<Q> с процессорами х*- Хе<х>. образуют процессы п оболузншшшя запросов, п^-

q ЛХ =■ <i el : ieQ a ld )

q * q x '

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

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

Сеть ДеСеМО определяется следующей семеркой:

n =■ <1 , q. M, р, x, f, с> .

где пятерка а » <i, q. m. p. x> определяет архитектуру сети.

Функции р^. распределений вероятности времени обслужи-

вания запросов, определен« для всех пунктов обслуживания, .

Для каждого контура Оч определена функция с задающая емкость контура в базовом пункте 1 еОч обслуживания, т. е. задающая для одного, строго определенного пункта . среднее число с оэ»-^ запросов, предназначенных для этого пункта обслуживания, и постоянно находящихся в контуре. с=<.с^> • сч: о,—• Таким образом, емкости контуров задают ограничения на общее число запросов, находящихся в сети в установившемся режиме.

Дта определения стационзрных характеристик сети ДеСеЮ составим систему уравнений баланса количества запросов по фазам обработки запросов. При атом в каждом процессе п выделяется столько фаз « обработки запросов сколько разних входных пунктов обслуживания имеет процесс. Фаза ® обработки запросов,

определенная через входной пункт -¡«л обслуживания, включает в

п

себя пункт 1 н все пункты 1 обслуживания, достижимые х>-пунктом 1 в процессе п <1:> и <;-!<£Пчх: 1>_ чНЬ-Р.

Достижимость пунктов обслуживания в рамках одного процесса определяется аналогично достижимости пунктов обслуживания в рамках контура, т. е.

С 1 » О <-» С1,1е11 Л р *0Э.

Ч* >)

С1>-Пч><-([->.р « С!*-"«*^-'1 ~ Ск>-Пчх-^:>:>.

ч*

Каждая фаза обработки запросов имеет свои временные

характеристики, а именно, собственное среднее время и второй

момент V* времени обработки запросов. 1ЧХ - 2 *

- сГР СзЗ

V2

СП? Сб}

5 »о, 1чх сы

р*чхС;о-преобразование Лапласа (плотности распределения вероятности) времени обслуживания запросов в Фазе ® .

^ I

р* = р"с-о )ч\ где:

р'сзэ-преобразование = хо'»"''л Лапласа (плотности г со

распределения вероятности) времени обслуживания запросов в пункте -)еЛч„ обслуживания, г' -коэффициент попадания запросов в )-й пункт обслуживания ч*-го процесса при условии, что извне запросы передаются через 1-й (входной) пункт обслухнвашш.

где:

-о.

Коэффициент r*qx вычисляется следующим образом:

х1

i i q х

г =• т-^1- . где:

И"

^чх-интенс;гоность потока запросов, передаваемых j-му пункту

обслуживания в Фазе обработки «> . * -интенсивность потока запросов, передаваемых в Фазу т.е.

в i-й пункт обслуживания извне q*-ro процесса. Интенсивности <х' >. х jen связаны следующей системой

Jqx iqx qX ^ ^

линейных уравнений:

х1 = з'-х * S х1 -т р . 1еЛ . rae s'=f 1' -1'1

jqx i jqx k¿n Iqx lej Hk) J qx J \ O.

qx

а интенс!шность \ равна:

X = \ X-m-p ,X => \ • m - p

• q» jfen ' 1 У k'

qx __q

&числнв средние времена v^ (и вторые моменты времени.)

обработки запросов во всех фазах Ф1г!х обработки запросов, можно

составить уравнения баланса сети ДеСеМО.

с Y Т Г /„ . qe<o>, где: С1) 4 xá<x> ién 1Ч* _ qx

х-среднее количество запросов находящихся в фазе ^ 1в процессоре х) в очереди и/или на обслуживании, n¿ х-коэффициент изменения количества запросов, обрабатываемых в фазе ® по отношению к количеству приведенных запросов контура, т. е. запросов, передаваемых базовому пункту обслуживания в контуре.

Значение n согласно формуле Ляттлз разно: КГ~ = х ■ с w v- :> где-

i. qx tqx i qx i qx * M '

\ -среднее время ожидания запросов фазы ®>qx в очереди

процессора X,

-среднее время обработки за!фосов в фазе ®>qx.

Среднее время ожидания в очереди процессора одинаково

для всех фаз обработки связанных с данным процессором, и

равно сумме: _ _ _ _.

w = w = w + w , где-

i qx х о.х v,x "

wo)l-среднее время ожидания завершения текущей обработки процессором х,

\х-среднее время обслуживания всех запросов, кахеджукея в очереди процессора в момент прибытия нового запроса. Если рассматривать процессор как ГМО типа M^e^i, то тогда первое слагаемое \ х и второе слагаемое \ х соответевстшо раиш-

= I У

■v2.

/2 ,

к = У У V., , где:

-среднее число запросов фаза находящихся в очереди

процессора х в в момент прибытия нового запроса, согласно формуле Лнтла равно: и~к1<. т.е.

Я / > х, ' V ■ и

"кЙ{У> "" ),п<

Суммируя соотношения, определяющие Ч7х. получаем сле-

дующую систему уравнений:

* = У У ' х ^ ■ ^ * У У

х ъ • V.. ■

_)хх ,))сх }кх

с неизвестными »Г". й~к)|. Но, поскольку время ожидания в очереди процессора одинаково для всех фаз обработки, связанных с данным процессором, q,ke{Q}l то эта система

уравнений решается как одно уравнение:

У У Х „ /2 ^ - * *

ч»" 1 _ у Ух-—'

и окончательно среднее количество (Г^ =х1чх ■ (> запросов фазы ®1чх в процессоре х равняется:

ы = х . •

к зх гя*

ГУ У Х.к -/2

1

+ V

В уравнениях баланса N /п.1чх осталось вычислить

ч*

коэффициенты л изменения количества запросов С по отношению к

количеству приведенных запросов контура).т.е.

X

пг,» = х5— . гдо:

I Ч я

\

/^-интенсивность потока запросов, передаваемых в фазу ®1чх при условии, что количество запросов в контуре не меняется

X ■

к/ = У х: • р , х* = V х * ■ р. 1Ч,< ' 1 к£« 1 к) ч* ч

И тогда уравнения (1)' баланса получают следующий вид:

с , У у

4 Х«{Х> 1 кп "и ч*

ГУ У х V /2

У у X V- 14

4/ГМ Мп 'к» »"

кй{9) леП

q. ke<Q>

leO

.. ,-------. — . jen . Приведем

iqx JX* ¡ex

потоков запросов во всех фазах обработки

о неизвестными интенсивности х

контура к одной искомой интенсивности определив коэффициенты ш1Чх изменения интенсивностей потоков запросов по отноиекию к приведенной интенсивности Лч, т. е. интенсивности потока запросов.

передаваемых базовому пункту контура.

х

„ . 14*

и перепишем систему C1-Z) уравнений баланса.

V I I

4 хе<Х> 1ёП

'I 2

ke<Q> Jen

" i, 'V\ ^ jk х jxx

- I I

kfeíCD jéri

j V x

jkx

(.3)

с неизвестными приведенными интенетго.чостями хч-хк- ч.*«=<С£> потоков запросов в контурах.

Завершающи этапом построения системы уравнений баланса сети ДеСеМО является введение коэффициентов ограничения очередей. Коэффициент ограничения очереди процессора * вычисляется следующим образом: с

ч

-с— '

X

причем суммарное количество с^ запросов, циркулирующих через

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

данным процессором, т. ©. „ _

с = V ) с * ч#<о> 1ёп 1Ч*

где с - емкость контура ч в фазе ® равняется

с = п -с .

Вслючкм коэффициенты г в систему (3) уравнений баланса:

' I

С = X q ч

I I

хе<Х> 1еП

V

kt<Q> JtH

jk>

•V- /2

JO

• I I

n -V j k x j V >

С 4)

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

Третья глава посвящена исследованию погрешности метода контуров для двух видов сетей ДеСеМО. кольцевой и сети с центральным

п

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

В кольцевой сети массового обслуживания находятся и процессоров, которые образуют замкнутое кольцо обработки запросов. В ' сольце циркулируют к запросов. которые обрабатываются последовательно всеми процессорами в порядке поступления. На входе процессоров образуются очереди Пусть распределения вероятности времени обработки запросов подчиняются показательному закону со средними значениями . 1=Г7ТТ. В установившемся режиме

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

к ск-1 з ск-1 -) з ск-1 -1 -...1 э

I % - - *■ -

- I - (К-1 -I .

ы- I * г

У ' У

=1 1 -О 1 =0 1=0

I г э N-1

к ск-1 э ск-1 -1 5 ск-1 -1 -...1

К-К-К-...2

- -(К-». -V -. . . -V >

Ы— 1 12 N-1

К. . ' К.

=о 1 =о 1 =0 1 =0

I 2 Э N - 1

Время цикла каждого запроса, т. е. среднее время, за которое в установившемся режиме запрос совершает круг, равно 1 - «-"х.

Исследования, проведенные для различных значений параметров к. 1=1.и показали, что самые большие погрешности метода контуров наблюдаются в том случае, когда один процессор замедляет прохождешге запросов в кольце, т. е. когда интенсивность обслуживания одного процессора меньше интенснвиостей • ■ ■

обслуживания остальных процессоров, лри этом интенс!шн0сти обслуживания остальных процессоров равны друг другу т.е. >■','• ^^ ^ На Р1!с1 показаны погрешности <*-гонтуря-«-точнов>

/1гочнов!'100!! расчета времени I- цикла для N=8 процессоров. Погрешности в пиковых значениях. для незначительно

превышают 6/.-

О 15 32 48

Рис.1. Погрешности метода контуров для кольцевой сети массового обслуживания.

Далее, анализировался общий вариант сети массового обслуживания, в которой находятся N пользователей и один центральный обслуживающий прибор. Каждый пользователь может передавать центральное/ прибору последовательность 1=17?', запросов, а затем получать последовательность К1 ответов, которые сбдумивавтся в порядке поступления и порождают следующие запросы. На входе обслуживающего прибора образуется очередь запросов, которые обслуживаются в порядке поступления. На входе пользователей могут также образовываться очереди, а между 1 -м пользователем и обслуживающим прибором циркулируют \ запросов и ответов.

Пусть времена обдумывания пользователей подчиняются показательному закону распределения со средними значениями равными 1 . 1 =Г7м. Если принять. что времена обслуживания запросов центральным прибором тоже подчиняются показательному закону распределения, но со средними значениями равными 1 • i-i.fi. то такая сеть имеет прямое аналитическое решение. В стационарном режиме интенсивности 1=1 .и, циркуляции запросов и ответов

между пользователями и обслухивавщим прибором определяются

следующим соотношением:

к .к ,.. сю. . к

V

Ск ■ ■>< -15! ,—, [ А-'

1 2_а__П —

с I ■ к ! ■ • С к -12! ■ - к ! О

12 I N * ' .

1

к , к . . . С к =15 . . к =0 } =1

12 I N

где р - вероятность того, что центральный оослужнвающнй прибор

свободен:

к .к

I 2

V- V

С к +к

• -к 3 : г—,

-ь-П

Среднее пользователем

к

1 <

время ь циркуляции пары запрос-ответ между и обслуживающим прибором определяется следующим образом Среднее время ответа на запрос пользователя

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

г =Ъ -1 /V . г = К УХ -1 .

V . V V I V V

Исследования относительных погрешностей %г=(Сгкс,„тур-гточнов:5 ^точное1 'Юоя расчета времени ответа, при использовании коэффициентов г в виде г^к'-п/н*, для , н=о. в н я-о. 7в. показали, что. для варианта сети , 1=1.N. имеющего самые большие погрешности. графики погрешностей сглаживаются и одновременно опускаются вга{э С рис. 2), принимая в некотором диапазоне отрицательные значения, когда степень * принимает значения меньше единицы. Правда, для слишком малых значений степени $ выигрыш, за счет выравнивания относительных погрешностей расчета по всему диапазону изменений параметров 1=Г7м, теряется воледствии излишнего

смещения графиков и возникновения больших отрицательных погрешностей. но в оптимальном варианте погрешности не превышают 10"/.

м/И-о 10000

-1(Н

7.2я

-8.55?

Рис. 2. Погрешности метода контуров для соги массового

обслуживания с центральным обслуживающим прибором.

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

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

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

На рис. 3 указана схема передает файла, учитывающая особенности транспортного протокола. Обратим внимание, что. после приема всех п> Фрагментов файла, адресат передает инициатору подтверждение. Но, так как оно вырабатывается объектом прикладного уровня (в пункте 1<ю обслуживания), принимаем, что через транспортное соединение подтверждение передается как фрагмент данных и в случае необходимости разбивается на м пакетов.

На рис. А указаны погрешности 5Л=[Съдесемо~''1.лм:"*'ьлк13 'loov-аналитического расчета среднего времени доставки файла по сравнению с результатами имитационной модели lan cLogic Activity Network? в случае, когда одновременно установлены 4 разных сеанса передачи файла. Поскольку рассматриваемая модель имеет вид сети с центральным обслуживающим прибором, предполагалось получить более достоверные результаты для коэффициентов ?'lt=ccc'~i:>/'c" и степени

-<-1. lia рис. 4 указаны погрешности >«• для двух значений степени к s=o. 75. Самые больше погрешности (.для s=o.7s около юу.) получаются в случае перегрузки сети передачи пакетов, т. е. для малих значений параметра <j. определяющего скорость передачи пакетов.

файл

m фрагментов

О

ИНИЦИАТОР

cu

N. CCFN

Т. CCFN

i i 1

i i э 4 22

Т. DTRT |

Т. DTIN

N. DTIN I t СС J

ъ

схс::::п м

N. DTTN N. DTIN (АКЗИ I

Г

N. DTIN ItDC)

N. CRST ¡ N. DTRT ¡ tCR) !

¡ ! | N. CRNS

u

N. DTRT

i O пакет

N. DTRT N. DTRT

¡ICC1 N. DTRT

N. DTIN

í íAK] i пакет {

¡ D I

i [ DR3

С AKJ ¡ ¡ N. DTRT N. DTRT I

N. DTIN X

I AK)

i (DC) N.DTRT I

i

N. DRST í (

сеть

( DRl

N. DTIN N. DTIN

ax:::::n

ükJ

0

м

ox::;

CJ

N. DIND

i i

В 2 в «

T. DTRT

i i

SO во

m Фрагментов

zx- ■ ■■ I J

P-l/M p'l/m

файл

Т. OI ND

й

АДРЕСАТ

соединение передача подтверждение разъединение

. Рис. 3. Схема передачи файла. - 18 -

i

3Q

4 О

В X

Т. CIND

Т. DTIN

i

2 О

> (.

i i

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

погрешность бремени доставки файла

s = 0.75, s=l

Рио. 4. Сравнение результатов аналитической и имитационной моделей.

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

Поскольку программа ДеСеМО использует динамические структуры данных, память не является критическим фактором, при рассматренин ограничений анализируемых объектов. Фактором. ограничивающим применение программы является количество различных контуров в сети ДеСеМО. Если принять, что решение одного уравнения баланса занимает время и все контуры организованы в структуру бинарного уравновешенного дерева, то тогда время *-0, необходимое на решение системы уравнений баланса, растет с логарифмом íog^iO количества г контуров. Дяя г4.8,... дерево контуров является вполне симметричным н. если для ураЕНОвехения каждого нового контура необходимо s шагов итерации, то время t-0 равно t6ctT's'°Vrt.

ЗАКЛЮЧЕНИЕ

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

замкнутой детализированной сети массового обслуживания СДеСеМО). т. е. -замену: л'' СеМО о изменением количества запросов, произвольными ¡.-з.-лределениями Бремени обработки запросов, различными контурами обработки и .детализацией обработки внутри обслуживших приборов (процессоров).

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

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

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

5. Разработаны программные модули для расчета моделей ДеСеМО.

0. Установлено, что погрешность метода контуров при расчете моделей ДеСеКО приемлем полученные погрешности не превышали, как правило. 10>0.

7. Установлено, что время расчета симметричных моделей ДеСеМО гораздо меньше, чем время расчета в других известных моделях. Установлено, что для моделей ДеСеМО произвольной конфигурации трудоемкость расчета не более чем <-т •51с'9г"''> где: г-количество контуров. ^-константа зависящая от точности расчета, »--время расчета одного контура.

8. Показана возможность построения эффективной системы анализа влияния архитектуры на Функциональные параметры (т.е. среднее время реакции, коэффициенты использования процессоров, средние длины очередей) распределенных вычислительных систем.

9. Основные положения диссертации отражены в следующих публикациях: Абросимов Л. И. . Краюикин В. А. . Турлей Д. Расчет временны:-характеристик древовидных шинных ЛВС. В кн. Проектирована вычислительных сетей и систем коллективного пользования. //Тр. ин-та /Моск. унарг. ин-г. -1990. -Вып. 229. -С. 25-32. Абросимов Л. И , Турлей Д. Формализация описания протоколе! взаимодействия процессом для анализа сетевой архитектуры. //Х\ Всесоюзная школа-семинар по вычислительном сетям: Тезис: докладов -Ленинград. П. с 110-1^

1...... м-41. Ь ...........и,•«щи», и