Hardlock-freeatomic
Что такое lock-free programming?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Lock-free — алгоритм, где хотя бы один поток гарантированно делает прогресс (без мьютексов). Реализуется через atomic-операции, особенно CAS (compare-and-swap).
// Lock-free стек: push через CAS-loop
template<class T>
class Stack {
struct Node { T value; Node* next; };
std::atomic<Node*> head_{nullptr};
public:
void push(const T& v) {
Node* n = new Node{v, nullptr};
n->next = head_.load(std::memory_order_relaxed);
while (!head_.compare_exchange_weak(
n->next, n,
std::memory_order_release,
std::memory_order_relaxed)) {
// n->next обновлён текущим head, retry
}
}
};compare_exchange_weak/strong — CAS: меняет значение только если оно совпало с expected. Проверить, lock-free ли тип: std::atomic<T>::is_always_lock_free. Lock-free сложнее mutex, но выигрывает при высокой contention.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.