1. элементы теории марковских случайных процессов. При проектировании средств вычислительной техники широкое - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
10. анализ систем по схеме марковских случайных 1 67.76kb.
Теория случайных процессов 1 46.03kb.
4. Моделирование по схеме марковских случайных процессов 1 139.99kb.
Рабочая учебная программа По дисциплине: Избранные главы теории вероятностей... 1 180.17kb.
Лекция №2 «История развития вычислительной техники»» по дисциплине... 1 76.23kb.
О существовании случайных процессов 1 22kb.
Моделирование бизнес процессов управления: idef 1 161.52kb.
Техническое обслуживание средств вычислительной техники и компьютерных... 1 20.89kb.
Техническое обслуживание средств вычислительной техники и компьютерных... 1 20.85kb.
Викторина по истории вычислительной техники 1 39.71kb.
Учебная программа Дисциплины р6 «Аппаратные средства вычислительной... 1 164.8kb.
«оценка состояний эвс на основе марковских моделей» 1 60.97kb.
Направления изучения представлений о справедливости 1 202.17kb.

1. элементы теории марковских случайных процессов. При проектировании средств вычислительной - страница №1/1

1. элементы теории марковских случайных процессов.
При проектировании средств вычислительной техники широкое

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

и синтеза вычислительных структур, которые можно рассматривать

как стохастические системы без последствия.


1.1. Понятие марковского случайного процесса.
Функционирование широкого класса систем можно представить

как процесс перехода из одного состояния в другое под

воздействием каких-либо причин. Например, процесс

функционирования ЭВМ характеризуется тем, что в каждый момент

времени обработкой информации заняты те или иные блоки. Процесс

прохождения обрабатываемой информации по блокам ЭВМ можно

рассматривать как процесс перехода системы из одного состояния в

другое. В полной мере это отнорсится и к процессу

функционирования ЭВМ с точки зрения надежности. В каждый момент

времени некоторые узлы работоспостбны, а некоторые отказали и

восстанавливаются. Если каждому возможному множеству

работоспособных (или отказывающих) элементов поставить в

соответствие множество состояний системы, то отказы и

восстановления элементов будут отражаться переходом объекта из

одного состояния в другое.

Пусть имеется некоторая физическая система S, которая в

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

Si. Если состояния системы меняются во времени случайным

образом, то процесс смены состояний можно рассматривать как

случайный процесс, описываемый случайной функцией X(b).

Полное множество состояний Si исследуемой системы может

----


быть либо конечным (i = 1, n), либо бесконечно большим.

Большинство реальных систем имебт дискретное конечное

пространство состояний. Последовательность состояний такой

----


системы Si (i = 1, n) и сам процесс переходов из состояния в

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

случайные цепи.

В зависимости от времени пребывания системы в каждом

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

непрерывным временем предполагают, что переход системы из одного

состояния в другое может осуществляться в любой момент времени,

т. е. время пребывания системы в каждом состоянии представляет

непрерывную случайную величину.

Для систем с дискретным временем время пребывания системы в

каждом состоянии фиксированное, а моменты переходов t1, t2, ...,

tk размещаются на временной оси через равные промежутки и

называются "шагами" или "этапами". Время нахождения системы в

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

Таким образом, случайный процесс с непрерывными состояниями

и непрерывным временем функционирования описывается непрерывной

случайной функцией времени. Непрерывные и дискретные цепи

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

При исследовании непрерывных и дискретных случайных цепей

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

системы. Граф состояний системы представляет собой совокупность

вершин, изображающих возможные состояния системы Si, и

совокупность ветвей, изображающих возможные переходы системы из

одного состояния в другое.

1.2. МАРКОВСКИЕ СЛУЧАЙНЫЕ ПРОЦЕССЫ

С ДИСКРЕТНЫМИ СОСТОЯНИЯМИ И ДИСКРЕТНЫМ ВРЕМЕНЕМ


Дискретные цепи Маркова
Пусть имеется некоторая система S, которая в процессе функцио-

нирования может принимать различные состояния Si, i=1..n. Если сос-

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

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

