Comments 6
Тут стоит обратить внимание на путаницу в терминах. Lock-free алгоритмы раньше назывались неблокирующими. Теперь же они считаются лишь частным случаем неблокирующих. Но на самом деле это всё же механизм хоть и оптимистичной, но блокировки.
Здесь нет никакой путанницы, есть вполне четкие определения для блокирующих и lock-free алгоритмов. Можно например почитать здесь: Lock-Free and Wait-Free, definition and examples.
Wait-free алгоритмы межпоточного взаимодействия основаны на той же идее — отсутствие конкуренции за общий ресурс.
В общем случае - это не так. Например атомарное изменение счетчтка - это wait free операция над общим ресурсом.
ИМХО, это была неудачная идея смешивать в кучу concurrency и распределенные системы. Несмотря на то, что многопроцессорную систему можно рассматривать как распределенную, здесь есть принципиальное отличие: соединение между узлами надежное и доставка сообщений по шине гарантирована. С точки зрения CPU нет никакой неопределенности, каждый узел находится в состоянии определенном протоколом (MESI, MOESI, etc.) и система всегда находится в состоянии консенсуса. Поэтому читать про проблему византийский генералов сразу после секции о многопоточности весьма странно.
Это другая, не самая удачная классификация. Собственно в примерах кода вы там можете у локфри наблюдать бесконечный цикл, что эффективно является блокировкой. Пока один тред активно меняет значение, другой висит заблокированным.
Атомарное изменение счётчика приводит ко блокировке на уровне процессорных ядер на сколько я понимаю. Ведь это read-modify-write операция.
Доставка может и гарантирована, но вот время этой доставки варьируется. А задержавшееся слишком на долго сообщение малоотличимо от недоставленного.
Очень странно что вам странно читать про задачу генералов после упоминания протоколов консенсуса, применяемых между ядрами процессора.
Это другая, не самая удачная классификация.
Вы считаете, что классификация описанная в статье и книге "The Art of Multiprocessor Programming" неудачная? Приведите, пожалуйста, аргументы почему.
Собственно в примерах кода вы там можете у локфри наблюдать бесконечный цикл, что эффективно является блокировкой
Нет, blocking, lock-free, wait-free это про гарантии прогресса алгортима, а не время обработки. В случае блокировок если процесс/поток захвативший лок зависнет, никакой другой поток не сможет продолжить, в отличие от lock-free который выполнится за конечное число шагов.
Атомарное изменение счётчика приводит ко блокировке на уровне процессорных ядер на сколько я понимаю. Ведь это read-modify-write операция.
И тем не менее - это wait-free операция, которая завершится за определенное количество циклов.
Доставка может и гарантирована, но вот время этой доставки варьируется. А задержавшееся слишком на долго сообщение малоотличимо от недоставленного.
Это как? Я вычитал значение переменной и оно как-то не доставилось или слишком долго? Операция чтения из памяти может потребовать разное количество циклов для завершения, но когда оно закончится значение будет гарантировано доставлено.
Очень странно что вам странно читать про задачу генералов
Да, потому что задача про византийских генералов - это задача в которой присутствует ненадежный канал связи который не доставляет(или подменяет) сообщения. В процессорах такой проблемы нет.
Эта классификация развивалась стихийно и термины вводились абы как. Потом определения подгонялись уже под практику использования. Ну реально, какое отношение имеет "засыпание потока" к "блокировке исполнения"? Да никакого. Поток может и без засыпания бесконечной долбёжкой заблокировать другие потоки навсегда даже при lock-free. А может и вообще никогда не засыпать - это ж не сделает mutex неблокирующим.
Разделение на "конечное неограниченное" и "конечное ограниченное" - это тоже бессмыслица. Всё, что не ограничено, - потенциально бесконечно. Отсутствие ограничения - это просто определение потенциальной бесконечности.
Число циклов для инкремента счётчика в лучшем случае (если применяется балансировка) пропорционально числу ядер. Причём всё это время, на сколько я понимаю, ядро висит заблокированным. Это не wait-free и даже не lock-free.
А что толку от доставленного сообщения, если битва уже произошла? Слишком поздно доставленное сообщение может быть уже никому не интересно. Ну, в случае процессоров, это актуально лишь для систем реального времени.
. Ну реально, какое отношение имеет "засыпание потока" к "блокировке исполнения"? Да никакого. Поток может и без засыпания бесконечной долбёжкой заблокировать другие потоки навсегда даже при lock-free.
Тем не менее - именно такое общепринятое толкование Non-blocking algorithm. Если в вашей статье подразумевается какое-то другое, дайте пожалуйста ссылку на определение.
Число циклов для инкремента счётчика в лучшем случае (если применяется балансировка) пропорционально числу ядер.
Это зависит, конечно, от архитектуры, но на популярных если ядро владеет кеш линией (exclusive) инкрементирование счетчика бесплатно. Для других ядер будет пенальти.
А что толку от доставленного сообщения, если битва уже произошла? Слишком поздно доставленное сообщение может быть уже никому не интересно.
Т.е. вы считаете, что нет приниципаильной разницы между синхроным и ассинхронным вызовом, надежной и ненадежной доставкой?
Консистентно о Консенсусе