?

Log in

me

Unix - система с кооперативной многозадачностью да и ваще *****

На днях ускорил считалку на 5% путем расстановки sched_yield() после окончания каждой подзадачи (подзадача считается порядка 1ms). Дополнительный бонус - исчезли лаги по 50+ms. Т.е. налицо поведение системы с cooperative multitasking.

До этого обломалась борьба с лагами с помощью выставления тредам считалок низкого приоритета, равно как и выставление важному треду высокого. После недолгих изысканий выяснилось, что приоритеты в оперативной системе FreeBSD/Linux отсутствуют. Точнее, они есть в документации. В двух видах. SCHED_OTHER и SCHED_RR/SCHED_FIFO. SCHED_OTHER отпал сразу - его реализация умещалась в одной емкой строчке: return 0; SCHED_RR продержался дольше. Для начала смутило "for obvious reasons only root can set SCHED_RR". Это еще почему мне вот интересно? Ну а во-вторых это просто не работает. Ну т.е. в top и во всех остальных местах вам пишут, что ваш тред имеет мега приоритет. Real Time. Самый главный. Всегда первым возвращается в функции, которая отдает следующий тред для выполнения. Небольшая проблема - функцию никто не зовет :) Поэтому несмотря на приоритет ваш Real Time тред постоит, подождет свои 100 ms.

Говорят есть какие-то real time scheduler-ы для linux. Но т.к. с real time тредами я уже знаком в scheduler-ы веры нет.

Comments

Я не совсем понимаю, что означают real-time thread'ы без соответствующего scheduler'а. В чём сложность взять нормальное real-time ядро, раз уж хочется real-time'ности? Там нормальный preemptive scheduler, mutex'ы с поддержкой priority inheritance.
Я тоже не совсем понимаю что значит "POSIX совместимый" если ставить return 0; :) Mutex-ы вообще не могут быть нормальными по определению - с помощью них нельзя разбудить сразу несколько потоков, только по одному. В этом свете pthreads - хромой по определению API, которому никакой scheduler не поможет.

Интересно что означает priority inheritance. Там же нет приоритетов per se - только скорость с которой они меняются? Я наивно думал, что пока работает тред с приоритетом 1 чуваки с приоритетом 2 будут ждать. И это действительно так в виндах насколько можно видеть. Однако, под unix приоритет это такое пожелание, на которое кладется во всех местах, а настоящий приоритет назначается исходя из соображений авторов ядра, увеличивавших интерактивность своего ftp сервера судя по всему :)

За ссылку спасибо. Сложности две - у нас FreeBSD и много машин.

Ну, если быть честным, то разбудить сразу несколько потоков будет можно только если OS scheduler поддерживает такой примитив, иначе это всё равно будет «по очереди». Зато с не-mutex'ами есть проблема с (неограниченной) инверсией приоритетов.

Я наивно думал, что пока работает тред с приоритетом 1 чуваки с приоритетом 2 будут ждать.
Вот это и называется “preemptive scheduling” (ну точнее это “run till block”, а “preemptive scheduling” означает, что если появился поток с высшим приоритетом, то текущий будет вытеснен), и для этого как раз и нужен правильный скедьюлер (и тогда уже важно иметь что-нибудь вроде priority inheritance или priority ceiling). То есть имеет смысл говорить о приоритетах тогда, когда они имеют осмысленную семантику в рамках выбранного скедьюлера. Альтернативой приоритетам могут быть например дедлайны (и стоимость, если известна), тогда можно делать что-нибудь вроде Earliest Deadline First.

В general purpose ядрах все пытаются сделать что-то вроде fair scheduling, которое, конечно, никогда не fair, и вдобавок не имеет хорошо определённого значения приоритетов (это может быть хинт системе, или тот самый return 0). С FreeBSD я не специалист, но подозреваю, что you're screwed.

Я всё это к тому, что если вкладывать какой-то смысл в слово «приоритет», то и использовать соответствующий диспетчер.

Проблема «много машин» как-то относится к диспетчеризации?

Эээ. Примитив у ядра, конечно, есть и крайне удобный - msleep/wakeup. Зачем вместо них наружу показано убожество в виде pthreads непонятно.

Инверсия приоритетов случается от блокировок (=mutex-ов), которых не должно быть in the first place. Если есть mutex-ы, будет и priority inversion, btw почему борьба с priority inversino это особый случай я не очень понимаю. Типа мы поддержали mutex-ы, чуваки! Они, правда, не работают ни хрена, но вы на это не обращайте внимания, зато бесплатно! :)

Слово приоритет имеет семантику. То, что в unix по дефолту словом приоритет называется хинт и вызывает мое недовольство. Еще большее раздражает "real time thread", который ни в коем разе не может носить громконе имя "real time" :)

много машин относится к тому, что поменять на них ядро и тем более систему - нетривиальное занятие граничащее с невозможностью при текущем раскладе

Зачем вместо них наружу показано убожество в виде pthreads непонятно.
Стандартизация, как я понимаю.



Инверсия приоритетов случается от блокировок (= mutex-ов), которых не должно быть in the first place.
Сильно несогласен с этим утверждением, mutex'ы здесь собственно не причём (и как раз с ними есть очевидное решение unbounded priority inversion), а вот со всякими condition variable, семафорами и прочими радостями всё гораздо печальнее, так как хорошего решения нету: нету очевидного низкоприоритетного потока, который может разблокировать высокоприоритетный, соответственно приоритет нельзя пробустить (так как неизвестно, чей).



Инверсия приоритетов случается от блокировок (= mutex-ов), которых не должно быть in the first place.
Что не работает-то?



Слово «приоритет» имеет семантику, но только в рамках скедьюлера. Да, эта семантика может быть хинтом (например во всех fair scheduling системах). Что за “real-time thread”, который нифига не “real-time” — о чём конкретно идёт речь?



много машин относится к тому, что поменять на них ядро и тем более систему - нетривиальное занятие граничащее с невозможностью при текущем раскладе
Назвался груздем, полезай в кузов. Нечего использовать не-real-time систему для real-time задачи. Ну то есть у меня ощущение какой-то наивности в подходе: вот у нас на куче машин стоит какое-то говно, и мы хотим, чтоб всё было real-time, но захотели мы это только сейчас.

стандартизация не позволила добавить пару syscall-ов?

инверсия приоритетов в данном случае вообще не при чем. Нету в программе ни mutex-ов ни condvar-ов, ни тем более семафоров. Один select на всю программу. Замена его на kqueue ничего не меняет.

если неизвестно какой бустить - бустить можно рандомный.

в документации слово приоритет есть, а что для этого нужен особый шедулер такого слова в документации нет. И у слова приоритет есть понятное значение. Почитайте документацию про SCHED_RR/SCHED_FIFO, там достаточно слов realtime. например тут уже во втором сниппете все написано

какая нахер real time задача? Я просто хочу, чтобы один дорогой моему сердцу тред всегда выполнялся, если ему есть что делать и вытеснял все другие, а не ждал регулярно по 100+ms. Если для этого требуется особый real-time шедулер, #define PREEMPTIVE и пляски с бубном то это называется говно, а не система.

На куче машин у нас стоит офигеть какой крутой FreeBSD. Могу выдать email админов и вы им расскажете какие они идиоты, что поставили это говно. Мне вы уже объяснили, что я наивный, спасибо :)

Нету в программе ни mutex-ов ни condvar-ов, ни тем более семафоров. Один select на всю программу.
Ну так а что этот селект в ядре-то делает? Явно использует один из синхронизационных примитивов, очень вероятно, что condvar. Раздолье для инверсии приоритетов. Я с такой хернёй уже год борюсь на более другой операционной системе (с похожими корнями), где какие-то ненатуралы придумали в обработчике аппаратного прерывания ждать на condvar, освобождаемом каким-то низкоприоритетным потоком ядра, и где все mutex'ы в ядре не реализуют priority inheritance protocol, хотя диспетчер preemptive и run-till-block.

если неизвестно какой бустить - бустить можно рандомный.
Нельзя, это не даёт никаких гарантий по времени, соответственно не решает проблемы unbounded priority inversion в общем случае. Плюс, можно создать так дедлок на пустом месте.

это называется говно, а не система.
О, значит мысль я донёс. Это говно называется система, предназначенная для взаимодействия с пользователем.

Email админов мне ни к чему конечно, просто когда нужны миллисекундная предсказуемость, general purpose OS с непонятным диспетчером использовать не стоит, и об этом надо думать до (правда обычно конечно не получается) :-)

И это действительно так в виндах насколько можно видеть.
Очень сомневаюсь, что в виндах это так, иначе бы всё там было ещё хуже (инверсии приоритетов в пользовательских приложениях ооочень плохо бы повлияли на продаваемость OS). Ну правда я последний раз винды видел в январе 2006, так что может там всё сильно изменилось.
ну я не знаю что именно там устроено по другому. Подозреваю таки preemptive scheduling хотя бы раз 50 в секунду там таки есть. Его достаточно, чтобы обсуждаемая программа работала без таких больших лагов. Подозреваю, что и про priority inversion в MS что-то слышали

Подозреваю таки preemptive scheduling хотя бы раз 50 в секунду там таки есть.
Подозреваю, что таки имеет место какое-то недопонимание preemptive scheduling. Переключения 50 раз в секунду дабы никто не простаивал (и подобные схемы) — это нифига не real-time и очень плохо решает проблему инверсии приоритетов.

Отсюда:

The system treats all threads with the same priority as equal. The system assigns time slices in a round-robin fashion to all threads with the highest priority. If none of these threads are ready to run, the system assigns time slices in a round-robin fashion to all threads with the next highest priority. If a higher-priority thread becomes available to run, the system ceases to execute the lower-priority thread (without allowing it to finish using its time slice), and assigns a full time slice to the higher-priority thread.
Из того, что сказано по ссылке на их решение priority inversion и вышеуказанного параграфа, делаю вывод, что у них смесь fair scheduling и preemptive scheduling. Проблема в том, что нормальный preemptive scheduling должен дополняться ещё политикой run-till-block, а никакими не fair переключениями на потоки того же приоритета на каждый тик таймера. Иначе невозможно предсказать время выполнения потока, так как оно зависит от количество потоков того же приоритета, находящихся в очереди в тот же момент.

опять 25. Нету priority inversion, он у вас в мозгу случился :)

Хочется, чтобы тред с высоким приоритетом вытеснял низкоприоритетные, даже если низкоприоритетные не лезут в ядро, а просто считают. Этого ни linux ни в freebsd по дефолту может не происходить очень долго, а в виндах происходит на раз. Называйте это как хотите.

Можно поподробнее зачем нужен run-till-block? По-моему, как раз наоборот подход виндов - всем с одинаковым приоритетом дать по slice-у более вменяемый. Кого волнует "время выполнения потока"? Мне, например, важнее чтобы все потоки выполнялись более-менее равномерно. Тогда не будет тех самых задержек на непонятно сколько. С трудом могу представить обратную ситуацию. Разве что пресловутый FTP сервер :)

PI может быть там, где есть любая синхронизация. Что у вас система делает эти 100+ms, вы знаете? Я вот более чем уверен, что она делает какую-то херню (вероятно, внутри ядра), которая в данный момент совсем не важна, и потому должна иметь меньший приоритет. А раз она держит что-то более высоко-приоритетное, это и есть PI.

Можно поподробнее зачем нужен run-till-block? По-моему, как раз наоборот подход виндов - всем с одинаковым приоритетом дать по slice-у более вменяемый. Кого волнует "время выполнения потока"? Мне, например, важнее чтобы все потоки выполнялись более-менее равномерно. Тогда не будет тех самых задержек на непонятно сколько. С трудом могу представить обратную ситуацию. Разве что пресловутый FTP сервер :)
“Равномерность” — это fairness, который плох тем, что предсказуемость поведения системы совсем никакая: если у меня есть три потока выполняющихся каждый за 20с, лучшее, что я могу сказать — это что они умрут где-то после 60с, притом очень вероятно, что они ещё и кэш будут друг другу постоянно портить. Когда есть run-till-block, понятен порядок выполнения (исходя из приоритетов), нет необходимости использовать синхронизацию там, где данные могут быть доступны только потокам низких (или равных приоритетов), если мы знаем, что не будем заблокированы до окончания работы с данными. Вот как раз тогда приоритеты имеют наиболее осмысленную семантику: всегда выполняется что-то с самым высоким приоритетом, если оно не заблокировано. Добавляем PIP, и у нас ещё появляется дополнительная гарантия на то, что высокоприоритетные потоки не будут вытеснены потоками более низких приоритетов неограниченное время.

Зачем это нужно: любая система, требующая чёткого понимания, какие потоки важнее, как определён порядок выполнения, в присутствии синхронизации между потоками. Например, системы управления реальными объектами, получение и обработка данных сенсоров, проигрывание видео (тут правда soft real-time, cтараются просто достичь QoS, для чего система реализованная в Windows довольно адекватная).

тоже самое происходит если просто sleep звать из "высокоприоритетного" треда. Sleep-то вряд ли подвержен PI?

