Norenkov.Osnovy.Avtomatizirovannogo.Proektirovania.2002 (525024), страница 30
Текст из файла (страница 30)
Так, например, на итерации 0 имеют место изменения переменных 5 иС, поэтому на следующей итерации обращения происходят только к моделям элементов с выходами А иВ.3.6. Математическое обеспечение анализана системном уровнеОсновные сведения из теории массового обслуживанияОбъектами проектирования на системном уровне являются такие сложные системы, как производственные предприятия, транспортные системы, вычислительные системы и сети, автоматизированные системы проектированияи управления и т.
п. В этих приложениях анализ процессов функционированиясистем связан с исследованием прохождения через систему потока заявок (ина-1253. Математическое обеспечение анализа проектных решенийче называемых требованиями или транзактами). Разработчиков подобныхсложных систем интересуют прежде всего такие параметры, как производительность (пропускная способность) проектируемой системы, продолжительностьобслуживания (задержки) заявок в системе, эффективность используемого всистеме оборудования.Заявками могут быть заказы на производство изделий, задачи, решаемые ввычислительной системе, клиенты в банках, грузы, поступающие на транспортировку, и др. Очевидно, что параметры заявок, поступающих в систему, являются случайными величинами и при проектировании могут быть известнылишь их законы распределения и числовые характеристики этих распределений. Поэтому анализ функционирования на системном уровне, как правило, носитстатистический характер.
В качестве математического аппарата моделирования удобно принять теорию массового обслуживания, а в качестве моделейсистем на этом уровне использовать системы массового обслуживания(СМО).Типичными выходными параметрами в СМО являются числовые характеристики таких величин, как время обслуживания заявок в системе, длины очередей заявок на входах, время ожидания обслуживания в очередях, загрузкаустройств системы, а также вероятность обслуживания в заданные сроки и т. п.В простейшем случае СМО представляет собой некоторое средство(устройство), называемое обслуживающим аппаратом (ОА), вместе с очередями заявок на входах.
Более сложные СМО состоят из многих взаимосвязанных ОА. Обслуживающие аппараты СМО в совокупности образуют статические объекты СМО, иначе называемые ресурсами. Например, ввычислительных сетях ресурсы представлены аппаратными и программнымисредствами.В СМО кроме статических объектов фигурируют динамические объекты — транзакты. Например, в вычислительных сетях динамическими объектами являются решаемые задачи и запросы на информационные услуги.Состояние СМО характеризуется состояниями составляющих ее объектов.Например, состояния ОА выражаются булевыми величинами, значения которых интерпретируются как true (занято) и false (свободно), и длинами очередей на входах ОА, принимающими неотрицательные целочисленные значения.Переменные, характеризующие состояние СМО, будем называть переменными состояния или фазовыми переменными.Правило, согласно которому заявки выбирают из очередей на обслуживание, называют дисциплиной обслуживания, а величину, выражающую преимущественное право на обслуживание, — приоритетом.
В бесприоритетных дисциплинах все транзакты имеют одинаковые приоритеты. Средибесприоритетных дисциплин наиболее популярны дисциплины FIFO (первымпришел — первым обслужен), LIFO (последним пришел — первым обслужен) исо случайным выбором заявок из очередей.1263.6. Математическое обеспечение анализа на системном уровнеВ приоритетных дисциплинах для заявок каждого приоритета на входе ОАвыделяется своя очередь. Заявка из очереди с низким приоритетом поступаетна обслуживание, если пусты очереди с более высокими приоритетами. Различают приоритеты абсолютные, относительные и динамические. Заявка из очереди с более высоким абсолютным приоритетом, поступая на вход занятогоОА, прерывает уже начатое обслуживание заявки более низкого приоритета. Вслучае относительного приоритета прерывания не происходит, более высокоприоритетная заявка ждет окончания уже начатого обслуживания. Динамические приоритеты могут изменяться во время нахождения заявки в СМО.Исследование поведения СМО, т.
е. определение временных зависимостейпеременных, характеризующих состояние СМО, при подаче на входы любыхтребуемых в соответствии с заданием на эксперимент потоков заявок, называютимитационным моделированием СМО. Имитационное моделирование проводят путем воспроизведения событий, происходящих одновременно или последовательно в модельном времени.
При этом под событием понимают фактизменения значения любой фазовой переменной.Подход, альтернативный имитационному моделированию, называют аналитическим исследованием СМО. Аналитическое исследование заключаетсяв получении формул для расчета выходных параметров СМО с последующейподстановкой значений аргументов в эти формулы в каждом отдельном эксперименте.Модели СМО, используемые при имитационном и аналитическом моделировании, называются имитационными и аналитическими соответственно.Аналитические модели удобны в использовании, поскольку для аналитического моделирования не требуются сколько-нибудь значительные затраты вычислительных ресурсов, часто без постановки специальных вычислительныхэкспериментов разработчик может оценить характер влияния аргументов навыходные параметры, выявить те или иные общие закономерности в поведении системы. Но, к сожалению, аналитическое исследование удается реализовать только для частных случаев сравнительно несложных СМО.
Для сложных СМО аналитические модели если и удается получить, то только при принятииупрощающих допущений, ставящих под сомнение адекватность модели.Поэтому основным подходом к анализу САПР на системном уровне проектирования считают имитационное моделирование, а аналитическое исследование используют при предварительной оценке различных предлагаемых вариантов систем.Некоторые компоненты СМО характеризуются более чем одним входными (или) выходным потоками заявок.
Правила выбора одного из возможныхнаправлений движения заявок входят в соответствующие модели компонентов. В одних случаях такие правила относятся к исходным данным (например,выбор направления по вероятности), но в некоторых случаях желательно найтиоптимальное управление потоками в узлах разветвления. Тогда задача моделирования становится более сложной задачей синтеза, характерными примерами являются маршрутизация заявок или синтез расписаний и планов.1273. Математическое обеспечение анализа проектных решенийАналитические модели СМОКак отмечено выше, аналитические модели СМО удается получить придовольно серьезных допущениях.
К числу типичных допущений относятся следующие.Во-первых, как правило, считают, что в СМО используются бесприоритетныедисциплины обслуживания типа FIFO.Во-вторых, времена обслуживания заявок в устройствах выбираются в соответствии с экспоненциальным законом распределения.В-третьих, в аналитических моделях СМО входные потоки заявок аппроксимируются простейшими потоками, т. е. потоками, обладающими свойствамистационарности, ординарности (невозможности одновременного поступлениядвух заявок на вход СМО), отсутствия последействия.В большинстве случаев модели СМО отображают процессы с конечныммножеством состояний и с отсутствием последействия.
Такие процессы называют конечными марковскими цепями.Марковские цепи характеризуются множеством состояний S, матрицей вероятностей переходов из одного состояния в другое и начальными условиями(начальным состоянием). Удобно представлять марковскую цепь в виде графа,в котором вершины соответствуют состояниям цепи, дуги — переходам, весадуг — вероятностям переходов (если время дискретно) или интенсивностямпереходов (если время непрерывно).Отметим, что интенсивностью перехода называют величину F =limP (*,)/*,при (г —> 0, где Р{ (fj) - вероятность перехода из состояния St в состояние S завремя tr Обычно используют условиеми'что эквивалентно(3.44)где N—число состояний.
На рис. 3.17 приведен пример марковской цепи в виде графа с состояниями б1,,..., S4, а в табл. 3.9 представлена матрица интенсивностей переходов для этого примера.Т а б л и ц а 3.9СостояниеSi5з5452Vn5i-Ki2-Ki3-Ki4VuКм00SiV21-Vi\5з54128000-F34F34K420-F423 6 Математическое обеспечение анализа на системном уровнеБольшинство выходных параметров СМОможно определить, используя информацию о поведении СМО, т. е.
информацию о состоянияхСМО в установившихся (стационарных) режимах и об их изменениях в переходных процессах. Эта информация имеет вероятностную природу, что обусловливает описание поведенияРис. 3.17. ПримерСМО в терминах вероятностей нахождения сиемарковской цепитемы в различных состояниях. Основой такого описания, а следовательно, имногих аналитических моделей СМО являются уравнения Колмогорова.Уравнения Колмогорова можно получить следующим образом.Изменение вероятности Р нахождения системы в состоянии St за время t}есть вероятность перехода системы в состояние S из любых других состояний за вычетом вероятности перехода из состояния St в другие состояния завремя f,, т.
е.Р(0 = Р(ж,) - Р(0 = IP ,(gp (О - ЕР„(ОР,(0,,/eJ(3.45)*еКгде P(t) и P(f) - вероятности нахождения системы в состояниях S и S соответственно в момент времени t, а Р,(^,) и РД?,) — вероятности изменениясостояний в течение времени ?,; произведение вида Р ,(f,)P (0 есть безусловнаявероятность перехода из S в 5 , равная условной вероятности перехода, умноженной на вероятность условия; J и К — множества индексов инцидентныхвершин по отношению к вершине S по входящим и исходящим дугам на графесостояний соответственно.Разделив выражение (3.45) на /, и перейдя к пределу при t —> О, получимоткуда следуют уравнения Колмогорова*L(Vj i Р)-Р1'viI Vik..*JВ стационарном состоянии dP/dt = 0 и уравнения Колмогорова составляютсистему алгебраических уравнений, в которой /-и узел представлен уравнениемZ(Fy,P) = P Z F t .(3.46)j*Прибавляя Vt ( Р к левой и правой частям уравнения (3 .46) и учитывая (3 .44),получаемNN;=1\ Основы автоматизированногопроектированияJl J 'It-11293 Математическое обеспечение анализа проектных решенийт.
е.где Р — финальные вероятности.Пример аналитической моделиПримером СМО, к которой можно применить аналитические методы исследования, является одноканальная СМО с простейшим входным потоком интенсивностью А и длительностью обслуживания, подчиняющейся экспоненциальному закону обслуживания интенсивностью ц. Для этой СМО нужно получитьаналитические зависимости среднего числа NW заявок, находящихся в системе,среднюю длину Qm очереди к ОА, время Tw пребывания заявки в системе,время Тт ожидания в очереди.На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
