Кількісні показники оцінки ефективності системи

Причини переривання виконання процесу

· виконання процесу завершилося;

· процес запитав виконання операції, що вимагає очікування якого-небудь іншого ресурсу;

· виконання перерване системою.

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

Кількісні показники оцінки ефективності системи

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

Втрачений час: M = T - t;

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

Відношення реактивності: R = t / T;

показує частку процесорного часу (часу виконання) в загальному часі реакції.

Штрафне відношення: P = T / t;

показує, в скільки разів загальний час виконання процесу перевищує необхідний процесорний час.

Середні значення величин T, M, R, P і можуть служити кількісними показниками ефективності. Реальні системи, як правило, орієнтовані на конкретні характеристики процесів, зокрема, на певні діапазони значень t, тому вказані показники зручно розглядати як функції тривалості процесу: T(t), M(t), R(t), P(t).

4. Вимоги до дисциплін планування.

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

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

FCFS

FCFS (first come - first serve - першим прийшов - першим обслуговується) - проста дисципліна, робота якої зрозуміла з її назви. Це дисципліна без витіснення, тобто, процес, вибраний для виконання на ЦП, не уривається, поки не завершиться (або не перейде в стан очікування за власною ініціативою). Як дисципліна без витіснення, FCFS забезпечує мінімум накладних витрат. Середній втрачений час при застосуванні цієї дисципліни не залежить від тривалості процесу, але штрафне відношення при рівному втраченому часі буде великим для коротких процесів. Тому дисципліна FCFS вважається кращою для довгих процесів. Істотною гідністю цієї дисципліни, разом з її простотою, є та обставина, що FCFS гарантує відсутність нескінченного відкладання процесів: будь-який процес, що поступив в систему, врешті-решт буде виконаний незалежно від ступеня завантаження системи.

Процес A поступає у момент часу 0 і вимагає для виконання 6 одиниць процесорного часу. ЦП у цей момент вільний, і процес A відразу ж активізується. У момент часу 2 поступає процес B, що вимагає 11 одиниць. Оскільки ЦП зайнятий процесом A, процес B чекає в черзі готових процесів до моменту 6, коли процес A закінчиться і звільнить ЦП. Тільки після цього процес B починає виконуватися. Поки процес B виконується, поступають ще два процеси: C - у момент часу 8 і D - у момент 10, які чекають завершення процесу B. Коли процес B завершиться, ЦП буде відданий процесу C, що поступив раніше, а процес D залишається в очікуванні. У лінійці, розташованій під тимчасовою шкалою, вказані ідентифікатори процесів, активних в даний момент часу.

RR

RR (round robin - карусель) - проста дисципліна з витісненням. Процес отримує в своє розпорядження ЦП на деякий квант часу Q (у простому випадку розмір кванта фіксований). Якщо за час Q процес не завершився, він витісняється з ЦП і прямує в кінець черги готових процесів, де чекає виділення йому наступного кванта, і так далі Показники ефективності RR істотно залежать від вибору величини кванта Q. RR забезпечує якнайкращі показники, якщо тривалість більшості процесів наближається до розміру кванта, але не перевершує його. Тоді більшість процесів укладаються в один квант і не стають в чергу повторно. При величині кванта, прагнучій до нескінченності, RR вироджується в FCFS. При Q, прагнучому до 0, накладні витрати на перемикання процесів зростають настільки, що поглинають весь ресурс ЦП. RR забезпечує якнайкращі показники справедливості: штрафне відношення P на великій ділянці тривалості процесів t залишається практично постійним. Тільки на ділянці t < Q штрафне відношення починає змінюватися і при зменшенні t від Q до 0 зростає експоненціально. Втрачений же час M істотно росте із збільшенням тривалості процесу.

На малюнку 2.3 показані приклади планування по дисципліні RR з різними величинами кванта Q=1 (рис.2.3.а) і Q=4 (рис.2.3.б). Розглянемо докладніше роботу на початковій тимчасовій ділянці рис.2.3.а. Процес A поступає у момент часу 0 і отримує квант часу ЦП. До моменту закінчення кванта в черзі вже є процес B. Процес A відправляється в чергу, а наступний квант отримує процес B. У момент часу 2 процес B прямує в чергу, а з черги вибирається процес A. У цей же момент поступає новий процес - C. Цей процес ставиться в кінець черги, а першим в черзі коштує процес A, тому наступний квант віддається процесу A і так далі Надаємо читачеві самостійно закінчити розгляд цього прикладу, а також прикладу, показаного на мал. 2.3.б.

