Здравствуйте, Философ, Вы писали:

Ф>Без блокировок совсем не выходит, название "lock-free" — это обман.

Всё-таки, взаимных блокировок не происходит, и это важно, бо взаимные блокировки в вытесняющей многозадачности — это злейшее зло, как выяснилось. ))
В кооперативной-однопроцессорной (одноядерной) многозадачности оно таким злом не было за невозможностью.

Вот там мьютексы были паиньками, что ими всё засрали нахрен в 80-е до 95-го, а потом как ужаснулись, когда пошло более одного ядра + вытесняющая многозадачность...


Ф>Проблема в переключении контекстов, в том что они долгие/медленные?

Да. Переключение контекстов заставляет перепрошивать внутренние таблицы виртуальной памяти, т.е. подтягивать эти таблицы, считай, в кеш 0-го уровня.
Помимо этого, переключение потока дорогое еще для потока, который вытесняют, потому что его ставят в очередь потоков, а это приоритетная очередь, операции в которой относительно затратны.

Итого, который поток уходит — его дорого убирать из-за решедуллинга.
Который поток ставят — его дорого ставить из-за переобновления таблиц виртуальной памяти.


Ф>Без блокировок совсем не выходит: другое ядро или другой процессор никаким другим способом не может синхронизировать работу с участком памяти, только блокировки, только сигнал LOCK. "lock-free" — это обман.

Никакого обмана. ))
CAS не блокирует ни один из потоков, выполняющих эту операцию над одним и тем же словом в памяти.
Просто гонку на CAS выиграет только один из потоков.

Т.е., lock-free гарантирует, что в каждый момент времени хотя бы один поток продвигается в своём исполнении.
Сравнить со столкновением потоков, где поток захватывает мьютексом или семафором ресурс, а потом ОС вытесняет этот поток и даёт тики потокам, которые этот ресурс в какой-то момент начинают ожидать. Да еще зачастую через spin-wait (как оно есть в мьютексах), а ждать там можно хоть до седьмого пришествия, только бесполезно. ))

Напротив, в lock-free алгоритмах ушедший в спячку поток никак не затормозит конкурирующие за ресурс потоки, а ровно наоборот.

Здравствуйте, Философ, Вы писали:

Ф>Без блокировок совсем не выходит, название "lock-free" — это обман.

Всё-таки, взаимных блокировок не происходит, и это важно, бо взаимные блокировки в вытесняющей многозадачности — это злейшее зло, как выяснилось. ))
В кооперативной-однопроцессорной (одноядерной) многозадачности оно таким злом не было за невозможностью.

Вот там мьютексы были паиньками, что ими всё засрали нахрен в 80-е до 95-го, а потом как ужаснулись, когда пошло более одного ядра + вытесняющая многозадачность...


Ф>Проблема в переключении контекстов, в том что они долгие/медленные?

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

Итого, который поток уходит — его дорого убирать из-за решедуллинга в очередях потоков.
Который поток ставят — его дорого ставить из-за переобновления таблиц виртуальной памяти.


Ф>Без блокировок совсем не выходит: другое ядро или другой процессор никаким другим способом не может синхронизировать работу с участком памяти, только блокировки, только сигнал LOCK. "lock-free" — это обман.

Никакого обмана. ))
CAS не блокирует ни один из потоков, выполняющих эту операцию над одним и тем же словом в памяти.
Просто гонку на CAS выиграет только один из потоков.

Т.е., lock-free гарантирует, что в каждый момент времени хотя бы один поток продвигается в своём исполнении.
Сравнить со столкновением потоков, где поток захватывает мьютексом или семафором ресурс, а потом ОС вытесняет этот поток и даёт тики потокам, которые этот ресурс в какой-то момент начинают ожидать. Да еще зачастую через spin-wait (как оно есть в мьютексах), а ждать там можно хоть до седьмого пришествия, только бесполезно. ))

Напротив, в lock-free алгоритмах ушедший в спячку поток никак не затормозит конкурирующие за ресурс потоки, а ровно наоборот.