Основи планування: FCFS, SJF і Round-Robin

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

Цілі лекції

Після опрацювання матеріалу ви зможете:

• розрізняти довгострокове, середньострокове й короткострокове планування;
• пояснювати пропускну здатність, використання CPU, справедливість, час очікування, відгуку й обороту;
• відрізняти витискальне планування від невитискального;
• будувати діаграми Ганта для FCFS, невитискального SJF і Round-Robin;
• обчислювати час очікування, відгуку й обороту;
• пояснювати сильні сторони й обмеження трьох алгоритмів.

Передумови

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

1. Рівні планування

Довгостроковий планувальник контролює надходження робіт і співвідношення CPU-bound та I/O-bound навантажень. У багатьох інтерактивних ОС ця роль менш виражена, ніж у пакетних системах.

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

Короткостроковий планувальник обирає задачу з черги готових. Саме з його рішеннями пов'язані FCFS, SJF і RR у цій лекції. Диспетчер технічно передає керування обраній задачі: перемикає контекст і переходить до потрібної команди.

2. Критерії планування

Цілі можуть конфліктувати:

• використання CPU - частка часу корисної роботи процесора;
• пропускна здатність (throughput) - кількість завершених робіт за одиницю часу;
• час обороту (turnaround time) - від надходження до завершення;
• час очікування (waiting time) - сумарний час у черзі готових;
• час відгуку (response time) - від надходження до першого запуску;
• справедливість - відсутність невиправданого голодування та прийнятний розподіл CPU.

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

3. Позначення і формули

Для кожного процесу використовуватимемо:

• A (arrival time) - час надходження до черги готових;
• B (burst time) - потрібний час CPU;
• S (start time) - момент першого запуску;
• C (completion time) - момент завершення;
• T (turnaround time) - час обороту;
• W (waiting time) - сумарний час очікування;
• R (response time) - час першого відгуку.

T = C - A
W = T - B
R = S - A

Формула W = T - B коректна для наших прикладів, де B є всім часом виконання на CPU і немає окремих I/O burst. Для витискального алгоритму очікування може складатися з кількох проміжків, але формула все одно врахує їх суму.

4. Витискальне і невитискальне планування

За невитискального (non-preemptive) планування задача після отримання CPU працює до завершення свого CPU burst або добровільного блокування.

За витискального (preemptive) планування ОС може перервати задачу: наприклад, після вичерпання кванту, надходження важливішої роботи або системної події.

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

5. Наскрізний набір процесів

В усіх трьох алгоритмах використаємо ті самі дані:

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

6. FCFS

First-Come, First-Served виконує задачі в порядку надходження. Це проста невитискальна черга FIFO.

0        5     8 9    11
|   P1   | P2  |P3| P4 |

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

7. Невитискальний SJF

Shortest Job First обирає серед уже готових задач найкоротший CPU burst. Алгоритм не може вибрати процес, який ще не надійшов.

У момент 0 готовий лише P1, тому він працює до 5. Потім доступні P2, P3 і P4; порядок за тривалістю: P3, P4, P2.

0        5 6    8     11
|   P1   |P3| P4 | P2  |

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

Витискальний варіант називають Shortest Remaining Time First (SRTF). Він не входить до розрахунку цієї лекції.

8. Round-Robin

Round-Robin (RR) дає кожній готовій задачі не більше кванту q. Якщо задача не завершилася, її витискають і додають у хвіст черги.

Для q = 2 готова черга змінюється так:

0   2   4 5   7   9 10 11
| P1| P2|P3| P1| P4|P2|P1|

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

Вибір кванту важливий:

• дуже великий q наближає RR до FCFS;
• дуже малий q дає частіший відгук, але збільшує кількість перемикань контексту;
• квант має бути суттєво більшим за час самого перемикання.

9. Як не помилитися в розрахунках

1. Спочатку побудуйте часову шкалу, враховуючи моменти надходження.
2. Запишіть перший старт S і завершення C кожного процесу.
3. Обчисліть T = C - A.
4. Обчисліть W = T - B.
5. Обчисліть R = S - A, використовуючи лише перший старт.
6. Перевірте, що сума всіх виконаних відрізків дорівнює сумі burst: 5+3+1+2=11.

Не плутайте response time із turnaround time: відгук закінчується під час першого отримання CPU, оборот - під час повного завершення.

Практичні завдання

Завдання 1. Відтворіть FCFS

Для наскрізного набору самостійно побудуйте шкалу FCFS, знайдіть S і C, а потім перевірте значення таблиці.

Завдання 2. Змініть квант

Побудуйте RR для того самого набору з q = 1. Після кожної одиниці часу явно записуйте готову чергу. Порівняйте кількість перемикань і середній час відгуку з q = 2.

Завдання 3. Оберіть алгоритм для сценарію

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

Підсумок

• Довгострокове планування допускає роботи, середньострокове призупиняє й повертає процеси, короткострокове обирає наступну готову задачу.
• Критерії планування конфліктують: кращий середній оборот не гарантує кращого першого відгуку чи справедливості.
• T=C-A, W=T-B, R=S-A.
• FCFS простий, але має ефект конвою.
• Невитискальний SJF віддає CPU найкоротшій із готових задач, але потребує оцінки burst і може спричинити голодування.
• Round-Robin витискає задачу після кванту й покращує інтерактивний відгук ціною перемикань.
• Коректний розрахунок починається з часової шкали й чітких правил обробки одночасних подій.