Очередь перед мьютексом

Здесь терминология конфликтует. Я пишу про приоритеты потоков с точки зрения планировщика ядра. В твоей цитате ничто не говорит о том с каким приоритетом выполняется background и foreground потоки сборщика мусора.

Я провёл эксперимент. В цикле каждые 500 мсек создаю 100к объектов. Смотрю в htop. У приложения 6 потоков и у всех в столбце PRI стоит 20, а в NI — 0. Иногда появляется седьмой. С таким же приоритетом.

ВМ C# запускает все потоки в том числе и сборщика мусора с дефолтным приоритетом.

хотя мне и не особо хочется обсуждать этот конкретный пример с фоновой сборкой мусора в нете, но тем не менее -

https://dzone.com/articles/deep-dive-into-net-garbage-collection

цитато:

The thread for background GC runs at a lower priority concurrently with your application’s threads and will be suspended when the foreground GC threads become active so that you do not have to compete GC modes occurring simultaneously. If you are using workstation GC, then background GC is always enabled. Starting with .NET 4.5, it is enabled on server GC by default, but you do have the ability to turn it off using runtimeconfig.json.

Левая информация с левого сайта. Похоже сильно протухшая. Там конфигурация проекта в json файле. Так было вначале dotnetcore. Это уже выбросили и заменили православный xml для msbuild. Так же натурный эксперимент опровергает написанное. Приоритеты у всех потоков одинаковые.

а давайте, батенька, вы просто прогуглите инет на предмет паттерна

low priority thread garbage collector

и там все увидите.

Я думал у тебя есть конкретные сведения по приоритетам потоков сборщика мусора. Мало ли что там пишут в гугле. В гугле и моё сообщения из этой темы можно найти. И что, теперь это пруф? По этому вопросу котируется какой-нибудь MSDN, например.

Какова вероятность что следующим проснётся «нужный»?

Вероятность около 100%. Попробуй написать подобный код и посмотри. Я попробовал и еще ниразу не получил результат не по порядку.

Мало ли что там пишут в гугле.

не знаете-ли. а другого энторнета у меня для вас нет

Проверь в чебурнете.

они пробуждаются в той же последовательности, в которой пришли? То есть там образуется внутренняя очередь (thread-safe queue)? Или же в рандомном порядке?

А Вам это зачем? Возможно действительно очередь, но это поведение implementation-specific, и полагаться на него нельзя. Если бы в документации было прямо указано, что гарантируется какая-либо очерёдность захвата мьютекса, то тогда да, можно было бы где-то использовать. А так, оставлена возможность изменения поведения для разработчиков самого мьютекса.

А что происходит в данной архитектуре, если рабочие потоки работают? Приложение падает по оом потому что треды сборки мусора не получают управления?

читать тут https://learn.microsoft.com/ru-ru/dotnet/standard/garbage-collection/background-gc

Не на что там смотреть. Если у тебя что-то зависит от порядка пробуждения заданного снаружи — это просто плохой дизаен. Потоки, если ты не играл с приоритетами, часто крутятся операционными системами по банальному раунд робину, отчего может показаться что там есть какой-то порядок но... в числе других процессов — поэтому в общем случае порядок не определен. Всякое упорядочивание типа «Б происходит после А» проще добиться явными сигналами, т.е. посылкой сообщений, барьерами в памяти, логической переменной, семафорами. Или... отдавать задачу из очереди любому свободному воркеру из пула. «Воркер» на то и воркер, что ему обычно пофиг, какую задачу делать. Порядок пробуждения в таком случае не особо важен. Ну и да. Все эти попытки ручного управления порядком обычно ограничивают возможности распараллеливания, т.к. потоки в основном отдыхают на мьютексе.

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

Покури про планировщики. Раунд робин — это перебор по очереди и есть :) но есть другие процессы кроме твоей проги и всякие прерывания от устройств, которые эту идиллию превращают в полноценный рандом. Из-за этого монетка, которая по твоим наколенным тестам падала одинаково, может встать на ребро в любой момент, чаще всего когда «совсем не ждешь».

Фи, пропаганда мелкосакса

Интересно даже стало. Каким образом другие процессы и прерывания могут нарушить цепочку раунд робина в какой-нибудь риалтайм системе?

Попробуй написать подобный код и посмотри.

Начнём с того что в обозримом будущем конкретно мне это вряд-ли понадобится. Специфика софта с которым мне приходится иметь дело состоит в том что задачи делятся на «это нужно сделать прям здесь и сейчас», и «всё остальное» (в основном IO) что отправляется на обработку в единственный background thread. И там где нужно «здесь и сейчас» мы не гнушаемся ничем, включая busy-wait loops, и прибиванием threads гвоздями к изолированным ядрам.

Я попробовал и еще ниразу не получил результат не по порядку.

Я даже не знаю - вы или счастливчик, или «так получилось». При любом раскладе - это не доказывает ничего. В лучшем случае - fairness обеспечивается ядром, в худшем - вы залетаете как минимум на O(N^2) и неконтролируемые задержки.

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

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

Единственное - если кто-то убьёт тред в середине использования данной системы (стоящий в очереди или занявший объект), то могут быть проблемы, но это вроде и обычных мютексов касается.

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

Более того, насколько я знаю, обычно так и делается.

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

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

Просто там наговнокожено, а изменение приоритетов — это способ отобрать время у говнокода. Опять вернулись к моему тезису, что приоритеты это костыли, которые втыкают вместо исправления говнокода. Там, где нет говнокода, приоритеты не нужны.

Не костыли к мютексу, а именно честная очередь

Мы оба понимаем что это мало отношения имеет к fairness mutex’а как такового?

