FCFS и SJF

~4 минуты · 2 примера · 3 вопроса

Два простых алгоритма планирования и наглядная демонстрация «эффекта конвоя».

FCFS (First-Come, First-Served) обслуживает процессы строго в порядке прихода; SJF (Shortest Job First) выбирает первым процесс с наименьшим временем выполнения.

FCFS: первым пришёл — первым обслужен

Самый простой алгоритм: процессы выполняются в порядке их прихода, как очередь в магазине. Он невытесняющий — начатый процесс работает до конца, его не прерывают.

Плюс — честность и простота. Минус — эффект конвоя (convoy effect): если первым пришёл «тяжёлый» процесс, все короткие застрянут за ним. Один человек с полной тележкой задерживает всю очередь.

# (имя, время выполнения), все пришли в момент 0
procs = [("P1", 24), ("P2", 3), ("P3", 3)]

t = 0
total_wait = 0
for name, burst in procs:
    wait = t
    total_wait += wait
    t += burst
    print(f"{name}: ожидание={wait}, завершение={t}")

print(f"Среднее ожидание (FCFS): {total_wait/len(procs):.2f}")
Ожидаемый вывод
P1: ожидание=0, завершение=24
P2: ожидание=24, завершение=27
P3: ожидание=27, завершение=30
Среднее ожидание (FCFS): 17.00

Короткие P2 и P3 ждали по 24+ единицы из-за «тяжёлого» P1. Среднее ожидание — целых 17.

SJF: кратчайшая задача первой

Идея: пускать первыми короткие процессы. Тогда они быстро освобождают процессор, и среднее ожидание падает. Это доказуемо оптимальный алгоритм по среднему времени ожидания (если все процессы доступны сразу).

Возьмём те же процессы и отсортируем по длине. Сравните среднее ожидание с FCFS.

procs = [("P1", 6), ("P2", 8), ("P3", 7), ("P4", 3)]

# сортируем по времени выполнения — короткие первыми
order = sorted(procs, key=lambda p: p[1])
print("Порядок выполнения:", " -> ".join(name for name, _ in order))

t = 0
total_wait = 0
for name, burst in order:
    wait = t
    total_wait += wait
    t += burst
    print(f"{name}: burst={burst}, ожидание={wait}")

print(f"Среднее ожидание (SJF): {total_wait/len(procs):.2f}")
Ожидаемый вывод
Порядок выполнения: P4 -> P1 -> P3 -> P2
P4: burst=3, ожидание=0
P1: burst=6, ожидание=3
P3: burst=7, ожидание=9
P2: burst=8, ожидание=16
Среднее ожидание (SJF): 7.00

Сравнение FCFS и SJF

КритерийFCFSSJF
Среднее ожиданиеможет быть большим (эффект конвоя)минимальное (оптимально)
Простотаочень простойнужно знать длину задач
Справедливостьчестный по порядкудлинные задачи могут «голодать»
Типневытесняющийобычно невытесняющий

Главная проблема SJF

У SJF две беды. Первая — откуда заранее знать длину процесса? На практике её приходится прогнозировать по прошлому поведению. Вторая — голодание (starvation): если короткие процессы приходят непрерывно, длинный может не дождаться процессора никогда. Эти проблемы решают другие алгоритмы — Round Robin и приоритеты со старением, о которых дальше.

Итог

  • FCFS обслуживает в порядке прихода — просто, но страдает от эффекта конвоя.
  • SJF пускает короткие процессы первыми и даёт минимальное среднее ожидание.
  • В нашем примере SJF дал среднее ожидание 7.00 — заметно лучше FCFS.
  • Минус SJF: нужно знать (прогнозировать) длину задач и есть риск голодания длинных.
  • Оба алгоритма обычно невытесняющие.

Проверь себя

Три вопроса по уроку. Ответы никуда не идут — это для тебя.

1Что такое «эффект конвоя» в FCFS?

2Почему SJF даёт минимальное среднее время ожидания?

3Какая проблема характерна для SJF?