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

Размещено на http://allbest.ru

1. НЕПРЕРЫВНО-СТОХАСТИЧЕСКИЕ МОДЕЛИ

К этому классу моделей относятся системы и сети массового обслуживания.

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

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

· потоки поставок продукции некоторому предприятию,

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

· транспортные потоки,

· заявки на обработку информации ЭВМ от удаленных терминалов (информационные потоки),

· обслуживание задач в ВС,

· обслуживание покупателей в магазине.

Акт обслуживания состоит из двух составляющих: ожидание обслуживания заявки и собственно обслуживание заявки. Система массового обслуживания или прибор обслуживания состоит из двух элементов:

1) накопителя, в котором заявки ожидают обслуживания;

2) канала обслуживания, в котором выполняется действие обслуживания заявки.

- Пi - i-я система (прибор) массового обслуживания;

- Нi - накопитель заявок;

- Кi - канал обслуживания;

- Wi - входной поток заявок;

- Ui - поток обслуживании;

- Yi - выходной поток обслуженных заявок;

- Т_{ож. н.} - время ожидания в накопителя;

- Т_{об. к.} - время обслуживания в канале.

ЗАЯВКА - объект, обслуживаемый в приборе (которому выделяются ресурсы (канал)).

В НАКОПИТЕЛЕ заявки ожидают обслуживания. В нем может находиться сразу несколько заявок.

КАНАЛ - объект, выполняющий действие обслуживания. В канале может обслуживаться не более одной заявки.

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

Поток событий называется ОДНОРОДНЫМ, если он характеризуется только моментами поступления этих событий

{t_c}={t₁,t₂,...,t_n...}.

Однородный поток событий также может быть задан в виде последовательности промежутков времени между n-м и (n-1)-м событиями t_n.

Поток событий называется НЕОДНОРОДНЫМ, если он характеризуется не только моментами наступления событий, но и их параметрами, т.е. {t_n, f_n}, где t_n - вызывающие моменты, f_n - набор признаков события.

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

Поток с ОГРАНИЧЕННЫМ ПОСЛЕДЕЙСТВИЕМ - это поток, в котором интервалы между наступлениями событий dt1, dt2, ... , dtn являются случайными независимыми величинами.

Поток называется ОРДИНАРНЫМ, если вероятность Р_ndt того, что на малый интервал времени dt, примыкающий к моменту t, попадает больше одного события (n>1), пренебрежительно мала по сравнению с вероятностью P_1dt того, что на интервал времени dt попадает ровно одно событие

P_1dt >> P_ndt

СТАЦИОНАРНЫЙ поток событий - поток, для которого вероятность появления того или иного числа событий на интервале времени dT зависит лишь от величины этого интервала и не зависит от того, где на оси времени (0,t) взят этот участок.

То есть, если dT1 = dT2, то Р_ndt1 = Р_ndt2.

Поток событий называется потоком БЕЗ ПОСЛЕДЕЙСТВИЯ,если для любых двух непересекающихся интервалов времени dt1 и dt2, число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой.

Поток называется ПРОСТЕЙШИМ (или стационарным пуассоновским), если он является стационарным, ординарным и не имеет последействия одновременно.

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

.

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

.

СМО характеризуется СОСТОЯНИЯМИ Z_i, которое является совокупностью состояний накопителя Z_iH и канала Z_iK:

Z_i = (Z_iH, Z_iK ).

Накопитель может принимать следующие состояния Z_iH:

Z_iH = 0 - накопитель пуст;

Z_iH = 1 - в накопителе одна заявка;

...

Z_iH = N - в накопителе N заявок, накопитель полон, однако это возможно для конечных накопителей. Для бесконечных

Z_iH = .

Канал может принимать следующие состояния Z_iK:

Z_iK = 0 - канал свободен, заявки не обслуживаются;

Z_iK = 1 - канал занят обслуживанием заявки.

стохастический математический информация терминал

2. КОМПОЗИЦИЯ СМО

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

В зависимости от числа каналов и способов их объединения выделяются многоканальные и многофазные сети.

Если каналы К_i различных приборов обслуживания соединены параллельно, то это МНОГОКАНАЛЬНОЕ обслуживание.

Пример. Трехканальное обслуживание:

Рис 1. Трехканальное обслуживание

Если приборы обслуживания П_i и/или их параллельные композиции соединены последовательно, то это МНОГОФАЗНОЕ обслуживание.

Пример. Двухфазное обслуживание:

Рис 2. Двухфазное обслуживание