SJN

SJN (shortest job next - найкоротша робота - наступна) - невитісняюча дисципліна, в якій найвищий пріоритет має найкоротший процес. Для того, щоб застосовувати цю дисципліну, повинна бути відома тривалість процесу - задаватися користувачем або обчислюватися методом екстраполяції. Для коротких процесів SJN забезпечує кращі показники, чим RR, як по втраченому часу, так і по штрафному відношенню. SJN забезпечує максимальну пропускну спроможність системи - виконання максимального числа процесів в одиницю часу, але показники для довгих процесів значно гірші, а при високому ступені завантаження системи активізація довгих процесів може відкладатися до безкінечності. Штрафне відношення слабо змінюється на основному інтервалі значень t, але значно зростає для найкоротших процесів: такий процес під час вступу до системи має найвищий пріоритет, але вимушений чекати, поки закінчиться поточний активний процес.

Приклад планування по цій дисципліні показаний на малюнку 2.4. Що поступив у момент часу 0 процес A захоплює ЦП. Процес B, що поступив у момент 1, вимушений чекати звільнення ЦП процесом A, хоча процес B і коротший. До моменту 6 - звільнення ЦП - з двох наявних в черзі процесів (B і C) вибирається коротший процес B. Процес C отримує ЦП тільки у момент часу 9, коли закінчується процес B. Коли у момент часу 16 процес C звільняє ЦП, з двох наявних в черзі процесів вибирається коротший процес E, хоча він поступив пізніше, ніж процес D.

PSJN

PSJN (preemptive SJN - SJN з витісненням) - поточний активний процес уривається, якщо його час виконання, що залишився, більший, ніж у новоприбулого процесу. Дисципліна забезпечує ще більшу перевагу коротким процесам перед довгими. Зокрема, в ній усувається те зростання штрафного відношення для найкоротших процесів, яке має місце в SJN.

Розглянемо приклад, представлений на малюнку 2.5. Процес A поступає в систему першим і встигає використовувати одиницю часу ЦП перш, ніж в систему приходить процес B. Процес B вимагає 3 одиниці процесорного часу, а процесу A залишилося використовувати ще 5 одиниць. Процес A витісняється, ЦП віддається процесу B. При звільненні ЦП в черзі вже є і процес C, але його тривалість більша, ніж залишок часу процесу A, тому процес C отримує ЦП тільки у момент часу 9, коли процес A завершиться. Процес C встигає використовувати тільки одну одиницю часу ЦП, коли приходить короткий процес E і витісняє процес C з ЦП. Виконання C знов відкладається до звільнення ЦП, яке відбувається у момент 14. У момент 17 приходить процес D. Його тривалість (6) менша, ніж повна тривалість процесу C (7), але до цього часу процес C вже використав 4 одиниці часу ЦП, і для завершення йому необхідно ще тільки 4 одиниці, тому процес D не витісняє процес C.

HPRN

HPRN (highest penalty ratio next - з найбільшим штрафним відношенням - наступний) - дисципліна без витіснення, що забезпечує якнайкращі показники справедливості. Це досягається за рахунок динамічного перевизначення пріоритетів. Всякий раз при звільненні ЦП для всіх готових процесів обчислюється поточне штрафне відношення:

p[i]=(w[i]+t[i]) / t[i]

де i - номер процесу; w[i] - час, витрачений процесом на очікування; t[i] - тривалість процесу - передзадана або прогнозована.

У прикладі, показаному на малюнку 2.6, під тимчасовою шкалою дані поточні значення штрафного відношення для процесів-претендентів в ті моменти часу, коли виконується перемикання. Так, у момент часу 6 два процеси - B і C - претендують на використання ЦП. Поточне штрафне відношення для процесу B складає: p[B]=(5+3)/3=2.33

а для процесу C: p[C]=(3+7)/7=1.43;

отже, ЦП віддається процесу B. Аналогічні обчислення проводяться в моменти часу 9 і 16.

SRR

