Планировщик: кто пойдёт следующим
В статье про многозадачность я оставил вопрос открытым -переключение контекста может прыгнуть к любому потоку, но какой будет выбран? Это решает планировщик, и он, без преувеличения, самая трудно сбалансированная часть всего ядра, потому что ему надо примирить две цели, которые противоречат друг другу.
Две цели, которые противоречат друг другу
Одна цель, это приоритеты, к примеру приём из сети должен идти раньше фоновых часов, иначе пакеты потеряются. Важное вперёд.
Другая цель, это "честность", но часы не должны ждать вечно лишь потому, что всегда найдётся что-то поважнее. Каждый рано или поздно должен получить своё время на процессор или ядро CPU.
Эти две цели вступают в противоречие друг с другом. Только приоритеты ведут к голоданию (starvation), низкоприоритетный поток никогда не получит ход. Только честность (fairness) ведёт к вялой системе, которая больше не реагирует на тебя. Поэтому мой планировщик, это гибрид двух известных миров -классы приоритетов (как у MLFQ - Multilevel Feedback Queue Scheduling) и виртуальное время ради честности (как у CFS в Linux - Completely Fair Scheduler).
Четыре класса приоритетов
На самом верху стоят четыре класса, в строгом порядке:
typedef enum {
SCHED_CLASS_RT = 0, // жёсткое реальное время, строго, FIFO
SCHED_CLASS_INTERACTIVE, // реагирует на тебя: WM, консоль
SCHED_CLASS_NORMAL, // обычные программы
SCHED_CLASS_IDLE, // только если больше ничего нет
} sched_class_t;
- RT - это для жёсткого реального времени, например приём из сети, которому нельзя ждать. Пока RT-поток готов, он исполняется, строго и без обсуждений.
- INTERACTIVE - это для всего, что должно реагировать на пользовательский ввод, оконный менеджер, консоль.
- NORMAL - это обычные программы.
- IDLE - получает ход, только когда вообще ничего не работает на конкретном ядре процессора.
Внутри каждого класса есть ещё восемь ступеней приоритета, называемых "бакетами" (bucket). Так у потока есть класс (грубо) и ступень в нём (точно).
Выбор за постоянное время O(1)
Как планировщик среди, может быть, сотен потоков за доли секунды находит нужного? Битмапами. У каждого CPU есть class_mask (у какого класса вообще есть готовые потоки) и по prio_bitmap на класс (какой бакет (bucket) занят). Одна единственная команда процессора, "найди младший установленный бит" (bsf), за постоянное время даёт необходимую нам информацию. Никакого обхода списков.
Выбор идёт в три ступени:
① RT первым, строго: старший занятый бакет, голова FIFO
if (class_mask & (1 << SCHED_CLASS_RT)) {
prio = bsf32(rt->prio_bitmap);
return rt->buckets[prio].head;
}
② INTERACTIVE + NORMAL: Общий пул-выигрывает меньшая vruntime
③ IDLE - запасной, ничего нет для выполнения
vruntime: честность против голодания
Вторая ступень, это сердце всего и трюк против голодания (starvation). Классы INTERACTIVE и NORMAL я трактую не строго по бакетам, а как один общий пул. Каждый поток в нём несёт виртуальное время - vruntime. Оно измеряет, сколько процессорного времени он уже получил, но по приоритету. Всегда выбирается тот, у кого vruntime меньше.
Хитрость в весе. Когда поток получает миллисекунду реального процессорного времени, его vruntime растёт, но высокоприоритетный поток стареет при этом медленнее низкоприоритетного:
uint64_t delta = now_ns - t->last_start_ns; // сколько он только что работал
t->runtime_total += delta;
// vruntime растёт ВЗВЕШЕННО: выше приоритет->меньше прирост->раньше снова готов
t->vruntime += sched_calc_vruntime_delta(delta, global_prio);
Так важный поток получает процессорное время чаще, потому что его vruntime поднимается медленнее, и он скорее снова оказывается "наименьшим". Но неважный затем неизбежно догоняет, ведь его vruntime стоит на месте, пока он ждёт, и в какой-то момент он становится наименьшим. Никто не голодает (мутный термин для слуха. Но если использовать starvation, то тоже возникают вопросы если не в теме).
То, что эти два класса, это один общий пул, я сделал не сразу. Раньше планировщик строго выбирал старший занятый бакет(bucket) первым, и именно это заставляло важный загрузочный поток голодать: он висел в более низком бакете с наименьшей vruntime и всё равно никогда не получал процессорное время, потому что старший бакет всегда имел приоритет. vruntime-пул разрешил эту проблему.
Страховка: старение (aging)
Даже у vruntime-пула остаётся лазейка- высоковзвешенный поток, который постоянно держит наименьшую vruntime, мог бы "заморить голодом" другого. Против этого есть страховка. Если готовый поток ждёт дольше 100 миллисекунд (впятеро больше целевой задержки), его выдвигают вперёд, что бы ни говорила vruntime. Именно этот случай я однажды видел вживую в сериальном выводе дебагера, сообщением [SCHED-STARVE tid=23 wait_ms=824], и тогда встроил старение (aging).
Приоритет не фиксирован
Особенность-эффективный приоритет потока не жёсткий, планировщик наблюдает за его поведением и подстраивает.
Считаются два сигнала:
int bonus = 0;
if (t->sleep_score > 0) bonus += t->sleep_score / 16; // часто спит-> интерактивный -> +
if (t->cpu_burst_avg > 5ms) bonus -= 2; // пожирает CPU -> −
t->dyn_prio = t->base_prio - bonus; // меньше = важнее
Поток, который часто спит, потому что ждёт ввода или сообщений, опознаётся как интерактивный и получает небольшой бонус, ему ведь надо реагировать живо. Поток, который, наоборот, долго подряд пожирает CPU, опознаётся как вычислитель и слегка понижается. Так интерактивная программа сама всплывает наверх, а прожорливая опускается вниз, и никому не надо настраивать это вручную.
(Ловушка, стоившая мне нервов - приоритет нельзя менять, пока поток висит в очереди, иначе его уберут из неверного бакета, и битмапы станут несогласованными. Результатом была порча runqueue с зависанием при загрузке.)
Квант времени
Сколько потоку позволено работать до вытеснения? Тоже динамически - целевая задержка в 20 миллисекунд, делённая на число готовых потоков, ограниченная диапазоном от 1 до 20 мс.
uint32_t sched_calc_slice(cpu_runqueue_t* rq) {
uint64_t s = SCHED_TARGET_LATENCY_NS / rq->runnable_total; // 20 мс / число
return clamp(s, 1ms, 20ms);
}
Если готовых потоков много, каждому достаётся квант покороче, чтобы всё же каждый получил процессорное время в пределах 20 мс. Если их мало, кванты становятся длиннее, это экономит накладные расходы на переключение (да да, переключение тоже не на халяву).
Через несколько ядер
У каждого CPU своя очередь готовых потоков со своими классами и бакетами. Чтобы ни одно ядро не переполнялось, пока другое бьёт баклуши, балансировщик нагрузки перетаскивает потоки от перегруженного к свободному (work stealing). А если на одном CPU просыпается важный поток, который должен запуститься немедленно, ядро шлёт целевому CPU межпроцессорное прерывание с сигналом перепланироваться (wakeup preemption).
Последняя тонкость, это наследование приоритета против классической ловушки- важный поток ждёт мьютекс (mutex), который держит неважный, а тот не получает процессорное время и косвенно блокирует важного (инверсия приоритета). Решение - поток который держит мьютекс на время наследует приоритет ждущего, чтобы закончить и отпустить его.
Честная часть, она же правда жизни
Почти за каждым абзацем здесь стоят дата и зависание при загрузке. Планировщик возник не за чертёжной доской, он рос месяцами из настоящих ошибок голодания потоков и порчи очередей, и большинство из них всплывали лишь тогда, когда подключались два ядра: счётчики времени per-CPU расходились и переполняли vruntime, двойные пробуждения портили бакеты, RT-потоки монополизировали оба ядра и морили загрузку. На одном ядре планировщик сегодня работает спокойно ипочти стабильно. На двух я ещё дорабатываю напильником, и это, как я уже говорил в первой части, одна из многих больших открытых строек. Еще один момент, это то, что использование aging говорит, что я что то не додумал в планировщике. Потому что это - костыль. Буду искать, думать, исправлять.
◀ Предыдущая статья Содержание Следующая статья ▶
*Система не стоит на месте, поэтому в дальнейшем тексты могут не совпадать с реальным положением.