Основы проектирования систем
 Скачать 1.88 Mb.
|
|
2.4.7. Решение задачи синтеза Синтез оптимальной системы направлен на построение системы, наилучшим образом соответствующей своему назначению. Основные этапы синтеза: формирование критерия эффективности, устанавливающего способ оценки качества системы в целом; определение оптимальных параметров структуры и режима функционирования системы, обеспечивающих выполнение заданных ограничений на характеристики системы (задача оптимизации); анализ качества функционирования оптимальной системы путем сопоставления её характеристик с заданными ограничениями на имитационных моделях или реальных системах. Решение задачи синтеза связано с определением зависимостей характеристик функционирования системы от параметров, которые представляются сложными математическими конструкциями. При этом возможность получения приемлемых результатов в процессе решения задач синтеза из-за их сложности и большой трудоемкости с учетом специфических особенностей реальных систем превосходит возможности математических методов оптимизации, и задача синтеза в общем виде оказывается математически неразрешимой. Для того чтобы снизить сложность задачи синтеза, процесс проектирования разделяют на последовательность этапов, на каждом из которых решаются частные задачи синтеза – определяются параметры, связанные с отдельными аспектами организации системы, с использованием тех или иных моделей. 57 В зависимости от целей можно выделить следующие частные задачи (этапы) синтеза: структурный синтез, состоящий в выборе способа структурной организации системы, в рамках которой могут быть удовлетворены требования технического задания; структурный синтез включает в себя два этапа: элементный синтез, состоящий в определении требований к параметрам отдельных элементов системы; топологический (конфигурационный) синтез, состоящий в определении способа взаимосвязи элементов системы, т.е. топологии (конфигурации) системы; функциональный синтез, состоящий в выборе режима (способа) функционирования системы; нагрузочный синтез, состоящий в определении требований к параметрам нагрузки, обеспечивающим функционирование системы с заданным качеством. На каждом из перечисленных этапов синтеза определяются значения соответствующего подмножества параметров, характеризующих структурную, функциональную организацию системы или нагрузку, возлагаемую на систему. При этом значения параметров оптимизируются лишь в отношении факторов, учитываемых на каждом из этапов синтеза, но не в отношении системы в целом. Поэтому многоэтапный синтез позволяет получить лишь приближенные оптимальные решения, качество которых проверяется путем детального анализа синтезированной системы. 2.4.8. Детальный анализ спроектированной системы Необходимость детального анализа спроектированной системы обусловлена необходимостью получения качественного проекта синтезируемой системы. Задача синтеза обычно решается с использованием сравнительно простых моделей, позволяющих получить решение в явной аналитической форме. При этом погрешность модели, а также методов расчета характеристик системы в случае применения приближенных аналитических зависимостей может привести к значительным различиям между расчетными и реальными значениями оптимизируемых параметров. В связи с этим возникает необходимость проверки и уточнения найденных значений параметров структурно-функциональной организации системы, для чего необходимо использовать наиболее адекватные модели, позволяющие получить результаты, в максимальной степени соответствующие реальным. В качестве таких моделей обычно применяются имитационные модели, которые могут быть построены с максимальным приближением к реальной системе за счёт большей детализации по сравнению с аналитической моделью. Кроме того, в процессе детального анализа синтезированной системы должны быть выявлены предельные возможности системы, узкие места в системе, а также определено, насколько хорошо (с каким запасом) выполняются заданные требования к качеству функционирования проектируемой системы. 58 3. Математические модели дискретных систем Многообразие структурно-функциональной организации реальных систем определяет использование множества разных моделей для решения задач системного проектирования. Случайный характер процессов, протекающих в подавляющем большинстве реальных систем (например, процессы обработки и передачи данных в компьютерных сетях) обусловливает широкое применение дискретных стохастических (вероятностных) моделей, функционирование которых описывается случайными величинами. Для рассматриваемых ниже моделей будем полагать, что: априорно известны параметры, описывающие структурную и функциональную организацию системы и создаваемую в ней нагрузку; система и, следовательно, модель функционирует в установившемся режиме, при котором её характеристики не меняются со временем; модели относятся к классу структурно-функциональных моделей, отображающих структурные и функциональные особенности организации проектируемой системы. В зависимости от способа представления и реализации будем использовать концептуальные (содержательные), математические (абстрактные) и программные (компьютерные) модели. Для изучения процессов, протекающих в дискретных системах со стохастическим характером функционирования, широко используются модели массового обслуживания (ММО), которые делятся на простейшие (базовые) модели в виде систем массового обслуживания и сетевые модели в виде сетей массового обслуживания, представляющие собой математические объекты, описываемые в терминах математического аппарата теории массового обслуживания. 3.1. Базовые модели В качестве простейших математических моделей систем со стохастическим характером функционирования используются системы массового обслуживания (СМО), содержащие один (рисунок 15) или несколько (рисунок 17) устройств У (устройств, приборов, каналов), обслуживающих заявки (запросы) З, поступающие в систему, и один (рисунок 15 и 17) или несколько (рисунок 17) накопителей Н, в которых находятся заявки, образующие очереди (О) и ожидающие обслуживания. СМО, используемые в качестве моделей дискретных систем со стохастическим характером функционирования, могут быть классифицированы по следующим признакам: 1) по числу мест в накопителе: с накопителем неограниченной емкости Е (рисунок 15), называемые СМО без потерь; Е У З Н(О) b, b Рисунок 15. Система массового обслуживания 59 с накопителем ограниченной емкости Е (рисунок 17), называемые СМО с потерями; без накопителя ( 0 E ), называемые СМО с отказами; 2) по количеству устройств: с одним устройством (рисунок 15), называемые одноканальными; с несколькими устройствами (рисунок 17), называемые многоканальными, причем, устройства могут быть идентичными (однородные системы) и затрачивать одинаковое время на обслуживание любой заявки, либо разными (неоднородные системы), длительности обслуживания заявок в которых различны; в дальнейшем, если не оговорено другое, будем полагать, что все устройства идентичны и равнодоступны для любой заявки; 3) по количеству классов (типов) заявок, поступающих в СМО: с однородным потоком заявок одного класса (рисунок 15 и 17); с неоднородным потоком заявок нескольких классов (рисунок 17). Следует отметить, что заявки в математической модели будут отнесены к разным классам только в том случае, если они различаются длительностью обслуживания в устройстве и/или имеют разные приоритеты при занесении в накопитель или при выборе из накопителя на обслуживание. В остальных случаях заявки образуют однородный поток. Модели реальных систем, представляемые в виде СМО разных классов, будем называть базовыми моделями. Для описания базовых моделей используются три группы параметров: структурные; нагрузочные; функциональные параметры (параметры управления). К структурным параметрам относятся: количество устройств N ; количество H и ёмкости H E E , , 1 накопителей; способ взаимосвязи накопителей с устройствами, задаваемый, например, в виде матрицы инцидентностей (связей) N n H h i I n h , 1 ; , 1 , , элементы которой принимают два значения: 1 , n h i , если накопитель h связан с устройством n , и 0 , n h i – в противном случае. У i i b / 1 1 H Рисунок 17. СМО с неоднородным потоком ДО У 1 У N Рисунок 17. СМО с N устройствами и накопителем ограниченной емкости Е 60 Нагрузочные параметры СМО включают в себя параметры потока заявок, поступающих в систему, и параметры обслуживания заявок. К ним же относится количество классов заявок H, которое равно 1 для СМО с однородным потоком заявок и H >1 для СМО с неоднородным потоком. Функциональные параметры задаются в виде конкретных стратегий управления потоками заявок в СМО, определяющих правила занесения заявок в накопители и выбора из очереди на обслуживание. 3.1.1. Параметры потока заявок Основным параметром потока заявок является его интенсивность – среднее число заявок, поступающих в систему за единицу времени. Величина / 1 a определяет средний интервал времени между двумя последовательными заявками. Для описания детерминированного (регулярного) потока заявок достаточно задать интенсивность потока или значение интервала / 1 a . Для случайного потока заявок, в общем случае, необходимо задать законы распределений ) ( A интервалов времени между заявками. При исследовании моделей массового обслуживания аналитическими методами часто предполагается, что поток заявок – простейший. Предположение о простейшем потоке заявок позволяет для многих математических моделей получить достаточно простые аналитические зависимости характеристик от параметров в явном виде. Свое название «простейший» поток получил именно благодаря этой особенности. Анализ моделей с потоками заявок, отличными от простейших, обычно усложняет математические выкладки и в большинстве случаев не позволяет получить аналитическое решение в явном виде. В случае потоков, отличных от простейшего, эффективным инструментом исследования становится имитационное моделирование. Простейший оток – это стационарный ординарный поток без последействия. Простейший поток иногда называют «экспоненциальным», поскольку интервалы времени между заявками в таком потоке распределены по экспоненциальному закону с функцией и плотностью распределения соответственно e A 1 ) ( , λτ e λ τ a ) ( , (1) где 0 – интенсивность потока заявок. Легко убедиться, что среднее значение (математическое ожидание) и дисперсия интервалов между заявками в простейшем потоке соответственно равны / 1 a и 2 / 1 D , тогда коэффициент вариации 1 / a D Простейший поток часто называют уассоновским, поскольку число заявок, поступающих за некоторый заданный промежуток времени t, распределено по закону Пуассона : 61 e k t t k P k ! ) ( ) , ( , (2) где ) , ( t k P – вероятность поступления k заявок за некоторый фиксированный интервал времени t (k = 0, 1,…; t >0); – интенсивность потока заявок. Простейший поток заявок обладает следующими замечательными свойствами. 1. Сумма H простейших потоков с интенсивностями H , , 1 образует простейший поток с интенсивностью H k k 1 (3) 2. Вероятностное (но не детерминированное) разрежение простейшего потока заявок, при котором любая заявка случайным образом с некоторой вероятностью p исключается из потока независимо от того, исключены другие заявки или нет, приводит к образованию простейшего потока с интенсивностью p ' , где - интенсивность исходного потока. Поток исключенных заявок – также простейший с интенсивностью ) 1 ( '' p Простейший поток заявок является математическим представлением некоторого «идеального» потока, обладающего рядом замечательных свойств, благодаря которым для многих математических моделей удаётся получить достаточно простые аналитические зависимости, связывающие характеристики функционирования систем массового обслуживания с исходными параметрами. Одним из таких свойств является «отсутствие последействия», которое заключается в том, что поступление в систему очередной заявки не зависит от того, когда и сколько заявок поступило ранее. Предположение о простейшем потоке широко используется не только из- за простоты получения математических зависимостей, но и по той причине, что многие реальные потоки близки к простейшим. Эта близость во многих случаях обусловлена следующим. Во-первых, суммирование (объединение) независимых стационарных ординарных потоков образует простейший поток при условии, что складываемые потоки оказывают более или менее одинаковое влияние на суммарный поток, причем на практике суммарный поток становится близким к простейшему уже при суммировании 5 потоков. Отметим, что при этом к суммируемым потокам не предъявляется требование отсутствия последействия. Во-вторых, можно показать, что стационарный ординарный поток заявок близок к простейшему, если на него оказывает влияние множество случайных факторов. Предположение о простейшем характере входного потока заявок оправдано также в тех случаях, когда известно, что коэффициент вариации интервалов между последовательными заявками реального потока меньше единицы. В этом случае использование простейшего потока в модели позволяет получить так называемые верхние оценки характеристик обслуживания заявок, 62 гарантирующие, что в реальной системе значения характеристик будут не хуже, чем полученные на модели. 3.1.2. Параметры обслуживания заявок Длительность обслуживания заявок в устройстве в общем случае задается функцией ) ( B или плотностью ) ( ) ( / B b распределения. Величина, обратная средней длительности обслуживания b , характеризует среднее число заявок, которое может быть обслужено за единицу времени, и называется интенсивностью обслуживания: b μ / 1 Во многих случаях аналитические зависимости могут быть получены для произвольного закона распределения длительности обслуживания заявок, если поток поступающих в систему заявок – простейший. При этом для определения средних значений характеристик обслуживания достаточно задать, кроме математического ожидания b , второй момент распределения или коэффициент вариации b длительности обслуживания. Время 0 T , измеряемое от момента поступления некоторой заявки в систему до момента завершения обслуживания заявки, находящейся в устройстве, называется временем дообслуживания. Математическое ожидание этого времени 2 / ) 1 ( ] [ 2 0 b b T M , (4) где –интенсивность простейшего потока заявок, поступающих в систему. Время 0 T учитывает, что в момент поступления заявки в системе может и не оказаться заявок, т.е. учитывает простои системы. 3.1.3. Стратегии управления потоками заявок В современных системах с очередями, например в компьютерных сетях, широко применяются разнообразные стратегии управления потоками заявок и организации очередей, определяющих: правило занесения поступающих заявок в накопитель (буфер), называемое дисци линой буферизации; правило выбора заявок из очереди для обслуживания в устройстве, называемое дисци линой обслуживания. Реализация этих правил осуществляется сучетом риоритетов заявок, устанавливающих преимущественное право заявок одного класса по отношению к заявкам других классов на занесение (в накопитель) или выбор из очереди (для обслуживания в устройстве). Дисциплины буферизации могут быть разбиты на два класса: без вытеснения заявок, находящихся в накопителе, при этом заявки, поступившие в систему и заставшие накопитель заполненным до конца, теряются; с вытеснением заявки данного класса или заявки самого низкоприоритетного класса, которая теряется. 63 В последнем случае дисциплины буферизации могут использовать следующие правила вытеснения заявок такого же или самого низкого приоритета из накопителя: вытеснение последней заявки, т. е. поступившей в систему позже всех; вытеснение «долгой» заявки, т. е. находящейся в накопителе дольше всех; вытеснение случайное, т.е. удаляемая заявка выбирается случайным образом. Отметим, что дисциплины буферизации актуальны только для систем с накопителями ограниченной емкости. В то же время в качестве моделей реальных систем часто используются СМО с накопителями неограниченной емкости, означающими, что любая поступившая заявка всегда найдет место в накопителе, т.е. не будет потеряна. И это несмотря на то, что в реальной системе емкость накопителя – ограничена. Такое предположение оправдано в тех случаях, когда вероятность переполнения ограниченной емкости в реальной системе мала. В частности, если вероятность переполнения накопителя ограниченной емкости меньше 10 -4 , в качестве модели может использоваться СМО с накопителем неограниченной емкости, при этом погрешность результатов расчета характеристик функционирования не превысит 5%. Это означает, что в этом случае дисциплина буферизации практически не влияет на характеристики обслуживания заявок. |