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

Московський Державний Инженерно;

Фізичний Институт.

(Технічний Университет).

Кафедра «Комп'ютерні системи та технологии».

Реферат на тему:

" Основні поняття теорії ймовірностей, дозволяють поставити часи надходження заявок і часів їх обслуговування. Поняття потоку подій. Типи потоків. Правила використання ймовірнісних характеристик в блоках моделі. Приклади. «.

2002 р Основні поняття теорії ймовірностей, дозволяють поставити часи надходження заявок і часів їх обслуживания.

Кожна система масового обслуговування має певної структурою, яка характеризується сукупністю параметрів. Основним компонентом структури СМО є канали обслуживания.

Залежно від кількості каналів розрізняють одноканальные і многоканальные СМО. Натомість, многоканальные СМО можуть утримувати однакові різні продуктивністю канали обслуживания.

Продуктивність каналу обслуговування обратна тривалості обслуговування заявки, рівної проміжку часу, необхідного каналу обслуговування обслуговування заявки. У випадку це випадкова величина з функцією розподілу F (TAUоб), плотностью.

___ розподілу f (TAUоб) і математичним очікуванням TAUоб. Типи заявок різняться або законами розподілу, або тільки математичними очікуваннями при однакових законах розподілу. У цьому приймається припущення про незалежність длительностей обслуговування щодо різноманітних заявок одного типу, зовсім коректний більшість реальних систем. Поруч із математичним очікуванням тривалості обслуговування використовується понятие.

___ інтенсивності потоку обслуговування MU = 1 / TAUоб — величини, зворотної середньої тривалості обслуговування і що характеризує кількість заявок, що може бути обслужили в одиницю часу постійно загруженным каналом обслуговування. Найбільше число результатів отримано для тривалості обслуговування з експоненційною щільністю распределения.

— MU*TAUоб f (TAUоб) = MU * е Если в останній момент появи заявки на вході СМО хоча б тільки канал вільний до обслуговування, її обслуговування, може бути розпочато негайно, без затримки. Проте спробуємо цілком імовірна ситуація, коли заявка захоплює СМО повністю завантаженою, тобто все m каналів обслуговування зайняті обслуговуванням. І тут початок обслуговування затримується, заявка триватиме місце у відповідної черги. Отже, другим важливий компонент структури СМО є чергу, параметром якої є місць у черзі n. У пріоритетних системах загальна чергу можна розділити сталася на кілька черг за кількістю различаемых системою пріоритетів, кожної у тому числі має бути указано.

___ місць ni, і = 1, N. На місць у черзі то, можливо накладено обмеження, це може бути зроблене як кожної черги, у окремішності, так всієї сукупності черг в цілому. У цьому можливі конфліктні ситуації, розв’язанням яких може бути системи прийняти заявку.

Залежно від кількості місць у черги розрізняють СМО з відмовами, і, СМО без відмов. У СМО з відмовами місць у черзі звісно, і внаслідок вероятностного характеру як вхідного потоку, і процесів обслуговування, існує ненульова можливість, що яка на вхід СМО заявка застане все канали зайнятими обслуговуванням і всі місця у черги зайнятими потребують обслуговування заявками, то є її відмова. У СМО без відмов заявка або відразу призначається обслуговування, тоді як час надходження вільний хоча б тільки канал обслуговування, або безумовно приймається у чергу на обслуживание.

Потоки подій. Типи потоков.

Перехід системи на певну стан Si називається подією. У процесі роботи система неодноразово може повертатися до стану Si. Послідовність таких однорідних подій утворює потік подій Si ", Si ", … .

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

T1 T2 Ti.

—+——+—+—-+—+——-+————-> t.

Потік називається ординарним, якщо у ньому відбуваються поодиночке.

Якщо інтервали є невипадковими, то потік називається регулярним чи детермінованим й цілком характеризується законом зміни довжини інтервалів серед. Інакше потік називається випадковою і характеризується спільним законом розподілу системи випадкових величин (Т1, Т2, …, Тn).

Насправді найчастіше має справу з потоками, у яких інтервали часу між двома соседними.

—— подіями Ti (і = 1, n) — безперервні випадкові величини. Такий випадковий потік характеризується багатовимірної щільністю вероятности f (TAU1, TAU2,…, TAUn), де TAUi — конкретні значення випадкових величин Тi.

Потік називається стаціонарним, якщо його характеристики не змінюються у часі. Можливість влучення тієї чи іншої числа m подій не ділянку осі часу t, t+TAU залежить від TAU та залежною від t. Інтенсивність чи щільність потоку подій, тобто середня кількість подій у одиницю часу, постійна, тобто. LA = const.

