Планирование CPU

EuroSys 2016, Лондон. Lozi, Lepers и команда EPFL/UBC публикуют статью «The Linux Scheduler: A Decade of Wasted Cores». Они находят четыре бага в CFS, дефолтном планировщике Linux с 2007 года. Симптом: ядра простаивают секундами, пока готовые потоки ждут в очереди. Последствия: kernel make медленнее на 13%, TPC-H проседает на 14-23%, sync-heavy задачи теряют производительность в разы. Десятилетие production-серверов недополучало CPU, и никто не замечал, потому что инвариант «готовый поток на свободном ядре» нигде не проверялся. Планировщик OS не теоретическая дисциплина, это деньги.

• **Android**: CFS (Completely Fair Scheduler) с приоритетами - UI-потоки получают CPU первыми, иначе анимации лагают
• **Nginx**: Round Robin между worker-процессами обеспечивает равномерную нагрузку при тысячах соединений
• **Linux kernel**: Multilevel queue - real-time (SCHED_FIFO), normal (CFS), idle (SCHED_IDLE)
• **AWS Lambda**: планировщик определяет, какая функция получает CPU при burst трафика

Цели урока

• Сравнить FCFS, SJF, RR, Priority, MLFQ, CFS по latency vs throughput vs fairness
• Прорисовать Gantt chart для набора задач при разных дисциплинах
• Понимать метрики: turnaround time, waiting time, response time, jitter
• Объяснить устройство Linux CFS: vruntime, red-black tree, weight по nice value
• Знать когда нужен SCHED_FIFO/SCHED_DEADLINE и trade-offs real-time планирования

История планирования: от batch до CFS

В 1961 году Фернандо Корбато представил Compatible Time-Sharing System (CTSS) в MIT - первую систему с разделением времени между пользователями. До этого компьютеры работали в batch-режиме: программы запускались по одной, без переключения. CTSS впервые реализовала Round Robin на уровне пользователей. В 1964 году Multics (прямой предок Unix) расширил концепцию многоуровневыми очередями. Linux Completely Fair Scheduler, используемый сегодня на миллиардах устройств, вырос из этих идей 60-летней давности.

Критерии планирования

**Критерии планирования** определяют, насколько эффективно планировщик распределяет процессорное время. Разные системы оптимизируют разные метрики.

**Конфликт метрик:** Для интерактивных систем критичны Response Time и Waiting Time. Для batch-систем важнее Throughput и Turnaround Time. Нельзя оптимизировать всё одновременно - выбор алгоритма зависит от типа нагрузки.

FCFS (First-Come, First-Served)

**FCFS (First-Come, First-Served)** - самый простой алгоритм планирования. Процессы выполняются в порядке поступления в очередь готовности, как очередь в магазине.

**Convoy Effect:** Если первым пришёл длинный процесс, все короткие ждут его завершения. Как машины за медленным грузовиком. Преимущества FCFS: простота, честность, нет overhead. Недостатки: convoy effect, плохо для интерактивных систем.

SJF (Shortest Job First)

**SJF (Shortest Job First)** - алгоритм, который выбирает процесс с минимальным временем выполнения. Математически доказано: SJF минимизирует среднее время ожидания.

**Проблема SJF: Starvation.** Длинные процессы могут ждать бесконечно если постоянно приходят короткие. **Решение: Aging** - постепенно повышать приоритет долго ждущих процессов. **Другая проблема:** на практике невозможно знать burst time заранее - используют экспоненциальное скользящее среднее прошлых выполнений.

Round Robin (RR)

**Round Robin (RR)** - алгоритм с вытеснением по времени. Каждый процесс получает небольшой квант времени (time quantum), после чего вытесняется и отправляется в конец очереди.

**Quantum имеет критическое значение.** Слишком большой quantum - вырождается в FCFS. Слишком малый - overhead от context switch поглощает CPU (при quantum=1мс и switch=1мс -> 50% времени тратится впустую). Правило: 80% процессов должны завершаться за один quantum.

Priority Scheduling

**Priority Scheduling** - каждому процессу назначается приоритет. CPU выделяется процессу с наивысшим приоритетом. Это основа для большинства современных планировщиков.

**Starvation и Aging:** Низкоприоритетные процессы могут ждать бесконечно. Aging - решение: каждые N секунд ожидания автоматически повышать приоритет. В Linux CFS использует 'виртуальное время' (vruntime) - процессы с меньшим vruntime получают CPU первыми, что математически гарантирует справедливость без явного aging.

**Priority Inversion:** Высокоприоритетный поток ждёт ресурс, удерживаемый низкоприоритетным. Именно это едва не уничтожило Mars Rover в 2003 году. Решение - Priority Inheritance Protocol: низкоприоритетный поток временно наследует высокий приоритет заблокированного.

Ключевые идеи

• **Критерии оценки:** CPU utilization, Throughput, Turnaround/Waiting/Response Time - разные алгоритмы оптимизируют разные метрики
• **FCFS**: прост, но convoy effect делает его непригодным для интерактивных систем
• **SJF**: оптимален теоретически по Waiting Time, но требует предсказания burst time и вызывает starvation
• **Round Robin**: справедлив, лучший Response Time, но overhead от context switch при малом quantum
• **Priority Scheduling**: основа реальных ОС - Aging решает starvation, многоуровневые очереди разделяют real-time и batch

Вопросы для размышления

• Почему Priority Inversion на Mars Rover не был обнаружен на Земле до запуска - какие тесты нужны для планировщиков?
• Какой алгоритм планирования лучше для медицинской системы жизнеобеспечения - RR или Priority? Почему нельзя допускать starvation?
• Linux CFS использует 'виртуальное время' вместо квантов - как это решает проблему несправедливости классического RR?

Связанные уроки

• os-02-processes
• os-03-threads
• os-05-sync
• os-06-deadlocks
• ds-04-queues
• rt-24