Моделювання складних систем

Моделювання в області системотехніки та системного аналізу. Імітація випадкових величин, використання систем масового обслуговування, дискретних і дискретно-безперервних марковських процесів, імовірнісних автоматів для моделювання складних систем.

Рубрика Программирование, компьютеры и кибернетика
Вид методичка
Язык украинский
Дата добавления 24.04.2011
Размер файла 753,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Знайдемо граничні ймовірності станів даної СМО:

,

.

В сталому режимі система буде обслуговувати 45% заявок:

Pоб = P0 = 0.667/(0.8 + 0.667) = 0.455,

а відмову одержать 55% заявок:

Pвідм = P1 = 1 - Pоб = 0.545.

Інтенсивність вихідного потоку дорівнює

лоб = лPоб = 0.8 * 0.455 = 0.364,

тобто лінія пропускає в середньому 0.364 розмови за хвилину.

лном = м = 0.667 (розмов/хвилину),

що майже в два рази більше лоб.

Висновок: внаслідок неоднорідності потоку подій виникають численні відмови, а телефонна станція фактично використовується набагато менше її номінальної можливості. Телефонну станцію можна оптимізувати шляхом додання додаткових обслуговуючих автоматів або створення невеликої черги заявок.

4.2.2.2 Багатоканальна СМО з відмовами

Для телефонної станції, що була описана у попередньому прикладі, визначимо таку кількість ліній зв'язку, при яких відсоток заявок, які будуть обслуговані, буде не менше 90%. Узагальнена структурна схема такої СМО приведена на рисунку 4.4.

Рисунок 4.4 - Структурна схема багатоканальної СМО

Стан СМО залежить від кількості заявок, які знаходяться в системі:

- у СМО немає жодної заявки;

- у СМО знаходиться одна заявка (один канал зайнятий, інші вільні);

- у СМО знаходиться k заявок (k каналів зайняті, інші вільні);

- у СМО знаходиться n заявок (усі n каналів зайняті).

Рисунок 4.5 - Розмічений граф станів багатоканальної СМО з відмовами

Граф станів СМО на рисунку 4.5 відповідає схемі загибелі та розмноження. З S0 у S1 систему переводить потік заявок з інтенсивністю л. Той же потік заявок переводить систему з будь-якого лівого стану в сусідній правий. Сумарний потік обслуговувань, що дається трьома каналами, має інтенсивність 3м, k каналами - kм.

Припустимо, що кількість ліній зв'язку для нашого прикладу дорівнює 3. Знайдемо зведену інтенсивність потоку заявок, яку будемо використовувати для визначення наступних величин: с = л/м = 1.2. с є зведеною інтенсивністю потоку заявок та характеризує середнє число заявок, що надходить за час обслуговування однієї заявки.

За формулами, отриманими для моделей загибелі та розмноження, обчислимо ймовірності станів. Так, P0 дорівнює:

,

або

,

P0 = [1 + с/1! + с2/2! + с3/3!]-1 = [1 + 1.2 + 0.72 + 0.288 ]-1 = 0.312.

Решта ймовірностей:

, , ..., , ..., ,

або

, , ..., , ..., ,

P1 = P0с/1! = 0.374;

P2 = 0.224;

P3 = 0.09.

Так, граничні ймовірності знайдені. За ними можна обчислити характеристики СМО. Спочатку знайдемо. Для цього потрібно, щоб усі n каналів були зайняті, тоді

,

Pв = P3 = 0.09.

Звідси знаходимо відносну пропускну здатність - імовірність того, що заявка буде обслугована:

,

Pоб = 1 - Pв = 0.91.

Інтенсивність вихідного потоку можна обчислити, помноживши інтенсивність потоку заявок л на Pоб.

.

Середнє число зайнятих каналів :

, або

.

= лPоб/м = с(1 - Pв) = 1.2*0.91 = 1.09 з 3 заданих каналів.

