Как я могу написать структуру без блокировки?

Question

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

Как я могу написать структуру без блокировки?

Answer 1

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

Например, в настоящее время я работаю над многопоточным приложением, в котором есть настраиваемая система обмена сообщениями (список очередей для каждого потока, очередь содержит сообщения для обработки потоком) для передачи информации между потоками. Существует глобальная блокировка этой структуры. В моем случае мне не нужна скорость, поэтому это не имеет значения. Но если эта блокировка станет проблемой, она может быть заменена отдельными блокировками в каждой очереди, например. Тогда добавление / удаление элемента в / из определенной очереди не повлияет на другие очереди. Все еще была бы глобальная блокировка для добавления новой очереди и тому подобного, но это не было бы настолько оспариваемым.

Даже отдельная очередь для нескольких производителей / потребителей может быть записана с гранулярной блокировкой для каждого элемента вместо глобальной блокировки. Это также может устранить раздоры.

Answer 2

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

Answer 3

Основной принцип синхронизации без блокировки таков:

• всякий раз, когда вы читаете структуру, вы следите за чтением с помощью теста, чтобы увидеть, не изменилась ли структура с тех пор, как вы начали чтение, и повторяйте попытки, пока вы не преуспеете в чтении, пока что-то еще не появится и не будет мутировать, пока вы при этом;

• всякий раз, когда вы изменяете структуру, вы упорядочиваете свой алгоритм и данные таким образом, чтобы был один атомарный шаг, который, в случае его выполнения, заставляет все изменение становиться видимым для других потоков, и упорядочивает вещи так, чтобы ничего не происходило. изменения видны, если этот шаг не сделан. Для этого шага вы используете любой атомный механизм без блокировки на вашей платформе (например, сравнение и установка, привязка к нагрузке + условное хранение и т. Д.). На этом шаге вы должны затем проверить, не мутировал ли какой-либо другой объект объект с момента начала операции мутации, зафиксировать, если это не так, и начать заново, если он это сделал.

В сети существует множество примеров структур без блокировки; не зная больше о том, что вы реализуете и на какой платформе трудно быть более конкретным.

Answer 4

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

См. здесь для канонической статьи на эту тему.

Также попробуйте эту статью в Википедии статью для дальнейших идей и ссылок.

Answer 5

Если вы прочитаете несколько реализаций и статей по теме, вы заметите, что есть следующая общая тема:

1) Объекты общего состояния имеют неизменяемый стиль lisp / clojure : все операции записи выполняются, копируя существующее состояние в новый объект, вносят изменения в новый объект и затем пытаются обновить общее состояние (получено из выровненного указателя, который может быть обновлен с помощью примитива CAS). Другими словами, вы НИКОГДА не изменяете существующий объект, который может быть прочитан больше, чем текущий поток. Неизменяемость может быть оптимизирована с использованием семантики копирования при записи для больших и сложных объектов, но это еще одно дерево орехов

2) вы четко указываете, какие допустимые переходы между текущим и следующим состоянием действительны : тогда проверка правильности алгоритма станет на порядок проще

3) Обработка отброшенных ссылок в списках указателей опасности для каждого потока . После того, как контрольные объекты в безопасности, используйте повторно, если это возможно

Смотрите еще один мой связанный пост, где некоторый код, реализованный с помощью семафоров и мьютексов, (частично) переопределён в стиле без блокировки: Взаимное исключение и семафоры

Answer 6

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

Answer 7

Уменьшить или исключить общее изменяемое состояние.

Answer 8

Взгляните на мою ссылку ConcurrentLinkedHashMap для примера того, как написать структуру данных без блокировки. Он не основан на каких-либо научных работах и ​​не требует многолетних исследований, как полагают другие. Это просто требует тщательного проектирования.

Моя реализация действительно использует ConcurrentHashMap, который является алгоритмом блокировки каждой корзины, но он не полагается на эту деталь реализации. Его можно легко заменить на реализацию без блокировок в Cliff Click. Я позаимствовал идею у Клиффа, но использовал ее более явно, чтобы смоделировать все операции CAS с помощью конечного автомата. Это значительно упрощает модель, так как вы увидите, что у меня есть блокировка псевдо через состояния 'ing. Еще одна хитрость заключается в том, чтобы позволить лень и разрешать по мере необходимости. Вы увидите это часто, когда вы возвращаетесь назад или позволяете другим потокам «помочь» в очистке. В моем случае я решил разрешить удаление мертвых узлов в списке, когда они достигают головы, а не заниматься сложностью удаления их из середины списка. Я могу изменить это, но я не полностью доверял своему алгоритму обратного отслеживания и хотел отложить существенное изменение, такое как использование подхода с 3 узлами блокировки.

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

Answer 9

Можете ли вы уточнить, что вы подразумеваете под структурой?

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

Answer 10

В Java используйте пакеты java.util.concurrent в JDK 5+ вместо того, чтобы писать свои собственные. Как было упомянуто выше, это действительно поле для экспертов, и если у вас нет свободного года или двух, откатить свой собственный вариант невозможно.