У вузькому значенні стационарность означає незалежність щільності ймовірності f (TAU1, TAU2,…, TAUn) від вибору початку отсчета.

Якщо випадкові величини Ti є залежними, потік називається потоком з последействием, бо до будь-якого моменту часу наступне протягом потоку перебуває у вероятностной залежність від предыдущего.

Якщо випадкові величини Ti є незалежними, то випадковий потік називається потоком з обмеженою последействием для нього справедливо: f (TAU1, TAU2,…, TAUn) = f1(TAU1)*f2(TAU2)*…*fn (TAUn).

Випадковий потік подій називається потоком без післядії, для будь-яких непересічних ділянок часу число подій, потрапляють однією їх, залежить від того, скільки подій потрапило інші ділянки. Умова відсутності післядії означає, що події наступають у системі незалежно друг від друга. Для такого потоку справедливо: fi (TAUi) = f (TAUi), i=1,2,…, n.

Потік називається пуассоновским, якщо число m подій потоку, потрапляють на ділянку TAU, розподілено згідно із законом Пуассона ma pm = (a / m!) * e де, а — середня кількість подій, потрапляють на ділянку TAU, однакову для стаціонарного потоку a = LA*TAU.

Визначимо функцію розподілу довжини інтервалу T у стаціонарном пуассоновском потоке.

F (TAU) = P (T < TAU).

Висловимо F (TAU) через ймовірність P (T >= TAU)= F0(TAU) того, що у інтервал TAU не потрапляє жоден з событий:

0 -aa.

F (TAU) = 1 — F0(TAU) = 1 — p0 = 1 — a /0! * e = 1 — e.

Для стаціонарного пуассоновского потоку справедливо:

— LA*TAULA*TAU.

F (TAU) = 1 — e, f (TAU) = LA*e, тобто інтервал часу підпорядкований експонентному (показовому) закону розподілу з параметрами.

M (Ti) = SIGMA (Ti) = ——— .

LA де LA — інтенсивність потоку, характеризує середнє число подій у одиницю времени.

LA = ———- - величина, зворотна середньому времени.

M (Ti) між событиями.

Cтационарный пуассоновский потік є взірцем випадковоГо потоку без післядії. Він інтервал часу від начала відліку до першої події є непрерывную випадкову величину T1, розподілену по экспоненциальному закону з функцією щільності распределения.

— LA*TAU1 f1(TAU1) = LA*e = f (TAU1) = f (TAUi) = f (TAU), що є ознакою відсутності последействия.

Стаціонарний пуассоновский потік подій, у якого властивостями ординарности, стаціонарності й відсутності післядії, називається найпростішим потоком.

Якщо процес переходів у системі відбувається під впливом найпростішого потоку, такий процес є марковским, причому щільність ймовірності переходу у відповідній НМЦ совпвдает з інтенсивністю потоку переходів LA.

Пример.

Двухпроцессорная обчислювальна система варта обробки найпростішого потоку завдань, вступників з інтенсивністю LA. Продуктивність процесоров, відповідно, рівні B1 і B2, причому B1 > B2. Трудомісткість завдань представляє випадкову величину із середнім значенням teta.

Завдання полягає у першу чергу приймається обслуговування процесором, яке має більшу продуктивність. Якщо обидва процесора зайняті, користувач отримує отказ.

Визначити в що встановилася режимі ймовірність відмови Ротк, коефіцієнти завантаження процесорів KSI1, KSI2.

Розглянемо можливі стану системи, які визначаються станами процессоров:

S00 — обидва процесора простаивают;

S10 — перший процесор зайнятий рішенням завдань, другий простаивает;

S01 — другий процесор зайнятий, перший простаивает;

S11 — обидва процесора вирішують задач.

Граф функціонування системи має вид:

+——-+ LA.

MU2 | S00 +——————-+.

+————>| || S11 |t.

±+ ±+ ±+.

Випадкова величина Тк* інтервалу між сусідніми подіями потоку Эрланга К-го порядку представляє суму До незалежних випадкових величин, підлеглих показовому закону розподілу k.

Tk* = SUMMA Ti. Щільність розподілу має вигляд: і = 1 k-1.

LA (LA*TAUk) -LA*TAUk fk (TAUk) = —————————— e.

(K -1)!

Зазвичай випадкову величину Tk* нормують коефіцієнтом До, т. е.

Tk*.

Tkн = ——;

К.

Для нормованого потоку Эрланга К-го порядка.

1 1.

