Интересно, как реализованы базовые примитивы мультипоточности в C++? Такие как mutex

насколько я понимаю, все базируется на атомарной test-and-set инструкции (которую я бы назвал fetch-and-set)
и spin_lock блокировке, которая выглядит примерно так:

spin_outer:
cmp flag, 1
je spin_outer // waiting until 0

spin_inner:
test-and-set ax, flag //executed atomicly
// {
// mov ax, flag // fetch current value to ax
// mov flag, 1 // set flag to 1
// }

cmp ax, 1
jne spin_inner // if old value was 0

// now in critical section

call do_work

mov flag, 0 // clean flag
leave:

но это приводит не просто к простою потока, а постоянной нагрузке

при использовании std::mutex для критической секции такого не наблюдается.

как же работает мютекс?

Здравствуйте, barney, Вы писали:

B>Интересно, как реализованы базовые примитивы мультипоточности в C++? Такие как mutex

B>но это приводит не просто к простою потока, а постоянной нагрузке

B>при использовании std::mutex для критической секции такого не наблюдается.

B>как же работает мютекс?

В linux mutex работает через системный вызов futex, который освобождает процессор и добавляет поток в очередь, если мьютекс занят.
Документация: manual
Можно почитать здесь: статья
Также есть комментарии в коде ядра futex.c

что значит mutex и std::mutex ?
называйте точно о чем говорите

Здравствуйте, barney, Вы писали:

B>Интересно, как реализованы базовые примитивы мультипоточности в C++? Такие как mutex
Конкретная реализация целиком зависит от рантайма и на разных платформах реализована по разному.

B>это приводит не просто к простою потока, а постоянной нагрузке
B>при использовании std::mutex для критической секции такого не наблюдается.

Под Windows, например (VS2013), std::mutex реализован без использования вызовов WinAPI, почти так, как вы и описали, но spin блокировка крутится заданное число циклов (сейчас 4000) и уже по истечении этого времени квант потока отдается (он засыпает на pause). Фактически в С++ рантайм вынесены "кишки" стандартной critical section.

V>Конкретная реализация целиком зависит от рантайма и на разных платформах реализована по разному.

Вот это и хочется изучить. Т.к не понятно, как именно мьютекс "усыпляет" поток, и кто потом его "просыпает"
как вообще работает эта машинерия.
Собственно для этого и создал данный топик
для тех кому интересно было бы исследовать и обсудить реализации для различных ОС / архитектур

V>Под Windows, например (VS2013), std::mutex реализован без использования вызовов WinAPI, почти так, как вы и описали, но spin блокировка крутится заданное число циклов (сейчас 4000) и уже по истечении этого времени квант потока отдается (он засыпает на pause). Фактически в С++ рантайм вынесены "кишки" стандартной critical section.

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

какой смысл их исследовать ?
в юниксе код открыт, хотите открывайте и читайте
в винде WRK тоже открыт + windows internal pdf есть

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

Здравствуйте, barney, Вы писали:

B>Интересно, как реализованы базовые примитивы мультипоточности в C++? Такие как mutex

В разных реализациях STL и для разных ОС по-разному. Например, в GCC для unix-like-ов std::mutex-это приплюснутый врайпер над POSIX API.

  void
       lock()
       {
         int __e = __gthread_mutex_lock(&_M_mutex);
   
         // EINVAL, EAGAIN, EBUSY, EINVAL, EDEADLK(may)
         if (__e)
           __throw_system_error(__e);
       }

 static inline int
 __gthread_mutex_lock (__gthread_mutex_t *mutex)
 {
   if (__gthread_active_p ())
     return __gthrw_(pthread_mutex_lock) (mutex);
   else
     return 0;
 }

Здравствуйте, barney, Вы писали:

V>>Конкретная реализация целиком зависит от рантайма и на разных платформах реализована по разному.

B>Вот это и хочется изучить. Т.к не понятно, как именно мьютекс "усыпляет" поток, и кто потом его "просыпает"
B>как вообще работает эта машинерия.

