Норенков И.П. - Автоматизированное производство (1054022), страница 30
Текст из файла (страница 30)
Разработчиков подобных сложных систем интересуют прежде всего такие параметры, как производительность (пропускная способность) проектируемой системы, продолжительность обслуживания (задержки) заявок в системе, эффективность используемого в системе оборудования.Заявками могут быть заказы на производство изделий, задачи, решаемые в вычислительной системе, клиенты в банках, грузы, поступающие на транспортировку и др.
Очевидно, что параметры заявок, поступающих в систему, являются случайными величинами и при проектировании могут бытьизвестны лишь их законы распределения и числовые характеристики этих распределений. Поэтомуанализ функционирования на системном уровне, как правило, носит статистический характер. В качестве математического аппарата моделирования удобно принять теорию массового обслуживания, ав качестве моделей систем на этом уровне использовать +'+&$/. /)++#(#8# #2+47@'()*'9 (СМО).Типичными выходными параметрами в СМО являются числовые характеристики таких величин, как время обслуживания заявок в системе, длины очередей заявок на входах, время ожидания обслуживания в очередях, загрузка устройств системы, а также вероятность обслуживания в заданныесроки и т.п.В простейшем случае СМО представляет собой некоторое средство (устройство), называемое#2+47@'()<A'/ )00)")&#/ (ОА), вместе с очередями заявок на входах.
Более сложные СМО состо&.+.)$(*),$" . !"#$%!#&'&($"!))$*+($*,#&($"!)&*775@!"! 3%!#*%!#&F*:,$*$I*:+*F*)&* !)!@&'! +($*,#)KH (*L*)&Mят из многих взаимосвязанных ОА. Обслуживающие аппараты СМО в совокупности образуют +&)&'1$+%'$ #23$%&. СМО, иначе называемые "$+7"+)/'. Например, в вычислительных сетях ресурсыпредставлены аппаратными и программными средствами.В СМО, кроме статических объектов, фигурируют -'*)/'1$+%'$ #23$%&. — транзакты.
Например, в вычислительных сетях динамическими объектами являются решаемые задачи и запросы на информационные услуги.Состояние СМО характеризуется состояниями составляющих ее объектов. Например, состоянияОА выражаются булевыми величинами, значения которых интерпретируются как true (занято) и false(свободно), и длинами очередей на входах ОА, принимающими неотрицательные целочисленные значения. Переменные, характеризующие состояние СМО, будем называть переменными состояния илифазовыми переменными.Правило, согласно которому заявки выбирают из очередей на обслуживание, называют -'+='04'*#; #2+47@'()*'9, а величину, выражающую преимущественное право на обслуживание, — 0"'#"'&$&#/. В 2$+0"'#"'&$&*., -'+='04'*), все транзакты имеют одинаковые приоритеты. Среди бесприоритетных дисциплин наиболее популярны дисциплины FIFO (первым пришел — первым обслужен), LIFO (последним пришел — первым обслужен) и со случайным выбором заявок из очередей.В 0"'#"'&$&*., -'+='04'*), для заявок каждого приоритета на входе ОА выделяется своя очередь.
Заявка из очереди с низким приоритетом поступает на обслуживание, если пусты очереди с более высокими приоритетами. Различают приоритеты абсолютные, относительные и динамические.Заявка из очереди с более высоким )2+#4<&*./ 0"'#"'&$&#/, поступая на вход занятого ОА, прерывает уже начатое обслуживание заявки более низкого приоритета. В случае #&*#+'&$45*#8# 0"'#"'&$&) прерывания не происходит, более высокоприоритетная заявка ждет окончания уже начатогообслуживания.
Динамические приоритеты могут изменяться во время нахождения заявки в СМО.Исследование поведения СМО, т.е. определение временных зависимостей переменных, характеризующих состояние СМО, при подаче на входы любых требуемых в соответствии с заданием на эксперимент потоков заявок, называют '/'&)='#**./ /#-$4'"#()*'$/ СМО. Имитационное моделирование проводят путем воспроизведения событий, происходящих одновременно или последовательнов модельном времени. При этом под +#2.&'$/ понимают факт изменения значения любой фазовойпеременной.Подход, альтернативный имитационному моделированию, называют )*)4'&'1$+%'/ '++4$-#()*'$/ СМО.
Аналитическое исследование заключается в получении формул для расчета выходных параметров СМО с последующей подстановкой значений аргументов в эти формулы в каждом отдельном эксперименте.Модели СМО, используемые при имитационном и аналитическом моделировании, называютсяимитационными и аналитическими соответственно.Аналитические модели удобны в использовании, поскольку для аналитического моделированияне требуются сколько-нибудь значительные затраты вычислительных ресурсов, часто без постановкиспециальных вычислительных экспериментов разработчик может оценить характер влияния аргументов на выходные параметры, выявить те или иные общие закономерности в поведении системы.
Но,к сожалению, аналитическое исследование удается реализовать только для частных случаев сравнительно несложных СМО. Для сложных СМО аналитические модели если и удается получить, то только при принятии упрощающих допущений, ставящих под сомнение адекватность модели.Поэтому основным подходом к анализу САПР на системном уровне проектирования считаютимитационное моделирование, а аналитическое исследование используют при предварительной оценке различных предлагаемых вариантов систем.Некоторые компоненты СМО характеризуются более чем одним входным и (или) выходным потоками заявок.
Правила выбора одного из возможных направлений движения заявок входят в соответствующие модели компонентов. В одних случаях такие правила относятся к исходным данным (например,выбор направления по вероятности), но в некоторых случаях желательно найти оптимальное управление потоками в узлах разветвления. Тогда задача моделирования становится более сложной задачей синтеза, характерными примерами являются маршрутизация заявок или синтез расписаний и планов.&.+.)$(*),$" .
!"#$%!#&'&($"!))$*+($*,#&($"!)&*785@!"! 3%!#*%!#&F*:,$*$I*:+*F*)&* !)!@&'! +($*,#)KH (*L*)&MC0:D+-+A.,7+. /45.D+ *E$. Как отмечено выше, аналитические модели СМО удается получить при довольно серьезных допущениях. К числу типичных допущений относятся следующие.Во-первых, как правило, считают, что в СМО используются бесприоритетные дисциплины обслуживания типа FIFO.Во-вторых, времена обслуживания заявок в устройствах выбираются в соответствии с экспоненциальным законом распределения.В-третьих, в аналитических моделях СМО входные потоки заявок аппроксимируются 0"#+&$;>'/' потоками, т.е.
потоками, обладающими свойствами стационарности, ординарности (невозможности одновременного поступления двух заявок на вход СМО), отсутствия последействия.В большинстве случаев модели СМО отображают процессы с конечным множеством состоянийи с отсутствием последействия. Такие процессы называют %#*$1*./' /)"%#(+%'/' =$09/'.Марковские цепи характеризуются множеством состояний S, матрицей вероятностей переходовиз одного состояния в другое и начальными условиями (начальным состоянием).
Удобно представлятьмарковскую цепь в виде графа, в котором вершины соответствуют состояниям цепи, дуги — переходам, веса дуг — вероятностям переходов (если время дискретно) или интенсивностям переходов ( если время непрерывно).Отметим, что интенсивностью перехода называют величину Vij = lim Pij(t1) / t1 при t1→ 0, где Pij(t1) — вероятность перехода из состояния Si в состояние Sj за время t1. Обычно принимается условиеVii = -∑ Vij,что означаетj≠ iN∑ Vij = 0.(3.44)j=1где N — число состояний. На рис. 3.17 приведен пример марковской цепи в виде графа с состояниями S1,...,S4, а в табл. 3.9 представлена матрица интенсивностей переходов для этого примера.M:BD+=: 3.9Состояние%+,.3.)7.
Пример марковской цепиS1S2S3S4S1-V12-V13-V14V12V13V14S2V21-V2100S300-V34V34S40V420-V42Большинство выходных параметров СМО можно определить, используя информацию о поведении СМО, т.е. информацию о состояниях СМО в установившихся (стационарных) режимах и об ихизменениях в переходных процессах. Эта информация имеет вероятностную природу, что обусловливает описание поведения СМО в терминах вероятностей нахождения системы в различных состояниях. Основой такого описания, а следовательно, и многих аналитических моделей СМО являются 7")(*$*'9 O#4/#8#"#().Уравнения Колмогорова можно получить следующим образом.Изменение вероятности Pi нахождения системы в состоянии Si за время t1 есть вероятность перехода системы в состояние Si из любых других состояний за вычетом вероятности перехода из состояния Si в другие состояния за время t1, т.е.Pi(t) = Pi(t+t1) - Pi(t) = ∑ Pji(t1)Pj(t) - ∑ Pik(t1)Pi(t),j∈Jk∈K(3.45)где Pi(t) и Pj(t) — вероятности нахождения системы в состояниях Si и Sj соответственно в момент времени t, а Pji(t1) и Pik(t1) — вероятности изменения состояний в течение времени t1; произведение вида&.+.)$(*),$" .
!"#$%!#&'&($"!))$*+($*,#&($"!)&*795@!"! 3%!#*%!#&F*:,$*$I*:+*F*)&* !)!@&'! +($*,#)KH (*L*)&MPji(t1)Pj(t) есть безусловная вероятность перехода из Sj в Si, равная условной вероятности перехода, умноженной на вероятность условия; J и K — множества индексов инцидентных вершин по отношениюк вершине Si по входящим и исходящим дугам на графе состояний соответственно.Разделив выражение (3.45) на t1 и перейдя к пределу при t→0, получимlim Pi(t)/t1 = ∑ (lim Pji/t1)Pj - ∑ (lim Pik/t1)Pi,t→0j t→0kt→0откуда следуют уравнения КолмогороваdPi/dt =∑ (Vji Pj ) - Pi ∑ Vik.jkВ стационарном состоянии dPi/dt = 0 и уравнения Колмогорова составляют систему алгебраических уравнений, в которой i-й узел представлен уравнением∑ (VjiPj ) = Pi ∑ Vik.j(3.46)kПрибавляя ViiPi к левой и правой частям уравнения (3.46) и учитывая (3.44), получаемNNj=1k=1∑ (VjiPj ) = Pi ∑ Vik =0,т.е.N∑ (VjiPj ) = 0,j=1где Pj — финальные вероятности."8+/.8 :0:D+-+A.,742 /45.D+.
Примером СМО, к которой можно применить аналитическиеметоды исследования, является одноканальная СМО с простейшим входным потоком интенсивностью λ и длительностью обслуживания, подчиняющейся экспоненциальному закону обслуживания интенсивностью µ. Для этой СМО нужно получить аналитические зависимости среднего числа Nav заявок, находящихся в системе, среднюю длину Qav очереди к ОА, время ?av пребывания заявки в системе, время ?or ожидания в очереди.На рис. 3.18 представлен граф состояний рассматриваемой СМО, где Sk — состояние с k заявками всистеме. Матрица интенсивностей представлена в табл. 3.10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
