Математическое моделирование

Контрольные вопросы

Какие задачи структурной идентификация вы знаете?

Что понимается под ранжированием входов и выходов объекта?

В чем заключается сущность метода непосредственного ранжирования?

Литература

1. Растригин Л.А. Современные принципы управления сложными объектами, М.: Советское радио, 1980 г. -- 232 стр.

2. Растригин Л.А., Маджаров Н.Е. Введение в идентификацию объектов управления, М.: Энергия, 1977 г. - 216 стр.

Лекция 8. ИССЛЕДОВАНИЕ ЗАДАЧ СТРУКТУРНОЙ ИДЕНТИФИКАЦИИ (2 часа)

План

1. Метод парных сравнений

2. Определение рационального числа входов и выходов объекта, учитываемых в модели

3. Определение характера связи между входом и выходом модели объекта

1. Метод парных сравнений

Эксперту предлагается проранжировать факторы попарно, т. е. каждой паре факторов х_i и x_l поставить в соответствие число q_il:

где знак “” обозначает предпочтительность. Так, выражение х_ix_l следует читать: “i-й фактор более предпочтителен при ранжировании, чем l-и”. Знак ~ является знаком эквивалентности факторов с точки зрения ранжирования. Числа q_il обладают очевидным свойством

q_il + 0 = q_il.

Таким образом, каждый (j-и) эксперт свое мнение представляет в виде таблицы п?п (табл. 1)

Или

где верхний индекс определяет номер эксперта.

Таблица 2-1

	x1	X2	. . .	xn
x1	0	qj12	. . .	qj1n
x2	qj21	0	. . .	qj2n
. . .	. . .	. . .	. . . . . . . . .	. . .
xn	qjn1	qjn2	. . .	0

Осредним мнение экспертов. Для этого достаточно построить осредненную таблицу (n?n)

Где

-- среднее предпочтение i-го фактора перед l-м. Это и есть мнение экспертов. Определим согласованность экспертов. В качестве меры согласованности аналогично предыдущему естественно выбрать дисперсию величин . В силу того, что среднее значение равно нулю, для дисперсии получаем:



где суммирование производится по всей таблице . Максимальное значение дисперсии будет иметь место при полной согласованности экспертов и равно:

Тогда, вводя критерий согласованности как отношение дисперсии средних предпочтений к максимальной дисперсии, получаем:

Однако эксперты могут противоречить. Примером такой таблицы может служить табл. 2, где противоречие имеет вид , т.е. оказалось что и одновременно.

Таблица 2

	x1	x2	x3
x1	0	1	-1
x2	-1	0	1
x3	1	-1	0

Выявление подобных противоречий совершенно необходимо не только в осредненной таблице, но и в мнении каждого эксперта. Это можно сделать на основе. следующего, довольно очевидного правила, которое называется правилом транзитивности.

Для предпочтений оно имеет вид:

если х₁х₂ и x₂х₃, то х₁х₃. (5)

Для эквивалентности:

если х₁ ~ х₂ и x₂ ~ х₃, то х₁ ~ х₃

Таблицы, представляющие собой мнение каждого эксперта, должны удовлетворять указанной транзитивности и при обнаружении противоречий возвращаются соответствующему эксперту для разрешения отмеченных противоречий.

Для определения рангов ранжируемых факторов следует определить правило назначения рангов по таблице Q. Таких правил может быть много. Рассмотрим два из них,

Правило 1. Определим суммарные предпочтения каждого фактора

Естественно считать, что первый ранг имеет фактор, суммарное предпочтение которого максимально, т. е. при

первый ранг имеет фактор x_z, т. е. k_z=1. Аналогично образуются ранги остальных факторов.

Рассмотренное правило, однако, излишне осредняет предпочтения. Так, фактор, имеющий ряд явных предпочтений, которые легко обнаруживают эксперты, получит первый ранг только потому, что его второстепенность по отношению к другим факторам будет не столь ярко выражена. Именно в этом случае часто приходится обращаться к другому правилу.

Правило 2. Основная мысль этого правила опирается на идею усиления контраста. Для этого вводится порог д. Если предпочтение выше этого порога, то оно имеет явный характер, а если ниже, то оно сомнительно, т. е. больше соответствует эквивалентности. Получаем следующее преобразование матрицы средних предпочтений в контрастную матрицу U, которую легко преобразовать в ранжированный ряд:

Где

Как видно, это преобразование целиком и полностью определяется порогом д (0<д<1). При д=1 контрастная матрица U становится нулевой и все факторы эквивалентны. При д=0 она полностью заполняется единицами, но при этом почти неизбежно появление противоречий в виде нарушений транзитивности предпочтений (5).

Поэтому при выборе порога д следует помнить, что его увеличение приводит к отказу от ранжирования, а уменьшение--к увеличению числа явных предпочтении и к опасности появления противоречий.

Одной из возможных рекомендаций по определению оптимального порога является выбор порога д на “пороге противоречий”, т. е. такого значения д, незначительное уменьшение которого приводит к противоречиям.

2. Определение рационального числа входов и выходов объекта, учитываемых в модели

Описанным выше образом получаются ранжированные ряды всех претендентов на входы и выходы модели:

(6)

(здесь для удобства произведена перенумерация ранжированных факторов таким образом, чтобы их номер стал равен рангу, т. е. k_i=i).

