Моделирование систем массового обслуживания (стр. 5 из 7)

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

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

,

где p(t) – вероятность попадания в какое-либо состояние

l - множество определенных коэффициентов

Для стационарного потока:

- базисная модель

- интерфейсная модель

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

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

Методика вывода уравнений Колмогорова

-интенсивность перехода

1. Найдем вероятность того, что в момент времени t система

находится в состоянии S1. Придадим t малое приращение Dt и

определим, что система в момент времени t+Dt находится в состоянии S1.

2. Найдем вероятность того, что система находится в состоянии S2:

3. Найдем вероятность того, что система находится в состоянии S3:

4. Найдем вероятность того, что система находится в состоянии S4:

В результате получаем систему уравнений Колмогорова:

Интегрирование данной системы даст искомые вероятности состояний, как функций времени. Начальные условия берутся в зависимости от того, какого было начальное состояние системы. Если при t=0 система находится в состоянии S1, то начальные условия будут p₁=1, p₂= p₃= p₄=0. Кроме этого, к системе добавляются условия нормировки:

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

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

2. Если стрелка направлена «из» состояния, соответствующий член имеет знак “-“, если «в» состояние, то знак “+”.

3. Каждый член равен произведению плотности вероятности перехода (интенсивность), соответствующий данной стрелке, и вероятности того состояния, из которого выходит стрелка.

Пример.

Рассмотрим многоканальную СМО с отказами. Состояние системы характеризуется по числу занятых каналов, т.е. по числу заявок.

S0 – все каналы свободны

S1 – занят один канал, остальные свободны

Sk – занято k каналов, остальные свободны

Sn – заняты все n каналов.

l

l

l

l

l

m

2m

3m

km

(k+1)m

nm

Разметим граф, т.е. проставим у стрелок интенсивности соответствующих потоков событий. Пусть система находится в состоянии S1. Как только закончится обслуживание заявки, занимающей этот канал, система переходит в состояние S0, интенсивность перехода m. Если занято 2 канала, а не один, то интенсивность перехода составит 2m.

Предельные вероятности состояний p₀и p_n характеризую установившийся режим работы системы массового обслуживания при t®¥.

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

Зная все вероятности состояний p₀, … , p_{n ,} можно найти характеристики СМО:

· вероятность отказа – вероятность того, что все n каналов заняты

· относительная пропускная способность – вероятность того, что заявка будет принята к обслуживанию

· среднее число заявок, обслуженных в единицу времени

Полученные соотношения могут рассматриваться как базисная модель оценки характеристик производительности системы. Входящий в эту модель параметр l = 1 / t_{ОБРАБОТКИ}, является усредненной характеристикой пользователя. Параметр m является функцией технических характеристик компьютера и решаемых задач.

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

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

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

Идея метода: вместо того, чтобы описывать случайное явление с помощью аналитической зависимости производится «розыгрыш», т.е. происходит моделирование случайного явления с помощью некоторой процедуры, дающей случайный результат. Произведя такой розыгрыш n раз, получаем статистический материал, т.е. множество реализаций случайного явления, которое потом можно обработать обычными методами математической статистики. Метод Монте-Карло предложил Фон-Нейман в 1948 году, как метод численного решения некоторых математических задач.