От якою ціною досягається порівняно високий рівень імовірності обслуговування.

4.2.2.3 Одноканальна СМО з обмеженою чергою

Розглянемо найпростішу з усіх можливих СМО з чергою - одноканальну систему (n = 1), до якої надходить потік заявок з інтенсивністю л, інтенсивність обслуговування м. Заявка, що надійшла в момент, коли канал зайнятий, стає в чергу й очікує обслуговування. Припустимо, що кількість місць у черзі обмежена числом m, і якщо заявка надійшла в момент, коли в черзі вже стоять m заявок, вона залишає систему необслугованою.

Приклад: на вхід ОС надходять заявки, утворюючи один найпростіший вхідний потік з інтенсивністю л = 18 с-1. ОС має процесор з середньою швидкодією В = 50*103 оп/с. Обслуговування заявки полягає у виконанні процесором відповідної прикладної програми. Середня трудомісткість прикладних програм приймається приблизно однаковою та дорівнює и = 2.5*103 оп. Від заявки до заявки конкретна трудомісткість змінюється випадково. Для простоти будемо вважати закон її розподілу експоненціальним. Для збереження заявок, які не можуть бути негайно обслуговувані, виділена буферна зона пам'яті з ємністю в чотири комірки, службова інформація про одну заявку займає дві комірки пам'яті. Оцінимо характеристики однопроцесорної ОС із мінімальною ємністю буферної пам'яті.

Параметри даної системи:

л = 18 с-1;

м = В/и = 20 c-1;

m = 2;

с = л/м = 0.9.

Структурна схема СМО приведена на рисунку 4.6.

Рисунок 4.6 - Структурна схема одноканальної СМО з обмеженою чергою

Стани системи нумеруватимемо за кількістю заявок, які знаходяться в СМО ( як тих, що обслуговуються, так і тих, що чекають на обслуговування):

- канал вільний;

- канал зайнятий, черги немає;

-канал зайнятий, одна заявка в черзі;

- канал зайнятий, k-1 заявок стоять у черзі;

- канал зайнятий, m заявок стоять у черзі.

Граф станів СМО показаний на рисунку 4.7.

Рисунок 4.7 - Розмічений граф станів одноканальної СМО з обмеженою чергою

Інтенсивності потоків подій, що переводять систему за стрілками справа наліво, дорівнюють л, а справа наліво - м. Дійсно, за стрілками зліва направо систему переводить вхідний потік заявок (як тільки надійде заявка, система переходить у наступний стан), справа наліво - потік звільнень зайнятого каналу, що має інтенсивність м (як тільки буде обслугована чергова заявка канал звільниться). Зображена на рисунку 4.7 схема являє собою схему загибелі та розмноження. Вирази для обчислення граничних ймовірностей станів мають вигляд:

,

,

,

,

.

Якщо використовувати позначення , тоді формули матимуть вигляд:

,

,

,

,

.

Ймовірність P0 можна обчислити за даною формулою тільки якщо с?1 (с=1 дає неозначеність. В цьому випадку ).

Для нашого прикладу значення ймовірностей будуть

P0 = (1 - 0.9)/(1 - 0.66) = 0.29;

P1 = 0.29*0.9 = 0.26;

P2 = 0.81*0.29 = 0.23;

P3 = 0.73*0.29 = 0.21.

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

Очевидно, що заявка одержує відмову тільки у випадку, коли канал зайнятий та усі m місць у черзі теж зайняті:

,

Pв = P3 = 0.21.

Знаходимо ймовірність обслуговування:

,

Pоб = 1 - Pв = 0.79.

Інтенсивність вихідного потоку:

.

Середня кількість заявок, які знаходяться в черзі, ():

.

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

,

де - середня кількість заявок у черзі, - середня кількість заявок, що обслуговуються. Величина дорівнює:

.

Таким чином, середня кількість заявок, пов'язаних із СМО, буде

.

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

, або

.

тобто середній час очікування дорівнює середньому числу заявок у черзі, поділеному на інтенсивність потоку заявок (формула Літтла). Для нашого прикладу можна зробити висновок, що ті заявки, котрі потрапили у систему, чекають відносно недовго, але 21% усіх заявок отримує відмову.

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

.

4.2.2.4 Багатоканальна СМО з обмеженою чергою

Розглянемо для попереднього прикладу двупроцесорну СМО з розміром буферу (чергою) у 2 елементи:

л = 18 с-1;

м = В/и = 20 c-1;

m = 2;

n = 2.

На рисунку 4.8 приведена узагальнена структурна схема СМО.

Рисунок 4.8 - Структурна схема багатоканальної СМО з обмеженою чергою

Стани системи позначимо за кількістю заявок, що перебувають у системі:

- всі канали вільні;

- один канал зайнятий, решта вільні;

- k каналів зайняті, а решта вільні;

- всі n каналів зайняті;

- усі n каналів зайняті, та одна заявка перебуває в черзі;

- усі n каналів зайняті, та r заявок очікують у черзі;

- усі n каналів зайняті, та всі m місць у черзі зайняті.

Граф станів показаний на рисунку 4.9. У кожної стрілки стоять відповідні інтенсивності потоків подій. Дійсно, за стрілками зліва направо систему переводить завжди однаковий потік заявок з інтенсивністю л; за стрілками зліва направо систему переводить потік обслуговувань, інтенсивність якого дорівнює м, помножену на кількість зайнятих каналів.

Рисунок 4.9 - Розмічений граф станів багатоканальної СМО з обмеженою чергою

Граф на рисунку 4.9. є схемою загибелі та розмноження, розглянутою в попередніх розділах. Позначимо та виразимо граничні ймовірності:

,

,

.

Розрахуємо ймовірності станів для наведеного прикладу:

с = л/м = 0.9;

P0 = 0.39;

P1 = 0.35;

P2 = 0.16;

P3 = 0.07;

P4 = 0.03.

Знайдемо деякі показники ефективності обслуговування. Заявка, що надійшла, одержує відмову в обслуговуванні, якщо зайняті всі n каналів і всі m місць у черзі:

.

Відносна пропускна здатність доповнює ймовірність відмови до одиниці:

.

Абсолютна пропускна здатність СМО дорівнює:

.

Середня кількість зайнятих каналів:

,

або

.

Введемо позначення і визначимо середню кількість заявок у черзі:

Складаючи середню кількість заявок у черзі та середню кількість зайнятих каналів , одержимо середню кількість заявок, які перебувають у системі:

.

Маючи та , за формулою Літтла легко знайти відповідно і

,

.

4.2.2.5 Одноканальна СМО з необмеженою чергою

Розглянемо одноканальну СМО з чергою, на яку не накладені ніякі обмеження (ні за довжиною черги, ні за часом очікування). На дану СМО надходить потік заявок з інтенсивністю л. Потік обслуговування має інтенсивність м. Потрібно знайти граничні ймовірності станів СМО, а також показники її ефективності (за умови, що всі потоки подій є найпростішими). Стани системи, як і раніше, пронумеровані за кількістю заявок, які знаходяться в СМО:

- канал вільний;

- канал зайнятий, але черги немає;

- канал зайнятий, та одна заявка очікує в черзі;

- канал зайнятий, і k - 1 заявок знаходяться у черзі;

- канал зайнятий, та m заявок чекають у черзі.

Теоретично, кількість станів ніяк не обмежена (тобто є нескінченною). Граф станів одноканальної СМО з необмеженою чергою зображений на рисунку 4.10. За всіма стрілками потік заявок з інтенсивністю л переводить систему зліва направо, а справа наліво - потік обслуговувань з інтенсивністю м.

Рисунок 4.10 - Розмічений граф станів одноканальної СМО з необмеженою чергою

