5. Багаторівневі черги із зворотним зв'язком (Multilevel Feedback Queue)

Для систем, в яких процеси можуть бути легко розсортовані на різні групи, був розроблений інший клас алгоритмів планування. Для кожної групи процесів створюється своя черга процесів, що знаходяться в стані готовність. Цим чергам приписуються фіксовані пріоритети. Наприклад, пріоритет черги системних процесів встановлюється більше, ніж пріоритет черг призначених для користувача процесів. А пріоритет черги процесів, запущених студентами, — нижче, ніж для черги процесів, запущених викладачами. Це значить, що жоден призначений для користувача процес не буде вибраний для виконання, поки є хоч один готовий системний процес, і жоден студентський процес не одержить в своє розпорядження процесор, якщо є процеси викладачів, готові до виконання. Усередині цих черг для планування можуть застосовуватися самі різні алгоритми. Так, наприклад, для великих рахункових процесів, що не вимагають взаємодії з користувачем (фонових процесів), може використовуватися алгоритм FCFS, а для інтерактивних процесів — алгоритм RR.

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

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

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

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

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

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

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

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

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

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

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

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

               Планування з використанням багаторівневої черги. (Multilevel queue scheduling)

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

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

Вибір черги здійснюється за наступними правилами:

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