Содержание к диссертации
Введение
Глава 1. Задачи обработки сообщений в параллельных системах 10
1.1. Архитектура современных параллельных систем 10
1.2. Межпроцессорное взаимодействие в параллельных системах 13
1.3. Задача маршрутизации сообщений и подходы к ее решению 27
1.4. Алгоритмы отказоустойчивой маршрутизации 31
1.5. Выводы по главе 39
Глава 2. Процедура маршрутизации сообщений с обходом отказов 40
2.1. Модель параллельной системы и представление процесса
2.2. Характеристика предлагаемой процедуры маршрутизации 44
2.3. Примеры использования процедуры маршрутизации 56
2.4. Выводы по главе 62
Глава 3. Устройство маршрутизации на основе созданной процедуры 63
3.1. Функциональная организация устройства маршрутизации 63
3.2. Анализ работы устройства маршрутизации 95
3.3. Выводы по главе 114
Глава 4. Оценка эффективности разработанной процедуры и устройства динамической маршрутизации сообщений.. 115
4.1. Оценка допустимости и длины маршрутов 115
4.2. Оценка вероятности правильной передачи сообщения 118
4.3. Аналитическая оценка аппаратной сложности устройства марщрутизации 122
4.4. Определение предельной длины таблиц маршрутизации 124
4.5. Оценка длины формата сообщения 126
4.6. Экспериментальная оценка созданной процедуры маршрутизации 127
4.6.1. Постановка эксперимента 127
4.6.2. Архитектура экспериментальных программных средств 132
4.6.3. Q-схемы моделируемой системы 141
4.6.4. Результаты эксперимента 145
4.7. Выводы по главе 151
Заключение 152
Список литературы
- Межпроцессорное взаимодействие в параллельных системах
- Характеристика предлагаемой процедуры маршрутизации
- Анализ работы устройства маршрутизации
- Определение предельной длины таблиц маршрутизации
Введение к работе
Одним из перспективных направлений развития параллельных вычислительных систем (ВС) является создание массивно параллельных систем с распределенной памятью (МРР-системы). Отличительной особенностью МРР-систем является разделение физической памяти между процессорами (модулями), что дает возможность каждому модулю работать независимо от других. Благодаря такой архитектуре МРР-системы позволяют ввести средства оперативного восстановления работоспособности при появлении отказов модулей и/или связей (локальных отказовых неоднородностей). Указанные средства способны динамически исключать отказы из логической структуры системы, обеспечивая сохранение ее работоспособности в целом (возможно с деградацией производительности).
Включение в МРР-системы средств восстановления работоспособности предъявляет особые требования к подсистеме маршрутизации между процессорными модулями. Она должна не только выбирать кратчайший маршрут для передачи сообщения, но и обеспечивать обход отказовых неоднородностей. Независимо от конфигурации отказов подсистема маршрутизации должна выбирать кратчайший маршрут между любыми работоспособными модулями.
Существует множество алгоритмов отказоустойчивой (динамической) маршрутизации, ориентированных на системы с различными топологическими структурами (матрицы, гиперкубы, кубы циклов). Последние разработки в данной области - «Алгоритм адаптивной маршрутизации с кластерами без отказов» Л.А. Закревского и М.Г. Карповского, «Алгоритм отказоустойчивой маршрутизации на основе расширенных безопасных уровней», разработанный Jie Wu, «Алгоритм отказоустойчивой маршрутизации на основе распределенного блока восстановления», предложенный Gul N. Khan, Gu Wei, «Алгоритм отказоустойчивой маршрутизации на базе вектора вероятности», созданный J. Al-Sadi, К. Day, М. Ould-Khaoua.
Известные алгоритмы не гарантируют выбор кратчайших маршрутов при определенных комбинациях отказов. Кроме того, им свойствен ряд других недостатков: значительное время передачи сообщений и высокая сложность реализации.
В связи с вышеизложенным, актуальной задачей при построении МРР-систем является создание процедур и устройств маршрутизации, позволяющих исключить зацикливания и повысить достоверность передачи сообщений.
Работа выполнена при поддержке фанта «Столетовские гранты-2003» Министерства образования РФ, а также в рамках совместных работ с ОКБ «Авиаавтоматика» по договору №1.121.03 от 22 августа 2003 года. Основная часть диссертационной работы выполнена в рамках плана научно-исследовательских работ Курского государственного технического университета по единому заказ-наряду Министерства образования Российской Федерации в 1998-2004 годах, утвержденному начальником управления планирования и финансирования научных исследований.
Целью диссертационной работы является повышение достоверности передачи сообщений в МРР-системах с матричной структурой на основе создания аппаратно-ориентированной процедуры и устройства динамической маршрутизации сообщений с выбором альтернативных участков маршрута.
Задачами диссертационной работы являются:
1. Исследование существующих процедур отказоустойчивой маршрутизации сообщений в параллельных и распределенных системах и выявление их недостатков.
2. Разработка алгоритма и процедуры отказоустойчивой маршрутизации сообщений, основанной на динамическом выборе альтернативных участков маршрута из фиксированного множества. 3. Проектирование функциональной схемы устройства динамической маршрутизации сообщений на основе созданной процедуры.
4. Аналитические оценки аппаратной сложности устройства маршрутизации и вероятности правильной передачи сообщений в МРР-системе с использованием разработанной процедуры.
5. Исследование на имитационной модели зависимости времени передачи сообщений в МРР-системе от интенсивности потоков исходящих сообщений в процессорах при различных значениях наработки процессора на отказ и оценка потери сообщений из-за отказов при различных значениях наработки процессора на отказ.
Методы исследования.
При решении поставленных задач использовались методы теории множеств, теории графов, теории вероятностей, теории проектирования ЭВМ, теории автоматов и математической статистики. Экспериментальные исследования проводились на основе библиотеки классов имитационного моделирования и визуальной среды программирования, разработанных под руководством доц. Зотова И.В.
Научная новизна результатов диссертационной работы:
1. Создан алгоритм отказоустойчивой маршрутизации сообщений в матричных МРР-системах, обеспечивающий обход отказавших модулей на основе динамического изменения участков маршрута.
2. Разработана процедура отказоустойчивой маршрутизации сообщений в МРР-системах, позволяющая исключить зацикливания и повысить вероятность правильной передачи сообщений при уменьшении времени их передачи на основе динамического выбора альтернативных реализаций маршрута.
3. Получены аналитические оценки вероятности правильной передачи сообщений в МРР-системе и зависимость коэффициента потерь сообщений от наработки процессора на отказ, показывающие, что разработанные процедура и устройство маршрутизации позволяют повысить достоверность передачи не менее, чем в 2 раза, и снизить потери сообщений в 1.5 раза.
Практическая ценность работы заключается в следующем:
1. Спроектирована функциональная схема устройства маршрутизации сообщений на основе созданного алгоритма и получена оценка аппаратной сложности.
2. Расширена имеющаяся библиотека классов имитационного моделирования и визуальная среда программирования для ее поддержки за счет включения дополнительных функций управления клапанами, учитывающих особенности построения маршрута.
3. Определен размер таблицы маршрутизации предлагаемого модуля для систем реальной размерности, не превышающий IK слов.
Технические решения защищены патентом РФ № 2222044 и решениями о выдаче патентов по заявкам № 2003104071, № 2003129963.
Реализация и внедрение.
Результаты диссертационной работы используются в учебном процессе в Курском государственном техническом университете в дисциплинах «Организация ЭВМ и систем», «Отказоустойчивые многопроцессорные платформы» и внедрены на предприятиях ОАО «Счетмаш», ООО ПП «Микрокод», что подтверждается соответствующими актами.
Апробации работы.
Основные положения диссертационной работы докладывались и получили положительную оценку на НТК «Распознавайие-2001» (г. Курск, 2001), НТК «Методы и средства систем обработки информации» (г. Курск, 2003), НТК «Распознавание-2003» (г. Курск, 2003), на научно-технических семинарах Курского государственного технического университета с 2001 по 2004 год. Публикации.
Результаты диссертационной работы отражены в 8 публикациях, в том числе 3 статьях, 1 патенте на изобретение, 2 решениях о выдаче патента. В работах, опубликованных в соавторстве, лично соискателем предложено: в [1,2,7] - процедура выбора направления передачи сообщения, в [6,8] - алгоритм ретрансляции сообщений в матричных параллельных системах, в [3,4,5] -модуль для передачи сообщений.
На защиту выносятся:
1. Процедура отказоустойчивой маршрутизации сообщений для матричных МРР-систем.
2. Результаты аналитической оценки вероятности правильной передачи сообщений МРР-системой при использовании разработанной процедуры и аппаратной сложности устройства маршрутизации,
3. Результаты исследования на имитационной модели зависимости времени передачи сообщений в МРР-системе от интенсивности потоков исходящих сообщений в процессорах при различных значениях наработки процессора на отказ и оценка потерь сообщений из-за отказов при различных значениях наработки процессора на отказ.
4. Функциональная схема устройства маршрутизации на основе созданной процедуры.
Объем и структура работы.
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 160 страниц текста и поясняется 37 рисунками и 8 таблицами; список литературы включает 78 наименований; приложения содержат 71 страницу. Общий объем составляет 231 страницу. Области возможного использования.
Результаты диссертационной работы могут быть использованы при создании коммутационных процессоров в однородных параллельных системах с распределенной памятью, в абонентских системах, в системах сбора данных.
Межпроцессорное взаимодействие в параллельных системах
Важнейшим элементом архитектуры любых высокопроизводительных вычислительных систем, в том числе и МРР систем, являются средства обмена данными между процессором и оперативной памятью, процессором и другими устройствами, между различными процессорами. Организация внутренних коммуникаций вычислительной системы определяется ее топологией.
В зависимости от сложности пространственного строения принято выделять простые и сложные ВС. Простые ВС (одномерные и двумерные), как правило, представляются плоскими графами и имеют небольшой предел наращивания. Сложные ВС (допускающие n-мерные варианты построения) ориентированы на применение в системах значительной размерности и обеспечивают топологически простой механизм наращивания в теоретически произвольных пределах [2].
Для сравнительной оценки этих систем используются следующие количественные характеристики: т - время передачи сообщения от процессорного элемента (ПЭ) -передатчика к ПЭ-приемнику, или задержка сообщения (message delay); X - загрузка каналов связи (количество сообщений, приходящихся на канал связи в единицу времени), или плотность потока сообщений (message traffic density); с - удельная сложность (число каналов связи в расчете на один ПЭ).
Кроме количественных характеристик иногда вводят ряд вспомогательных параметров, а также качественные характеристики: коммутационная сложность системы, максимальные потери при выходе из строя произвольного ПЭ (определяется степенью нарушения межпроцессорных связей в системе или степенью ограничения количества обменных взаимодействий) [3].
Некоторые из простых топологий изображены на рис. 1.1.
Простейший вариант топологической структуры представляет собой одномерная цепочка (рис. 1.1 а) [4]. Удельная сложность с=2 и не зависит от размерности N. Цепочка предоставляет достаточно простой механизм расширения структуры при добавлении ПЭ. Однако, использование такой топологии при построении ВС большой размерности нецелесообразно, поскольку средняя задержка сообщения т и загрузка каналов связи X зависят от N. Кроме того, выход из строя і-го ПЭ разрушает каналы взаимодействия пар ПЭ (mk, ni), = 0,J-1,/ = / + I,JV, хотя система в целом сохраняет работоспособность.
При соединении линией связи первого и последнего ПЭ простой цепочки (то и mN„i) образуется кольцевая структура [5]. На практике получили распространение две разновидности кольцевых структур: двунаправленная (рис. 1Л б) и однонаправленная (рис. 1Л в).
В двунаправленной кольцевой структуре каждый і-й ПЭ может непосредственно принимать и передавать сообщения как от ((i+l)mod N)-ro (т.е. соседнего справа) ПЭ, так и от ((i+N-I) mod N)-ro (т.е. соседнего слева) ПЭ,/ = 0,ЛГ-1.
В однонаправленной — направление, в котором осуществляется движение сообщений, фиксируется и І-й ПЭ непосредственно передает сообщения только ПЭ (i+1) modN, принимая при этом сообщения только от ПЭ (І+N-l) mod N. Кольцевым структурам независимо от направлений передачи информации присущи те же положительные свойства, что и одномерной цепочке (простота комплексирования, наращивания, малая удельная сложность, простота маршрутизации сообщений). Хотя значение т и X немного ниже, чем в простой цепочке, кольцевые структуры также не могут служить эффективной основой для построения ВС значительной размерности (N 10 - 20), поскольку зависимость т. и А, от N имеет порядок N/2. ВС с кольцевой организацией обладают малой надежностью, так как отказ по меньшей мере одного ПЭ или канала связи существенно уменьшает возможное число обменных взаимодействий.
Одним из возможных способов повышения надежности кольцевых структур, причем при одновременной минимизации их диаметра (и, следовательно, значения т), является организация дополнительной связи между ПЭ nil и т,, где іє{0,2,4,...,N-2}, j=(i+3)mod N, N - четное. В результате образуется хордо-кольцевая структура (рис. 1.1 г). Свойства хордо-кольцевых структур были исследованы в работе [6].
Максимально возможное быстродействие систем достигается при их реализации в виде полносвязных структур [3]. Особенностью таких структур является единичное расстояние между любой парой ПЭ (рис.1.Ід). Каждая пара ПЭ в полносвязной структуре соединяется индивидуальным двунаправленным каналом и, таким образом, межпроцессорный обмен информацией осуществляется без транзитной передачи сообщений (ретрансляции). Рассматриваемые структуры позволяют строить ВС достаточно высокой надежности, поскольку отказ любого ПЭ не нарушает связей между другими ПЭ, а выход из строя канала связи между і-м и j-м ПЭ исключает возможность взаимодействия только І-го и j-ro ПЭ. С другой стороны полносвязные структуры не могут служить эффективной основой для построения многопроцессорных систем (N 10) вследствие квадратичного роста числа межпроцессорных связей, высокой удельной сложности и чрезвычайно низкой загрузки каналов связи. Статические системы с шинной организацией позволяют минимизировать число межмодульных линий связи (рис.1.1е). Достоинством такой организации является практическая независимость числа межмодульных соединений от числа ПЭ, а также простота подключения дополнительных ПЭ. Однако такие ВС, аналогично кольцевым, не позволяют объединять значительное (N 10 - 20) число ПЭ. Это обусловлено критичностью системы к росту межпроцессорного обмена, а также ограничениями электрического характера. При одновременной генерации сообщений каждым ПЭ время ожидания освобождения шины системы N равняется в среднем — условных временных интервалов, хотя рассматриваемые структуры не предполагают транзитной передачи сообщений. Другим недостатком шинных структур является низкая надежность, которая фактически определяется надежностью общей шины.
Характеристика предлагаемой процедуры маршрутизации
Основная идея предлагаемой процедуры состоит в следующем. Каждый маршрут разбивается на множество участков ограниченной длины, каждому из которых соответствует некоторый подмаршрут исходного маршрута. Для любого участка может быть введено несколько альтернативных реализаций (подмаршрутов). Число и конфигурация таких реализаций для участка произвольны. При передаче сообщения осуществляется последовательный перебор возможных реализаций участков до тех пор, пока не будет найдена реализация, обеспечивающая передачу сообщения в конечный модуль участка. Если такой реализации не существует, то осуществляется попытка перехода к очередной реализации предыдущего участка. При отказе выбранной реализации осуществляется возврат сообщений в начальный модуль. Если при возврате происходит отказ одного из модулей и возврат становится невозможным, то реализуется вариант обхода отказавшего модуля по фиксированному алгоритму (greedy routing).
Под маршрут Rs будем ассоциировать с s-м участком маршрута R. Часть маршрутного кода R \ соответствующую подмаршруту Rs,s = \,%, обозначим как R и назовем маршрутным кодом s-ro подмаршрута (участка). Выделенные подмаршруты R]iR2i...,R переобозначим как Ri,R ,...yR и назовем базовыми реализациями первого, второго, и т.д., \,-го участков соответственно.
В дополнение к базовой реализации R введем для s-ro подмаршрута множество альтернативных реализаций iRl,Rf,..,,R ]=Asis = \,Z Потребуем, чтобы 1 /?J /i, q \,A,s, s = \,%. Положим Л =ЛяиДМ и назовем As множеством реализаций s-ro участка маршрута R. Обозначим через т+(/?м и m (RqA соответственно начальный и конечный модули реализации Rqs є As. Далее (если не указано иное) будем для упрощения считать, что Гт+(й/) = т+(/? т+(Д,),т-(лГ)-т-(л; и-(Д,), (2.18) \/R?,Rf =As,q q",S = \,Z, где m+(Rs) и m (Rs) соответственно начальный и конечный модули s-ro участка маршрута R. Замечание 4. Следует отметить, что условие (2.18) не является ограничением процедуры Н ив общем случае может не выполняться (содержательно это означает начало и/или завершение реализаций участка в различных модулях). Потребуем, чтобы выполнялось условие RfnRf\ - min VR ,Rf є Л„ q Ф q",s = І . (2.19) Каждую реализацию R% eAs представим кодом R вида (2.14), применив подстановку (2,13) к записи R% в виде (2.12). Длину кода R; ч обозначим R через п( ) Я ( г)ч — z По аналогии с выражением (2.15) запишем (2.20) где я = hs h — длина реализации R] Для каждого подмаршрута Rs, s = \,%, введем переменную qs {qs є{0Д,...,/1Л}), значением которой будем задавать активную (текущую) реализацию s-ro участка. Первоначально положим qs-0 (активны базовые реализации). Замечание 5. Любой маршрут R є 4 (/ ) будем далее рассматривать как последовательность активных реализаций его участков в момент t . Каждому модулю таЬ є М поставим в соответствие таблицу маршрутизации Т{таь) [34]. Элемент таблицы Т{таЬ) будем обозначать через Т {таЬ), а длину таблицы — через Г(таі) ; индекс ф при этом будем называть адресом (элемента) таблицы маршрутизации. Таблицу Т{твЬ) представим как упорядоченное множество подтаблиц Г(«Л) = (Г,,)К4),ГИЮ.-. )Ю), (2.21) где %аЬ— число маршрутов і? є 4 (/), R = (./?;,/?2,...,/М, таких, что таЬ=т+{щ), s є(і,2,...,;г},?є{0,1,...,Л,}. Каждую подтаблицу T c (mal)), c-l,gab, формально зададим в виде = » ( ;), д є л„ Чет И ))" упорядоченного множества
Обозначим через маршрут обхода отказавшего модуля в подмаршруте Rs. Обход будем совершать в направлении о-*0 = ст* [0]сг* [1] стД0]<г* [1J, выбор которого зависит от работоспособности последующего модуля, а приоритетное направление <т*0 - а-' [0]а [1]. Каждое выбранное направление обхода сохраним в поле направлений обхода BDF (Bypass direction field). Обход отказавшего модуля осуществим через работоспособные соседние модули в направлении основного маршрута за четыре шага.
Анализ работы устройства маршрутизации
Рассмотрим процесс функционирования предлагаемого модуля подробно. Поскольку модуль предназначен для включения в состав коммуникационной системы, его работу будем рассматривать во взаимосвязи с другими аналогичными модулями системы.
Исходное состояние всех регистров, триггеров и счетчиков модуля и всех входящих в его состав блоков является нулевым. В БПМК 64 (рис.3.7) в ячейках с ненулевыми адресами размещены маршрутные коды и признаки для всех участков, начинающихся данным модулем. Все ячейки блока 65 (рис.3.7) находятся в нулевом состоянии. (Цепи приведения элементов модуля в исходное состояние на рис.3.3-3.8 для упрощения условно не показаны.)
Поскольку регистры 31.1-31.К БООС 1.1 — 1.5 (рис.3.4) находятся в нулевом состоянии, на выходах элементов И 35.1-35.К присутствуют сигналы логической единицы, что, в свою очередь, обусловливает наличие нулевого сигнала на выходе элемента НЕ 41, индицирующего отсутствие сообщений в соответствующем БООС. Нулевые сигналы с выходов элементов НЕ 41 БООС 1.1—1.5 обеспечивают нулевой уровень сигнала на втором выходе БАОС 3 (рис.3.3). Нулевой сигнал с прямого выхода триггера 10 запуска блокирует работу БС 9, запрещая формирование на его выходах импульсов синхронизации. Нулевой сигнал с прямого выхода триггера 18 отказа (признак работоспособности текущего модуля) через выходы 28.1-28.4 модуля передается соседним модулям системы и сообщает им о работоспособном состоянии текущего модуля. Аналогичные сигналы поступают на входы 27.1-27.4 модуля с прямых выходов триггеров 18 отказа соседних модулей. Нулевое состояние регистра 7 обусловливает наличие нулевого уровня сигнала на выходе элемента ИЛИ 22,1, что, в свою очередь, приводит к блокировке мультиплексора 12, На выходе мультиплексора 12 присутствует сигнал логического нуля (F="0") независимо от сигналов на его первом-четвертом входах.
Так как на всех выходах регистра 7 и на выходе мультиплексора 12 присутствуют сигналы логического нуля, при этом триггер 46 (рис.3.6) находится в нулевом состоянии и на его прямом выходе, соответственно, также присутствует нулевой сигнал v="0", на выходах 4.7-4.13 блока 4 в соответствии с таблицей 3.2 (строка 1) будет код "0000010" (единичный сигнал на выходе 4.12 и нулевые сигналы на выходах 4.7-4.11, 4.13). Нулевые сигналы с выходов 4.7 и 4.8 блока 4 (рис.3.3) настраивают коммутаторы 14, 15, 16 и 17 на прием соответствующих полей адресной части сообщения с выхода мультиплексора 2. (Действие остальных сигналов с выходов блока 4 в исходном состоянии несущественно.) Описанное выше исходное состояние характерно для каждого модуля коммуникационной системы.
Работа коммуникационной системы в целом начинается с момента подачи сообщения на вход 24.1 одного из модулей от обслуживаемого этим модулем ОУ. Обобщенный формат сообщения показан на рис.3.9а. Сообщение включает информационное поле I и адресную часть. В информационном поле размещается информация, подлежащая передаче модулю — приемнику сообщения. В состав адресной части входят адресное поле А, содержащее маршрутный код текущего участка маршрута и код маршрута используемый при обходе отказавшего модуля в случае возврата сообщения, а также признак возврата и поле счетчика шагов при возврате (поле A3), а также признаки следующего (поле А1) и текущего участка маршрута (поле А2), и одноразрядное поле статуса сообщения С, используемое для пометки сообщения как квитанции при его возврате в случае обнаружения отказавшего модуля.
С входа 24.1 модуля сообщение подается на информационный вход БООС 1.1 (рис.3.3), с которого поступает на информационный вход демультиплексора 32 (рис,3.4). Так как на адресном входе демультиплексора 32 находится единичный код с выходов элементов И 35.1-35.К, сообщение проходит на первый выход демультиплексора 32, откуда через блок элементов ИЛИ 34.1 передается на информационный вход регистра 31.1.
Одновременно с сообщением на вход 24.1 модуля (рис.3.3) и, следовательно, на информационный вход БООС 1.1 поступает импульс синхронизации. Этот импульс проходит (рис.3.4) через элементы И 36.1-36.К, открытые единичными сигналами с выходов соответствующих элементов И 35.1- 35.К, и далее через элементы ИЛИ 37.1-37.К поступает на входы синхронизации регистров 31.1-31
Определение предельной длины таблиц маршрутизации
Вычислительный эксперимент осуществлялся на базе библиотеки классов имитационного моделирования, построенной на основе аппарата расширенных Q-схем. Условия проведения вычислительного эксперимента следующие.
1. Эксперимент осуществлялся отдельно над каждой процедурой. При этом регистрировалось количество сообщений (заявок) в системе, количество потерянных заявок, среднее время обработки сообщений в зависимости от интенсивности потоков сообщений и интенсивности отказа модулей в системе.
2. Частота генерации заявок (/ет) каждым модулем определялась экспоненциальным законом, параметр которого менялся от 20 до 50 тактов.
3. Наработка модуля на отказ (Тотк) также определялась экспоненциальным законом с параметрами 1000, 2000, 3000, 4000, 5000, 6000.
Если рассматривать каждый модуль как систему массового обслуживания, то их функционирование можно описать на языке Q-схем, в котором объектами обслуживания (обработки) являются сообщения или пакеты. Сообщения поступают в массовом порядке, моменты их поступления образуют поток, удовлетворяющий свойствам потока Пуассона (простейшего потока) [37].
Язык Q-схем - полуформальный графический язык. Он универсален и позволяет описывать системы широкого класса. Поэтому данный язык был использован при экспериментальном исследовании разработанной процедуры. Q-схема — это граф, вершины которого отображают элементы системы (реальные или вспомогательные абстракции), а дуги связывают элементы между собой. Все вершины разделяются на 4 вида в зависимости от того, какой элемент они моделируют. Связи делятся на 2 вида. Графическое изображение используемых базовых элементов для построения Q-схем дано на рис.4,За-г.
Первый элемент, представленный на рис. 4.3а обозначается как генератор заявок. Его функция - имитировать поступление заявок в систему извне в соответствии с некоторым законом распределения. Параметр X задается в соответствии с законом распределения. Если закон экспоненциальный, то это интенсивность потока заявок. При равномерном законе это уже интервал возможных значений.
Второй элемент, представленный на рис. 4.36 - канал. Его функция -имитация обработки заявки в течение времени, определяемого некоторым законом распределения времени обслуживания заявок. Параметр и, аналогичен параметру X для генератора.
Третий элемент представленный на рис. 4.3в - накопитель (или очередь). Он имитирует в схеме возможные скопления заявок. Накопитель характеризуется предельной длиной очереди — L. Она может быть бесконечной (накопитель без потерь) или ограниченной (накопитель с потерей заявок). Также накопитель характеризуется дисциплиной обслуживания заявок. Типовые дисциплины - FIFO (первым пришел -первым ушел) и LIFO (первым пришел - последним ушел), но возможны и иные дисциплины обслуживания, например, случайный выбор заявок.
Четвертый элемент - треугольник - это клапан (рис.4.Зг). Он имитирует управление потоками заявок. Например, он может блокировать прохождение заявок или, наоборот, разрешить в зависимости от значений некоторых управляющих сигналов, которые поступают от других элементов по управляющим линиям.
Связи в Q-схеме разделяются на два типа. Информационные связи -изображаются сплошными стрелками (рис. 4.3) - отображают пути прохождения заявок в системе. Управляющие связи - изображаются пунктирными стрелками (рис. 4.3) - передают управляющее воздействие на элементы Q-схем. На связи накладывается ряд ограничений. Так, генератор (если он не является управляемым) не может иметь входящих линий и обязан иметь хотя бы одну выходную информационную. Входящие управляющие связи допускаются только у клапанов (минимум — одна связь, максимум не ограничивается). Выходящие управляющие связи допустимы только у каналов и очередей. Число данных связей произвольно.
Базовый набор элементов Q-схем не достаточно эффективно позволяет удовлетворить требования при построении процедуры маршрутизации. Приходится разрешать некоторые ситуации, возникающие при построении достаточно сложных схем, использующих множество клапанов и дополнительных связей.
