Этот пост я давно откладывал. Расскажу как писал SharedMutex в yaclib (RWLock, RWMutex) для С++20 coroutines.

Что это вообще такое?
mutex, который позволяет параллельные чтения и эксклюзивные записи.
А так же может
* требовать приоритета reader над writer, наоборот, или "равенства" ("честности")
* позволять рекурсивный mutex lock
* upgrade lock, про это подробнее в комментах

Мне хотелось в первую очередь универсальное решение, так что в первом пункте я выбрал “честность”.
Рекурсивность может быть достигнута внешним кодом, а необходимость в ней на мой взгляд признак плохого дизайна.
upgrade lock – специфичная опция требующая дополнительных усилий, в которой я не заинтересован.
А еще меня устраивало ограничение в не более чем 2^32 одновременных вызовов reader/writer lock

Как добиться “честности”?
Первое, что приходит в голову, общая очередь всех lock-ов ожидающих захвата (к слову в rust tokio примерно так и реализован rwlock).
Собственно такую же идею реализовали в arangodb, что и сподвигло меня написать это нормально.

Есть ли существенные недостатки в такой имплементации? К сожалению, да.
Когда мы вызываем writer unlock и следующий, кто залочит, reader, мы хотим разбудить всех reader-ов в очереди, для этого придется пробежаться по всей очереди, что может быть медленно.
Поэтому в том же tokio будят только reader-ов из начала очереди, поэтому не параллельных критических секций может становится значительно больше чем потенциально могло быть.
Представьте очередь вида w r w r … w, то есть, в худшем случае суммарное время исполнения всех критических секций может вырасти в n раз при такой имплементации.
На практике все не так плохо, так как худшие случаи редки, а чтения обычно достаточно быстрые.

Будет неправильным не заметить, что у такой имплементации может быть очень полезное свойство, ее можно сделать аналогично mpsc vyukov queue (примерно также как в mcs spinlock, что впрочем и является в некотором виде первоисточником), то есть получить практически wait-free с полным отсутствие contention.
К сожалению я не встречал таких вменяемых реализаций, только экспериментальные rw spinlock-и на си.

То есть чтобы достичь "честности", нам понадобится две "очереди".
В одну будем класть reader-ов, в другую writer-ов.
Тогда reader unlock всегда будит 0-1 writer, а writer unlock будит либо всех reader-ов, либо 0-1 writer.

Собственно именно такая идея является основой для большинства остальных реализации: golang RWMutex, userver SharedMutex ...

"честность" контролируется тем, что мы используем в качестве reader/writer очередей (fifo/batched lifo) и кого будим в unlock-ах.

Как только это заработало, следующее о чем я подумал это fast-path, в случае отсутствия конкуренции.
Начал я с банального, добавил atomic_uint64_t счётчик – сколько сейчас writer/reader, и соответственно fast-path это cas-loop в котором я пытался его изменить:

0 w 0 r -> 1 w 0 r // writer lock
1 w 0 r -> 0 w 0 r // writer unlock
0 w n r -> 0 w n+1 r // reader lock
m w n r -> m w n-1 r // not last reader unlock
0 w 1 r -> 0 w 0 r // last reader unlock

В целом это уже неплохо, но хотелось чтобы множество reader-ов не конфликтовали в cas-loop, то есть хотелось для reader-ов делать fetch_add/sub

Я много пытался, но оно не работало правильно :)
В итоге я подсмотрел идею в golang RWMutex.
Можно завести дополнительный атомарный счетчик (reader(s) wait), который будет использоваться для синхронизации последнего reader unlock и первого writer lock.
Вообще можно подумать, а почему просто не переписать решение с golang?
Основной нюанс, то что решение в golang может за lock засыпать несколько раз, что невозможно с C++20 stackless coroutines.
Ну и как следствие моя реализация оказалась в некоторых местах более оптимальной, нет slow-path в reader unlock, а fast-path для writer lock всего лишь один cas. В golang это не так потому что реализация сделана из других примитивов (userspace аналога futex и полноценного golang Mutex).