В кокой еще реалтайм? Где ты в ОП увидел реалтайм? В реалтайм у тебя будет SCHED_FIFO с явным освобождением проца задачей или SCHED_DEADLINE вообще, а не SCHED_RR. Только нафига превращать линукс в нетварь или... зачем вообще тогда линукс? :) Для трех с половиной задач в реалтайме ось общего назначения — ненужный оверхэд.

Если нужны такие гарантии, ось тебе скорее всего не нужна. Просто «задачи» будут не прогами в некоторой оси, а... частью бинаря прошивки. Даже планировщика может не понадобиться, если тайминги все известны и порядок отклика весь определен циклограммой.

SCHED_FIFO это и есть SCHED_RR, только без таймслайсов. А если приоритет одинаковый (это понятно из ОП), то и вовсе одно и тоже. Нормально в риалтайме работает RR. Риалтайм это я для пущего упрощения тестбенча притащил, ведь треды, ожидающие мутекса обычно имеют одинаковый приоритет и таки будут заходить по RR в общем случае.

Мне не понятно твое заявление, как могут помешать этому другие процессы или прерывания (никаких прерываний воркеры не подразумевают и отрабатывают за 1 присест, это для упрощения).

Если мы не в какой-то там реалтайм-системе, а в линуксе, который по определению с вытесняющей многозадачностью, ведро у потока юзерской задачи заберет проц когда захочет, какие там ты ему хотелки не выставляй. А с каким-нито FULLPREEMPTIVE_RT патчем , например, IRQ будут видны в системе как потоки ядра с политикой FIFO, которые не отдадут проц пока он им нужен.

См рядом :) не все сетапы будут такие как ты хочешь.

Ты слишком категоричен и в целом не прав. Хотя то, что ты описал, тоже конечно бывает.

Не знаю что такое «fairness mutex’а», но получившийся объект вполне можно назвать мютексом при желании.

Не знаю что такое «fairness mutex’а»

Очень хороший point, на самом деле. Мне было бы интересно даже не взятие mutex’а именно в том порядке в котором треды пришли (что на самом деле определить довольно сложно, учитывая что они могли придти с нескольких ядер literally одновременно), а относительная частота взятия mutex’а когда несколько threads дерутся за mutex in a tide loop.

tight loop.

fixed. Пишите уж лучше «тесный» или «тугой».

треды за мьютексы не дерутся. видя, что мьютекс занят, они засыпают сном младенца в очереди к мьютексу. и видят сны про розовых пони.

Жду “fair_mutex” забилженый поверх любых стандартных POSIX примитивов. Желательно со статистикой поведения именно в описанном случае (чтобы 2 раза не вставать).

могу ошибаться, давно смотрел, но сейчас на Linux std::mutex он поверх pthread_mutex_t, а тот построен поверх вызова futex и спин лока. Очередей там нет. Так что порядок пробуждения будет зависеть больше от того, в каком порядке планировщик будет давать работу твоим потокам, которые заблокировались на этом мутексе, а после освобождения - кто первый проснулся, того и тапки. Не стоит надеяться на порядок прихода блокировку.

Собственно вот главное из futex.2

       FUTEX_WAKE (since Linux 2.6.0)
              This operation wakes at most val of the waiters that are
              waiting (e.g., inside FUTEX_WAIT) on the futex word at the
              address uaddr.  Most commonly, val is specified as either
              1 (wake up a single waiter) or INT_MAX (wake up all
              waiters).  No guarantee is provided about which waiters
              are awoken (e.g., a waiter with a higher scheduling
              priority is not guaranteed to be awoken in preference to a
              waiter with a lower priority).

Конкретно:

No guarantee is provided about which waiters are awoken (e.g., a waiter with a higher scheduling priority is not guaranteed to be awoken in preference to a waiter with a lower priority).

А где порядок пробуждения декларирован?

Я такого ни разу не встречал.

Просто там наговнокожено, а изменение приоритетов — это способ отобрать время у говнокода. Опять вернулись к моему тезису, что приоритеты это костыли, которые втыкают вместо исправления говнокода. Там, где нет говнокода, приоритеты не нужны.

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

Я про FUTEX_WAKE выше привёл, там явное: нет гарантии.

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

Какова вероятность что следующим проснётся «нужный»?

Более того: даже если у нас «честный FIFO», откуда разраб может знать, какой из его потоков первым упёрся в занятый мьютекс? Параллелизм в принципе предполагает недетерминированность таких вещей, а потому сам сабжевый вопрос не имеет смысла. Как собственно и «честный FIFO» – разве что для самого ядра с целью равномерной балансировки.

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

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

Пробуждение из мютекса делает не планировщик а сисколл

Спешу не согласиться: после того как thread захвативший mutex его отпускает - все карты в руках именно у планировщика. Более того - если кто-то с более высоким приоритетом ждёт mutex по-хорошему приоритет того кто его держит надо бустить.

Я не смотрел как они устроены, но это звучит очень плохо. В планировщик засунули код для захвата мютекса? Или, ещё хуже, мютекс после слипа лочится в юзерспейсе с шансом «не получилось»?

Я не смотрел как они устроены, но это звучит очень плохо.

«Се ля ви».

В планировщик засунули код для захвата мютекса?

Если поспать таки пришлось, и с CPU Вас сняли: да выбора-то особо и нет - кто-то должен принять решение «кто следующий». И лучше - если это будет «educated decision» (thread priority dependent).

Или, ещё хуже, мютекс после слипа лочится в юзерспейсе с шансом «не получилось»?

Ну, обычно на spinlock какое-то время крутяться прежде чем уснуть. Я бы сказал - оправданная стратегия.

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

chatgpt детектед

Неправда. планировщик вполне по алгоритму распределяет.