Алгоритм циклічного планування з прикладом

⚡ Розумний підсумок

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

🔄 Визначення: Кожне готове завдання виконується по черзі протягом фіксованого інтервалу часу.
🇧🇷 Квант часу: Процесор перемикає процеси через фіксований інтервал, квант часу.
🇧🇷 Справедливість: Кожен процес отримує рівний процесорний час, що запобігає перевантаженню.
🧮 Превентивний: Випереджений процес переміщується в кінець черги.
✅ переваги: Справедливий розподіл, відсутність ефекту конвою, передбачуваний час реагування.
⚠️ Недоліки: Продуктивність залежить від кванта часу та додає накладні витрати на перемикання контексту.

Детальніше

Що таке кругове планування?

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

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

Характеристики кругового планування

Ось важливі характеристики кругового планування:

Круговий алгоритм – це превентивний алгоритм.
Процесор перемикається на наступний процес після фіксованого інтервалу часу, який називається часовим квантом/часовим зрізом.
Процес, який виймається, додається в кінець черги.
Кругова система – це гібридна модель, яка працює за тактовим режимом.
Часовий інтервал має бути мінімальним, він призначається для конкретного завдання, яке потрібно обробити. Однак він може відрізнятися залежно від ОС.
Це алгоритм реального часу, який реагує на подію протягом певного проміжку часу.
Круговий робін — один із найстаріших, найсправедливіших та найпростіших алгоритмів.
Це широко використовуваний метод планування в традиційних ОС.

Приклад кругового планування

Розглянемо наступні три процеси:

Черга процесу	Час вибуху
P1	4
P2	3
P3	5

Крок 1) Виконання починається з процесу P1, який має час пакету 4. Тут кожен процес виконується протягом 2 секунд. P2 і P3 все ще в черзі.

Крок 2) У момент часу = 2, P1 додається до кінця черги, і P2 починає виконуватися.

Крок 3) У момент часу = 4, P2 витісняється та додається в кінець черги. Починається виконання P3.

Крок 4) У момент часу = 6, P3 витісняється та додається в кінець черги. Починається виконання P1.

Крок 5) У момент часу = 8, P1 має пакетний час виконання 4. Виконання завершено. P2 починає виконання.

Крок 6) P2 має час пакетної обробки 3. Він вже виконався протягом 2 інтервалів. У момент часу = 9 P2 завершує виконання. Потім P3 починає виконання до завершення.

Крок 7) Давайте розрахуємо середній час очікування для наведеного вище прикладу.

Wait time
P1 = 0 + 4 = 4
P2 = 2 + 4 = 6
P3 = 4 + 3 = 7

Переваги кругового планування

Ось переваги/плюси методу кругового планування:

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

Недоліки кругового планування

Ось недоліки/протипоказання використання циклічного планування:

Якщо час зрізання ОС низький, продуктивність процесора зменшиться.
Цей метод витрачає більше часу на перемикання контексту.
Його ефективність значною мірою залежить від кількості часу.
Для процесів неможливо встановити пріоритети.
Кругове планування не надає особливого пріоритету важливішим завданням.
Це знижує розуміння.
Менший квант часу призводить до вищих накладних витрат на перемикання контексту в системі.
Знаходження правильного кванта часу є досить складним завданням у цій системі.

Найгірша затримка

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

dt = Позначає час виявлення, коли завдання додається до списку
st = Позначає час перемикання з одного завдання на інше
et = Позначає час виконання завдання

формула:

^T_worst = {(dt_i+ st_i+ et_i ), + (dt_i+ st_i+ et_i )₂ +...+ (dt_i+ st_i + et_i )_N., + (dt_i+ st_i + et_i  + et_i) N} + t_ISR
t_ISR = sum of all execution times

Поширені запитання

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

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

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

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

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