Случайный процесс, протекающий в системе S, называется марковс-

ким, если для любого момента времени t0 вероятность любого состоя-

ния системы при t>t0 зависит только от ее состояния при t=t0 и не

зависит от того, как и когда система пришла в это состояние. Если

число состояний Si, которые система может принимать, конечно, то

такие системы описывает марковский случайный процесс с дискретными

состояниями, или марковская цепь.

Если переходы системы из одного состояния в другое возможны в

строго определенные, заранее фиксированные моменты времени tj, то

такую систему описывает марковский случайный процесс с дискретным

временем. Марковский случайный процесс с диcкретными состояниями и

дискретным временем называют дискретной марковской цепью.

Обычно марковскую цепь изображают в виде графа, вершины которо-

го соответствуют возможным состояниям системы Si, а дуги - возмож-

ным переходам системы из состояния Si -> Sj. Каждой дуге соответс-

твует переходная вероятность Pij(k)=P[Sj(k)/Si(k-1)] - это условная

вероятность перехода системы на К-ом шаге в состояние Sj при усло-

вии, что на предыдущем (К-1)-ом этапе система находилась в состоя-

нии Si.

Марковская цепь называется однородной, если переходные вероят-



ности не зависят от номера шага. Если переходные вероятности меня-

ются от шага к шагу, марковская цепь называется неоднородной.

Полным описанием однородной марковской цепи служит матрица пе-

реходных вероятностей

----> j

| P11 P12 .... P1j .... P1n|



| P21 P22 .... P2j .... P2n| n ____

|Pij| = | ..........................| SUMMA(Pij)=1; i=1, n

| | Pi1 Pi2 .... Pij .... Pin| j=1

| | ..........................|

i | Pn1 Pn2 .... Pnj .... Pnn|
Для неоднородной марковской цепи требуется К матриц, где К -

число шагов.

Определим для однородной марковской цепи вероятности всех сос-

тояний системы на каждом шаге по заданной матрице переходных веро-

ятностей |Pij|, причем известно начальное состояние системы.

Пусть в начальный момент t0 система находится в состоянии Si.

Тогда Pi(0)=1, Pj(0)=0, j=1,2,..,n, j=/=i. Найдем вероятности состоя-

ний после 1-го шага P1(1)=Pi1, P2(1)=Pi2, ..., Pj(1)=Pij,

...,Pn(1)=Pin. Найдем вероятность состояний после 2-го шага, расс-

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

- после 1-го шага система была в состоянии S1;

- после 1-го шага система была в состоянии S2;

.............................................

- после 1-го шага система была в состоянии Sn.

Вероятности гипотез известны и равны вероятностям состояний си-

стемы после 1-го шага.

Тогда по формуле полной вероятности:

P1(2)=P1(1)*P11+P2(1)*P21+...+Pn(1)*Pn1


P2(2)=P1(1)*P12+P2(1)*P22+...+Pn(1)*Pn2

.......................................

n ___

Pi(2)=SUMMA [Pj(1)*Pji] i=1,n



j=1

Аналогично после 3-го шага вероятности определяются выражением

n ___

Pi(3) = SUMMA [Pj(2)*Pji] i=1,n



j=1

После К-го шага

n ___

