Concurrency and Consistency. Non-blocking, lock-free and async. Пост №1. В чем разница между Blocking, Non-blocking, lock-free?

После написания десятков постов о традиционном способе синхронизации конкуррентных программ - блокирующей синхронизации, я задумался, а возможен ли другой путь? Я что-то слышал про lock-free алгоритмы, а также слышал что в распределенных системах существуют conflict-free структуры данных. Вдогонку к этому - флешбэки из десятых когда был максимальный хайп вокруг функционального программирования и отовсюда звучал тезис - "только на ФП языках получается трушный concurrency код". Что же там такого под капотом у этих языков чего нет у остальных я разобраться не успел, но у меня закрались сомнения от таких сильных заявлений, ведь какой бы не был язык все что мы пишем превращается в
- syscalls для ядра ОС написанного на С.
- инструкции для процессора.

Поэтому в новом цикле постов будем развеивать туман. Начнем с разбора основных баззвордов.

Блокирующий (blocking) вызов

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

В такие моменты исполнение инструкций потоком останавливается, поток засыпает. Разблокировка потока происходит по сигналу ОС или рантайма ЯП.

Примеры блокирующих функций:
- функции работы с сокетами (send, recv, accept)
- функции работы с файлами (fsync, fdatasync)
- синхронизация (pthread_mutex_lock, pthread_cond_wait, pthread_barrier_wait)
- sleep 😊


Неблокирующий (non-blocking) вызов

Тут все намного проще. Неблокирующая функция - та в которой нет вызовов блокирующих функций. И как следствие остановить выполнение такой функции может только ОС или рантайм языка программирования через вытесняющую многозадачность.

Как обеспечивать синхронизацию в случае когда мы не можем себе позволить засыпать и передавать контроль ОС? Ответ - Spinlocks. Потому что это примитив с активным ожиданием, то есть он заставляет потоки постоянно крутится в ожидании освобождения ресурса.


Lock-free

Понятие lock-free обычно упоминают в контексте структур данных или алгоритмов. В общем случае это код в котором
- Отсутствуют мьютексы. Как следствие невозможно уснуть и передать контроль ОС. Отсутствует блокирующая синхронизация
- Отсутствуют спинлоки. Несмотря на неблокирующую логику спинлоков у нас в программе создается ситуация эксклюзивного владения и при захвате примитива одним потоком у остальных нет возможности продвигаться и делать полезную работу.


С чем мы в итоге остаемся?

Для того чтобы строить lock-free алгоритмы и логику у нас остается только один путь - самостоятельно писать код на атомарных операциях (CAS, TAS, FAA).

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


Нужно ли стремиться к lock-free коду?

Когда мы пишем код, используем структуры данных, алгоритмы мы всегда взвешиваем все за и против. В Concurrency тоже самое.

Алгоритм / структура данных построенный на Blocking примитивах работает предсказуемо и понятно, не самый сложный код. Поддержка в любом ЯП и ОС из коробки. Для низконагруженных приложений - обязательно к использованию. Под высокой нагрузкой может стать бутылочным горлышком.

Алгоритмы и СД со спинлоками или трушные lock-free без них потенциально позволяют увеличить пропускную способность системы, но все равно существует риск пауз связанных с активным ожиданием. Плюс такие программы все таки сложнее проектировать и реализовывать. Подступаться к снаряду стоит после того как убедились что бутылочное горлышко именно в блокирующих примитивах.

На этом первый пост всё, спасибо что читали, оставляйте комментарии и реакции, чтобы я видел что вы ждали посты❤️