Свободная от блокировок многопоточность является настоящей экспертов по поточной обработке

Текущие реализации "без блокировок" большую часть времени следуют одному и тому же шаблону:

• * прочтите некоторые состояние и сделать его копию **
• * изменить копию **
• выполнить заблокированную операцию
• повторить попытку, если она не удалась

_{(* необязательно: зависит от структуры данных / алгоритма)}

Последний бит пугающе похож на спин-блокировку. Фактически, это базовая спин-блокировка . :)
Я согласен с @nobugz в этом: стоимость взаимосвязанных операций, используемых в многопоточности без блокировки, во многом зависит от задач кэширования и согласования памяти, которые он должен выполнять .

Однако вы получаете "свободную от блокировок" структуру данных, так это то, что ваши "блокировки" очень мелкие . Это снижает вероятность того, что два параллельных потока обращаются к одной и той же «блокировке» (области памяти).

В большинстве случаев уловка заключается в том, что у вас нет специальных блокировок - вместо этого вы обрабатываете, например, все элементы в массиве или все узлы в связанном списке как «спин-блокировка». Вы читаете, изменяете и пытаетесь обновить, если с момента последнего чтения обновлений не было. Если было, попробуйте еще раз.
Это делает вашу "блокировку" (о, извините, неблокирующую :) очень мелкой, без дополнительных требований к памяти или ресурсам.
Повышение детализации снижает вероятность ожидания.Сделать его как можно более детализированным без введения дополнительных требований к ресурсам - это здорово, не правда ли?

Однако большая часть удовольствия может исходить от обеспечения правильного порядка загрузки / сохранения .
Вопреки интуиции, процессоры могут свободно переупорядочивать операции чтения / записи в память - кстати, они очень умны: вам будет трудно наблюдать это из одного потока. Однако вы столкнетесь с проблемами, когда начнете использовать многопоточность на нескольких ядрах. Ваша интуиция сломается: просто потому, что инструкция находится раньше в вашем коде, это не означает, что это на самом деле произойдет раньше. ЦП могут обрабатывать инструкции не по порядку: и им особенно нравится делать это с инструкциями с доступом к памяти, чтобы скрыть задержку основной памяти и лучше использовать свой кеш.

Конечно, вопреки интуиции, последовательность кода не течет «сверху вниз», вместо этого она выполняется так, как будто никакой последовательности вообще не было - и может быть названа «игровой площадкой дьявола». Я считаю, что невозможно дать точный ответ о том, какие переупорядочения загрузки / магазина будут иметь место. Вместо этого всегда говорят о майах и майах и банках и готовятся к худшему. «О, ЦП мог бы переупорядочить это чтение, чтобы оно происходило перед этой записью, поэтому лучше всего поставить барьер памяти прямо здесь, на этом месте»

Ситуация осложняется тем фактом, что даже эти mays и mights могут различаться в зависимости от архитектуры процессора.Например, может случиться так, что что-то, что гарантированно не произойдет в одной архитектуре , может произойти в другой.

Чтобы получить правильную "свободную от блокировок" многопоточность, вы должны понимать модели памяти.
Получение правильной модели памяти и гарантий не является тривиальным делом, однако, как показано в этой истории, когда Intel и AMD внесли некоторые исправления в документацию MFENCE , вызвав некоторое волнение. -up среди разработчиков JVM . Как оказалось, документация, на которую разработчики полагались с самого начала, изначально была не такой уж точной.

Блокировки в .NET приводят к неявному барьеру памяти, поэтому вы можете безопасно использовать их (большую часть времени, то есть ... см., Например, это Джо Даффи - Брэд Абрамс - величие Вэнса Моррисона о ленивой инициализации, блокировках, нестабильности и барьерах памяти. :) (Обязательно следуйте ссылкам на этой странице.)

В качестве дополнительного бонуса вы познакомитесь с моделью памяти .NET во время побочного квеста. . :)

Есть также "старое, но золотое" от Вэнса Моррисона: Что должен знать каждый разработчик о многопоточных приложениях .

... и, конечно же, как упомянул @Eric , Джо Даффи является исчерпывающим читателем по этой теме.

Хороший STM может максимально приблизиться к детальной блокировке и, вероятно, обеспечит производительность, близкую или равную производительности ручной реализации. Один из них - STM.NET из проектов DevLabs MS.

Если вы не a.Зилот, работающий только с NET, Дуг Ли проделал большую работу над JSR-166 .
Cliff Click предлагает интересный подход к хеш-таблицам, который не полагается на чередование блокировок - как это делают параллельные хеш-таблицы Java и .NET - и, кажется, хорошо масштабируется до 750 процессоров.

Если вы не боитесь проникать на территорию Linux,В следующей статье дается больше информации о внутреннем устройстве текущих архитектур памяти и о том, как совместное использование строк кэша может снизить производительность: Что каждый программист должен знать о памяти .

@Ben сделал много комментариев по поводу MPI: Я искренне согласен с тем, что MPI может хорошо проявить себя в некоторых областях. Решение, основанное на MPI, может быть проще в рассуждении, проще в реализации и менее подвержено ошибкам, чем реализация полусырой блокировки, которая пытается быть умной. (Однако - субъективно - это верно и для решения на основе STM.) Я также готов поспорить, что на несколько световых лет легче правильно написать достойное распределенное приложение, например, Erlang, как показывают многие успешные примеры.

MPI, однако, имеет свои издержки и свои проблемы, когда он запускается в одноядерной многоядерной системе . Например. в Erlang есть проблемы, которые необходимо решить, связанные с синхронизацией планирования процессов и очередей сообщений .
Кроме того, в своей основе системы MPI обычно реализуют своего рода совместное N: M планирование для «облегченных процессов». Это, например, означает неизбежное переключение контекста между легковесными процессами. Это правда, что это не «классический переключатель контекста», а в основном операция в пользовательском пространстве, и ее можно сделать быстро - однако я искренне сомневаюсь, что ее можно выдержать 20-200 циклов, которые требуется для операции с блокировкой . Переключение контекста в пользовательском режиме определенно медленнее даже в библиотеке Intel McRT. N: M планирование с облегченными процессами не новость.LWP существовали в Solaris очень давно. Они были заброшены. Были волокна в NT. Сейчас они в основном реликвии. В NetBSD были «активации». Они были заброшены. В Linux был свой собственный взгляд на потоки N: M. Кажется, сейчас он несколько мертв.
Время от времени появляются новые претенденты: например, McRT от Intel или совсем недавно User-Mode Scheduling вместе с ConCRT от Microsoft.
На самом низком уровне они делают то же, что и планировщик N: M MPI. Erlang - или любая система MPI - может значительно выиграть в системах SMP, используя новую UMS .

Думаю, вопрос ОП не касается достоинств и субъективных аргументов за / против любого решения, но если бы мне пришлось ответить на этот вопрос, я полагаю, это зависит от задачи: для создания низкоуровневых высокопроизводительных базовых структур данных, которые работать в одиночной системе с многими ядрами , либо методы low-lock / «lock-free», либо STM дадут лучшие результаты с точки зрения производительности и, вероятно, превзойдут MPI решение в любое время с точки зрения производительности, даже если вышеупомянутые морщины разгладятся, например в Эрланге.
Для создания чего-либо умеренно более сложного, работающего в одной системе, я, возможно, выбрал бы классическую крупномасштабную блокировку или, если производительность имеет большое значение, STM.
Для построения распределенной системы система MPI, вероятно, станет естественным выбором.
Обратите внимание, что существуют реализации MPI для .NET, а также (хотя они кажутся не такими активными).