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

Российская Академия Наук Институт проблем управления

:: Г13 од

¡пттз

На правах рукописи УДК 681.324

Богуславский Леонвд Борисович

ВЕРОЯТНОСТНЫЕ МЕТОДЫ И МОДЕЛИ УПРАВЛЕНИЯ ПОТОКАМИ ДАННЫХ И РЕСУРСАМИ В СЕТЯХ И МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ

Специальность 05.13.13 - Вычислительные машины, комплексы, системы и сети

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

Москва - 1995 г.

Работа выполнена в йнстктуте проблем управления Российской Академии наук.

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

член-корреспондент РАН Лаван В. К.

доктор технических наук, профессор Кгкатущенко В.В.

доктор технических наук Пороцкий С. М.

Ведущая организация - Институт проблак передач информации РАН,

г.'москва

_ Ф^МаЛХ .

Защита состоится " Ь " октября 1995 г. в 7.Х часов на заседании диссертационного совета N2 2 (Д002.68.01) Института проблей /правления РАН по адресу: Москва, 117806, Профсоюзная ул., 63. Телефон совета: 334-93-23.

С диссертацией можно озкаконнтъея в библиотеке Института проблем управления.

Автореферат разослан

1995 Г.

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

Е. В. Юрггевич

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

Актуальность проблемы. Достижения микроэлектроники и техники зязи создала предпосылки для быстрого развития распределенных выделительных систем (ВС). Их основными компонентами в части обра-1тки й передачи информации являются многопроцессорные ВС (КВС) й зтк. Появление сотой было связано со стремленном к коллективному ^пользовании пвтоноиных компьютерах, програмкных и янфорнаиион-хх. ресурсов, неяодящехся во многих отдельных вычислительных цект-5.x, и соответственно, к более эффективному совместному распредз-экизз нагрузки на эти ресурсы. Создание МВС основано на использо-ihhs параллвлнзма алгоритмов .многих задач путем выполнения ветвой 1кой задачи одновременно на нкожестэ» вычислительных элементов процессоров), осуществляющих доступ к общим устройствам хранения «формаций, основный из которых являятся общая память. Таккн обра-зк, КЗС обладакт тзк же преииущестзок перед однопроцессорными си-гекамж, что и csr:s ЭВМ перед отдельными ЗЗМ, а ккеико - повышоня-л коэффициентов использования ресурсов системы.

Однпи из основных критериев эффективности-я качества ВС и сз--эй, принимаемых во вникание при проектировании, производстве, пределения и расширений конфигурация н настройке в процессе экс-пуатации, т.е. в течения всего жизненного цикла, является их производительность. При проэктнровании новых ВС к сотей, архитектура эторых значительно отличается от существуюашх, единственным ме-эдок прогнозирования производительности является модалированио. эн кастройке ВС яля сетей на определенную нагрузку (траффян) я ря планирований их мощности для удовлетворения возрастающих по-ээбностей, моделирование является наиболее экономичным способом энска оптинальной конфигурации среди огромного множества возмояс->tx конфигураций. Даже при повседневной управлении БС и сетью ко-элирование помогает выбрать наилучший вариант 00 использования, эккципиалънык достоинством применения моделирования, покяко пслу-аомых численных оценок производительности, является осознание нутренних особенностей структуры я поведения ВС к сети, которое риходит в процессе разработки и анализа моде.':».

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

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

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

Многие проблемы проектирования сетей ЭВИ к МВС связаны с распределением ресурсов среди конкуркрукикх требования к& эти ресурсы, причем моменты появления этих требований и требуемые объект росурсоЕ заранее неизвестны, носят случайный характер, возможне различный для разных категорий источников (абонентов, пользователей), к варьируется в гаироких пределах. Зти обстоятельства приводят к необходимости включения в сети ЭВМ и МЗС некоторого 'механизма управления потоками ,-анных к ресурсами (УПДР). Обычно механизм УПДР представляет собой множество операционных правил, согласнс которым обрабатываются потоки данных (запросов, сообденкй, пакето! к т.п.). Этк правила должны: определять маршруты прохождения потоков данных, а тькжа стратегии, алгоритмы к дисциплины обспуживаний в узлах МВС и сети; прогнозкровать, предотвращать и исключат» перегрузки и блскяровкк путем рвгуляровакия входного траффяка г управления распределением буферной памяти.

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

зие процессоров к модулей памяти, особенности к характеристики сй-зтекы коммутации). Модель» потоков данных (или нагрузки) описывз-этся поведение требований к ресурсам сети ЗЗМ кля НЗС (места возникновения к потребления потоков, их интенсивность и т.п.). Модель !«еханизна УПДР представляет собой алгоритм распределения ресурсоэ, зключаюиий пороговые ограничения, выбор маршрутов, вид алгоритмов цоступа к т. п.

К настоящему времени в России и за рубежом создан значительный задел математических методов оценки производительности сетей ЭВМ и МЗС, основанных на аппарате теории кассового обслуживания и учитывающих влияние первых двух компонентов, т. е. параметров оборудования и потоков данных, при простейших механизмах управления (или при существенно упрощающих допущениях). В гораздо меньшей степени решена проблема разработки нетодов оценки производительности для достаточно сложных реальных механизмов УПДР, обеспечиэахг £шх высокоэффективную работу современных сетей ЭВМ и МЗС. Главная трудность прй этом состоит в сильной взаимозависимости поведения эазличных очередей в соответствующих моделях реальных механизмов ШЛР. Имеющиеся по этой проблематике публикации в значительной степени разрозненны и отражают, как правило, отдельные частные ас-1екты указанной проблемы.

Цель» диссертационной работы является разработка методологи-1еской базы и математического аппарата моделирования механизмов ГОДР в сетях ЭВМ и ИБС в ориентации на построение, анализ эффектя-зкости и развитие реальных сетей и НВС.

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

Научная новизна работы заключается в обосновании и разработке адиной методологической базы н комплекса новых математических мо-зелв-й а методов для исследования, оценки эффективности к практиче-:кого выбора механизмов управления потоками данных и ресурсами (УПДР) в еэтях ЭВМ и многопроцессорных вычислительных системах

- б

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

Практическая ценность работы. Результаты диссертационной работы позволяют научно обоснованно решать такие ваянные в практак( разработки, создания н развития сетей ЭВМ к КВС задачи, как оцеккг проектных решений при выборе архитектуры и конфигурация КВС к сети, при выборе технических и управляющих программных средств, уточнении к настройке параметров сети или ИБС; оценка эффекткьчост! средств распределенной обработки к хранения данных - иерархкчсско! памяти в локальных сетях к МВС, спецпроцессоров в НВС, сетевой архитектуры <клкент-сераэр»; сравнительный акалей и выбор иеханкзно] УПДР в МВС, в частности - стратегий доступа к критическим ресурса; с учетом конкретных особенностей реалькизс МВС; оценка эффективности и выбор параметров лкнойкых, сквозных и кнтарсетевых протокола] с учетом особенностей потоков данных и степени загрузки оборудования сети, к др.

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

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

- при разработке,систены программного обеспечения МОСТ, предназначенной для построения неоднородных сетей из однородных сете: (или отдельных ЭВМ) произвольной топологии;

- при создании ВСКП АН Молдовы;

- при создании информационно-вычислительных сетей угледобывающего концерна <ХДБ Соколов» (Чешская республика), Кошицкого Поли' технического института (Словацкая республика), в Носприватизаци (г. Москва) и Государственной Думе РФ.

Практическое использование результатов диссертационной работ: подтверждено соответствующими материалами о внедрении.

Результаты•диссертации, опубликованные в монохрафкях и стать ях. используются в учебной процессе в Московском физнко-техничес ком институте (МФТИ) и Москозсгок Государственном Уняверсктете пу

гей сообщения (МГУПС).

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

- 10-й Международный конгресс IFAC (Мюнхен, ФРГ, 1987 г.);

- Международная конференция по локальный и городским сетям свя-»и «LAN & MAN» (Киото, Япония, 1994 г. ) ;

- 6-я, 10-я, 11-я и 13-я Всессюз. школы-семинары по вычислите-1ьным сетям (1981, 1985, 1986, 1988 гг.);

- Всесоюзное совещание по пробленан управления (Ереван, 1983 г.);

- 2-е Всосоюз. совещание «Автоматизация проектирования и конст->уировання» (1983 г.).

- 4-я Всесоюз. шк.-сом. «Распараллеливание обработки информации» (1983 г. ).

- 2-е Всесоюз.совещ. «Высокопроизводительныз вычислительные синены» (Батуми, 1984 г. ).

- 4-я Всесоюз. конференция «Вычислительные сети коммутации пактов» (Рига, 1985 г.);

- Всесоюз. семинар по методам и средствам применения ЭВМ в народном хозяйстве (Москва, 1985 г. ) ;

- 6-я Всесоюз. шк. «Многопроцессорные вычислительные системы» (Звенигород, 1985 г.).

Публикации. По теме диссертации опубликовано 37 печатных ра-5от, в том числе 3 монографии.

Структура к обьен работы. Диссертация состоит яз введения, ;еми глав, заключения, списка литературы и приложения, общий объем эсновной части работы составляет 252 страницы машинописного текста, 71 рисунок и 13 таблиц. Список литературы содержит работ».

Зриложзиив, посвшонное практической реализации результатов диссе-этацян, занимает 22 страницы.

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

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

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

- в

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

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

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

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

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

сокую скорость доступа большого числа пользователей к общим базам данных большого объема.

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

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

транспортный уровень для управления сквозной передачей данных и логическом соединении двух абонентов (сквозные протоколы);

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

канальный уровень для управления передачей данных между смек-кыкн узлами сети {линейные протоколы).

Управление соецянешшк сетей в шлюзе обычно осуществляется ка транспортном а сетевом уровнях. любом урояна управление потокам* основывается кв пороговых ограничениям: и выделении расурсоз езтя. Анализ зффзкткьностя к к о до л ::р о 2 а. ш: я механизмов УПДР в глобальный сетях осуществляются а главах 6 я 7.

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

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

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

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

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

л»бой группы i=77n, состоящей из m модулей, н любого ее модуля j

л 1 -1 -1

