Алгоритмы без блокировок обычно включают использование сравнения и замены (CAS) или аналогичных инструкций ЦП, которые обновляют некоторое значение в памяти не только атомарно, но и условно, а также с индикатором успеха.Таким образом, вы можете кодировать что-то вроде этого:
1 do
2 {
3 current_value = the_varibale
4 new_value = ...some expression using current_value...
5 } while(!compare_and_swap(the_variable, current_value, new_value));
compare_and_swap() атомарно проверяет, является ли значение the_variable по-прежнему current_value, и только если это так, оно будет обновлятьсяЗначение the_variable в new_value и возвращаемый true
точный синтаксис вызова будет зависеть от ЦП и может включать ассемблерный язык или предоставляемые системой / компилятором функции-оболочки (используйте последний, если он доступен - возможны другие оптимизации компилятора или проблемы, которые их использование ограничивает безопасным поведением);как правило, проверяйте свои документы
Значение заключается в том, что когда другой поток обновляет переменную после чтения в строке 3, но до того, как CAS в строке 5 попытается обновить, инструкция сравнения и обмена будетошибка, потому что состояние, из которого вы обновляете, равно , а не , которое вы использовали для вычисления желаемого целевого состояния.Можно сказать, что такие циклы do / while «вращаются», а не блокируются, поскольку они вращаются и округляются до тех пор, пока CAS не преуспеет.
Важно, что существующая библиотека потоков может иметь двухступенчатую блокировкуподход для мьютекса, блокировки чтения-записи и т. д., включающий:
Первый этап: вращение с использованием CAS или аналогичного (т. е. вращение на {чтение текущего значения, если оно не установлено, затем cas (текущий)= не установлено, новое = установлено)}) - это означает, что другие потоки, выполняющие быстрое обновление, часто не приводят к тому, что ваш поток переключается на ожидание, и все связанные с этим относительно длительные накладные расходы связаны с этим.
Второй этап используется только в том случае, если превышен некоторый предел итераций цикла или истекшего времени: он просит операционную систему поставить в очередь поток, пока он не узнает (или, по крайней мере, не подозревает), что блокировка может быть получена.
Следствием этого является то, что если вы используете мьютекс для защиты доступа к переменной, то вряд ли вам удастся добиться большего, если выиспользование собственного мьютекса на основе CAS для защиты той же переменной.
Алгоритмы без блокировок вступают в свои права, когда вы работаете непосредственно с переменной, достаточно маленькой, чтобы обновляться непосредственно самой инструкцией CAS.Вместо того, чтобы ...
- получить мьютекс (вращаясь на CAS, возвращаясь к более медленной очереди ОС)
- обновить переменную
- освободить мьютекс
... они упрощены (и сделаны быстрее) простым вращением CAS для непосредственного обновления переменных.Конечно, вам может показаться, что работа по вычислению нового значения из старого болезненного повторения умозрительно повторяется, но если не будет много разногласий, вы не будете тратить эти усилия часто.
Эта возможность обновления только одного места в памяти имеет далеко идущие последствия, и обходные пути могут потребовать некоторого творческого подхода. Например, если у вас был контейнер, использующий алгоритмы без блокировки, вы можете решить рассчитать потенциальное изменение элемента в контейнере, но не можете синхронизировать его с обновлением переменной размера в другом месте в памяти. Возможно, вам придется жить без размера или иметь возможность использовать приблизительный размер, когда вы выполняете CAS-вращение, чтобы увеличить или уменьшить размер позже, но любое данное считывание размера может быть немного неправильным. Вам может понадобиться объединить две логически связанные структуры данных - такие как свободный список и контейнер элемента - для совместного использования индекса, а затем разбить битовые поля ядра для каждого из них в одно и то же атомарное слово в начале каждой записи. , Оптимизация данных такого рода может быть очень инвазивной и иногда не даст вам те характеристики поведения, которые вам нужны. Mutexes и др. В этом отношении намного проще, и, по крайней мере, вы знаете, что вам не понадобится перезапись мьютексов от до , если требования эволюционируют только на этом шаге. Тем не менее, разумное использование подхода без блокировок действительно может быть достаточным для многих нужд и может привести к очень приятному улучшению производительности и масштабируемости.
Основным (хорошим) следствием алгоритмов без блокировок является то, что один поток не может удерживать мьютекс, а затем происходит его замена планировщиком, так что другие потоки не могут работать, пока он не возобновится; скорее - с помощью CAS - они могут вращаться безопасно и эффективно без опции восстановления ОС.
Вещи, которые блокируют бесплатные алгоритмы, могут быть полезны для обновления счетчиков использования / ссылок, изменения указателей для точного переключения указанных данных, свободных списков, связанных списков, маркировки блоков хеш-таблиц, используемых / не использованных, и распределения нагрузки. Конечно, многие другие.
Как вы говорите, простое сокрытие использования мьютексов за некоторыми API не освобождает от блокировки.