Кто следующий: EEVDF в nos

Есть одна ситуация, по которой судят о планировщике. Задачу только что разбудили — скажем, закончилось чтение с диска, которого она ждала, — а её процессор занят задачами, которые никогда не останавливаются, чтобы чего-то подождать. Сколько пройдёт времени, прежде чем разбуженная задача начнёт выполняться?

До 25 октября ответ в nos был такой: по тику за каждую занятую задачу, которая стоит в очереди перед ней. За двумя — 8 мс, за четырьмя — 33 мс. И процессор делился неровно: четыре задачи, которым он был нужен целиком, получали 8, 25, 33 и 33 процента. Теперь то же пробуждение занимает микросекунды, а процессор делится по весам: четыре равные задачи получают по 25 процентов с точностью до десятой доли процента. Новый планировщик — EEVDF, та же политика, по которой Linux с версии 6.6 планирует обычные задачи.

Он появился в три шага: измерить, перестроить очередь, сменить политику. Ниже — все три шага, две ошибки, найденные по дороге, и почему более интересную из них теперь нельзя написать.

Старый планировщик: карусель по всем задачам#

У каждого процессора была очередь, а в очереди — один список: все задачи, которые живут на этом процессоре. Готовые к выполнению, заблокированные на чём-то, спящие до срока и idle-задача процессора лежали в нём вперемешку. Чтобы решить, кто выполняется следующим, планировщик проходил список с головы, пропускал всё, что выполняться не может, и брал первую задачу, которая может. Вытесненная задача уходила в хвост. Это и есть карусель (round robin). Вот этот обход в том виде, в каком он был (sched.cpp на 8d5df60), без комментариев:

for (auto currEntry = TaskList.Flink; currEntry != &TaskList; currEntry = currEntry->Flink)
{
    Task* cand = CONTAINING_RECORD(currEntry, Task, ListEntry);
    if (cand == curr)
    {
        cand->ListEntry.Remove();
        TaskList.InsertTail(&cand->ListEntry);
        break;
    }
    if (cand->PreemptDisableCounter.Get() != 0)
        continue;
    if (cand->IsBlocked() && !SleepIsOver(cand, &now))
        continue;
    if (cand->IsIdle())
    {
        if (idle == nullptr)
            idle = cand;
        continue;
    }
    next = cand;
    break;
}

С ним было четыре беды.

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

И ничего из этого никто не измерял.

Шаг 0: сначала измерить#

В ядре есть сэмплирующий профилировщик profile, но внутрь планировщика он не заглядывает там, где ему нечем сэмплировать без NMI: на arm64 и под эмуляцией TCG в QEMU. А сколько разбуженная задача ждёт процессор, не считал вообще никто, хотя именно это число хороший планировщик и должен улучшить. Поэтому первый коммит (7a896aa) добавил счётчики в очередь каждого процессора: сколько ждали разбуженные задачи, сколько ждали вытесненные, прежде чем снова выполниться, сколько стоило решение и скольких задач оно коснулось, и сколько задач было готово каждый раз, когда таймер процессора заглядывал в очередь. Ожидание разбуженной задачи начинается в Unblock(), который её разбудил и поставил отметку времени, или в момент срока спящей задачи, а заканчивается, когда задача начинает выполняться. Ожидания складываются в корзины по степеням двойки микросекунд, поэтому перцентиль печатается как граница корзины, например <256us.

Счётчики пишет только процессор этой очереди, под блокировкой очереди, которую он и так держит. В первой версии счётчики были атомарными, а на x86 атомарная запись — это lock xchg, инструкция с блокировкой, и таких было пять на каждое решение. Хватает обычных relaxed-записей (da9c429): писатель один, а читатель на другом процессоре видит значение до обновления или после, но никогда не записанное наполовину.

Команда шелла sched [ms] печатает окно этих счётчиков, по строке на процессор. sched probe разыгрывает ситуацию из начала поста. Спиннеры — это задачи, привязанные к одному процессору, которые никогда его не уступают. Рядом с ними, на том же процессоре, ждущая задача спит на событии. А задача самого шелла на другом процессоре будит её по одному замеру за раз и засекает, через сколько та начнёт выполняться. Вот карусель под HVF, гипервизором Apple, на четырёх vCPU. EX44, 20-процессорный сервер на Intel, дал те же числа.

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

Шаг 1: очередь только из тех, кто может выполняться#

Второй шаг (1bd0b8d) политику не трогал — ходы по-прежнему шли по кругу, — но перестроил очередь вокруг того, что нужно решению:

