Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ДОСЛІДЖЕННЯ РОЗІМКНУТИХ СТОХАСТИЧНИХ АНАЛІТИЧНИХ МОДЕЛЕЙ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ (ОС).
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Автоматизовані Системи Управління
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Моделювання систем
Група:
КН-4
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
EMBED Word.Picture.8
Звіт
до лабораторної роботи №1
з дисципліни “Моделювання систем”
ДОСЛІДЖЕННЯ РОЗІМКНУТИХ СТОХАСТИЧНИХ АНАЛІТИЧНИХ МОДЕЛЕЙ
ОБЧИСЛЮВАЛЬНИХ СИСТЕМ (ОС)
Виконав:
студент гр. КН-4
Львів-2008
Мета роботи: вивчити методи розрахунку розімкнутих стохастичних мережних моделей ОС, які ґрунтуються на представленні обчислювального процесу марківським випадковим процесом.
Теоретичні відомості
Можливість інтерпретації роботи ОС стохастичними мережами основана на модульності побудови сучасних обчислювальних засобів, функціональної незалежності модулів і паралельній їх роботі.
Будемо розглядати обчислювальний процес (ОП) як послідовність етапів рахунку і вводу-виводу інформації при звернені до файлів F1,...,Fn, пов’язаних з конкретною реалізацією задачі. Типова діаграма такого процесу показана на рис. 1.
EMBED Word.Picture.8
Рис. 1. Граф марківського ланцюга, що є моделлю обчислювального процесу: P0,i - ймовірності переходів: EMBED Equation.2
Стан ОП, що відповідає етапу рахунку, який позначений символом Е0, а стан, що відповідає зверненню до файлів F1,...,Fn, - символами Е,...,Еn. Закінчення обчислювального процесу розглядається як перехід процесу в стан Еn+1,що поглинає ОП. В цих позначеннях ОП - це послідовність станів Еt0,Et1,...,Etn, що змінюються в моменти часу t0,t2,...,tn, причому Eti{E1,...,En} і заключний стан процесу Etn=En+1.
Властивість марківської моделі ОП заключається в тому, що приймається допущення про відсутність післядії ОП, яка означає, що наступні стани ОП залежать тільки від біжучого його стану і не залежать від попередніх.
EMBED Word.Picture.8
Рис.2. Розімкнута стохастична мережна модель ОС
Відображаючи множину станів ОП на множину модулів ОС (процесори, канали вводу- виводу (КВВ), пристрої вводу-виводу (ПВВ)), з якими пов’язане обслуговування ОП в цих станах, приходимо до наступної мережної моделі ОС (рис.2).Модулі ОС представляються системами масового обслуговування (СМО). Стан Е0 ототожнюється з роботою процесора (ПР), стани Еі EMBED Equation.2 - з роботою ПВВ і КВВ. На рисунку 2 P1,i відповідають P0,i-1 EMBED Equation.2 рис.1.
Передбачається, що файл Fi знаходиться на ПВВ EMBED Equation.2 . Коли декілька файлів знаходяться на одному ПВВ, ймовірність звернення до цього пристрою дорівнює сумі ймовірності звернень до розташованих на ньому файлів. Наприклад, на ПВВ3 розташовані файли F5, F6, F10, з цього випливає, що P1,3=P0,5+P0,6+P0,10.
Зображена на рис.2 стохастична модель ОС представляє собою розімкнуту мережу. Особливість такої моделі заключається в тому, що в ній одночасно можуть існувати змінна кількість активних ОП, конкуруючих за захоплення ресурсів ОС. Процес розв`язку задачі полягає в послідовному обслуговуванні відповідної заявки, що циркулює в мережі СМО. В данних методичних вказівках розглядаються експоненціальні мережі, для яких існують точні аналітичні розв’язки. Для них характерним є експоненціальний розподіл часу обслуговування СМО мережі і найпростіший вхідний потік заявок з інтенсивністю EMBED Equation.2 .
Розімкнута стохастична мережа визначається наступною сукупністю параметрів:
1) числом N СМО S1,..., SN (ПР,ПВВ,КВВ), що утворюють мережу (див. рис.2);
2) числом каналів (пристроїв, що обслуговують) К1,...,КN, що входять в системи S1,..., SN;
3) матрицею ймовірностей передач Р=[Pij], де Pij - ймовірність того, що заявка, яка залишає систему Si, поступить в систему Sj(i,j=0,N);
4) інтенсивністю EMBED Equation.2 джерела заявок 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, має наступний вигляд:
EMBED Equation.3 (1)
Ймовірності Рi,j визначають порядок циркуляції заявок в мережі.
Нехай EMBED Equation.2 - середня кількість звертань від пристрою, що моделюється системою Sі мержі до пристрою, що моделюється системою Sj мережі за час розв`язку однієї задачі. Тоді середня кількість етапів обслуговування заявки в системі Sі мережі при однократному розв`язку задачі
EMBED Equation.2 EMBED Equation.2 . (2)
В цьому випадку EMBED Equation.2 , тобто Pij - це частина заявок, що проходять через систему Sі, які направляються в систему Sj. Якщо всі заявки, які обслуговуються системою Sі поступають в систему Sj, то Pij=1. Якщо система Sі не зв`язана по виходу з системою Sj, то Pij=0.
Для елементів матриці Р повинна виконуватися наступна умова
EMBED Equation.2 ,
так як заявки в мережі не губляться і заявка, що залишає систему Sі, обов`язково попадає в деяку іншу систему.
Будемо розглядати тільки встановлений (стаціонарний) режим. В цьому випадку середнє число заявок, що поступили в систему Sі за деякий проміжок часу, дорівнює середньому числу заявок, що залишили систему за той самий проміжок часу, тобто інтенсивності вхідного і вихідного потоків заявок для системи Si рівні між собою. Для експоненціальних мереж в стаціонарному режимі ймовірність стану визначається добутком ймовірностей станів систем, що складають мережу , при чому ймовірності станів систем визначаються для випадку, коли кожна з систем функціонує незалежно. Таким чином розімкнут Sі у стохастичну мережу, що зображена на рис.2, можна звести до еквівалентної мережі, яка показана на рис.3, де EMBED Equation.2 - сумарна інтенсивність потоку заявок, які поступають в систему Sі від інших систем мережі.
Визначивши послідовно характеристики li,mi,wi,ui систем EMBED Equation.2 мережі, можна знайти аналогічні характеристики l,m,w,u мережі в цілому. Інтенсивності EMBED Equation.2 визначаються з системи рівнянь вигляду
EMBED Equation.2 , (3)
яка випливає з умови встановленого режиму мережі.
V1
S1
EMBED Equation.2
Vn
V2
.
S2
EMBED Equation.2
....
Sn
n
Рис.3. Мережа, що еквівалентна розімкнутій експоненціальній мережі
У векторній формі система рівнянь має такий вигляд
EMBED Equation.2 , (4)
де EMBED Equation.2 -вектор-стовпчик: Р* - транспонована матриця передач Р.
З системи (3) визначається співвідношення інтенсивностей потоків EMBED Equation.2 EMBED Equation.2 i EMBED Equation.2 :
EMBED Equation.2 . (5)
Коефіцієнти EMBED Equation.2 називаються коефіцієнтами передачі і визначають середнє число етапів обслуговування в системі Si в розрахунку на одну заявку, яка поступає від джерела S0, і відповідають раніше введеним величинам ai.
Для розімкнутих стохастичних мереж відома інтенсивність джерела заявок EMBED Equation.2 . Тому система (3) має єдиний розв`язок вигляду (5), де EMBED Equation.2 - фіксована величина.
Умова існування стаціонарного режиму мережі пов`язана з існуванням стаціонарних режимів в її системах. Для системи Si стаціонарний режим існує, якщо завантаження системи EMBED Equation.2 менше одиниці, тобто
EMBED Equation.2 (6)
Для одноканальних СМО під EMBED Equation.2 мається на увазі відносна частина часу, на протязі якого канал використовується, тобто зайнятий обслуговуванням вимог, що поступають, і визначається добутком EMBED Equation.2 . Для багатоканальних СМО величина EMBED Equation.2 визначає середнє число зайнятих каналів ki. Тому для знаходження завантаження кожного з каналів необхідно поділити середнє число зайнятих каналів ki на загальне число каналів в системі Ki. Таким чином, як для одноканальної, так і для багатоканальної системи завантаження
EMBED Equation.2 (7)
Підставляючи (7) в (6) отримаємо
EMBED Equation.2 EMBED Equation.2 EMBED Equation.2 . (8)
Звідки EMBED Equation.2 EMBED Equation.2 . EMBED Equation.2 З цього випливає , що стаціонарний режим буде існувати в розімкнутій мережі, якщо виконується умова
EMBED Equation.2 . (9)
Для багатоканальної СМО в стаціонарному режимі ймовірність того, що в системі EMBED Equation.2 знаходиться EMBED Equation.2 заявок визначається з рівняння
EMBED Equation.2 , (10)
де
EMBED Equation.2 (11)
EMBED Equation.2 (12)
EMBED Equation.2 - ймовірність відсутності заявок в системі Sj визначається з умови нормування:
EMBED Equation.2 ; (13)
EMBED Equation.2 ; (14)
EMBED Equation.2 ; (15)
для одноканальних СМО
EMBED Equation.2 ; (16)
Ймовірність стану мережі знаходимо перемноживши ймовірності станів систем мережі:
EMBED Equation.2 , (17)
або
EMBED Equation.2 . (18)
Знайдемо характеристики lj, mj, wj, uj багатоканальної СМО. Середнє число заявок,що очікують обслуговування в системі, тобто середня довжина черги, визначається як математичне сподівання випадкової величини EMBED Equation.2 EMBED Equation.2 :
EMBED Equation.2
EMBED Equation.2 . (19)
Так як EMBED Equation.2 <1, оскільки розглядається стаціонарний режим,
EMBED Equation.2 EMBED Equation.2 (20)
Середнє число заявок в системі Sj дорівнює сумі середньої довжини черги lj і середнього числа зайнятих каналів EMBED Equation.2 :
EMBED Equation.2 , EMBED Equation.2 (21)
Середній час очікування заявки в черзі згідно формулі Літтла дорівнює частці від ділення середньої довжини черги lj на інтенсивність EMBED Equation.2 , що входить в систему Sj потоку:
EMBED Equation.2 , EMBED Equation.2 (22)
Середній час перебування заявки в системі дорівнює частці від ділення середнього числа заявок mj на інтенсивність EMBED Equation.2 , що входить в систему Sj потоку:
EMBED Equation.2 , EMBED Equation.2 (23)
Використовуючи (20) - (23), визначаємо характеристики мережі в цілому.
Середнє число заявок, що очікують обслуговування в мережі,
EMBED Equation.2 . (24)
Середнє число заявок, що перебувають в мережі,
EMBED Equation.2 . (25)
Кожна заявка поступає на обслуговування в систему Sj мережі в середньому EMBED Equation.2 разів. Тому середній час очікування w (перебування u) заявки в мережі дорівнює сумі взважених по коефіцієнтах передачі EMBED Equation.2 середніх часів очікування wj (перебування uj) заявок в кожній з систем Sj:
EMBED Equation.2 ; (26)
EMBED Equation.2 . (27)
Хід роботи
На основі топології мережі і моделі ОП визначити матрицю ймовірностей передач Р мережі.
Скласти систему рівнянь для знаходження інтенсивностей вхідних потоків EMBED Equation.2 EMBED Equation.2 і розв`язати її. Обчислити коефіцієнти передачі EMBED Equation.2 EMBED Equation.2 .
Перевірити виконання умов стаціонарного режиму розімкнутої мережі.
Визначити характеристики систем мережі EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 і аналогічні характеристики l, m, w, u мережі в цілому.
Встановити зв`язок користувача з ЕОМ.
Запустити програму на виконання з директорії, яку вкаже викладач.
Ввести вхідні дані.
Виконати розрахунки.
Виведені результати розрахунків на екран дисплея, зафіксувати в протоколі звіту.
Побудувати графіки залежностей знайдених характеристик мережі від інтенсивності вхідного потоку EMBED Equation.2 .
Індивідуальне завдання
Варіант 5.1
Модель ОС:
Розв’язок задачі
Граф марковського ланцюга, що є моделлю ОП
EMBED Visio.Drawing.11
Результати роботи програми
Висновки
Під час лабораторної роботи я вивчив методи розрахунку розімкнутих стохастичних мережних моделей ОС, які ґрунтуються на представленні обчислювального процесу марківським випадковим процесом. Як видно з графіків залежності від вхідного потоку, зі збільшенням інтенсивності на крок EMBED Equation.3 збільшуються і характеристики системи в цілому, а саме: середня кількість заявок, що очікують обслуговування в мережі; середня кількість заявок, що перебувають в мережі; середній час очікування заявки в мережі і середній час перебування заявки в мережі. Якщо розглядати детальні графіки для кожної системи EMBED Equation.3 , то середня кількість заявок, що очікують обслуговування в мережі, найбільша в другій і третій системі, а найменша – в четвертій та п’ятій; середня кількість заявок, що перебувають в мережі, найбільша в першій, а найменша – в четвертій та п’ятій; середній час очікування заявки в мережі найбільший в другій та третій, а найменший – в четвертій та п’ятій; середній час перебування заявки в мережі найбільший в першій, а найменший – в четвертій та п’ятій системі.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора