Норенков И.П. - Основы автоматизированного проектирования (1060628), страница 30
Текст из файла (страница 30)
Но, к сожалению, аналитическое исследование удается реализовать только для частных случаев сравнительно несложных СМО. Для сложных СМО аналитические модели если и удается получить, то только при принятииупрощающих допущений, ставящих под сомнение адекватность модели.Поэтому основным подходом к анализу САПР на системном уровне проектирования считают имитационное моделирование, а аналитическое исследование используют при предварительной оценке различных предлагаемых вариантов систем.Некоторые компоненты СМО характеризуются более чем одним входными (или) выходным потоками заявок.
Правила выбора одного из возможныхнаправлений движения заявок входят в соответствующие модели компонентов. В одних случаях такие правила относятся к исходным данным (например,выбор направления по вероятности), но в некоторых случаях желательно найтиоптимальное управление потоками в узлах разветвления. Тогда задача моделирования становится более сложной задачей синтеза, характерными примерами являются маршрутизация заявок или синтез расписаний и планов.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 пребывания заявки в системе,время Тт ожидания в очереди.На рис.
3.18 представлен граф состояний рассматриваемой СМО, где Sk —состояние с k заявками в системе. Матрица интенсивностей представлена втабл. ЗЛО. Уравнения Колмогорова для установившегося режима имеют видИспользуя уравнения Колмогорова, можно выразить все Рр i= 1,2,3,..., черезР0. ПолучимР^Щц^аР^Р2= ((А + ц)/», - АР0)/ц = (1 + я)Р, - аР0 = <ЛР0;Р3= (1 + а)Р2 - aPt = а2Р}= с?Р0 и т. д.Здесь введено обозначение я = А. /ц. Отметим также, что установившийся режим возможен только при а < 1.Так как S Р = 1, то Р = 1/(1 + а + а2+а3+...) =1-а.Рис.
3.18. Граф состояний1303.6. Математическое обеспечение анализа на системном уровнеТ а б л и ц а 3.10СостояниеSoSi5гSiS*So-КД000SiS2к05з00S4-Х.-ДкЦ-Х-цкц-Х- ц000А.ц-Х-ц000Теперь нетрудно получить и остальные требуемые результаты:Nm - Z Pkk = Р,+ 2Р2+ ЗР3 + ... = а(\ - а\\- а);= Р2 + 2Р3... = Z (k- \)Pk = Р^Времена пребывания в системе и очереди определяются соотношениями:иN av = ^Тav2av = ^которые называют формулами Литтла:Имитационное моделирование СМОДля представления имитационных моделей можно использовать языки программирования общего применения, однако такие представления оказываютсядовольно громоздкими. Поэтому обычно используют специальные языки имитационного моделирования на системном уровне.
Среди языков имитационногомоделирования различают языки, ориентированные на описание событий,средств обслуживания или маршрутов движения заявок (процессов). Выборязыка моделирования определяет структуру модели и методику ее построения.Ориентация на устройства характерна для функционально-логического и более детальных иерархических уровней описания объектов.Для описания имитационных моделей на системном уровне (иногда их называют сетевыми имитационными моделями — СИМ) чаще используютязыки, ориентированные на события или процессы.
Примерами первых могутслужить языки Симскрипт, SMPL и ряд других. К числу вторых относятся языки Симула, SOL, а также популярный язык GPSS.Языки имитационного моделирования реализуются в программно-методических комплексах моделирования СМО, имеющих ту или иную степень специализации. Так, комплексы на базе языка GPSS можно использовать во многихприложениях, но есть специализированные комплексы для моделирования вычислительных сетей, систем управления предприятиями и т. п.5-1313. Математическое обеспечение анализа проектных решенийПри использовании языков, ориентированных на процессы, в составе СИМвыделяются элементарные части и ими могут быть источники входных потоков заявок, устройства, накопители и узлы.Источник входного потока заявок представляет собой алгоритм, в соответствии с которым вычисляются моменты tk появления заявок на выходе источника.
Источники могут быть зависимыми и независимыми. В зависимых источниках моменты появления заявок связаны с наступлением определенныхсобытий, например с приходом другой заявки на вход некоторого устройства.Типичным независимым источником является алгоритм выработки значений tkслучайной величины с заданным законом распределения.Устройства в имитационной модели представлены алгоритмами выработкизначений интервалов (длительностей) обслуживания. Чаще всего это алгоритмыгенерации значений случайных величин с заданным законом распределения.Но могут быть устройства с детерминированным временем обслуживания иливременем, определяемым событиями в других частях СИМ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
