MS_glavy_123 (Учебное пособие), страница 5

Рис. 8

, и , интерпретируют работу генераторов заявок ( и соответственно). Пунктирными прямоугольниками объединены позиции, представляющие один единый элемент СМО.

Приведенное в учебном пособии описание основных положений по СП позволяет читателям самостоятельно разобраться с работой примеров СП для СМО.

Рис. 9

Материалы для углубленного изучения теоретических основ СП, доказательств теорем (например, о достижимости состояний и др.), хорошо изложены в монографии [6].

2.1.2. Марковские случайные процессы

Случайный процесс, протекающий в системе называется марковским случайным процессом (или «процессом без последействия»), если он обладает следующим свойством: для каждого момента времени: вероятность любого состояния системы в будущем (при >0) зависит только от ее состояния в настоящем (при t= ) и не зависит от того, когда и каким образом система пришла в это состояние.

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

Случайный процесс называется процессом, с дискретным временем, если переходы системы из состояния в состояние возможны только в строго определенные, фиксированные моменты времени. Эти моменты принято называть «шагами» или «этапами» процесса.

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

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

образуют полную группу и несовместны.

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

Вероятности переходов (переходные вероятности) можно запи­сать как условные вероятности .

Легко видеть, что вероятности состояний системы после k-гo шага

если вероятности переходов от шага к шагу не меняются (цепь Маркова однородна).

Рассмотрим теперь непрерывную цепь Маркова.

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

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

Рис. 10

Поставим задачу: найти одну из вероятностей состояний, на­пример . Придадим t малое приращение и найдем вероят­ность того, что в момент t+ система будет находиться в состоянии .

Могут представиться две возможности:

1) в момент t система уже была в состоянии , а за время не вышла из этого состояния; это происходит с вероятностью ;

2) в момент t система была в состоянии , а за время пере­шла из него в состояние . Вероятность совмещений этих событий

Применяя правило сложения вероятностей, получим

)= +

Раскроем скобки в правой части, перенесем в левую и раз­делим обе части неравенства на ; получим

Устремляя к нулю и переходя к пределу, видим, что левая часть есть ни что иное как производная функции . Рассуждая аналогично, получим систему дифференциальных уравнений, на­зываемых уравнениями Колмогорова. Интегрирование этих урав­нений даст искомые вероятности состояний как функции времени. Начальные условия должны быть заданы: если в момент t = 0 сис­тема находилась в состоянии , то надо принять .

Оказывается, что все уравнения построены по определенному правилу: в левой части каждого уравнения стоит производная вероятности состояния, а правая часть содержит столько чле­нов, сколько стрелок связано с данным состоянием. Если стрелка

направлена из состояния, соответствующий член имеет знак «минус»; если в состояние — знак «плюс». Каждый член равен произведению плотности вероятности перехода, соответствую­щей данной стрелке, умноженной на вероятность того состоя­ния, из которого исходит стрелка.

Это правило составления дифференциальных уравнений для ве­роятностей переходов является общим и справедливо для любой непрерывной марковской цепи.

2. 1. 3. Системы массового обслуживания

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

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

Поток заявок является стационарным, если его характеристики не изменяются во времени, и нестационарным — в противном случае.

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

.

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

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

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

,

где — вероятность того, что за время в систему поступит ровно k заявок. Математическое ожидание и дисперсия распределения Пуассона .

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

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

Плотность распределения интервала времени между двумя соседними заявками в потоке Эрланга k-ro порядка

При k=1 поток будет простейшим.

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

(2. 1)

где — параметр распределения, Г( ) — гамма-функция

обладающая следующими свойствами: Г(х + 1) = хГ(х), Г(n) = (n- 1)!

Математическое ожидание и дисперсия гамма-распределения соответственно равны и . Обозначив - длительность обслуживания заявки, запишем (2.1) в виде

(2.2)

где — математическое ожидание длительности обслуживавания.

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

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

для этого закона легче получить аналитические решения;

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