Очистка памяти на основе эпох

Epoch-based reclamation (EBR) - метод управления памятью для lock-free структур данных. Проблема, которую он решает: когда поток удаляет узел из конкурентной структуры, другие читатели всё ещё могут держать указатель на этот узел. Мгновенное освобождение памяти приведёт к тому, что читатели обратятся к уже освобождённой памяти. Подсчёт ссылок решает проблему, но добавляет атомарные инкременты на каждое обращение. EBR избавляет от накладных расходов на уровне отдельных обращений.

Схема состоит из трёх частей:

• Глобальный счётчик эпох, инкрементируемый сборщиками. Обычно циклически сменяются два или три значения (например, 0, 1, 2).
• Каждый зарегистрированный поток хранит локальную эпоху, фиксируемую при pin'е, и limbo-список узлов, удалённых им в этой эпохе.
• Перед обращением к структуре поток выполняет pin, копируя глобальную эпоху в локальную. Pin означает: "я могу держать указатели, начиная с этой эпохи и новее".

Когда узел удаляется, память не освобождается сразу - узел добавляется в limbo-список текущего потока с меткой текущей глобальной эпохи. Узел можно безопасно освободить только тогда, когда локальные эпохи всех зарегистрированных потоков продвинулись дальше эпохи удаления этого узла. Фоновый или совмещённый с другими операциями проход обходит limbo-списки, освобождает безопасные узлы, после чего глобальный счётчик увеличивается.

Модель накладных расходов здесь противоположна подсчёту ссылок: нулевые затраты на горячем пути при каждом доступе (одно relaxed-чтение глобальной эпохи при pin/unpin) ценой ограниченного разрастания памяти - освобождённая память остаётся в limbo, пока хотя бы один поток остаётся pinned. Стандартная защита от этого - порог удалений на поток, который запускает проход очистки при разрастании limbo-списка.

EBR используется по умолчанию во многих lock-free библиотеках: Crossbeam в Rust, userspace RCU (URCU) в Linux, C-библиотеке gregburd/skiplist и большинстве академических реализаций lock-free skip-list и очередей. Главная альтернатива - hazard pointers, где более высокие накладные расходы при каждом доступе обмениваются на более строгие границы по объёму памяти в худшем случае. В shared-memory-consistency-causality показано, как делегированная очистка через hazard pointers ломается в модели памяти, допускающей нарушения причинности между чтением и записью: сборщик освобождает память, которую читатель всё ещё использует.