Что такое бес блокировочное многопоточное программирование?

Ключевым аспектом безблокировочного программирования является использование аппаратно встроенных атомарных операций.

На самом деле, даже сами блокировки должны использовать эти атомарные операции!

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

Вот простой пример: конкурентное увеличение счётчика. Мы представим две версии, которые обе являются "безопасными для потоков", т.е. могут вызываться несколько раз одновременно. Сначала блокировочная версия:

int counter = 0;
std::mutex counter_mutex;

void increment_with_lock()
{
    std::lock_guard<std::mutex> _(counter_mutex);
    ++counter;
}

Теперь безблокировочная версия:

std::atomic<int> counter(0);

void increment_lockfree()
{
    ++counter;
}

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

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

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

Для «безблокировочного» подхода идея состоит в том, что вы выполняете свою работу в другом месте, а затем пытаетесь атомарно зафиксировать эту работу в «видимом состоянии», и если вы неудачны, то повторяете попытку.

Проблемы с «безблокировочным» подходом заключаются в следующем:

• Трудно разработать безблокировочный алгоритм для чего-то, что не является тривиальным. Это связано с тем, что существует ограниченное количество способов реализовать часть «атомарного фиксирования» (часто полагаясь на атомарную операцию «сравнить и поменять», которая заменяет указатель на другой указатель).
• Если возникает конкуренция, производительность оказывается хуже, чем у блокировок, так как вы многократно выполняете работу, которая потом отменяется или требует повторной попытки.
• Практически невозможно разработать безблокировочный алгоритм, который был бы одновременно корректным и «честным». Это означает, что (в условиях конкуренции) некоторые задачи могут оказаться удачливыми (и многократно фиксировать свою работу и продвигаться дальше), в то время как другие могут быть крайне неудачливыми (и постоянно терпеть неудачу и повторять попытки).

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

Исследователи разработали такие структуры, как безблокировочные связанные списки (а также очереди FIFO/FILO) и некоторые безблокировочные деревья. Я думаю, что нет ничего более сложного, чем это. Что касается того, как они работают, то, поскольку это трудно, применяется сложный подход. Наиболее разумный подход — определить, какой тип структуры данных вас интересует, а затем поискать в интернете соответствующие исследования безблокировочных алгоритмов для этой структуры.

Также обратите внимание, что существует так называемый «блокирующий свободный» подход, который похож на безблокировочный, за исключением того, что вы знаете, что можете всегда зафиксировать работу и никогда не придется повторять попытку. Разработать блокирующий свободный алгоритм еще сложнее, но конкуренция не влияет на производительность, поэтому две другие проблемы, связанные с безблокировочными алгоритмами, исчезают. Примечание: пример «конкурентного счетчика» в ответе Керрека SB совсем не является безблокировочным, а на самом деле является блокирующим свободным.

Стандарты C и C++ (C11 и C++11) ввели поддержку потоков, а также атомарных типов данных и операций, которые могут использоваться в многопоточном программировании. Атомарная операция обеспечивает гарантии для операций, которые могут столкнуться с состоянием гонки между двумя потоками. Как только поток завершает выполнение такой операции, он может быть уверен, что операция была выполнена полностью.

Современные процессоры обычно поддерживают атомарные операции, такие как compare and swap (CAS) и атомарные инкременты.

Кроме того, атомарные типы могут обладать свойством "без блокировок" (lock-free). Это свойство, возможно, следовало бы назвать "без состояния" (stateless), так как оно подразумевает, что операция над таким типом данных никогда не оставит объект в промежуточном состоянии, даже если выполнение будет прервано обработчиком прерываний или чтение из другого потока произойдет во время обновления.

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