Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ДОСЛІДЖЕННЯ РОЗІМКНУТИХ СТОХАСТИЧНИХ АНАЛІТИЧНИХ МОДЕЛЕЙ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ (ОС
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2008
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Інформаційні технології
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Звіт
до лабораторної роботи №1
з дисципліни “Моделювання систем”
ДОСЛІДЖЕННЯ РОЗІМКНУТИХ СТОХАСТИЧНИХ АНАЛІТИЧНИХ МОДЕЛЕЙ
ОБЧИСЛЮВАЛЬНИХ СИСТЕМ (ОС)
Мета роботи: вивчити методи розрахунку розімкнутих стохастичних мережних моделей ОС, які ґрунтуються на представленні обчислювального процесу марківським випадковим процесом.
Теоретичні відомості
Можливість інтерпретації роботи ОС стохастичними мережами основана на модульності побудови сучасних обчислювальних засобів, функціональної незалежності модулів і паралельній їх роботі.
Будемо розглядати обчислювальний процес (ОП) як послідовність етапів рахунку і вводу-виводу інформації при звернені до файлів 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)
Хід роботи
На основі топології мережі і моделі ОП визначити матрицю ймовірностей передач Р мережі.
Скласти систему рівнянь для знаходження інтенсивностей вхідних потоків і розв`язати її. Обчислити коефіцієнти передачі .
Перевірити виконання умов стаціонарного режиму розімкнутої мережі.
Визначити характеристики систем мережі , , , , , і аналогічні характеристики l, m, w, u мережі в цілому.
Встановити зв`язок користувача з ЕОМ.
Запустити програму на виконання з директорії, яку вкаже викладач.
Ввести вхідні дані.
Виконати розрахунки.
Виведені результати розрахунків на екран дисплея, зафіксувати в протоколі звіту.
Побудувати графіки залежностей знайдених характеристик мережі від інтенсивності вхідного потоку .
Індивідуальне завдання
Варіант 5.1
омер варіанта
Кількість с-м мережі Si
К-сть каналів ki в с-мі мережі Si (i=1..N)
Номер завдання
Кількість файлів
Відображення стану вводу-виводу ОП на системи мережі
Імовірності переходів марківскої моделі ОП
Середній час обслуговування каналами систем мережі
Інтервал зміни і крок приро-щення інтен-сивності вхід-ного потоку (0
1
2
3
4
5
6
7
8
9
V
1
Модель ОС:
Розв’язок задачі
Граф марковського ланцюга, що є моделлю ОП
Результати роботи програми
Висновки
Під час лабораторної роботи я вивчив методи розрахунку розімкнутих стохастичних мережних моделей ОС, які ґрунтуються на представленні обчислювального процесу марківським випадковим процесом. Як видно з графіків залежності від вхідного потоку, зі збільшенням інтенсивності на крок збільшуються і характеристики системи в цілому, а саме: середня кількість заявок, що очікують обслуговування в мережі; середня кількість заявок, що перебувають в мережі; середній час очікування заявки в мережі і середній час перебування заявки в мережі. Якщо розглядати детальні графіки для кожної системи , то середня кількість заявок, що очікують обслуговування в мережі, найбільша в другій і третій системі, а найменша – в четвертій та п’ятій; середня кількість заявок, що перебувають в мережі, найбільша в першій, а найменша – в четвертій та п’ятій; середній час очікування заявки в мережі найбільший в другій та третій, а найменший – в четвертій та п’ятій; середній час перебування заявки в мережі найбільший в першій, а найменший – в четвертій та п’ятій системі.
13.02.2013 14:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора