Безблокировочная многопоточность для настоящих экспертов по резьбонарезанию

Я читал ответ, который Джон Скит дал на вопрос, и в нем он упомянул следующее:

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

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

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

Ура

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если вы не фанатик только .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 .

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

Книга Джо Даффи:

http://www.bluebytesoftware.com/books/winconc/winconc_book_resources.html

Он также ведет блог на эти темы.

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

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

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

Этому положили конец два события: растущее несоответствие между скоростью RAM и CPU. И способность производителей чипов размещать на чипе более одного ядра процессора.

Проблема скорости ОЗУ потребовала, чтобы разработчики микросхем поместили буфер в микросхему ЦП. В буфере хранятся код и данные, быстро доступные ядру ЦП. И может быть прочитан и записан из / в ОЗУ с гораздо меньшей скоростью. Этот буфер называется кеш-памятью ЦП, у большинства ЦП их как минимум два. Кэш 1-го уровня маленький и быстрый, 2-й - большой и медленный. Пока ЦП может читать данные и инструкции из кеша 1-го уровня, он будет работать быстро. Промах в кеше действительно дорого обходится, он переводит ЦП в спящий режим на целых 10 циклов, если данные не находятся в 1-м кэше, и до 200 циклов, если их нет во 2-м кэше и их нужно читать из ОЗУ.

Каждое ядро ​​процессора имеет свой собственный кеш, они хранят свое «представление» об оперативной памяти. Когда ЦП записывает данные, запись производится в кеш, который затем медленно сбрасывается в ОЗУ. Неизбежно, теперь каждое ядро ​​будет иметь разное представление о содержимом ОЗУ. Другими словами, один ЦП не знает, что написал другой ЦП, пока этот цикл записи в ОЗУ не завершится и ЦП не обновит свое собственное представление.

Это совершенно несовместимо с потоком. Вы всегда на самом деле все равно , что состояние другого потока, когда вы должны прочитать данные , которые были написаны в другом потоке. Чтобы гарантировать это, вам необходимо явно запрограммировать так называемый барьер памяти. Это низкоуровневый примитив ЦП, который гарантирует, что все кэши ЦП находятся в согласованном состоянии и имеют актуальное представление об ОЗУ. Все ожидающие записи должны быть сброшены в ОЗУ, а затем необходимо обновить кеши.

Это доступно в .NET, метод Thread.MemoryBarrier () его реализует. Учитывая, что это 90% работы, которую выполняет оператор блокировки (и 95 +% времени выполнения), вы просто не впереди, избегая инструментов, предоставляемых .NET, и пытаясь реализовать свои собственные.

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

Я согласен с Джоном Скитом по этому поводу; Беспроблемная потоковая передача - это игровая площадка дьявола, и ее лучше оставить людям, которые знают, что они знают то, что им нужно знать.

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

Несмотря на то, что потоковая передача без блокировок может быть сложной в .NET, часто вы можете значительно улучшить использование блокировки, точно изучив, что именно нужно заблокировать, и минимизируя заблокированный раздел ... это также известно как минимизация гранулярности блокировки .

В качестве примера просто скажем, что вам нужно сделать коллекцию потокобезопасной. Не следует просто слепо блокировать метод, выполняющий итерацию по коллекции, если он выполняет какую-либо задачу с интенсивной загрузкой процессора для каждого элемента. Вы , возможно , нужно только поставить замок вокруг создания неполной копии коллекции. Итерация по копии может работать без блокировки. Конечно, это сильно зависит от специфики вашего кода, но с помощью этого подхода я смог исправить проблему с блокировкой .