Оскільки кількість станів системи нескінченна, та при черга може необмежено зростати, то граничні ймовірності для такої СМО можна обчислити не завжди, а тільки коли система не перевантажена. Якщо , то граничні ймовірності існують, а при черга при необмежено зростає. При СМО порається з потоком заявок лише тоді, коли цей потік є регулярним і час обслуговування дорівнює інтервалу між заявками. У цьому ідеальному випадку у СМО взагалі не буде черги, але канал буде безперервно зайнятий.

Обчислимо граничні ймовірності станів. Для отримаємо вираз:

Ряд у цій формулі являє собою геометричну прогресію. Відомо, що при ряд збігатиметься: це нескінченно спадна геометрична прогресія зі знаменником . При маємо розбіжний ряд.

Припустимо, що . Підсумовуючи прогресію, маємо

.

Імовірності знаходяться за формулами:

Очевидно, що з усіх максимальною є - імовірність того, що канал буде взагалі вільний. Як би не була навантажена система з чергою, якщо вона порається з потоком заявок (тобто ), тоді найімовірніша кількість заявок у системі дорівнюватиме 0.

Щодо абсолютної пропускної здатності () та відносної пропускної здатності (), то обчислювати їх немає потреби, тому що черга є необмеженою, та кожна заявка коли-небудь буде обслугованою, тому з тієї самої причини .

Середня кількість заявок у СМО дорівнює

Застосуємо формулу Літтла та знайдемо середній час перебування заявки в системі:

.

Середня кількість заявок у черзі

.

За формулою Літтла знайдемо середній час перебування заявки в черзі:

Таким чином, усі показники ефективності одноканальної СМО з необмеженою чергою знайдені.

4.3 Завдання для самостійної роботи

1. Залізнична каса має два віконця, у кожному з них продають квитки тільки в один з пунктів: Санкт-Петербург або Київ. Потоки пасажирів, що придбають квитки до Санкт-Петербургу або Києва, однакові по інтенсивності, яка дорівнює . Середній час обслуговування пасажира (продажу йому квитка) . Потоки пасажирів вважати найпростішими. З застосуванням теорії масового обслуговування визначити ефективність цього рішення.

2. Залізнична каса має два віконця, у кожному з яких продають квитки в два пункти: Санкт-Петербург та Київ. Потоки пасажирів, що придбають квитки до Санкт-Петербургу та Києва, однакові по інтенсивності, яка дорівнює . Середній час обслуговування пасажира (продажу йому квитка) . Потоки пасажирів вважати найпростішими. З застосуванням теорії масового обслуговування визначити ефективність цього рішення.

3. Двопроцесорна ОС обслуговує потік заявок з інтенсивністю л = 2 заявки/хв, середній час обслуговування однієї заявки tоб = 2 хв. Число місць у накопичувачі дорівнює 3. Знайти ймовірність відмови в обслуговуванні, середню довжину черги; середню кількість зайнятих процесорів та час очікування заявки в черзі.

4. Однопроцесорна ОС, що працює в режимі пакетної обробки, обслуговує потік заявок з інтенсивністю л = 1 з/хв, tоб = 1.25 хв. Кількість місць у черзі дорівнює 3. Знайти ймовірність відмови в обслуговуванні, середню довжину черги, коефіцієнт використання приладу, середній час очікування заявки в черзі та середній час перебування заявки в системі.

5. Мережний інтерфейс комутатора являє собою СМО з одним каналом обслуговування (один MII, Media Independent Interface). Буфер інтерфейсу може вмістити не більше 3 пакетів одночасно й працює згідно з дисципліною FIFO (m = 3). Якщо в буфері вже перебувають три пакети, наступному пакету, що надійшов на інтерфейс, буде відмовлено у передачі. Потік пакетів, що надходять на інтерфейс, має інтенсивність л = 1 пакетів/мс. Процес передачі триває в середньому 1.25 мс. Визначити ймовірність відмови; відносну й абсолютну пропускні здатності СМО; середню кількість пакетів, які перебувають на інтерфейсі (включаючи також переданий), середній час очікування пакета в буфері, ймовірність обслуговування, середню кількість пакетів, що очікують передачі, та середній час перебування пакета на інтерфейсі (включаючи передачу).

