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

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

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

2) Вибір процесу на виконання з черги готових процесів.

3) Переключення контекстів „старих” і „нових” процесів.

1) та 2) розв’язуються програмними засобами, а 3) в значній мірі апаратно.

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

- побудовані на принципі квантування;

- побудовані на принципі пріоритетів.

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

- процес закінчився і покинув систему;

- процес перейшов в стан Очікування;

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

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

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

- циклічно;

- FIFO (перший прийшов — перший обслуговується);

- LIFO (останній прийшов — перший обслуговується ).

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

 

 

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

Є алгоритми які використовують:

- відносні пріоритети;

- абсолютні пріоритети.

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

Інакше розв’язується проблема визначення моменту зміни активного процесу.

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

 

 

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

У багатьох ОС алгоритми планування побудовані з використанням як квантування, так і пріоритетів. Наприклад, в основі планування лежить квантування, але величина кванту так/або порядок вибору процесу з черги готових визначається пріоритетами процесів.