Pi(k)= SUMMA [Pj(k-1)*Pji i=1,n



j=1
Аналогично для неоднородной марковской цепи

n

Pi(k)= SUMMA [Pj(k-1)*Pji(k)] (2)



j=1
Все многообразие марковских цепей подразделяется на эргодичес-

кие и разложимые.

Разложимые марковские цепи содержат невозвратные состояния, на-

зываемые поглощающими. Из поглощающего состояния нельзя перейти ни

в какое другое. На графе поглощающему состоянию соответствует вер-

шина, из которой не выходит ни одна дуга. В установившемся режиме

поглощающему состоянию соответствует вероятность, равная 1.

Эргодические марковские цепи описываются сильно связанным гра-

фом. Это означает, что в такой системе возможен переход из любого

состояния Si в любое состояние Sj (i,j=1..n) за конечное число ша-

гов.

Для эргодических цепей при достаточно большом времени функцио-



нирования (t стремится к бесконечности) наступает стационарный ре-

жим, при котором вероятности Pi состояний системы не зависят от

времени и не зависят от распределения вероятностей в начальный мо-

мент времени, т.е. Pi=const.

Каждая компонента Pi вектора таких стационарных вероятностей

характеризует среднюю долю времени, в течение которого система на-

ходится в рассматриваемом состоянии Si за время наблюдения, измеря-

емое К шагами.

Для определения стационарных вероятностей Pi нахождения системы

в состоянии Si (i=1..n) нужно составить систему n линейных однород-

ных алгебраических уравнений с n неизвестными:

n

Pi= SUMMA(Pj*Pji) i=1..n (3)



j=1

Причем, искомые вероятности должны удовлетворять условию:

n

SUMMA(Pi) = 1



j=1 n

или, что равносильно Pi=1- SUMMA Pj (4)

j=1

j=/=i


Поэтому любое уравнение системы (3) можно заменить уравнением

(4).


Систему линейных алгебраических уравнений (3) удобно составлять

непосредственно по размеченному графу состояний. При этом в левой

части уравнения записывается вероятность состояния, соответствующе-

го рассматриваемой вершине графа, а в правой части - сумма произве-

дений. Число слагаемых соответствует числу дуг графа, входящих в

рассматриваемое состояние. Каждое слагаемое представляет произведе-

ние вероятности того состояния, из которого выходит дуга графа, на

переходную вероятность, которой помечена соответствующая дуга гра-

фа.
Пример.
Центральный процессор мультипрограммной системы в любой

момент времени выполняет либо программы пользователя, либо

программы операционной системы, либо находится в состоянии

ожидания.

Продолжительность нахождения системы в каждом состоянии

кратна длительности шага дельтаt.

Определить коэффициент использования процессора, если

задана матрица вероятностей переходов из одного состояния в

другое.

+----+-----+-----+-----+



| \ j| S1 | S2 | S3 |

|i \ | | | |

+----+-----+-----+-----|

| S1 | 0,7 | 0,2 | 0,1 |

| S2 | 0,8 | 0,1 | 0,1 |

| S3 | 0,8 | 0,05| 0,15|

+----+-----+-----+-----+
S1 - состояние, в котором реализуются задачи пользователя

S2 - состояние, в котором реализуются программы

операционной системы

S3 - состояние простоя

Граф функционирования системы имеет вид:
+-----+0,7 +-----+0,1

| | | |


| +--+--+ 0,2 +--+--+ |

+->| S1 +--------------------->| S2 |<-+

| |<---------------------| |

+---+-+ 0,8 +-+---+

^ | | ^

| | | |


| | | |

| | | |


| | | |

| | | |


| |0,1 +-----+ 0,1| |

| +-------->| |<---------+ |

+-----------| S3 +------------+

0,8 | |<-+ 0,05

+--+--+ |

| |


+-----+0,15
Составим для установившегося режима систему линейных

алгебраических уравнений.


Р1 = 0,7P1 + 0,8P2 + 0,8P3

Р2 = 0,2P1 + 0,1P2 + 0,05P3

Р3 = 0,1P1 + 0,1P2 + 0,15P3

P1 + P2 + P3 = 1


В результате решения получаем значение вероятностей

состояния в установленном режиме:

Р1 = 0,749; Р2 = 0,154; Р3 = 0,097.
Коэффициент простоя процессора Кп = Р3 = 0,097.

Коэффициент использования Ри = 1 - Кп = 0,903, при этом на

обработку программ пользователя затрачивается 74,3% времени, а

на обслуживание операционной системы - 15,4%.

1.3. Непрерывные марковские цепи.
Непрерывные марковские цепи описывают функционирование

систем, принимающих в процессе работы конечное число состояний

-----

Si (i = 1, n) и осуществляющих переходы из одного состояния в



----

другое (Si --> Sj, i, j = 1, n) случайным образом в произвольный

момент времени t. Иначе говоря, время пребывания системы в

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

Случайный процесс с непрерывным временем называется

непрерывной марковской цепью, если поведение системы после

произвольного момента времени t0 зависит только от состояния

процесса в момент времени t0 и не зависит от предыстории

процесса, предшествующей моменту времени t0.

Определим для непрерывной марковской цепи вероятности всех

---

состояний системы для любого момента времени Pi(t), i = 1,n. Так



как для любого момента времени t все состояния системы образуют

полную группу событий, то

n

SUMMA Pi(t) = 1



i=1

Рассмотрим параметры, определяющие непрерывную марковскую

цепь.

Пусть система в момент времени t находится в состоянии Si.



Рассмотрим элементарный промежуток времени DELTAt, примыкающий

к моменту времени t. За интервал DELTAt система может

перейти из состояния Si в состояние Sj с переходной вероятностью

Pij(t,DELTAt). зависящей в общем случае как от t, так и от DELTAt.

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

ширине интервала DELTAt при условии, что DELTAt --> 0:


Pij(t,DELTAt)

lim ---------------- = LAij(t) (1)

DELTAt->0 DELTAt
Эта характеристика называется интенсивностью перехода или плот-

ностью вероятности перехода и в общем случае зависит от t.

Из формулы (1) следует, что при малом DELTAt вероятность

перехода Pij(t,DELTAt) с точностью до бесконечно малых высших

порядков равна
Pij(t,DELTAt) ~= LAij(t)*DELTAt
Если плотности вероятностей переходов представляют собой

функции времени LAij(t), марковский процесс называется неод-

нородным.

Если все плотности вероятностей переходов не зависят от t

(т.е. от начала отсчета элементарного участка DELTAt), то

марковский процесс называется однородным (LAij(t) = LAij

= const).

Для непрерывных марковских цепей интенсивности переходов

проставляются у соответствующих дуг графа. Такой граф называется

размеченным.

Кроме интенсивностей переходов, для описания непрерывных

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

состояний системы в исходный (нулевой) момент времени

|P(0)| = (P1(0), P2(0), ..., Pn(0)).

Зная множество состояний системы, значения интенсивностей

переходов LAij(t), а также вектор начальных вероятностей

----

системы |P(0)|, определим вероятности состояний Pi(t), i = 1, n



системы, граф которой имеет вид:

+------+


| |Pii(DELTAt)

+---+---+ |

P1i(DELTAt) | |<-+ Pi,n(DELTAt)

+---------------->| Pi(t) +------------------+

| +---------------| |<---------------+ |

| |Pi1(DELTAt) +--+---++ Pn,i(DELTAt)| |

| | ^ | ^ | | |

| | | | | | | |

| | +----+ | | +------+ | |

| | | +---+ +-----+ | | |

| | (1)| |(2) (3)| |(4) | |

| V | V | V | V

+--+----+ +-+-----+ +--+----+ +--+----+

| | | | | | | |

| P1(t) |------|Pi-1(t)|-----|Pi+1(t)|-----| Pn(t) |

| | | | | | | |

+-------+ +-------+ +-------+ +-------+
(1) - Pi-1,i(DELTAt) (2) - Pi,i-1(DELTAt)

(3) - Pi+1,i(DELTAt) (4) - Pi,i+1(DELTAt)

Как следует из приведенного графа, марковская цепь однородна,

так как вероятности перехода не зависят от t.

Для момента времени t+DELTAt справедливо соотношение

n

Pi(t + DELTAt) = SUMMA Pj(t) * Pji(DELTAt) =



j = 1

n

= Pi(t) * Pii(DELTAt) + SUMMA Pj(t) * Pji(DELTAt)



j = 1

j <> i


Из свойства матрицы переходных вероятностей (Ш-4) следует,

что


n

Pii(DELTAt) = 1 - SUMMA Pij(DELTAt)

j = 1

j <> i
Тогда Pi(t + DELTAt) =


n n

= Pi(t)*{1 - SUMMA Pij(DELTAt)} + SUMMA Pj(t) * Pji(DELTAt)

j = 1 j = 1

j <> i j <> i


или Pi(t + DELTAt) - Pi(t) =
n n

= - Pi(t) * SUMMA Pij(DELTAt) + SUMMA Pj(t) * Pji(DELTAt)

j = 1 j = 1

j <> i j <> i


Разделим обе части равенства на DELTAt и устремим DELTAt

к нулю


Pi(t + DELTAt) - Pi(t)

lim = -------------------------- =

DELTAt->0 DELTAt
n Pij(DELTAt)

= - Pi(t) * SUMMA lim -------------- +

j = 1 DELTAt->0 DELTAt

j <> i
n Pji(DELTAt)

+ SUMMA Pj(t) * lim --------------

j = 1 DELTAt->0 DELTAt

j <> i
В результате получим систему дифференциальных уравнений

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

ее автора - советского математика Колмогорова А. Н.
dPi(t) , n n

------- = Pi(t) = - Pi(t) * SUMMA LAij + SUMMA Pj(t) * LAij

dt j = 1 j = 1

j <> i j <> i


Pi(0) = Pi0 - вектор начальных условий.

----


i = 1, n
Интегрирование этой системы по времени позволяет получить

вероятности состояний как функции времени Pi(t).

Существенно, что в системе Колмогорова можно ограничиться

n - 1 уравнением. Дополнительно используется условие нормировки


n

SUMMA Pj = 1.

j=1
Анализируя дифференциальные уравнения Колмогорова, можно

сформулировать формальное правило для их написания непосредственно

по размеченному графу системы.

В левой части уравнения стоит производная от вероятности

рассматриваемого состояния по времени, а в правой части -

столько слагаемых, сколько дуг графа связано с рассматриваемым

состоянием. Каждое слагаемое равно произведению плотности

вероятности перехода, соответствующей данной дуге графа, на

вероятность того состояния, из которого исходит дуга графа. Если

стрелка направлена из рассматриваемого состояния,

соответствующее произведение имеет знак минус. Если стрелка

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

Это правило составления дифференциальных уравнений

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

справедливо для любой непрерывной марковской цепи.

Для эргодических однородных марковских цепей существует ста-

ционарный режим при t --> БЕСКОНЕЧНОСТЬ. При стационарном режиме

вероятности состояний стремятся к некоторым

установившимся значениям - предельным вероятностям
lim Pi(t) = Pi,

t -> БЕСКОНЕЧНОСТЬ


которые постоянны и не зависят от начального состояния системы.

Поскольку в установившемся режиме вероятности состояний

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

нулю. Поэтому система дифференциальных уравнений Колмогорова с

постоянными коэффициентами вырождается в систему линейных алгебра-

ических уравнений.

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

характеризуют среднюю долю времени, в течение которого система

находится в данном состоянии при наблюдении за системой в

течение достаточно продолжительного времени (на бесконечном интер-

вале).

1.4. Потоки событий.


Переход системы в некоторое состояние Si называется

событием. В процессе работы система неоднократно может

возвращаться в состояние Si. Последовательность таких

однородных событий образует поток событий Si', Si", ... .

Поток событий удобно отображать в виде отметок на оси

времени, соответствующих моментам наступления событий.

T1 T2 Ti

--+----+--+---+--+-----+---------> t

0
Поток называется ординарным, если события в нем происходят

поодиночке.

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

регулярным или детерминированным и полностью характеризуется

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

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

распределения системы случайных величин (Т1, Т2, ....., Тn).

На практике наиболее часто приходится иметь дело с

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

----


событиями Ti (i = 1, n) - непрерывные случайные величины. Такой

случайный поток характеризуется многомерной плотностью вероят-

ности f(TAU1, TAU2,......,TAUn), где TAUi - конкретные значения

случайных величин Тi.

Поток назывется стационарным, если его характеристики не

изменяются во времени. Вероятность попадания того или иного числа

m событий на участок оси времени t,t+TAU зависит только от TAU и не

зависит от t. Интенсивность или плотность потока событий, то есть

среднее число событий в единицу времени, постоянна:LA = const.

В узком смысле стационарность означает независимость плотности

вероятности f(TAU1, TAU2,......,TAUn) от выбора начала отсчета.

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

называется потоком с последействием, ибо для любого момента

времени последующее течение потока находится в вероятностной

зависимости от предыдущего.

Если случайные величины Ti являются независимыми, то

случайный поток называется потоком с ограниченным

последействием и для него справедливо:

f(TAU1, TAU2,......,TAUn) = f1(TAU1)*f2(TAU2)*.......*fn(TAUn).

Случайный поток событий называется потоком без

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

число событий, попадающих на один из них, не зависит от того,

сколько событий попало на другие участки. Условие отсутствия

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

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

fi(TAUi) = f(TAUi), i=1,2,....,n

Поток называется пуассоновским, если число m событий потока,

попадающих на участок TAU, распределено по закону Пуассона

m -a

pm = (a / m!) * e



где а - среднее число событий, попадающих на участок TAU, равное

для стационарного потока a = LA*TAU.

Определим функцию распределения длины интервала T в стационарном

пуассоновском потоке

F(TAU) = P(T < TAU)

Выразим F(TAU) через вероятность P(T >= TAU)= F0(TAU) того,

что в интервал TAU не попадает ни одно из событий:

0 -a -a


F(TAU) = 1 - F0(TAU) = 1 - p0 = 1 - a /0! * e = 1 - e

Для стационарного пуассоновского потока справедливо:

-LA*TAU -LA*TAU

F(TAU) = 1 - e , f(TAU) = LA*e ,

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

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

1

M(Ti) = SIGMA(Ti) = ------ .



LA

где LA - интенсивность потока, характеризующая среднее

число событий в единицу времени

1

LA = ------- - величина, обратная среднему времени



M(Ti)

между событиями.

Cтационарный пуассоновский поток является примером случайного

потока без последействия. Для него интервал времени от начала

отсчета до наступления первого события представляет собой непрерывную

случайную величину T1, распределенную по экспоненциальному закону с

функцией плотности распределения
-LA*TAU1

f1(TAU1) = LA*e = f(TAU1) = f(TAUi) = f(TAU),

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

Стационарный пуассоновский поток событий, обладающий свойствами

ординарности, стационарности и отсутствия последействия, называется

простейшим потоком.

Если процесс переходов в системе происходит под

воздействием простейшего потока, то такой процесс является

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

НМЦ совпвдает с интенсивностью потока переходов LA.


Пример.

Двухпроцессорная вычислительная система предназначена для

обработки простейшего потока задач, поступающих с интенсивностью

LA. Производительность процесоров, соответственно, равны B1

и B2, причем B1 > B2. Трудоемкость задач представляет случайную

величину со средним значением teta.

Задача в первую очередь принимается на обслуживание

процессором, имеющим большую производительность. Если оба

процессора заняты, пользователь получает отказ.

Определить в установившемся режиме вероятность отказа Ротк,

коэффициенты загрузки процессоров KSI1, KSI2.
Рассмотрим возможные состояния системы, которые

определяются состояниями процессоров:

S00 - оба процессора простаивают;

S10 - первый процессор занят решением задач, второй

простаивает;

S01 - второй процессор занят, первый простаивает;

S11 - оба процессора заняты решением задач.
Граф функционирования системы имеет вид:
+-----+ LA

MU2 | S00 +-------------+

+-------->| |<----------+ |

| +-----+ MU1 | |

| | V

+--+--+ +-+---+



| S01 | | S10 |

| | | |


+---+-+ +-+---+

^ | | ^


| | LA +-----+ LA | |

| +-------->| S11 |<---------+ |

+-----------| +------------+

MU1 +-----+ MU2


B1

Здесь MU1 = ---- - интенсивность решения задач первым

teta

процессором;


B2

MU2 = ---- - интенсивность решения задач вторым процессором.

teta
По графу запишем систему линейных дифференциальных

уравнений А.Н.Колмогорова.


dP00(t)

--------- = LA*P00(t) + MU1*P10(t) + MU2*P01(t)

dt

dP10(t)


--------- = LA*P00(t) - (MU1 + LA)*P10(t) + MU2*P11(t)

dt

dP01(t)



--------- = - (LA + MU2)*P01(t) + MU1*P11(t)

dt

dP11(t)



--------- = LA*P10(t) + LA*P01(t) - (MU1 + MU2)*P11(t)

dt

P00(t) + P10(t) + P01(t) + P11(t) = 1



Пусть начальные условия заданы вектором вероятностей:
P00(0) = 1, P10(0) = P01(0) = P11(0) = 0.
Решение этой системы при заданных начальных условиях

позволяет определить вероятности состояний как функции времени.

Последние, в свою очередь, позволяют определить требуемые

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

Поскольку марковский процесс, описывающий работу

вычислительной системы, является эргодическим, существует

стационарный режим, при котором вероятности состояний стремятся

к постоянным величинам.

При этом система дифференциальных уравнений Колмогорова

вырождается в систему линейных уравнений:


-LA*P00 + MU1*P10 + MU2*P01 = 0

LA*P00 - (MU1 + LA)*P10 + MU2*P11 = 0

-(LA + MU2)*P01 + MU1*P11 = 0

LA*P10 + LA*P01 - (MU1 + MU2)*Р11 = 0

P00 + P10 + P01 + P11 = 1
Выражения для вероятностей в установившемся режиме имеют

вид:


MU1*MU2*(2*LA + MU1 + MU2)

P00 = ----------------------------- * Р11;

LA**2 * (LA + MU2)
MU1

P01 = -------------- * Р11;

LA + MU2
MU2*(LA + MU1 + MU2)

P10 = ------------------------- Р11;

LA*(LA + MU2)
LA**2

P11 = ----------------------------------------------------------

MU1*MU2

LA**2 * ----------- * (2*LA+MU1+MU2)+LA*(MU1+MU2)



LA + MU2
Вероятность отказа совпадает с вероятностью состояния, в

котором оба процессора заняты, т. е. Ротк = Р11.

Коэффициенты загрузки процессоров KSIi (i = 1,2) представляют

собой вероятности пребывания соответствующих процессоров в занятом

состоянии:

KSI1 = Р10 + Р11;

KSI2 = Р01 + Р11.

Примерами потоков с ограниченным последействием являются

потоки Эрланга. Они образуются путем закономерного просеивания

простейшего потока. Под закономерным просеиванием будем понимать

такую процедуру, в результате которой безусловно исключается

некоторая последовательность событий в исходном потоке.

Если из исходного простейшего потока исключить (К - 1)

событие, а каждое К-е сохранить, то получим поток Эрланга К-го

порядка.
+-+ +-+ +-+

-|+|--+---+--+--|+|------+--+----+---|+|-+----->t

+-+ +-+ +-+

<- K-1-> <- Ti -><- K-1 ->

<------- Tk* ------->
Случайная величина Тк* интервала между соседними событиями

потока Эрланга К-го порядка представляет сумму К независимых

случайных величин, подчиненных показательному закону

распределения

k

Tk* = SUMMA Ti. Плотность распределения имеет вид:



i = 1

k-1


LA(LA*TAUk) -LA*TAUk

fk(TAUk) = -------------------- e

(K -1)!
Обычно случайную величину Tk* нормируют коэффициентом К,

т. е.


Tk*

Tkн = -----

К
Для нормированного потока Эрланга К-го порядка
1 1

M(Tkн) = -------- D(Tkн) = ----------------

LA (LA*K)**2
Таким образом, при неограниченном увеличении порядка К

нормированный поток Эрланга приближается к регулярному потоку с

1

постоянными интервалами, равными -------- .



LA
Нормированный поток Эрланга в зависимости от порядка К

позволяет получить любую степень последействия, от полного

отсутствия (К = 1) до жесткой статистической связи (К =

бесконечности). Благодаря этому реальный поток событий с

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

нормированным потоком Эрланга соответствующего порядка, имеющим



примерно те же математическое ожидания и дисперсию, что находит

широкое применение при моделировании произвольных потоков.




Если бы природа имела столько законов, как государство, сам Господь не в состоянии был бы управлять ею. Людвиг Берне
ещё >>