Альтернативы блокировок для синхронизации

Ответ 1

Алгоритмы без блокировки обычно включают использование методов сравнения и замены (CAS) или аналогичных инструкций, которые обновляют некоторое значение в памяти не только атомарно, но и условно и с индикатором успеха. Таким образом вы можете закодировать что-то вроде этого:

do
{
    read the current value
    calculate the new value
} while(!compare_and_swap(current_value, new_value);

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

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

В значительной степени ваша существующая библиотека потоковой передачи может иметь двухступенчатый подход к блокировке для мьютексов, блокировок чтения и записи и т.д., связанных с прядением с использованием CAS или аналогичных (например, spin on {читать текущее значение, если оно не установлено тогда cas ( current = not set, new = set)}), что означает, что другие потоки, выполняющие быстрое обновление, часто не будут приводить к тому, что ваш поток будет заменен на ожидание, и все относительно длительные накладные расходы, связанные с этим. Второй этап будет состоять в том, чтобы сообщить операционной системе, чтобы очередь в потоке, пока не найдет мьютекс бесплатно. Следствием этого является то, что если вы используете мьютекс для защиты доступа к переменной, то вряд ли вы добьетесь большего успеха, реализовав свой собственный "мьютекс" для защиты одной и той же переменной.

Алгоритмы блокировки свободны, когда вы работаете непосредственно с переменной, достаточно малой для непосредственного обновления самой инструкции CAS. Вместо того, чтобы быть...

• получить мьютекс (вращаясь на CAS, отступая на более медленную очередь ОС)
• Обновить переменную
• релиз мьютекса

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

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

Ядро (хорошее) следствие алгоритмов без блокировки заключается в том, что один поток не может удерживать мьютекс, а затем может быть заменен планировщиком, так что другие потоки не могут работать до тех пор, пока он не возобновится; скорее - с CAS - они могут вращаться безопасно и эффективно без опции резервного копирования ОС.

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

Как вы говорите, просто скрытие использования мьютексов за некоторым API не блокируется.

Ответ 2

Существует множество различных подходов к синхронизации. Существуют различные варианты передачи сообщений (например, CSP) или транзакционный память.

Оба эти могут быть реализованы с использованием блокировок, но это детализация реализации.

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

Ответ 3

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

Однако большинство решений без блокировки требуют значительных размышлений со стороны человека, проектирующего конкретную область проблем/конкретных проблем. Они вообще не применимы для всех проблем. Примеры таких реализаций см. В Библиотека Intel Threading Building Blocks.

Самое главное отметить, что свободное от блокировки решение не является бесплатным. Вы собираетесь дать что-то, чтобы выполнить эту работу, на минимальном уровне сложности реализации и, возможно, производительности в сценариях, где вы работаете на одном ядре (например, связанный список МНОГО медленнее, чем вектор). Удостоверьтесь, что вы тестировали, прежде чем использовать блокировку на основе предположения, что это будет быстрее.

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

Ответ 4

Еще одна библиотека для добавления в список чтения: Fast Flow

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

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