Выбор рациональных чисел n*, q* и m*, характеризующих модель, т. е. размерность ее входов и выходов, следует также производить экспертно. Для этого нужно начать с минимального числа входов и выходов (n₁, q₁, m₁, т. е. с простейшей модели, например, с n₁=0; q₁=m₁=1). Назовем эту модель F₁ [характер связи Y=F₁ (X, U), где Y=(y₁, ..., y_m1); X=(x₁, ..., x_n1); U=(u₁, ..., u_q1): при этом выяснять .не нужно, модель рассматривается как “черный ящик”]. Таким образом, первая, простейшая модель характеризуется тройкой F₁=<n₁, q₁, т₁>. Вторая модель F₂=<n₂, q₂, m₂> должна быть выбрана экспертами из трех:

(7)

Здесь мы воспользовались ранжированными рядами (6), что позволяет усложнять объект введением фактора, имеющего очередной ранг.

Эксперты ранжируют тройки (7) по критериям, заранее оговоренным. Тройка, получившая первый ранг, образует F₂. Аналогично (i+1)-я модель F_i+1 определяется ранжированием трех полученных из F_i троек:

Таким образом, получим последовательность моделей объекта F₁, F₂, ..., F_l, расположенных в порядке их уточнения и усложнения. Теперь остается в этом ряду установить предпочтение, т. с. выбрать ту модель, которая и будет идентифицироваться. Это можно также сделать с помощью экспертов. Пусть в результате получен ряд предпочтений:

Это означает, что следует остановиться на модели

F_z=(n_z, q_z, m_z)

и таким образом n*=n_z, q*=q_z, m*=m_z.

3. Определение характера связи между входом и выходом модели объекта

Мы уже говорили, что структура модели определяется видом оператора модели F. Этот оператор, прежде всего, характеризуется кодом A. C него и следует начинать.

Определение кода A требует четырех двоичных выборов:



где каждый из признаков может принимать одно из двух значений: 0 или 1. Анализ следует начинать с простейшего (нулевого) случая. Действительно, код А построен так, что наличие трудностей в процессе идентификации отражается единицами кода. Так, динамический объект (б=1) труднее идентифицировать, чем статический (б=0); стохастический (в=1) труднее детерминированного (в=0), нелинейный (г=1) сложнее линейного (г=0) и т. д.

В процессе выбора кода A модели следует иметь в виду, что, учитывая эти трудности, вполне можно намеренно “снизить” модель, т.е. сделать ее значительно проще объекта. Так, поведение заведомо динамического объекта можно описывать статической моделью, если динамика объекта не слишком ярко выражена; нелинейный объект можно аппроксимировать линейным и т. д. Разумеется, что при этом эффективность управления, построенного на основе такой модели, снизится. Но если это снижение невелико, а выигрыш в идентификации значителен, то такой выбор следует считать оптимальным.

После выбора кода A модели следует определить конкретную форму ее оператора F.

Контрольные вопросы

Чем различается два правила для определения рангов ранжируемых факторов в методе парных сравнений?

Как определяется рациональное число входов в выходов объекта?

Как определяется характер связи между входом и выходом модели объекта?

Литература

1. Растригин Л.А. Современные принципы управления сложными объектами, М.: Советское радио, 1980 г. -- 232 стр.

2. Растригин Л.А., Маджаров Н.Е. Введение в идентификацию объектов управления, М.: Энергия, 1977 г. - 216 стр.

Лекция 9. АНАЛИТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ (2 часа)

План

1. Потоки заявок

2. Марковские модели

1. Потоки заявок

Простейший поток. При аналитическом моделировании характеристики системы вычисляются наиболее просто для потока заявок, называемого простейшим. Простейший поток -- это поток заявок, который обладает следующими свойствами: 1) стационарность; 2) отсутствие последействия; 3) ординарность.

Стационарность означает постоянство вероятности того, что в течение определенного временного интервала поступит одинаковое количество заявок вне зависимости от расположения интервала на оси времени.

Отсутствие последействия заключается в том, что поступившие заявки не оказывают влияния на будущий поток заявок, т. е. заявки поступают в систему независимо друг от друга.

Ординарность -- это значит, что в каждый момент времени в систему поступает не более одной заявки.

Любой поток, обладающий этими свойствами, является простейшим.

У простейшего потока интервалы времени между двумя последовательными заявками -- независимые случайные величины с функцией распределения:

F()=l-e ^-. (1)

Такое распределение называется экспоненциальным (показательным) и имеет плотность

f()=, (2)

математическое ожидание длины интервала

(3)

дисперсию

(4)

и среднеквадратическое отклонение, равное математическому ожиданию. Экспоненциальное распределение характеризуется одним количественным параметром -- интенсивностью.

Простейшие потоки заявок обладают следующими особенностями:

1. Сумма М независимых, ординарных, стационарных потоков с интенсивностями сходятся к простейшему потоку с интенсивностью

(5)

при условии, что складываемые потоки оказывают примерно одинаковое малое влияние на суммарный поток.

2. Поток заявок, полученный в результате случайного разрежения исходного стационарного ординарного потока, имеющего интенсивность , когда каждая заявка исключается из потока с определенной вероятностью р независимо от того, исключены другие заявки или нет, образует простейший поток с интенсивностью р.

3. Интервал времени между произвольным моментом времени и моментом поступления очередной заявки имеет экспоненциальное распределение с таким же математическим ожиданием 1/, что и интервал времени между двумя последовательными заявками.

4. Простейший поток создает тяжелый режим функционирования системы, поскольку, во-первых, большее число (63 %) промежутков времени между заявками имеет длину меньшую, чем ее математическое ожидание 1/, и, во-вторых, коэффициент вариации,

Рис. 1. Распределение Пуассона

равный отношению среднеквадратического отклонения к математическому ожиданию:

и характеризующий степень нерегулярности потока, равен единице, в то время как у детерминированного потока коэффициент вариации = 0, а для большинства законов распределения 0<<1.

Простейший поток имеет широкое распространение не только из-за аналитической простоты связанной с ним теории, но и потому, что большое количество реально наблюдаемых потоков статистически неотличимы от простейшего. Этот эмпирический факт подтвержден рядом математических моделей, в которых при довольно общих условиях доказывается, что поток близок к простейшему.

Пуассоновский поток. Пуассоновским потоком называется ординарный поток заявок с отсутствием последействия, у которого число заявок, поступивших в систему за промежуток времени ф, распределено по закону Пуассона:

(6)

где Р (k, -- вероятность того, что за время ф в систему поступит точно k заявок; -- интенсивность потока заявок.

Математическое ожидание и дисперсия распределения Пуассона равны . Вид зависимостей этого распределения при для разных , показан на рис. 1.

Следует подчеркнуть, что распределение Пуассона дискретно. Стационарный пуассоновский поток является простейшим.

Если нестационарный поток, интенсивность которого представляет собой функцию времени , описывается законом распределения Пуассона, то такой поток называется пуассоновским, но не простейшим. В распределении Пуассона длительности интервалов между двумя последовательными заявками -- это случайные величины с экспоненциальным распределением.

Эрланговский поток. В общем случае интервалы времени между поступлением заявок могут иметь функцию распределения общего вида G (). Если интервалы независимы, то говорят, что заявки образуют рекуррентный поток или поток с ограниченным последействием.

Поток называется рекуррентным (потоком Пальма), если он стационарен, ординарен, а интервалы времени между заявками представляют собой независимые случайные величины с одинаковым произвольным распределением. Тогда простейший поток рассматривается как частный случай рекуррентного потока. Примером рекуррентного потока может служить поток Эрланга.

Рис. 2. Потоки Эрланга

Потоком Эрланга го порядка называется поток, у которого интервалы времени между моментами поступления двух последовательных заявок представляют собой сумму k независимых случайных величин, распределенных по экспоненциальному закону с параметром . Поток Эрланга получается из простейшего путем исключения (k -- 1) заявок с сохранением каждой k-й заявки (рис. 2). Плотность распределения интервала времени между двумя соседними заявками в потоке Эрланга k-го порядка

 (7)

Поток Эрланга превращается в простейший при k = 1. Приведенные потоки наиболее широко используются в теории массового обслуживания, в том числе при аналитическом моделировании ВС.

2. Марковские модели

Общие сведения. В теории массового обслуживания к наиболее изученным и исследованным относятся модели, у которых случайный процесс функционирования относится к классу марковских процессов, т. е. марковские модели.

Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент и не зависят от того, когда и как система пришла в это состояние.

При исследовании ВС аналитическим моделированием наибольшее значение имеют марковские случайные процессы с дискретными состояниями и непрерывным временем.

Процесс называется процессом с дискретными состояниями, если его возможные состояния z₁, z₂,... можно заранее перечислить, т. е. состояния системы принадлежат конечному множеству, и переход системы из одного состояния в другое происходит мгновенно.

Процесс называется процессом с непрерывным временем, если смена состояний может произойти в любой случайный момент.



Рис. 3. Пример графа состояний

Описание марковской модели. Для описания поведения системы в виде марковской модели следует определить понятие состояния системы; выявить все состояния, в которых может находиться система; указать, в каком состояний находится система в начальный момент; построить граф состояний, т. е. изобразить все состояния, например, кружками и возможные переходы из состояния в состояние -- стрелками, соединяющими состояния (на рис. 3 выделено пять состояний); разметить граф, т. е. для каждого перехода указать интенсивность потока событий, переводящих систему из состояния z_i в состояние z_j

(8)

где p_ij (t, t + -- вероятность перехода из состояния z_i в состояние z_j за время от t до t + .

Для стационарных марковских процессов интенсивности переходов не зависят от времени: _ij (t) = _ij, тогда p_ij (t, t + .

Понятие состояния зависит от целей моделирования. В одном случае, например, оно может быть определено по состояниям элементов, каждый из которых может быть "свободен" или "занят" в другом случае состояние системы определяется числом заявок, находящихся на обслуживании и в очередях.

Уравнения Колмогорова для вероятностей состояний. Исчерпывающей количественной характеристикой марковского процесса является совокупность вероятностей состояний, т. е. вероятностей p_i (t) того, что в момент t процесс будет находиться в состоянии z_i (t = 1, ..., n).

Рассмотрим, как определяются вероятности состояний по приведенному на рис. 3 графу состояний, считая все потоки простейшими. В случайный момент времени t система может находиться в одном из состояний z_i с вероятностью p_i (t). Придадим t малое приращение и найдем, например, p₂ (t + ) -- вероятность того, что в момент t + t система будет в состоянии z₂. Это может произойти, во-первых, если система в момент t была в состоянии z₂ и за время не вышла из него; во-вторых, если в момент t система была в состоянии z₁ или z₅ и за время перешла в состояние z₂.

В первом случае надо вероятность р₂(t) умножить на вероятность того, что за время система не перейдет в состояние z₁, z₃ или z₄. Суммарный поток событий, выводящий систему из состояния z₂, имеет интенсивность. Значит, вероятность того, что за время система выйдет из состояния z₂, равна. Отсюда вероятность первого варианта

Найдем вероятность перехода в состояние z₂. Если в момент t система находилась в состоянии z₁ с вероятностью p₁ (t), то вероятность перехода в состояние z₁ за время равна

Аналогично для состояния z₅

Складывая вероятности и , получим

,

Раскроем квадратные скобки, перенесем p₂ (t) в левую часть и разделим обечасти на :

.

Если устремить к нулю, то слева получим производную функции :

Аналогичные уравнения можно вывести для всех остальных состояний. Получается система дифференциальных уравнений:

(8)

Эта система линейных дифференциальных уравнений дает возможность найти вероятности состояний, если задать начальные условия. В левой части каждого уравнения стоит производная вероятности i-го состояния, а в правой -- сумма произведений вероятностей всех состояний, из которых ведут стрелки в данное состояние, на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность i-гo состояния.

Представим уравнения Колмогорова в общем виде:

(9)

Здесь учтено, что для состояний, не имеющих непосредственных переходов, можно считать

Предельные вероятности состояний. В теории случайных процессов доказывается, что если число п состояний системы конечно и из каждого состояния можно перейти в любое другое за конечное число шагов, то существуют предельные (финальные) вероятности состояний:

(10)

Сумма вероятностей всех возможных состояний равна единице. При в системе S устанавливается стационарный режим, в ходе которого система случайным образом меняет свои состояния, но их вероятностные характеристики уже не зависят от времени. Предельную вероятность состояния z_i можно трактовать как среднее относительное время пребывания системы в этом состоянии.

Для вычисления предельных вероятностей нужно все левые части в уравнениях Колмогорова (9) положить равными нулю и решить полученную систему линейных алгебраических уравнений:

(11)

В связи с тем, что эти уравнения однородные, т. е. не имеют свободного члена и, значит, позволяют определить неизвестные только с точностью до произвольного множителя, следует воспользоваться нормировочным условием

(12)

и с его помощью решить систему уравнений.

Модель размножения и гибели. Разновидностью марковской модели с дискретным числом состояний и непрерывным временем является модель размножения и гибели. Она характерна тем, что ее граф состояний имеет вид цепи (рис. 4). Особенность этого графа состоит в том, что каждое из средних состояний z₁, ..., z_n-1 связано прямой и обратной стрелками с каждым из соседних состояний -- z_j правым и левым, а крайние состояния z₀ и z_n -- только с одним соседним состоянием.

Рис. 4. Граф состояний модели размножения и гибели

В этой модели формулы для определения вероятностей состояний, полученные в результате решения уравнений Колмогорова, имеют вид:

(13)

(14)

Эти формулы часто, используют при решении задач теории массового обслуживания.

Контрольные вопросы

Простейший поток и его свойства.

Основная характеристика экспоненциального распределения.

Пуассоновский поток.

Поток Эрланга и его основные свойства.

Какой процесс называется Марковским, описание Марковской модели?

Для чего используется уравнение Колмогорова?

Граф состояний модели размножения и гибели и основные формулы.

Литература

1. Альянах И.Н. Моделирование вычислительных систем, Л.: Машиностроение, 1988 г. - 223 стр.

2. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: Наука, 1980 г. - 208 стр.

3. Зобов Б.И., Сурков А.В. Основы моделирования вычислительных систем. М.: МЛТИ, 1982 г. -32 стр.

4. Масков А.И. моделирование вычислительных систем. Пермь: ПГУ, 1982 г. - 95 стр.

Лекция 10. ХАРАКТЕРИСТИКИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ (2 часа)

План

1. Характеристики вычислительных систем как систем массового обслуживания

2. Характеристики вычислительных систем как сложных систем массового обслуживания

3. Методы приближённой оценки характеристик вычислительных систем

1. Характеристики вычислительных систем как систем массового обслуживания

Описание системы. Предположим, что моделью ВС является одноканальная СМО с однородным бесконечным простейшим потоком заявок и неограниченной очередью. Интенсивность потока заявок равна . Длительность обслуживания заявки -- это случайная величина с математическим ожиданием .

Наряду с понятием средней длительности обслуживания используется понятие интенсивности обслуживания -- величины, обратной , и характеризующей число заявок, которое может обслужить прибор в единицу времени.

Поток обслуживания тоже будем считать простейшим с интенсивностью . В соответствии с символикой, принятой в теории массового обслуживания, такая система обозначается М/М/1.

Выделим состояния СМО по числу заявок, находящихся в системе:

z₀ -- прибор свободен, очереди нет;

z₁ -- прибор занят (обслуживает заявку), очереди нет;

z₂ -- прибор занят, одна заявка в очереди;

z_k -- прибор занят, (k -- 1) заявок стоит в очереди.



Рис. 1. Граф состояний СМО

Граф состояний такой системы изображен на рис. 1. Это модель размножения и гибели, но с бесконечным количеством состояний, поскольку, очередь неограниченна.

Коэффициент загрузки. Предельная вероятность состояния

(1)

Обозначая получаем

. (2)

Ряд в этой формуле представляет собой геометрическую прогрессию. Известно, что при с < 1 ряд сходится. Сумма членов прогрессии при этом равна 1/(1 -- с), откуда

Это вероятность того, что прибор свободен и очередь отсутствует. Значит, вероятность того, что прибор занят обслуживанием заявки,

Это означает, что отношение

(3)

служит мерой загрузки СМО и является коэффициентом загрузки. Тогда коэффициент простоя.

Число заявок в СМО. Вероятности состояний z₁, ..., z_k, ... определяются из общей формулы размножения и гибели:

Определим среднее число заявок в системе п. В текущий момент времени в системе может быть 0, 1, 2, .... k, ... заявок с вероятностями p₀, p₁, p₂,…, p_k… Математическое ожидание количества заявок равно

Подставим значение р_k и р₀, исключив первое слагаемое, равное нулю:

Вынесем за знак суммы с (1 -- р):

Но -- это производная по от :

.

Меняя местами операции дифференцирования и суммирования, получим

(4)

Сумма в этой формуле -- это сумма бесконечно убывающей прогрессии при она равна с/(1--с), а ее производная 1/(1- с)². Следовательно, число заявок в системе в установившемся стационарном режиме

п = с/(1 - с). (5)

Длина очереди. Найдем среднее число заявок в очереди к обслуживающему прибору -- среднюю длину очереди l. Она равна среднему числу заявок в системе за вычетом среднего числа заявок, находящихся под обслуживанием. Число заявок под обслуживанием может быть равно нулю, если прибор свободен, или единице, если прибор занят. В установившемся режиме математическое ожидание такой случайной величины равно вероятности того, что прибор занят. А эта вероятность определена ранее -- с. Откуда получается средняя длина очереди в СМО:

(6)

Зависимость средней длины очереди от коэффициента загрузки изображена на рис. 2. При с > 0,6--0,7 очередь стремительно увеличивается и при с 1 уходит в бесконечность. У детерминированной системы коэффициенты вариации интенсивностей потоков заявок и обслуживания равны нулю, при с < 1 очередь отсутствует, а при с 1 -- уходит в бесконечность. Для систем, которые имеют промежуточные коэффициенты вариации 0 <v < 1, зависимости средней длины очереди от коэффициента загрузки лежат в области, заштрихованной на рис. 2.

Время реакции. Для определения среднего времени реакции рассмотрим поток заявок, прибывающих в СМО, и поток заявок, покидающих систему. Если в системе устанавливается предельный стационарный режим при с<1, то среднее число заявок, прибывающих в единицу времени, равно среднему числу заявок, покидающих ее: оба потока имеют интенсивность .

Рис. 2. Зависимость средней длины очереди от коэффициента загрузки для простейшей СМО

Рис. 3. Временная диаграмма процессов поступления и ухода заявок

Обозначим через Х (t) число заявок, поступивших в СМО до момента времени t, а через Y (t) -- число заявок, покинувших СМО до момента t. Та и. другая функции являются случайными и меняются скачком -- увеличиваются на единицу в моменты прихода или ухода заявок (рис. 3).

Очевидно, что для любого момента времени t разность функций п (t)=Х (t) -- Y (t) есть число заявок, находящихся в СМО. Рассмотрим большой промежуток времени Т и вычислим среднее число заявок, находящихся в системе:

Интеграл изображен в виде заштрихованной фигуры на рис. 3. Она состоит из прямоугольников, каждый из которых имеет высоту, равную единице, и основание, равное времени пребывания в системе i-й заявки t_i:

где сумма распространяется на все заявки, поступившие в систему за время Т.

Разделим правую и левую части на Т.

Разделим и умножим правую часть на :



Произведение ,--это среднее количество заявок, пришедших за время Т. Если разделить сумму всех времен t_i на среднее число заявок, то получится среднее время пребывания заявки в системе, т. е. среднее время реакции и:

(7)

Это формула Литтла: для каждой СМО при любом характере потока заявок и при любом распределении времени обслуживания среднее время реакции равняется среднему числу заявок в системе, деленному на интенсивность потока заявок. Отсюда получается:

(8)

Вторая формула Литтла связывает среднее время пребывания заявки в очереди и среднее число заявок в очереди подобным соотношением:

(9)

Среднее время реакции равняется сумме среднего времени пребывания заявки в очереди и средней длительности обслуживания заявки:

(10)

Важно отметить, что в системе М/М/ 1 времена ожидания и реакции, а также периоды между моментами ухода следующих друг за другом заявок распределены по экспоненциальному закону. Для других систем при аналитическом моделировании не всегда представляется возможным определить законы распределения выходных характеристик.

При с > 1 в системе не устанавливается стационарный режим. В пределе длина очереди, а значит, и времена ожидания и реакции стремятся к бесконечности.

2. Характеристики вычислительных систем как сложных систем массового обслуживания

Многомерный поток. На вход обслуживающего прибора может поступать многомерный поток заявок, состоящий из заявок типов 1, ..., М, у которых интенсивности равны Предположим, что каждый из потоков заявок одного типа является простейшим. Загрузка прибора потоком заявок типа i будет составлять

где -- средняя длительность обслуживания заявок типа i. Суммарная загрузка прибора со стороны всех потоков

(11)



Рис. 4. Граф состояний многоканальной СМО

моделирование параметрическая идентификация вычислительная система

Условие существования стационарного режима: Р < 1. Остальные характеристики обслуживания n_i, l_i, u_i, определяются для каждого i-гo потока в отдельности по формулам (5)-- (9).

Средние времена ожидания _ср и реакции u_ср по одной заявке из суммарного потока в системе связаны со средними количествами заявок в очереди и в системе следующими соотношениями:

(12)

(13)

где -- суммарная интенсивность потоков; -- вероятность того, что поступившая заявка является заявкой i-гo типа;

l_cp -- средняя длина очереди заявок всех типов; n _ср -- среднее число заявок всех типов в системе.

Многоканальная СМО. Предположим, что система имеет т обслуживающих каналов с одинаковой интенсивностью обслуживания , при общем простейшем потоке заявок с интенсивностью . Такая система условно обозначается М/М/т. Граф состояний этой системы (рис. 4) подобен графу одноканальной СМО. Интенсивности перехода в соседнее правое состояние определяются, как и у одноканальной СМО, интенсивностью входного потока : с приходом очередной заявки система переходит в следующее правое состояние. Иначе обстоит дело с интенсивностями у нижних стрелок. Пусть система находится в состоянии z₁ -- работает один канал. Он производит обслуживании в единицу времени. Тогда . Представим, что система находится в состоянии z₂. Для перехода в состояние z₁ надо, чтобы закончил обслуживание первый или второй канал. Значит, суммарная интенсивность их обслуживания Суммарный поток обслуживания k каналами имеет интенсивность k. При kт интенсивность обслуживания сохраняется т. Получается модель размножения и гибели. Делая выкладки, как для одноканальной СМО, получим

Средняя длина очереди

(14)

Прибавляя к ней среднее число заявок, находящихся под обслуживанием, равное среднему числу занятых каналов

получим среднее число заявок в системе:

(15)

По формулам Литтла определяется среднее время пребывания заявки в очереди:

(16)

и в системе -- время реакции:

(17)

В теории массового обслуживания имеются аналитические формулы для простейших СМО при одномерном и многомерном потоке заявок для одноканальных и многоканальных систем без ограничений и с ограничениями длин очередей.

Потоки обслуживания. При моделировании конкретных ВС потоки заявок и обслуживания могут отличаться от простейших. Потоки заявок могут быть, например, пуассоновскими или эрланговскими. Длительности обслуживания можно представить в общем случае гамма-распределением. Это распределение с плотностью вероятности

(18)

где -- математическое ожидание длительности обслуживания М [ ]; k -- параметр распределения (k 1); Г (k) -- гамма-функция.

Дисперсия гамма-распределения

(19)

При k = 1 гамма-распределение вырождается в экспоненциальное. В пределе при k это распределение становится детерминированным с постоянной длительностью обслуживания . Параметр распределения k может быть определен по математическому ожиданию и дисперсии:

(20)

Рис. 5. Нормированное распределение Эрланга

При целочисленном k Г (k) = (k--1)!. Тогда из уравнения (18) имеем

, (21)

Это плотность нормированного распределения Эрланга k-го порядка. Вид распределения изображен на рис. 5. В данном распределении в отличие от потока Эрланга математическое ожидание не зависит от k и при k это распределение стремится к детерминированному, а не к нормальному.

В частных случаях длительности обслуживания могут быть распределены по экспоненциальному, равномерному, нормальному и другим законам. Для некоторых сочетаний законов распределений потоков заявок и обслуживании получены аналитические зависимости характеристик от параметров системы.

Системы с произвольным распределением длительности обслуживания. Представим, что моделью ВС является одноканальная СМО с неограниченной очередью. В эту систему поступает простейший поток заявок с интенсивностью . Заявки обслуживаются в порядке поступления. Длительность обслуживания имеет произвольное распределение с математическим ожиданием и коэффициентом вариации . Такая система обозначается M/G/1. В этой системе в установившемся режиме среднее число заявок в очереди

(26)

среднее число заявок в системе

(27)

Последние два выражения называются формулами Поллачека--Хинчина. Средние времена пребывания заявок в очереди и в системе определяются по формулам Литтла.

Для системы M/G/1 могут быть аналитически определены дисперсии выходных характеристик. Подобные формулы известны также для случая многомерного простейшего потока заявок.

Системы с отказами. Предположим, что на ВС, представленную как m-канальная СМО, поступает простейший поток заявок с интенсивностью К. Поток обслуживания имеет произвольный закон распределения с интенсивностью р. Это система M/G/m. При этом очередная заявка, поступившая в систему, когда все каналы заняты, покидает ее без обслуживания. Это означает, что очереди в системе отсутствуют. Характеристиками такой системы могут служить пропускная способность, вероятность обслуживания и среднее число занятых каналов. Данная система соответствует модели размножения и гибели. На основании формул (13) и (14) (лекция 9) можно вывести вероятность того, что в СМО находится т заявок, т. е. все каналы заняты:

(28)

Вероятность того, что очередная заявка будет обслужена,

(29)

Пропускная способность системы определяется как среднее число заявок, обслуживаемых в единицу времени;

(30)

а среднее число занятых каналов определяется по формуле

(31)

Системы с приоритетными дисциплинами диспетчеризации.

В теории вычислительных систем детально изложены и исследованы аналитические зависимости характеристик от параметров ВС, представленных моделями СМО с ординарными и неординарными, одномерными и многомерными потоками заявок, обслуживаемых одноканальными и многоканальными приборами с произвольными законами распределения длительности обслуживания и различными дисциплинами диспетчеризации, включая системы с относительным, абсолютным, смешанным и динамическим приоритетами.

Например, допустим, что в СМО поступает М типов простейших потоков с интенсивностями и длительности обслуживания заявок каждого потока имеют математические ожидания и дисперсии . В системе используется смешанная дисциплина диспетчеризации с тремя классами: 1) заявкам типов 1,..., M₁ присвоены абсолютные приоритеты по отношению к заявкам второго и третьего классов; 2) заявкам типов M₁+1,..., M₁+M₂ -- относительные приоритеты по отношению к заявкам третьего класса; 3) заявки типов M₁+M₂+1,..., M обслуживаются в порядке поступления. Среднее время ожидания заявок различных типов определяется из выражения:

(22)

где

Из формулы (22) могут быть получены как частные случаи

характеристики систем с абсолютными (, относительными (М₁ = M₃ = 0) и смешанными приоритетами с двумя классами заявок: с абсолютными и относительными приоритетами (М₃ = 0), с абсолютными приоритетами и без приоритетов (М₂ = 0), с относительными приоритетами и без приоритетов (M₁ = 0).

3. Методы приближённой оценки характеристик вычислительных систем

Оценка при большой нагрузке. Аналитические зависимости, позволяющие определить параметры распределений выходных характеристик, имеются только для ограниченного круга систем. У более широкого круга систем могут быть вычислены средние значения в стационарном установившемся режиме. Однако остается ряд систем и режимов, для которых отсутствуют точные формулы даже по определению средних значений. К таким системам относятся, в первую очередь, системы с произвольными распределениями периодов поступления и длительностей обслуживания заявок. Это системы G/G/1 и G/G/m. При отсутствии точных зависимостей приходится довольствоваться приближенными оценками.

Одним из методов приближений является оценка характеристик при близких к единице значениях коэффициента загрузки, как наиболее важных с практических позиций. В частности, для системы G/G/1 время ожидания заявки в очереди распределено по экспоненциальному закону и среднее время ожидания можно определить по следующей формуле:

(33)

где -- дисперсия периодов поступления и длительностей обслуживания заявок соответственно.

Используя зависимость (10) и формулы Литтла, можно вычислить средние значения других характеристик.

Определение границ. При значениях 0 с < 1 для оценки характеристик используется несколько различных подходов определения верхней и нижней границ, в пределах которых находится истинное значение той или иной характеристики. Например, для системы G/G/1 приводятся следующие формулы расчета границ среднего времени ожидания заявки в очереди:

(24)

где v, -- коэффициенты вариации периодов поступления и длительностей обслуживания заявок соответственно.

Средняя длина очереди , и среднее число заявок в системе .

Дискретное и непрерывное приближения. Другие методы оценки ориентированы не на поиск приближенного решения исходной задачи, а на точное решение упрощенно сформулированной задачи. Уравнения, описывающие работу системы G/G/1, преднамеренно преобразуются к такому виду, при котором полученная система уравнений может быть решена.

В теории массового обслуживания показано, что если исходные величины являются дискретными, можно определить точное распределение времени ожидания. На этом основывается метод дискретного приближения, при котором промежутки времени между моментами поступления заявок и длительности обслуживания аппроксимируются дискретными распределениями.

Для исследования нестационарных систем и режимов перегрузки оказывается полезным метод непрерывного приближения. Процессы поступления и ухода заявок -- это ступенчатые вероятностные процессы (рис. 3). Но когда длины очередей значительно больше единицы, а времена ожидания существенно больше среднего времени обслуживания, становится разумной замена этих ступенчатых процессов сглаженными непрерывными функциями времени, поскольку величины отдельных ступенек малы по сравнению со средними значениями (рис. 6).

Когда Х(t) становится значительно больше единицы, на основании закона больших чисел можно ожидать лишь небольшого относительного отклонения этой величины от ее среднего значения

Рис. 6. Временная диаграмма процессов поступления и ухода заявок с непрерывной аппроксимацией зависимостей количества заявок от времени М [х(t)]= На этом основывается приближение первого порядка, которое заключается в замене вероятностного процесса его средним значением, зависящим от времени, т. е. детерминированным процессом . Это относится и к процессу ухода заявок . Тогда число заявок в системе тоже представляет собой детерминированную непрерывную функцию времени:

(23)

Функции и определяются из зависимостей:

(36)

(37)

--число поступивших и покинувших систему заявок к нулевому моменту времени.

Диффузионная аппроксимация. Непрерывное приближение является довольно грубым, поскольку не учитывает случайный характер процессов поступления и ухода заявок. По методу диффузионной аппроксимации непрерывное приближение усовершенствуется путем учета флуктуаций относительно среднего значения. С этой целью случайный процесс (23) заменяется марковским процессом диффузионного типа ч (t) с непрерывным временем и непрерывным множеством состояний. Диффузионный процесс определяется коэффициентом сноса

и коэффициентом диффузии

Эти коэффициенты выражаются через параметры исходной модели. Для системы G/G/1 считается, что при больших t распределение Х (t) является приближенно нормальным с математическим ожиданием и дисперсией и распределение Y(t) тоже приближенно нормальное с математическим ожиданием и дисперсией . Тогда коэффициент сноса

(38)

и коэффициент диффузии

(39)

В связи с тем, что процесс п (t) не может принимать отрицательных значений, для аппроксимирующего процесса ч(t) задается граничное условие, удерживающее его траекторию на неотрицательной полуоси. Например, при достижении ч(t) =0 совершается скачок в целочисленные точки положительной полуоси, выполняемый с заданным распределением вероятностей после экспоненциальной задержки в нуле.

Применение диффузионной аппроксимации дает возможность получения оценок различных характеристик СМО. В частности, для системы G/G/1 средняя длина очереди в стационарном режиме определяется по формуле

(40)

при постоянных коэффициентах сноса и диффузии, соответствующих случаю независимых от длины очереди вероятностных характеристик поступления и обслуживания заявок.

Контрольные вопросы

Одноканальная СМО для описания ВС.

Как определяется коэффициент загрузки ВС?

Как определяется число заявок в СМО?

Как определяется длина очереди в СМО?

Как определяется время реакции в СМО?

Формулы Литтла.

Многоканальная СМО для описания ВС.

Основные характеристики многоканальной СМО.

Для каких систем используются методы приближенной оценки характеристик?

Литература

1. Альянах И.Н. Моделирование вычислительных систем, Л.: Машиностроение, 1988 г. - 223 стр.

2. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: Наука, 1980 г. - 208 стр.

3. Зобов Б.И., Сурков А.В. Основы моделирования вычислительных систем. М.: МЛТИ, 1982 г. -32 стр.

4. Масков А.И. моделирование вычислительных систем. Пермь: ПГУ, 1982 г. - 95 стр.

Лекция 11. НЕСТАЦИОНАРНЫЕ РЕЖИМЫ ФУНКЦИОНИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ (2 часа)

План

1. Нестационарные режимы функционирования вычислительных систем

2. Характеристики вычислительных систем как стохастических сетей

1. Нестационарные режимы функционирования вычислительных систем

Переходные процессы. До сих пор рассматривались характеристики ВС в стационарном установившемся режиме. Однако на практике не менее важным является анализ нестационарных режимов. Значения выходных характеристик в нестационарных режимах функционирования ВС можно определить для одних систем путем численного решения уравнений Колмогорова задавая в них интенсивности как функции времени для других систем -- в результате непрерывной или диффузионной аппроксимации процессов.

Частным случаем нестационарных режимов является переходный процесс, когда, например, в начальный момент времени в системе отсутствуют очереди и начинают поступать заявки с постоянной интенсивностью л. Важно уметь определять, когда установится стационарный режим.



В работе приводятся результаты анализа переходных процессов для системы M/G/1. Интенсивность входящего пуассоновского потока принималась равной 0,95 заявок в минуту, а среднее время обслуживания v =1 мин. Коэффициент загрузки с = 0,95. Рассматривались следующие распределения длительности обслуживания:

1) экспоненциальное распределение