Сеть СМО характеризуется ОПЕРАТОРОМ СОПРЯЖЕНИЯ R, который задает маршрут прохождения заявок в этой сети. Оператор сопряжения R отражает взаимосвязь элементов структуры между собой.

По способу соединения различают РАЗОМКНУТЫЕ и ЗАМКНУТЫЕ сети.

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

Рис 13. Разомкнутая сеть.

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

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

Рис 14. Замкнутая сеть.

Сеть СМО характеризуются ВНУТРЕННИМИ ПАРАМЕТРАМИ Н, к которым относятся:

1) число фаз в сети L_ф,

2) число каналов в каждой фазе L_kj, j=1, ..., L_ф,

3) число накопителей в каждой фазе L_Hk k=1,..., L_ф,

4) емкость каждого i-го накопителя сети L_Hi.

Таким образом, сеть СМО характеризуется следующей совокупностью внутренних параметров:

H = (L_ф, L_kфi, L_Hфi, L_Hi).

В зависимости от емкостей накопителей различают следующие разновидности СМО:

- с потерями, L_Hi = 0, ожидание невозможно;

- с ожиданием, L_Hi = ;

- смешанные, L_Hi = N, 0<N< .

СМО характеризуются ДИСЦИПЛИНОЙ ОБСЛУЖИВАНИЯ (алгоритмом обслуживания) А.

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

Выделяются следующие виды правил:

· правила поступления (допуска к обслуживанию);

· правила ухода (переполнения накопителя);

· правила выбора маршрута обслуживания;

· правила блокировки.

Выделяют две части дисциплины обслуживания (ДО):

· ДО в накопителе;

· ДО в канале.

Существуют различные дисциплины обслуживания в накопителе:

· дисциплина обслуживания с НЕУПОРЯДОЧЕННОЙ ОЧЕРЕДЬЮ.

· дисциплина обслуживания с УПОРЯДОЧЕННОЙ ОЧЕРЕДЬЮ.

ДО с упорядоченной очередью разделяются на две разновидности:

· БЕСПРИОРИТЕТНЫЕ;

· ПРИОРИТЕТНЫЕ.

Бесприоритетные ДО используются в том случае, когда заявки не отличаются друг от друга, то есть в случае однородного потока заявок.

Существуют две основные бесприоритетные дисциплины обслуживания:

- FIFO (first input, first output - первый пришел, первый вышел (обслужился));

- LIFO (last input, first output - последний пришел, первый вышел (обслужился)).

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

· статические и динамические;

· абсолютные и относительные.

СТАТИЧЕСКИЙ ПРИОРИТЕТ означает, что заявка получает свой приоритет при появлении в системе и не изменяет его до выхода из системы. Приоритет не зависит от состояний СМО.

ДИНАМИЧЕСКИЙ ПРИОРИТЕТ означает, что приоритет заявки изменяется в зависимости от ситуации.

ОТНОСИТЕЛЬНЫЙ ПРИОРИТЕТ (без прерывания обслуживания) означает, что заявка с более высоким приоритетом обслуживания, поступившая в прибор обслуживания П_i, ожидает окончания обслуживания предшествующей заявки каналом K_i и только после этого занимает канал.

АБСОЛЮТНЫЙ ПРИОРИТЕТ (с прерыванием обслуживания) означает, что заявка с более высоким приоритетом, поступившая в прибор П_i, прерывает обслуживание каналом K_i заявки с боле низким приоритетом и сама занимает канал.

При этом вытесненная заявка может либо покинуть систему, либо может снова поступить на какое-то место в накопитель Н_i.

Блокировки отражают наличие управляющих связей в СМО, регулирующих поток заявок от состояний СМО.

Таким образом, Q-схема задается семеркой

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

где z₀ = (z_0H, z_0k) - начальное состояние Q-схемы, включающее начальное состояние накопителей z_0H и начальное состояние каналов z_0k.

2.1 Условные графические обозначения СМО

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

ВЕРШИНЫ.
	- канал обслуживания Кi;
	- источник заявок И (модель внешней среды);
	- бесконечный накопитель Hi Y2i - выходной поток заявок накопителя, поступающих на обслуживание;
	- конечный накопитель Hi с отказом в обслуживании по времени ожидания; Y1i - выходной поток заявок накопителя, получивших отказ в обслуживании, Y2i - выходной поток заявок накопителя, поступающих на обслуживание в канал;
	-конечный накопитель Hi с отказом в обслуживании по размеру очереди, Y1i - выходной поток заявок накопителя, получивших отказ в обслуживании, Y2i - выходной поток заявок накопителя, поступающих на обслуживание в канал;
	-элемент блокировки Вi, указывает на зависимость потока заявок Yi от состояния других элементов СМО;
	- элемент разветвления процесса обслуживания;
