Лабораторна робота 5
Дослідження розімкнутих стохастичних моделей
обчіслювальних систем (ОС)
Мета роботи - вивчити методи розрахунку розімкнутих стохастичних мережних моделей ОС, основаних на представленні обчислювального процесу марковським випадковим процесом.
Теоретична частина
Можливість інтерпритації роботи ОС стохастичними мережами основана на модульності побудови сучасних обчислювальних засобів, функціональної незалежності модулів і паралельній їх роботі.
Будемо розглядати обчислювальний процес (ОП) як послідовність етапів рахунку і вводу-виводу інформації при звернені до файлів F1,...,Fn, пов’язаних з конкретною реалізацією задачі. Типова діаграма такого процесу показана на рис. 1.

Рис. 1 Граф марківського ланцюга, що є моделлю обчислювального процесу: P0,i - ймовірності переходів:

Стан ОП, що відповідає етапу рахунку, який позначений символом Е0, а стан, що відповідає зверненню до файлів F1,...,Fn, - символами Е,...,Еn. Закінчення обчислювального процесу розглядається як перехід процесу в стан Еn+1,що поглинає ОП. В цих позначеннях ОП - це послідовність станів Еt0,Et1,...,Etn, що змінюються в моменти часу t0,t2,...,tn, причому Eti({E1,...,En} і заключний стан процесу Etn=En+1.
Властивість марківської моделі ОП заключається в тому, що приймається допущення про відсутність післядії ОП, яка означає, що наступні стани ОП залежать тільки від біжучого його стану і не залежать від попередніх.

Рис.2. Розімкнута стохастична мережна модель ОС
Відображая множину станів ОП на множину модулів ОС (процесори, канали вводу- виводу (КВВ), пристрої вводу-виводу (ПВВ)), з якими пов’язане обслуговування ОП в цих станах, приходимо до наступної мережної моделі ОС (рис.2).Модулі ОС представляються системами масового обслуговування (СМО). Стан Е0 ототожнюється з роботою процесора (ПР), стани Еі - з роботою ПВВ і КВВ. На рисунку 2 P1,i відповідають P0,i-1 рис.1.
Передбачається, що файл Fi знаходиться на ПВВ . Коли декілька файлів знаходяться на одному ПВВ, ймовірність звернення до цього пристрою дорівнює сумі ймовірності звернень до розташованих на ньому файлів. Наприклад, на ПВВ3 розташовані файли F5, F6, F10, з цього випливає, що P1,3=P0,5+P0,6+P0,10.
Зображена на рис.2 стохастична модель ОС представляє собою розімкнуту мережу. Особливість такої моделі заключається в тому, що в ній одночасно можуть існувати змінна кількість активних ОП, конкуруючих за захоплення ресурсів ОС. Процес розв`язку задачі полягає в послідовному обслуговуванні відповідної заявки, що циркулює в мережі СМО. В данних методичних вказівках розглядаються експоненціальні мережі, для яких існують точні аналітичні розв’язки. Для них характерним є експоненціальний розподіл часу обслуговування СМО мережі і найпростіший вхідний поток заявок з інтенсивністю .
Розімкнута стохастична мережа визначаєтья наступною сукупністю параметрів:
1) числом N СМО S1,..., SN (ПР,ПВВ,КВВ), що утворюють мережу (див. рис.2);
2) числом каналів (пристроїв, що обслуговують) К1,...,КN, що входять в системи S1,..., SN;
3) матрицею ймовірностей передач Р=[Pij], де Pij - ймовірність того, що заявка, яка залишає систему Si, поступить в систему Sj(i,j=0,N);
4) інтенсивністю джерела заявок S0, що визначає кількість генеруємих задач;
5) середніми тривалостями обслуговування заявок V1,...VN в системах S1,..., SN.
При розрахунку мережі знаходяться ймовірності станів мережі Pr(M1,...,MN), де Мi - кількість заявок в системі Si, а також, що визначаються на їх основі, середні довжини черг заявок l1,...,lN, що очікують обслуговування в системах S1,...,SN, середнє число заявок m1,...,mN, що перебувають в кожній з систем мережі; середній час очікування w1,...,wN і середній час перебування u1,...uN заявок в системах S1,..., SN.
Аналогічні характеристики l,m,w i u мережі в цілому визначаються через одноіменні значення li,mi,wi i ui (i=1,N) . Величини w i u характерезують середній час відповідно очікування і перебування задач в ОС при їх розв’язку.
Матриця ймовірностей передач для мережі, що зображеня на рис.2, має наступний вигляд:

(1)
Ймовірності Рi,j визначають порядок циркуляціїзаявок в мережі.
Нехай - середня кількість звертань від пристрою, що моделюється системою Sі мержі до пристрою, що моделюється системою Sj мережі за час розв`язку однієї задачі. Тоді середня кількість етапів обслуговування заявки в системі Sі мережі при однократному розв`язку задачі
. (2)
В цьому випадку , тобто Pij - це частина заявок, що проходять через систему Sі, які направляються в систему Sj. Якщо всі заявки, які обслуговуються системою Sі поступають в систему Sj, то Pij=1. Якщо система Sі не зв`язана по віходу з системою Sj, то Pij=0.
Для елементів матриці Р повина виконуватися наступна умова
,
так як заявки в мережі не губляться і заявка, що залишає систему Sі, обов`язково попадає в деяку іншу систему.
Будемо розглядати тільки встановлений (стаціонарний) режим. В цьому випадку середнє число заявок, що поступили в систему Sі за деякий проміжок часу, дорівнює середньому числу заявок, що залишили систему за той самий проміжок часу, тобто інтенсивності вхідного і вихідного потоків заявок для системи Si рівні між собою. Для експоненціальних мереж в стаціонарному режимі ймовірність стану визначається добутком ймовірностей станів систем, що складають мережу , при чому ймовірності станів систем визначаються для випадку, коли кожна з систем функціонує незалежно. Таким чином розімкнут Sі у стохастичну мережу, що зображена на рис.2, можна звести до еквівалентної мережі, яка показана на рис.3, де - сумарна інтенсивність потоку заявок, які поступають в систему Sі від інших систем мережі.
Визначивши послідовно характеристики li,mi,wi,ui систем мережі, можна знайти аналогічні характеристики l,m,w,u мережі в цілому. Інтенсивності визначаються з системи рівнянь вигляду
, (3)
яка випливає з умови встановленого режиму мережі.

S1

.
S2


....
Sn
(n
Рис.3 Мережа, що еквівалентна розімкнутій експоненціальній мережі
У векторній формі система рівнянь має такий вигляд
, (4)
де -вектор-стовпчик: Р* - транспонована матриця передач Р.
З системи (3) визначається співвідношення інтенсивностей потоків
i :
. (5)
Коефіцієнти називаються коефіцієнтами передачі і визначають середнє число етапів обслуговування в системі Si в розрахунку на одну заявку, яка поступає від джерела S0, і відповідають раніше введеним величинам ai.
Для розімкнутих стохастичних мереж відома інтенсивність джерела заявок . Тому система (3) має єдиний розв`язок вигляду (5), де - фіксована величина.
Умова існування стаціонарного режиму мережі пов`язана з існуванням стаціонарних режимів в її системах. Для системи Si стаціонарний режим існує, якщо завантаження системи менше одиниці, тобто
(6)
Для одноканальних СМО під мається на увазі відносна частина часу, на протязі якого канал використовується, тобто зайнятий обслуговуванням вимог, що поступають, і визначається добутком . Для багатоканальних СМО величина визначає середнє число зайнятих каналів ki. Тому для знаходження завантаження кожного з каналів необхідно поділити середнє число зайнятих каналів ki на загальне число каналів в системі Ki. Таким чином, як для одноканальної, так і для багатоканальної системи завантаження
(7)
Підставляючи (7) в (6) отримаємо

. (8)
Звідки
.З цього випливає , що стаціонарний режим буде існувати в розімкнутій мережі, якщо
виконується умова
. (9)
Для багатоканальної СМО в стаціонарному режимі ймовірність того, що в системі знаходиться заявок визначається з рівняння
, (10)
де
(11)
(12)
- ймовірність відсутності заявок в системі Sj визначається з умови нормування:
; (13)
; (14)
; (15)
для одноканальних СМО
; (16)
Ймовірність стану мережі знаходимо перемноживши ймовірності станів систем мережі:
, (17)
або
. (18)
Знайдемо характеристики lj, mj, wj, uj багатоканальної СМО. Середнє число заявок,що очікують обслуговування в системі, тобто середня довжина черги, визначається як математичне сподівання випадкової величини
:

. (19)
Так як <1, оскільки розглядається стаціонарний режим,
(20)
Середнє число заявок в системі Sj дорівнює сумі середньої довжини черги lj і середнього числа зайнятих каналів :
, (21)
Середній час очікування заявки в черзі згідно формулі Літтла дорівнює частці від ділення середньої довжини черги lj на інтенсивність , що входить в систему Sj потоку:
, (22)
Середній час перебування заявки в системі дорівнює частці від ділення середнього числа заявок mj на інтенсивність , що входить в систему Sj потоку:
, (23)
Використовуючи (20) - (23), визначаємо характеристики мережі в цілому.
Середнє число заявок, що очікують обслуговування в мережі,
. (24)
Середнє число заявок, що перебувають в мережі,
. (25)
Кожна заявка поступає на обслуговування в систему Sj мережі в середньому разів. Тому середній час очікування w (перебування u) заявкі в мережі дорівнює сумі взважених по коефіцієнтах передачі середніх часів очікування wj (перебування uj) заявок в кожній з систем Sj :
; (26)
. (27)

Порядок проведення роботи.
1. На основі топології мережі і моделі ОП визначити матрицю ймовірностей передач Р мережі.
2. Скласти систему рівнянь для знаходження інтенсивностей вхідних потоків і розв`язати її. Обчислити коефіцієнти передачі .
3. Перевірити виконання умов стаціонарного режиму розімкнутої мережі.
4. Визначити характеристики систем мережі ,, lj,mj,wj,uj і аналогічні характеристики l,m,w,u мережі в цілому.
5. Встановити зв`язок користувача з ЕОМ.
6. Запустити програму на виконання з директорії, яку вкаже викладач.
7. Ввести вхідні дані.
8. Виконати розрахунки.
9. Виведені результати розрахунків на екран дисплея зафіксувати в протоколі звіту.
10. Побудувати графіки залежностей знайдених характеристик мережі від інтенсивності вхідного потоку .
Зміст звіту.
1. Мета лабораторної роботи.
2. Короткі теоретичні відомості.
3. Графова модель ОП і топологічна модель мережі.
4. Аналітичний розрахунок характеристик мережі.
5. Вихідні дані завдання.
6. Результати розрахунку програми.
7. Графіки залежностей характеристик мереж l,m,w,u від інтенсивності вхідного потоку .
8. Висновкі в роботі.