• список готовых содержит только задачи, которые могут выполняться. Заблокировавшаяся задача уходит из него до пробуждения, так что решение никогда не перешагивает через задачу, которая выполняться не может;
• список спящих содержит задачи, которые спят до срока, по возрастанию срока. Одноразовый таймер процессора заведён на его голову, и каждое решение смотрит только на голову;
• у idle-задачи своё место, отдельно от обоих списков;
• стек пробуждений содержит задачи, разбуженные с прошлого решения.

Раньше блокировка была одним битом во флагах задачи. Block() его ставил, Unblock() снимал, а задача в любом случае оставалась в списке, и каждый обход через неё перешагивал. Теперь Block() и Unblock() — это операции compare-and-swap над одним словом задачи, RunState, которое говорит, где задача находится относительно своей очереди:

Вот сторона будящего (task.cpp):

void Task::Unblock()
{
    long was = RunState.Cmpxchg(RunQueued, RunBlocking);
    if (was != RunSleeping)
        return;

    if (RunState.Cmpxchg(RunWaking, RunSleeping) != RunSleeping)
        return;

    WakeTime.Set((long)GetBootTime().GetValue());
    TaskQueue->PushWake(this);
}

Если задача ещё в Blocking на своём процессоре, первый compare-and-swap снова делает её Queued, и Schedule(), который собирался её снять, видит, что она готова, и оставляет её. Если она в Sleeping, второй делает её Waking. Из двух будящих, или из будящего и срока спящей задачи, этот шаг выигрывает ровно один, и только победитель кладёт задачу в стек пробуждений её очереди.

Стек пробуждений — lock-free стек, в который кто угодно может класть задачи из любого контекста, обработчиков прерываний в том числе, а опустошает его только свой процессор, и сразу целиком, на следующем решении. Поскольку по одному элементу из него никогда ничего не снимают, проблемы ABA у него нет. Это классическая ловушка lock-free стеков: элемент снимают и кладут обратно между тем, как другой процессор прочитал вершину, и его compare-and-swap.

Есть тонкость с порядком памяти. Будящий сначала публикует работу, например ставит флаг «есть что делать», и только потом смотрит на состояние задачи. Спящий делает зеркально: сначала поднимает своё состояние, потом проверяет, нет ли работы. Взгляд будящего — всегда операция с блокировкой, даже когда делать нечего, ведь неудачный compare-and-swap — тоже такая операция. Простое чтение позволило бы arm64 выполнить этот взгляд раньше, чем опубликованная работа станет видна другому процессору, и спящий мог бы проверить, ничего не найти и уснуть навсегда, хотя работа его ждёт. На x86 простое чтение было бы безопасным. На arm64 — нет.

Решение стало немного дешевле и намного проще. Если мерить рядом под HVF в покое, оно стоит 660 нс против 740 у карусели и касается в среднем 1,1 задачи там, где старый обход смотрел на 2,6. На EX44 оно подешевело с 1,5 мкс до 1,2–1,3.

Загрузка, которая ждала тридцать секунд#

Idle-задача каждого процессора — это ещё и то, что выполняет код его запуска, а на загрузочном процессоре это сама загрузка вместе с самотестами. Старый планировщик считал idle-задачу последним средством, что бы она ни выполняла. В новой очереди это превратилось в настоящую ошибку. Самотест кольца запускает производителя, привязанного к загрузочному процессору, и тот в цикле ждёт потребителя, которого загрузка ещё не запустила. Производитель забирал процессор на следующем тике и не отдавал, а загрузка стояла, пока он не сдавался через 30 секунд. Примерно раз на несколько сотен загрузок под HVF самотест падал с сообщением, что из ста тысяч значений вышло два.

Нашли это так: загружались в цикле, пока одна из загрузок не встала, потом подключили lldb к GDB-заглушке QEMU и спросили, где каждый процессор. Производитель выполнялся, процессоры с 1 по 3 стояли остановленные, а потребителя не было ни в одной очереди. Старый обход прятал тот же изъян из-за случайного порядка в списке. Теперь idle-задача — последнее средство, только пока она простаивает внутри Cpu::Idle(), а выполняя загрузку, она ходит в свою очередь, как любая другая задача. Это правило держит самотест TestIdleTakesTurns: рядом с задачей, привязанной к загрузочному процессору, которая только и делает, что уступает его, сон загрузки на 1 мс длится 1 мс, а по старому правилу длился 2000. С тех пор четыреста загрузок подряд ни разу не встали.

Шторм пробуждений#