"лучшее, что я могу сказать — это что они умрут где-то после 60с" - а что, можно что-то еще лучше сделать? Если бы они умерли практически одновременно через 60 сек это было бы оптимально с моей точки зрения.

Кеш друг другу портить это да, но так не надо 1000 раз переключать, можно и пореже :)

run till block в сочетании с назначаемыми системой понятными только ей приоритетами превращают все в описанный бардак imho. Система решила, что мой "типа высокоприоритетный" тред сегодня имеет приоритет пониже и привет - ждет пока поблокается тред считалки. А он и не блокается - зачем ему лишний раз тормозить. Вот 100+ms и набегает. Какая же это осмысленная семантика приоритетов с точки зрения пользователя всей этой марахайки?

наверно run till block удобен в realtime системах, но здесь же блин кажуалы сидят, они realtime системы только в зоопарке и видели :)
Система решила, что мой "типа высокоприоритетный" тред сегодня имеет приоритет пониже и привет - ждет пока поблокается тред считалки. А он и не блокается - зачем ему лишний раз тормозить. Вот 100+ms и набегает.
Не понял сценария, с какой радости система решит уменьшать приоритет? Всё гоняется с установленным тобой приоритетом, кроме случая когда высокоприоритетный поток (ВП) попытался взять мутекс, который держится низкоприоритетным (НП). В этом случае, до того момента когда НП отпустит мутекс, приоритет НП временно повышается до приоритета ВП (пресловутый priority inheritance). Как мутекс отпускается, приоритет НП возвращается на начальное значение.
с такой радости. Посмотрит - что-то тред много CPU сожрал и уменьшит. Об том и спич.

С установленным мной приоритетом? Не в этой жизни :) В этой - return 0; вместо установленного приоритета

про PI и мутекс я понял, здесь это не происходит
Посмотрит - что-то тред много CPU сожрал и уменьшит. Об том и спич.
Это какой-то полный бред, совсем не связанный с нормальным preemptive scheduling. Грёбаный fairness.
sleep из любого треда — это фактически инструкция разбудить поток не раньше чем через время сна. Разбудить — заскедулить его в соответствии с его приоритетом. Если в это время будет что-то более высокоприоритетное работать, ясно дело проснётся он позже, иначе вытеснит.

Лучше чем сказать, что умрут где-то после 60с — сказать в каком порядке они будут выполняться и умирать, более того, зная порядок можно точнее сказать, кто когда будет умирать.

Да по-моему не только в realtime системах удобно это, просто всем запудрены мозги fairness'ом :-)
теорию я понял и с ней полностью согласен. Практика - SCHED_RR тред, sleep на 5ms - спит 50. В системе других SCHED_RR нет, только обычные. Но FreeBSD решила, что у них будет одинаковый 44-й приоритет положив тем самым b на спецификацию и на всех наивных заодно.

в каком порядке выполняться и умирать - это было бы хорошо, но я бы предпочел виндовый шедулер any day :)

мне тут рассказали, что complete fair scheduler якобы работает как надо. А еще можно поставить SCHED_BATCH и тоже все будет хорошо, но это все под Linux
Практика - SCHED_RR тред, sleep на 5ms - спит 50. В системе других SCHED_RR нет, только обычные. Но FreeBSD решила, что у них будет одинаковый 44-й приоритет положив тем самым b на спецификацию и на всех наивных заодно.
Ну так а кто занимает процессор эти 45 мс? И вообще, с какой гранулярностью скедулер переключает процессы известно? А то если что-нибудь меньше 22 Hz, то всё понятно.

Кроме того, отсутствие user-space потоков высшего приоритета ещё не означает, что не может быть такой задержки: есть ещё системные потоки (всякое I/O и memory handling запросто может быть высокоприоритетным), но самое главное — аппаратные прерывания у которых приоритет выше приоритета scheduler'а. И в этих аппаратных прерываниях часто присутствуют busy-wait'ы при каждой попытке обращения к девайсу, и в сумме это может складываться в многие миллисекунды. Вот только пару недель назад заменял в чужом драйвере сетевухи JNE на JMP вокруг кода, который без дела ждал 20 мс если повезёт, и 100 мс если не повезёт.
обычный тред занимает. HZ=1000.

в системе в этот момент вообще ничего не происходит. Только все ядра грубо говоря делают nop и SCHED_RR тред ждет чего-то, видимо, пока один из запущенных blocked. вот здесь пишут, что шедулер может и 140 ms за раз потоку выдать, соответственно, мы и наблюдаем эффект.
Щедрый какой :-)

