OSDev

Кто-нибудь вплотную сталкивался с вопросами планирования выполнения потоков в многопроцессорных системах (общие идеи, алгоритмы и т.д.)? Я в своей оси уже заложил поддержку многопроцессорности и надеюсь в относительно близком будущем взяться за её фактическую реализацию. Ну а поскольку раньше этим вопросом серьёзно не интересовался, решил начать выискивать информацию по этому вопросу.

Мы когда-то пытались обсуждать этот вопрос, не помню, здесь или на sysbin'е, но видать дело не пошло. Я у себя пока поддержку многопроцессорности так и не сделал. Пока что вношу изменения по мелочам в различные структуры, пробую запускать доп. аппаратные ядра в холостом режиме, не более. Реально нужны алгоритмы планирования, включая синхронизацию страничного кэша и т.п. Если есть какие-то идеи на эту тему, будет интересно обсудить.

А что имеется в виду под "страничным кэшем", что его нужно синхронизировать? TLB, что ли? Если так, то подобные вопросы обсуждать точно не со мной: у АРМов и ИА-32 довольно много технических различий в подобных вещах. Меня-то, собственно, интересуют в первую очередь алгоритмы планирования, почему тему так и назвал -- а они не зависят от особенностей железа.

Под страничным кэшем понимается TLB. Суть проблемы заключается в том, что если обычные кэши L1, L2, L3 и т.д. являются когерентными, то есть синхронизируются аппаратно, то TLB - нет. И любые изменения касающиеся адрессного пространства нужно пробрасывать на другие процессоры вручную. Обычно это делается за счет IPI. То есть поменял страничку адресного протранства, сбросил локальный TLB и сообщил остальным процессорам в системе о необходимости сбросить TLB. В противном случае, два потока одного и того же процесса выполняющиеся на различных процессорах одновременно имеют шанс работать с одной и той же виртуальной памятью (с точки зрения потоков) и в то же время с разной физической памятью.

Планирование на многопроцессорных системах - большая и больная тема. Обычно все сводится к проблеме балансировка нагрузки vs масштабируемость. Есть два основных подхода:
1) Одно общее расписание для всей системы. То есть одна очередь задач. Освободившийся процессор выхватывает следующую задачу из очереди. Балансировка нагрузки стремится к идеальной, масштабируемость к нулю, так как возникает куча вопросов по синхронизации. В эту же телегу бонусом идут вопросы по эффективному использованию кэшей.
2) Каждый процессор имеет свое локальное расписание, глобального расписания как бы нет. Вернее оно есть, но оно рудиментарно. Балансировка нагрузки стремиться к нулю, масштабируемость к идеальной.

Мое лючное ИМХО, нужно пытаться плясать от второго подхода.

Мое ИХМО от первого.
По крайней мере проблем будет минимум. Ловим прерывание тормозим все ядра/процессоры через IPI. Выполняем планирование в одном потоке. Раскидываем по ядрам задачи.
Эффективность правда маленькая.
А со вторым вариантом вопросов много и проблемы блокировки надо решать.

Консистентными. Когерентность это немного другое, оно относится к порядку изменения одинаковой ячейки при одновременной модификации несколькими процами. Обычно изменение происходит по порядковому номеру процессора. В основном это относится к мутексам.


Не вижу особых вопросов по синхронизации. Переназначил потоку идентификатор процессора и всё, ну и пару вспомогательных параметров, как указатель ядерного стека. Впрочем я не пробовал.


А куда плясать? Балансировка она либо есть, либо нет. Тут либо 1) либо 2) без вариантов.

В таком режиме от многозадачности толку мало а может и совсем нет.
Если очередь общая, то как правило всё равно есть свои очереди на процессор, просто эта самая общая очередь является средством перераспределения нагрузки. Планируются потоки. Схема эта реально сложная и сложность возрастает при увеличении количества ядер, но именно такая схема даст наилучшее распределение нагрузки. Если надо сбросить кэш TLB, то по таблицам, которые должны вестись в системе, посылаются IPI на соответствующий процесcор, на котором этот адрес есть в кэше.
Есть альтернатива - процесс (не поток!) привязывается к одному ядру и соответственно все потоки процесса - тоже. В общем - между ядрами планируются процессы (с их потоками). Такая схема проще в реализации и содержит меньшую вероятность необходимости сброса кэша TLB у других процессоров. Эта схема хороша для кластеров, NUMA и т.п. Насколько я понимаю - нечто подобное сделано у DFBSD (с особыми заморочками про vkernel). Минус схемы тоже понятен - с одним большим процессом в системе сделать нормальную паралельную работу сложно.
Это навскидку - я об этом как-то даже пока не задумывался. У меня есть более близкие задачи. Лично мне ближе вторая схема со всеми её ограничениями.

Ну, у меня с тормозами внутри ядра проблем не будет, никаких глобальных блокировок нет. Хотя совершенно очевидно, что, если на двух или большем числе процессоров в одно и то же время будет выполняться код, требующий доступа к одной и той же структуре данных, то им тормозиться всё же придётся -- но это, думается, неизбежно. Моя цель в этом плане состояла в том, чтобы не тормозить тот системный код, который не "завязан" на ресурсы, используемые системным же кодом на другом процессоре. Скажем, если на одном процессоре выполняемый им поток переводится в ожидание (и нужен доступ к спискам потоков), а на другом обрабатывается запуск операции ввода-вывода (которой потоки не нужны совершенно), то они реально будут работать параллельно.

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

Что же касается синхронизации изменений, поддержания когерентности кэшей и т.д., то это вопросы очень важные, но более низкого порядка, так сказать; сейчас же меня интересуют вопросы "стратегического" плана.

Есть предположение, что основная проблема балансировки связана с нелинейностью загрузки процессора по времени, когда ядра заняты "скачками". Если измерение после одного тика таймера показало, что некое ядро загружено на 100%, это не значит, что в следующем тике оно будет так же загружено. Имеет смысл накапливать некую статистику загрузки за 2 или более тиков таймера, чтобы принять адекватное решение.

Ещё имеет смысл использовать адаптивный (или как ещё называют интеллектуальный, smart) планировщик. Вот ZarathustrA описал две основных концепции и задался вопросом выбора. А ведь можно динамически применять то один то другой вид планирования в зависимости от текущей загрузки, и таким образом применять обе концепции. В периоды, когда загрузка системы низкая, то можно применять линейное распределение потоков по второму варианту. И лишь при сильной загрузке системы запускать механизм балансировки по первому варианту. При снижении загрузки нужно опять вернуться к линейному распределению.