Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Основні відомості з теорії масового обслуговування.

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

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

Типовими вихідними параметрами в СМО є числові характеристики таких величин, як:

- час обслуговування заявок у системі,

- довжини черг заявок на входах,

- час очікування обслуговування в чергах,

- завантаження пристроїв системи,

- імовірність обслуговування в заданий термін і т.п.

У найпростішому випадку СМО являє собою деякий засіб (пристрій) - обслуговуючий апарат (ОА), разом із чергами заявок на входах. Складніші СМО складаються з багатьох взаємозалежних ОА, які в сукупності утворять статичні об'єкти СМО - ресурси. Наприклад, в обчислювальних мережах ресурси представлені апаратними й програмними засобами.

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

Стан СМО характеризується станами складових її об'єктів. Наприклад, стани ОА виражаються логічними величинами, значення яких інтерпретуються як true (зайняте) і false (вільно), і довжинами черг на входах ОА, що приймають позитивні цілі значення. Змінні, які характеризують стан СМО називають змінними стану або фазовими змінними.

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

У безпріоритетних дисциплінах, всі транзакти мають однакові пріоритети. Серед безпріоритетних дисциплін найбільш популярні дисципліни FIFO (першим прийшов - першим обслужений), LIFO (останнім прийшов - першим обслужений) і з випадковим вибором заявок з черг.

У пріоритетних дисциплінах, для заявок кожного пріоритету на вході ОА виділяється своя черга. Заявка із черги з низьким пріоритетом надходить на обслуговування, якщо порожні черги з вищими пріоритетами. Розрізняють пріоритети абсолютні, відносні й динамічні.

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

Дослідження поводження СМО (визначення часових залежностей змінних, які характеризують стан СМО) при подачі на входи потоків заявок (відповідно до завдання на експеримент), називають імітаційним моделюванням СМО. Імітаційне моделювання проводять шляхом відтворення подій, що відбуваються одночасно або послідовно в часі.

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

Моделі СМО, які використовуються при імітаційному й аналітичному моделюванні, називаються імітаційними й аналітичними відповідно.

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

Тому основним підходом до аналізу САПР на системному рівні проектування вважають імітаційне моделювання, а аналітичне дослідження використають при попередній оцінці різних варіантів систем.

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

Аналітичні моделі СМО.Як відзначено вище, аналітичні моделі СМО вдається одержати при досить серйозних припущеннях. До числа типових припущень відносяться наступні.

- як правило, вважають, що в СМО використаються безпріоритетні дисципліни обслуговування типу FIFO;

- часи обслуговування заявок у пристроях вибираються відповідно до експонентного закону розподілу;

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

У більшості випадків моделі СМО відображають процеси з кінцевою множиною станів і з відсутністю післядії. Такі процеси називають кінцевими марковськими колами.

Марковські кола характеризуються множиною станів S, матрицею ймовірностей переходів з одного стану в інший й початковими умовами (початковим станом). Зручно представляти марковське коло у вигляді графа, в якому вершини відповідають станам кола, дуги - переходам, ваги дуг - імовірностям переходів (для дискретного часу) або інтенсивностям переходів (для неперервного часу).

Інтенсивністю переходу називають величину Vij = lim Pij(t1) / t1 при t1→0, де Pij(t1) — імовірність переходу зі стану Si у стан Sj за час t1. Звичайно приймається умова

де N — число станів. На рис. 3.17 наведений приклад Маяковського кола у вигляді графа зі станами S1,...,S4, а в табл. 3.9 представлена матриця інтенсивностей переходів для цього прикладу.

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

Рівняння Колмогорова можна одержати в такий спосіб.

Зміна ймовірності Pi знаходження системи в стані Si за час t1 є імовірність переходу системи в стан Si з будь-яких інших станів за винятком імовірності переходу зі стану Si в інші стани за час t1, тобто

де Pi(t) і Pj(t) — імовірності знаходження системи в станах Si й Sj відповідно в момент часу t, а Pji(t1) і Pik(t1) — імовірності зміни станів протягом часу t1; добуток виду Pji(t1)Pj(t) є безумовна ймовірність переходу з Sj в Si, рівна умовної ймовірності переходу, помноженої на ймовірність умови; Jі K— множини індексів вершин стосовно вершини Si по вхідних і вихідних дугах на графі станів відповідно.

Розділивши (3.45) на t1 і перейшовши до межі при t→0, одержимо

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

На мал. 3.18 представлений граф станів розглянутої СМО, де Sk — стан з k заявками в системі. Матриця інтенсивностей представлена в табл. 3.10. Рівняння Колмогорова для сталого режиму мають вигляд

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

Вибір мови моделювання визначає структуру моделі й методику її побудови.

Орієнтація на пристрої характерна для функціонально-логічного й детальніших ієрархічних рівнів опису об'єктів.