имеет место равенство Хр^/ц^ р(, где X н - средние времена подготовки запросов в процессорах я обслуживания а модуле j, р^ -вероятность доступа в этот модуль, а парахатр pi характеризует загрузку модулей группы i. Предполагается также, что процессор в любой момент временя иояет иметь не более одного запроса в ОП. В этом случае моделью системы является замкнутая сеть ИО с N заявками, состоящая из IS-ста!сдай с параметром X, моделирующей работу H процессоров, и п групп одноканальных устройств, моделирующих п групп модулей ОП. Состояние этой сета описывается вектором 1=«(1 , ...,1п) дляк очередей к каждой кз групп. (Доказывается, что наличке а процессорах блокоз локальной па.чята (ЛП) мох<ет быть учтено путем соответствующего выбора значения параметра Л). Стационарная вероятность л(1) произвольного состояния сатн 1 определяется выражением

-1 П К"1*1!)-1! ' -1

п( 1} » G '(Ы). + , ГГ i Р, - в к( 1), (1)

1 ' ' " n 1 = 1 ( 1 J

где G - функция разбиения, (К)x"N!/(Н-х)î, =х!/[(х-у)!yi].

Основными показателянк провзводхтелькости являются: сроднее

число активных процессоров Р , средняя длина очереди Ь к группе i,

2 А 1 дисперсия этой длк1зл <?1 и среднее чясло занятых устройств этой

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

L - G-1 l ... £ " 1к(1). (2)

1 1-0 1-0 • I n

a для. <r* » R( эта se формула справедлива с заменой множителя ^

на. соответственно, (Ij-L^)2 н r^(1()= п^li/(r^)7 наконец,

p - N-L- ... -L . Ain

Пусть рассмотренная выше KBC с п группами модулой ОП включает в себя также t групп спецпроцессоров (т.е. N процессоров рассмат-

риваются как скалярные процессоры). Группа i«n+l,n+t состоит из п^ одинаковых спецпроцессоров, каждый вз которых выполняет свою операцию за среднее вреня (д )-1. Запрос от скалярного процессора на выполнение операции типа i (выдаваемый с вероятностью pj направляется в любой из свободных спецпроцессоров группы i, а в случае, если все они заняты, ожидает в очереди к этой группе, общей для всех скалярных процессоров. Тогда группа спецпроцессоров i моделируется п^-канальным устройством, и средняя длина очереди к группе модулей ОН или спецпроцессоров равна N N-l -...-1 , ,

\ П ♦ t - 1 Л

ь. - <Г* Z I V(l).

1 1=0 1 =0 1 1 «!♦*.

где

я(1) - (N)x п

1 '■' 1=1

'm -1+1

Л1 n + t

Р1 _ ТТ

1 1 Р,1/ П г, (к)

з^ (к) =го1п (т1, к) при ае п+17п+Е; а дисперсия сг^ и среднее число занятых модулей ОП или спецпроцессоров II определяются аналогичными формулами с заменой 1 на (1 -Ь ) я г (1 ).

Как видно из формул (1) и (2), при большой размерности модели, заключающейся в большом количестве заявок (Ы -—» «) и/клк устройств, основную трудность представляет вычисление функции разбиения; для преодоления этой трудности в п.2.2 разрабатываются асимптотические приближения на базе метода Лапласа. В частности, для случая однородной нагрузки (т. е. п=1, К^Н, 1^=1*) получены следующие приближения: при м —» N —» ю, И/М=а, где постоянная а не зависит от N и М, имеем

К * М [1-(1-1/М)/(1+ах*-1/М)], Ь « Их*, (3)

где х%(0,1) - корень уравнения р(1-х)-х/(ах+1-1/М)=0, преобразуемого к квадратному, а при М-«М0<о: и М —» » инеем

й " йр при Г=Нр/М^1 И К в М при ГК1, Ь я Мх*, (4)

где х°е(0,1) - корень уравнения (1-х)г-х/[х+(К-1)/Н]=0, если г>1 и (1-г)гЫ>1. Приведенные в диссертации численные результаты показывают, что эти приближения позволяют получить приемлемую точность расчета показателей Ь и Е даже для небольших значений N и М.

Непрерывные ноцели позволяют также исследовать случай локализованных обращений к однородна иовуляк ОП (т.е. п=1): если к-й

запрос процессора приходятся п модуль ОП, то ого (к+1)-Й запрос попадает к этому модул» ОП с вероятностью а, а с вероятностью (1-<х) / (М-1) - к 1~иу модули ОП (3*1). Доказывается, что при нулевом времена подготовки запросов среднее число занятых модулей ОП равно И " ММ/ (Ы+М-1) я не зависят от а.

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

Г Г \

за конфликтов. Тогда й(М,К) «■ п|1-^1-(1/п)j j, гдо п=зяах(Н,К) и

и*-тв.1.п(М,М). Другой способ основан на декомпозиционной аппроксимации коделя. используя которую получаем:

1ля случая локализованных обращений приближенный анализ дискретной «одела дает ту жа формулу К«КМ/(И+М-1), что я непрерывные модели.

В я. 2. 4 рассмотрев два варианта организации КВС с общой пя-к блоками ЛП. С первом варкпято кагедый блок ЛП доступен лчгь ¡собственному* процессору д при обрашоиик в ЛП конфликтов нэ воз-шкаат. При втором варгантв возможны обрищания к лгобоку блоку ЛП, гркчем обращение к "чужому" ЛП вызывает конфликты в интерфейсе 5роцессоры-0П, я не учитываются конфликты, возкЕкакщяо прг; обрыце-чяя процессора а собственный блок ЛП я зшкоторого другого процесса з тот же самый блок ЛП. Анализ копрорытзлх моделей этих вариантов ЙВС показал, что в первом варианте среднее число активных гроцессоров вычисляется по формуле

£ к ч

Р Я0)

КГ

р

к

v +г.-у

а г

■до » . V*1 - срздпяз вроиьна, соответственно, подготовк»

спроса э процессора и обслуживания запросов э ОП и ЛП; р - воро-тность того, что запрос процессора адресован к собственному блоку :П; Во втором варианте справедлива та ¡ко

2 3 > 3 12

юрмула. в которой вместо кмтанснвкос^я v следует подставить ян-

з

знсявкость определяемую выра»вкЕэк

- 3.4 -

-1

'з '

где ро - вероятность обращения процессора к ОП, а V" - средняя длительность обслуживания в ЛП запросов от чужого процессора. Имитационное моделирование КВС с односвязиык ккторфайсок и блокака ЯП на основе реальной гистограммы вренен запросов при постоянных временах обслуаавания запросов в СП и ЛП показало, что относительная ошибкаг в расчете Р^ по модели но превышает 7%.

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

В данной главе исследовалось влияние» стратегий доступа с обратной связью на пронзЕодктольность системы, причем особое пнш-нанне уделялось следующим двум стратегиям: Простой Стратегии, гд& п(п) равно константе, и Сложной Стратегии, где я(п)"та1 пря пзг^, а(п)**1а, прк г^спзп +п л при последующих попытках.

Цель анализа заключалась в разработке кстодов сценки т&кех показателей производительности, как; X) ерздноз число тактов Т<5), затрачиваемых на получение доступа к требуемой удаленной памяти; 2) ервдн&о число тактов затрачиваемых прк чтопзк па возврат

ответа от памятя в ссответствугяакЕ процессор; 3) комбинированный

» ( 1 ) < 2 i

показатель эффективности 'Г =Т +(l-w)ï , где w - доля запросов па запясъ. разный среднему времени, затрачиваемому на получение доступа к ппкяти и (а случаи чтеняк) на возврат ответа; а также такие общэупотребккые показатели производительности, как среднее чксло процессоров, генерирующих удаленные запросы (т.е. активных), И и коэффициент использования пины U.

5

Показано, что точные модели практически непрнкенякы при боль-шпХ N накду экспоненциального роста числа ах состояний. Поэтому для оценки указанных критериев разработаны прзблхяеенпые нодэли и методы, основание на анализе синхронных сетей очередей (при допущения о статистической независимости последовательных попыток передача одного s того же запроса) я методз анализа разновесного состояния (АРС) . Для нахождения численных оценок показателей производительности получена следующая система уравнений, количество которых не завяси? от чаелг прс-цоссоров N:

К H (1-v) s/t; К vs/t; К - N (l-w)/(Ç t) ;

г ^ w g hg"

К = N /[t(l-p)Ç]; К =» FS /t; X - Ht/y,

a <] s ч g

