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

Question

Я читал через ответ это Джон Скит дал ответ на вопрос, и в нем он упомянул об этом:

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

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

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

Ваше здоровье

Answer 1

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

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

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

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

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

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

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

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

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

---

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

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

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

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

... и, конечно, как @Eric упомянул, Джо Даффи является окончательным чтением по предмету.

Хороший STM может приблизиться к мелкозернистой блокировке, насколько он получает, и, вероятно, обеспечит производительность, которая находится близко или наравне с реализацией ручной работы. Один из них является St.net от Devlabs Projects MS

Если вы не Zealot только .NET, Даг Ли проделал отличную работу в JSR-166.
Клифф Клифф Имеет интересный взгляд на хэш -столы, которые не полагаются на полоску блокировки - как это делают параллельные хэш -таблицы Java и .net - и, похоже, хорошо масштабируются до 750 процессоров.

Если вы не боитесь отправиться на территорию Linux, в следующей статье дает больше понимания внутренних архитектур памяти и того, как обмен линии кеша может разрушить производительность: Что каждый программист должен знать о памяти.

@Ben сделал много комментариев о MPI: Я искренне согласен с тем, что MPI может сиять в некоторых областях. Решение на основе MPI может быть проще рассуждать, легче реализовать и менее подвержена ошибкам, чем наполовину выпеченная блокировка реализации, которая старается быть умной. (Однако это - субъективно - также верно для решения на основе STM.) Я также стараюсь, чтобы легкие годы легче правильно написать приличное распределен Применение в EG Erlang, как предполагают многие успешные примеры.

MPI, однако, имеет свои расходы и свои проблемы, когда он работает на одиночная многоядерная система. Анкет Например, в Эрланге есть проблемы, которые необходимо решить вокруг Синхронизация планирования процессов и очереди сообщений.
Кроме того, по их основу системы MPI обычно внедряют своего рода кооператив N: M планирование Для «легких процессов». Это, например, означает, что между легкими процессами неизбежно существует переключение контекста. Это правда, что это не «классический контекстный переключатель», а в основном пользовательский пространство, и его можно сделать быстро - однако я искренне сомневаюсь, что его можно принести под 20-200 циклов. Бвязанная операция занимает. Анкет Пользовательский режим переключения контекста Конечно, медленнее Даже в библиотеке Intel MCRT. N: M Планирование с легкими процессами не нова. LWP были там в Solaris в течение долгого времени. Они были заброшены. Были волокна в NT. Сейчас они в основном реликвия. Были «активации» в NetBSD. Они были заброшены. У Linux был свой собственный взгляд на тему n: m резьбы. Кажется, сейчас это несколько мертв.
Время от времени есть новые претенденты: например, MCRT от Intel, или совсем недавно Планирование пользовательского режима вместе с Захово от Microsoft.
На самом низком уровне они делают то, что делает планировщик N: M MPI. Erlang - или любая система MPI - может получить большую пользу от SMP -систем, используя новые UMS.

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

Answer 2

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

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

Он также пишет блог по этим темам.

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

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

Answer 3

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

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

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

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

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

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

Answer 4

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

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

Answer 5

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

Answer 6

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

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