Багаторівневі черги зі зворотним зв'язком

(MultilevelFeedback Queue Scheduling).

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

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

Для простоти розглянемо ситуацію, коли процеси в змозі готовність організовані в 4 черги, як на малюнку 3.6. Планування процесів між чергами здійснюється на основі витісняючого пріоритетного механізму. Чим вище на малюнку розташовується черга, тим вище її пріоритет. Процеси в черзі 1 не можуть виконуватися, якщо в черзі 0 є хоч би один процес. Процеси в черзі 2 не будуть вибрані для виконання, поки є хоч один процес в чергах 0 і 1. І, нарешті, процес в черзі 3 може отримати процесор у своє розпорядження тільки тоді, коли черги 0, 1 і 2 порожні. Якщо при роботі процесу з'являється інший процес в якій-небудь пріоритетнішій черзі, процес, що виконується, витісняється таким, що з'явився. Планування процесів усередині черг 0-2 здійснюється з використанням алгоритму RR, планування процесів в черзі 3 грунтується на алгоритмі FCFS.

Процес, що народився, поступає в чергу 0. При виборі на виконання він отримує у своє розпорядження квант часу розміром 8 одиниць. Якщо тривалість його CPU burst менше цього кванта часу, процес залишається в черзі 0. Інакше, він переходить в чергу 1. Для процесів з черги 1 квант часу має величину 16. Якщо процес не укладається в цей час, він переходить в чергу 2. Якщо укладається — залишається в черзі 1. У черзі 2 величина кванта часу складає 32 одиниці. Якщо і цього мало для безперервної роботи процесу, процес поступає в чергу 3, для якої квантування часу не застосовується, і, за відсутності готових процесів в інших чергах, він може виконуватися до закінчення свого CPU burst. Чим більше значення тривалості CPU burst, тим в менш пріоритетну чергу потрапляє процес, але тим на більший процесорний час він може розраховувати для свого виконання. Таким чином, через деякий час усі процеси, що вимагають малого часу роботи процесора виявляться розміщеними у високопріоритетних чергах, а усі процеси, що вимагають великого рахунку і з низькими запитами до часу відгуку, — в низькопріоритетних.

Мал. 3.6.Схема міграції процесів у багаторівневих чергах планування із зворотним зв'язком. Витіснення процесів пріоритетнішими процесами і завершення процесів на схемі не показане.

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

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

· Кількість черг для процесів, що знаходяться в змозі готовність.

· Алгоритм планування, діючий між чергами.

· Алгоритми планування, діючі усередині черг.

· Правила приміщення процесу, що народився, в одну з черг.

· Правила перекладу процесів з однієї черги в іншу.

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

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

1. Опишіть роботові алгоритму «Багаторівневі черги зі зворотним зв'язком»

2. Накресліть схему міграції процесів у багаторівневих чергах планування із зворотним зв'язком. Витіснення процесів пріоритетнішими процесами і завершення процесів на схемі не показане.

Література

Електроний ресурс http://cs.mipt.ru/docs/courses/osstud/ 03/ch3.htm