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

В обох випадках вибір процесу на виконання з черги готових здійснюється однаково: вибирається процес, що має найвищий пріоритет. По різному зважується проблема визначення моменту зміни активного процесу. У системах з відносними пріоритетами активний процес виконується доти, поки він сам не залишить процесор, перейшовши в стан ОЧІКУВАННЯ (чи ж відбудеться помилка, чи процес завершиться). У системах з абсолютними пріоритетами виконання активного процесу переривається ще при одній умові: якщо в черзі готових процесів з'явився процес, пріоритет якого вище пріоритету активного процесу. У цьому випадку перерваний процес переходить у стан готовності. На малюнку 7 показані графи станів процесу для алгоритмів з відносними (а) і абсолютними (б) пріоритетами.

Рис. 7. Графи станів процесів у системах
(а) з відносними пріоритетами; (б)з абсолютними пріоритетами.

3.1. Алгоритми планування, засновані на квантуванні.

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

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

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

Кванти, виділені одному потоку, можуть бути фіксованої величини, а можуть і змінюватися в різні періоди життя потоку. Нехай, наприклад, спочатку кожному потоку призначається досить великий квант, а величина кожного наступного кванта зменшується до деякої заздалегідь заданої величини. У такому випадку перевагу одержують короткі задачі, які встигають виконуватися протягом першого кванта, а тривалі обчислення будуть проводитися у фоновому режимі. Можна уявити собі алгоритм планування, у якому кожен наступний квант, визначений конкретному потоку, більше попереднього. Такий підхід дозволяє зменшити накладні витрати на переключення задач у тому випадку, коли відразу декілька задач виконують тривалі обчислення.

Потоки одержують для виконання квант часу, але деякі з них використовують його не цілком, наприклад через необхідність виконати ввід або вивід даних. У результаті виникає ситуація, коли потоки з інтенсивними звертаннями до в/в використовують тільки невелику частину виділеного їм процесорного часу. Алгоритм планування може виправити цю «несправедливість». Як компенсацію за невикористані цілком кванти потоки одержують привілеї при наступному обслуговуванні. Для цього планувальник створює дві черги готових потоків Черга 1 утворена потоками, що прийшли в стан готовності в результаті вичерпання кванта часу, а черга 2 — потоками, яких завершилася операція в/в. При виборі потоку для виконання насамперед проглядається друга черга, і тільки якщо квант виділяється потоку з першої черги.

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

3. 2. Алгоритми планування, засновані на пріоритетах

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

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

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

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

У системах з