Уже касались этой темы, но я до сих пор так и не понял многих моментов.

Вот что по этому поводу в concurrency in practice пишут:

автор 15.4.4. The ABA Problem
The ABA problem is an anomaly that can arise from the naive use of compareͲandͲswap in algorithms where nodes can
be recycled (primarily in environments without garbage collection). A CAS effectively asks "Is the value of V still A?", and
proceeds with the update if so. In most situations, including the examples presented in this chapter, this is entirely
sufficient. However, sometimes we really want to ask "Has the value of V changed since I last observed it to be A?" For
some algorithms, changing V from A to B and then back to A still counts as a change that requires us to retry some
algorithmic step.
This ABA problem can arise in algorithms that do their own memory management for link node objects. In this case, that
the head of a list still refers to a previously observed node is not enough to imply that the contents of the list have not
changed. If you cannot avoid the ABA problem by letting the garbage collector manage link nodes for you, there is still a
relatively simple solution: instead of updating the value of a reference, update a pair of values, a reference and a
version number. Even if the value changes from A to B and back to A, the version numbers will be different.
AtomicStampedReference (and its cousin AtomicMarkableReference) provide atomic conditional update on a pair of
variables. AtomicStampedReference updates an object referenceͲinteger pair, allowing "versioned" references that are
immune[8] to the ABA problem. Similarly, AtomicMarkableReference updates an object referenceͲboolean pair that is
used by some algorithms to let a node remain in a list while being marked as deleted.[9]
-------------
[8] In practice, anyway; theoretically the counter could wrap.
[9] Many processors provide a doubleͲwide CAS (CAS2 or CASX) operation that can operate on a pointerͲinteger pair, which would make this
operation reasonably efficient. As of Java 6, Atomic-StampedReference does not use doubleͲwide CAS even on platforms that support it.
(DoubleͲwide CAS differs from DCAS, which operates on two unrelated memory locations; as of this writing, no current processor implements
DCAS.)

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

UsmanquestionerНепонятно почему языки без автоматического управления памятью более узявимы.- https://ru.wikipedia.org/wiki/Проблема_ABA
- http://stackoverflow.com/a/19663933

авторWhen automatic garbage collection is enabled ,no two objects can be allocated with the same reference and co-exist at the same time,that's because as long as there is a reference count greater then 0 the reference itself will not be released and re-used.

Я не силён в С и мне не ясна эта фраза.

одна ссылка в С может указывать на два объекта?

Leonid Kudryavtsev,

Проблема на самом деле в следующем. Алгоритмы на атомиках выглядят примерно так:


авторwhile(true)
--remember state
--do some stuff
--if(change state if state is same atomic){
----break;
--}
}

Так вот считается, что есть класс алгоритмов при которых мы хотим проверить то, что состояние не изменилось, а не то, что оно было таким же как в начале итерации.


Пока никто не смог доходчиво объяснить причем тут языки с автоматическим управлением памятью

Usman,

а Вы можете целиком мысль выразить ?

непонятно, какой вывод нужно сделать прочитав ссылку.

questioner,

в вики пример со стеком:
изначально в нём
авторA
B
C

делаем pop.

Чтобы это сделать надо поменять ссылку на головы на next.
Что делаем.

Запоминаем текущую голову(A)
запоминаем новую голову(B)

Атомарное действие, что если старая голова всё ещё указывает на A, то мы делаем B головой.



Теперь представляем ситуацию, что перед CAS стек менялся по следующей схеме

авторA
B
C
->
авторB
C
->
авторC
->
авторA
C

А теперь наш CAS случается и получается полна хрень
->
авторB
C


Причем тут автоматическое управление памятью?

Ссылка на B держится, соответственно он не вычистится.

UsmanquestionerUsman,

а Вы можете целиком мысль выразить ?

непонятно, какой вывод нужно сделать прочитав ссылку.Например, в Си - нет никакого GC, который занимался бы автоматическим управлением памятью - там все вручную:
выделение и освобождение, доступ к памяти неконтроллируемый... но при желании вы всегда можете
запилить свою собственную реализацию алгоритма подсчета ссылок или реализовать часть концепции JMM (:

наводящая статья: https://ru.wikipedia.org/wiki/Управляемый_код (только замените .NET на JVM, а CLR на JRE)

Я привел пример, который будет некорректно работать в джаве.

Можете привести пример, который будет работать в джаве, но не будет работать в Си ?

Leonid KudryavtsevquestionerПока никто не смог доходчиво объяснить причем тут языки с автоматическим управлением памятью
подозреваю, что НЕ при чем.

Как я понимаю, автор описывает КОНКРЕТНОЕ решение для КОНКРЕТНОГО языка. При этом, делает некоторое "не очень корректное" ПРЕДПОЛОЖЕНИЕ которое помогает ему в реализации.

Дальше, он начинает описывать/доказывать, что в данном случае, его решение корректно. А проблемы негров (пользователей других языков, где это не так) - его не волнуют. Возможно, по ходу описания, он высказал легкое сочувсвтвие неграм, считая, что без данной возможности "хитро вывернутся" они обречены на вечные муки (подозреваю, что негры об этом и не подозревают).

Поэтому его алгоритм / код на конкретном языке программирования - будет работать корректно.

Если же кто-то, у кого руки растут не из того места, использует его алгоритм не по назначению, то у него "и одна ссылка будет указывать на два объекта" и много другого веселого будет )))

Если я правильно понял контекст и общий смысл вырванного Вами из книги абзаца.

IMHO

Конкретно в приведенном мною алгоритме проблема инкапсулирована в самом алгоритме. Стек считается нетронутым если голова не менялась. Не вот упорно не могу понять причем тут язык программирования если просто условие кривое?

Leonid Kudryavtsev,

Как можно оценить решение не вникая в него?

Логика там более чем простая

Leonid Kudryavtsev,

По поводу исходного кода - его нет у меня.я взял из википедии идею и попытался её объяснить.

Но кстати в книге есть пример: