Текущие реализации без блокировок в большинстве случаев следуют одной и той же схеме:
- * прочитайте какое-нибудь состояние и сделайте копию этого **
- * изменить копию **
- выполнить блокированную операцию
- Повторите попытку, если это не удалось
(* необязательно: зависит от структуры данных / алгоритма)
Последний бит очень похож на спинлок. На самом деле это базовый спинлок . :)
Я согласен с @nobugz в этом: стоимость операций с блокировкой, используемых в многопоточности без блокировки, , в которой преобладают задачи кеша и согласованности памяти, которые она должна выполнять .
Однако, что вы получаете с «безблокировочной» структурой данных, так это то, что ваши «блокировки» очень мелкозернистые . Это уменьшает вероятность того, что два параллельных потока получат доступ к одной и той же «блокировке» (ячейке памяти).
Уловка в большинстве случаев заключается в том, что у вас нет выделенных блокировок - вместо этого вы лечите, например, все элементы в массиве или все узлы в связанном списке как «спин-блокировка». Вы читаете, изменяете и пытаетесь обновить, если с момента вашего последнего чтения обновления не было. Если это так, повторите попытку.
Это делает ваше «блокирование» (ах, простите, не блокирующее :) очень мелкозернистым, без введения дополнительных требований к памяти или ресурсам.
Делая это более мелкозернистым, уменьшает вероятность ожидания. Звучание как можно более мелким, без дополнительных требований к ресурсам звучит замечательно, не так ли?
Большая часть удовольствия может быть получена от , обеспечивающего правильную загрузку / заказ в магазине .
Вопреки своей интуиции, процессоры могут свободно менять порядок чтения / записи памяти - кстати, они очень умные: вам будет трудно наблюдать за этим из одного потока. Однако вы столкнетесь с проблемами, когда начнете выполнять многопоточность на нескольких ядрах. Ваша интуиция сломается: просто потому, что инструкция находится в вашем коде раньше, это не значит, что она на самом деле произойдет раньше. Процессоры могут обрабатывать инструкции не по порядку: им особенно нравится делать это с инструкциями, имеющими доступ к памяти, чтобы скрыть задержку основной памяти и лучше использовать свой кэш.
Теперь, несмотря на интуицию, он уверен, что последовательность кода не передается «сверху вниз», вместо этого она работает так, как будто последовательности вообще не было - и ее можно назвать «игровой площадкой дьявола». Я полагаю, что невозможно дать точный ответ относительно того, какая перестановка заказов на загрузку / хранение будет иметь место. Вместо этого каждый всегда говорит в терминах mays и mights и can и готовится к худшему. «О, процессор может переупорядочить это чтение до этой записи, поэтому лучше поставить барьер памяти прямо здесь, на этом месте».
Вопросы осложняются тем, что даже эти mays и mights могут различаться в зависимости от архитектуры процессора. Например, может иметь место, например, то, что гарантированно не произойдет в одной архитектуре может произойти в другой.
Чтобы получить многопоточность без блокировок, вы должны понимать модели памяти.
Получение модели памяти и правильных гарантий не является тривиальным, как показывает эта история, в которой Intel и AMD внесли некоторые исправления в документацию MFENCE, что вызвало некоторое недовольство среди разработчиков JVM . Как оказалось, документация, на которую опирались разработчики с самого начала, была не совсем точной.
Блокировки в .NET приводят к неявному барьеру памяти, поэтому вы можете безопасно их использовать (большую часть времени, то есть ... см., Например, это Джо Даффи - Брэд Абрамс - Величие Вэнса Моррисона при отложенной инициализации, блокировках, энергозависимости и ограничениях памяти. :) (Обязательно перейдите по ссылкам на этой странице.)
В качестве дополнительного бонуса вы познакомитесь с моделью памяти .NET после побочного квеста . :)
Также есть «старый, но голди» от Вэнса Моррисона: Что каждый разработчик должен знать о многопоточных приложениях .
... и, конечно же, как упомянул @ Эрик , Джо Даффи - окончательное прочтение на эту тему.
Хороший STM может быть настолько близок к мелкозернистой блокировке, насколько это возможно, и, вероятно, будет обеспечивать производительность, близкую или равную производительности ручной реализации.
Одним из них является STM.NET из проектов DevLabs MS.
Если вы не фанат только для .NET, Даг Ли проделал отличную работу в JSR-166 .
Cliff Click имеет интересное представление о хеш-таблицах, которые не зависят от чередования блокировок - как это делают параллельные хеш-таблицы Java и .NET - и, похоже, хорошо масштабируются до 750 процессоров.
Если вы не боитесь выходить на территорию Linux, следующая статья дает более полное представление о внутренностях современных архитектур памяти и о том, как совместное использование строк кэша может снизить производительность: Что должен знать каждый программист о памяти .
@ Бен сделал много комментариев по поводу MPI: я искренне согласен, что MPI может светить в некоторых областях. Решение на основе MPI может быть легче рассуждать, проще в реализации и менее подвержено ошибкам, чем полусухая реализация блокировки, которая пытается быть умной. (Однако это - субъективно - также верно для решения на основе STM.) Я бы также поспорил, что световые годы легче правильно написать приличное распределенное приложение, например. Эрланг, как показывают многие успешные примеры.
MPI, однако, имеет свои собственные затраты и свои собственные проблемы, когда он работает на одноядерной многоядерной системе . Например. в Erlang существуют проблемы, которые необходимо решить в связи с синхронизацией планирования процессов и очередей сообщений .
Кроме того, в своей основе MPI-системы обычно реализуют своего рода кооперативное N: M планирование для «легких процессов». Это, например, означает, что между облегченными процессами неизбежно происходит переключение контекста. Это правда, что это не «классический переключатель контекста», а в основном операция в пользовательском пространстве, и она может быть выполнена быстро - однако я искренне сомневаюсь, что она может быть перенесена в циклы 20-200, которые блокируемая операция занимает . Переключение контекста в пользовательском режиме , безусловно, медленнее даже в библиотеке Intel McRT.
N: M планирование с легкими процессами не является новым. LWP были там в Солярисе в течение долгого времени. Они были заброшены. Были волокна в NT. Сейчас они в основном реликтовые. В NetBSD были «активации». Они были заброшены. У Linux был свой взгляд на тему потоков N: M. Кажется, он уже несколько мертв.
Время от времени появляются новые претенденты: например, McRT от Intel или совсем недавно Планирование в пользовательском режиме вместе с ConCRT от Microsoft.
На самом низком уровне они делают то, что делает планировщик N: M MPI. Erlang - или любая система MPI - может значительно выиграть в системах SMP, если использовать новую UMS .
Я полагаю, что вопрос ОП не о достоинствах и субъективных аргументах за / против какого-либо решения, но если бы мне пришлось ответить на это, я думаю, это зависит от задачи: для построения низкоуровневых, высокопроизводительных базовых структур данных, которые работать на одиночной системе с многими ядрами , либо с низкими блокировками / без блокировок, либо с STM даст лучшие результаты с точки зрения производительности и, вероятно, побьет MPI решение в любое время с точки зрения производительности, даже если вышеуказанные морщины сглажены, например, в Эрланге.
Для создания чего-то более сложного, работающего в одной системе, я бы, возможно, выбрал классическую грубую блокировку или, если производительность очень важна, STM.
Для построения распределенной системы система MPI, вероятно, сделала бы естественный выбор.
Обратите внимание, что есть реализации MPI для .NET, а также (хотя они, кажется, не так активны).