2) нормированное распределение Эрланга 8-го порядка со средним, равным восьми,



3) комбинация экспоненциального распределения со средним значением 4 и распределения Эрланга 4-го порядка со средним значением 2/3

Зависимости среднего времени ожидания заявок в очереди в течение переходного процесса для этих случаев показаны на рис. 1. Установившиеся значения соответственно равны 19; 10,69 и 35,2 мин. Если принять длительность переходного процесса равной бремени, в течение которого среднее время ожидания достигает 0,8 от установившегося значения, то для этих случаев она соответственно составит 15,2; 8,55 и 28,2 ч. За эти времена система успевает обслужить 867, 487 или 1605 заявок. Можно утверждать, что ВС с суточным циклом никогда не работают практически в установившемся режиме при большой загрузке. Этот вывод можно распространить на ВС с большей длительностью цикла, если они имеют соответственно меньшие интенсивности поступления и обслуживания заявок.

Режимы перегрузок. Методы непрерывной и диффузионной аппроксимации дают возможность проанализировать поведение системы при изменяющихся во времени интенсивностях прихода и обслуживания заявок. С практических позиций наибольшую важность представляет анализ режима перегрузок, когда в течение некоторого интервала времени коэффициент загрузки с > 1.

Рассмотрим этот режим на упрощенном примере (рис. 2). Предположим, что в одноканальную систему поступает одномерный поток заявок с интенсивностью . Заявки обслуживаются в порядке поступления с постоянной интенсивностью

