На основе прочитанных статей и материалов у меня в голове выстроились некоторые связи и закономерности, ими и хочу поделиться с вами:
- Фиксация количества потоков в Wait-Free. В отличии от lock-free и mutex реализаций wait-free структура должна заранее знать сколько конкурентных участников в системе (потоков). Нужно для того чтобы гарантировать фиксированное количество итераций (вместо бесконечных циклов).
- Потоки кооперируют а не конкурируют. Вместо блокировки и борьбы за ресурс участники подхватывают промежуточные состояние друг друга и доводят их до завершения. За счет этого достигается lock-free семантика. Реализуется через cхему "анонсирования изменений" во внутренностях алгоритма (термин - announce array в литературе)
- Для wait-free важна не только кооперация но и приоритеты. Сама по себе кооперация не дает гарантию wait-free но если ее приправить механикой приоритетов это то что гарантирует честность и очередность.
- Работа с памятью. SMR (Safe Memory Reclamation) это отдельная ось исследований. Ведь у нас структура данных над общей памятью и мы ничем не защищаем её. Если в языках с GC эту боль на себя забирает рантайм (ценой перформанса, и в худшем случае потерей статуса wait-free), то в C++ / Rust работа с памятью на плечах программиста. Благо существуют алгоритмы и подходы к этой задаче:
- Подсчет ссылок (
std::shared_ptr и std::atomic<shared_ptr>)- Hazard Pointers (
std::hazard_pointer)- Quiescent State-Based Reclamation. Реализован внутри языках Linux а также nogil версии Python (пруф)
- Epoch-based Reclamation.
crossbeam-epoch в Rust.Также стоит помнить про аллокаторы памяти. Это тоже алгоритм и он является частью нашей программы. И если у него под капотом есть блокировки то наши ухищрения потеряют смысл.