Потерянное пробуждение — худшая из ошибок планировщика: задача спит вечно, и нет паники, которая бы об этом сказала. Поэтому ещё один самотест, TestWakeStorm, будит задачи во всех окнах, которые оставляют четыре состояния. Кольцо задач, по две на процессор, каждая привязана к своему, передаёт по кругу маркер, так что каждая передача — это пробуждение на другом процессоре. У половины ожиданий есть срок, время от времени задача засыпает, чтобы срок соревновался с сигналом, который за ней идёт, а на каждом из остальных процессоров какая-нибудь задача всё время уступает процессор, чтобы списки готовых не пустели. Если маркер стоит две секунды, загрузка падает и называет задачу, которой маркер был отправлен, и где эта задача сейчас. Контрольный прогон, который терял одно пробуждение из 1500, упал на 1633-й передаче. На EX44 3008 передач между 32 задачами на 20 процессорах занимают 60 мс.

Шаг 2: EEVDF#

EEVDF расшифровывается как Earliest Eligible Virtual Deadline First: первой выполняется допустимая задача с самым ранним виртуальным дедлайном. Её описали Ион Стойка и Хуссейн Абдель-Вахаб в 1995 году, а с Linux 6.6 она решает, кто выполняется среди обычных задач Linux. В nos это eevdf.cpp, несколько сотен строк, которые ничего не знают о задачах, блокировках и процессорах, только о сущностях и очереди, в которой они стоят (0ce9d2f). Устроено это так:

• У каждой задачи есть вес, он берётся из её значения nice, от -20 до 19. Таблица линуксовая: 1024 при nice 0, и каждый шаг примерно в 1,25 раза больше следующего, так что разница в один nice — это около десяти процентов процессора между двумя задачами, которым он нужен целиком.
• У каждой задачи есть виртуальное время выполнения — полученное ею процессорное время в масштабе: наносекунда на процессоре добавляет к нему 1024/вес виртуальных наносекунд, так что у более тяжёлой задачи оно растёт медленнее.
• V — взвешенное среднее виртуальных времён всех задач в очереди: там, где была бы каждая из них, получи она ровно свою долю.
• Лаг задачи — это V минус её виртуальное время, то есть сколько ей должны. Задача допустима (eligible), пока её лаг не отрицателен.
• Каждая задача просит у процессора квант за раз, по умолчанию 3 мс, а её виртуальный дедлайн — это точка, где окажется её виртуальное время, когда она этот квант получит.

Следующей выполняется допустимая задача с самым ранним дедлайном. Две ручки делают разное. Вес решает, сколько процессора задача получит. Квант решает, как скоро после того, как она стала допустимой, она его получит: короткий квант — это ранний дедлайн, то есть меньшая задержка, а не большая доля.

Почему разбуженная задача теперь выполняется сразу#

Ответ на случай с пробуждением следует из лага. Задача, которая засыпает, уносит свой лаг с собой и приносит обратно, когда просыпается. Ждущая задача из пробы всю жизнь ждёт, пока работают спиннеры, поэтому ей всегда что-то должны. Когда она просыпается, она допустима, её дедлайн самый ранний в очереди, и IPI, который за ней приходит, тут же отдаёт ей процессор. Спиннер никогда не спит, поэтому и в пробуждение ему принести нечего.

Чтобы это работало, лаг должен пережить момент возвращения в очередь. Вступление в очередь сдвигает V, потому что собственный вес задачи теперь входит в среднее, и уже одно это отняло бы часть принесённого лага. Поэтому, как это делает place_entity в Linux, лаг сначала увеличивается в (W + w) / W раз, где W — вес, который уже стоит в очереди, а w — вес самой задачи:

lag = Stdlib::Max(-se->LagLimit(), Stdlib::Min(se->LagLimit(), lag));
u64 load = Stdlib::Min(sums.Load, (u64)1 << 24);
lag = (lag * (s64)(load + se->Weight)) / (s64)load;
v = average - (u64)lag;

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

Без плавающей точки#

Ядро держит SSE и x87 выключенными, потому что не сохраняет их регистры при переключении контекста, и плавающая точка превратилась бы в медленную программную эмуляцию. Здесь всё в целых числах. Обратная величина веса хранится с фиксированной точкой, (1024 << 32) / вес, а допустимость проверяется без деления, так же как в Linux: если отсчитывать от наименьшего виртуального времени в очереди, задача допустима, когда её расстояние, умноженное на суммарный вес очереди, не больше взвешенной суммы расстояний всех задач. Произведениям нужно 128 бит:

bool EevdfQueue::Eligible(const SchedEntity* se, const Sums& sums)
{
    u64 span = Stdlib::Min(se->VRuntime - sums.Base, MaxSpan);
    return (unsigned __int128)span * sums.Load <= (unsigned __int128)sums.Weighted;
}

Виртуальные времена всегда сравниваются только через разность, поэтому переполнение им не страшно.

O(n), и это намеренно#

Исходная идея была — решение за O(1). Точному EEVDF нужна допустимая задача с самым ранним дедлайном, и чтобы быстро её находить, нужна упорядоченная структура: Linux держит дополненное красно-чёрное дерево, это O(log n). O(1) означало бы корзины виртуального времени и приближение. nos не делает ни того, ни другого. Каждое решение проходит список готовых и считает V и все допустимости с нуля. Это O(n) по задачам, которые могут выполняться на этом процессоре, и между решениями не хранится ничего, что могло бы разойтись с действительностью.

Почему это правильный размен, говорят счётчики из шага 0. В списке готовых только те задачи, которые могут выполняться, а их мало: на простаивающем EX44 таймер находит в среднем 0,2 готовой задачи на процессор, а самое большее с загрузки — пять. Под HVF с восемью отправителями netload процессор 0 находил две готовые задачи и больше в 58% своих взглядов. На таких коротких списках дерево стоило бы больше, чем экономило бы. Корзины подождут, пока измерение не покажет процессор с множеством готовых задач.

Остальное#

• На прерывании выполняющаяся задача — один из кандидатов и сохраняет процессор, если только у другой допустимой задачи дедлайн не наступает раньше. У задачи, которая уступает процессор, дедлайн сдвигается как минимум на квант дальше V. Сдвиг ограничен, так что задача, которая уступает без конца, не может без конца отодвигать свой дедлайн.
• Одноразовый таймер процессора заводится на конец кванта выполняющейся задачи, так что квант заканчивается, когда наступает дедлайн, а не на следующем тике. Но только пока ждёт кто-то ещё: задача, которая одна на своём процессоре, закончила бы квант, ничего не решив, а vCPU гостя на собственном ядре ради этого выходил бы из гостя каждые 3 мс.
• Idle-задача учитывается, только пока выполняет что-то кроме простоя, например загрузку: она вступает в очередь, когда перестаёт простаивать, и уходит, сохраняя лаг, когда снова начинает.
• sched queue [cpu] печатает, что EEVDF знает о каждой задаче на процессоре: её nice, квант, лаг, дедлайн и допустима ли она. sched nice <pid> <n> и sched slice <pid> <us> меняют вес и квант задачи.

Ошибка, которую больше нельзя написать#

В первой версии EEVDF в планировщике была ошибка порядка. Очередь получала задачу на процессоре параметром. Выбрав следующую задачу, планировщик сразу снимал её со списка готовых. Затем текущая задача засыпала, и её лаг считался от V. Но в этот момент следующая задача не была ни в списке, ни на процессоре, поэтому V её не учитывал.

Рядом с одним спиннером такой V был виртуальным временем самой засыпающей задачи, и она засыпала с нулевым лагом: ей ничего не были должны, каждый раз. При каждом пробуждении ей приходилось ждать, пока у спиннера кончится остаток кванта, вплоть до целых 3 мс, а рядом с двумя спиннерами пробуждение занимало несколько микросекунд, потому что там V всё ещё учитывал второго. Эта инверсия и была подсказкой. Строка, добавленная в sched probe, чтобы печатать лаг, с которым проснулась ждущая задача, подтвердила: ноль, рядом с одним спиннером, каждый раз.

Первое исправление перенесло снятие со списка на после засыпания и оставило комментарий, почему порядок важен. Правила самого проекта просят большего: из двух решений выбирать то, где ошибку нельзя написать, а не то, где комментарий просит её не писать. Поэтому теперь задачей на процессоре владеет очередь (eevdf.cpp). Задача в очереди либо в списке, либо текущая, в V она учитывается в обоих случаях, а ни там ни там не бывает никогда. Перемещают её пять вызовов — Join, JoinCurrent, Leave, PutBack и Take, — и Take отказывает через BugOn, панику ядра с номером строки, пока текущая задача ещё есть:

void EevdfQueue::Leave(SchedEntity* se)
{
    /* On the queue: current, or on the list */
    BugOn(se != Curr && se->Entry.IsEmpty());

    /* V with se in it */
    s64 lag = (s64)(V() - se->VRuntime);
    s64 limit = se->LagLimit();
    se->VLag = Stdlib::Max(-limit, Stdlib::Min(limit, lag));

    if (se == Curr)
    {
        Curr = nullptr;
        return;
    }
    se->Entry.RemoveInit();
    Count--;
}

