Concurrency and Consistency. Non-blocking, lock-free and async. Пост №3. Что существует кроме Lock-Free? Гарантии в блокирующей и неблокирующей синхронизации.

В посте №1 я дал определение понятию lock-free. Дальше сразу пошёл разбирать ABA-проблему, и это было ошибкой. Всё-таки важный кусочек базы я упустил, поэтому делаю шаг назад.

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

- Примитив обеспечивал эксклюзивный доступ к критической секции - это гарантия mutual exclusion и, по сути, гарантия безопасности нашего кода.
- В нашем коде отсутствовали взаимоблокировки - это гарантия deadlock freedom.
- Поток, намеревающийся попасть в критическую секцию, гарантированно попадал в неё за конечное время - это гарантия starvation freedom.

За дедлоки обычно отвечает программист, гарантии отсутствия голодания обычно падают на рантайм языка программирования (потому что в нём реализован примитив синхронизации) и рантайм ОС, потому что он планирует исполнение потоков.

А какие есть гарантии в неблокирующей синхронизации?

- Гарантия отсутствия препятствий (Obstruction-free): если поток активен и у него нет конкурентов, он должен исполнять полезные инструкции, демонстрировать прогресс.
- Гарантия отсутствия блокировок (Lock-free): наш код гарантирует, что в случае конкурентного исполнения кто-то обязательно достигнет прогресса.
- Гарантия отсутствия ожидания (Wait-free): каждый поток завершает операцию за ограниченное число шагов, независимо от того, что делают другие потоки.

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

P.S. Канал переходит в режим Wait-Free, теперь посты гарантированно будут публиковаться за конечное количество дней😁 Я вернулся.