Шпаргалка по "Математическому моделированию"

Тр – время работы системы. S – время, в течение которого обслуживается заявка.

S*Pобсл.АЛУ=m – та доля  времени, в течение которого заявка обслуживается в АЛУ. Тогда:

m – мы нашли ранее.

m=T/(1- π)

p – это в принципе вероятность простоя АЛУ. Т.е. вероятность, что АЛУ работает = 1-р.

S=T/((1- π)(1-p))

Lоч – средняя длина очереди.

Пример: система массового обслуживания.

π2 – вероятность того, что не завершилось обслуживание заявки.

2 режима работы:

1. Блокировки в источнике  (пунктирная линия).

2. С потерей заявки (сплошная линия).

j1t1j2t2…

j1=0..n1

j2=0..n2

j1j2 – состояние очередей

t1=0,1,2 (свободен, занят, заблокирован) – состояние первого канала.

t2=0,1 – состояние второго  канала.

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

целом.

Посмотрим, как будет  выглядеть начало графа:

π1 – вероятность того, что заявка не обслужится.

 

13. Модель «Память-АЛУ». Кодирование состояний. Построение графа состояний.
14. Модель «Память-АЛУ». Построение и решение системы уравнений. Анализ результатов.
15. Системы массового обслуживания (СМО). Марковский случайный процесс. Потоки заявок (событий). Нотация Кендала.

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

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

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

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

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

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

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

Вероятность того, что  величина интервала между событиями  в просеянном потоке окажется равным i тактам: P_i = q^i-1(1 - q) .

Это выражение соответствует геометрическому распределению.

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

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

Это т.н. нормировочное  уравнение.

Таким образом, при t → ∞ в системе устанавливается некоторый предельный стационарный режим, который состоит в том, что система случайным образом меняет свои состояния, но вероятность каждого из них уже не зависит от времени. Эта вероятность представляет собой не что иное, как относительное время пребывания системы в данном состоянии.

При моделировании систем процесс их функционирования удобно представлять в виде графа, вершинами  которого являются состояния S_i, а направленные дуги описывают переходы между состояниями. Если процесс является марковским и известны вероятности переходов из состояния в состояние, то вероятности состояний P_i могут быть найдены исходя из того, что вероятность любого состояния S_i равна сумме произведений вероятностей состояний S_j, из которых есть переход в данное состояние на вероятности этих переходов p_ji , т.е

 

Рассмотрим  на примере эту процедуру (рис 2.3).

Система может  находиться в одном из трех состояний: S₁, S₂ или S₃.

                                  S

Рис. 2.3. Пример графа для  случайного процесса

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

P₁ = p₁₁P₁ + p₃₁P₃ ;

P₂ = p₁₂P₁ + p₃₂P₃ +p₂₂P₂ ;

P₃ = p₁₃P₁ + p₂₃P₂ .

Попытка решить эту систему  непосредственно неизбежно приведет к тождеству. Но, тем не менее, решение существует и может быть получено, если воспользоваться нормировочным уравнением P₁ + P₂ + P₃ = 1.

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

Допустим, вероятности переходов  из состояния в состояние имеют  следующие значения:

p₁₁ =0,25, p₁₂ =0,5, p₁₃ = 0,25, p₂₂ = 0,5, p₂₃ = 0,5, p₃₁ = 0,5, p₃₂ = 0,5.

Тогда решение  системы уравнений дает следующие  результаты: P₁ = 0,2, P₂ = 0,5, P₃ =0,3.

Теперь рассмотрим пример исследования вычислительного  узла (рис. 2.4) с использованием аппарата Марковской дискретной цепи.

Из памяти макрокоманд (МК) по синхросигналу через каждые два такта в арифметико-логическое устройство (АЛУ) считываются макрокоманды. Если АЛУ готово принять макрокоманду, она обрабатывается, иначе макрокоманда загружается в регистровую память (РП) объемом n ячеек (мест ожидания) и ожидает освобождения АЛУ. При полном заполнении РП макрокоманда блокируется в памяти макрокоманд и процесс дальнейшей выборки приостанавливается. Интервалы времени обработки макрокоманд в АЛУ случайны и имеют геометрическое распределение с параметром π, т.е. с вероятностью (1- π) обработка макрокоманды в АЛУ по окончании очередного тактового интервала завершится, а с вероятностью π продлится еще на один интервал.

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

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

