4. Задача про простій верстатів.

Задача про простій верстатів стосовно до довільного розподілу часу обслуговування детально досліджують у прекрасній монографії: Н.Д. Джейсуол «Очереди с приоритетами» «Мир», М., 1973.

Додержуючись результатів, отриманих у цій монографії, можна записати, що

Де (G(S) - перетворення Лапласа-Стільтьеса функції щільності розподілу часу обслуговування.

Враховуючи те, що при постійному часі обслуговування

Становить інтерес обчислити яким чином впливає вид функції розподілу часу обслуговування на значення величини  -- відносної втрати продуктивності верстатів.

Оскільки вироджений закон розподілу (постійний час обслуговування) характеризується коефіцієнтом варіації =0, а показовий розподіл коефіцієнтом варіації =1, ці два розподіли є ніби то граничними.

Проведені обчислення для n від 1 до 20 при значеннях ( від 0.1 до 1 показали максимальні розходження в результатах в 5-6%. Тому в практиці інженерних розрахунків для будь-якого виду закону розподілу можна використовувати результати й аналітичні вирази, отримані раніше для Марковської моделі відповідної СМО.

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

1. Чи залежать величини граничних ймовірностей станів СМО з відмовами від виду закону розподілу часу обслуговування.

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

3. У яких випадках модель СМО для класичної задачі про простій верстатів з довільним законом розподілу часу обслуговування може бути зведена до харківської моделі.

Рекомендована література

1. Е.С. Вентцель. Исследование операций. «Сов. радио» М., 1972.

2. Кофман А., Крюн Р. Массовое обслуживание. Теория и применение. «Мир», М., 1965р.

3. Джейсуол Н. Очереди с приоритетами. «Мир», М., 1973.

12. Лекція 12

Взаємовідношення часових характеристик СКС та моделей СМО

План лекції

1. Розподіл часу обробки даних у СКС.

2. Характеристики вихідних потоків інформації.

3. Диспетчерські програми операційної системи

1. Розподіл часу обробки даних у СКС

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

Імовірність проходження певного логічного шляху в програмі визначається ймовірністю надходження відповідної інформації й імовірністю певного стану системи. Алгоритми СКС по повноті відомостей про можливий час їхньої реалізації можна розділити на три типи.

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

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

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

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

Зупинимося докладніше на статистичних характеристиках часу реалізації алгоритмів другого типу.

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

або щільність розподілу:

Тут, P(T<t) – імовірність того, що тривалість обслуговування не перевищить деякого t

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

У загальному випадку обслуговування заявок має унімодальний розподіл з більш-менш симетричним розкидом щодо деякого середнього значення. Він в загальному випадку може бути апроксимований розподілом Ерланга:

Де - параметр розподілу

- інтенсивність обслуговування

Г() – гамма-функція

Середній час обслуговування при цьому становить:

а дисперсія й коефіцієнт варіації часу обслуговування заявок відповідно:

Показовий розподіл - окремий випадок розподілу Ерланга при = 1. При — час обслуговування постійний.

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