A2. Симулятор планувальника

базовийспирається на модуль 7

Мета

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

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

Що має вийти

Програма, яка читає опис задач і друкує метрики для кожного алгоритму.

./sched workload.txt

На вході текстовий файл, рядок на задачу: ім’я, час надходження, тривалість, пріоритет.

# name arrival burst priority
A 0 24 2
B 0 3 1
C 0 3 1

Вихід — рядок на алгоритм із трьома метриками, усі усереднені:

алгоритм       очікування  оборот  відгук
FCFS                 17.00   27.00   17.00
SJF                   3.00   13.00    3.00
RR(q=4)               5.67   15.67    3.67
MLFQ                  ...

Етапи

1. Читання опису й перевірка на прикладі з модуля.

   Набір A 0 24, B 0 3, C 0 3 розібраний у модулі 7: FCFS дає 17.00, SJF — 3.00, RR із квантом 4 — 5.67. Якщо ваші числа збігаються, читання і метрики правильні.

2. FCFS і SJF.

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

3. SRTF — витісняльний варіант SJF.

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

4. Round Robin із параметром кванта.

   Квант передається аргументом. Обов’язково побудуйте графік «квант → середній час відгуку» і «квант → кількість перемикань»: на ньому видно компроміс, про який ідеться в модулі.

5. MLFQ.

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

   Щоб MLFQ мав сенс, задачам потрібна поведінка вводу-виводу: додайте у формат опис «працює X, потім чекає Y».

6. Порівняння.

   Прогоніть усі алгоритми на трьох різних наборах: тільки обчислювальні задачі, тільки інтерактивні, суміш. Зробіть висновок письмово.

Метрики рахуються так

Для задачі: час обороту = завершення − надходження; час очікування = оборот − тривалість; час відгуку = перший запуск − надходження.

Усі три усереднюються по задачах. Плутанина між оборотом і очікуванням — найчастіша причина, коли числа «майже збігаються» з еталонними.

Автоперевірка

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

cd labs/a2-scheduler
./check.sh ./sched

Перевірка ганяє п’ять наборів із наперед порахованими відповідями, включно з прикладом із модуля 7 і випадком, де FCFS демонструє ефект конвою.

Часті помилки

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

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

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

MLFQ без старіння. Без періодичного підняття довгі задачі не отримають процесора ніколи. Це не особливість реалізації, а голодування.

Далі, якщо цікаво

Додати SCHED_FIFO і SCHED_RR як окремі класи з абсолютним пріоритетом над рештою — і побачити, як задача реального часу підвішує всі інші.