Многопоточность без блокировки - для настоящих экспертов
Я читал ответ, который Jon Skeet дал на вопрос, и в нем он упомянул следующее:
Насколько я понимаю, многопоточность без блокировок предназначена для настоящих экспертов по многопоточности, из которых я не один.
Это не первый раз, когда я слышал это, но я нахожу очень мало людей, говорящих о том, как вы на самом деле делаете это, если вам интересно узнать, как писать многопоточный код без блокировок.
Поэтому мой вопрос - помимо изучения всего, что вы можете о многопоточности и т. Д., С чего вы начинаете пытаться научиться специально писать многопоточный код без блокировок и какие есть хорошие ресурсы.
ура
6 ответов
Текущие реализации без блокировок в большинстве случаев следуют одной и той же схеме:
- * прочитайте некоторое состояние и сделайте копию этого **
- * изменить копию **
- выполнить блокированную операцию
- повторите попытку, если это не удалось
(* необязательно: зависит от структуры данных / алгоритма)
Последний бит очень похож на спинлок. На самом деле это базовый спинлок.:)
Я согласен с @nobugz в этом: стоимость операций с блокировкой, используемых в многопоточности без блокировки, зависит от задач кеша и согласованности памяти, которые она должна выполнять.
Однако, что вы получаете с "безблокировочной" структурой данных, так это то, что ваши "блокировки" очень мелкозернистые. Это уменьшает вероятность того, что два параллельных потока получают доступ к одной и той же "блокировке" (ячейке памяти).
Большую часть времени трюк заключается в том, что у вас нет выделенных блокировок - вместо этого вы рассматриваете, например, все элементы в массиве или все узлы в связанном списке как "спин-блокировка". Вы читаете, изменяете и пытаетесь обновить, если не было обновлений с момента вашего последнего чтения. Если было, попробуйте снова.
Это делает ваше "блокирование" (о, извините, не блокирование:) очень мелкозернистым, без введения дополнительных требований к памяти или ресурсам.
Делая это более мелкозернистым, уменьшает вероятность ожидания. Звучание как можно более мелким, без дополнительных требований к ресурсам звучит замечательно, не так ли?
Большая часть удовольствия, однако, может прийти от правильной загрузки / заказа магазина.
Вопреки своей интуиции, процессоры могут свободно менять порядок чтения / записи памяти - кстати, они очень умные: вам будет трудно наблюдать за этим из одного потока. Однако вы столкнетесь с проблемами, когда начнете выполнять многопоточность на нескольких ядрах. Ваша интуиция сломается: просто потому, что инструкция находится в вашем коде раньше, это не значит, что она на самом деле произойдет раньше. Процессоры могут обрабатывать инструкции не по порядку: и им особенно нравится делать это с инструкциями с доступом к памяти, чтобы скрыть задержку основной памяти и лучше использовать свой кэш.
Теперь против интуиции совершенно очевидно, что последовательность кода не передается "сверху вниз", вместо этого она работает так, как будто последовательности вообще не было, и ее можно назвать "игровой площадкой дьявола". Я полагаю, что невозможно дать точный ответ относительно того, какая перестановка заказов на загрузку / хранение будет иметь место. Вместо этого каждый всегда говорит с точки зрения мужчин и могил и банок и готовится к худшему. "О, процессор может переупорядочить это чтение до того, как оно будет записано, поэтому лучше поставить барьер памяти прямо здесь, на этом месте".
Вопросы осложняются тем фактом, что даже эти " маи" могут отличаться в разных архитектурах ЦП. Например, может случиться так, что то, что гарантированно не произойдет в одной архитектуре, может произойти в другой.
Чтобы получить многопоточность без блокировок, вы должны понимать модели памяти.
Получение модели памяти и правильных гарантий, однако, не тривиально, как демонстрирует эта история, в которой 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 были там в Солярисе долгое время. Они были заброшены. Были волокна в NT. Сейчас они в основном реликтовые. В NetBSD были "активации". Они были заброшены. У Linux был свой взгляд на тему потоков N:M. Кажется, он уже несколько мертв.
Время от времени появляются новые претенденты: например, McRT от Intel или совсем недавно планирование пользовательского режима вместе с ConCRT от Microsoft.
На самом низком уровне они делают то, что делает планировщик N:M MPI. Erlang - или любая система MPI - может принести большую пользу в системах SMP, используя новую UMS.
Я предполагаю, что вопрос OP не о достоинствах и субъективных аргументах за / против какого-либо решения, но если бы мне пришлось ответить на это, я думаю, это зависит от задачи: для построения низкоуровневых, высокопроизводительных базовых структур данных, которые работают на Одна система со многими ядрами, либо с низким уровнем блокировки / без блокировок, либо с STM, даст наилучшие результаты с точки зрения производительности и, вероятно, превзойдет MPI-решение в любое время с точки зрения производительности, даже если вышеуказанные складки будут устранены. например, в Эрланге.
Для создания чего-либо более сложного, работающего в одной системе, я бы, возможно, выбрал классическую грубую блокировку или, если важна производительность, STM.
Для построения распределенной системы MPI-система, вероятно, сделала бы естественный выбор.
Обратите внимание, что существуют реализации MPI и для .NET (хотя они, кажется, не так активны).
Книга Джо Даффи:
http://www.bluebytesoftware.com/books/winconc/winconc_book_resources.html
Он также пишет блог на эти темы.
Хитрость в правильном создании программ с низким уровнем блокировки заключается в том, чтобы на глубоком уровне точно понять, каковы правила модели памяти для конкретной комбинации оборудования, операционной системы и среды выполнения.
Лично я не настолько умен, чтобы правильно программировать с минимальными блокировками, кроме InterlockedIncrement, но, если вы, здорово, сделайте это. Просто убедитесь, что вы оставили много кода в коде, чтобы люди, которые не так умны, как вы, случайно не сломали один из ваших инвариантов модели памяти и не обнаружили ошибку, которую невозможно найти.
В наши дни не существует такого понятия, как "поточная обработка без блокировки". Это была интересная игровая площадка для научных кругов и тому подобное, еще в конце прошлого века, когда компьютерное оборудование было медленным и дорогим. Алгоритм Деккера всегда был моим любимым, современное оборудование выставило его на пастбище. Это больше не работает.
Два события закончились этим: растущее несоответствие между скоростью ОЗУ и процессором. И способность производителей чипов поставить более одного ядра процессора на чип.
Проблема со скоростью ОЗУ требовала, чтобы разработчики микросхем поместили буфер в микросхему процессора. В буфере хранятся код и данные, быстро доступные ядру процессора. И может быть прочитан и записан из / в ОЗУ с гораздо меньшей скоростью. Этот буфер называется кэшем ЦП, большинство ЦП имеют как минимум два из них. Кэш 1-го уровня маленький и быстрый, второй - большой и медленный. Пока процессор может читать данные и инструкции из кэша 1-го уровня, он будет работать быстро. Промах кеша действительно дорогой, он переводит ЦП в спящий режим на 10 циклов, если данные не находятся в 1-м кеше, и на 200 циклов, если он не находится во 2-м кеше, и его необходимо прочитать из БАРАН.
Каждое ядро ЦП имеет свой кэш, они хранят свой собственный "вид" оперативной памяти. Когда процессор записывает данные, запись производится в кэш, который затем медленно сбрасывается в RAM. Неизбежно, каждое ядро теперь будет иметь различное представление о содержимом оперативной памяти. Другими словами, один ЦП не знает, что написал другой ЦП, пока этот цикл записи в ОЗУ не завершится и ЦП не обновит свое собственное представление.
Это совершенно несовместимо с потоками. Вам всегда действительно важно, в каком состоянии находится другой поток, когда вы должны прочитать данные, которые были записаны другим потоком. Для этого вам нужно явно запрограммировать так называемый барьер памяти. Это низкоуровневый примитив ЦП, который гарантирует, что все кэши ЦП находятся в согласованном состоянии и имеют современное представление ОЗУ. Все ожидающие записи должны быть сброшены в ОЗУ, затем необходимо обновить кэши.
Это доступно в.NET, метод Thread.MemoryBarrier() реализует его. Учитывая, что это 90% работы, которую выполняет оператор блокировки (и 95+% времени выполнения), вы просто не впереди, избегая инструментов, которые предоставляет вам.NET, и пытаясь реализовать свои собственные.
Google для блокировки свободных структур данных и программного обеспечения транзакционной памяти.
Я согласен с Джоном Скитом в этом; Потоки без блокировки - это игровая площадка дьявола, и лучше всего оставить ее людям, которые знают, что они знают, что им нужно знать.
Когда дело доходит до многопоточности, вы должны точно знать, что вы делаете. Я имею в виду изучить все возможные сценарии / случаи, которые могут возникнуть при работе в многопоточной среде. Многопоточность без блокировок - это не библиотека или класс, который мы включаем, это знания / опыт, которые мы получаем во время нашего путешествия по потокам.
Несмотря на то, что многопоточность без блокировок может быть затруднена в.NET, часто вы можете добиться значительных улучшений при использовании блокировки, изучая в точности то, что нужно заблокировать, и минимизируя заблокированный раздел... это также известно как минимизация степени детализации блокировки.
Например, просто скажите, что вам нужно сделать поток коллекции безопасным. Не просто слепо бросайте блокировку вокруг метода, выполняющего итерацию по коллекции, если он выполняет некоторую нагрузку на процессор для каждого элемента. Вам может потребоваться только поставить блокировку вокруг создания мелкой копии коллекции. Итерация по копии может работать без блокировки. Конечно, это сильно зависит от специфики вашего кода, но я смог исправить проблему с конвоем блокировки с помощью этого подхода.