Программирование

Ошибка в lock-free списке C#: race condition и ABA

Разбор гонки данных в lock-free списке с двойной буферизацией в C#. Почему сумма элементов не совпадает, хотя количество верно? Исправления: in-flight счётчики, ConcurrentQueue, sequence tagging для thread-safety.

Авторы: НейроАгент

Ошибка в реализации lock-free списка с двойной буферизацией в C#

Задача: Реализовать lock-free список, где один поток читает (изредка проверяет накопленные данные и выгружает их все сразу), а несколько потоков пишут. Читающий поток не блокирует писателей.

Идея реализации: Использовать два узла (двойная буферизация): один для чтения, другой для записи. При запросе чтения происходит атомарный свап узлов. Перед свапом текущий узел помечается флагом -1 (закрыт для записи), чтобы писатели перешли на новый.

Проблема: В тестах с 11 писателями (каждый добавляет 111011 элементов) число прочитанных элементов совпадает с ожидаемым (operations == writers.Length * numWriteRequest), но сумма элементов отличается на нанопроцент (например, expected != sum). Ошибка воспроизводится крайне редко (0.000000000000000001% случаев).

Вопросы:

  • Где ошибка, гонка данных (race condition) или ABA-проблема?
  • Почему сумма не совпадает, хотя количество элементов правильное?
  • Как исправить реализацию для полной thread-safety?

Код реализации:

csharp
public struct ConcurrentList<T>
{
 class Node
 {
 public Node Next;
 public T[] Items;
 public int Counter;
 }
 public ConcurrentList(int capacity)
 {
 Node a = new Node() { Counter = 0, Items = new T[capacity] };
 Node b = new Node() { Counter = 0, Items = new T[capacity] };
 a.Next = b;
 b.Next = a;
 _head = a;
 _locker = new();
 }
 object _locker;
 private Node _head;

 public void Add(T data)
 {
 while (true)
 {
 Node head = _head;
 int currentCounter = head.Counter;
 if (currentCounter < 0) continue;
 if (Interlocked.CompareExchange(ref head.Counter, currentCounter + 1, currentCounter) == currentCounter)
 {
 int index = currentCounter;
 if (index >= head.Items.Length)
 {
 lock (_locker)
 {
 Grow(ref head, index);
 head.Items[index] = data;
 }
 return;
 }
 head.Items[index] = data;
 return;
 }
 }
 }

 [MethodImpl(MethodImplOptions.NoInlining)]
 private void Grow(ref Node head, int index)
 {
 lock (_locker)
 {
 if (index < head.Items.Length) return;
 Array.Resize(ref head.Items, Math.Max(1, index * 2));
 }
 }

 public int Count => _head.Counter + _head.Next.Counter;
 public bool IsEmpty => _head.Counter == 0;

 public ReadOnlySpan<T> Items
 {
 get
 {
 Node oldHead = _head;
 int counter;
 do
 {
 counter = oldHead.Counter;
 } while (Interlocked.CompareExchange(ref oldHead.Counter, -1, counter) != counter);

 Interlocked.Exchange(ref _head, oldHead.Next);

 if (counter > oldHead.Items.Length)
 {
 Grow(ref oldHead, counter);
 }
 oldHead.Counter = 0;
 if (counter <= 0) return ReadOnlySpan<T>.Empty;
 return oldHead.Items.AsSpan(0, counter);
 }
 }
}

Тестовый код:

csharp
static async Task Main(string[] args)
{
 Task[] writers = new Task[11];
 int numWriteRequest = 111011;
 var list = new ConcurrentList<int>(writers.Length * numWriteRequest);
 long ComplectedCount = 0;
 for (int i = 0; i < writers.Length; i++)
 {
 writers[i] = new Task(() =>
 {
 for (int j = 0; j < numWriteRequest; j++)
 {
 list.Add(j);
 }
 Interlocked.Increment(ref ComplectedCount);
 });
 }
 foreach (var w in writers) w.Start();

 long sum = 0;
 int operations = 0;
 while (ComplectedCount != writers.Length || list.Count > 0)
 {
 var items = list.Items;
 foreach (var item in items) sum += item;
 operations += items.Length;
 }

 long expected = writers.LongLength * (numWriteRequest * (numWriteRequest - 1L)) / 2L;
 Console.WriteLine(expected == sum);
 Console.WriteLine(operations == writers.Length * numWriteRequest);
 Console.WriteLine(expected);
 Console.WriteLine(sum);
 Console.WriteLine(operations);
}

Подозрения: Писатель может добавить элемент после свапа (используя локальную ссылку на старый head), но это не должно влиять, так как элементы пишутся в конец.

Это классическая гонка данных в вашей lock-free реализации: вы “публикуете” слот (увеличиваете счётчик) раньше, чем записываете в него значение, поэтому читатель иногда считывает пустой (или ещё не установленный) элемент. Это не ABA-проблема в чистом виде — ABA тут маловероятна; причина — порядок операций «резервирование → запись → чтение». Исправление — изменить порядок публикации/записи или добавить простую синхронизацию завершения писателей (in‑flight/writer‑count) либо использовать проверяемую публикацию (sequence/flags) или готовую concurrent коллекцию.

Содержание

lock-free: где ошибка — гонка данных, а не ABA

Коротко: в вашем коде Add делает атомарный CAS на head.Counter и только затем пишет head.Items[index] = data. Читатель, в свою очередь, делает CAS, чтобы пометить буфер закрытым (Counter -> -1) и сразу же читает диапазон 0…counter-1. Если писатель успел увеличить счётчик (резервировать слот), но ещё не записал значение, то читатель увидит «зарезервированное» место как часть диапазона и прочитает пустое/неинициализированное значение.

Почему это не ABA в практическом смысле:

  • ABA — это классическая проблема для pointer/CAS‑алгоритмов, когда значение возвращается к предыдущему и CAS ошибочно думает, что ничего не менялось; см. вводные по ABA Wikipedia и обзор решений (tag/versioning) у Stroustrup и других.
  • В вашей реализации узлы фиксированы (две Node) и CAS применяется к целому счётчику элементов, а не к указателю, и «симптомы» (количество операций верно, сумма — нет) типичны не для ABA, а для расхождения между публикацией счётчика и реальным завершением записи. Для общего контекста о тонкостях lock‑free операций и видимости записей полезны материалы CMU L31 Lock-Free и аналитика по ABA/публикации у MoodyCamel solving-the-aba-problem.

Почему количество элементов совпадает, а сумма — нет

Наблюдение:

  • operations == total CAS‑резервов (всех успешных инкрементов счётчика) — потому что читатель берёт значение counter, которое отражает число зарезервированных слотов.
  • expected != sum — потому что некоторые из зарезервированных слотов ещё не содержали записанного значения в момент чтения.

Простой таймлайн одного такого редкого случая:

  • time t0: head.Counter == N
  • writer W: CAS(head.Counter, N -> N+1) — успешно; index = N (зарезервирован)
  • W прерывисто: ещё не выполнил head.Items[N] = value
  • reader R: читает counter (видит N+1), успешно CAS(… -> -1), выполняет Exchange(_head,…), читает oldHead.Items[0…N] — слот N ещё не записан => возвращает дефолтное значение (0 для int)
  • позднее W записывает head.Items[N] = value (в уже «вытащенный» буфер) — значение «потеряно» для текущего прохода, потому что reader уже прочитал этот слот

Итого: количество прочитанных слотов (operations) соответствует числу резервов, но часть значений была прочитана до фактической записи — отсюда небольшая расхинка в сумме. Вероятность очень мала, потому что окно между успешным CAS и фактической записью короткое; зато в многопоточной нагрузке оно иногда наступает.

