Алгоритми планування процесів у сучасних ОС.

Алгоритми планування процесів у сучасних ОС.

Планування процесів і потоків

• Підсистема управління процесами і потоками в ОС відповідальна за забезпечення процесів необхідними ресурсами;
• ОС використовує спеціальні інформаційні структури, для зберігання інформації про те, які ресурси виділені кожному процесу;
• Поняття процес (задача) і потік (нитка);
• Поняття синхронізації потоків;

Управління процесами

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

Створити процес - це перш за все створити описувач процесу, який необхідний ОС для управління ним (наприклад: ідентифікатор процесу, ступінь привилегированности). Приклади описателей процесу:

• Блок управління завданням (ТСВ) в OS/360;
• Керуючий блок процесу (РСВ) в OS/2;
• Дескриптор процесу в UNIX;
• Об'єкт-процес Windows;

Створення процесу включає завантаження кодів і даних в оперативну пам'ять

• У багатопоточній системі при створенні процесу ОС створює потік;
• Потік-нащадок;

Планування і диспетчеризація потоків

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

Завдання планування:

• Визначення моменту часу для зміни поточного активного потоку;
• Вибір для виконання потоку з черги готових потоків;

Диспетчеризація - це реалізація рішення, знайденого в результаті планування.

Завдання диспетчеризації:

• Збереження контексту поточного потоку;
• Завантаження контексту нового потоку;
• Запуск нового потоку на виконання;

Управління процесами

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

Стан процесів

• ВИКОНАННЯ - активне стан процесу, під час якого процес володіє всіма необхідними ресурсами і безпосередньо виконується процесором;
• ОЧІКУВАННЯ - пасивне стан процесу, процес заблокований, він не може виконуватися по своїх внутрішніх причин, він чекає здійснення деякої події, наприклад, завершення операції вводу-виводу, одержання повідомлення від іншого процесу, звільнення якого-небудь необхідного йому ресурсу;
• ГОТОВНІСТЬ - також пасивне стан процесу, але в цьому випадку процес заблокований у зв'язку з зовнішніми по відношенню до нього обставинами: процес має всі необхідні для нього ресурси, він готовий виконуватися, однак процесор зайнятий виконанням іншого процесу.

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

В стані ВИКОНАННЯ в однопроцесорній системі може знаходитися тільки один процес, а в кожному з станів ОЧІКУВАННЯ і ГОТОВНІСТЬ - кілька процесів, ці процеси утворюють черги відповідно очікують і готових процесів. Життєвий цикл процесу починається з стану ГОТОВНІСТЬ, коли процес готовий до виконання і чекає своєї черги. При активізації процес переходить у стан ВИКОНАННЯ та знаходиться в ньому до тих пір, поки або він сам звільнить процесор, перейшовши в стан ЧЕКАННЯ якої-небудь події, або буде насильно "витиснутий" з процесора, наприклад, внаслідок вичерпання відведеного даному процесу кванта процесорного часу. В останньому випадку процес повертається в стан ГОТОВНІСТЬ. У цей же стан процес переходить з стану ОЧІКУВАННЯ, після того, як очікувана подія відбудеться.

Алгоритми планування

Два класа:

• Що не витісняють - рішення приймається додатком (застосовуються в NetWare)
• Що витісняють - рішення приймається ОС (застосовуються в UNIX, Windows, OS/2, VMS)

Алгоритми планування процесів

Планування процесів включає в себе рішення наступних завдань:

• визначення моменту часу для зміни виконуваного процесу;
• вибір процесу на виконання з черги готових процесів;
• перемикання контекстів "старого" і "нового" процесів.

Існує два основних типи процедур планування процесів - витісняють (preemptive) і не витісняють (non-preemptive).

