Блокировка свободной синхронизации

Question

Мой вопрос связан с многопоточностью синхронизации без блокировки. Я хотел знать следующее:

1. Каковы общие подходы для достижения этой цели? Я где-то читал о LockFreePrimitives, таких как CompareAndExchange (CAS) или DoubleCompareAndExchange (DCA), но объяснения не было дано? Любые подходы к минимизации использования замков?

2. Как Java / .NET достигает своих параллельных контейнеров? Они используют блокировки или синхронизацию без блокировки?

Заранее спасибо.

Answer 1

Вот несколько общих подходов, которые могут свести к минимуму использование блокировок, если ваш алгоритм имеет некоторые особенности, которые можно использовать:

1. При обновлении одной числовой переменной вы можете использовать неблокирующие примитивы, такие как CAS, atomic_increment и т. Д. Они обычно намного быстрее классического блокирующего критического раздела (lock, mutex).

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

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

4. Если вы полагаетесь на неявный эффект блокировки памяти блокировками, чтобы обеспечить видимость одной переменной между потоками, просто используйте volatile ¹ , если доступно.

5. Иногда использование условной переменной (и связанной блокировки) на практике происходит слишком медленно. В этом случае volatile занятое вращение намного эффективнее.

Еще несколько полезных советов по этой теме здесь: http://software.intel.com/en-us/articles/intel-guide-for-developing-multithreaded-applications/

Приятное прочтение в другом вопросе SO: Многопоточность без блокировки предназначена для настоящих экспертов по потокам (не пугайтесь названия).

И недавно обсуждаемая реализация atomic_decrement без блокировки на Java: Голодание в неблокирующих подходах

---

¹ Использование volatile здесь применимо к таким языкам, как Java, где volatile определило семантику в модели памяти, но не к C или C ++, где volatile предшествовало введению модель многопоточной памяти и не интегрируется с ней. Подобные конструкции доступны в этих языках, такие как различные спецификаторы std::memory_order в C ++.

Answer 2

Есть несколько полезных способов использовать синхронизацию без блокировки (например, упоминания @Tudor).Но я хочу предупредить об одном: синхронизация без блокировок не составляет.

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

Вкратце - каждый элемент может быть согласован с самим собой, но не согласован между собой.

Answer 3

Сравнение и замена полезны, но есть еще более простая (так называемая, «без блокировки») техника, которая полезна в определенных случаях использования производителем / потребителем, которая может быть полезна, поэтому я упомяну ее.

Представьте, что у вас есть функция doWork (), которая пишет в буфер.

1. Поток A инициализирует энергозависимую логическую переменную (флаг) в false, которая доступна как для потока A, так и создает объект энергозависимого буфера, который doWork выводит в поток B (глобальный и т. Д.).
2. Поток A создает поток B, который вызывает doWork ().
3. Функция doWork () потока B начинает создание / запись в буфер.Когда закончено, он устанавливает логическое значение true.
4. Поток A может опрашивать глобальный логический флаг, который начинается с false.Когда он становится истинным (не ложным), он может получить доступ к данным в объекте буфера, будучи уверенным, что он завершен.Между опросами Тема А может выполнять другую работу.(Так, например, он опрашивает один раз при вызове обновления и не ожидает истинного значения).Это не учитывает обработку ошибок, но это также может быть обработано в буфере.

Это работает только потому, что A только читает, а B только пишет, но этот вариант использования довольно распространен для 'фоновые рабочие темы.Это будет работать только на Java или C #, где volatile поставляется с гарантиями.