Как исправить: практические варианты (от простого к lock-free)

Ниже — проверенные варианты по возрастанию сложности. Под каждым — преимущества/недостатки и примерные куски кода.

1) Самый простой и надёжный: готовые concurrent коллекции

Если цель — надёжно собирать элементы от многих писателей и обрабатывать батчами одним читателем — используйте готовые структуры: ConcurrentQueue + BlockingCollection или BlockingCollection с ConcurrentQueue. Это снимает тонкие ошибки, работает быстро и легко тестируется.

Пример идеи (псевдокод):

  • writers: bc.Add(item)
  • reader: взять все доступные элементы через TryTake в цикле или Drain через GetConsumingEnumerable и собирать батчи

Документация Microsoft по thread-safe коллекциям: Thread-Safe collections - .NET

Плюсы: простота, корректность, хорошо протестировано. Минусы: немного больше накладных расходов, не «голый» lock‑free.

2) Минимальное исправление вашей реализации: in‑flight writers (рекомендую)

Идея: отслеживать число активных писателей, которые уже зарезервировали слот и ещё не закончили запись. Перед свапом читатель сначала атомарно помечает буфер закрытым (как сейчас), а затем ждёт, пока все in‑flight писатели завершат. Это гарантирует: после перехода на следующий буфер все слоты до counter действительно записаны.

Что нужно добавить:

  • В Node: int InFlight (считает писателей, которые начали операцию для этой Node)
  • В Add: увеличить InFlight перед чтением/резервом; при выходе уменьшить InFlight везде (и в успешном, и в неуспешном пути)
  • В Items.get: после успешного CAS на -1 — ждать, пока InFlight == 0 (SpinWait/Yield), затем менять _head и читать.

Ключевой момент: читатель ждёт только завершения писателей, уже резервировавших слот; это не блокирует писателей (они свободны писать и завершать), и окно race исчезает.

Пример изменения (иллюстративно — вставьте using System.Threading):

csharp
class Node
{
 public Node Next;
 public T[] Items;
 public int Counter; // как раньше — число зарезервированных слотов
 public int InFlight; // новые: число писателей, которые начали работу с этой Node
}

public void Add(T data)
{
 while (true)
 {
 Node head = _head;
 Interlocked.Increment(ref head.InFlight); // пометить, что мы работаем с этим head
 int currentCounter = Volatile.Read(ref head.Counter);
 if (currentCounter < 0)
 {
 Interlocked.Decrement(ref head.InFlight);
 continue; // кто-то закрыл буфер — попробуем снова
 }

 if (Interlocked.CompareExchange(ref head.Counter, currentCounter + 1, currentCounter) == currentCounter)
 {
 int index = currentCounter;
 if (index >= head.Items.Length)
 {
 lock (_locker) { Grow(ref head, index); }
 }
 // Гарантированно пишем в свой слот, потом выходим
 Volatile.Write(ref head.Items[index], data);
 Interlocked.Decrement(ref head.InFlight);
 return;
 }
 Interlocked.Decrement(ref head.InFlight);
 // CAS не удался — повторяем
 }
}

public ReadOnlySpan<T> Items
{
 get
 {
 Node oldHead = _head;
 int counter;
 do
 {
 counter = Volatile.Read(ref oldHead.Counter);
 } while (Interlocked.CompareExchange(ref oldHead.Counter, -1, counter) != counter);

 // дождаться завершения всех писателей, которые уже участвовали с этим узлом
 while (Volatile.Read(ref oldHead.InFlight) != 0)
 {
 Thread.SpinWait(1); // or Thread.Yield()
 }

 Interlocked.Exchange(ref _head, oldHead.Next);

 if (counter > oldHead.Items.Length) Grow(ref oldHead, counter);
 oldHead.Counter = 0;
 if (counter <= 0) return ReadOnlySpan<T>.Empty;
 return oldHead.Items.AsSpan(0, counter);
 }
}

