C ++ 11: Атомная переменная: lock_free свойство: что это значит?
Я хотел понять, что подразумевается под свойством lock_free атомарных переменных в c ++ 11. Я гуглил и видел другие соответствующие вопросы на этом форуме, но все еще имел частичное понимание. Цените, если кто-то может объяснить это сквозным и простым способом.
Решение
Джерри уже упоминал общий правильность проблемы с блокировками, то есть их сложно понять и правильно запрограммировать.
Другая опасность блокировок заключается в том, что вы теряете детерминизм в отношении времени выполнения: если поток, получивший блокировку, задерживается (например, отменяется по расписанию операционной системой или «заменяется»), то возможно, что вся программа задерживается, потому что ожидает блокировки. В отличие от этого, алгоритм без блокировки всегда гарантированно добиться некоторого прогресса, даже если какое-то количество потоков задерживается где-то еще.
В общем, программирование без блокировки часто помедленнее (иногда значительно), чем заблокированное программирование с использованием неатомарных операций, потому что атомарные операции наносят значительный ущерб кэшированию и конвейерной обработке; Тем не менее, он предлагает детерминизм и верхние границы задержки (по крайней мере, общая задержка вашего процесса; как заметил @ J99, отдельные потоки могут все еще испытывать голодание, пока достаточно Другой темы прогрессируют). Ваша программа может работать намного медленнее, но она никогда не блокируется полностью и всегда добивается определенного прогресса.
Сама природа аппаратных архитектур позволяет некоторым небольшим операциям быть по сути атомарными. На самом деле, это очень необходимо любой аппаратное обеспечение, поддерживающее многозадачность и многопоточность. В самом сердце любой Примитив синхронизации, такой как мьютекс, вам нужен немного своего рода атомарная инструкция, которая гарантирует правильное поведение блокировки.
Итак, имея это в виду, теперь мы знаем, что некоторые типы, такие как логические числа и целые числа машинного размера, могут быть загружены, сохранены и обменены атомарно. Таким образом, когда мы оборачиваем такой тип в std::atomic шаблон, мы можем ожидать, что результирующий тип данных действительно будет предлагать операции загрузки, хранения и обмена, которые не используют блокировки. В отличие от вашей реализации библиотеки всегда разрешено реализовать атомарный Foo как обычный Foo охраняется замком.
Чтобы проверить, является ли атомным объект без блокировки, вы можете использовать is_lock_free функция-член. Кроме того, есть ATOMIC_*_LOCK_FREE макросы, которые говорят вам, является ли атомарный примитив типы потенциально иметь инстанцирование без блокировки. Если вы пишете параллельные алгоритмы, которые вы хотите освободить от блокировок, вы должны, таким образом, включить утверждение, что ваши атомарные объекты действительно свободны от блокировок, или статическое утверждение в макросе, чтобы иметь значение 2 (это означает, что каждый объект соответствующего типа всегда свободен от блокировки).
Другие решения
Вероятно, проще всего начать с разговора о том, что произойдет, если не безблокировочный.
Наиболее очевидный способ решения большинства элементарных задач — блокировка. Например, чтобы обеспечить одновременную запись в переменную только одного потока, вы можете защитить ее мьютексом. Любой код, который собирается записать в переменную, должен получить мьютекс перед выполнением записи (и выпустить его позже). Только один поток может одновременно владеть мьютексом, поэтому, пока все потоки следуют протоколу, не более одного может писать в любой момент времени.
Однако если вы не будете осторожны, это может привести к тупику. Например, давайте предположим, что вам нужно написать два различные переменные (каждая из которых защищена мьютексом) в качестве атомарной операции, т. е. необходимо убедиться, что при записи в одну из них вы также пишете в другую). В таком случае, если вы не будете осторожны, вы можете вызвать тупик. Например, давайте назовем два мьютекса A и B. Поток 1 получает мьютекс A, затем пытается получить мьютекс B. В то же время поток 2 получает мьютекс B, а затем пытается получить мьютекс A. Поскольку каждый из них содержит один мьютекс ни один не может получить оба, и ни один не может продвинуться к своей цели.
Существуют различные стратегии, позволяющие их избежать (например, все потоки всегда пытаются получить взаимные исключения в одном и том же порядке, или, если не удается получить взаимный доступ в течение разумного периода времени, каждый поток освобождает удерживаемый мьютекс, ожидает некоторого случайного количества время, а затем снова пытается).
Однако при программировании без блокировок мы (очевидно, достаточно) не используем блокировки. Это означает, что тупик, как выше, просто не может произойти. Если все сделано правильно, вы можете гарантировать, что все потоки непрерывно продвигаются к своей цели. Вопреки распространенному мнению, это делает не означает, что код обязательно будет работать быстрее, чем хорошо написанный код с использованием блокировок. Это, однако, означает, что взаимоблокировки, подобные описанным выше (и некоторые другие типы проблем, такие как блокировки в реальном времени и некоторые типы условий гонки), устранены.
Теперь о том, как именно вы это делаете: ответ короткий и простой: он варьируется — широко. Во многих случаях вы смотрите на конкретную аппаратную поддержку для атомарного выполнения определенных операций. Ваш код либо использует их напрямую, либо расширяет их для предоставления операций более высокого уровня, которые все еще являются атомарными и свободными от блокировок. Даже возможно (хотя и редко практично) реализовать атомарные операции без блокировки без аппаратной поддержки (но, учитывая ее непрактичность, я перейду к попыткам углубиться в детали, по крайней мере, сейчас).
Без блокировки является одним из методов неблокирования. Для алгоритма он включает в себя глобальное свойство progress: когда поток программы активен, он может сделать шаг вперед в своем действии, для себя или, в конечном счете, для другого.
Предполагается, что алгоритмы без блокировок лучше работают в тяжелых условиях, когда потоки, работающие с общими ресурсами, могут тратить много времени на ожидание своего следующего активного интервала времени. Они также почти обязательны в контексте, где вы не можете заблокировать, как обработчики прерываний.
Реализации алгоритмов без блокировок почти всегда основаны на методе сравнения и замены (некоторые могут использовать такие вещи, как ll / sc) и стратегии, в которых видимая модификация может быть упрощена до одного изменения значения (в основном указателя), что делает ее точкой линеаризации и циклическим над этой модификацией, если значение изменилось. В большинстве случаев эти алгоритмы пытаются завершать задания других потоков, когда это возможно. Хорошим примером является очередь без блокировки Micheal&Скотт (http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html).
Для инструкций более низкого уровня, таких как Compare-and-Swap, это означает, что реализация (возможно, микрокод соответствующей инструкции) не требует ожидания (см. http://www.diku.dk/OLD/undervisning/2005f/dat-os/skrifter/lockfree.pdf)
Для полноты, алгоритм без ожидания заставляет прогрессировать для каждого потока: каждая операция гарантированно завершается за конечное число шагов.