Ну важно ещё помнить, что даже если scheduler больше 140 ms не даёт потоку, если в последний момент будет вызван обработчик аппаратного прерывания, то может получиться и больше, и scheduler ничего не сможет сделать до его завершения.
А если попробовать Windows-Solaris?
в виндах все работает как часы. Осталось винды на кластер поставить :)
без проблем, есть Windows HPC (Windows cluster edition) с MPI и всем фаршем.
Если фря, то какое ядро и какой шедулер?
7.2 stable, шедулер ULE насколько понимаю
Ага. А TZ какой -- стандартный 1000? Я просто как-то не очень понимаю, откуда получаются чисилки порядка 100 ms (или это всё же 100 us?)
TZ не знаю какой, думаю стандартный. Я тоже не понимаю, откуда 0.1 sec и понимать как-то нет ни времени ни желания. Если со sched_yield()-ом работает, то и ладно, но то, что без него не работает - минус в карму
sysctl kern.clockrate
sysctl kern.timecounter

Upd: хотя, про минус в карму -- подпишуся :(


Edited at 2009-09-29 11:19 pm (UTC)
kern.clockrate: { hz = 1000, tick = 1000, profhz = 666, stathz = 133 }

про timecounter полтора экрана, на что там смотреть? Вроде пишет, что использует kern.timecounter.hardware: ACPI-fast

HZ вроде хороший :)
100ms - цифра не простая. Это дефолтное значение так называемого timeslice - максимального времени, которое может выполнятся один процесс до принудительного переключения на другой. Отцы-основатели решили, что при работе через терминалы именно такое значение создает ощущение комфортности при минимальных накладных расходах. У вас задачи другие, поэтому вероятно вам подойдет значение поменьше - получите лучшее время отклика ценой больших накладных расходов на более частое переключение процессов :)
Меняется оно через sysctl, в зависимости от версии ОС и используемого планировщика оно может называться kern.quantum, kern.sched.quantum, kern.sched.slice. Единицы измерения у этих переменных тоже разные, причем зависят не только от имени переменной, но и от используемого планировщика (ULE/4BSD).

Отсюда:

options PREEMPTION # Enable kernel thread preemption
Allows threads that are in the kernel to be preempted by higher priority threads. It helps with interactivity and allows interrupt threads to run sooner rather than waiting.
Это, надеюсь, включено? Правда, неясно, влияет ли это как-то на user threads.

отключено afaik. Судя по описанию влияет только на kernel threads
Я подозреваю, что под kernel threads здесь всё же подразумеваются потоки как примитивы ядра (а не какие-нибудь зелёные потоки, симулирующиеся в user-space). Может конечно быть, что потоки ядра гоняются с приоритетами из какой-то группы (выше user-space приоритетов), и только для них делается preemption (для user-space по дефолту может быть time-sharing, но только если сейчас не работает что-то из preemption группы), но тогда обычно можно user-space потоку дать как раз такой более высокий приоритет из preemptive группы приоритетов, иногда даже выше приоритета ядра.
надо будет как-нибудь попробовать, посмотреть что будет с #define PREEMPTIVE
Для начала смутило "for obvious reasons only root can set SCHED_RR". Это еще почему мне вот интересно?
Это чтоб произвольный юзер не мог убить систему запустив RR поток, который вытеснит всех остальных и не отдаст никогда управление. По-хорошему должен быть просто специальный permission для юзеров, которые могут использовать этот scheduling class (так сделано в Solaris и, кажется, Linux).
эти опасения напрасны, в силу неясных обстоятельств RR тред ничем не отличается от обычного и убить ими систему не выйдет :) Что интересно в обратную сторону тоже нельзя - если я хочу создать мега idle-овый тред, то мне опять же root нужен. Точнее это вообще невозможно, т.к. можно только поднять "приоритет"

Насколько я понимаю, для совсем критических вещей

Неплохо бы порыскать среди микроядерных осей.
Потом, взять тот же MINIX.
На FreeDOS посмотреть.

Re: Насколько я понимаю, для совсем критических вещей

мне еще работать нуна :) Я бы лучше винды поставил - они хоть и не realtime и без микроядра, но работают предсказуемо

> На FreeDOS посмотреть.

TSR'ы писать? Back to 80's?
me

April 2014

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
27282930   
Powered by LiveJournal.com