ДУГИ.
	-дуга первого типа- отображает маршрут продвижения заявки в СМО;
	-дуга второго типа- отображает функциональную зависимость между элементами (вершинами) СМО.

3. КАЧЕСТВЕННАЯ ЗАВИСИМОСТЬ ХАРАКТЕРИСТИК СИСТЕМЫ ОТ ВНУТРЕННИХ ПАРАМЕТРОВ

3.1 Система массового обслуживания с бесконечным накопителем

Рис. 1. Система массового обслуживания с бесконечным накопителем

На рис.1 приведено графическое изображение одноканальной системы массового обслуживания (СМО), состоящей из канала обслуживания К и бесконечного накопителя Н, причем

N₁ - входной поток заявок, поступающий из источника заявок И,

N₂ - выходной поток заявок.

Время обслуживания заявки в СМО складывается из времени ожидания в накопителе и времени обслуживания в канале, т.е.

_об.с=_ож+_об.к

Очевидно, если интервалы времени поступления заявок больше времен обслуживания в канале (_з.>>_об.к), то заявки не попадают в накопитель Н, время ожидания _ож = 0 и время обслуживания в системе равно времени обслуживания в канале (_об.с=_об.к).

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

При _з.=_об.к для одноканальной системы наступает критический режим работы СМО, поскольку при дальнейшем увеличении входного потока заявок (т.е. при дальнейшем уменьшении _з.) все поступающие заявки не успевают обслуживаться и величина очереди накопителя и время ожидания _ож. становятся бесконечными (при бесконечном времени эксперимента). Поэтому идеальный график зависимости _об.с от _з. будет выглядеть так как показано на рис. 2.

Рис. 2. График зависимости _об.с от _з для СМО с бесконечным накопителем.

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

3.2 Система массового обслуживания с конечным накопителем

Система массового обслуживания (СМО) с конечным накопителем приведена на рис. 3.

Рис. 3. Система массового обслуживания с конечным накопителем

Здесь N₁ - входной поток заявок, поступающий из источника заявок И, N₂ - выходной поток обслуженных заявок, N₃ - выходной поток заявок получивших отказ в обслуживании в связи с конечностью накопителя.

Идеальный график зависимости _об.с от _з. для СМО с конечным накопителем приведена на рис. 4.

Рис. 4. График зависимости _об.с от _з для СМО с конечным накопителем

В области перегрузки СМО, когда _п.з. < _крит., среднее время обслуживания заявки в системе конечно и равно

_об.с= _ож + _об.к = _{макс об.к} + _об.к = (_макс + 1) _об.к ,

где _макс - емкость накопителя.

Время критического режима _крит. для СМО с конечным накопителем определяется также как и для СМО с бесконечным накопителем.

Для многоканальной системы _крит.= _об.с./n , где n - число каналов в многоканальной системе.

3.3 Зависимость времени обслуживания в системе от времени обслуживания в канале

Рис. 5. График зависимости _об.с от _об.к. для СМО с бесконечным (1) и конечным (2) накопителем

4. СТОХАСТИЧЕСКИЕ СЕТИ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СТОХАСТИЧЕСКАЯ СЕТЬ Совокупность взаимосвязанных СМО, в среде которых циркулируют заявки, - это сети массового обслуживания или стохастические сети. Представление ВС в виде стохастической сети обеспечивает более глубокий уровень стратификации системы, чем ВС в виде отдельной СМО.

Рис 15. Разомкнутая (а) и замкнутая (б) стохастические сети С.

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

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

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

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

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

4.2 Модели ВС как системы массового обслуживания

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

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

Рис 16. Многоканальная система массового обслуживания:

О - очередь заявок;

1, 2, ...,m - каналы.

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



Рис 17. Фрагмент ВС.

К процессору с оперативной памятью подсоединены через селекторный канал СК и устройства управления УУ два накопителя на магнитных лентах и три накопителя на магнитных дисках. На устройствах внешней памяти располагаются наборы данных - файлы.

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

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

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



Рис 18. Стохастическая сеть фрагмента ВС

Модель состоит из двух одноканальных СМО S1 и S4, отображающих процессор и селекторный канал соответственно, и двух многоканальных СМО S2 и S3, представляющих внешнюю память на магнитных лентах и дисках соответственно.

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

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

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

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

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

Размещено на Allbest.ru

...