Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
РОЗРАХУНОК ПАРАМЕТРІВ РОЗІМКНУТИХ СТОХАСТИЧНИХ АНАЛІТИЧНИХ МОДЕЛЕЙ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2012
Тип роботи:
Розрахункова робота
Предмет:
Планування експериментів
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти, науки, молоді і спорту України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
Розрахункова робота
з дисципліни «Планування експериментів»
на тему:
«РОЗРАХУНОК ПАРАМЕТРІВ РОЗІМКНУТИХ СТОХАСТИЧНИХ АНАЛІТИЧНИХ МОДЕЛЕЙ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ»
Мета роботи - вивчити методи розрахунку розімкнутих стохастичних аналітичних моделей обчислювальних систем (ОС), основаних на представленні обчислювального процесу (ОП) марківським випадковим процесом.
ОСНОВНІ ТЕОРЕТИЧНІ ПОЛОЖЕННЯ.
Можливість інтерпретації роботи ОС стохастичними мережами основана на модульності побудови сучасних обчислювальних засобів, функціональної незалежності модулів і паралельній їх роботі.
Будемо розглядати обчислювальний процес (ОП) як послідовність етапів рахунку і вводу-виводу інформації при зверненні до файлів F1,...,Fn, пов’язаних з конкретною реалізацією задачі. Типова діаграма такого процесу показана на рис. 1.
Рис. 1. Граф марківського ланцюга, що є моделлю обчислювального процесу: P0,i - ймовірності переходів:
Стан ОП, що відповідає етапу рахунку, позначений символом Е0, а стан, що відповідає зверненню до файлів F1,...,Fn, - символами Е1,...,Еn. Закінчення обчислювального процесу розглядається як перехід процесу в стан Еn+1. В цих позначеннях ОП - це послідовність станів Е(t0),E(t1),...,E(tk), що змінюються в моменти часу t0,t2,...,tk, причому E(ti)({E1,...,En} і заключний стан процесу E(tk)=En+1.
Властивість марківської моделі ОП полягає в тому, що приймається припущення про відсутність післядії ОП, яка означає, що наступні стани ОП залежать тільки від біжучого його стану і не залежать від попередніх.
Рис.2. Розімкнута стохастична модель ОС.
Відображаючи множину станів ОП на множину модулів ОС (процесори, канали вводу- виводу (КВВ), пристрої вводу-виводу (ПВВ)), з якими пов’язане обслуговування ОП при перебуванні його в цих станах, приходимо до наступної моделі ОС (рис.2). Модулі ОС представляються системами масового обслуговування (СМО). Перебування в стані Е0 ототожнюється з роботою процесора (ПР), а перебування в станах Еі - з роботою ПВВ і КВВ.
Передбачається, що файли 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 ;
4) інтенсивністю джерела заявок S0, що визначає кількість генеруємих задач в одиницю часу;
5) середніми тривалостями обслуговування заявок ν1,...νN в системах S1,..., SN.
При розрахунку мережі знаходяться ймовірності станів мережі Pr(M1,...,MN), де Mi - кількість заявок в системі Si, а також середні довжини черг заявок l1,...,lN, що очікують обслуговування в системах S1,...,SN, середнє число заявок m1,...,mN, що перебувають в кожній з систем мережі; середній час очікування w1,...,wN і середній час перебування u1,...,uN заявок в системах S1,..., SN.
Аналогічні характеристики l, m, w i u мережі в цілому визначаються через відповідні значення li, mi, wi i ui . Величини w i u характерезують середній час відповідно очікування і перебування задач в ОС при їх розв’язку.
Матриця ймовірностей передач для мережі, що зображеня на рис.2, має наступний вигляд:
(1)
Ймовірності Рi,j визначають переходи заявок в мережі.
Нехай - середня кількість звертань від пристрою, що моделюється системою Si, до пристрою, що моделюється системою Sj мережі за час розв`язку однієї задачі. Тоді середня кількість етапів обслуговування заявки в системі Si мережі при однократному розв`язку задачі
, (2)
В цьому випадку , тобто Pij - це частина заявок, що проходять через систему Si, які направляються в систему Sj. Якщо всі заявки, які обслуговуються системою Si поступають в систему Sj, то Pij=1. Якщо система Si не зв`язана по виходу з системою Sj, то Pij=0.
Для елементів матриці Р повинна виконуватися наступна умова
(3)
так як заявки в мережі не губляться і заявка, що залишає систему Si, обов`язково попадає в деяку іншу систему.
Будемо розглядати тільки стаціонарний режим. В цьому випадку середнє число заявок, що поступили в систему Si за деякий проміжок часу, дорівнює середньому числу заявок, що залишили систему за той самий проміжок часу, тобто інтенсивності вхідного і вихідного потоків заявок для системи Si рівні між собою. Для експоненційних мереж ймовірність стану мережі в стаціонарному режимі визначається добутком ймовірностей станів систем, що складають мережу , при чому ймовірності станів систем визначаються для випадку, коли кожна з систем функціонує незалежно. Таким чином розімкнуту стохастичну мережу, що зображена на рис.2, можна звести до еквівалентної мережі, яка показана на рис.3, де - сумарна інтенсивність потоку заявок, які поступають в систему Si від інших систем мережі.
Визначивши послідовно характеристики li, mi, wi, ui систем мережі, можна знайти аналогічні характеристики l, m, w, u мережі в цілому. Інтенсивності визначаються з системи рівнянь вигляду
(4)
яка випливає з умови усталеного режиму мережі.
S1
S2
. . .
Sn
(n
Рис. 3. Мережа, що еквівалентна розімкнутій експоненційній мережі рис.2.
У векторній формі система рівнянь має такий вигляд , (5)
де - вектор-стовпчик: Р* - транспонована матриця передач Р.
З системи (4) визначається співвідношення інтенсивностей потоків i :
. (6)
Коефіцієнти називаються коефіцієнтами передач і визначають середнє число етапів обслуговування системою Si в розрахунку на одну заявку, яка поступає від джерела S0, і відповідають раніше введеним величинам αi.
Для розімкнутих стохастичних мереж відома інтенсивність джерела заявок . Тому система (4) має єдиний розв`язок вигляду (6). Умова існування стаціонарного режиму мережі пов`язана з існуванням стаціонарних режимів в її системах. Для системи Si стаціонарний режим існує, якщо завантаження системи менше одиниці, тобто
(7)
Для одноканальних СМО під розуміється відносна частина часу, на протязі якого канал використовується, тобто зайнятий обслуговуванням вимог, що поступають, і визначається добутком . Для багатоканальних СМО величина визначає середнє число зайнятих каналів ki. Тому для знаходження завантаження кожного з каналів необхідно поділити середнє число зайнятих каналів ki на загальне число каналів в системі Ki. Таким чином, як для одноканальної, так і для багатоканальної системи завантаження
(8)
Підставляючи (8) в (7) отримаємо
. (9)
Звідки .З цього випливає , що стаціонарний режим буде існувати в розімкнутій мережі, якщо виконується умова
. (10)
Для багатоканальної СМО в стаціонарному режимі ймовірність того, що в системі Si знаходиться Mi заявок визначається з рівняння
, (11)
де
(12)
(13)
- ймовірність відсутності заявок в системі Sj і визначається з умови нормування:
; (14)
; (15)
; (16)
для одноканальних СМО ; (17)
Ймовірність стану мережі знаходимо, перемноживши ймовірності станів систем мережі:
, (18)
або
. (19)
Знайдемо характеристики lj, mj, wj, uj багатоканальної СМО. Середнє число заявок, що очікують обслуговування в системі Sj, тобто середня довжина черги, визначається як математичне сподівання випадкової величини :
. (20)
Так як <1, оскільки розглядається стаціонарний режим,
(21)
Середнє число заявок в системі Sj дорівнює сумі середньої довжини черги lj і середнього числа зайнятих каналів :
, (22)
Середній час очікування заявки в черзі згідно формулі Літла дорівнює частці від ділення середньої довжини черги lj на інтенсивність вхідного потоку в систему Sj:
, (23)
Середній час перебування заявки в системі Sj дорівнює частці від ділення середнього числа заявок mj на інтенсивність :
, (24)
Використовуючи (21) - (24), визначаємо характеристики мережі в цілому.
Середнє число заявок, що очікують обслуговування в мережі,
. (25)
Середнє число заявок, що перебувають в мережі,
. (26)
Кожна заявка поступає на обслуговування в систему Sj мережі в середньому разів. Тому середній час очікування w (перебування u) заявкі в мережі дорівнює сумі зважених по коефіцієнтах передачі середніх часів очікування wj (перебування uj) заявок в кожній з систем Sj:
, (27)
. (28)
ПОРЯДОК ВИКОНАННЯ РОБОТИ
Номер варіанту: II – 4
Вхідні дані
Рис.1. Розімкнута стохастична модель ОС.
Рис. 2. Граф марківського ланцюга, що є моделлю обчислювального процесу: P0,i - ймовірності переходів:
Стаціонарний режим буде існувати, якщо виконується умова:
i
1
1/(10*0.5)=0.2
2
1/(2.5*0.4)=1
3
1/(2.5*0.1)=4
4
1/(4*0.3)=0.8333
5
1/(2.5*0.1)=4
6
1/(6.5*0.1)=1.538
Отже, стаціонарний режим існує, оскільки
Обчислимо коефіцієнти завантаженості каналу :
Обчислимо ймовірності відсутності заявок в системі Sj. для багатоканальних систем:
Обчислимо середню довжину черги в системі :
Обчислимо середню кількість заявок в системі
Обчислимо середній час очікування заявки в черзі :
Обчислимо середній час перебування заявки в системі Si
Обчислимо характеристики l, m, w, u для всієї мережі:
= 0.02924398;
= 0.27974398;
= 0.97479946;
=9.32479946.
Висновки: на цій розрахунковій роботі я вивчив методи розрахунку розімкнутих стохастичних аналітичних моделей обчислювальних систем (ОС), основаних на представленні обчислювального процесу (ОП) марківським випадковим процесом.
01.02.2013 03:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора