Планирование CPU
Как ОС решает, кто выполняется следующим, и почему этот выбор меняет и среднее ожидание, и справедливость.
Работы всегда больше, чем CPU. Планировщик выбирает один готовый процесс за раз, и этот выбор определяет, кто ждёт. Разные цели — пропускная способность, задержка, справедливость — приводят к разным алгоритмам.
Сначала приходит долгая задача. Посмотри, как всё за ней простаивает.
| Процесс | Приход | Длительность | Состояние | Использовано |
|---|---|---|---|---|
| P1 | 0 | 6 | ожидает | — |
| P2 | 1 | 4 | ожидает | — |
| P3 | 2 | 2 | ожидает | — |
| P4 | 3 | 1 | ожидает | — |
- P1
P1 приходит с длительностью 6мс
- Среднее время ожидания
- 0
- Среднее время оборота
- 0
- Общее время
- 0
| Алгоритм | Среднее время ожидания | Среднее время оборота | Общее время |
|---|---|---|---|
| First-Come, First-Served | 5.5 | 8.75 | 13 |
| Shortest Job First | 4 | 7.25 | 13 |
| Round-Robin | 5.75 | 9 | 13 |
Время ожидания — сколько процесс простоял готовым, не выполняясь. Время оборота — от появления до завершения. Именно по этим двум числам и оценивают алгоритмы планирования.
Round-Robin даёт каждому процессу фиксированный квант и переходит к следующему. Ни один процесс не ждёт вечно, поэтому система ощущается отзывчивой — но короткие кванты означают больше переключений контекста, а они стоят реального времени.
# Правило, которое стоит запомнить:
#
# waiting time = (момент завершения - приход) - burst
# turnaround time = момент завершения - приход
#
# Пример из набора «convoy» (P1=6, P2=4, P3=2, P4=1):
#
# FCFS: P1[0..6] P2[6..10] P3[10..12] P4[12..13]
# среднее ожидание = (0 + 5 + 8 + 9) / 4 = 5.5
#
# SJF : P1[0..6] P4[6..7] P3[7..9] P2[9..13]
# среднее ожидание = (0 + 3 + 5 + 8) / 4 = 4.0
#
# SJF выигрывает, потому что короткие работы успевают
# пройти раньше, а не стоят за длинной. Это и есть convoy effect.Практика
Какой алгоритм может бесконечно морить долгую задачу голодом, если короткие продолжают приходить?
Подсказки
- Подумай, какую задачу постоянно обгоняют более короткие.
- Один из этих алгоритмов не даёт новой короткой задаче пролезть вперёд.
12 XP
Сравни в симуляторе ниже FCFS и SJF на одном и том же наборе процессов. Где среднее время ожидания меньше и почему?
Подсказки
- Запусти оба и сравни среднее время ожидания, которое покажет симулятор.
- Спроси себя, задерживает ли долгая задача короткие за собой.
18 XP
Расставь решения планировщика Round-Robin по порядку для P1(4мс), P2(2мс) при кванте 2мс.
Подсказки
- Каждый процесс получает квант, прежде чем его вытеснят.
- Процесс, завершившийся раньше, покидает очередь.
15 XP