Для опису імітаційних моделей на системному рівні частіше використають мови, орієнтовані на події або процеси. Прикладами перших можуть служити мови Сімскріпт і SMPL. Прикладами других можуть бути мови Симула, SOL та GPSS.

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

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

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

Пристрої в імітаційній моделі представлені алгоритмами генерації значень інтервалів (тривалості) обслуговування. Найчастіше це алгоритми генерації значень випадкових величин із заданим законом розподілу. Але можуть бути пристрої з детермінованим часом обслуговування або часом, обумовленим подіями в інших частинах моделі.

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

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

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

У процесі моделювання відбуваються зміни модельованого часу, що найчастіше приймається дискретним, вимірюваним у тактах. Час змінюється після того, як закінчена імітація чергової групи подій, які відносяться до моменту часу tk. Імітація супроводжується нагромадженням статистики таких даних, як кількості заявок, що вийшли із системи обслуженими і необслуженими, сумарний час зайнятого стану для кожного із пристроїв, середні довжини черг і т.п. Імітація закінчується, коли поточний час перевищить заданий відрізок часу або коли вхідні джерела вироблять задане число заявок. Після цього роблять обробку накопичених у файлі статистики даних, що дозволяє одержати значення необхідних вихідних параметрів.

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

Розглянемо можливу схему реалізації подієвого методу імітаційного моделювання.

Моделювання починається з перегляду операторів генерування заявок, тобто зі звертання до моделей джерел вхідних потоків. Для кожного незалежного джерела такий обіг дозволяє розрахувати момент генерації першої заявки. Цей момент разом з ім'ям - посиланням на заявку - заноситься в список майбутніх подій (СБС), а відомості про заявку - у список заявок (СЗ).

Запис у СЗ містить у собі ім'я заявки, значення її параметрів (атрибутів), місце, займане в цей момент у моделі. У СБС події впорядковуються по збільшенню моментів настання.

Потім з СБС вибирають сукупність відомостей про події, що ставляться до найбільш раннього моменту часу. Ця сукупність переноситься в список поточних подій (СТС), з якого витягаються посилання на події. Обіг по посиланню до СЗ дозволяє встановити місце в моделі заявки А, з якої зв'язане модельована подія. Нехай цим місцем є пристрій Х. Далі програма моделювання виконує наступні дії (рис. 3.19):

1) змінює параметри стану пристрою Х, наприклад, якщо заявка А звільняє Х, а черга до Х не була порожня, то відповідно до заданої дисципліни обслуговування із черги до Х вибирається заявка В и надходить на обслуговування в Х;

2) прогнозується час настання наступної події, пов'язаного із заявкою В, шляхом звертання до моделі пристрою Х, у якій розраховується тривалість обслуговування заявки В; відомості про цю майбутню подію заносяться в СБС і СЗ;

3) відбувається імітація руху заявки А в моделі по маршруті, обумовленому заданою програмою моделювання, доти, поки заявка не прийде на вхід деякого ОА; тут або заявка затримується в черзі, або шляхом звертання до моделі цього ОА прогнозується настання деякої майбутньої події, пов'язаної з подальшою долею заявки А; відомості про цю майбутню подію також заносяться в СБС і СЗ;

4) у файл статистики додаються необхідні дані.

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

Мережі Петрі— апарат для моделювання динамічних дискретних систем (переважно асинхронних паралельних процесів). Мережа Петрі визначається як четвірка <P,T,I,O>, де Ри M —кінцеві множини позицій і переходів, Iй 0— множини вхідних і вихідних функцій. Інакше кажучи, мережа Петрі являє собою орієнтований граф, у якому позиціямвідповідають вершини, зображувані кружками, а переходам — вершини, зображувані стовщеними рисками; функціям Iвідповідають дуги, спрямовані від позицій до переходів, а функціям ПРО— від переходів до позицій.

Як і у системах масового обслуговування, у мережах Петрі вводяться об'єкти двох типів: динамічні — зображуються мітками (маркерами) усередині позицій і статичні — їм відповідають вершини мережі Петрі.

Розподіл маркерів по позиціях називають маркуванням. Маркери можуть переміщатися в мережі. Кожна зміна маркування називають подією, причому кожна подія пов'язане з певним переходом. Уважається, що події відбуваються миттєво й різночасно при виконанні деяких умов Кожній умові в мережі Петрі відповідає певна позиція. Здійсненню події відповідає спрацьовування (порушення або запуск) переходу, при якому маркери із вхідних позицій цього переходу переміщаються у вихідні позиції. Послідовність подій утворить моделируемый процес.

Правила спрацьовування переходів (рис. 3.21), конкретизують у такий спосіб: перехід спрацьовує, якщо для кожної з його вхідних позицій виконується умова Ni Ki, де Ni — число маркерів в i-й вхідній позиції, Ki — число дуг, що йдуть від i-й позиції до переходу; при спрацьовуванні переходу число маркерів в i-й вхідної позиції зменшується на Ki, а в j-й вихідної позиції збільшується на Mj, де Mj — число дуг, єднальний перехід з j-й позицією.