void EevdfQueue::Take(SchedEntity* se)
{
    BugOn(Curr != nullptr || se->Entry.IsEmpty());

    se->Entry.RemoveInit();
    Count--;
    Curr = se;
}

У решения остаётся один порядок: выбрать следующую задачу, пока прежняя ещё текущая, затем прежняя засыпает или возвращается в список, и только после этого следующая берётся на процессор.

Тест, который проходил с ошибкой внутри#

Каждая загрузка запускает TestEevdf на процессоре, отличном от загрузочного (test.cpp). Пробуждение рядом с одним спиннером и рядом с двумя должно по медиане занимать меньше половины миллисекунды и меньше миллисекунды, а спиннер с nice 0 должен получать в 2,4–3,9 раза больше процессора, чем спиннер с nice 5. Веса говорят 3,06.

Чтобы убедиться, что тест поймает ошибку, её вернули на место. Тест прошёл: 153 мкс, с запасом под границей. Он будил ждущую задачу в фиксированном ритме — миллисекунда опроса и пауза 2 мс — против кванта в 3 мс, и пробуждения устоялись прямо перед концом кванта, где дождаться «остатка кванта» почти ничего не стоит. Теперь между сигналами тест ждёт случайную часть кванта, из фиксированного зерна:

        /* xorshift64 */
        x ^= x << 13;
        x ^= x >> 7;
        x ^= x << 17;
        Sleep(EevdfGapNs + (ulong)(x % SchedEntity::DefaultSliceNs));

С возвращённой ошибкой медиана — 1256 мкс, и загрузка падает. Без неё пробуждение занимает 4–8 мкс под HVF и 18–26 мкс под TCG, а доля выходит 2,9–3,1. Тест не доказан, пока не провалил тот прогон, ради которого существует.

У очереди есть и своя цель в C++-фаззере, eevdf (fuzz/cpp/targets/eevdf.cpp). Она собирает очередь для хоста и гоняет её в том порядке, в каком это делает планировщик, с задачами случайных весов и квантов, которые выполняются, засыпают, просыпаются, уступают процессор, уезжают и возвращаются. Каждый шаг сверяется с моделью, которая считает всё с нуля в 128 битах: выбранная задача допустима, и ни у одной допустимой дедлайн не раньше; вернувшаяся задача приходит с тем лагом, с которым ушла; уходящая уносит тот лаг, который даёт ей V; выполнившейся задаче начислено ровно то, что говорит её вес; и каждая задача в очереди либо в списке, либо текущая. Копия Leave, которая считала V без уходящей задачи, упала на первом же входе.

Проверка изменения на неопределённое поведение нашла ещё и гонку данных. Установка nice или кванта задачи читала указатель на её очередь под одной только блокировкой очереди, а при разборе очереди этот указатель записывался под одной только блокировкой задачи. Теперь обе функции берут обе блокировки, в том же порядке, в каком их берёт планировщик.

Числа#

sched probe под HVF на четырёх vCPU, на той же машине, что и таблица карусели выше:

На собственном железе EX44, на одном из производительных ядер, пробуждение рядом с одним, двумя и четырьмя спиннерами ждёт по медиане меньше 2 мкс, на 99-м перцентиле — меньше 64 мкс, а доли выходят 998; 498 и 499; и 250, 249, 249 и 249 промилле. TestEevdf при загрузке там же, на энергоэффективном ядре, намеряет 1 мкс рядом с одним спиннером и рядом с двумя и 3,0 для доли. За решения EEVDF всё же платит: в каждом из них V и все допустимости считаются с нуля от двух до четырёх раз. На EX44 в покое решение стоит 1,2–1,6 мкс на каждом процессоре, примерно как 1,5 мкс у карусели; под HVF, если мерить рядом, — 1,0 мкс против 0,74 у карусели. Блочный слой перемены не замечает: случайное чтение блоков по 4 КиБ с NVMe идёт со скоростью 26 768 IOPS при одном запросе в полёте (26 788 до того) и 180 610 при восьми (178 913). Тест ожидания на простаивающем процессоре, который существует потому, что такое ожидание однажды стоило целого тика, по-прежнему намеряет 22 мкс.

Самое долгое ожидание в каждом прогоне пробы там — 5–7 мс. Оно бывает и вовсе без спиннеров, и у карусели оно было тоже, так что очередь тут ни при чём.

Что осталось#

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