Ответ 1
Существующие "незакрепленные" реализации в большинстве случаев следуют за одним и тем же шаблоном:
- * прочитайте некоторое состояние и сделайте его копию **
- * изменить копию **
- выполнить операцию блокировки
- повторить попытку, если он не работает
(* необязательно: зависит от структуры/алгоритма данных)
Последний бит ужасно похож на спин-блокировку. Фактически, это основной spinlock.:)
Я согласен с @nobugz в этом: стоимость взаимосвязанных операций, используемых в бесключевой многопоточности, в которой доминируют задачи кэширования и памяти, которые она должна выполнять,
Однако вы получаете, однако, структуру данных, которая является "незакрепленной", так это то, что ваши "блокировки" очень мелкие. Это уменьшает вероятность того, что два параллельных потока обращаются к одной и той же "блокировке" (ячейке памяти).
Фокус в большинстве случаев заключается в том, что у вас нет выделенных блокировок - вместо этого вы лечите, например. все элементы в массиве или все узлы в связанном списке как "spin-lock". Вы читаете, изменяете и пытаетесь обновить, если обновление не было после вашего последнего чтения. Если есть, повторите попытку.
Это делает вашу "блокировку" (о, извините, не блокирует:) очень мелкозернистую, не вводя дополнительную память или требования к ресурсам.
Чем более мелкозернистый, тем меньше вероятность ожидания. Сделать его как можно более мелким, без дополнительных требований к ресурсам, здорово, не так ли?
Большая часть удовольствия, однако, может исходить от обеспечения правильной загрузки/сохранения магазина.
В отличие от одной интуиции, процессоры могут свободно изменять порядок чтения/записи в памяти - они очень умны, кстати: вам будет трудно наблюдать это из одного потока. Вы, однако, столкнетесь с проблемами, когда начинаете многопоточность на нескольких ядрах. Ваши интуиции сломаются: просто потому, что инструкция ранее в вашем коде, это не означает, что это произойдет на самом деле раньше. Процессоры могут обрабатывать инструкции не по порядку: и они особенно любят делать это с инструкциями с обращениями к памяти, чтобы скрыть затухание основной памяти и лучше использовать их кеш.
Теперь, убежденный против интуиции, что последовательность кода не течет "сверху вниз", вместо этого она работает так, как будто не было никакой последовательности - и ее можно назвать "дьявольской площадкой". Я считаю, что невозможно дать точный ответ на вопрос о том, какие переупорядочения груза/магазина будут иметь место. Вместо этого, каждый всегда говорит с точки зрения мейсов, мотивов и банок и готовится к худшему. "О, CPU может переупорядочить это чтение до того, как он напишет, поэтому лучше всего поставить здесь барьер памяти на этом месте".
Вопросы осложняются тем, что даже эти mays и mights могут различаться по архитектуре CPU. Например, может случиться так, что что-то, что гарантировано не произойдет в одной архитектуре, может случиться с другой.
Чтобы получить "незащищенную" многопоточность, вам нужно понять модели памяти.
Однако получение модели памяти и гарантий правильности не является тривиальным, о чем свидетельствует эта история, в которой Intel и AMD внесли некоторые исправления в документацию MFENCE, вызвав некоторые разжигание среди разработчиков JVM. Как оказалось, документация, на которую разработчики полагались с самого начала, была не столь точной в первую очередь.
Замки в .NET приводят к неявному барьеру памяти, поэтому вы можете безопасно их использовать (большую часть времени, то есть... см., например, это Joe Duffy - Brad Abrams - Vance Morrison greatness о ленивой инициализации, блокировках, летучих и барьерах памяти.:) (Не забудьте следовать ссылкам на этой странице.)
В качестве дополнительного бонуса вы получите представление о модели памяти .NET на стороннем квесте.:)
Существует также "oldie but goldie" от Vance Morrison: Что каждый Dev должен знать о многопоточных приложениях.
... и, конечно, как упоминалось @Eric, Joe Duffy является окончательным чтением по этому вопросу.
Хорошая STM может приблизиться к мелкозернистой блокировке по мере ее поступления и, вероятно, обеспечит производительность, близкую или эквивалентную реализации вручную. Одним из них является STM.NET из Проекты DevLabs MS.
Если вы не просто фанатик .NET, Дуг Ли сделал отличную работу в JSR-166. Cliff Click имеет интересный подход к хеш-таблицам, который не полагается на блокировку-striping - как это делают обычные хэш-таблицы Java и .NET - и похоже, хорошо масштабируются до 750 процессоров.
Если вы не боитесь рисковать на территорию Linux, следующая статья дает больше информации о внутренних компонентах существующих архитектур памяти и о том, как совместное использование кеш-памяти может разрушить производительность: Что каждый программист должен знать о памяти.
@Ben сделал много комментариев о MPI: я искренне согласен с тем, что MPI может сиять в некоторых областях. Решение на основе MPI может быть проще рассуждать, проще реализовать и с меньшей степенью подверженности ошибкам, чем реализация с половинной выдержкой блокировки, которая пытается быть умной. (Тем не менее - субъективно - также верно для решения на основе STM.) Я также хотел бы сделать ставку на то, что легче на лету легче правильно писать достойное распределенное приложение, например. Эрланг, как показывают многие успешные примеры.
MPI, однако, имеет свои собственные затраты и собственные проблемы, когда он запускается в одной многоядерной системе. Например. в Erlang существуют проблемы, которые необходимо решить вокруг синхронизации планирования процессов и очередей сообщений.
Кроме того, в их основе, MPI-системы обычно реализуют своего рода кооперативный N: M scheduling для "легких процессов". Это, например, означает, что между легкими процессами существует неизбежный контекст. Это правда, что это не "классический контекстный переключатель", а в основном операция с пользовательским пространством, и это можно сделать быстро, однако я искренне сомневаюсь, что он может быть приведен в 20-200 циклов, выполняемых с блокировкой. Переключение контекста пользовательского режима конечно медленнее даже в библиотеке Intel McRT.
Планирование N: M с легкими процессами не нова. LWPs были в Solaris в течение длительного времени. Они были оставлены. В NT были волокна. Сейчас они являются реликвией. В NetBSD были "активизации". Они были оставлены. У Linux был свой собственный подход к потоку N: M. Похоже, что он уже несколько мертв.
Время от времени появляются новые соперники: например McRT от Intel или последний раз "Планирование пользовательского режима" вместе с ConCRT от Microsoft.
На самом низком уровне они выполняют то, что делает планировщик N: M MPI. Erlang - или любая система MPI - может сильно повлиять на системы SMP, используя новый UMS.
Я думаю, что вопрос OP не касается достоинств и субъективных аргументов для/против какого-либо решения, но если бы я должен был ответить на это, я полагаю, это зависит от задачи: для построения низкоуровневых высокопроизводительных базовых структур данных, которые работайте в единой системе со многими ядрами, либо с помощью технологии с низким уровнем блокировки/ "без блокировки", либо с помощью STM обеспечит наилучшие результаты с точки зрения производительности и, вероятно, будет бить MPI-решение в любое время по производительности, даже если вышеуказанные морщины сглаживаются, например в Эрланг.
Для создания чего-либо умеренно более сложного, который работает на одной системе, я бы выбрал классическую крупнозернистую блокировку или если производительность вызывает большую озабоченность, STM.
Для создания распределенной системы, система MPI, вероятно, сделает естественный выбор.
Обратите внимание, что реализация MPI для .NET также (хотя они, похоже, не так активны).