Будем определять состояние  системы трехкомпонентным вектором,:

Комбинаторная составляющая этого вектора j - количество заявок , находящихся в накопителе (длина очереди), j = 0,1,2,...n.

Временная составляющая t1 - число тактов, оставшихся до появления заявки на выходе источника (t1=0, 1, 2). Значение 0 означает, что источник заблокирован.

Составляющая t1 определяет состояние канала обслуживания (АЛУ) и может принимать два значения: t2 = 0 - канал свободен; t2 =1 - канал занят обслуживанием заявки.

Построим  граф (рис. 2.6) и систему уравнений  для стационарных (финальных) вероятностей состояний

В состояние Р020 система больше не вернется, поэтому Pq2o = 0

 

Рис. 2.6. Граф переходов  для системы “АЛУ - память”

В состояние P020 система больше не вернется, поэтому Pq2o = 0

Из уравнений 6 и 7 системы определяем вероятности

Уравнение 5 превращается в тождество. Используя уравнение  нормировки

, получим 

Отсюда, учитывая, что сумма -  это сумма геометрической прогрессии, получим

Используя полученное значение p (фактически, это вероятность простоя АЛУ) и рассчитав вероятности всех остальных состояний, можно найти другие интересующие нас характеристики системы.

а) Среднее время обслуживания заявки системой в целом (время пребывания заявки в системе) S.

При прохождении заявки через систему, определенную долю времени она может пребывать заблокированной в источнике, часть времени находиться в очереди и, наконец, некоторое время обслуживаться каналом. Для достаточно большого интервала времени работы системы T_v среднее время, затраченное на пребывание заявок в фазе обслуживания Т =Р_обсл.Т_р, где Робсл. представляет собой сумму вероятностей всех состояний, в которых происходит обслуживание заявки каналом.

Для одной  заявки получаем: SP_обсл = m, где

среднее значение интервала между событиями в  просеянном регулярном потоке с вероятностью просеивания ж и тактовым интервалом Т. Заметим, что единственным состоянием данной системы с отличной от нуля вероятностью, в котором канал не обслуживает заявку, является состояние 010, вероятность которого мы обозначили как р. Следовательно, Робсл = 1-р- Отсюда

б) Интенсивность потока обработанных заявок (абсолютная пропускная способность):

где (1-р) - вероятность того, что канал обрабатывал заявку, (1-я:) -вероятность того, что обработка закончилась.

в) Средняя длина очереди

 

 

16. Простейший  поток, его  свойства  и  значение  при  исследовании СМО.

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

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

2. Поток ординарен,  если вероятность наступления  2х или более событий в течение  элементарного интервала времени  Δt→0. Есть величина бесконечно малая по сравнению с вероятностью наступления одного события. В нем не могут совпасть события.

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

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

Такого рода модели используются с использованием модели систем массового  обслуживания. Системы массового  обслуживания (СМО) – это системы, в которых можно выделить 2 взаимосвязанных роцесса:

Поступление заявок в  систему.

Обслуживание заявок системой.

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

T – интервал времени,  в течение которого происходили  события. Это случайная величина.

ti – интервал между  событиями. Тоже случайная величина.

СМО предполагает наличие 2х потоков:

Входной поток – т.е. множество моментов времени поступления заявок.

Поток обслуживаний –  т.е. множество моментов времени  окончания обработки заявок.

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

Поток называется неоднородным, если он задается последовательностью {ti, fi}, где fi – набор признаков  событий (признаки источников, требования к виду оборудования…).

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

Тип системы массового  обслуживания определяется судьбой  заявок, заставших канал обслуживания занятым:

СМО с очередями.