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

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

Мета

Модуль 7 розбирає FCFS, SJF, Round Robin і MLFQ на одному прикладі з трьох задач. Симулятор перенесе їх у числа для будь-якого набору задач: SJF справді дає найменший середній час очікування, платить за це довга задача, яка чекає останньою, і жоден алгоритм не виграє за всіма метриками.

Після цієї роботи ви зможете:

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

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

Завдання

Написати програму sched, яка читає опис задач із файлу і друкує середні метрики для кожного алгоритму планування.

./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                  ...

Що має вміти:

FCFS і SJF, обидва невитісняльні.
SRTF, витісняльний варіант SJF.
Round Robin із квантом, який передається аргументом. Без аргументу квант дорівнює 4: автоперевірка запускає програму без нього.
MLFQ з кількома чергами і періодичним підняттям усіх задач угору. Для нього формат задачі розширюється описом «працює X, потім чекає Y».
Простій процесора: якщо жодна задача ще не надійшла, час іде далі.
Вироджений випадок з однією задачею.

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

Обмеження. Мова будь-яка: скрипт запускає ./sched і читає лише вивід.

Що записати у звіт:

метрики на прикладі з модуля 7 і збіг із числами 17.00, 3.00 і 5.67;
таблицю «квант → середній час відгуку, кількість перемикань» для RR;
метрики всіх алгоритмів на трьох наборах з етапу «Порівняння»;
висновок: який алгоритм виграв на якому наборі і за якою метрикою.

Готово, коли:

./check.sh ./sched проходить усі тринадцять перевірок на чотирьох наборах;
SRTF і MLFQ, яких перевірка не торкається, друкують рядки в тій самій таблиці; на прикладі з модуля SRTF збігається з SJF, бо всі задачі надходять у нульовий момент;
у звіті є таблиця порівняння і висновок.

Перед початком

Прочитайте в модулі 7 розділи «Що оптимізуємо», «Класичні алгоритми» і «Багаторівневі черги зі зворотним зв’язком».
Розпакуйте архів курсу: перевірка лежить у labs/a2-scheduler/check.sh, набори задач вона створює сама.
Підійде будь-який Linux, зокрема контейнер і WSL2. Із системи потрібен лише компілятор або інтерпретатор вашої мови.

Етапи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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