Властивості пуассоновского потоку.

ЗМІСТ

    Передмова......................................................................................5

1.Системи масового обслуговування як об’єкти комп’ютерного моделювання.

1.1 Загальні відомості про системи масового обслуговування…………….6

1.2 Характеристики систем масового обслуговування……………………..7

1.3 Вхідний потік вимог………………………………………………………8

1.4 Властивості пуассоновського потоку…………………………………....9

1.5 Моделювання пуассоновського потоку…………………………………9

1.6 Організація черги…………………………………………………………11

1.7 Вихідний потік вимог…………………………………………………….11

1.8 Режими роботи СМО………………………………………………….....12

1.9 Типи моделей СМО………………………………………………………12

2. Аналіз СМО. Мережі СМО.

2.1. Формула Літтла…………………………………………………………13

2.2. Одноканальні СМО……………………………………………………..15

2.3. Багатоканальні СМО……………………………………………………18

2.4. Основи дискретно-подвійного моделювання СМО………………….18

2.4.1 Простір станів СМО........................................................................19

2.4.2 Алгоритм моделювання СМО……................................................21

2.5. Мережі СМО……………………………………………………………24

2.6. Операційний аналіз мереж СМО……………………………………...26

  2.6.1 Операційні змінні.…………………………………......................26

  2.6.2 Операційні залежності…………………………….......................28

2.7 Аналіз вузьких місць в мережі…………………………………...........31

3. Імітаційне моделювання систем масового обслуговування.

3.1. Формулювання проблеми та змістовна постановка завданн………..35

3.2. Розробка концептуальної моделі………………………………………35

3.3. Вибір ступеня деталізації опису об’єкта моделювання…………...…36

3.4. Опис змінних моделі……………………………………………………37

3.5. Формалізоване зображення концептуальної моделі………………….37

3.6. Вибір засобів реалізації імітаційної моделі…………………………...38

3.7. Розробка структурної схеми імітаційної моделі й опис її функціонування………………………………………………………………39

3.8. Програмна реалізація імітаційної моделі……………………………..39

3.9. Перевірка вірогідності й правильності імітаційних моделей.............40

4. Моделювання обчислювальних та операційних систем

4.1 Загальні відомості про обчислювальні та операційні системи.............43

4.2 Мережі та системи передачі даних..........................................................45

4.3 Проблеми моделювання комп’ютерів і мереж.........................................51

4.4 Імітаційна модель персонального комп’ютера .................................. ....53

Література..........................................................................................61      

Передмова

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

Методи комп’ютерного моделювання широко застосовуються в усіх сферах діяльності людини – від конструювання моделей технічних, технологічних та організаційних систем до вирішення проблем розвитку людства та всесвіту. Класичними об’єктами моделювання є інформаційні, виробничі, транспортні та інші системи, які в більшості випадків застосовуються для розв’язання задач проектування, реконструкції та довгострокового планування, а також використання моделей у контурі керування, тобто в реальному масштабі часу.

Дисципліна “ Моделювання комп’ютерних систем” займає важливе місце серед професійно-орієнтованих дисциплін.

Системи масового обслуговування як об'єкти комп'ютерного моделювання.

Загальні відомості про системи масового обслуговування.

У теорії й практиці моделювання систем важливе місце займають моделі систем масового обслуговування (СМО). Такі системи зустрічаються нам щодня. Це процеси обслуговування в черзі на заправній станції, у магазині, бібліотеці, кафе, а також різні служби ремонту, медична допомога, транспортні системи, аеропорти, вокзали т.п. Черги виникають і тоді, коли є  потреба скористатися телефонним зв'язком або передати повідомлення по Інтернету. Більше того, будь-яке виробництво також можна представити як послідовність СМО. Особливе значення СМО придбали в інформатиці. Це, насамперед, комп'ютерні системи, мережі передачі інформації, бази й банки даних.

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

Перші теоретичні результати дослідження СМО були отримані датським ученим, співробітником Копенгагенської телефонної компанії А.К. Эрлангом у період 1908-1922 рр. Ці результати стосувалися практичних завдань підвищення якості обслуговування абонентів і визначення кількості телефонних ліній. Надалі з'ясувалося, що отримані теоретичні результати є настільки загальними, що їх можна використовувати для визначення максимальної кількості кас і продавців на торговельних підприємствах, для розрахунків запасів у магазинах, достатніх для їхньої безперебійної роботи і т.п. Однак більшість результатів була отримана для систем, у яких процеси надходження й обслуговування заявок є марковскими або напівмарковским. У цьому випадку процеси в СМО можна описати звичайними диференціальними рівняннями й у явному виді  обчислити основні характеристики системи.

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

Характеристики систем масового обслуговування.

Функціонування будь-якої СМО полягає в обслуговуванні потоку вимог, які одне за другим або групами надходять до неї в деякі, як правило, випадкові моменти часу.

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

У кожній системі обслуговування можна виділити:

- пристрої обслуговування (інші назви канали, сервери);

- вимоги (інші назви: заявки, виклики, клієнти), які потребують обслуговування;

-  черги.

Правила або алгоритми взаємодії пристроїв і вимог називають дисциплінами постановки в чергу й обслуговування.

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

Ефективність функціонування будь-який СМО найчастіше визначається такими показниками:

· середня кількість вимог, які система може обслужити в одиницю часу;

· середнє число вимог, які не були обслужені системою;

· імовірність того, що вимога, яка надійшла до системи, буде прийнята на обслуговування;

· середній час очікування вимог у черзі;

· закон розподілу часу очікування;

· середня кількість вимог у черзі;

· закон розподілу числа вимог черги;

· коефіцієнт завантаження пристрою обслуговування;

· середнє число пристроїв, зайнятих обслуговуванням.

Щоб визначити перераховані вище параметри, потрібно описати саму СМО, тобто задати деякі її характеристики. Це, насамперед:

· вхідний потік вимог;

· дисципліни постановки вимог у чергу й вибору вимог із черги;

· правила, за якими виконується обслуговування;

· вихідний потік вимог;

· режими роботи системи.

Вхідний потік вимог.

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

,              (1)

Тут   - інтенсивність потоку вимог (число вимог, які надходять у систему в одиницю часу).

 За допомогою виразу (1) можна визначити ймовірність  надходження  в систему за деякий проміжок часу  рівно  вимог.

Є кілька теорем теорії імовірностей, за допомогою яких можна довести, що більшість потоків вимог є пуассоновськими. На практиці вважається, що вхідний потік буде пуассоновським, якщо за певний проміжок часу вимоги надходять до системи від великої кількості незалежних джерел. Прикладами таких потоків можуть бути дзвінки абонентів у телефонній мережі або запити до централізованої бази даних від користувачів комп'ютерної мережі.

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

Кількість вимог, які надходять у систему від якого-небудь джерела, може бути необмеженим або обмеженим. Прикладом системи з необмеженою кількістю вимог може служити телефонна мережа з великим числом абонентів. Якщо ж обрати систему з відмовами та відновленням (ремонтом) устаткування виробничої дільниці, то в такій системі кількість вимог обмежена й дорівнює числу устаткування виробничої дільниці.

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

Властивості пуассоновского потоку.

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

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

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

Потік уважається ординарним, якщо в один і той же момент часу надходження  двох або більше вимог практично неможливо.

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

Пуассоновський потік вимог є частковим випадком більш загального потоку – потоку Эрланга. Потік Эрланга r -го порядку можна отримати шляхом просівання пуассоновського потоку.