Системный вызов futex работает в ядре, и усыпляет поток передачей управления функции schedule() планировщика процессов. Вообще планировщик вызывается или напрямую если процесс сам хочет освободить процессор, или из прерывания таймера. В зависимости от приоритетов процессов планировщик выбирает тот, которому положен следующий квант времени, и переключает на него контекст переключением таблицы страниц и загрузкой сохраненных значений регистров этого процесса.
Когда мьютекс освобождается, код futex помечает один из ждущих в очереди фьютекса потоков для исполнения, и планировщик при случае передаст ему управление.

lpd>Системный вызов futex работает в ядре, и усыпляет поток передачей управления функции schedule() планировщика процессов. Вообще планировщик вызывается или напрямую если процесс сам хочет освободить процессор, или из прерывания таймера. В зависимости от приоритетов процессов планировщик выбирает тот, которому положен следующий квант времени, и переключает на него контекст переключением таблицы страниц и загрузкой сохраненных значений регистров этого процесса.

Ага, schedule() вызывается и по прерыванию таймером работающего потока, и в futex, так?
Т.е должен быть механизм, который отличает поток, ждущий futex от работающего потока, квант времени которого истек.
Иначе нет строгих гарантий что futex поток не проснется "внезапно" если планировщику вдруг так вздумается.

lpd>Когда мьютекс освобождается, код futex помечает один из ждущих в очереди фьютекса потоков для исполнения, и планировщик при случае передаст ему управление.

Т.е есть какой то системный condition variable в ядре, по которому поток "вешается" спать, до наступления сигнала ядра,
которое, например возникает когда другой поток освобождает тот же мьютекс?

Здравствуйте, smeeld, Вы писали:

S>В разных реализациях STL и для разных ОС по-разному. Например, в GCC для unix-like-ов std::mutex-это приплюснутый врайпер над POSIX API.

А POSIX функция pthread_mutex_lock уже, я так понимаю, использует некие функции ядра?
в LINUX это futex
асли это DARWIN/MACH то есть некие ядерные mach_ функции для блокировки/просыпания потоков, которые завязаны на мьютекс

R>какой смысл их исследовать ?
R>в юниксе код открыт, хотите открывайте и читайте
R>в винде WRK тоже открыт + windows internal pdf есть

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

Здравствуйте, barney, Вы писали:

B>Мне интереснее человеческое общение на данные темы.
B>Например, книге нельзя задать вопрос по мере его возникновения.
B>Поэтому лично мне интереснее исследовать тему коллективным разумом.

Дело в том, что в зависимости, даже, от версии студии и стандарта С++ реализация может сильно наворочена для поддержки всех примитивов. Но в итоге, все сводится к старому доброму test_and_set. Под Windows вы также можете посмотреть реализацию в исходниках CRT. Microsoft вынесла всю реализацию в user mode. В случае необходимости усыпить поток, что бы он не тратил ресурсы процессора, используется ассемблерная вставка, вызывающая инструкцию pause, которая специально предназначена для ожидания внутри spin lock.

Здравствуйте, barney, Вы писали:

B>Т.е должен быть механизм, который отличает поток, ждущий futex от работающего потока, квант времени которого истек.
B>Иначе нет строгих гарантий что futex поток не проснется "внезапно" если планировщику вдруг так вздумается.
B>Т.е есть какой то системный condition variable в ядре, по которому поток "вешается" спать, до наступления сигнала ядра,
B>которое, например возникает когда другой поток освобождает тот же мьютекс?

Да, у futex в ядре есть очередь ожидающих его потоков.
Код mutex.lock() в user-level атомарно проверяет флаг занятости мьютекса, и, если он свободен, то просто захватывает его, и без вызова кода ядра возвращает управление захватывающему мьютекс коду. Если мьютекс уже кем-то занят, то mutex.lock() вызывает сисколл sys_futex(FUTEX_WAIT). Есть тонкость, что sys_futex в ядре еще раз проверяет занятость мьютекса на случай, если он освободился между проверкой mutex.lock() и sys_futex()(Это подробно описано в комментарии в коде ядра futex.c). Если фьютекс занят и поток нужно перевести в режим ожидания, то он добавляется в очередь, связанную в ядре с фьютексом.
Когда занимающий фьютекс поток освободит его вызовом mutex.unlock()(реализованный через сисколл sys_futex(FUTEX_WAKE)), код sys_futex(FUTEX_WAKE) в ядре выберет ожидающий поток из очереди фьютекса и пометит его системному планировщику(у которого есть свой глобальный список потоков) для исполнения. Этот поток когда до него дойдет очередь получит квант времени, на него переключится контекст, он вернется из sys_futex(FUTEX_WAIT), и окажется в коде mutex.lock(). Код mutex.lock() на всякий случай проверит, не был ли снова занят mutex, и если успеет атомарно захватит его.