M (Tkн) = ———— D (Tkн) = ———————-;

LA (LA*K)**2.

Отже, при необмеженому збільшенні порядку До нормований потік Эрланга наближається до регулярному потоку с.

1 постійними інтервалами, рівними ———— .

LA.

Нормований потік Эрланга залежно від порядку До дозволяє їм отримати будь-яку ступінь післядії, від повного відсутності (До = 1) до жорсткої статистичної зв’язку (До = нескінченності). Завдяки цьому реальний потік подій з последействием за окремих випадках апроксимувати нормованим потоком Эрланга відповідного порядку, у яких приблизно самі математичне очікування й дисперсию, що знаходить широке застосування під час моделювання довільних потоков.

Правила використання ймовірнісних характеристик в блоках модели.

GENERATE.

————————;

Q-схема Блок-диаграмма Оператор Примечание.

+——-+ +—+ LA | +————+ GENERATE_A, B, C, D, E |ІВ+———> |A, B, З, D, E | +—+ +——-+————+.

V Оператор GENERATE дозволяє описувати вхідний потік, операнды характеризуют властивості вхідного потоку транзактов. Слід пам’ятати, що модельне час у GPSS — ціле без знака 0, 1, 2, … Следовательно, всіх параметрів закону розподілу випадкових інтервалів міжду сусідніми подіями у потоці, мають сенс часу, мали бути зацікавленими з допомогою масштабу часу наведено до цілого формату.

Якщо параметри А, В — const, то оператор GENERATE описує рарнономерный закон розподілу довжини інтервалу між сусідніми событиями в потоке.

1 —- +——————-+ А — середнє (МО) = 1 / LA 2*В | P. S — площа | А >= В.

0 +———+———+.

А-В, А А+В P. S = 2B*h = 1, h = 1 / (2*B).

У — то, можливо різниться від const і тоді й сприймається як модифікатор, у разі довжина інтервалу окреслюється А*В.

З — затримка початку генерации.

D — число генерируемых транзактов (ємність источника).

—————>

Є - пріоритет транзактов. Ціле без знака 0, 1, 2 …

Предположим, що розподіл інтервалів парафій через певний блок GENERATE перестав бути рівномірним. Для входів транзактов в модель через блок GENERATE користувач у разі виконує два дії. 1. Визначає функцію, описує відповідне розподіл інтервалів часу. 2. Як операнда, А блоку GENERATE визначає функцію, а операнд У або визначається за умовчанням, або задається рівним нулю. За необхідності обчислити у процесі моделювання чергове значение інтервалу приходу у Верховну блоці GENERATE інтерпретатор визначає значение операнда, А шляхом обчислення відповідної функції. Це значение далі безпосередньо використовують у якість чергового інтервалу часу. Усі робиться бо коли б користувач визначив рівномірний розподіл у блоці GENERATE багатозначно середнього, рівним значенням функції, і із колосальним розмахом, рівним нулю. При нульовому значении розмаху значення функції використовують як б детермінованим чином, проте, оскільки самі значення функції обчислюються некоторим випадково, значення інтервалів часу також случайны.

Пример.

GENERATE₁₀, 2, 20,, 3 0.25 +———-+.

З | | +———+———-> t —-+—-+—-+—— 0 20 8 10 12.

Момент початку генерації A-B, А A+B.

ПРИМЕЧАНИЕ: Якби операнд З був відсутній, перший транзакт з’явився в час, визначається операндом, А (у нашій прикладі 10).

ADVANCE.

Q-схема Блок-диаграмма Оператор Примечания.

+—-+ | —>| K |—> V ADVANCE A, B затримка на.

+—-+ +———-+ випадкове час Активність, | A, B | із середнім знамає слу- +—-+—-+ чением, А = 1/LA чайну дли- | і рівномірним тельность V распределением Блок ADVANCE затримує просування транзакта на поставлене інтервал модельного времени.

А-Средний інтервал часу. Обов’язковий. Операнд може бути ім'ям, константою, СЧА або СЧА* параметр.

В-половина тимчасового інтервалу або модификатор-функция. Необов’язковий. Операнд може бути порожнім, позитивної константою, СЧА або СЧА* параметр.

Приклад. ADVANCE 100,50.

Цей приклад створює блок, который вибирає службове число між 50 і 150 включно (тобто. 100 плюс-мінус 50) і затримує який увійшов транзакт даний інтервал модельного времени.

Источники: 1. Шрайбер Т. Дж. Моделювання на GPSS. 2. Феррарі Д. Оцінка продуктивності обчислювальних систем. 3. internet 4. internet 5. internet.