Non-preemptive multitasking - невытесняющая багатозадачність - це спосіб планування процесів, при якому активний процес виконується до тих пір, поки він сам, за власною ініціативою, не віддасть управління планувальником операційної системи для того, щоб той вибрав з черги інший, готовий до виконання процес. Preemptive multitasking - яка витискає багатозадачність - це такий спосіб, при якому рішення про переключення процесора з виконання одного процесу на виконання іншого процесу приймається планувальником операційної системи, а не самою активною задачею.

Найбільш часто зустрічаються алгоритми:

• алгоритми, засновані на квантуванні
• алгоритми, засновані на пріоритетах

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

Існує безліч різних алгоритмів планування процесів, по-різному що вирішують перераховані вище завдання, переслідують різні цілі і забезпечують різне якість мультипрограммирования. Серед цієї безлічі алгоритмів розглянемо докладніше дві групи найбільш часто зустрічаються алгоритмів: алгоритми, засновані на квантуванні, і алгоритми, засновані на пріоритетах. Відповідно з алгоритмами, засновані на квантуванні, зміна активного процесу відбувається, якщо: процес завершився і покинув систему; помилка; процес перейшов у стан ОЧІКУВАННЯ; вичерпано квант процесорного часу, відведений даному процесу.

Інша група алгоритмів використовує поняття "пріоритет" процесу. Пріоритет - це число, характеризує ступінь привилегированности процесу при використанні ресурсів обчислювальної машини, зокрема, процесорного часу: чим вище пріоритет, тим вище привілеї.

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

Існує дві різновиди пріоритетних алгоритмів: алгоритми, що використовують відносні пріоритети, і алгоритми, що використовують абсолютні пріоритети. Алгоритми планування процесів, засновані на квантуванні.

Відповідно з алгоритмами, засновані на квантуванні, зміна активного процесу відбувається, якщо:

• процес завершився і залишив систему,
• сталася помилка,
• процес перейшов у стан ОЧІКУВАННЯ,
• вичерпано квант процесорного часу, відведений даного процесу.

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

Різновиди пріоритетних алгоритмів

• Алгоритми - використовують відносні пріоритети
• Алгоритми - використовують абсолютні пріоритети

Алгоритми планування

Існує досить великий набір різноманітних алгоритмів планування, які призначені для досягнення різних цілей і ефективні для різних класів задач. Багато з них можуть використовуватися на кількох рівнях планування. В цьому розділі ми розглянемо деякі найбільш уживані алгоритми стосовно процесу короткочасного планування.

First-Come, First-Served (FCFS)

Найпростішим алгоритмом планування є алгоритм, який прийнято позначати абревіатурою FCFS по першим літерам його англійської назви - First-Come, First-Served (першим прийшов, першим обслужений). Уявімо собі, що процеси, що перебувають у стані готовність, збудовані в чергу. Коли процес переходить в стан готовність, він, а точніше, посилання на його PCB поміщається в кінець цієї черги. Вибір нового процесу для виконання здійснюється з початку черги з видаленням звідти посилання на PCB. Чергу подібного типу має в програмуванні спеціальне найменування - FIFO1), скорочення від First In, First Out (першим ввійшов, першим вийшов).

Такий алгоритм вибору процесу здійснює невытесняющее планування. Процес, що отримав у своє розпорядження процесор, займає його до закінчення поточного CPU burst. Після цього для виконання вибирається новий процес з початку черги.

Перевагою алгоритму FCFS є легкість його реалізації, але в той же час він має і багато недоліків. Розглянемо наступний приклад. Нехай у стані готовність знаходяться три процесу p0, p1 і p2, для яких відомі часи їх чергових CPU burst. Ці часи наведені в таблиці 3.1. в деяких умовних одиницях. Для простоти будемо вважати, що вся діяльність процесів обмежується використанням тільки одного проміжку CPU burst, що процеси не здійснюють операцій вводу-виводу і що час перемикання контексту так мало, що ними можна знехтувати.

