Сопоставьте гарантии lock-free и wait-free для многопоточной операции: какой прогресс они обеспечивают при конкуренции потоков?
Lock-free гарантирует, что система в целом будет продвигаться: за конечное число шагов хотя бы один поток завершит операцию. Это не означает, что каждый поток получит результат: конкретный поток может бесконечно проигрывать конкуренцию.
Wait-free — более сильная гарантия: каждая операция каждого потока завершится за ограниченное число собственных шагов независимо от поведения остальных потоков. Поэтому lock-free подходит не для всех задач с жёсткими требованиями к задержкам, а wait-free обеспечивает предсказуемый прогресс отдельных операций.
Эти гарантии появились как способ описывать прогресс неблокирующих алгоритмов без привязки к конкретной реализации блокировок. Обычный мьютекс может остановить всех участников из-за блокировки, приостановки владельца или проблем с планированием.
Неблокирующие алгоритмы используют атомарные операции, часто сравнение-и-обмен, чтобы конкурирующие потоки могли повторять попытку без явного владения общей блокировкой. Для таких алгоритмов важно различать «кто-то продвигается» и «продвигается каждый» — именно это и разделяют lock-free и wait-free.
Представим очередь, в которой несколько потоков добавляют элементы через атомарную операцию сравнения-и-обмена. При конфликте один поток успешно обновляет состояние, а остальные повторяют попытку.
Такая схема может быть lock-free: каждая успешная попытка одного потока означает общий прогресс. Но отдельный поток под постоянной нагрузкой способен много раз проигрывать более удачному конкуренту. Если операция находится на критическом пути запроса, это приводит к неограниченной задержке, голоданию потока и нарушению требований к latency.
Lock-free означает отсутствие глобальной остановки прогресса: при достаточно активных потоках за конечное число шагов хотя бы одна из операций завершится. Гарантия относится к системе в целом, а не к каждому участнику.
Wait-free требует верхней границы числа шагов для каждой операции. Эта граница должна сохраняться даже при постоянных вмешательствах других потоков. Алгоритм может быть wait-free и одновременно lock-free, поскольку более сильное свойство включает более слабое.
Повторный цикл вокруг сравнения-и-обмена обычно сам по себе не делает алгоритм wait-free. Число неудачных итераций может зависеть от активности других потоков и не иметь конечной фиксированной границы. Экспоненциальная задержка, уступка планировщику или ограничение числа повторов уменьшают нагрузку, но не превращают алгоритм в wait-free.
В C++ свойство std::atomic<T>::is_lock_free() говорит о том, являются ли операции над конкретным атомарным объектом lock-free согласно реализации. Значение false допускает внутреннюю блокировку; это не означает неправильность, но может ухудшить масштабирование и поведение при особых сценариях. Lock-free также не означает wait-free: стандартная lock-free реализация может допускать неограниченное число неудачных повторов.
Гарантии прогресса нужно отличать от порядка памяти. memory_order_relaxed, acquire или sequentially consistent определяют видимость и упорядочивание операций, но не превращают алгоритм из lock-free в wait-free и не дают сами по себе верхнюю границу задержки.
Практическая оценка должна учитывать ABA-проблему, переполнение счётчиков, корректность времени жизни объектов и потребление памяти. Даже алгоритм с нужной гарантией прогресса может быть непригоден, если его задержки, кэш-конфликты или требования к архитектуре не соответствуют нагрузке.
В высоконагруженной очереди несколько производителей обновляют общий индекс через сравнение-и-обмен. В обычных условиях алгоритм масштабируется лучше мьютекса, но при всплеске нагрузки один производитель иногда выполняет сотни неудачных попыток подряд. Метрика среднего времени остаётся хорошей, а хвост задержек становится непредсказуемым.
Рассматривались три варианта. Мьютекс проще доказать и обычно даёт понятное поведение, но поток, удерживающий блокировку, может быть вытеснен, а конкуренция увеличивает задержки. Ограничение числа повторов с переходом к блокирующему пути снижает голодание, но усложняет реализацию и не сохраняет полностью неблокирующий характер.
Полностью wait-free алгоритм обеспечил бы наиболее строгую гарантию, однако потребовал бы другой структуры данных и более сложного доказательства, включая ограничение числа шагов для каждой операции. Для очереди выбрали lock-free путь с ограниченным числом повторов и fallback на мьютекс: это сохранило высокую пропускную способность и ограничило хвост задержек. Решение было принято после измерений, поскольку одно только название lock-free не описывает фактическую задержку.
Нет. Lock-free описывает прогресс алгоритма, а не отсутствие любой остановки конкретного потока. Поток может быть вытеснен планировщиком, прерван обработчиком или бесконечно проигрывать атомарные конфликты. Кроме того, окружающий код может использовать мьютекс или системный вызов, поэтому lock-free участок не делает всю функцию неблокирующей.
Ограничение повторов делает задержку ограниченной только для данного участка алгоритма, если после исчерпания попыток гарантированно выполняется конечный альтернативный путь. Если поток просто возвращает ошибку, откладывает операцию или снова попадает в неограниченный цикл, wait-free-гарантия всей операции не доказана.
Нужно установить конечную границу шагов для каждого возможного пути, включая обработку памяти, повторное планирование работы и взаимодействие с другими структурами. Поэтому retry limit — полезный инженерный приём, но не автоматическое доказательство wait-free.
is_lock_free() отсутствие голодания?Нет. Этот признак касается реализации атомарной операции и гарантии системного прогресса, но не справедливого распределения успехов между потоками. Один поток может постоянно выигрывать сравнение-и-обмен, пока другой проигрывает.
Для борьбы с голоданием применяют ограничение повторов, backoff, разделение данных, очереди ожидания или алгоритмы с более сильной гарантией прогресса. Выбор зависит от требований к пропускной способности, задержке, потреблению CPU и сложности доказательства корректности.