6. Двопроцесорна ОС, що працює в пакетному режимі, обслуговує найпростіший потік заявок з інтенсивністю л, середній час обслуговування одним процесором tоб. Побудувати розмічений граф станів і знайти граничні ймовірності станів, якщо с/n < 1 та m > ?, де n - кількість приладів, m - кількість місць у черзі.

7. У буфер клавіатури надходять повідомлення з кодами натиснутих клавіш із інтенсивністю л = 2 повідомлення в одиницю часу. Середній час обробки одного повідомлення дорівнює 0.4 одиниці часу. Повідомлення, що надходять у момент часу, коли контролер клавіатури повністю зайнятий, чекають у буфері, де є три ділянки пам'яті, кожну з яких може займати лише одне повідомлення. Повідомлення, що надходить у момент часу, коли буфер клавіатури зайнятий, стає в зовнішній буфер. Усі потоки подій найпростіші. Знайти середню кількість повідомлень, що очікують у буфері (як у внутрішньому, так і в зовнішньому); середній час очікування повідомлення в буфері клавіатури та у зовнішньому буфері; середній час обробки повідомлення (включаючи очікування й обслуговування); ймовірність того, що повідомлення, яке прибуло, знайде місце в зовнішньому буфері.

8. Задана ОС з двома ЕОМ. Середня швидкодія процесора B = 104 оп/с. Трудомісткість обробки запитів розподілена за експоненціальним законом з МО и = 5*105 оп. Число користувачів М = 6; час, необхідний користувачу для формування нового запиту та вводу його до системи, розподілений за експоненціальним законом з МО T = 100 с. Дисципліни очікування й обслуговування - безпріоритетні, за порядком надходження заявок.

9. Заявки на доступ до диска надходять за пуассоновим законом із середньою інтенсивністю заявки у хвилину. Якщо диск зайнятий роботою, то нова заявка розміщується у черзі (буферній пам'яті), де чекає обслуговування відповідно до дисципліни FIFO. Коли диск звільняється, починається обслуговування першої заявки з черги. Час обслуговування є експоненційно розподіленою випадковою величиною з математичним очікуванням . Обчислити і для кожного з наступних випадків:

а) НМД містить тільки один тримач магнітних голівок і може обслуговувати в кожен момент часу лише одну заявку;

б) НМД містить багато тримачів магнітних голівок, та кожен тримач може обслуговувати по одній заявці з однією та тією ж інтенсивністю м.

4.4 Контрольні питання

1. Що таке СМО та для чого вона призначена?

2. Які показники ефективності характеризують СМО?

3. Якими параметрами задається СМО?

4. Які види СМО існують?

5. З чого складаються СМО?

6. Що визначають формули Літтла?

7. Як обчислити показники ефективності для одноканальної СМО з відмовами?

8. Як обчислити показники ефективності для багатоканальної СМО з відмовами?

9. Як обчислити показники ефективності для одноканальної СМО з обмеженою чергою?

10. Як обчислити показники ефективності для багатоканальної СМО з обмеженою чергою?

11. Як обчислити показники ефективності для одноканальної СМО з необмеженою чергою?

ПЕРЕЛІК ПОСИЛАНЬ

1. Горбачов В.О. Технології моделювання систем: Навч. посібник. - Харків: СМІТ, 2004

2. Banks J., Discrete-event system simulation. - Prentice-Hall Inc., 1995. - 548 p.

3. Дрім М., Коутський З. Питання отримання випадкових величин за допомогою лічильників. - «Журнал обчислювальної математики та математичної фізики», 1962, т. 2, V-VI, № 3, с. 475

