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

86

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

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

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

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

Ура

вдхант
источник
Я использую платформы gcc, linux и X86 / X68. Lock-free не так сложно, как все говорят! Встроенные функции gcc atomic имеют барьеры памяти для Intel, но в реальной жизни это не имеет значения. Важно то, что память модифицируется атомарно. Когда вы проектируете структуры данных без блокировок, это просто потрясающе, что не имеет значения, когда другой поток видит изменение. Односвязные списки, списки пропуска, хеш-таблицы, свободные списки и т. Д. Довольно легко сделать без блокировки. Lock free не для всех. Это просто еще один инструмент, который подходит для определенных ситуаций.
johnnycrash
2
1024cores.net
Манкарс
Голосование за закрытие в качестве рекомендации ресурса или непонятно, о чем вы спрашиваете.
Чиро Сантилли 郝海东 冠状 病 六四 事件

Ответы:

100

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

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

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

Последний бит очень похож на спин-блокировку. Фактически, это простая спин-блокировка . :)
Я согласен с @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 (хотя они, похоже, не так активны).

Андраш Васс
источник
1
Хотя этот ответ содержит много полезной информации, основная идея о том, что алгоритмы без блокировок и структуры данных, по сути, представляют собой просто набор очень мелких спин-блокировок, неверна. Хотя вы обычно видите циклы повтора в структурах без блокировок, поведение сильно отличается: блокировки (включая спин-блокировки) исключительно захватывают некоторый ресурс, и другие потоки не могут выполнять работу, пока он удерживается. «Повтор» в этом смысле просто ожидает освобождения эксклюзивного ресурса.
BeeOnRope 01
1
С другой стороны, алгоритмы без блокировок используют CAS или другие атомарные инструкции не для получения эксклюзивного ресурса, а для завершения некоторой операции. Если они терпят неудачу, это происходит из-за мелкозернистой гонки с другим потоком, и в этом случае другой поток добился прогресса (завершил свою операцию). Если поток является неопределенно подозрительным, все остальные потоки все еще могут работать. Это как качественно, так и по производительности сильно отличается от эксклюзивных замков. Количество "повторных попыток" обычно очень мало для большинства CAS-петель даже в условиях сильной конкуренции ...
BeeOnRope 01
1
... но это, конечно, не означает хорошего масштабирования: конкуренция за одну ячейку памяти всегда будет довольно медленной на машинах SMP только из-за межъядерных задержек между сокетами, даже если количество отказов CAS равно низкий.
BeeOnRope 01
1
@AndrasVass - Я думаю, это зависит также от "хорошего" и "плохого" кода блокировки. Конечно, любой может написать структуру и назвать ее свободной от блокировок, хотя на самом деле она просто использует спин-блокировку пользовательского режима и даже не соответствует определению. Я также рекомендую всем заинтересованным читателям ознакомиться с этой статьей Херлихи и Шавита, в которой формально рассматриваются различные категории алгоритмов на основе и без блокировки. Все, что Херлихи по этой теме, также рекомендуется прочитать.
BeeOnRope 05
1
@AndrasVass - я не согласен. Большинство классических структур без блокировки (списки, очереди, параллельные карты и т. Д.) Не вращались даже для совместно используемых изменяемых структур, а практические существующие реализации того же, например, в Java, следуют тому же шаблону (я не такой знакомы с тем, что доступно в скомпилированных в собственном коде C или C ++, и там сложнее из-за отсутствия сборки мусора) Возможно, у нас с вами другое определение вращения: я не считаю «повторную попытку CAS», которую вы найдете в блокировках, «вращением». ИМО "раскрутка" подразумевает горячее ожидание.
BeeOnRope 05
27

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

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

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

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

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

Эрик Липперт
источник
38
Так что если и Эрик Липперт, и Джон Скит думают, что программирование без блокировок предназначено только для людей умнее их самих, тогда я смиренно убегу, крича, от этой идеи. ;-)
dodgy_coder
20

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

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

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

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

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

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

Ганс Пассан
источник
2
@ Davy8: состав делает это по-прежнему сложно. Если у меня есть две хэш-таблицы без блокировки и я как потребитель обращаюсь к ним обе, это не гарантирует согласованности состояния в целом. Самое близкое, что вы можете сделать сегодня, - это STM, где вы можете поместить два доступа, например, в один atomicблок. В общем, использование структур без блокировок во многих случаях может оказаться столь же сложной задачей.
Андраш Васс
4
Возможно, я ошибаюсь, но я думаю, что вы неправильно объяснили, как работает согласованность кеша. Большинство современных многоядерных процессоров имеют согласованные кеши, что означает, что аппаратное обеспечение кэширования обеспечивает одинаковое представление содержимого ОЗУ для всех процессов - путем блокирования вызовов «чтения» до завершения всех соответствующих вызовов «записи». Документация Thread.MemoryBarrier () ( msdn.microsoft.com/en-us/library/… ) вообще ничего не говорит о поведении кеша - это просто директива, которая не позволяет процессору переупорядочивать операции чтения и записи.
Brooks Moses
7
«В наши дни не существует такой вещи, как« потоковая передача без блокировки »». Расскажите об этом программистам на Erlang и Haskell.
Juliet
4
@HansPassant: «В наши дни не существует такой вещи, как« потоковая передача без блокировки »». F #, Erlang, Haskell, Cilk, OCaml, Microsoft Task Parallel Library (TPL) и Intel Threaded Building Blocks (TBB) - все они поддерживают многопоточное программирование без блокировок. В наши дни я редко использую блокировки в производственном коде.
JD
5
@HansPassant: так называемый барьер памяти. Это низкоуровневый примитив ЦП, который гарантирует, что все кеши ЦП находятся в согласованном состоянии и имеют актуальное представление об ОЗУ. Все ожидающие записи должны сбрасываться в ОЗУ, затем необходимо обновить кеши ". Барьер памяти в этом контексте предотвращает переупорядочивание инструкций памяти (загрузки и сохранения) компилятором или процессором. Ничего общего с согласованностью кешей ЦП.
JD
6

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

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

Марсело Кантос
источник
0

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

хвастун
источник
Существует множество библиотек, которые обеспечивают семантику потоковой передачи без блокировки. Особый интерес представляет STM, реализации которого существует довольно много.
Марсело Кантос,
Я вижу обе стороны этого. Получение эффективной производительности из библиотеки без блокировки требует глубоких знаний моделей памяти. Но программист, не обладающий этими знаниями, все равно может извлечь выгоду из преимуществ корректности.
Бен Фойгт
0

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

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

dodgy_coder
источник