коллективный разум это когда решается какая то проблема доселе не известная или не имеющая решения
а как устроены ОС описано в гугле на каждом шагу, плюс куча книг и исходников
это называется по другому, — научите меня бесплатно

это все равно что если бы я создал тему "как устроен С++ ?"
и объясняйте мне на пальцах все о нём

ну т.е. ваша тема флеймовая, — сам читать не хочу, объясняйте мне своими словами

R>коллективный разум это когда решается какая то проблема доселе не известная или не имеющая решения
R>а как устроены ОС описано в гугле на каждом шагу, плюс куча книг и исходников
R>это называется по другому, — научите меня бесплатно

феерическая чепуха)) про учебные группы слышал? добровольные, заметь
прийди еще в школу, поругай там разборы сортировки пузырьком)
а просветленные гуру — пусть идут мимо,
никто ж не претендует на их "небесплатное" внимание, лол)

lpd>Да, у futex в ядре есть очередь ожидающих его потоков.
lpd>Код mutex.lock() в user-level атомарно проверяет флаг занятости мьютекса, и, если он свободен, то просто захватывает его, и без вызова кода ядра возвращает управление захватывающему мьютекс коду. Если мьютекс уже кем-то занят, то mutex.lock() вызывает сисколл sys_futex(FUTEX_WAIT). Есть тонкость, что sys_futex в ядре еще раз проверяет занятость мьютекса на случай, если он освободился между проверкой mutex.lock() и sys_futex()(Это подробно описано в комментарии в коде ядра futex.c). Если фьютекс занят и поток нужно перевести в режим ожидания, то он добавляется в очередь, связанную в ядре с фьютексом.
lpd>Когда занимающий фьютекс поток освободит его вызовом mutex.unlock()(реализованный через сисколл sys_futex(FUTEX_WAKE)), код sys_futex(FUTEX_WAKE) в ядре выберет ожидающий поток из очереди фьютекса и пометит его системному планировщику(у которого есть свой глобальный список потоков) для исполнения. Этот поток когда до него дойдет очередь получит квант времени, на него переключится контекст, он вернется из sys_futex(FUTEX_WAIT), и окажется в коде mutex.lock(). Код mutex.lock() на всякий случай проверит, не был ли снова занят mutex, и если успеет атомарно захватит его.

То есть, в общем случае мьютексная блокировка требует сисколла (если не брать быстрый спинлок у futex — и то, это только у линукс)
и, значит, как минимум, смену контекста на ядерный + перепланирование потока. что может привести к серьезному простою на исполнение в CPU
Притом, даже, если конкурирующие потоки очень быстро работают (например размалывая какие то данные параллельно) — их будет поочередно кидать в ядро...

Хмм... Стало быть, мьютексы — не очень эффективный механизм. Тут нужен какой то иной подход.
Та же work queue или thread pool
Хотя, насколько я понимаю condition variable в основе work queue — тоже системный вызов. Который тоже задействует планировщик.

Интересно, можно ли както синхронизировать потоки некоей атомарной операцией в usermode.
Притом так, чтобы пока поток спит, на его месте (в ядре CPU) исполнялись другие потоки.

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

Здравствуйте, barney, Вы писали:

B>Интересно, можно ли както синхронизировать потоки некоей атомарной операцией в usermode.

В том и отличие mutex от spinlock, что первый может освободить процессор и для этого переходит в режим ядра сисколлом, а спинлок просто в user-level крутит атомарную проверку-и-захват флага, пока другой поток его не освободит. Если ожидание недолгое, то спинлок быстрее. Однако, если ожидание долгое, то лучше все-таки освободить процессор для других потоков.
Условная переменная работает тоже через sys_futex и переходит в режиме ядра для освобождения процессора, хотя ее тоже можно реализовать как спинлок на одних атомарных проверках в user-level.

