В списке рассылки разработчиков ядра Linux представлена (https://lkml.org/lkml/2012/2/12/64) реализация альтернативного алгоритма планирования задач - BLD (http://code.google.com/p/bld/) (Barbershop Load Distribution). В отличие от используемого в настоящее время планировщика, BLD ограничивается решением задачи по корректному распределению нагрузки путем отслеживания не всех привязанных к CPU очередей, а только наиболее и наименее загруженных очередей выполнения (rq, runqueue). BLD не пытается балансировать нагрузку на систему в контексте отслеживания бездействующих idle-процессов, а акцентирует внимание (http://rk-devel.blogspot.com/2012/02/barbershop-load-distrib...) на распределении всей нагрузки между имеющимися процессорами наиболее простым путём с минимальным числом усложнений.Для пояснения сути нового алгоритма приведена аналогия с парикмахерской в которой менеджер (планировщик задач) выстраивает клиентов (процессы) в несколько очередей (runqueue) к пари...
URL: https://lkml.org/lkml/2012/2/12/64
Новость: http://www.opennet.me/opennews/art.shtml?num=33070
Не прошло и пяти лет
Интересно, а оно будет корректно избегать распределения задач на HT суб-ядра при отсутвии максимальной нагрузки?
Все нормальные в Linux отрубают ХыперТрыйдинг
А что оно дает?
> А что оно дает?А я откуда знаю, это вы его включаете. :)
>> А что оно дает?
> А я откуда знаю, это вы его включаете. :)Оно может дать процентов 20 бонуса на сильно многопоточных вычислениях. А может и не дать. Потенциально позволяет поплотнее загрузить блоки выполнения за декодерами. Фэйк? Фэйк, 20% от ядра никак не тянет на честное ядро. Ну так вон у бульдозера и отключать как-то нечего - там 8 ядер тоже фэйковые. Реально оно себя ведет примерно как 6-ядерник на целочисленных операциях. АМДшники тоже у интела научились этому читерству. Ага, чтобы вывесить фэйковое как-бы-ядро-х86, совсем не обязательно реализовывать полный набор всех блоков за декодером ;)
>Фэйк, 20% от ядра никак не тянет на честное ядро.откуда 20%? Ванда нашептала? :) mov [addr], eax; jmp [addr]; и ваше 100%-е ядро будет 100 тактов 100% свободным, и это, если КП сейчас хоть сколько нибудь свободен. Это если по памяти. Если по софту, то тут спецы пытаются сделать ровной загрузку и выполнение 4-х инструкций за такт (до коре1 было 3), а вы про обычный софт :))) 7-zip выдаёт от 50 до почти 100% прирост скорости от НТ на некоторых данных.
> 7-zip выдаёт от 50 до почти 100% прирост скорости от НТ на некоторых данных.А на всех остальных - 20-50% торможение от HT.
а это уже как раз от неправильной работы планировщика, который ни в зуб ногой не понимает разницу между потоками одного ядра и ядрами...
Хм, разве в современных ядрах планировщик не HT aware? Есть же такая опция вроде.
удивительно, но когда у вас "тормозит", 50% транзисторов простаивают. Впрочем, неспецам пофиг. У них всё-равно НТ виноват :)
> удивительно, но когда у вас "тормозит", 50% транзисторов простаивают.Спасибо гипертрейдингу за это!
Торможение становится проблемой в неоптимизированных под НТ играх
В остальном не тормозит
> откуда 20%? Ванда нашептала? :) mov [addr], eax; jmp [addr]; и ваше
> 100%-е ядро будет 100 тактов 100% свободным, и это, если КП
> сейчас хоть сколько нибудь свободен. Это если по памяти. Если по
> софту, то тут спецы пытаются сделать ровной загрузку и выполнение 4-х
> инструкций за такт (до коре1 было 3), а вы про обычный софт :)))Насколько я понимаю, цель этой пляски с бубном - показать софту больше ядер чтобы получить в лучшем случае (очень параллелизуемый софт) бОльший поток инструкций параллельно. Так что потенциально можно будет крушить больше команд за такт, параллельно и без конфликтов/зависимостей. Ну и при удачном раскладе наверное блоки выполнения за декодерами загружаются и правда поплотнее. Тем не менее, могу себе представить что это имеет и побочные эффекты, вероятно чаще перестает хватать кеша, etc. Т.к. там целая орава не очень взаимосвязанных сущностей пытается одеяло на себя тянуть.
> 7-zip выдаёт от 50 до почти 100% прирост скорости от НТ на некоторых данных.
Насчет 100% - ни разу не видел. Типично обычно процентов 20 прибавляет. Всякие клинические случаи рассматривать не будем. Достаточно погонять бенчмарки для ALU/FPU чтобы осознать что процессор не начинает себя вести как двойной набор блоков выполнения. Вообще все это число ядер - то еще жульничество, обусловленное тем что внутри х86 совсем уже не то чего было когда-то там.
Без НТ у каждого процессора по 1 набору регистров, с использованием НТ - по 2 набора, в результате ОС определяет его как 2 процессора. Процессор редко загружен на 100%, в даже на 100% загруженном процессоре есть простои, и НТ позволяет использовать это для извлечения дополнительной вычислительной мощности. На слабых процессорах или при невысокой загрузке удвоение числа ядер приводит к повышению отзывчивости и более плавной работе.
> Без НТ у каждого процессора по 1 набору регистров, с использованием НТ - по 2 набора,Регистры из воздуха возникают?
Вано, там как не тужся, вход и выход в и из Гипертрубы все равно один. :)
Гипертрединг позволяет одновременно разным потокам обрабатывать раздельно float и integer операции. Например это поможет при конвертировании видео, где аудио целочисленная математика, а видео - математика с запятой. А вот если все потоки только float либо только integer, то поймаешь тормоза, что и видно на линпаке.
> Ты наркоман? Гипертрединг позволяет одновременно разным потокам обрабатывать раздельно
> float и integer операции. Например это поможет при конвертировании видео, где
> аудио целочисленная математика, а видео - математика с запятой. А вот
> если все потоки только float либо только integer, то поймаешь тормоза,
> что и видно на линпаке.Ну почти угадал...
А в общем - софт для HT, как и для любой параллелезации, надо специально готовить.
По этому как написано, видео декодируетя за 45 минут вместо 1 часа, но остальные
23:15 комп будет тормозить.
Да ладно, обычно замедляется не сильнее чем на 2-3%, бывают конечно редкие исключения.
Вики, цитата 1: Эта технология увеличивает производительность процессора при определённых рабочих нагрузках путём предоставления «полезной работы» (англ. useful work) исполнительным устройствам (англ. execution units), которые иначе будут бездействовать; к примеру, в случаях кэш-промаха. Процессоры Pentium 4 (с одним физическим ядром) с включённым Hyper-threading операционная система определяет как два разных процессора вместо.Вики, цитата 2: В процессорах с использованием этой технологии каждый физический процессор может хранить состояние сразу двух потоков, что для операционной системы выглядит как наличие двух логических процессоров (англ. Logical processor). Физически у каждого из логических процессоров есть свой набор регистров и контроллер прерываний (APIC), а остальные элементы процессора являются общими. Когда при исполнении потока одним из логических процессоров возникает пауза (в результате кэш-промаха, ошибки предсказания ветвлений, ожидания результата предыдущей инструкции), то управление передаётся потоку в другом логическом процессоре. Таким образом, пока один процесс ждёт, например, данные из памяти, вычислительные ресурсы физического процессора используются для обработки другого процесса.
Лень было самому писать, тупо копи-пастнул. Теперь ловлю сладких пупсиков в сети их невежества :))))
> Вики, цитатаНа википедии как и на заборе написано ....й, а там даже дров нет.
> Физически у каждого из логических процессоров есть свой набор регистров и контроллер прерыванийФизически у каждого из логических - хорошо сказано, в стиле Windows,
я тоже так умею - теоретически на практике доказано. :)
Как и в спеках Интела ;).
> Как и в спеках Интела ;).Ладно, Вано, думай чё хошь, а из-за HT в Linux тормоза.
Мне не веришь, порой инет, там и Торвальдц и Молнар плевались на него.
Единственные, кто от него в выигрыше это dbenc и tbench
> Ладно, Вано, думай чё хошь, а из-за HT в Linux тормоза.Не только в Linux.
> Ладно, Вано, думай чё хошь, а из-за HT в Linux тормоза.Да нет там никаких особых тормозов. Просто фич довольно читерский. Сам по себе. Можешь на бульдозеровые бенчи посмотреть - там тоже весьма забавная ситуация, при том к линуху она относится чуть менее чем никак. Скорее к архитектуре этой штукенции.
Нда... На 5-тонный грузовик грузить 5 тонн это жуткое читерство :)
> Нда... На 5-тонный грузовик грузить 5 тонн это жуткое читерство :)Нет, читерство - это пытаться загрузить на 5-тонный грузовик 10 тонн.
Стоя на месте, он еще, может, и выдержит, но если пытаться поехать...
Где?Расписываю работу проца "на пальцах": стоит человек, ему во входной лоток ложат задания, он выполняет работу и ложит её на выходной лоток. Таких людей (блоков в проце) несколько сотен тысяч. Чтобы синхронизировать их используют тактовый генератор (в цеху это был бы звонок) который выдаёт квадратичный сигнал (высокий уровень - низкий - высокий - низкий), причём работа начинается только когда уровень меняется с низкого на высокий. Время от звонка до звонка = такт. Какие-то работы занимают меньше такта, какие-то десятки или сотни тактов. Положили нам во входящий лоток работу, а мы стоим-курим - звонок - хватаем работу, начинаем выполнять, выполнили - положили в выходной лоток результаты - опять курим - звонок - во входящем лотке пусто - курим - звонок - хватаем из входящего, там работы на 30 тактов - работаем не обращая внимания на звонки - сделали, положили в выходной лоток - курим.
Всё просто, правда?
Шло время, выполнение работ ускорялось. Чтобы не менять работающую схему её улучшили: теперь работы начинались (звонок) при любом изменении уровня (как с низкого на высокий, так и с высокого на низкий, но ввод-вывод по шине только при смене с низкого на высокий).
Шло время, выполнение работ ускорялось. Ещё улучшение: теперь за 1 такт работник может выполнять до 4 задач, но при этом он оперирует тем что было в лотке на начало такта. И вот здесь появляется HyperThreading: работнику накладывают двое подающих в два входных лотка, и он отдаёт в два выходных. Приоритетами ему выставляют задачи из какого лотка делать в первую очередь чтобы обеспечить боле-менее равномерное выполнение задач из обеих очередей.
Фух.
HT = второй аппаратный набор регистров, переключение контекста должно проходить быстрее. (такое еще есть в IXP серии) Проясните, в реальности все работает по другому?
> HT = второй аппаратный набор регистров, переключение контекста должно проходить быстрее.
> (такое еще есть в IXP серии) Проясните, в реальности все работает
> по другому?Да нет там набора, HT это тот же планировщик, тока в проце,
работает по принципу "мальчики - налево, девочки - направо".
.------.
,---------------| |
~---------/----\,--------------| |---------~
ВХОД | HT | | CORE | ВЫХОД
~---------\----/`--------------| |---------~
`---------------| |
.------.
> Да нет там набора, HT это тот же планировщик, тока в проце,HT - это всего лишь абстракция, позволяющая чуть поплотнее прогрузить блоки выполнения за декодером путем демонстрации бОльшего числа фэйковых ядер. Ну и соответственно в лучшем случае удается поплотнее затрамбовать микроинструкции в блоки выполнения, если повезет. Откуда и появляются 20% профита. Амд в бульдозере поступили не менее нахально, вообще внаглю заявив его 8-ядерным. Хотя блоками выполнения оно обеспечено на уровне примерно 6-ядерника. Но ведь маркетинг же, сцуко! Даешь 8 ядер любой ценой!!!1111
Вот только бенчи то не надуешь. Ну не ведет оно себя там как 8-ядерник и все тут.
Но так твоя педевикия и подтверждает мои слова, читай внимательно. Хотя что толку, если ты понять не можешь, что float и int обрабатываются разными исполнительными устройствами.
>Все нормальные в Linux отрубают ХыперТрыйдингА что, в AMD A4, A6 действительно на каждое реальное ядро по два квазиядра?
>>Все нормальные в Linux отрубают ХыперТрыйдинг
> А что, в AMD A4, A6 действительно на каждое реальное ядро по
> два квазиядра?Там эти же тапки, но абсолютно в другой профиль, например если случае 2 x 2 (2 physical x 2 logical) с Intel оптимальная стратегия использования это брать только реальные ядра, то в случае с AMD c точностью до наоборот, поскольку реальных задержек в работе квазиядер с какой-то там высокой точностью нет, то когда мы грузим всё на два ядра первого модуля второй модуль может вырубиться совсем а первый перейдёт в режим Turbo Core с повышенной частотой. И вместо проседания производительности как на HT мы получим прирост.
Ядро одно, два набора регистров. Это чем-то похоже на функцию (ядро), в которую можно передать разные данные (набор регистров), но код функции от этого не поменяется.Про наличие/отсутствие функций лучше уточнять на сайте производителя по каждой конкретной модели.
Ты хоть понимаешь, что опять пишешь? AMD A6 это обыкновенный K10 о встроенным GPU. Вот тебя и поймали в 100500-й раз. Лучше про HT продолжай копировать цытаты которые ты даже не понимаешь.
> Все нормальные в Linux отрубают ХыперТрыйдингДа нормальные его везде отрубают, не только в линаксе.
и ловят падение производительности при некоторых типах задач...
А я наоборот - включаю. У /me в любимой генточке компиляние идет куды как быстрее, разница, как говориццо, дана в ощущениях. Без всяких бенчей, чисто визуально. Ну а в каком-нить дебиане или красношапке от НТ может и вправду нет толку. Да и хрен бы с ними, се есть отрада некрофилов, не более.
i7 и атом - некрофилия? Ну-ну...
> Интересно, а оно будет корректно избегать распределения задач на HT суб-ядра при
> отсутвии максимальной нагрузки?А зачем? HT он на то и нужен, чтобы неэффективно ресурсы распределять.
> При этом на BLD ложится задача по вычислению
> нагрузки в каждой очереди и перегруппировки
> очередей в соответствии с вычисленной нагрузкой.Вас тут не стояло, перейдите в конец соседней!!!
> Вас тут не стояло, перейдите в конец соседней!!!Так если она короче - почему бы и нет? :)
Если будет реальный выигрыш, то почему бы и нет.
Очень скудно написано. Чем оно лучше того же BFS? Где сравнительные данные?
> Очень скудно написано. Чем оно лучше того же BFS? Где сравнительные данные?Там же сказано: есть только проект концепции прототипа. Нечего еще сравнивать.
...пой читаешь?> ... проводить сравнения производительности пока рано,
> прототип пока нацелен на обкатку базовых принципов.
>показывает хорошую производительность для таких типов нагрузки, как сборка ядра из исходных текстовизвечная проблема... такое ощущение, что все планировщики задач у них разрабатываются только для того, что ускорить кампеляцию йадра
Примеры более стабильных тестов, в студию?!
Которыми пользуются все.
Которые работаю везде.
Которые не используют внешние библиотеки и зависимости.
Результаты которых, только по одному названию можно
интерпретировать для своей машины, даже не проводя тестов.
Компиляция ядра + cpuburn(n+1) + тест хождения в базу через веб сервер.Компиляция порождает кучу мелких быстроживущих процессов, cpuburn в случае неправильной организации перераспределения приоритетов быстро и с удовольствием отодвинет все остальные процессы а база/вебсервер превосходно покажут остаточную интерактивность.
Хороший планировщик должен не просто разгрести эту сракофонию, он должен убедиться что все процессы и в том числе cpuburn получают одинаковый пенальт, а не по степени неудачности как сейчас на Фре в SCHED_ULE. Вот свежие патчи Мотина вселяют оптимизм.
> Компиляция ядра + cpuburn(n+1) + тест хождения в базу через веб сервер.Ну это все нагромождение, из-за которой теряется однозначность.
У сборки ядра, средняя погрешность не более 2%
>> Компиляция ядра + cpuburn(n+1) + тест хождения в базу через веб сервер.
> Ну это все нагромождение, из-за которой теряется однозначность.
> У сборки ядра, средняя погрешность не более 2%Сборка ядра никак не тестирует affinity и заполненость очередей. Может всё вышесказанное и нагромождение, но при тестировании шедулера только на компиляции он в вычислительных задачах будет плавать.
> Для пояснения сути нового алгоритма приведена аналогия с парикмахерской в которой менеджер (планировщик задач) выстраивает клиентов (процессы) в несколько очередей (runqueue) к парикмахерам (CPU), с учётом загруженности парикмахеров организуя очередь так, чтобы клиенту пришлось ждать как можно меньше времени.Ни разу не был в такой парикмахерской.
Обычно в парикмахерских два зала: мужской и женский. И очереди, соответственно, только две: в мужской зал (пул мужских парикмахеров) и в женский (пул женских парикмахеров). Клиент парикмахерской встаёт в одну из очередей и ждёт своей очереди на обслуживание. Бывают небольшие парикмахерские, в которых универсальные парикмахеры и одна общая очередь, где все в очереди ждут пока освободится парикмахер.
> Ни разу не был в такой парикмахерской.
> Обычно в парикмахерских два зала: мужской и женский. И очереди, соответственно, только
> две: в мужской зал (пул мужских парикмахеров) и в женский (пул
> женских парикмахеров). Клиент парикмахерской встаёт в одну из очередей и ждёт
> своей очереди на обслуживание. Бывают небольшие парикмахерские, в которых универсальные
> парикмахеры и одна общая очередь, где все в очереди ждут пока
> освободится парикмахер.Это у вас CFS-парикмахерская :)
@@:
lock btc [mutex]
jnc @b; выбрать поток для выполнения
lock btr [mutex]
"lock" - это блокирование шины для всех операций, включая доступ других ядер к памяти. Поэтому создают отдельные очереди для каждого ядра и общий диспетчер, который помещает потоки в очереди.
cli ; eat this, nut!
Зачем? Проблема не в прерывании, которое вмешается, а в том что мутекс один на 2+ одновременно (реально одновременно) работающих ядер.@@:
lock btc [mutex] ; пытаемся захватить мутекс; "lock" чтобы запретить другим ядрам доступ к ОП на время выполнения операции
jnc @b ; не получилось - пробуем пока не получится; ВАЖНО: здесь ядро по сути встало в непрекращающийся цикл пока мутекс не будет освобождён другим ядром; получаем следующий поток; мутекс всё ещё захвачен, текущее ядро мешает всем остальным
lock btr [mutex] ; освобождаем; "lock" чтобы освободить, т.к. иначе выполнение "lock btc" на другом ядре помешает выполнению нашей операции
Но если на каждое ядро будет своя очередь, то мутекс будет устанавливаться только ядром и диспетчером задач, который вмешивается на порядок реже. А если использовать MTRR, то можно исключить проблему когерентности кэша ядер, что даст дополнительные миллисекунды. А если... Впрочем, тебе и так хватит :)
> Зачем? Проблема не в прерывании, которое вмешается,Специально для Вани лучше сразу делать как-то так:
cli
hlt
Если алгоритм так просто, то возникает вопрос (задам последовав аналогии про парикмахерской) - учитывается ли то, что за человек пришёл (процесс обрабатывается)? К примеру, он может иметь длинные волосы, может прямые, может густые (разные по сложности выполнения), может иметь густые волосы, а может редкие (количество подключаемых библиотек).
Я думаю такие параметры весьма и весьма важны.
> - учитывается ли то, что за человек пришёл (процесс обрабатывается)? К
> примеру, он может иметь длинные волосы, может прямые, может густые (разные
> по сложности выполнения), может иметь густые волосы, а может редкие (количество подключаемых библиотек).Процессору без разницы какой кусок инструкций выполнить в заданный квант времени. По аналогии с парикмахерской парикмахер отстригает небольшой пучок волос и опять отправляет посетителя в очередь. Если посетитель важный то он может застолбить больше мест в очереди и таким образом его подстригут быстрее :-)
> Процессору без разницы какой кусок инструкций выполнить в заданный квант времени.кстати, нет. но учитывать в шедулере ещё и это — мегаоверкил.
Такое очучение что все кто эти планировщики пишут о теории массового обслуживания ни ухом ни рылом. Обсасывается на 4 курсе практически любого технического ВУЗа тема эта. И все давным давно открыто и переоткрыто.
> Такое очучение что все кто эти планировщики пишут о теории массового обслуживания
> ни ухом ни рылом. Обсасывается на 4 курсе практически любого технического
> ВУЗа тема эта. И все давным давно открыто и переоткрыто.Проблема в том, что это _теория_ массового обслуживания, которая более-менее работает в идеальных условиях. В планировщике задач нужно учитывать кучу нюансов и подводных камней, что сводит на нет все теоретические измышления.
>> Такое очучение что все кто эти планировщики пишут о теории массового обслуживания
>> ни ухом ни рылом. Обсасывается на 4 курсе практически любого технического
>> ВУЗа тема эта. И все давным давно открыто и переоткрыто.
> Проблема в том, что это _теория_ массового обслуживания, которая более-менее работает в
> идеальных условиях. В планировщике задач нужно учитывать кучу нюансов и подводных
> камней, что сводит на нет все теоретические измышления.Чувак, ты удивишься, но в науке _всё_ - теории. Что никак не мешает им работать на практике у тех, кто осилил и учёл.
Кого-то вы мне напомнили. Ааа, моего препода по базам данных. Вот он тоже всегда толкает про науку и математику (RA, Datalog, BCNF, 4NF и проч.). ИЧСХ он ни ДНЯ не работал по специальности и не сделал ни одного реального проекта. И ему тоже невдомёк, что в реальной жизни срать хотели на нормализацию. Есть ещё такие вещи как простота поддержки, простота работы, оптимизации.
так это ж сферический нуклайт в вакууме, он всегда такой.
> так это ж сферический нуклайт в вакууме, он всегда такой.Ну вот и сравниваем - где пингвинукс, который делают инженеры, которым надо чтобы ездило, а что оно не по феншую - так и фиг с ним, и *бсды делаемые академиками, которым главное чтоб по феншую, а если оно не ездит - да и хрен бы с ним. Нуклайт прямо эталонный представитель.
Сферический двигатель Венкеля тоже по науке заруливает всех, но вот что-то я не вижу серийных автомобилей с ним, а знаете почему? Его очень сложно сделать, имеет маленький ресурс, сложно обслуживать и чинить. Поэтому никто не заморачиваеться и ставят рядную четвёрку или V6.
> Сферический двигатель Венкеля тоже по науке заруливает всех, но вот что-то я
> не вижу серийных автомобилей с ним, а знаете почему? Его очень
> сложно сделать, имеет маленький ресурс, сложно обслуживать и чинить. Поэтому никто
> не заморачиваеться и ставят рядную четвёрку или V6.Ну вот вся бсда так и выглядит. Вон они делали generic подсистему журналирования. Так чтобы "для всех ФС - одним махом". Правда, "все ФС" оказались аж целым UFSом, древним и бестолковым, так что только выкрасить и выбросить. Есть еще ZFS, но тот реализует совсем другую механику и его эти приседания не интересуют. Отличная логика развития, как раз в таком духе.