Вытесняющее и невытесняющее планирование

Можно ли отобрать процессор у работающего процесса — и почему ответ определяет характер всей системы.

Вытесняющее планирование (preemptive) позволяет ОС отобрать процессор у работающего процесса; невытесняющее (non-preemptive) — нет, процесс работает, пока сам не уступит.

Две философии

В невытесняющем планировании процесс, получивший процессор, держит его до тех пор, пока сам не завершится или не уйдёт в ожидание (например, запросит ввод-вывод). FCFS и классический SJF — невытесняющие.

В вытесняющем планировании ОС может в любой момент (обычно по таймеру или приходу более важного процесса) прервать процесс и передать процессор другому. Round Robin и большинство современных планировщиков — вытесняющие.

Сравнение

Почему важна отзывчивость

Представьте текстовый редактор, который перестаёт реагировать на клавиатуру, пока фоновая проверка орфографии не закончит работу. В невытесняющей системе так и было бы. Вытеснение позволяет ОС регулярно «забирать» процессор у фоновой задачи и отдавать его обработке ввода — интерфейс остаётся живым.

Цена вытеснения

За отзывчивость платят переключениями контекста. Кроме того, вытеснение усложняет синхронизацию: процесс могут прервать прямо посреди изменения общих данных, что создаёт почву для гонок (следующий раздел). Поэтому критические участки приходится защищать.

Многоуровневые очереди с обратной связью

Реальные ОС не используют один алгоритм. Они применяют многоуровневые очереди с обратной связью (MLFQ) — несколько очередей с разными приоритетами и квантами:

• Новый процесс попадает в очередь высокого приоритета с маленьким квантом.
• Если он «съел» весь квант (значит, он вычислительно тяжёлый), его понижают в очередь с большим квантом, но меньшим приоритетом.
• Интерактивные процессы (часто уходят в ожидание ввода) остаются наверху и быстро получают процессор.

Так система автоматически отличает интерактивные задачи от «числодробилок» и обслуживает их по-разному — без необходимости заранее знать длину задач.

Симуляция: вытеснение более важным процессом

Покажем суть вытеснения: процесс работает, но приход высокоприоритетной задачи его прерывает.

# события: (время, имя, приоритет) — меньше число = важнее
arrivals = [(0, "Фон", 5), (3, "ВводКлавиатуры", 1)]
running = None
log = []

for time, name, prio in arrivals:
    if running is None:
        running = (name, prio)
        log.append(f"t={time}: запущен {name} (приоритет {prio})")
    else:
        if prio < running[1]:
            log.append(f"t={time}: пришёл {name} (приоритет {prio}) — "
                       f"ВЫТЕСНЯЕТ {running[0]}")
            running = (name, prio)
        else:
            log.append(f"t={time}: {name} ждёт, {running[0]} важнее")

for line in log:
    print(line)
print(f"Сейчас на процессоре: {running[0]}")

Вывод:

t=0: запущен Фон (приоритет 5)
t=3: пришёл ВводКлавиатуры (приоритет 1) — ВЫТЕСНЯЕТ Фон
Сейчас на процессоре: ВводКлавиатуры

Итог

• Невытесняющее планирование не отбирает процессор — процесс держит его до конца или ожидания.
• Вытесняющее позволяет ОС прервать процесс ради отзывчивости и справедливости.
• Плата за вытеснение — больше переключений и сложнее синхронизация.
• Современные ОС используют MLFQ: несколько очередей, авто-различение интерактивных и тяжёлых задач.