Непрерывно стохастические модели (Q-схемы)

Непрерывно стохастические модели (Q-схемы)

Особенность непрерывно стохастической модели будем рассматривать на примере систем массового обслуживания (СМО) в качестве типовых математических моделей. При этом используемая система формализуется как некая система обслуживания. Характерным для таких объектов является случайное появление требований (заявок) на обслуживание и завершение обслуживания в случайные моменты времени. Т.е. характер функционирования устройств носит стохастический порядок.

Основные понятия теории массового обслуживания.

В любом элементарном акте обслуживания можно выделить две основные составляющие:

1) Ожидание обслуживания

2) Собственно, обслуживание

Некоторые виды обслуживания некоторого оборудования:

ОА – обслуживающий аппарат

Рекомендуемые материалы

К – канал

Прибор обслуживания (i-ый) состроит из:

• накопителя заявок, в котором может одновременно находится L_i = {0, }, где  – емкость i-ого накопителя
• канала обслуживания заявок.

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

Поток событий называется однородным, если он характеризуется только моментами поступления этих событий (вызывающие моменты) и задается временной последовательностью: ,

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

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

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

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

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

Тогда среднее число сообщений наступивших на участке времени  составит:  - интенсивность  ординарного потока.

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

Поток заявок (), т.е. интервалы времени между моментами появления заявок на входе канала (это подмножество неуправляемых переменных)

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

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

Переход в новое состояние для i-ого прибора означает изменение количества заявок, которые находятся в накопителе или канале:

Где  – состояние накопителя, если он = 0, то накопитель пуст (нет заявок), если количество заявок совпадает с емкостью накопителя, то накопитель полон;  - состояние канала (0 – свободен или 1 - занят).

В практике моделирования элементарные Q-схемы обычно объединяют, при этом, если каналы различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание. А если последовательно – многофазное обслуживание. Таким образом для задания Q-схемы необходимо использовать оператор сопряжения R, отражающий взаимосвязь элементов структуры. Различаются разомкнутые и замкнутые Q-схемы.

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

Замкнутые – есть обратная связь.

Собственными внутренними параметрами Q-схемы будут являться:

• количество фаз
• количество каналов в каждой фазе
• количество накопителей каждой фазы
• ёмкость накопителя.

В зависимости от ёмкости накопителя в теории массового обслуживания применяют следующую терминологию: если емкость равна нулю (т.е. накопитель отсутствует, а есть только канал), то система с потерями. Если ёмкость стремится к бесконечности, то система с ожиданием, т.е. очередь заявок неограниченна.

Система смешанного типа.

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

Весь набор возможных алгоритмов поведения заявок в Q-схеме можно представить в виде оператора:

Q = (W, U, R, H, Z, A)

Где      W - подмножество входных потоков;

U - подмножество потока обслуживания;

R - оператор сопряжения элементов структуры;

H - подмножество собственных параметров;

Z - множество состояний системы;

A - оператор алгоритмов поведения и обслуживания заявок;

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

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

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

/* реально таких систем, конечно, не существует. Но существуют механизмы, которые позволяют свести к этим процессам.*/

Для Марковских процессов обычно составляют уравнения Колмогорова.

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

;

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

Для стационарного соотношения:

,

что дает возможность для стационарной зависимости получить

.

А затем связать выходные характеристики через набор коэффициентов соответствующих системе:

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

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

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

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

Пример: пусть есть некоторая система S, имеющая конечный набор состояний (будем рассматривать для 4 состояний).

Получаем ориентированный граф:

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

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

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

Это может быть реализовано двумя способами:

1. В момент t система S уже была в состоянии  и за время  не вышла из него.
2. В момент t система была в состоянии  и за время  перешла из него в состояние .

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

Аналогично вероятность второго способа равна вероятности того что в следующий момент t была в состоянии умноженную на условную вероятность перехода в состояния, т.е.:

=>  

Мы вывели уравнение Колмогорова для первого состояния.

Выведем далее для 2, 3 и 4 состояний.

Интегрирование данной системы дает искомые вероятности системы как ф-ции времени. Начальные условия берутся в зависимости от того какого было начальное состояние системы. Например, если в момент времени t = 0, система находилась в состоянии, то начальное условие будет .

Кроме того, необходимо добавлять условие нормировки (сумма вероятностей = 1).

Уравнение Колмогорова строится по следующему правилу: в левой части каждого уравнения стоит производная вероятности состояния, а правая часть содержит столько членов сколько стрелок связано с данным состоянием. Если стрелка направлена из состояния, то соответствующий член имеет знак "-", в состояние – "+". Каждый член равен произведению плотности вероятности перехода (интенсивности) соответствующий данной срелке, умноженной на вероятность того состояния, из которого исходит стрелка.

Лабораторная работа №1.

Определить среднее относительное время пребывания системы в предельном стационарном состоянии. Интенсивности переходов из состояния в состояние задаются в виде матрицы размером ≤ 10.

Отчет: название, цель, теоретическая часть и расчеты.

Рассмотрим многоканальную систему массового обслуживания с отказами.

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

Обзовем состояния:

- все каналы свободны

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

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

- заняты все n каналов

Граф состояний:

Разметим граф, т.е. расставим интенсивности соответствующих событий.

По стрелкам с лева на право система переводит один и тот же поток с интенсивностью .

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

Пусть система находится в . Тогда, когда закончится обслуживание заявки занимающей этот канал, система перейдет в  => поток, переводящий систему в другое состояние, будет иметь интенсивность перехода m. Если занято 2 канала, а не один, то интенсивность перехода составит 2m.

Уравнения Колмогорова:

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

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

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

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

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

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

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

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

Обратите внимание на лекцию "Кластерные архитектуры".

Самостоятельно: Метод вложенных цепей Маркова

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

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

Реальные процессы весьма часто обладают последействием и поэтому не являются Марковским. Иногда при исследовании таких процессов удается воспользоваться методами, разработанными для Марковских цепей. Наиболее распространенными являются:

1. Метод разложения случайного процесса на фазы (метод псевдо состояний)

2. Метод вложенных цепей