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

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

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

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

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

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

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

Сравнение

КритерийНевытесняющееВытесняющее
Отзывчивостьнизкаявысокая
Накладные расходыменьше (реже переключения)больше (чаще переключения)
Справедливостьхуже (можно «зависнуть» за длинным)лучше
Риск гонокнижевыше (процесс прерывают «посреди дела»)
ПримерыFCFS, SJFRR, приоритеты с вытеснением

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

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

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

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

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

Реальные ОС не используют один алгоритм. Они применяют многоуровневые очереди с обратной связью (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: несколько очередей, авто-различение интерактивных и тяжёлых задач.

Проверь себя

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

1Чем вытесняющее планирование отличается от невытесняющего?

2Какой главный плюс вытесняющего планирования?

3Как MLFQ отличает интерактивные процессы от вычислительно тяжёлых?

Следующий урок
13 · Состояние гонки и критическая секция Открыть урок 13
Урок 11: Round Robin и приоритеты