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) исполнялись другие потоки.

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