Почему автоматическая сборка мусора устраняет проблемы ABA?

Question

Я исследовал проблему ABA в Concurrency в книге практики, в Википедии, и я прочитал следующий пост

Как я понимаю, основная причина проблемы ABA заключается в том, что в алгоритме мы проверяем это состояние так же, как и раньше, но алгоритм подразумевает, что состояние не было затронуто.

Пример со структурой данных стека:

Чтобы добавить элемент в стек, мы используем следующий алгоритм:

create new stack node(save to `newNode` variable)

while(true) {
    oldHead = stack.get();
    newNode.next = oldHead; // point_1
    if(stack.compareAndSet(oldhead, newNode)) { // atomically replace head if now head same as was in start of iteration
        break;
    }    
}

Шаги, которые приводят к проблеме ABA:
Начальное состояние

a->b->c  // a-head, c- tail.

1. Thread_1 пытается добавить значение d в стек и ОС приостановить поток перед compareAndSet Операция (point_1)

2. Thread_2 затем выполнить pop (Thread_1 все еще приостановлен)

   b->c  // b-head, c- tail.
   

3. Thread_3 затем выполнить pop (Thread_1 все еще приостановлено)

   c // c-head, c- tail.
   

4. Затем Thread_4 выполняет push a(Тема_1 все еще приостановлена)

   a->c // a-head, c- tail.
   

5. Thread_1 активируется, и операция cas успешно выполняется, хотя в некоторых случаях это может быть нежелательно.

Хотя этот ответ принят, я не понимаю, почему автоматическая сборка мусора устраняет проблему.

Хотя я не эксперт в C I, я понимаю, что в C нельзя выделить один диапазон памяти для двух разных объектов.

Вы можете уточнить это более четко?

Answer 1

Вероятно, часть вашего замешательства связана с тем, что вы смешиваете саму структуру данных с содержимым.

В "правильной" реализации у вас будут стековые узлы, содержащие данные, а не сами данные. Итак, в итоге вы получаете Node(a), Node(b) и т. Д., Поэтому, когда какой-то поток проталкивает c в стек, он пройдет c, но это будет Node (c), который фактически выталкивается.

Это означает, что в такой среде вещь, введенная в стек на шаге 4, не будет a, это будет new Node(a), который будет отличаться от указателя Node(a) который другой поток видел на шаге 1. Эти объекты могут быть очень хорошими по бизнесу (поэтому в java, например, метод equals вернет true), но сравнение по указателю будет отличаться. И здесь мы подходим к части, где автоматический GC имеет значение. Блокированный поток из шага 1 по-прежнему содержит ссылку на старый экземпляр Node (a) в стеке / регистрах, даже если он был позже удален из стека и в нем нет сильных ссылок на него где-либо в куче. Это предотвращает удаление этого узла и повторное использование адреса памяти, что обмануло бы CAS.

Обратите внимание, что плохая ситуация, на которую вы ссылаетесь, может произойти только на языке, отличном от GC, если вы удалите (с точки зрения памяти) оригинальный узел (a), когда поток 1 все еще находится в критической секции. Это довольно сложно - вы оставляете поток с указателем на освобожденный блок памяти и должны быть действительно, действительно уверены, что не будут разыменовываться в более поздний момент, так как это приведет к гораздо худшему результату, чем ABA (вы могли бы прочитать любой мусор из освобожденного блока).

Если вы не реализуете уровень косвенности в форме Node(x) и просто позволяете клиентским вызовам напрямую выталкивать / извлекать / изменять внутренние узлы, тогда все ставки отключены - клиент может просто нажать один и тот же узел дважды, например, что приведет к бесконечности цикл позже. В вашем примере он сначала удалит, а затем повторно вставит тот же узел, но это предполагает много утечек между структурой данных и клиентским кодом - очень опасная вещь в многопоточной среде, особенно если вы хотите поэкспериментировать со структурами без блокировки,

Подводя итог, автоматический GC не защищает от всех случаев ABA. Он защищает от очень специфического случая ABA, связанного с повторным использованием памяти malloc, для агрессивно оптимизированного кода без блокировки, который содержит ссылки на мертвые объекты.