Срс 2. Базові дисципліни планування psjn, hprn, srr, mlfb
PSJN
PSJN (preemptive SJN - SJN з витісненням) - поточний активний процес уривається, якщо його час виконання, що залишився, більший, ніж у новоприбулого процесу. Дисципліна забезпечує ще більшу перевагу коротким процесам перед довгими. Зокрема, в ній усувається те зростання штрафного відношення для найкоротших процесів, яке має місце в SJN.
Розглянемо приклад, представлений на малюнку 2.1. Процес 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.
Рисунок 2.1 – Планування процесів по дисципліні PSPN |
HPRN
HPRN (highest penalty ratio next - з найбільшим штрафним відношенням - наступний) - дисципліна без витіснення, що забезпечує якнайкращі показники справедливості. Це досягається за рахунок динамічного перевизначення пріоритетів. Всякий раз при звільненні ЦП для всіх готових процесів обчислюється поточне штрафне відношення:
p[i]=(w[i]+t[i]) / t[i]
де i - номер процесу; w[i] - час, витрачений процесом на очікування; t[i] - тривалість процесу - передзадана або прогнозована. Для процесу p[i], що тільки що поступив=1. ЦП віддається процесу, що має найбільше значення p[i]. Для коротких процесів HPRN забезпечує приблизно ті ж показники справедливості, що і SJN, для довгих - ближчі до FCFS. На великому діапазоні середньої тривалості процесів показники, забезпечувані HPRN, представляють середнє між SJN і FCFS і слабо залежать від тривалості. Ще одна перевага HPRN - в тому, що в часі очікування може враховуватися (з деякими ваговими коефіцієнтами) і очікування в інших чергах і, таким чином, виконується більш комплексний облік завантаження системи. Істотним недоліком методу є необхідність переобчислення штрафного відношення для всіх процесів при кожному перемиканні, що погано узгоджується із загальною політикою мінімізації накладних витрат в дисциплінах без витіснення.
У прикладі, показаному на малюнку 2.2, під тимчасовою шкалою дані поточні значення штрафного відношення для процесів-претендентів в ті моменти часу, коли виконується перемикання. Так, у момент часу 6 два процеси - B і C - претендують на використання ЦП. Поточне штрафне відношення для процесу B складає:
p[B]=(5+3)/3=2.33
а для процесу C:
p[C]=(3+7)/7=1.43;
отже, ЦП віддається процесу B. Аналогічні обчислення проводяться в моменти часу 9 і 16.
Рисунок 2.2 – Планування процесів по дисципліні HPRN |
SRR
SRR (selfish RR - егоїстичний RR) - метод з витісненням, що дає додаткові переваги виконуваним процесам, що дозволяє підвищити пропускну спроможність. Всі процеси розділяються на дві категорії - нові і вибрані. Новими вважаються ті процеси, які не отримали ще жодного кванта часу ЦП, решта всіх процесів - вибрані. Під час вступу до системи кожному процесу дається деякий пріоритет P0, однаковий для всіх процесів, який надалі зростає. В кінці кожного кванта часу перераховуються пріоритети всіх процесів, причому пріоритети нових процесів зростають на величину dA, а вибраних - на величину dB. ЦП віддається процесу з найвищим пріоритетом, а при рівності пріоритетів - тому, який раніше поставлений в чергу. Показники дисципліни істотно залежать від вибраного співвідношення між dA і dB. При dB/dA=1 дисципліна вироджується в звичайну RR, при dB >> dA - в FCFS. Власне дисципліна SRR забезпечується в діапазоні значень 0<dB/dA<1.
Розглянемо роботу дисципліни на прикладі, показаному на рисунку 2.3. Параметри дисципліни в даному прикладі:
P0=0; dA=2; dB=1; Q=1.
Рисунок 2.3 – Планування процесів по дисципліні SRR |
Під тимчасовою шкалою тут показані поточні значення пріоритетів процесів. Процес A під час вступу отримує пріоритет 0. Оскільки на цей момент інших процесів немає, процес A починає виконуватися. Отримавши ЦП, процес A потрапляє в категорію вибраних, тому при закінченні кванта у момент 1 пріоритет процесу A зростає на 1. У момент 1 поступає процес B, йому привласнюється початковий пріоритет 0, на даний момент це нижче, ніж пріоритет A, тому ЦП залишається у процесу A. Після ще одного кванта, до моменту часу 2 пріоритет процесу A збільшується ще на 1 і стає рівним 2, але пріоритет процесу B, як нового, збільшується на 2 і стає рівним пріоритету A. За принципом RR ЦП віддається процесу B, як довше чекаючому. Процес B тепер також стає вибраним і надалі його пріоритет росте повільніше. Новий процес C, що поступає пізніше, має нульовий початковий пріоритет і вимушений чекати 3 кванти, поки їх пріоритет не порівняється з пріоритетами вибраних процесів. Аналогічним чином відбувається обслуговування і решти процесів, що поступають.
MLFB
FB (foreground-background - передний-задний плани) - черга готових процесів розщеплюється на дві підчерги - черга переднього плану і черга заднього плану. Черги обслуговуються по дисципліні RR, але чергу переднього плану має абсолютний пріоритет: поки в ній є процеси, черга заднього плану не обслуговується. Новий процес прямує в чергу переднього плану. Якщо процес використовував встановлене число N квантів в черзі переднього плану, але не завершився, він переводиться в чергу заднього плану.
Узагальнення дисципліни FB на n черг з номерами 0, 1 ..., n-1 і з абсолютними пріоритетами, що убувають при зростанні номера черги, носить назву MLFB (multiply level feed back - багаторівневі черги із зворотним зв'язком). Розщеплювання черги готових процесів на дві і більш за підчергу забезпечує селекцію процесів по тривалості - довші процеси потрапляють в черзі з великими номерами і, відповідно, з меншими пріоритетами. Дисципліна MLFB дуже ефективна для систем, що працюють в інтерактивному режимі.
На рисунку 2.4 показані приклади роботи 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 потрапив в цю чергу раніше, він отримує наступний квант і так далі.
Рисунок 2.4 – Планування процесів по дисципліні MLFB |
У простому варіанті MLFB черга з великим номером не обслуговується до тих пір, поки є процеси в чергах з меншими номерами. Можливі, проте, численні варіації методу MLFB, наприклад, такі:
разом з переважним обслуговуванням високопріоритетної черги надавати (але з меншою частотою) кванти часу і чергам з низькими пріоритетами;
виконувати зворотне переміщення процесу в чергу з меншим номером після того, як процес прочекав встановлений інтервал часу в низькопріоритетній черзі;
встановити розмір кванта залежним від номера черги, наприклад: Q[n]=q*n або Q[n]=q*2n; оскільки в черзі з великими номерами потрапляють довші процеси, їх обслуговування з великим квантом дозволить заощадити витрати на перемикання;
обслуговувати різні черги по різних дисциплінах (наприклад: RR - для першої черги, FCFS - для другої).