Плюсы:

  • Небольшое изменение существующей логики.
  • Устраняет описанную гонку: reader не уносит незавершённые слоты.
    Минусы:
  • Reader может немного подождать (spin-wait) на очень редкие случаи; это не блокирует писателей.
  • Требуется аккуратность с Grow/lock и памятью.

Важно: использовать Volatile.Read/Volatile.Write (или Interlocked операции) для видимости между потоками при публикации данных. Подробнее об атомарных операциях и видимости в lock‑free коде — материалы по lock‑free алгоритмам и ABA: CMU L31, обсуждение ABA и тегов у moodycamel.

3) True lock‑free: sequence / per‑slot tagging (сложнее, но без ожидания)

Если вам нужна полностью неблокирующая схема без ожиданий читателя, применяют per‑slot sequence numbers или state flags:

  • каждому слоту соответствует sequence (long), который меняется в заранее определённом порядке;
  • писатель пишет значение в слот, делает MemoryBarrier/Volatile.Write и затем обновляет sequence (publish);
  • читатель смотрит sequence для каждого слота и читает только те, для которых sequence показывает «опубликовано»;
  • варианты: алгоритмы ring‑buffer с sequence как у LMAX Disruptor или реализации lock‑free queue с tag/sequence (см. статьи с примерами у moodycamel и Concurrency Freaks).

Такой подход даёт минимальные задержки у читателя, но сложен в реализации и отладки, особенно при динамическом росте/перераспределении буферов. Для вдохновения и шаблонов смотрите: moodycamel article и блог Concurrency Freaks double-instance-locking.

Рекомендации и тестирование

  • Если вам важнее корректность и простота — используйте ConcurrentQueue/BlockingCollection. Это стандартный путь для producer‑consumer. См. MS Docs.
  • Если хотите минимально править текущую реализацию — примените in‑flight счётчик (вариант 2). Он прост, понятен и устраняет описанную гонку без кардинальной перестройки.
  • Для максимальной производительности и без ожиданий — реализуйте per‑slot sequence/tagging (вариант 3) или используйте готовые высокопроизводительные lock‑free библиотеки/алгоритмы.
  • Тестирование: стресс‑тесты, long‑running fuzzing, и многопоточность с примусом прерываний (удержание потоков после CAS) помогут отловить редкие условия. Также используйте инструмент анализатора гонок/TSAN‑подобные средства, где это возможно.
  • Учтите роль сборщика мусора и особенностей платформы: для ссылочных типов GC может снижать вероятность некоторых ABA‑эффектов, но не заменяет правильной синхронизации (см. обсуждение ABA и GC: Baeldung).

Источники

  1. ABA problem - Wikipedia
  2. L31_LockFree Lock-Free Programming (Geoff Langdale) — CMU lecture notes
  3. Solving the ABA Problem for Lock-Free Free Lists — moodycamel blog
  4. Thread-Safe collections - .NET | Microsoft Learn
  5. Concurrency Freaks: Double Instance Locking
  6. The ABA Problem in Concurrency — Baeldung
  7. (Аналитические обсуждения и примеры lock‑free/queue подходов находятся в исходном списке источников из анализа.)

Заключение

Коротко: баг — не ABA, а race condition между резервированием слота (CAS инкремент счётчика) и фактической записью значения в массив. Потому операции (резервы) считаются правильно, а значение в некоторых слотах читается до завершения писателя — отсюда маленькая, но реальная потеря суммы. Самое простое и безопасное исправление — либо перейти на готовые concurrent коллекции, либо добавить per‑node in‑flight счётчик и ждать его обнуления перед свапом; для полного lock‑free поведения нужны per‑slot sequence/flags или специализированные алгоритмы.

Авторы
НейроАгент
Автор
Проверено модерацией
НейроОтветы
Модерация
Ошибка в lock-free списке C#: race condition и ABA