МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
Звіт до лабораторної роботи №3 “ Дослідження замкнутих стохастичних моделей обчіслювальних систем (ОС)” Мета роботи: вивчити методи розрахунку замкнутих стохастичних мережних моделей ОС, що основані на представлені обчислювального процесу марківським випадковим процесом. Теоретична частина Характерна особливість замкнутих стохастичних мережних моделей ОС на відміну від розімкнутих - наявність в ОС постійного числа активних ОП (рис. 4).
Рис.4. Замкнута стохастична мережна модель ОС. Такими моделями описуються, як правило, ОС, які працюють в інтерактивному (діалоговому) режимі, коли число користувачів фіксоване, і кожен з них не ініціює нового запиту до системи поки не отримає відповіді на попередній запит, а також системи пакетної обробки з фіксованим числом розділів оперативної пам`яті при умові, що кількість завдань в пакеті не зменшується. В цьому випадку кількість заявок, циркулюючих в мережі, визначається коефіцієнтом мультипрограмуванням М. Для однозначного опису параметрів замкнутих і розімкнутих мереж виділимо систему
(див. рис.4) в замкнутій мережі як фіктивне джерело заявок, при чому його інтенсивність
- це інтенсивність заявок, що відповідають завершеним роботам, які проходять по дузі, на якій знаходиться
. Інтенсивність
визначає продуктивність системи. Ця величина не залежить від будь-яких зовнішніх причин, визначається конфігурацією мережі і її параметрами. Замкнуті мережі визначаються тими ж самими параметрами, що і розімкнуті, за винятком параметра
. Замість нього задається коефіцієнт мультипрограмування М, а
визначається на основі розрахунку мережі. На рис. 4 виконано перевизначення систем по відношенню до рис.2; система
(див. рис.2) позначена на рис.4 як
, а система
(див. рис.2) - як
. Відповідно змінюється і матриця ймовірностей передачі.
{28} В замкнутих мережах на відміну від розімкнутих стаціонарний режим завжди існує, так як розміри черг в системах мережі кінцеві і не перевищують по величині М. Різні розподіли М заявок по системах мережі визначають її стан. Стан
, визначає, що в ситемі
перебуває
заявок, в
заявок і т.д. Позначимо множину всіх можливих станів
. Так як для замкнутої мережі
, число різноманітних розподілів М заявок по N системам кінцево і дорівнює числу сполучень
, (29) де
- потужність множини
. Для замкнутої мережі система рівнянь (3), яка визначає інтенсивності
вхідних потоків, має безмежну множину рішень. Однак з неї можна визначити співвідношення інтенсивностей потоків
і
, тобто коефіцієнти передач
, які визначаються розв`язком системи рівнянь (3), в яку підставляються значення
. В цьому випадку корені
системи N-го порядку чисельно визначають значення
. Для визначення ймовірностей станів замкненої мережі використовується той самий підхід, що і для визначення ймовірностей розімкнутої мережі. У випадку замкнутих мереж вводиться додатковий нормуючий множник, який враховує, що сума ймовірностей станів дорівнює одиниці і для будь-яких станів
. Ймовірність станів замкнутої мережі
, (30) де
- ймовірність того , що в стистемі Sj знаходиться Mj заявок;
- символ сумування по всім станам множини A(M,N). Величина
(31) називається нормованою константою. Підставляючи значення
з (10) в (30), отримаємо

. (32) На основі (32) обчислюємо всі необхідні характеристики. Розглянемо алгоритм обчислення величини G(M) для мережі з одноканальними СМО. Введемо допоміжну функцію
, (33) де
, при чому

. (34) Для r>0 i i>0


, (35) де символи
і
- сумування по всіх станах множини A(r,i), для яких
і
>0 відповідно :
;
. (36) Таким чином , рекурентне співвідношення (35) разом з початковими умовами (36) дає правило знаходження нормованої константи (31). Для зручності обчислень використаємо табл.1. Спочатку в першу строку табл.1 заносяться величини
. Потім обчислюються значення
, що утворюють перший стовпчик. Всі інші величини
визначаються сумою величини
, що стоїть зліва в данній стрічці, і величини
, яка стоїть вище в даному стовпчику і помноженому на відповідне даному стовпчику значення
. Кінцевим результатом є величина
. Табл.1 Стрічка Стовпці   1 ... i ... N  0 g(0,1)=1 ... g(0,i)=1 ... g(0,N)=1  1 g(1,1)=t ... g(1,i) ... g(1,N)  ... ... ... ... ... ...   r 
 g(r,i-1) g(r-1,i)ti g(r,i)  ...  ...  ... ... ... ... ... ...  M 
... ... ... g(M,N)   Знайдемо основні характеристики функціонування замкнутої мережі, використовуючи введену функцію g(r,i). Обчислимо ймовірність того, що в системі
перебуває число заявок, більше чи рівне l:

. (37) Тоді маргинальний розподіл
числа заявок в системі
визначачається як різниця між
(38)
Коефіцієнт завантаження системи

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

(40) Інтенсивність вхідного потоку в систему

,
(41) На основі формули Літтла
,
. (42) Звідки середнє число заявок, що очікують в системі

,
(43) Середній час очікування
і перебуття
заявок в системі
відповідно
,
(44)
,
(45) Аналогічні характеристики для мережі в цілому визначаються по формулам (24) - (27). Хід роботи Індивідуальне завдання: кількість систем в мережі – 5, кількість каналів у кожній мережі – 1, кількість файлів –
Імовірності переходів марківскої моделі –
, Середній час обслуговування каналами систем –

Складемо матрицю ймовірностей передач для мережі і знайдемо інтенсивності потоків для кожної системи:



Знайдемо коефіцієнти передачі, які визначають середнє число етапів обслуговування в системі Si в розрахунку на одну заявку, яка поступає від джерела S0 :

Стрічка Стовпці   1 2 3 4 5  0 g(0,1)= 1 g(0,2)=1 g(0,3)= 1 g(0,4)= 1 g(0,5)= 1  1 g(1,1)= 0,7 g(1,2)= 1,225 g(1,3)= 1,7875 g(1,4)= 2,0125 g(1,5)= 2,7625  2 g(2,1)= 0,49 g(2,2)= 1,1331 g(2,3)= 2,1385 g(2,4)= 2,5913 g(2,5)= 4,663  3 g(3,1)= 0,343 g(3,2)= 0,937 g(3,3)= 2,1399 g(3,4)= 2,722 g(3,5)= 6,2191  
–– зававнтаження системи;

Середнє число заявок в систем: Середня довжина черги:

Середній час очікування заявки в черзі Середній час перебування заявки в системі


–– середнє число заявок в мережі;
–– середній час очікування заявки в мережі;
–– середній час перебування заявки в мережі. Тепер перевірим аналітичні розрахунки характеристик мережі із результатами розрахунку програми: Коефіцієнт мультипрограмування M=2 Кількість систем в мережі N=5
Коефіцієнт мультипрограмування M=3 Кількість систем в мережі N=5
Коефіцієнт мультипрограмування M=4 Кількість систем в мережі N=5
Коефіцієнт мультипрограмування M=5 Кількість систем в мережі N=5
Коефіцієнт мультипрограмування M=6 Кількість систем в мережі N=5
Побудуємо графіки залежності величин L , M , W, U в залежності від коефіцієнту мультипрограмування М .

Мал . 1 Мал . 2

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