Якщо процеси розташовані в черзі процесів, готових до виконання порядку p0, p1, p2, то картина їх виконання виглядає так, як показано на малюнку 3.2. Першим для виконання вибирається процес p0, який процесор отримує на весь час свого CPU burst, тобто на 13 одиниць часу. Після його закінчення в стан виконання перекладається процес p1, він займає процесор на 4 одиниці часу. І, нарешті, можливість працювати отримує процес p2. Час очікування для процесу p0 становить 0 одиниць часу, для процесу p1 – 13 одиниць, для процесу p2 – 13 + 4 = 17 одиниць. Таким чином, середній час очікування в цьому випадку - (0 + 13 + 17)/3 = 10 одиниць часу. Повний час виконання для процесу p0 становить 13 одиниць часу, для процесу p1 – 13 + 4 = 17 одиниць, для процесу p2 – 13 + 4 + 1 = 18 одиниць. Середнє повне час виконання виявляється рівним (13 + 17 + 18)/3 = 16 одиницям часу.

Round Robin (RR)

Модифікацією алгоритму FCFS є алгоритм, який отримав назву Round Robin (Round Robin - це вид дитячої каруселі в США) або скорочено RR. По суті, це той же самий алгоритм, реалізований тільки в режимі яка витісняє планування. Можна уявити собі всі безліч готових процесів організованим циклічно - процеси сидять на каруселі. Карусель обертається так, що кожен процес знаходиться близько процесора невеликий фіксований квант часу, звичайно 10 – 100 мілісекунд (див. рис. 3.4.). Поки процес знаходиться поруч з процесором, він отримує процесор свого розпорядження і може виконуватися.

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

Першим для виконання вибирається процес p0. Тривалість його CPU burst більше, ніж величина кванта часу і тому процес виповнюється до закінчення кванта, тобто протягом 4 одиниць часу. Після цього він поміщається в кінець черги готових до виконання процесів, яка приймає вигляд p1, p2, p0. Наступним починає виконуватися процес p1. Час його виконання збігається з величиною вибраного кванта, тому процес працює до свого завершення. Тепер черга процесів у стані готовність складається з двох процесів, p2 і p0. Процесор виділяється процесу p2. Він завершується до закінчення відпущеного йому процесорного часу, і чергові кванти відміряють процесу p0 - єдиного не закінчив до цього моменту свою роботу. Час очікування для процесу p0 (кількість символів "Г" у відповідному рядку) становить 5 одиниць часу, для процесу p1 – 4 одиниці часу, для процесу p2 – 8 одиниць часу. Таким чином, середній час очікування для цього алгоритму виходить рівним (5 + 4 + 8)/3 = 5,6(6) одиниці часу. Повне час виконання процесу p0 (кількість непустих стовпців відповідному рядку) становить 18 одиниць часу, для процесу p1 – 8 одиниць, для процесу p2 – 9 одиниць. Середнє повне час виконання виявляється рівним (18 + 8 + 9)/3 = 11,6(6) одиниці часу.

Легко побачити, що середній час очікування і середнє повне час виконання для зворотного порядку процесів не відрізняються від відповідних часів для алгоритму FCFS і складають 2 і 8 одиниць часу відповідно.

На продуктивність алгоритму RR сильно впливає величина кванта часу. Розглянемо той самий приклад з порядком процесів p0, p1, p2 для величини кванта часу, що дорівнює 1 (див. табл. 3.3.). Час очікування для процесу p0 складе 5 одиниць часу, для процесу p1 - теж 5 одиниць, для процесу p2 – 2 одиниці. В цьому випадку середній час очікування виходить рівним (5 + 5 + 2)/3 = 4 одиниць часу. Середнє повне час виконання складе (18 + 9 + 3)/3 = 10 одиниць часу.

При дуже великих величинах кванта часу, коли кожен процес встигає завершити свій CPU burst до виникнення переривання по часу, алгоритм RR вироджується в алгоритм FCFS. При дуже малих величинах створюється ілюзія того, що кожен з n процесів працює на власному віртуальному процесорі з продуктивністю ~ 1/n від продуктивності реального процесора. Правда, це справедливо лише при теоретичному аналізі за умови нехтування часом перемикання контексту процесів. У реальних умовах при занадто малою величиною кванта часу і, відповідно, занадто частому перемиканні контексту накладні витрати на переключення різко знижують продуктивність системи.