4. Молчанов О.О, Моделювання та проектування складних систем. - К. Вища школа, 1988. - 359 с.

5. Томашевський В.М. Моделювання систем. Київ, Видавницька група BHV, 2005. - 353 с.

6. Совєтов Б.Л., Яковлєв С.О. Моделювання систем: Навч. посібник для ВНЗ за спец. «Автоматизація систем керування». - М.: Вища школа, 1985. - 217 с. ил.

7. Кендел М., Часові ряди /Пер. с англ. та передмова Ю.П. Лукашина, М. «Фінанси і статистика», 1981. - 199 с.

8. Клейнрок Л. Теорія масового обслуговування /Пер. с англ. І.І. Глушко. - М.: Машинобудування, 1979. - 432 с.

9. Lazowska Е., Zahorjan J., Graham G., Sevcik, Quantitative System Performance. Computer System Analysis Using Queuing Network Models. Prentice-Hall Inc., 1984. - 412 p.

Размещено на Allbest.ru


Подобные документы

  • Засоби візуального моделювання об'єктно-орієнтованих інформаційних систем. Принципи прикладного системного аналізу. Принцип ієрархічної побудови моделей складних систем. Основні вимоги до системи. Розробка моделі програмної системи засобами UML.

    курсовая работа [546,6 K], добавлен 28.02.2012

  • Поняття моделювання як процесу, що полягає у відтворенні властивостей тих чи інших предметів і явищ за допомогою абстрактних об’єктів та описів у вигляді зображень, планів, алгоритмів. Системи масового обслуговування. Модель роботи видавничого центру.

    курсовая работа [255,8 K], добавлен 15.09.2014

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

    курсовая работа [194,4 K], добавлен 04.03.2010

  • Роль імітаційного моделювання в дослідженні складних технічних систем. Види оцінки правильності моделі. Створення програми, яка прогнозує рух фізичного маятника з вібруючою точкою підвісу шляхом чисельного інтегрування його диференційного рівняння.

    курсовая работа [758,6 K], добавлен 06.08.2013

  • Основні положення системного аналізу, його використання. Характеристика та основні ознаки складних систем. Використання теорії графів для структурного аналізу. Графова потокова модель технологічного комплексу. Виділення внутрішніх комплексів в ТК.

    курсовая работа [88,3 K], добавлен 01.06.2010

  • Основні поняття моделювання систем, етапи створення, надійність, ефективність. Життєвий цикл та структурне інформаційне забезпечення модельованої системи. Зміст сase-технології, програмне забезпечення та кодування інформації. Головні завдання контролінгу.

    курсовая работа [151,3 K], добавлен 27.05.2014

  • Класифікація інформаційних систем. Дослідження особливостей мови UML як засобу моделювання інформаційних систем. Розробка концептуальної моделі інформаційної системи поліклініки з використанням середи редактора програмування IBM Rational Rose 2003.

    дипломная работа [930,4 K], добавлен 26.10.2012

  • Технології об'єктно-орієнтованого аналізу та проектування інформаційних систем. Історія та структура мови UML. Опис функціональної моделі засобами UML. Використання UML в проектуванні програмного забезпечення. Характеристика CASE-засобів Visual Paradigm.

    дипломная работа [7,9 M], добавлен 26.05.2012

  • Unified modeling language як мова об'єктно-орієнтованого моделювання. Дослідження сучасних сase-засобів моделювання бізнес процесів. Кодогенератор для забезпечення зв'язку між Delphi і Rose. Перелік основних інструментів для створення моделі в ERwin.

    дипломная работа [3,2 M], добавлен 22.10.2012

  • Створення системи експериментального дослідження математичних моделей оптимізації обслуговування складних систем. Визначення критеріїв оптимізації обслуговуваних систем та надання рекомендацій щодо часу проведення попереджувальної профілактики.

    дипломная работа [3,0 M], добавлен 22.10.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.