v «= t + F + [l+(ta+l)CJ/CÇ(I-p)] + (1-w)(s+l+Ç"1); Ç-1-7T =U/K, K=K +K , 0 = Л.-(1-Х/Н)" » 1-е"

Ъ a h

В зтях уравнениях К , К я К - среднее число КП, обслуживающих

г w h

запросы на чтение н запись s пытающихся передать ответ; . К^ и К^ -среднее чгсло процессоров, пытающихся передать запрос п <спящях» после неудачного доступа; я, t s t - цикл НП и средние времена (за единицу времени пряиято время передачи по иине) генерации удаленного запроса и анализа запроса, переданного по шине; п - вероят-

* ь

кость отказа в получения ¡якны. а р - вероятность конфликта по доступу к панятк в точно разновосц.1, причем р=(К<_+К +К ) / (N-1), так как удаленный запрос процессора i направляется к НП j (j^i) с вероятностью 1/(Н-1) для всех i,j. Наконец. F отражает вид стратегий: пря Простой Стратегии Г=ир/(Х-р), при Сложной Стратегии

Г, п г- п \ и о -ч

пз xj +а2р 1 j^l-p aj+a3p 1 2j/(l-p), а для произвольной фу-

пхцал обратной связи и(п) F= £ га(п) рп. Решая эту смс ому уравке-

П«1

ндй, получаем значения показателей производительности:

Т<1} » [l+(l+tJÇ]/tÇ(l-p>] + F, Т(2> = 1 + K/U. (5)

Принимая во внямакио справедливость выражения (ü) для произ-

вольной стратегия доступа, приходим к следующему аыаоду: если

*

найдено оптимальное значение ш=Н (дающэе кннпкук Т ) для Простой Стратегки, то нельэя улучпить это значение Т , вводя стратеги» с любой другой фунхадкей ш(п), так как значение т' при (l-p)F/p*H больше, чем при Простой Стратегии с т=М. Тем но кенэо, можно попытаться улучшить такие пажкыа показатели производительности, как дисперсии (Г^, и <т2 времен t(Ii (число тактов, требуемых для доступа к памяти, сродное значение которого равно Т<п), t<2) (число тактов, требуемых для возвращения ответа, со средник Т1"") и t*-=

( 1 ) / 9 J •

*»t +(l-w)t ~ (со средним Т ) клк вероятность Р(Т ) того, что время t*, затрачиваемое на получение доступа к памяти и (при чтении) возвращение ответа, не превыаааот Т •

При произвольной функции а(п) кнеек

<ra>4r*+(l-w)a*. «г* - ль/(1-тгь)г,

- § + (1-р) Е Г(п+1)у + Z n(i) - У/(1-р) - г]* Рп,

где Ф » п /[(l-pj (1-jt )а1 ж у =l+t +l/(l-rr ). примем пса Простой

ь г b 2 а

Стратегии о- = Ф+Р[ (зг+и) / (1-р) ] . Наконец, вероятность Р(Т ) определяется выражением P(Tf) (l-w)P(T )+wP (Tf), где 2 p„ ~ значения этой вероятности, соответственно, для запросов на чтение и запись, причем

т

г

р

<V - (1-Р) Е Е р" (!-*,) <<»>,

t. -t + 2 n:f(n)io г 4 '

Рг(Т)-(1-р) Е Е рп(1-ль)п"2 '<?1а1)+л~1т%{и)'*.

где при Простой Стратегия у(0)=ъ --Ь -2, г>(п)=у(п-1)-т-Ъа-2 для п>0, а при произвольной функции п(п) вхесто константы ш следует подставить эту функцию.

Обширные численные результата показывают высокую скорость, хорошую точность и чувствительность разработанных приближений: в

»

частности, относительная погрешность оценки основного показателя Т меньше 5% для любых значений ПОС иге н параметров нагрузки t к V. Однако, при екз ошибка приближения может достигать 20%, основной причиной чего является использование допущения о статистической независимости последовательных попыток передачи одного и того же запроса.

При анализе Простой Стратегия выявлена следующая корреляция

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

Исследовано, как влияет на значения дисперсии сг2 и вероятности Р(Т ) применение Сложной Стратегии вместо ПростоЗ, к показано, что таким образом можно достичь существенного улучшения данных показателей при сохранения оптимальным значения основного показателя Т . Более того, получен следующий интересный и неочевидный результат: а случав высокой нагрузки для минимизации дисперсии <тг к для максимизации Р(Т(.) при т , лишь немного большем, чем среднее оптимальными являются прямо противоположные варианты Сложной Стратегия. Для минимизации дисперсии сг2 следует установить большое значение ПОС только для первой попытки доступа и одинаковые мелью значения ПОС дли остальных попыток, в то время как для максимизации Р(Т } при указанных Т , наоборот, следует установить для первой попытки малое значение ПОС, а затеи - одинаковые большие значения.

С целью синхронизации выполнения параллельных ' процессов в многопроцессорных вычислительных системах используется механизм критических ресурсов (5СР). Если процесс, пытающийся получить доступ к 1СР, находит его занятым, он должен ждать его освобождения. Это озшданяв кожет быть организовано двояким образом: либо находясь в активном состоянии, т. е. занимая некоторый процессор, непрерывно пытаться получить доступ к КР - такая стратегия называется спиннингом, либо освобождая процессор и переходя в состояние блокировки до тех пор, пока не будут одновременно свободны требуемый КР и некоторый процессор - эта стратегия называется блокированиям. Очевидны недостатки каждой из этих стратегий. При спиннинге соответствующий процессор пребывает в непроизводительном простое на все время ожидания доступа. Блокирование процесс?, зедет к перезагрузка кэш-памяти соответствующего процессора, что в отношении производительности соответствующего процессора эквивалентно потере Ь тактов его работы. Возможны компромиссные стратегия спиннинга

В блокирования, при которых время спиннинга ограничивается некоторый случайным значением t (со сродник Т ), по достакенин которого начинается процесс блокирования. Тогда предельный» стратегиями доступа к КР являются чистый спиннинг с ^ когда спиннинг ведется до конца, т.е. до успешного доступа к КР, а немедленное блокирование с когда процесс переходят о состояние блокировки после первой ясо безуспешной попытки доступа.

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

Предлагаемая модель включает 3 статистически идентичных процессов, выполнение каждого из которых можно рассматривать как чередование фазы вычислений на процессоре (все N процессоров также идентичны) с доступе« к одному из Н статистически идентичных КР, каждый нз которых выбирается с вероятностью 1/М. Выполнение процесса заканчивается фазой освобождения процессора, после которое процесс проводит некоторое время е состоянии обдумывания (среднее значение этого вреиенв равно а затеи снова пытается ка-

чать фазу вычисления на любом свободном процессоре. Если свободных процессоров нет. этот процесс становится во входную очередь к МВС.

Каждый процесс пс окончании фазы вычислений (среднее пронк которой равно И^1) с вероятностью требует доступ к некоторому

КР, а с вероятностью д заканчивается, освобождая процессор (сред-

р

нее время, затрачиваемое на освобождение, равно ¿г'1)- Если время ожидания доступа к КР достигло предельного времени спиннинга, процесс покидает очередь а после перезагрузки кзш-памяти я освобождения соответствующэго процессора в течение в сроднен Тс тактов помещается в очоредь блокированных запросов, относящуюся к требуемому КР. После использования КР (среднее время которого равно й"1) процесс с вероятностью заканчивается, освобождая процессор, а с вероятность» начинает новув фазу вычислений. Предполагается

экспоненциальный характер распределений времен всех фаз процесса.

Основным показателем производительности является коэффициент использования КР и. в силу однородности нагрузки одинаковый для всех КР, т.е. и=»Х./М, где Ь - среднее число занятых К.Р. Другими показателями являются средние количества процессов в фазах вычисления Р. обдумывания О и освобождения процессора I*. Эти показатели

связаш следующими равенствами:

P(l-q^) - utb; + «у-« рР - - V^Q. (S)

к можно ограничиться нахождением величины L яля Р, в затем вычислять значения остальных показателей, используя (6).

В отиопзэнаи показателя Р спразодлвэо неравенство Р а р<0> « =» rain{P ,Р }, где Р «ц K/[(i (1-q )]. ар - значоиио Р а случае

II ti р i* i

бесконечно малого времен» доступа к JCP. В случае палого числа КР М, используя асимптотическое приближения (4) п проводя декомпозицию по Нортону, доказывается. что при больном числе процессоров я любых значениях параметров системы справедливо Р^ » Р(0). где Р^ -значение Р з случае чистого спиннинга ко всем КР. Слодоваггльно, з этом случаз никакая другая стратегия не моаот значятопьно улучшать производительность КЗС по сравношгп с чистым спиннингом, т. е. чистый спиннинг - почти оптимальная стратегия для больгзкх КЗС с ограниченным числом КР. Этот синод подтвержден имитационным моделированиям, иоказавпим, что при малых (накладных расходах на пэре-кпягчеино процессов) максимально© улучеониа коа£>фз:цааита использования ЮР U, достигаемое путзм замены стратегия частого спиннинга na оптимальную стратегия, очень мало з составляет 1%; если жо Т^ велико, то прг малой врэмани спиннинга значение и сунвстяенно какыга, чем при чметок спвиияиге.

Пусть теперь и велико. При чистом спиннинге, применяя асимптотическое приближение (3), получаем

L « ИЗ/(M-1+S), (7)

где 8 - сроднее чясло процессов, ожндаж^их обслуживания в КР няа узеэ обслуаяэежгяхся, причем 5«=ain (Ss }, а 8д и - коркп уравнений

дв{п-за) - М, и sa/(H-i+3a) с - ^/{«c+u-vv*;1}-3~üs » nt я sj/[tí1(K-n-sj)3 с

зря немедленном блокирования согласно методу АРС в дополнена® к (7) яспользувм: ЛКбо урвВПвПЧв

íit (J-S-Щ - íi, L (8)

(если получаемые показателя удовлетворяют неравенству I^H+p+RsH), либо ио(Я-L-H)"Цгдэ среднее число процессов в фазе переключения контекста W=M,La/(»»,**), a h^-tT1. В случае сяеваяяоЯ стратеги*

спиннинга й блокирования, когда ОсТ^сш, (7) дополняется либо ура-вненвем (8) (если в результате З^+Ь+К+Р+К^К), либо и (И-Ь-^В = где /ц , Да=Т~1, а среднее число процессов оакдавд-

щих обслуживания в состояния спиннинга, - корень уравнения

д Ьг/М - д 3 + II Ь Э /(Ь-Х+5 ).

1 не 1 I я

Реиая эти системы уравнений при различных значениях среднего предельного времени спиннинга Т^ я фиксированных значениях остальных систен*£ых параметров, нахедик оптимальную стратегию доступа. Приведенные численные примеры такого поиска показала хорошую точность разработанных приближений," обеспечивающих высокую скорость расчета и примерную оптимальность найденных стратегий доступа. Оказалось, что если значения Ь при частом спинингэ (Ь) к ненецла-

ннои блокировании (Ь ) значительно отличаются, то либо чистый спи-

ь

вникг (когда Т велико я, следовательно, Ь >Ь ), л»бо немедленное

с я Ь

блокирование (когда т^ мало й, следовательно, ь <1»ь) является почте оптимальной стратегией. В этом случае можно кзбохшть поиска оптик&льного значения Т^, многократно репая системы уравнений, определенных в предыдущем подразделе; достаточно найти значения Ь_ и Ь по соответствующих приближениям я выбрать из них максимальное.

Разработанные приближения успешно применялись для решения следующей практической задачи. Рассмотрим базу данных, поддерживаемую К-процессорной системой, к которой осуществляют доступ Л независимых пользователей. Эта база данных может быть разбита на К частой, доступ к каждой из которых контролируется отдельным КР. Прк помощи приближений найдоко минимальное число КР (т. е. частей базы данных) вместе с оптимальней стратегией доступа, обаспечнваю-щкх время доступа к базе данных, не превышающее некоторого заранее выбранного значения, причем правильность выбора подтверждена к::к-

тшдизй.

Пятая глава посвящена анализу таких особенностей современных Локальных вычислительных сетей (ЛВС), как широко распространенная архитектура «клиент-сервер» а приоритетные методы доступа к обшей среде передача (общему каналу).

Приоритет любой станнки ЛВС можно задавать ко только адресом. но к местом ее подключения к каналу и временем реакцяк на нзмене-::«а состояния канала. На совместной использовании зтех способов основано децентрализованное пространственно-временное управление

(ДПЗУ) доступом к каналу. Рассмотрим сеть с абонентами п разных категорий срочности, требующн;:и передача по каналу к образующими согласно многоуровнему алгоритму ДПВУ гн-1 уровень приоритета. Рассмотрим два варианта алгоритмов ДПЕУ.

Согласно алгоритму ДПВУ со сменой приоритетов после каждой передачи по каналу (ДПВУ КП), станция на 1-к уровне приоритета прослуиивает канал а ожидания паузы длительность» т = Т + 2г (1-17п), где Тп - минимальная обнаруживаемая пауза, определяемая аппаратным обеспечением; 2т - время прохождения сигнала по двум подканалам. Если есть какая-то станция более высокого приоритета, то ока начнет передавать несущую раньсо. к рассматриваемая станция нэ дождется паузы Т^ Если пауза длительностью Т( все же наступает (нет более приоритетных станций), то данная ста?щкя начинает борьбу за канал - посылает з канал несущую. Если затем в течение 2г станция «не услышат слева» по подканалу чузкую несущую, то она начнет передачу сообщения. В протявиом случае борьба за канал проиграна. Станция, прсигравяиэ борьбу г;з 1-м уровне приоритета, переходят на более высокий, (±—1)-й урорэпь приоритета. Исключения составляют станция на 1-м приоритете, которые сохраняют тот же приоритет. Станция повышает свой уровень пряорктета, переходя на (1-1)-Л уровень, также в ток случае, когда она обнаружила паузу То и но дождалась паузы Т( (±>1)- Таким образом, после любой успепгной передачи в сети всо станцяк, кроме тех, которые находятся на 1-ом приоритете, повыпают свой приоритет. Стакцяп ка 1-ом приоритете переходят на 0-й приорятет только в том случае, когда последняя нз станций на 0-м приоритете закончат передачу в канал.

В отличао от алгоритма ДПВУ КП, при алгоритме ДПВУ со сменой приоритетов пря отсутствии станций кг более высоком уровне пряоря-тэтов (ДПВУ ОУ) стакцна на любом 1-м уровне приоритета переходят на (1-1)-8 уровень, как только на последнем нз остается ка одно» стакцзя (1ы).

Моделью приоритетных процедур доступа к общему каналу является однолинейная С.ЧО, в которой очередь разделана на зоны О. 1, 2, . . . п, соответствующие п уровням пргсритетов доступа к каналу. В 1-а зону (1*0) поступает простейший поток требочанмй 1-5! категория срочности с интенсивность» А . Он соответствует суммарному потоку требований 1-й сропноста на передачу по каналу, поступающих на все станции сотн. Холвчестзо мост для ожядаигя в кгядой из зон не

ограничено. Длительность обслуживания О (время занятости какала передачей пакета с учетом пауз) фиксировано. Без потере общности

п

предполагаем 0«»1 и Х- £ А <1.

1-1

На основе описания поведения этой СМО случайным регенерирующим процессом с зависимыми циклами регенерации, в п.6.1 разработан метод расчета среднего времени 9 огхидакия 8 очереди для требований 1-й категории срочности, называемых 1-гребоваииянн. Б частности, для случая п=0 я Аз-0 имеем при алгоритме ЯПВУ КП:

И1 - А/[2(1-Х)] + х[ (1-Х)(е г-1) - 2Хг ^/2;

Йг - А/[2(1-А)] + X} X (1-Х) (в^2-1) - 2А. ]/(2Аа).

Получены тешке оценки максимального времени т*""1 оказания требований, срочность которых убывает с росток 1. Предположим сначала, что К источников требований (узлов ЛВС) разделены на группы по категориях срочности, т.о. каждый источник порождает требовании только одной срочности. Тогда

л

Т°в* (ОХИ)«**; Т5""" (ДЛВУ КЛ)■ « 1-1+2(М-1) , 1-17п. п<н-

1■1

И '1+1" ■ '1+1'

ОУ) « Е К1 - т~

.1-1

Г1+П _

- 2, 1»1,п,

I -I

.■»-» к з ]

где ОТП - доступ с чистым относительным приоритетом; и - ^исло источников группы 1; [х] означает наименьшее целое число, большее или равное х. Следовательно, Т"*(ДПВУ ¡СП) > Т""" (ДЕЗУ ОУ). Рассмотрим другую модель приоритетной системы: пусть каждый из И ис~ точников может порождать требование лвбой категории срочности. Кмеек;

т"ж(дпзу кп)»1-1+2(к-1), т"*"(дпву оу)-(1+х) (к-1), 1-17«;

т"*(отп) «» н-д, т"ах(отп) -

В этом случае т"а"{ДПВУ ¡СП) - т"ж(ДПВУ ОУ). • 1

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

о

ЛВС архитектуры «клиент-сервер>, состоящей из N узлов-клвоитов (УК) я сервера, управляющего иерархией устройств общей дисковой памяти. Предусмотрены два способа доступа к файлам панятн сервера: либо весь требуемый файл передается по сети с коммутацией канал-канал, яябо требуемый блок этого файла передается по локальной се-

тя типа Ethernet и Token Ring. В узле-клиентэ (УК) номер i<=l,N выполняется Jt статистически адэнтичных процессов, а аппаратные средства этого УК состоят из процессора я устройств локальной памяти (ЛП). Пыполненяе процесса можно представить как некоторое число чередующихся фаз вычисления на процессоре и доступа к памяти (как к локальной, так я распределенной), после чего процесс переходит з фазу обдумывания, а затем снова возвращается в фазу вычисления. Удаленный доступ процесса к распределенной памяти сервера состоят нз следующих фаз: 1) через устройства сетевого интерфейса данного УК. к сервера запрос посылается по локальной сети в сервер; 2) с некоторой вероятностью требуемый файл считывается из библиотека ' файлоз на магнитных лентах;. ,3) файл .перемешается на верхний уровень дисковой иерархии и приводится в исходный вид, что представляется как некоторое "случайное число чередующихся фаз работы упра-'' вляющэго процессора сервера п доступа к дискам; 4) либо весь фаЗл передается по сети с коммутацией канал-канал, лябо его блок передается з УК по соответствующей сети.

Задавая вероятности доступа, предполагая экспоненциальность распределения времен выполнения фаз вычисления и доступа к любому устройству иерархической памяти и сети связи и представляя процессы/запросы/файлы от УК с произвольным номером i«l,N траизактами ноазнэнного класса L, получаек модель ЛВС в виде замкнутой экспоненциальной сета очередей с и классами заявок, состоящей нз одно-канальных устройств (с дисциплиной обслуживания PS для процессоров ts FIFO для других узлов) и IS-станций. Выписывая мультипликативную формулу стационарной вероятности состояния этой сети очередей, получаем явные выражения для таких показателей производительности рассматриваемой ЛВС. как среднее число процессов в фазе обдумывания калдого УК, пропускные способности разных подсистом ЛВС по запросам от разных У 1С я коэффициенты использования ее устройств.

В реальных ЛВС, несмотря на больиое обшее число УК N, число УК п. обеспечивающах параллельное выполнение большого числа проце- ■ ссов к, соответственно, обладающих развитой подсистемой ЛП. сраэ-нятельно невеляко В каждом аз остальных N-n УК (ко'^рыэ обычно являю!ся персональными компьютерами) может одновременно выполняться только 1 процесс, т. о. J^l для ien+l,N. Это позволяет существенно упростить зектор-состояние сети, объединяя заявки классов

n+l,N о R ткпов (т.е. в расснатркваемой модели теперь только n+R классов заявок), а также разделяя все устройства ЛП в каждом из УК а зсо диски сорвера на группы равномерно нагруженных устройств.

Приведенные численные результаты показывает эффективность применения разработанного метода для поиска возможных «узких нест».

Шестая глава посвящена анализу линейных протоколов, регланен-тирующих следующее функции управления передачей данных ножду смежными узлакв глобальной сети: установлена«, поддержание к разъединение связя кех:ду узлами, защита с; ошибок а отказов в приеме, согласование скоростей работа смежных узлоЕ. Совокупность данных, передаваемых между смеанымя узлами свти как одно целое, называется каàpou. Ecus в полученной информационном кадре не обнаружено ошибок s п принимающей узле имеется свободой буфер, то это означает правильный прэом кадра, и узлу, выславпему кадр, посылается положительная кватапцкя (в противном случае - отрицательная квататщкя).

Протоколы различаются по току, используется в них передача кадров с упрежденявн правильного приема или нет. В первом случае узлу-отправятели разрешается передача нескольких кадров подряд до прихода первой квитанцка. Серия кадров, переданных подряд между двумя последовательно поступавшими квитанциями. называется гшелоном. Этому случав соответствуют, напргкер, протоколы HDLC, SDLC, BDCMP. Во втором случав узел-отправитель ждет получения квитанция после передачи каждого информационного кадра (например, протоколы ТМК, BCS). Протоколы первого ткпа называются конвейерными, а второго - аьартстопкыми.

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

Объектами исследования в гл. 6 являются конвейерные протоколы HDLC, DDCHP к SDLC, а также обобщенные протоколы <р ^ и <р . При протоколе ç>j б условиях. когда в каждом узле есть пакеты, подлежащие передаче другому узлу, осуществляется взаимная передача эшелонов наксанальноё длины, после чего узлы обмениваются квитанциями. Есля

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

Рассмотрим два снежных узла, соединенных дуплексной связью. Пусть i-3 узел (1=1,2) можот послать подряд не белее W информационных кадров другому узлу, но дожидаясь квитанции ( - максимальная длина эшелона кадров). Считается, что в узле з любой момент находятся по крайней мере один пакет для передачи другому узлу. Это позволяет проанализировать возможности протоколов. Временем распространокия сигнала по каналу пренебрегаем. Предположим также, что времоиа передачи отдельных кадров из i-ro узла незавиеккн и имеют экспонекцяальноа распродоление со средним Т -t^+t^, где t* и

t1^- средние времена передачи частзй кадра с данными я с квитанцией.

Основные критерия качества: - вероятность занятости какала i передачей информационных кадров (активность канала); степень загруженности канала i передачей информационных частей кадров:■ pj=gj f t®/Tt ] ; пропускная способность i-oro канала 91~9l/'Tl я общая пропускная способность звена узел - узел в-е^+в^.

Рассмотрим протоколы сначала без учета ошибок или отказов при приеме кадроз. Анализируя марковский процесс, моделирующий протоколы HDLC, SDLC и DDCMP, получаем следующее выражение для степени

загруженности 1-го канала при протоколе HDLC

и

Р, (HDLC)(t'j'/Tj) [1-(Т^(Т +Т2) ')],

гдэ 1-1 ^ пря f"?' и пропускной способности звена узел - узел 12 При 1- 1, '

в ( HDLC ) = (1/Tt)[l-(T2/(T+T2)) l3 + (l/T2) [l-C^/^+TJ) 2].

Выражения для критериев качества протоколов SDLC и DDCMP • аналогичны. Необходимо только учитывать различия в структуре

— —д

кадроч, которые приводят к различным значениям Т я

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

= (Wj + W2)/T(Ç>1). (9) .

где

[/ \ И +1 / \ 2 ^ , е

ИГГ1/(Ц1+,1г)] 1 [^Г1)'!"1 I I *

ы 1 - г

х 1 / ] <И3+з)1/вЛ,

в »о '

где И -Т \ а 5* - сродна«, время, необходимое для обмена квитанциями. Аналогично рассматривается протокол

Рассмотрим протоколы с учетом постоянной вероятности р ссаиб-

„ (»)

ки в кадре, переданном по х-иу каналу. Пусть . д , - вероятность

п к

того, что нз к отправленных из 1-го узла кадров будет иорно принято п кадров (п л к). Кз (9) следует, что пропускная способность

в знелона каксинальяой длины.

При селективном отказе пропускная способность протокола

равна

всвп-фх) " tKi(1 " р1} + ~ Р2) l/ïiî',).

а при групповом отказе:

протокола С

О(^) [<"

L J

У .

(1)

где ди » L по nW

в (ф )> гр '

1-р,

рг

г

[1-(1-ра> 2

Аналогично исследуется протоколы HDLC a

Специальный интерес представляет случай, когда характеристики потоков кадров в обоих направлениях одинаковы (сккнетричггыо потоки), т.о. т, 'ij^VI^Vî, Тогда для i»l,2 ггрк отсутствии потерь кадров

(HDLC) - (1 - 2"Н)/Т, 0^) - g^p^/T.

где

g, (HDLC) =1-2"*; g, (e^-l/R-iR-t*/?)/«], gs (?,)».l/ri+tk/râ), (10)

h-Î -

В

<W + s)i

(1/2)"((W - l)i)_1 l (1/2)"-il-

Соответетвуюгака формулы прч учете опзибок в кадрах (р »» р •» р)

сведены з табл. 1. Из (10) можно определить граничное услсэио для относительной эффективности протоколоп <р н <рг. Действительно,

/е<?д - д/^/д,««»,) - (2И -к ± + (ии/л)],

гда у\ «■ ц??. т. а, протокол ?> эффективнее протокола при 7)>К,

Таблица 1

д. Селективный отказ . Групповой отказ

д (ИОЬС) (1-р)[ 1-(2-р)"И) (1-р)3 {1-[(1-Р)/(2-р)]н>

(1-р) [2-(!*-£*/?) /Щ 1-р ,, /1 ч"/Г, к-^/т] РН [1-(1-р)] /[2-

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

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

3 большинстве протоколов сквозного управления потоками данных з качество основного управляемого параметра используется размер эякя Т.\ рапкый числу пакетов ила сообщонай, которые но;ано передать !Одряд, из дояздаясь квитанций, я соотвотстзукщая схема ограиячэ-нагрузка на ЛС называется нежанизгюи окна.

В качестве другой схены ограничения нагрузки на ЛС автором предложен механизм семафора в зависимости от состояния буферной памяти адресата (БНА), основанный на установлении в отправителе с помощью соответствующих управляющих команд одного из двух режииоЕ работы: «Передача» ял к «Остановка».

При возрастании заполненности БЯА до уровня г* отправителю посылается команда, устанавливающая рожим «Остановка». Если затем заполненность БПА понижается до уровня г", то адресат посылкой специальной команды устанавливает в отправителе режим «Передача». Границы г* к г® должны выбираться таккк образом, чтобы экстремальные отклонения заполненности БПА практически находились в пределах некоторого диапазона (х ,х ), где хг>г*, xt<r*. обеспечивая требуемой средний уровень г заполнения БПА. Разработана следующая система граничных условий для значений х4, г* и г":

Г1 * Г2? ** ^а(ТП + О + V + m7*i ° S V

г"2 " " + Ткв> + V " + Ткв>'

где д ид - интенсивности входного потока к выборки пакетов из

8х 'в Л * _

БПА; Тп (Т ) и т (Ткз) - минимальная (средняя) задержка пакетов и квитанций. При определения границ . г® к г'г из мкокоства значений х . удовлетворяющих приведенным условиям; следует выбрать иккика-лыюо. Имитационное моделирование показало, что описанный мотод приближенной оценки границ г® к г* дает хорошие результаты. Выбираемые границы обеспечивали работу ЛС в оптимальном режиме заполненности БПА с ошибкой до 5%. Фактическая пропускная способность ЛС достигала 90% максимально возможной при достаточно небольшой среднем времени доставки пакетов.

Параметры V?, г* и г* опксаикых механизмов ограничений нагрузки фиксируются. основываясь на средних значениях кнтопсмвкост&Й потоков. Однако на практике еходкшко потока к интенсивности потребления пакетов абонентами-адресатами характеризуются резкими колебаниями. Поэтому необходимы адаптивнее неханкзкы ограничения нагрузки, одним кэ которых является предложенный автором кеханзгзк семафорной корректировка размера окна, согласно котораку имеются два границы заполненности БПА: г" к г", га>г®, ПрЕ поступлений в

1 2 3 1

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

отправителю посылается конанда, уменьшающая размер окна на единицу. Если заполненность БПА меньше величины г", то соответствующая команда увеличивает размер окна на единицу. Команды корректировки размера окна посылаются вместе с квитанциями. Если заполненность БПА находится между г® и , то размер окна не изменяется.

Моделирование этого механизма показало, что он достаточно эффективен при значениях параметров г" и г®, равных соответственно ] (0,3+0, 4)Кг [ и ] (0,65+0,75)Rz[, где - число буферов у адресата, а ]х[ - целое число, ближайшее к х. Механизм обеспечивает стабильную работу ЛС в области удовлетворительных значений среднего времени доставки пакетов и фактической пропускной способности соединения. При этом частота отказов на входе в адресат остается низкой. Основным достоинством данного механизма можно считать стабильность в обеспечении желаемых характеристик.

В гл. 7 также описываются и систематизируются существующие аналитические модели механизмов сквозного управления, в частности:

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

2. Для оценки эффективности механизма окна в архитектуре SNA и механизма скользящего окна применяется модель ЛС, построенная яа осного декомпозиции по Нортону.

3. Модель стартстопного сквозного протокола для анализа влияния длительности тайм-аута на пропускную способность ЛС, на среднюю задержку пакета в буферной памяти отправителя и на вероятность заполнения ограниченной буферной памяти отправителя.

4. Модель двух схен повторных передач пакетов: локальное повторение пакетов из предыдущего связного процессора (СП-повтор) я сквозное повторение из узла-отправителя (ГЗК-повтор).

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

ограничения нагрузки, является величина "W-m, а не абсолютное значение W.

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

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

Приложение к работе посвящено практической реализации результатов диссертации. Оно содержит описание структуры иерархической информационно-вычислительной сети архитектуры «клиент-сервер», реализуемой в Государственной Духе РФ, и расчет производительности варианта этой сети. Разработка структуры этой сети и расчет ее производительности, позволивший выявить «узкие мвс^м> я таким образок определить стратегию дальнейшего развитая сети, проведаны на основе теоретических результатов, полученных в гл. 2 и 5.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

ступными либо только «собственным», либо всем процессорам.

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

?.. 3. При анализе дискретных моделей МВС для случаев однородной нагрузки и локализованных обращений получены приближенные оценки среднего числа занятых модулей памяти.

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

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

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

4- 2. Приближения, разработанные для значений показателен производительности при большок чнслэ КР, показали. что если этн значения при чистом спннинге я немедленном блокнрованкк значительно отлачаются, то одна аз этих предельных стратегий почти оптимальна.

5. Проведен анализ таккх особенностей локальных вычислительных сетей (ЛВС), как кетоды доступа к общеху каналу к архитектура

•«клмент-сервер». В частности:

5. 1. Для двух алгоритмов децентрализованного пространственно-временного управления доступом к каналу разработан метод расчета среднего и максимального времени ожидания в очереди для требований различных категорий срочности.

5. 2. Для оценки производительности обобщенной ЛВС архитектуры «клиент-сервер» с одним сервером, управляющим доступом к иерархической распределенной памяти, разработана модель я виде замкнутой экспоненциальной сети счэредей, учитывающая различные возможности организации удаленного доступа и получены явные выражения для показателей производительности ЛВС.

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

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

3. Наиболее полное воплощение получение теоретические я практические результаты нашли при разработке системы программного обеспечения МОСТ, предназначенной для построения неоднородных сетей из однородных сетей (или отдельных ЭВМ) произволь: й топологии; .,ри создании ВСКД АН Молдовы и информационно-вычислительных ;етей угледобывающего концерна <ХДБ Соколова- (Чешская республика), Согаицкого Политехнического института (Словацкая республика), в Юсприватизации (г. Москва) и Государственной Думе РФ.

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

МОНОГРАФИИ

1. Богуславский JI. Б. Управление потокани данных в сетях ЭВМ. М. : Энергоатомиздат, 1984. 168 с.

2. Богуславский Л.Б. , Дрожжинов В. И. Основы построения вычислительных сетей для автоматизированных систем. М. : Энергоатомиздат, 1990. 256 с.

3. Богуславский Л.Б. , Ляхов А. И. Методы оценки производительности многопроцессорных систем. "М. : Наука, 1992. 213 с.

СТАТЬИ И ДРУГИЕ ПУБЛИКАЦИИ

4. Boguslavski L., Gelenbe Е. A communication protocol and а problem of coupled queues // In: Performance of Computer Systems/ M. Arato, A. Butrimenko, E. Gelenbe, (ebs). IIASA, North-Holland Publishiing Company, 1979. P.517-523.

5. Богуславский Л. Б. Исследование одного класса систем с групповым обслуживанием // Автоматика к телемеханика. 1980. н£ 1. С. 46-50.

6. Богуславский Л.Е. , Файнберг Е. А. Об оптимальной стратегии включения обслуживающего прибора в одном классе систем с групповын обслуживанием //Проблемы передачи информации. 1980. n£ 3. С.95-107.

7. Boguslavskii L.B., Gelenbe Е. A comaufiication protocol and a problem of coupled queues // Rodst. Sterov. 1980. V.10, Ы^З. P.149-157. (Польша)

8. Богуславский Л.Б. , Дрожжинов З.И., Мартиросян В.А. Анализ сквозного управления потокани данных в сетях ЭВМ // Автоматика и вычнсл. техника. 1980. N° 5. С. 61-69.

9. Башаркн Г.П., Богуславский Л.Б., Штейнберг В.И. Анализ конфликтов в общей памяти мультипроцессорных сксток // Автоматика и вычисл. техника. 1980. N26. С. 27-32.

10. Богуславский Л. Б. , Геленбе Е. Аналитические модели процедур управления звеном передача данных сетей ЭВМ с коммутацией пакетов // Автоматика и телемеханика. 19В0. N2 7. С. 181-191.

11. Богуславский Л. Б. , Дрожжинов В. И. . Мартиросян В. А. Методы и модели управления потоками данных в сетях ЭВМ // Зарубежная радиоэлектроника. 1980. N2 ю. С. 3-27.

12. Богуславский Л. Б., Крейнин А. Я. Анализ влияния аппаратных конфликтов на производительность мультипроцессорных систем // Управляющие системы и машины. 1981. N?2. С.42-47.

13. Богуславский Л. Б. , Мартиросян 3. А. Моделирование алгоритмов изолированной маршрутизации сообщений // Труды VI Всесоюз. шк.-сем. но вычислительным сетям. Москва-Винница, 1931.4. 3. С. 9-13.

14. Богуславский Л. Б. , Дрожжинов В. И. , Семенова Т.А. 'Исследование сотя СЕ1С0П с помощью моделирования и измерений // Автоматика и вычкел.техника. 1983= к£ 2. С. 21-31.

15. Богуславский Л.Б., Коган Я. А. Асимптотический анализ производительности вычислительных структур большой размерности // Автоматика я вычисл.техника. 1S83. N°5. С.73-79.

15. Нашарив Г.П., Богуславский Л. Б. , Самуилов К. Е. О методах расчета пропускной способности сетей связи ЭВМ //В сб. : Итоги науки и техники: Электросвязь. Т. 9. М. : ВИНИТИ, 1983. С. 32-106.

17. Богуславский Л. Б. , Гулевич А. В., Дрэжжинов В. И. Управление передачей данных в интерсетях // Всесоюзное совещание по проблемам управления, Ереван, 1983. К. : Ин-т проблем управления, 1383. С.445-446.

13. Богуславский Л. Б. , Гулевич А.В., Лукьянова Т.Д. Анализ структур й ро;к55нов работы внутрисистемного интерфейса многопроцессорных вычислительных систем // Тез. докл. IV Всесоюз. шк. -сем. «Распараллеливание обработки информации». ФМИ АН УССР, 1983. Ч.3. С.38-42.

19. Богуславский Л. Б. , Коган Я. А. , Лукьянова Т.Д., Ляхов А. И. Система автоматизации оценки производительности мультипроцессорных вычислительных систем // Тр. Jj Всесоюз. созещ. Автоматизация проектирования я конструирования»: Тез.докл. М. : ИПУ, 1983. 4.1. С. 88-89.

20. Богуславский л. Б. Моделирование Параллельной памяти и внутрисистемного интерфейса многопроцессорной вычислительной системы // Тез. докл. II Всесоюз. совещ. высокопроизводительные вьгацелительные системы». Батуми, 1S84. С.165-167.

21. Kogan Ya. A,, Boguslavsky L. В. Performance ^nalysis of memor^ interference in nultiprocessors with private cache memories // Performance Evaluation. 1985. V.5, N°2. P.97-104.

22. Богуславский Л.Б.. Дрожжинов В.И., Петров Ю.А. Принципы конструирования распределенных автоматизированных систем управле-

ния // Проблемы информационных систем. К.1ШТИ, 1985. Ы^З. С.7-3?.

23. Богуславский Л. Б. Проблемы автоматизации проектирования, эксплуатации и развития производственных и учрежденческих локальных вычислительных сетей // Тез. докл. VI Всесоюз.шк. «Многопроцессорные вычислительные системы*. К. : КПУ, 198S. С. 15-15.

24. Богуславский Л.Б., Догадько Г.Г., Кучеров В.П., Сидоренко М. В. , Стекольщик Р.Б. Оценка эффективности и измерения вычислительных сетей мини- и микроэвм с программным обеспечением DECnet ,// Тез. докл. X Всесоюз. шк.-сем. по вычислительным сетям. М.: ВИНИТИ, 1935. 4.2. С. 254-259.

25. Богуславский Л.Б., Кучеров В.П., Столяр А.Л. Сравнительный анализ протоколов DDCKP и HDLC // Тр. X Всесоюзной школы-семинара по .вычислительным сетям. К.: ВИНИТИ, 1SC5. Ч.3. С. 123-128.

26. Богуславский Л.Б., Миноскн В. Г. Анализ методов периодической архивизации информации в двухуровневой памяти вычислительных систем // Тр. Всесоюзного семинара по методам и средствам применения ЭВМ в народном хозяйстве. .4. : НДНТП, 1985. С. 139-143.

27. Богуславский Л.Б., Сидоренко М.В. , Столяр А.Л. Моделирование процедур управления устройствами связи в сетях мини- и микро ЭВМ // Тезисы докладов 4-й Всесоюз. конф. »Вычислительные сетг коммутации пакетов». Рига; НЭЕТ, 1985. Т. 1. С. 61-Б5.

28. Богуславский Л. Б. , Горчаков В.Н.., Долганов А. В., Херсонский М.И. Пакет программ ДАЭС - средство административного управления сетей СМ ЭВМ // Тез. докл. XI Всесоюз. шк.-сек. по вычислительным сетям. М.: ВИНИТИ, 1986. Ч.З. С.220-225.

29. Boguslavsky L.B., Stolyar A.L. Performance analysis of data .Orink and communication device control procedures in distributed micro/minicoapufeer systems. Systea Modeling and Optinization 11 Lect. Note in .Control and^nf. Sci. Springer - Ver. 1386. ы£в4. P.91-101.

30. Boguslavsky L.B., Do'lganov .A.V, Configuration design and management of computer networks // Broc. lOth IFAC World Congress, Munich, 1987. V.4. P.71-75

31. Богуславский Л.Б., Сидоренко М.В. , Столяр А.Л., Тукунов А. Н. Принципы организации, моделирование к измерения программного шлюза СПО МОСТ для неоднородных сетей СК и ЕС ЭВМ //Тез. докл. XXII Всесоюз. шк.-сем. по вычислительным сетям. Москва - Алма-Ата. 1988. Ч.3. С.242-247.

32. Богуславский Л.Б., Подлазов B.C., Столяр А.Л. Анализ методов приоритетного доступа к локальной сети с ограничением на время доставки сообщений // Автоматика и телемеханика. 1989. n2i0. С. 175-12В.

33. Такагя X. , Богуславский Л.5. Библиография книг по анализу очерадой к оценка производительности //Автоматика- и вычнсл. техника.. 1SS2. 3. С. 22-40.

34. Bcgusiavsky L., Harzallah К., Kreinin A., Sevcik К. and А. Vainstein. Cptiwal strategies for spinning and blocking // Journal c£ Parallal and Distributed Computing-.. 1S94. V.21, N'22. P.246-254.

35. Bcguslavsky L.B., Lyakhov A.I., Sevcik K.C. Performance evaluation of client-server distributed information systeas // In Prcc, Int. Ccnf. on Local and Metropolitan Communication Systens (IAN Й MAN). Kyoto, Japan, Dec.1994. P.445-453.

36. Богуславский Л.К., Ляхов А.И., Иевчкк K.C. Сравнительный акали-з стратегий доступа к критическим ресурсам в больших многопроцессорных системах на база асимптотических методов // Автоматика и телемеханика. 1395. н2г. С. 125-140.

37. Богуславский Л. Б. , Ляхоз А.й., Оценка производительности распределенных информационно-вычислительных систем архитектуры <КЯИЕНТ-СЕРП£Р> // Автоматика к телемеханика. 1935. ц£д. C.iG0-i75.

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

В монографии [23 автору принадлежат главы, посвященные анализу особенностей архитектуры соарвмонных локальных сетей, конфигурация их узлов is процедур управления связью. В работах [3, 9, 12, 15, 18,19,211 аитору принадлежит анализ особенностей структуры современных НВС, разработка к-зпрерыэкых и дискретных аналитичэских моделей для оценки производительности ИБС и решение этих полелей с гтомощьзз точ??ых и приближенных методов. В [4,7,10] автор разработал аналитические модели процедур управления звеном передачи данных сетей с коммутацией пакетов; в [б] - модель систень с групповым обслуживанием; в [8,11] - методы сквозного управления а их модели; в [13] - методы моделирования алгоритмов изолированной наршрутнза-цкя сообщений; в [14] - методы исследования и модели сети СЕКОП;

в [16] - обзор современных моделей систем комхутации данных к математических' результатов их анализа; в [17] - математическую модель шлюза; в [22] - принципы конструирования распределенных автоматизированных систем управления; в [24] - методы измерения производительности вычислительных сетей; в [25] - подход к исследованию и формальные модели протоколов ООСМР в. НПЬС; в [26] - анализ методов периодической архивизации информации в двухуровневой памяти вычислительных систем; а [27] - модели управления устройствами связи; а [28] - обзор архитектуры современных сетей ЗВК; в [30] -.методы управления конфигурацией сетей (и предложена их практическая реализация); б [31] - нодель шлюза СПО МОСТ к методика измерений; в [32] - модели приоритетного доступа; в [33] - (совместно с Такагн)■библиография книг по анализу очередей к оценке производительности; в [34,36] - нодели МБС с одним критический ресурсом и множеством однородных критических ресурсов, точные (для первой кодеин) и асимптотические (для второй) катоды эа анализа; в [35,37] - кодель сети архитектуры «клиент-сераар> а точные- катоды ео анализа.

Зах. Тарах 1С0.

117805, Косым» ГСЛ-7, Профсовлим, £5.

Институт аровдем уара»д»ядя.

ВВЕДЕНИЕ

ГЛАВА 1. ПРИНЦИПЫ УПРАВЛЕНИЯ ПОТОКАМИ ДАННЫХ И РЕСУРСАМИ

1.1. Общие задачи и функции механизмов управления потоками данных и ресурсами и методы их моделирования

1.2. Управление в многопроцессорных системах 23 1. 3. Управление в локальных сетях

1. 4. Управление в глобальных сетях 35 Выводы к главе

ГЛАВА 2. АНАЛИЗ КОНФЛИКТОВ ДОСТУПА К РЕСУРСАМ

МНОГОПРОЦЕССОРНЫХ СИСТЕМ

2. 1. Система с полносвязным интерфейсом: непрерывные модели 49 2. 2. Асимптотический анализ моделей большой размерности

2.3. Система с полносвязным интерфейсом: дискретные модели

2. 4. Система с односвязным интерфейсом и блоками локальной памяти

Выводы к главе

ГЛАВА 3. СРАВНИТЕЛЬНЫЙ АНАЛИЗ СТРАТЕГИЙ ДОСТУПА С ОБРАТНОЙ

СВЯЗЬЮ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ

3. 1. Системы с неравномерным доступом к памяти

3.2. Стратегии доступа и критерии эффективности

3. 3. Точные модели и основные допущения

3. 4. Приближенные модели и методы

3. 5. Численные результаты

3. 6. Вывод приближений для дисперсий и вероятностных распределений

Выводы к главе

ГЛАВА 4. УПРАВЛЕНИЕ КРИТИЧЕСКИМИ РЕСУРСАМИ

В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ

4. 1. Описание модели 144 4. 2. Системы с малым числом критических ресурсов

4. 3. Система с большим числом критических ресурсов 158 Выводы к главе

ГЛАВА 5. УПРАВЛЕНИЕ ПОТОКАМИ ДАННЫХ И РЕСУРСАМИ

В ЛОКАЛЬНЫХ СЕТЯХ

5. 1. Анализ методов приоритетного доступа

5. 2. Оценка производительности локальной сети архитектуры «клиент-сервер»

Выводы к главе

ГЛАВА 6. УПРАВЛЕНИЕ КАНАЛАМИ СВЯЗИ

6. 1. Структура линейных протоколов 198 6. 2. Модели линейных протоколов 211 Выводы к главе

ГЛАВА 7. УПРАВЛЕНИЕ СКВОЗНОЙ ТРАНСПОРТИРОВКОЙ ДАННЫХ

7. 1. Методы управления сквозной транспортировкой данных 223 7. 2. Анализ ограничения нагрузки и длительности тайм-аута на ожидание подтверждений в логическом соединении

7. 3. Анализ схем повторных передач пакетов

7. 4. Имитационное моделирование сквозных протоколов

7. 5. Управление передачей пакетов при объединении сетей

Выводы к главе

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

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

В связи с этим проблемы моделирования и оценки производительности ВС и сетей представляют устойчивый интерес: издаются специализированные журналы по данной тематике (Performance Evaluation, Performance Evaluation Review, Computer Performance и др. ); в ведущих журналах типа IEEE Transaction on Computers и Communications of the ACM периодически выходят тематические выпуски, посвященные появлению новых методов оценки производительности; ежегодно проходит множество специализированных международных конференций по оценке производительности и моделированию ВС и сетей.

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

Первые подходы к анализу сетей очередей были даны в работах [8-10] с 1957 г. по 1967 г., однако только с работы [11] в 1971 г. начинается активное использование сетей массового обслуживания в качестве адекватных моделей ВС и информационно-вычислительных сетей. Далее особый вклад в развитие методов анализа и применения сетей очередей для моделирования различных ВС и сетей внесли работы следующих ученых: Bard [12], Baskett и Chandy [13], Busen [14], Kelly [15], Kleinrock [1,16,17], Kobayashi [18,19], Lavenberg [6], Reiser [20], Sevcik [21], Whitt [22], Авен [3,23], Башарин и Бочаров [7], Вишневский и Жожикашвили [24], Головкин [25], Гнеденко и Коваленко [26], Игнатущенко [27], Каган [28], Липаев [29], Майоров [30], Прангишвили [31,32], Самойленко [33], Сокол [34], Якубайтис [35] и др. Широкое использование аппарата сетей массового обслуживания привело к тому, что с 1986 г. стал выходить специальный журнал Queueing Systems; как в нашей стране (в том числе и в Институте проблем управления), так и за рубежом появилось много коммерческих программных систем по расчету сетей массового обслуживания (из зарубежных систем следует отметить QNET4, RESQ, PANACEA и др. ).

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

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

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

ЭВМ и МВС (см. выше), основанных на аппарате теории массового обслуживания и учитывающих влияние первых двух компонент, т. е. параметров оборудования и потоков данных, при простейших видах механизмов управления (или при существенно упрощающих допущениях). В гораздо меньшей степени решена проблема разработки методов оценки производительности для достаточно сложных реальных механизмов УПДР, обеспечивающих высокоэффективную работу современных сетей ЭВМ и МВС. Главная трудность при этом состоит в сильной взаимозависимости поведения различных очередей в соответствующих моделях реальных механизмов УПДР [1,5]. Имеющиеся по этой проблематике публикации в значительной степени разрозненны и отражают, как правило, отдельные частные аспекты указанной проблемы.

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

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

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

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

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

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

Реализация и внедрение результатов. Результаты диссертационной работы были использованы:

- при разработке системы программного обеспечения МОСТ, предназначенной для построения неоднородных сетей из однородных сетей или отдельных ЭВМ) произвольной топологии;

- при создании ВСКП АН Молдовы;

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

Практическое использование результатов диссертационной работы подтверждено соответствующими материалами о внедрении.

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

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

- 10-й Международный конгресс IFAC (Мюнхен, ФРГ, 1987 г.);

- Международная конференция по локальным и городским сетям связи «LAN & MAN* (Киото, Япония, 1994 г. ) ;

- 6-я, 10-я, 11-я и 13-я Всесоюз. школа-семинар по вычислительным сетям (1981, 1985, 1986, 1988 гг.);

- Всесоюз. совещание по проблемам управления (Ереван, 1983 г.);

- 2-е Всесоюз. совещание «Автоматизация проектирования и конструирования» (1983 г. ).

- 4-я Всесоюз. шк.-сем. «Распараллеливание обработки информации» (1983 г.).

- 2-е Всесоюз. совещ. «Высокопроизводительные вычислительные системы» (Батуми, 1984 г.).

- 4-я Всесоюз. конференция «Вычислительные сети коммутации пакетов» (Рига, 1985 г. ) ;

- Всесоюз. семинар по методам и средствам применения ЭВМ в народном хозяйстве (Москва, 1985 г. );

- 6-я Всесоюз.шк. «Многопроцессорные вычислительные системы» (Звенигород, 1985 г.).

Публикации. По теме диссертации опубликовано 37 печатных работ, в том числе следующие 3 монографии:

Богуславский Л.Б. Управление потоками данных в сетях ЭВМ. М. •. Энергоатомиздат, 1984. 168 с.

Богуславский JI. Б. , Дрожжинов В. И., Основы построения вычислительных сетей для автоматизированных систем. М. : Энергоатомиздат, 1990. 256 с.

Богуславский Л.Б., Ляхов А.И. Методы оценки производительности многопроцессорных систем. М.: Наука, 1992. 213 с.

Структура и объем работы. Диссертация состоит из введения, семи глав, заключения, списка литературы и приложения. Общий объем основной части работы составляет 252 страницы машинописного текста, 71 рисунок и 13 таблиц. Список литературы содержит 175 работ. Приложение, посвященное практической реализации результатов диссертации, занимает 22 страницы.

Выводы, теоретические и практические результаты

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

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

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

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

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

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

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

2. 3. При анализе дискретных моделей МВС для случаев однородной нагрузки и локализованных обращений получены приближенные оценки среднего числа занятых модулей памяти.

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

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

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

4. 2. Приближения, разработанные для значений показателей производительности при большом числе КР, показали, что если эти значения при чистом спининге и немедленном блокировании значительно отличаются, то одна из этих предельных стратегий почти оптимальна.

5. Проведен анализ таких особенностей локальных вычислительных сетей (ЛВС), как методы доступа к общему каналу и архитектура «клиент-сервер». В частности:

5. 1. Для двух алгоритмов децентрализованного пространственно-временного управления доступом к каналу разработан метод расчета среднего и максимального времени ожидания в очереди для требований различных категорий срочности.

5. 2. Для оценки производительности обобщенной ЛВС архитектуры «клиент-сервер» с одним сервером, управляющим доступом к иерархической распределенной памяти, разработана модель в виде замкнутой экспоненциальной сети очередей, учитывающая различные возможности организации удаленного доступа и получены явные выражения для показателей производительности ЛВС.

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

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

8. Наиболее полное воплощение полученные теоретические и практические результаты нашли при разработке системы программного обеспечения МОСТ, предназначенной для построения неоднородных сетей из однородных сетей (или отдельных ЭВМ) произвольной топологии; при создании ВСКП АН Молдовы и информационно-вычислительных сетей угледобывающего концерна «ХДБ Соколов» (Чешская республика), Кошицкого Политехнического института (Словацкая республика), в Мосприватизации (г. Москва) и Государственной Думе РФ.

- 305 -ЗАКЛЮЧЕНИЕ

1. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979. 600 с.

2. Satyanarayanan М. Multiprocessors: A comparative study. Englewood Cliffs (N.J.): Prentice-Hall, 1980.

3. Авен 0. И. , Гурин Н. Н. , Коган Я. А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982. 464 с.

4. Фатеев А.Е., Пороцкий С.М., Ляхов А.И. Методика оценки комплексной производительности ЭВМ ЕС // Вопросы радиоэлектроники. 1985. Вып.З. С.42-49.

5. Феррари Д. Оценка производительности вычислительных систем. М. : Мир, 1981. 576 С.

6. Heidelberger P., Lavenberg S.S. Computer performance evaluation methodology // IEEE Trans.Comput. 1984. V.33, N°12. P.1195 -1220.

7. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. М.: Наука, 1989. 336 с.

8. Gordon W.J., Newell G.F. Closed queueing systems with exponential servers // Oper. Res. 1967. V.15, N=2. P.254-265.

9. Jackson J.R. Job shop-like queueing systems // Management Sciences. 1963. V.10, N?l. P.131-142.

10. Jackson J.R. Networks of waiting lines // Oper. Res. 1957. V.5, N=4. P.518-521.

11. Moor F.R. Computational model of a closed queueing network with exponential servers // IBM J.Res.Develop. 1972. V.16, N=6. P.567-573.

12. Bard Y., Sauer C.H. IBM contributions to computer performance modelling // IBM J.Res.Develop. 1981. V.25, N?5. P.562-570.

13. Baskett F., Chandy K.M., Muntz R.R., Palacios F.G. Open, closed and mixed networks of queues with different classes of customers // J.ACM. 1975. V.22, N^2. P.248-260.

14. Busen J.P. Computational algorithms for closed queueing networks with exponential servers // Commun. ACM. 1973. V.16, N°9. P.527-531.

15. Kelly F.P. Reversibility and stochastic networks. N.Y.: Willey, 1980.

16. Клейнрок JI. Коммуникационные сети. M. : Наука, 1975. 256 с.

17. Клейнрок JI. Теория массового обслуживания. М. : Машиностроение, 1979.

18. Kobayachi Н. Modelling and analysis. Reading: Addison-Wesley, 1978. 446 p.

19. Kobayashi H. System design and performance analysis using analytic models // Current trends in programming methodology. Englewood Cliffs (N.J.): Prentice-Hall, 1978. V.3: Software Modelling.

20. Reiser M. A queueing network analysis of computer communication networks with window flow control // IEEE Trans. Commun. 1979. V.27, N=8. P.1199-1209.

21. Lazovska E., Zahorjan J., Graham G., Sevcik K. Quantitative system performance. NJ: Prentice Hall, Englewood Cliffs, 1984.

22. Whitt W. Open and closed models for networks of queues // AT & T Bell Lab.Techn.J. 1984. Vol.63, N=9. P.1911-1979.

23. Авен О.И., Коган Я. А. Управление вычислительным процессом в ЭВМ. М. : Энергия, 1978. 240 с.

24. Жожикашвили В.А. , Вишневский В. М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М. : Радио и связь, 1988. 192 с.

25. Головкин Б. А. Параллельные вычислительные системы. М. : Наука, 1980. 272 с.

26. Гнеденко Б.В., Коваленко И. В. Введение в теорию массового обслуживания. М. : Наука, 1987. 336 с.

27. Игнатущенко В.В. Организация структур управляющих многопроцессорных вычислительных систем. М. : Энергоатомиздат, 1984. 182 с.

28. Каган Б. М. Электронные вычислительные машины и системы. М. : Энергоатомиздат, 1985. 552 с.

29. Липаев В.В. Распределение ресурсов в вычислительных системах. М. : Статистика, 1979. 247 с.

30. Основы теории вычислительных систем / Под ред. С.А.Майорова. М. : Высшая школа, 1978. 408 с.

31. Прангишвили И.В. , Подлазов В. Г. , Стецюра Г.Г. Локальные микропроцессорные вычислительные сети. М: Наука, 1984. 176 с.

32. Прангишвили И.В., Стецюра Г.Г. Микропроцессорные системы. М. : Наука, 1980. 236 с.

33. Самойленко С.И., Давыдов А. А. , Золотарев В.В. , Третьякова

34. B. И. Вычислительные сети (адаптивность, помехоустойчивость,надежность). М. : Наука, 1981. 290 с.

35. Сокол Ю.М. Анализ пропускной способности буферированной многопортовой памяти // Автоматика и телемеханика. 1992. N?3.1. C. 153-163.

36. Якубайтис Э. А. Архитектура вычислительных сетей. М.: Статистика, 1980. 279 с.

37. Башарин Г. П. , Богуславский Л. Б. , Самуйлов К.Е. О методах расчета пропускной способности сетей связи ЭВМ //В сб. : Итогинауки и техники: Электросвязь. Т. 9. М. : ВИНИТИ, 1983. С.32-106.

38. Богуславский Л. Б. Управление потоками данных в сетях ЭВМ. М. : Энергоатомиздат, 1984. 168 с.

39. Богуславский Л.Б. , Дрожжинов В. И. Основы построения вычислительных сетей для автоматизированных систем. М. : Энергоатомиз-дат, 1990. 256 с.

40. Богуславский Л. Б. , Дрожжинов В. И. , Мартиросян В. А. Методы и модели управления потоками данных в сетях ЭВМ // Зарубежная радиоэлектроника. 1980. N=10. С.3-27.

41. Богуславский Л.Б. , Дрожжинов В. И. , Петров Ю.А. Принципы конструирования распределенных автоматизированных систем управления // Проблемы информационных систем. МЦНТИ, 1985. N=3. С.7-37.

42. Богуславский Л. Б., Дрожжинов В. И. , Семенова Т.А. Исследование сети СЕКОП с помощью моделирования и измерений // Автоматика и вычислительная техника. 1983. N=2. С.21-31.

43. Богуславский Л.Б., Ляхов А.И. Методы оценки производительности многопроцессорных систем. М.: Наука, 1992. 213 с.

44. Богуславский Л. Б. , Мартиросян В. А. Моделирование алгоритмов изолированной маршрутизации сообщений // Тр. YI Всесоюз.шк. -сем. по вычислительным сетям. Ч. 3. Москва-Винница, 1981. С.9-13.

45. Такаги X., Богуславский Л. Б. Библиография книг по анализу очередей и оценке производительности // Автоматика и вычислительная техника. 1992. N° 3. С.22-40.

46. Boguslavsky L.B., Dolganov A.V. Configuration design and management of computer networks // Proc. 10th IFAC World Congress, Munich, 1987. V.4. P.71-75

47. Башарин Г. П. , Богуславский Л.Б., Штейнберг В.И. Анализ конфликтов в общей памяти мультипроцессорных систем // Автоматика и вычислительная техника. 1980. N^ 6. С.27-32.

48. Богуславский Л.Б. Моделирование параллельной памяти и внутрисистемного интерфейса многопроцессорной вычислительной системы // Тез. докл. II Всесоюз. совещ. «Высокопроизводительные вычислительные системы». Батуми, 1984. С. 166-167.

49. Богуславский Л.Б., Коган Я. А. Асимптотический анализ производительности вычислительных структур большой размерности // Автоматика и вычислительная техника. 1983. N^5. С. 73-79.

50. Богуславский Л.Б., Крейнин А. Я. Анализ влияния аппаратных конфликтов на производительность мультипроцессорных систем // Управляющие системы и машины. 1981. N=2. С.42-47.

51. Богуславский Л.Б. , Ляхов А. И. , Шевчик К.С. Сравнительный анализ стратегий доступа к критическим ресурсам в больших многопроцессорных системах на базе асимптотических методов // Автоматика и телемеханика. 1995. N?2. С. 125-140.

52. Богуславский Л.Б. , Миносян В. Г. Анализ методов периодической архивизации информации в двухуровневой памяти вычислительных систем // Тр. Всесоюзного семинара по методам и средствам применения ЭВМ в народном хозяйстве. М. : МДНТП, 1985. С. 139-143.

53. Boguslavski L., Greenberg A.G., Jacquet P., Kruskal С.P.,

54. Stolyar A. Models of memory interference in multiprocessors / Rapport de Recherche N=1469 of Institute National de Recherche en Informatique et en Automatique, France. Juin 1991. 68 p.

55. Boguslavsky L., Harzallah K., Kreinin A., Sevcik K., Vainstein A. Optimal strategies for spinning and blocking // CSRI Tech. Rep. 277, Univ. of Toronto. Dec.1992.

56. Boguslavsky L., Harzallah K., Kreinin A., Sevcik K., Vainstein A. Optimal strategies for spinning and blocking // Journal of Parallel and Distributed Computing. 1994. V.21, N=2. P.246-254.

57. Kogan Ya.A., Boguslavsky L.B. Performance analysis of memory interference in multiprocessors with private cache memories // Performance Evaluation. 1985. V.5, N^2. P.97-104.

58. Богуславский JI. Б. Проблемы автоматизации проектирования, эксплуатации и развития производственных и учрежденческих локальных вычислительных сетей // Тез.докл. VI Всесоюз. шк. «Многопроцессорные вычислительные системы». М. : ИПУ, 1985. С. 15-16.

59. Богуславский Л.Б. , Кучеров В. П. , Столяр А.Л. Сравнительный анализ протоколов DDCMP и HDLC // Тр. X Всесоюз. шк. сем. по вычислительным сетям. М. :ВИНИТИ, 1985. Ч. 3. С. 123-128.

60. Богуславский Л.Б. , Ляхов А.И., Оценка производительности распределенных информационно-вычислительных систем архитектуры «КЛИЕНТ-СЕРВЕР» // Автоматика и телемеханика. 1995. N=9. С.

61. Богуславский Л.Б., Подлазов В.С., Столяр А.Л. Анализ методов приоритетного доступа к локальной сети с ограничением на время доставки сообщений // Автоматика и телемеханика. 1989. N° 10. С.175-186.

62. Boguslavsky L.B., Lyakhov A.I., Sevcik К.С. Performance evaluation of client-server distributed information systems // In

63. Proc. Int. Conf. on Local and Metropolitan Communication Systems (LAN & MAN). Kyoto, Japan, Dec.1994. P.445-459.

64. Богуславский Л. Б. Исследование одного класса систем с групповым обслуживанием // Автоматика и телемеханика. 1980. N^ 1. С.46-50.

65. Богуславский Л.Б., Геленбе Е. Аналитические модели процедур управления звеном передачи данных сетей ЭВМ с коммутацией пакетов // Автоматика и телемеханика. 1980. N^7. С. 181-191.

66. Богуславский Л. Б.,Файнберг Е. А. Об оптимальной стратегии включения обслуживающего прибора в одном классе систем с групповым обслуживанием // Проблемы передачи информации. 1980. N^3. С. 95-107.

67. Boguslavski L., Gelenbe Е. A communication protocol and a problem of coupled queues // In: Performance of Computer Systems

68. ASA, North-Holland Publishiing Company, 1979. P.517-523.

69. Boguslavskii L.B., Gelenbe E. A communication protocol and a problem of coupled queues // Rodst. Sterow. 1980. V.10, N=3. P.149-157. (Польша)

70. Богуславский Л.Б. , Горчаков В. М. , Долганов А.В. , Херсонский М.И. Пакет программ ДАЭС средство административного управления сетей СМ ЭВМ // Тез.докл. XI Всесоюз. шк.-сем. по вычислительным сетям. М.: ВИНИТИ, 1986. Ч.3. С.220-225.

71. Богуславский Л.Б., Гулевич А.В., Дрожжинов В.И. Управление передачей данных в интерсетях // Всесоюз.совещ. по проблемамуправления, Ереван, 1983. М. : Ин-т проблем управления, 1983. С. 445-446.

72. Богуславский JI. Б. , Дрожжинов В. И., Мартиросян В. А. Анализ сквозного управления потоками данных в сетях ЭВМ // Автоматика и вычислительная техника. 1980. N=5. С. 61-69.

73. Богуславский JI. Б. , Сидоренко М. В. , Столяр A. J1. Моделирование процедур управления устройствами связи в сетях мини- и микро ЭВМ // Тез. докл. 4-й Всесоюз.конф. «Вычислительные сети коммутации пакетов». Рига: ИЭВТ, 1985. Т.1. С.61-65.

74. Tanenbaum A. S. Computer networks. Englewood Cliffs (N.J.): Prentice-Hall, 1981. 517 p.

75. Шеннон P. Имитационное моделирование систем искусство и наука. М.: Мир, 1978. 418 с.

76. Вишневский В. М. Теория сетей массового обслуживания и ее применение для анализа и синтеза вычислительных систем и сетей // ТР- VI Всесоюз.шк. «Многопроцессорные вычислительные системы»: Тез.докл. М: ИПУ, 1985. С.17-18.

77. Closs F. Packet arrival and butter statistics in packet switching mode // Proc. 3rd Data Communications Symposium. St.

78. Petersburg, USA, 1973, Nov.13-15. P.12-17.

79. Феллер В. Введение в теорию вероятностей и ее приложения. Т. 1. М. : мир, 1964. 500с.

80. Кокс Д. , Смит У. Теория очередей. М. : Мир, 1966. 218 с.

81. Ховард Р. Динамическое программирование и марковские процессы. М. : Сов. радио, 1964. 140 с.

82. Mattson R.L. Evaluation of multilevel memories // IEEE Trans.Magn. 1971. V.7, N^12. P.814-819.

83. Пржиялковский В.В., Ломов Ю.С. Технические и программные средства Единой системы ЭВМ (ЕС ЭВМ-2). М.: Статистика, 1980.232 с.

84. Tucker S.G. IBM 3090 systems: An overview // IBM Syst.J. 1986. V.25, N^l. P.4-19.

85. Коган Я. A. , Ляхов А.И., Нерсесян С. Г. Асимптотический анализ эффективности использования кэш-памяти в многопроцессорных системах // Автоматика и телемеханика. 1986. N=11. С.142-151.

86. Коган Я.А. , Ляхов А.И., Нерсесян С. Г. Оценка показателей производительности кэш-памяти в многопроцессорных системах // Тр. VI Всесоюз.шк. "Многопроцессорные вычислительные системы": Тез. ДОКЛ. М.: ИПУ, 1985. С.30-32.

87. Ляхов А.И. Многопараметрический анализ эффективности использования кэш-памяти на основе асимптотических методов // Автоматика и телемеханика. 1989. N=11. С.155-165.

88. Смирнов Р.В. Анализ функционирования двухуровневой иерархической памяти процессора // Вопросы радиоэлектроники. Сер. ЭВТ.1980. Вып. 5. С. 3-11.

89. Pohm A.V., Agrawal О.P., Monroe R.N. The cost and performance tradeoffs of buffered memories // IEEE Proc. 1975. V.63, N=8. P.1129-1135.

90. Кошман A. E. , Соловьев С. П. Оценка номинальной производительности ЭВМ // Вопросы радиоэлектроники. Сер.ЭВТ. 1977. Вып.5. С.55-59.

91. Перспективы развития вычислительной техники: Справ. пособие в 11 кн. / Под ред. Ю.М.Смирнова. М. : Высш. шк. , 1989. Кн. 3: ЭВМ общего назначения. 143 с.

92. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Под ред.А. П. Ершова. М.: Наука, 1982. 336 с.

93. Прангишвили И. В. , Виленкин С. Я. , Медведев И. JI. Параллельные вычислительные системы с общим управлением. М.: Энергоатом-издат, 1983. 311 с.

94. Бурцев B.C. Принципы построения многопроцессорных вычислительных комплексов "Эльбрус". М., 1977. (Препр. /ИТМ и ВТ; NSl) .

95. Литвинов A.M., Плюснин В. У. , Брусиловский Е.Л. , Цуканов Ю. П. Особенности внутренней структуры высокопроизводительной муль-тисистемы ЕС 1065 // Вопросы радиоэлектроники. Сер. ЭВТ. 1981. Вып.5. С.16-28.

96. Ломов Ю.С. ЭВМ высокой производительности ЕС1066 и ЕС1065 // ЭВТ. 1987. Вып. 1. С. 177-188.

97. Пшеничников Л.Е., Сахин Ю. X. Архитектура многопроцессорного вычислительного комплекса "Эльбрус". М., 1977. (Препр./ИТМ и ВТ; N? 7).

98. Зотов С.М. , Семенихин С. В. Взаимодействие процессоров вмногопроцессорном вычислительном комплексе "Эльбрус". М., 1981. (Препр./ИТМ и ВТ;

99. Briggs F.A., Dubois M. Effectiveness of private caches in multiprocessor systems with parallel-pipelined memories // IEEE Trans. Comput. 1983. V.32, N^l. P.48-59.

100. Брусиловский E.Jl. , Слуцкин А. И. , Цуканов Ю. П. Анализ вариантов структуры двухуровневой ОП высокопроизводительных многопроцессорных систем // Вопросы радиоэлектроники. Сер.ЭВТ. 1980. Вып.З. С.53-62.

101. Lang Т., Valero М., Alegre I. Bandwidth of crossbar and multiple-bus connection for multiprocessors // IEEE Trans. Comput. 1982. V.31, N=12. P.1227-1234.

102. Hwang K. Advanced parallel processing with supercomputer architectures // Proc.IEE. 1987. N^io. P.1348-1379.

103. Test J., Myszenski M., Sueft R.C. The Alliant FX/Series: automatic parallelism in a multiprocessor mini-supercomputer // Multiprocessors and array processors. San Diego (Calif.): Simulation councils, 1987. P.35-44.

104. Infotron INX4 4 00 Intelligent switching system // DATAPRO Research Corp. C12-526-101. Communications switches. Delran, March 1986.

105. Шоу А. Логическое проектирование операционных систем. М. : Мир, 1981. 360 с.

106. Frank S., Inselberg A. Synapse tightly coupled multiprocessors: A new approach to solve old problems // AFIPS conf. proc., 1984: Nat.comput.conf., July 9-12, Las Vegas, Nevada. Las Vegas, 1984. P.41-50.

107. Вейцман К. Распределенные системы мини- и микро-ЭВМ. М. : Финансы и статистика, 1983. 232 с.

108. Локальные вычислительные сети-, опыт международной стандартизации. Сер. «Методические материалы и документация по пакетам прикладных программ». М: МЦНТИ, 1984, вып.27.

109. Манчестер Ф. Будущее бизнеса проектируется сегодня // Финансовые известия. 1994. N=18(79). С.1.

110. McClain F. Datatree and Unitree: Software for file and storage management // Proc. 10th IEEE Symp. Mass Storage, Dig. Papers, May 1990. P.126-128.

111. Sandberg R. et al. Design and implementation of the SUN network file system // Proc. 10th Usenix Conf., Portland OR, 1985. P.119-130.

112. Gerla M., Kleinrock L. Flow control: a comparative survey // IEEE Trans.Commun. 1980. V.28, N^4. P.553-574.

113. Райзер M. Оценка характеристик систем передачи данных // ТИИЭР . 1982. Т. 70, N^2. С. 28-59.

114. Бутрименко А. В. Разработка и эксплуатация сетей ЭВМ. М. : Финансы и статистика, 1981. 256 с.

115. Dec sets Х.25. Coals (Packetnet) // Datamation. 1980. N^10. P.59.

116. Digital enter phase III //Datamation. 1980. N=5. P.58-59.

117. Stuart W. DNA: the digital network architecture // IEEE Trans.Commun. 1980. V.28, N^4 . P.510-526.

118. Ahuja V. Routing and flow control in Systems Network Architecture // IBM Syst.J. 1979. V.18, N= 2. P.298-314.12 0. Atkins J. D. Path control: The transport network of SNA // IEEE Trans.Commun. 1980. N=4. P.527-538.

119. George F.D., Young G.E. SNA flow control: Architecture and implementation // IBM Syst.J. 1982. V.12, N^2. P.179-210.

120. Burkhart H., Millen R. Performance-measurement tools ina multiprocessor environment // IEEE Trans.Comput. 1989. V.38, N?5. P.725-737.

121. Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы. М: Мир, 1976. 736 с.

122. Митрофанов Ю.И., Беляков В.Г. , Курбанкулов В.Х. Методы и программные средства аналитического моделирования сетевых систем. М. : ВИНИТИ, 1982. 68 с.

123. McKenna J., Mitra D. , Ramakrishnan K.G. A class of closed Markovian queueing networks: integral representations, asymtotic expansions and generalizations // Bell System Techn.J. 1981. V.60, N?5. P.599-641.

124. McKenna J. , Mitra D. Integral representations and asymptotic expansions for closed Markovian queueing networks: normal usage // Bell System Techn.J. 1982. V.61, N^5. P.661-683.

125. McKenna J., Mitra D. Integral representation and asymptotic expansions for closed Markovian queueing networks: normal usage // Performance 81, Amsterdam, North-Holland, 1981. P.67-84.

126. Де Брейн H. Г. Асимптотические методы в анализе. М. : ИЛ, 1961. 248 с.

127. Bhandarkar D.P. Analysis of memory interference in multiprocessors // IEEE Trans. Comput. 1975. V.24, N=9. P.897-908.

128. Sevcik K.C., Zhou S. Performance benefits and limitations of large NUMA multiprocessors // In Proc. Performance'931. Conf., Rome, Sept. 1993.

129. Holliday M., Stumm M. Performance evaluation of hierarchical ring-based shared memory multiprocessors // Techn. Rep. CS-1992-18, Duke University, Department of Computer Science, Durham, North Carolina 27708-0129, Nov.1992.

130. Vranesic Z.G., Stumm M., Lewis D., White R. Hector: A hierarchically structured shared-memory multiprocessor // IEEE Computer. 1991. V.24. N^l. P.72-80.

131. Burkhardt H., Frank S., Knobe В., Rothnie J. Overview of the KSR-1 computer system // Techn. Rep. KSR-TR-9202001, Kendall Square Research, Boston, MA, Feb.1992.

132. Lenosky D., Laudon J., Joe Т., Nakahira D., Stevens L., Gupta A., Hennessy J. The DASH prototype: implementation and performance // In Proc. 19th Ann. Int.Conf. on Computer Architecture, May 1992.

133. Chaiken D., Kubiatowicz J., Agarwal A. LimitLESS directories: A scalable cache coherence scheme // In Proc. 4th Int. Conf. Architectural Support for Programming Languages and Oper. Syst. (ASPLOS IV), ACM, Apr.1991. P.224-234.

134. Shin K.G., Lee Y.-H., Sasidhar J. Design of HM2p -hierarchical multimicroprocessor for general-purpose application // IEEE Trans.Comput. 1982. V.C-31. N^l. P.1045-1053.

135. Pouzin L. Flow control in data networks-methods and tools // Proc. ICCC-76, Toronto, 1976, P.467-474.

136. Goyal A., Agerwala T. Performance analysis of future shared storage systems // IBM J. Res. Develop. 1984. V.28, N^i. P.95-107.

137. Hoogendoorn C.M. A general model for memory interference in multiprocessors // IEEE Trans.Comput. 1977. V.C-26, N°10.1. P.990-1005.

138. Patel J.H. Analysis of multiprocessors with private cache memories // IEEE Trans.Comput. 1982. V.C-31. N=4. P.296-304.

139. Fukuda A. Equilibrium point analysis of memory interference in multiprocessor systems // Systems and Computers .in Japan. 1986. V.17, N?3 . P.84-93.

140. Mogul J., Borg A. The effect of context switches on cache performance // In Proc. of 4th Int. Conf. on Architectural Support for Programming Languages and Operating Systems. 1991. P.75-84.

141. Ousterhout J. Scheduling techniques for concurrent systems // In Proc. of 3rd Int.Conf. on Distributed Computing Systems. 1982. P.22-30.

142. Gelenbe E., Mitrani I. Analysis and Synthesis of Computer Systems. London: Academic Press, 1980.

143. Матвеев В.Ф., Ушаков В. Г. Системы массового обслуживания. М.: МГУ, 1984. 239 с.

144. Климов Г.П., Ляху А. К. , Матвеев В. Ф. Математические модели систем с разделением времени. Кишинев: Штиинца, 1983.

145. Drakopoulos Е., Merges M.J. Performance analysis of client-server storage systems // IEEE Trans.Comput. 1992. V.41, N=11. P.1442-1452.

146. Souza E. et al. A clustering approximation technique for queueing network models with a large number of chains // IEEE Trans. Comput. 1986. V.35. N=5.

147. Ляхов А.И. Асимптотический анализ неоднородной сетевой модели многопроцессорных и многотерминальных систем // Автоматика и телемеханика. 1994. N?2. С. 161-171.

148. Сипсер Р. Архитектура связи в распределенных системах.

149. Т. 1, 2. М. : Мир, 1981. 350 С. ; 390 С.

150. Gelenbe Е., Grande I. L., Mussard P. Performance limits of the TMM protocol: modeling and measurement / IRIА/LABORIA, Res. Rep. 230, April, 1977.

151. Дэвис Д. , Барбер Д. , Прайс У. , Соломонидес С. Вычислительные сети и сетевые протоколы. М. : Мир, 1982. 563 с.

152. Gelenbe Е., Labetoulle J., Pujolle G. Performance evaluation of the protocol HDLC // Proc. Int. Conf. on Computer Network Protocols, Liege, 1978.

153. Masunaga P. A probabilistic automation model of the NRM, HDX HDLC procedure // Computer Networks. 1978. V.2, P.442-453.

154. Wang J. Delay and throughput analysysis for computer communication with balanced HDLC procedure // IEEE Trans. Comput. 1982. V.31, N°8. P.1128-1136.

155. Bux W. et. al. Data link-control performance: results comparing HDLC operational modes // Computer Networks. 1982. V.6, N°1. P.37-51.

156. Edge S., Hinckley A.J. A survey of end-to-end retransmission techniques // ACM SIGCOMM. Comp.Commun.Rev. 1978. V.8, N°4 . P.1-18.

157. Faiolle G., Gelende E., Pujolle G. An analytic evaluation of the performance of the «Send and Wait» protocol // IEEE Trans.Commun. 1978. V.26, N^3. P.313-319.

158. Ande F. et. al. A critical study of flow control methods in computer networks // ACM CIGCOMM Сотр. Commun. Rev. 1979. V.9, N?3. P.23-32.

159. Giessler A., Hanle J., Konig A., Pade E. Free buffer allocation an investigation by simulation // Computer Networks. 1978. V.2, N=3. P.191-208.

160. Sproule D. E., Mellor F. Routing, flow and congestion control in the DATAPAC network // IEEE Trans.Commun. 1981. V.29, N=4. P.386-391.

161. Jackson C., Georganas N. Dimensioning of message-switched computer communication networks with end-to-end flow control // Computer Communications. 1979. V.2, N?4. P.161-163.

162. Schwartz M. Performance analysis of the SNA virtual route pacing control //IEEE Trans.Commun. 1982. V.30, N^ l. P.172-184.

163. Pennotti M., Schwartz M. Congestion control in store and forward tandem links // IEEE Trans, commun. 1975. V.23, N^ 12. P. 1434-1443.

164. Шварц M. Сети ЭВМ. Анализ и проектирование. М. : Радио и связь, 1981. 336 с.

165. Chatterjee A., Georganas N. D., Verma P. К. Analysis of packet-network with end-to-end congestion control and random routing // Proc. ICCC-76. Toronto, 1976. P.488-494.

166. Georganas N. Local congestion control in computer-communication networks with random routing // In: ACM IEEE Data Commun. Symp. 1977. P.5.19- 5.24.

167. Chandy К. H., Herzog U., Woo L.S. Parametric analysis of gueueing networks // IBM J.Res.Develop. 1975. V.19, N^ i. p.43-49.

168. Irland M., Pujolle G. Models of tandem networks of queues motivated by packet switching / IRIA/LABORIA Research Report 256, 1977.

169. Magee F. Comparison of two pocket network protocols for flow control of customer virtual circuits // In Proc. ICCC-78, Tokyo, 1978, P.129-133.17 3. Postel J.B. Internetwork protocol approaches // IEEE Trans. Commun. 1980. V.28, N=4. P.604-611.

170. Bennet С. J. The overheads of trans-network fragmentation // Computer Networks. 1982. V. 6, N° 1. P. 21-36.

171. Schoch J. Packet fragmentation in internetwork protocols // Computer Networks. 1979. V.3, N°l. P.3-8.