FCFS и SJF

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

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

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

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

Итог

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