На рис. 3.21 показаний приклад розподілу маркерів по позиціях перед спрацьовуванням, це маркування записують у вигляді (2,2,3,1). Після спрацьовування переходу маркування стає іншою:

(1,0,1,4).

Можна вводити ряд додаткових правил й умов в алгоритми моделювання, одержуючи той або інший різновид мереж Петрі. Так, насамперед корисно ввести модельний час, щоб моделювати не тільки послідовність подій, але і їхню часову прив'язку. Це здійснюється доданням переходам ваги - тривалості (затримки) спрацьовування, яку можна визначати, використовуючи алгоритм, що задає при цьому. Отриману модель називають часовою мережею Петрі.

Якщо затримки є випадковими величинами, то мережу називають стохастичною. У стохастичних мережах можливе введення ймовірностей спрацьовування збуджених переходів. Так, на рис. 3.22 представлений фрагмент мережі Петрі, що ілюструє конфліктну ситуацію — маркер у позиції p може запустити або перехід t1, або перехід t2. У стохастичній мережі передбачається імовірнісний вибір переходу, що спрацьовує, у таких ситуаціях.

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

У багатьох задачах динамічні об'єкти можуть бути декількох типів, і для кожного типу потрібно вводити свої алгоритми поводження в мережі. У цьому випадку кожен маркер повинен мати хоча б один параметр, що позначає тип маркера. Такий параметр звичайно називають кольорами; кольори можна використати як аргумент у функціональних мережах. Мережа Петрі при цьому називають кольоровий.

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

Введені поняття пояснимо на наступному прикладі.

Приклад.Потрібно описати за допомогою мережі Петрі роботу групи користувачів на єдиній робочій станції WS при заданих характеристиках потоку запитів на користування WS і характеристиках вступників задач.

Мережа Петрі представлена на мал. 3.23.

Тут переходи зв'язані з наступними подіями: t1 — надходження запиту на використання WS, t2 — заняття станції, t3 — звільнення станції, t4 — вихід обслуженої заявки; позиція "4 використається для відображення стану WS: якщо в "4 є мітка, то WS вільна й заявка, що прийшла, викликає спрацьовування переходу t2; поки ця заявка не буде обслужена, мітки в "4 не буде, отже, що прийшли у позицію "1 запити змушені очікувати спрацьовування переходу t3.

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

Можливий й інший підхід до використання мереж Петрі для аналізу об'єктів, досліджуваних на системному рівні. Він не пов'язаний з імітацією процесів і заснований на дослідженні таких властивостей мереж Петрі, як обмеженість, безпека, сохраняемость, досяжність, жвавість.

Обмеженість (або До-обмеженість) має місце, якщо число міток у будь-якій позиції мережі не може перевищити значення К. При проектуванні автоматизованих систем визначення Додозволяє обґрунтовано вибирати ємності накопичувачів. Можливість необмеженого росту числа міток свідчить про небезпеці необмеженого росту довжин черг.

Безпека — окремий випадок обмеженості, а саме це 1-обмеженість. Якщо для деякої позиції встановлено, що вона безпечна, то її можна представляти одним тригером.

Сохраняемость характеризується сталістю завантаження ресурсів, тобто

де Ni-число маркерів в i-й позиції, Ai — вагарні коефіцієнт.

Досяжність Mk → Mj характеризується можливістю досягнення маркування Mj зі стану мережі, характеризуемого маркуванням Mk.

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

В основі дослідження перерахованих властивостей мереж Петрі лежить аналіз досяжності.

Один з методів аналізу досяжності будь-якого маркування зі стану Eо — побудова графа досяжності. Початкова вершина графа відображає Eо, а інші вершини відповідають маркуванням. Дуга з Ei в Ej означає подію Mi → Mj і відповідає спрацьовуванню переходу t.

У складних мережах граф може містити надмірно велика кількість вершин і дуг. Однак при побудові графа можна не відображати всі вершини, тому що багато хто з них є дублями (дійсно, від маркування Mk завжди породжується той самий подграф поза залежністю від того. з якого стану система прийшла в Ek). Тупики виявляються по відсутності дозволених переходів з якої-небудь вершини, тобто по наявності листів - термінальних вершин. Необмежений ріст числа маркерів у якій-небудь позиції свідчить про порушення обмеженості.

Приведем приклади аналізу досяжності.

Приклад 1.Мережа Петрі й граф досяжних розміток представлені на мал. 3.25.

На малюнку вершини графа зображені у вигляді маркувань, дуги позначені переходами, що спрацьовують. Жвавість мережі очевидна, тому що спрацьовують всі переходи, тупики відсутні.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
	\|	Інтерфейс системи

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.012 сек.