Hardabalock-free
Что такое ABA problem в lock-free?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
ABA problem — классическая проблема CAS-алгоритмов. Поток T1 читает значение A, потом делает CAS «если до сих пор A, поменяй на B». За это время T2 меняет A→C→A. T1 видит A, CAS «успешен», но логический инвариант нарушен.
// Lock-free stack: T1 видит head=A, хочет pop
Node* old = head.load();
Node* next = old->next;
// ... T2: pop A, pop B, push A обратно (A->next теперь мусор) ...
head.compare_exchange_strong(old, next); // CAS «успешен» на A, но next — мусорРешения:
- tagged pointer (double-width CAS) — version counter + pointer;
- hazard pointers — отложенное освобождение, пока кто-то «держит» указатель;
- epoch-based reclamation (RCU);
- отказаться от lock-free, использовать mutex.
ABA — основная причина сложности lock-free memory management.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.