SRR (selfish RR - егоїстичний RR) - метод з витісненням, що дає додаткові переваги виконуваним процесам, що дозволяє підвищити пропускну спроможність. Всі процеси розділяються на дві категорії - нові і вибрані. Новими вважаються ті процеси, які не отримали ще жодного кванта часу ЦП, решта всіх процесів - вибрані. Під час вступу до системи кожному процесу дається деякий пріоритет P0, однаковий для всіх процесів, який надалі зростає. В кінці кожного кванта часу перераховуються пріоритети всіх процесів, причому пріоритети нових процесів зростають на величину dA, а вибраних - на величину dB. ЦП віддається процесу з найвищим пріоритетом, а при рівності пріоритетів - тому, який раніше поставлений в чергу. Показники дисципліни істотно залежать від вибраного співвідношення між dA і dB. При dB/dA=1 дисципліна вироджується в звичайну RR, при dB >> dA - в FCFS. Власне дисципліна SRR забезпечується в діапазоні значень 0<dB/dA<1.

Розглянемо роботу дисципліни на прикладі, показаному на малюнку 2.7. Параметри дисципліни в даному прикладі:

P0=0; dA=2; dB=1; Q=1.

Під тимчасовою шкалою тут показані поточні значення пріоритетів процесів. Процес A під час вступу отримує пріоритет 0. Оскільки на цей момент інших процесів немає, процес A починає виконуватися. Отримавши ЦП, процес A потрапляє в категорію вибраних, тому при закінченні кванта у момент 1 пріоритет процесу A зростає на 1. У момент 1 поступає процес B, йому привласнюється початковий пріоритет 0, на даний момент це нижче, ніж пріоритет A, тому ЦП залишається у процесу A. Після ще одного кванта, до моменту часи 2 пріоритет процесу A збільшується ще на 1 і стає рівним 2, але пріоритет процесу B, як нового, збільшується на 2 і стає рівним пріоритету A. За принципом RR ЦП віддається процесу B, як довше чекаючому. Процес B тепер також стає вибраним і надалі його пріоритет росте повільніше. Новий процес C, що поступає пізніше, має нульовий початковий пріоритет і вимушений чекати 3 кванти, поки їх пріоритет не порівняється з пріоритетами вибраних процесів. Аналогічним чином відбувається обслуговування і решти процесів, що поступають.

FB

FB (foreground-background - передний-задний плани) - черга готових процесів розщеплюється на дві підчерги - черга переднього плану і черга заднього плану. Черги обслуговуються по дисципліні RR, але чергу переднього плану має абсолютний пріоритет: поки в ній є процеси, черга заднього плану не обслуговується. Новий процес прямує в чергу переднього плану. Якщо процес використовував встановлене число N квантів в черзі переднього плану, але не завершився, він переводиться в чергу заднього плану.

MLFB

Узагальнення дисципліни FB на n черг з номерами 0, 1..., n-1 і з абсолютними пріоритетами, що убувають при зростанні номера черги, носить назву MLFB (multiply level feed back - багаторівневі черги із зворотним зв'язком). Розщеплювання черги готових процесів на дві і більш за підчергу забезпечує селекцію процесів по тривалості - довші процеси потрапляють в черзі з великими номерами і, відповідно, з меншими пріоритетами. Дисципліна MLFB дуже ефективна для систем, що працюють в інтерактивному режимі.

На малюнку 2.8 показані приклади роботи MLFB для N=1. Під тимчасовою шкалою показані стани процесів в кожен момент часу: "а" - для активного процесу і номер черги - для неактивного. Процес A поступає в чергу 0 і, оскільки ЦП вільний, відразу ж вибирається з неї на виконання. Після використання одного кванта часу ЦП процес A переводиться в чергу 1. У цей момент (момент 1) в чергу 0 поступає процес B. Оскільки черга 0 має вищий пріоритет, ніж черга 1, на виконання вибирається процес B. Процес B після використання кванта (момент 2) потрапляє також в чергу 1. Оскільки у момент часу 2 черга 0 порожня, обслуговується черга 1, з неї вибирається процес A, який був поставлений в цю чергу раніше, ніж процес B. Після цього кванта (момент 3) процес A переходить в чергу 2, а в черзі 0 з'являється новий процес C, якому і буде відданий наступний квант. Після цього кванта (момент 4) процес C буде направлений в чергу 1. На цей момент часу ми маємо 3 процеси: процес A в черзі 2, процес B в черзі 1 і процес C в черзі 1. Обслуговується черга 1, процес B потрапив в цю чергу раніше, він отримує наступний квант і так далі