B>Кстати, отдельный вопрос — не понятно, как потоки привязываются к ядрам? Привязываются ли.
B>Т.е в общем виде может ли заснувший поток — проснуться в другом ядре?

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

lpd>В том и отличие mutex от spinlock, что первый может освободить процессор и для этого переходит в режим ядра сисколлом, а спинлок просто в user-level крутит атомарную проверку-и-захват флага, пока другой поток его не освободит. Если ожидание недолгое, то спинлок быстрее. Однако, если ожидание долгое, то лучше все-таки освободить процессор для других потоков.

т.е получается ядро просто исполняет некий набор инструкций (user mode) пока не прийдет системное прерывание таймера, или не встретится системный вызов.
Тогда управление перейдет в kernel. Т.е в общем случае, освободить ядро досрочно — такая же "по тяжеловесности" операция, как и истечение кванта времени, так?
Затем уже в ядре планировщик решает, на какой поток передать управление далее.
И "спящий" поток просто будет временно игнорироваться, т.о. исключаясь из планирования. Пока планировщику не просигналят — что он уже готов "проснуться"
В общем то, не так все и страшно, значит...

lpd>Условная переменная работает тоже через sys_futex и переходит в режиме ядра для освобождения процессора, хотя ее тоже можно реализовать как спинлок на одних атомарных проверках в user-level.

О, вот это интересно
А можно подробнее?
Как именно условная переменная реализована? Есть ли где то примеры, как это сделать через мьютекс
Я думал что condition variable и mutex это некие фундаментальные, не сводимые друг к другу классы, оказывается, первое реализуется через второе?

Здравствуйте, barney, Вы писали:

B>т.е получается ядро просто исполняет некий набор инструкций (user mode) пока не прийдет системное прерывание таймера, или не встретится системный вызов.
B>Тогда управление перейдет в kernel. Т.е в общем случае, освободить ядро досрочно — такая же "по тяжеловесности" операция, как и истечение кванта времени, так?
B>Затем уже в ядре планировщик решает, на какой поток передать управление далее.
B>И "спящий" поток просто будет временно игнорироваться, т.о. исключаясь из планирования. Пока планировщику не просигналят — что он уже готов "проснуться"
B>В общем то, не так все и страшно, значит...

То, что здесь писали про мьютекс и исполнение инструкций pause — это неправильно.
Для освобождения процессора нужно перейти в режим ядра и передать управление системному планировщику. Планировщик сохранит регистры потока в память, полностью прекратит его исполнение, и начнет исполнять на этом ядре какой-то другой поток другого процесса, или ядерный поток, если такие ждут квантов времени. В будущем планировщик может восстановить из памяти регистры усыпленного потока, в том числе переключить таблицу страниц, и вернуть его к исполнению.
Переход в режим ядра и тем более переключение контекста на другой поток — достаточно долгие операции.

B>Я думал что condition variable и mutex это некие фундаментальные, не сводимые друг к другу классы, оказывается, первое реализуется через второе?

Это разные операции. В теории одну можно свести к другой, но это не очень удобно.
И мьютекс, и условная переменная реализуются через системный вызов sys_futex().

lpd>Переход в режим ядра и тем более переключение контекста на другой поток — достаточно долгие операции.

возникла идея безумная. вот смотрите, ведь все равно- потоки используют общую память. т.е им не нужен "защищенный режим" изоляции друг от друга
можно ли на уровне ОС сделать "user mode" потоки?
например юзермодовское прерывание таймера, которое не меняет контекст (user to kernel)?
т.о. потоки в рамках одного процесса могут быстро останавливаться — юзермод таймер прерыванием — быстро переключать стек регистров — и продолжать управление.
т.е если общий квант времени, отведенного на процесс не истек — то получим сверхшустрые потоки в рамках этого кванта

lpd>Это разные операции. В теории одну можно свести к другой, но это не очень удобно.
lpd>И мьютекс, и условная переменная реализуются через системный вызов sys_futex().

Понятно. Я так понимаю это смотреть имплементацию POSIX cond_variable в ядре линукс?