Кратко — перечислю жизнеспособные стратегии, дам принцип работы итератора в каждой и отмечу особенности (корректность, производительность, утилизацию памяти).
1) Глобальная блокировка (coarse-grained lock)
- Идея: единственный мьютекс защищает весь список; итератор берет мьютекс на время перебора.
- Поведение итератора: простая последовательная итерация по указателям, нет особой логики.
- Плюсы: простота, легкая корректность (атомарность операций).
- Минусы: низкая конкурентность; читатели блокируют вставки/удаления.
- Стоимость: проход по списку $O(n)$ под блокировкой.
2) Мелкозернистые блокировки / hand-over-hand (lock coupling)
- Идея: узел имеет собственный замок; при переходе итератор берет замок следующего узла, затем отпускает предыдущий.
- Итератор: держит замок на текущем (или на следующем) узле, защищая чтение и безопасный доступ к next; при удалении узел блокируется.
- Плюсы: лучшее параллелизм чем глобальный замок; гарантированная корректность.
- Минусы: высокая сложность, риск дедлоков при ошибках; накладные расходы на блокировки.
- Подходит если требуется последовательный, «консистентный» проход в присутствии модификаций.
3) Оптимистическая проверка (optimistic traversal + validation)
- Идея: итератор читает указатели без блокировок, затем валидирует, что просмотренные участки не изменились (например, по версии/счетчику или по повторному чтению).
- Итератор: читает next, сохраняет версию узла, при сомнении повторяет от ближайшей валидной точки.
- Плюсы: хорошая производительность при редких конфликтов.
- Минусы: возможны рестарты; сложна реализация версионирования/валидации.
4) Логическое удаление + «помогающее» проходение (lazy / Harris-style lock-free list)
- Идея: удаление в два шага — логическая пометка узла (marked), затем физическое исключение (unlink) с помощью CAS; итератор при встрече помеченного узла пытается помочь с unlink.
- Итератор: читает next; если node помечен — пропускает/помогает удалить (CAS prev->next), иначе возвращает.
- Плюсы: высокая конкуррентость, можно строить без блокировок.
- Минусы: сложность корректного упоминания памяти; необходимость безопасной схемы рециклинга.
- Часто используется в lock-free решениях (Harris, Michael).
5) Read-Copy-Update (RCU) / epoch-based snapshots
- Идея: читатели работают без блокировок на "старых" версиях; писатели копируют и обновляют указатель головы; старые версии освобождаются только после окончания всех читателей (epochs).
- Итератор: входит в read-side критическую секцию, просто проходит по списку; гарантируется, что узлы, видимые при начале итерации, не будут немедленно освобождены.
- Плюсы: отличная скорость чтения при доминировании чтений; простые итераторы.
- Минусы: писатели дороже; требуется механизм отслеживания активных читателей; задержки освобождения памяти.
- Подходит для read-mostly рабочих нагрузок.
6) Снимок (immutable / copy-on-write, persistent list)
- Идея: при изменении создаётся новая версия списка (частично шарящаяся); итератор привязан к конкретной версии (snapshot).
- Итератор: безопасно проходит по своей версии, никаких специальных мер по удалению не требуется.
- Плюсы: простота итератора, сильная семантика (стабильный снимок).
- Минусы: затраты на копирование/аллоцирование; сложность управления версиями; хорош для функциональных/иммутабельных сред или при малом числе модификаций.
7) Безопасность освобождения памяти (обязательный компонент)
- Любая стратегия, где узлы могут быть освобождены, требует схемы, гарантирующей, что итератор не попадёт на уже freed память. Варианты:
- hazard pointers (каждый поток помечает узлы, которые использует);
- epoch-based reclamation (EBR) / quiescent-state-based reclamation;
- reference counting;
- полагаемся на GC (если есть).
- Без этого даже корректная логика обхода приводит к use-after-free.
8) Семантика итератора (дизайн-решение)
- Сильная (linearizable) — итератор видит список как последовательность атомарных изменений (дорого).
- Weakly consistent — итератор может увидеть часть изменений, пропустить некоторые; обычно быстрее и чаще используемо.
- Snapshot — итератор фиксирует состояние в момент создания.
Выбор семантики влияет на архитектуру (RCU/immutable для snapshot/fast reads, блокировки/валидация для strong).
Рекомендации по выбору
- Простота и корректность важны — начните с глобальной блокировки.
- Для высоких нагрузок чтения — RCU/epoch или immutable snapshots.
- Для высоких требований к конкурентности записи — lock-free с логическим удалением (Harris) + hazard pointers/EBR для безопасного освобождения.
- Если нужно «итератор, который продолжает работать» (прогрессивно пропускает удалённые узлы), реализуйте логическое удаление + итератор, который при встрече помеченных узлов пропускает их и, при возможности, помогает unlink.
Короткий алгоритм итератора для Harris-style list (примерная схема)
1. Читаем current->next (atomically).
2. Если next помечен как deleted — пробуем CAS(prev->next, next, next->next) чтобы unlink; повторяем без возврата значения.
3. Иначе считаем next валидным и возвращаем/перемещаемся вперёд.
4. При чтении каждого указателя защищаем его с помощью hazard pointer или находимся в read-epoch.
Заключение: нет универсально лучшей стратегии — выбор зависит от требований к производительности, семантике итератора и доступных примитивов управления памятью.