Shortest-Job-First (SJF)

При розгляді алгоритмів FCFS і RR ми бачили, наскільки істотним для них є порядок розташування процесів в черзі процесів, готових до виконання. Якщо короткі задачі розташовані в черзі ближче до її початку, то загальна продуктивність цих алгоритмів значно зростає. Якщо б ми знали час наступних CPU burst для процесів, що перебувають у стані готовність, то могли б вибрати для виконання не процес з початку черги, а процес з мінімальною тривалістю CPU burst. Якщо ж таких процесів два або більше, то для вибору одного з них можна використовувати вже відомий нам алгоритм FCFS. Квантування часу при цьому не застосовується. Описаний алгоритм отримав назву "найкоротша робота першої" або Shortest Job-First (SJF).

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

При використанні невытесняющего алгоритму SJF першим для виконання буде обрано процес p3, що має найменше значення тривалості чергового CPU burst. Після його завершення для виконання вибирається процес p1, потім p0 і, нарешті, p2. Ця картина відображена в таблиці 3.5.

Як ми бачимо, середній час очікування для алгоритму SJF становить (4 + 1 + 9 + 0)/4 = 3,5 одиниці часу. Легко порахувати, що для алгоритму FCFS при порядку процесів p0, p1, p2, p3 ця величина буде дорівнювати (0 + 5 + 8 + 15)/4 = 7 одиницям часу, тобто буде в два рази більше, ніж для алгоритму SJF. Можна показати, що для заданого набору процесів (якщо в черзі не з'являються нові процеси) алгоритм SJF є оптимальним з погляду мінімізації середнього часу очікування серед класу невытесняющих алгоритмів.

Для розгляду прикладу яка витісняє SJF планування ми візьмемо ряд процесів p0, p1, p2 і p3 з різними часом CPU burst і різними моментами їх появи в черзі процесів, готових до виконання (див. табл. 3.6.).

У початковий момент часу в стан готовність знаходяться тільки два процесу, p0 і p3. Менший час чергового CPU burst виявляється у процесу p3 тому він і вибирається для виконання (див. таблицю 3.7.). По закінченні 2 одиниць часу в систему надходить процес p1. Час його CPU burst менше, ніж залишок CPU burst у процесу p3, який витісняється зі стану виконання і переводиться в стан готовність. За після ще 2 одиниць часу процес p1 завершується, і для виконання знову вибирається процес p3. У момент часу t = 6 у черзі процесів, готових до виконання, з'являється процес p2, але оскільки йому для роботи потрібно 7 одиниць часу, а процесу p3 залишилося працювати всього 1 одиницю часу, то процес p3 залишається в стані виконання. Після його завершення в момент часу t = 7 у черзі перебувають процеси p0 і p2, з яких вибирається процес p0. Нарешті, останнім отримає можливість виконуватися процес p2.

Основну складність при реалізації алгоритму SJF є неможливість точного знання тривалості чергового CPU burst для які працюють процесів. В пакетних системах кількість процесорного часу, необхідне завдання для виконання, вказує користувач при формуванні завдання. Ми можемо брати цю величину для здійснення довгострокового SJF-планування. Якщо користувач вкаже більше часу, ніж йому потрібно, він буде чекати результату довше, ніж міг би, так як завдання буде завантажено в систему пізніше. Якщо ж він вкаже меншу кількість часу, завдання може не дорахуватися до кінця. Таким чином, в пакетних системах рішення завдання оцінки часу використання процесора перекладається на плечі користувача. При короткостроковому плануванні ми можемо робити тільки прогноз тривалості наступного CPU burst, виходячи з передісторії процесу. Нехай τ(n) - величина n-го CPU burst, T(n + 1) - передбачене значення для n + 1-го CPU burst, alpha- деяка величина в діапазоні від 0 до 1.

Визначимо рекурентне співвідношення

T(n+1)= alphaτ(n)+(1-alpha)T(n) T(0) покладемо довільній константою. Перше доданок враховує останнім поведінку процесу, тоді як другий доданок враховує його передісторію. При alpha= 0 ми перестаємо стежити за останнім поведінкою процесу, фактично вважаючи

T(n)= T(n+1)=...=T(0) тобто оцінюючи всі CPU burst однаково, виходячи з деякого початкового припущення.

Поклавши alpha= 1 ми забуваємо про передісторії процесу. У цьому випадку ми вважаємо, що час чергового CPU burst буде збігатися з часом останнього CPU burst:

T(n+1)= τ(n) Зазвичай вибирають alpha= 1/2 для рівноцінного обліку останнього поведінки і передісторії. Треба зазначити, що такий вибір alphaзручний і для швидкої організації обчислення оцінки T(n + 1). Для підрахунку нової оцінки потрібно взяти стару оцінку, скласти з виміряним часом CPU burst і отриману суму розділити на 2 наприклад, зсунувши її на 1 біт вправо. Отримані оцінки T(n + 1) застосовуються як тривалості чергових проміжків часу безперервного використання для процесору короткострокового SJF-планування.

Гарантоване планування

При інтерактивній роботі N користувачів обчислювальної системі можна застосувати алгоритм планування, який гарантує, що кожен із користувачів матиме в своєму розпорядженні ~1/N частину процесорного часу. Пронумеруємо всіх користувачів від 1 до N. Для кожного користувача з номером i введемо дві величини: Ti - час перебування користувача в системі або, іншими словами, тривалість сеанси його спілкування з машиною і τi - сумарна процесорний час вже виділене всіх його процесів протягом сеансу. Справедливим для користувача було б отримання Ti/N процесорного часу. Якщо

τi<<Ti/N то i-й користувач несправедливо обділений процесорним часом. Якщо ж

τi>>Ti/N система явно прихильний до користувача з номером i. Обчислимо для процесів кожного користувача значення коефіцієнта справедливості

τiN/Ti і будемо надавати черговий квант часу готовому процесу з найменшою величиною цього відношення. Запропонований алгоритм називають алгоритмом гарантованого планування. До недоліків цього алгоритму можна віднести неможливість передбачити поведінку користувачів. Якщо деякий користувач відправиться на пару годин і пообідати поспати, не перериваючи сеансу роботи, то після повернення його процеси будуть отримувати невиправдано багато процесорного часу.

Пріоритетне планування

Алгоритми SJF і гарантованого планування являють собою приватні випадки пріоритетного планування. При пріоритетне планування кожному процесу присвоюється певне числове значення - пріоритет, у відповідності з яким йому виділяється процесор. Процеси з однаковими пріоритетами плануються в порядку FCFS. Для алгоритму SJF в якості такого пріоритету виступає оцінка тривалості наступного CPU burst. Чим менше значення цієї оцінки, тим більше високий пріоритет має процес. Для алгоритму гарантованого планування пріоритетом служить обчислений коефіцієнт справедливості. Чим він менше, тим більше у процесу пріоритет.

Алгоритми призначення пріоритетів процесів можуть спиратися як на внутрішні параметри, пов'язані з подіями всередині обчислювальної системи, так і на зовнішні по відношенню до неї. До внутрішнім параметрами відносяться різні кількісні та якісні характеристики процесу такі як: обмеження за часом використання процесора, вимоги до розміру пам'яті, кількість відкритих файлів і використовуваних пристроїв введення-виведення, відношення середніх тривалостей I/O burst до CPU burst і т. д. Алгоритми SJF та гарантованого планування використовують внутрішні параметри. В якості зовнішніх параметрів можуть виступати важливість процесу для досягнення будь-яких цілей, вартість сплаченого процесорного часу й інші політичні чинники. Високий зовнішній пріоритет може бути присвоєний задачі лектора або того, хто заплатив $100 за роботу протягом однієї години.

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

Нехай в чергу процесів, що перебувають у стані готовність, надходять ті ж процеси, що й у прикладі яка витісняє алгоритму SJF, тільки їм додатково ще привласнені пріоритети . В обчислювальних системах не існує певної угоди, яке значення пріоритету – 1 або 4 вважати більш пріоритетним. Щоб уникнути плутанини, у всіх наших прикладах ми будемо припускати, що більше значення відповідає меншому пріоритету, тобто найбільш пріоритетним у нашому прикладі є процес p3, а найменш пріоритетним - процес p0.

Як будуть вести себе процеси при використанні невытесняющего пріоритетного планування? Першим для виконання в момент часу t = 0 вибирається процес p3, як володіє найвищою пріоритетом. Після його завершення в момент часу t = 5 в черзі процесів, готових до виконання, опиняться два процесу p0 і p1. Більший пріоритет з них у процесу p1 він і почне виконуватися . Потім у момент часу t = 8 для виконання буде обраний процес p2 і лише потім - процес p0.

Іншим буде надання процесора процесам у разі яка витісняє пріоритетного планування . Першим, як і в попередньому випадку, почне виконуватися процес p3, а по його закінченні - процес p1. Однак у момент часу t = 6 він буде витіснений процесом p2 і продовжить своє виконання тільки в момент часу t = 13. Останнім, як і раніше, буде виконуватися процес p0.

У розглянутому вище прикладі пріоритети процесів з плином часу не змінювалися. Такі пріоритети прийнято називати статичними. Механізми статичного пріоритетності легко реалізувати, і вони пов'язані з відносно невеликими витратами на вибір найбільш пріоритетного процесу. Однак статичні пріоритети не реагують на зміни ситуації в обчислювальній системі, які можуть зробити бажаною коригування порядку виконання процесів. Більш гнучкими є динамічні пріоритети процесів, змінюють свої значення за ходу виконання процесів. Початкове значення динамічного пріоритету, присвоєне процесу, діє протягом лише короткого періоду часу, після чого йому призначається нове, більш відповідне значення. Зміна динамічного пріоритету процесу є єдиною операцією над процесами, яку ми до сих пір не розглянули. Як правило, зміна пріоритету процесів проводиться узгоджено з вчиненням будь-яких інших операцій: при народженні нового процесу, розблокування або блокування процесу, після закінчення певного кванта часу або по завершенні процесу. Прикладами алгоритмів з динамічними пріоритетами є алгоритм SJF і алгоритм гарантованого планування. Схеми з динамічною пріоритетністю набагато складніше в реалізації і пов'язані з великими витратами по порівнянні зі статичними схемами. Однак їх використання передбачає, що ці витрати виправдовуються поліпшенням роботи системи.

Головна проблема пріоритетного планування полягає в тому, що при неналежному виборі механізму призначення та зміни пріоритетів низкоприоритетные процеси не можуть запускатися невизначено довгий час. Зазвичай трапляється одне з двох. Або вони все ж чекають своєї черги на виконання (в дев'ять годин ранку в неділю, коли всі пристойні програмісти лягають спати). Або обчислювальну систему доводиться вимикати, і вони губляться (при зупинці IBM 7094 в Массачусетському технологічному інституті в 1973 році були знайдені процеси, запущені в 1967 році і жодного разу з тих пір не исполнявшиеся). Рішення цієї проблеми може бути досягнуто з допомогою збільшення з часом значення пріоритету процесу, що перебуває у стані готовність. Нехай спочатку процесів присвоюються пріоритети від 128 до 255. Кожен раз після закінчення певного проміжку часу значення пріоритетів готових процесів зменшуються на 1. Процесу, побував в стані виконання, присвоюється початкове значення пріоритету. Навіть така груба схема гарантує, що будь-якому процесу в розумні терміни буде надано право на виконання.