В начальный момент t₀ коэффициент загрузки с < 1. В системе. имеются заявки, накопление которых обусловлено случайным характером их поступления и обслуживания.

Затем интенсивность поступления заявок начинает расти, достигая максимального значения. С момента t₁ становится с > 1 и увеличивается число заявок в системе. При максимальном число заявок n(t) растет линейно, стремясь к бесконечности. Но в связи с тем, что в момент t₂ интенсивность поступления начинает уменьшаться, рост n(t) замедляется и достигает максимума в момент t₃ при р = 1.

В режиме перегрузки накопление заявок в системе определяется в основном не случайными факторами, а превышением средней интенсивности поступления над интенсивностью обслуживания. С момента t₃ число заявок уменьшается до момента t₄ принимая установившееся значение. Длительность рассасывания числа заявок может быть приближенно оценена по равенству заштрихованных на рисунке площадей, обозначенных плюсом и минусом.

Важно подчеркнуть, что такая система может быть вполне работоспособна, если максимальное число заявок в системе, а соответственно и время реакции не превысят допустимых значений. При правильном задании стохастических ограничений, систему можно считать работоспособной даже при кратковременном превышении допустимых значений математическим ожиданием времени реакции. Этот подход дает возможность выбрать производительность ВС не по максимальной интенсивности поступления заявок, обеспечивая с < 1, а на существенно более низком уровне. Отдельные вопросы анализа нестационарных ВС рассматриваются в работах.