pavia писал(а):
Мое ИХМО от первого.
По крайней мере проблем будет минимум. Ловим прерывание тормозим все ядра/процессоры через IPI. Выполняем планирование в одном потоке. Раскидываем по ядрам задачи.
Эффективность правда маленькая.
А со вторым вариантом вопросов много и проблемы блокировки надо решать.
Дело хозяйское. Первый вариант дейтвительно проще в реализации, но при росте количества ядер его эффективность стремиться к нулю, так как накладные расходы на планирование будут расти линейно, если не квадратично.
Himik писал(а):
Консистентными. Когерентность это немного другое, оно относится к порядку изменения одинаковой ячейки при одновременной модификации несколькими процами. Обычно изменение происходит по порядковому номеру процессора. В основном это относится к мутексам.
Wikipedia по поводу терминологии говорит следующее:
In computing, cache coherence (also cache coherency) refers to the consistency of data stored in local caches of a shared resource.
Когерентность кэша (англ. cache coherence) — свойство кэшей, означающее целостность данных, хранящихся в локальных кэшах для разделяемого ресурса.
Соответственно под когерентностью кэша понимают механизм обеспечения целостности данных в памяти. Механизм реализуется за счет того, что одна и та же строка памяти может находиться ТОЛЬКО в одном кэше в момент времени. На практике реализуется за счет специального протокола работы системной шины, согласно которому ВСЕ устройства обладающие кэшем используют так называемый модуль слежения (Snooping Agent) который вычитывает ВСЕ транзакции обращения к памяти идущие по системной шине и блокирует транзакцию, если обнаруживает, что запрашиваемая строка памяти уже закэширована в подконтрольном агенту кэше. За этим следует сброс запрашиваемой строки из кэша в память, после чего транзакция разблокируется и данная строка переходит в другой кэш. В результате становится невозможной коллизия, при которой два процессора ОДНОВРЕМЕННО изменили одну и ту же область памяти.
Я полагаю, что я верно использовал термин.
Повторюсь. TLB не когерентен. Соответственно, целостность его содержимого необходимо поддерживать программно.
Himik писал(а):
Не вижу особых вопросов по синхронизации. Переназначил потоку идентификатор процессора и всё, ну и пару вспомогательных параметров, как указатель ядерного стека. Впрочем я не пробовал.
Проблема в том, что у нас единое расписание и единый алгоритм планирования использующий кучу структур данных. Чтобы все это работало корректно, все структуры данных должны оставаться целостными. По этой причине они должны быть защищены блокировками (например спинлоками). При росте количества ядер, с одной стороны возрастает интенсивность зарпросов на перепланирование (банально больше задач блокируются по тем или иным причинам в единицу времени). И с другой стороны процессоры ожидающие перепланирования простаивают большее время ожидая входа в критическую секцию планировщика. Причем заметьте, что они простаивают в холостом цикле, ничего не делая (кроме может быть обработки прерываний), так как чтобы что-нибудь делать они должны получить план от планировщика.
Himik писал(а):
А куда плясать? Балансировка она либо есть, либо нет. Тут либо 1) либо 2) без вариантов.
Плясать в сторону гибридного варианта, то есть совмещения приятного с полезным. По-крайней мере Linux пляшет в этом ритме. Более чем уверен, что большинство остальных операционных систем inductrial quality тоже выбрали этот стиль танца. Вопрос в том, что научиться лучше танцевать и как это сделать.
D-S писал(а):
D-S
В целом поддерживаю ваш ход мыслей. За исключением того, что первая схема в реализации все-таки проще второй. Я бы сказал - топорнее. Но вторая, более элегантная, так как она более эффективная и масштабируемая. Привязка процесса к процессору в западной литературе называется Affinity scheduling. Основной целью такого подхода обычно декларируют увеличение общей производительности системы за счет использования "разогретых" кэшей. Подход опирается на предположение, что если процесс уже выполнялся недавно на данном процессоре, то существует вероятность, что данные необходимые для дальнейшей работы процесса могут все еще быть в кэше процессора. А это значит, что экономится значительное количество тактов, которые бы процессоры пришлось бы потратить, чтобы подтянуть эти данные из памяти.
Himik писал(а):
Есть предположение, что основная проблема балансировки связана с нелинейностью загрузки процессора по времени, когда ядра заняты "скачками". Если измерение после одного тика таймера показало, что некое ядро загружено на 100%, это не значит, что в следующем тике оно будет так же загружено. Имеет смысл накапливать некую статистику загрузки за 2 или более тиков таймера, чтобы принять адекватное решение.
Вы верно мыслите. Вообще в балансировке корень всех зол - неодинаковость задач. Одна задача будет выполняться 30 тактов и заблокируется, другая - выест свой квантум времени до конца и будет насильственно выпилена планировщиком по тику таймера. Поэтому в балансировке стоит другая дилемма: насколько часто нужно производить перепланирование (по крайней мере - глобальное). Чем реже производишь перепланирование, тем меньше накладные расходы на само планирование и тем более разбалансированный план получаешь. И наоборот, чем чаще производишь перепланирование, тем больши накладные расходы на само планирование и меньше разбалансированность системы.
Himik писал(а):
Ещё имеет смысл использовать адаптивный (или как ещё называют интеллектуальный, smart) планировщик. Вот ZarathustrA описал две основных концепции и задался вопросом выбора. А ведь можно динамически применять то один то другой вид планирования в зависимости от текущей загрузки, и таким образом применять обе концепции. В периоды, когда загрузка системы низкая, то можно применять линейное распределение потоков по второму варианту. И лишь при сильной загрузке системы запускать механизм балансировки по первому варианту. При снижении загрузки нужно опять вернуться к линейному распределению.
Вы пляшете в верном направлении! Так держать!
Вход
Регистрация
FAQ
Поиск
рекомендую к прочтению главу 4 "Планировщик" из книги Роберта Лава "Разработка ядра Linux" (есть в электронном виде djvu). Описано множество неочевидных подводных камней, разобраны стратегии планировки и даны конкретные примеры. Большинство вопросов и сомнений отпадут.