Usman https://ru.wikipedia.org/wiki/Проблема_ABA
После слов

"прочитано одинаковое значение, и признак «значение одинаковое» трактуется как «ничего не менялось». Однако, другой поток может выполниться между этими двумя чтениями, поменять значение, сделать что-нибудь ещё и восстановить старое значение"

читать перестал. Т.к. это называется ОШИБКА ПРОГРАММИСТА. И почему это называется "проблемой", лично мне не понятно.

Например тот же Hibernate, если хочется удостоверится, что "ничего не менялось" банально использует поле version. Прикладные системы (напрмер OeBS) могут использовать поля с автором и временем модификации. Стандартная задача, которая на планете решается по 100500 раз в день и ни для кого проблемой не является.

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

questioner
автор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.

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

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

So do I. В данном случае соглашусь с questioner

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

Если я правильно понял "проблему с" ABA, то разумеется. В случае, когда руки растут из ж.... Нет ничего не возможного.

Выделили один объект. Освободили память. Выделили второй. Объектов два и возможно разных, а ссылка на них одинаковая.

Но вот то, что того же самого при должен уровне "профессионализма" нельзя добиться в Java - лично для меня требует доказательств ))) Я привык доверять профессионализму своих коллег.

Все мои высказывая прошу считать относящимися только к ссылки из русской Wiki )))

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

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

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

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

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

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

IMHO

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





Проблемы лично я не вижу ))) Вроде примерно так это решает и Hibernate (один из вариантов).

questioner
Если говорить об оптимизации, конкретных алгоритмах и конкретных решениях, то IMHO:
1. можно запомнить решения, которое написано в книжке и принять как "данной". Только вопрос зачем? Это пригодиться при решении других задач?
2. начать с более простых алгоритмов (например Circle Ring Buffer крайне прост и понятен)

IMHO & AFAIK

3. с точки зрения "оптимальности" алгоритмы и код которые включены в Java, в ряде обсуждений в И-нет приходят к "не все так однозначно" ( C ) дочь офицера.

AFAIK

questionerНе вот упорно не могу понять причем тут язык программирования

Leonid Kudryavtsevподозреваю, что НЕ при чем.

IMHO
questionerКонкретно в приведенном мною алгоритме проблема инкапсулирована в самом алгоритме.

у кого "проблема" ?
Подозреваю, у автора алгоритма проблемы нет и его код замечательно работает

questionerСтек считается нетронутым если голова не менялась. ....если просто условие кривое?

Это НЕ условие (условие это Техническое Задание: "реализовать стек")
Это одно из возможных Решений.

И оно НЕ кривое, т.к. подозреваю код работает и, наверное, более оптимально чем некоторые другие возможные решения.

IMHO & AFAIK

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

1. легко )))
книжку явно написал "умный дядька", поэтому можно подозревать, что явных ошибок (настолько простых) у него нет
это не говорит о том, что у него нет более хитрых ошибок )))
2.
Дай ссылку на исходный код. Есть очень большое ощущение (даже не вникая и не видя кода), что описанная тобой ситуация в конкретном коде просто не возможна. И я (даже не видя код), подозреваю почему не возможна )))

Например java.util.concurrent.ConcurrentLinkedQueue не хранит пользовательские данные непосредственно. Он их хранит в объекте Node. Если они были извлечен из коллекции, то снова там оказаться банально не могут. По определению. Т.к. вторая строка в коде метода помещения данных




Ну и я так понимаю, еще один "финт ушами", что вместо вызова old_val.equel( new_value ) достаточно просто сравнить указатели.



делаем pop.

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

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

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


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

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

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


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

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

Фигню наверное написал.

Статью из Wiki я вообще не понимаю, приводить не работающий код и на примере не работающего кода что-то объяснять - это за гранью добра и зла.

Cкачал первоисточник "concurrency in practice", пошел читать

IMHO Статья из Wiki /особенно руской/ это вынос мозга. За гранью добра и зла.

И так многозадачность вынос мозга, еще и они стараются

Складывается четкое убеждение, что кроме Doug Lea и еще одного человека, на этой планете вообще никто серьезно concurrent не занимается ))) Что в Java в коллекциях его код, что книжки под его авторством, что в C то же он. Подозреваю, он ABA проблему придумал, он же и варианты решения предложил.

В общем-то, с ABA все понятно (кроме того, зачем это все так громко называть и тем более, зачем изучать ошибочный код):

1)
Обращаться по указателю, если мы не гарантируем, что он эксклюзивно наш, выглядит как минимум грязно (его мог кто-то удалить)

В Java и .NET это относительно безопасно.

2)
Память реюзится.

Т.ч. последовательность delete и new следующие друг за другом, могут привести к тому, что разные объекты могут занять одну и ту же область памяти. Что может привести к описанным сценарию. Если кодировать с ошибками.

В Java этого нет

Но зачем нужно кодировать с ошибками, тема не раскрыта.

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


IMHO

Нет. В java данной проблемы имени Dog Lea нет. По определению. (т.к. Dog Lea похоже сам же ее и изобрел и сам же решил)

Но.... зато есть другая... О которой Dog Lea скромно говорить не стал. Его lock free алгоритм коллекции Concurrent Linked List, при некоторых патернах использования просто убивает Minor Garbage Collector как класс

В его алгоритме, мы не зачищаем Node.

Как я понимаю, мы этого корректно сделать и не можем, т.к. нагло обращаемся к их полям из других потоков не заботясь о синхронизации. (см. пред. сообщение, проблема N1 )

Т.е., мы можем с легкостью уйти от изобретенного им же ABA проблемы с помощь "letting the garbage collector manage link nodes for you" и бросая Node грязные. Но разумеется, в жизни когда все хорошо, это значит что где-то скрыта подлянка. Но об этой он не пишет. Ограничиваясь словами "If you cannot avoid ... letting..." ))) IMHO. Полный редиска

Сам не проверял. Сейчас выпью чаю и тест для ConcurrentLinkedQueue запущу.

В обычных коллекциях, например java.util.LinkedList




После удаления, элемент специально зачищается, что бы нельзя было мусором убить Minor Garbage Collector. В коллекциях lock free от Dog Lea этого нет.

Как страшно жить.

Зачем questioner Вы это сделали ((( Ну знал я, что по слухам в ConcurrentLinkedQueue есть проблемы из за которых от нее AKKA отказывается. Но деталей то я не знал. Что мне теперь с этими знаниями делать? Ты думаешь у меня печалей в жизни мало?

Запустил тест. Да, мусор из Eden прорывается, т.е. проблема есть.

Но в JConsole я даже не сразу и заметил. На моем AMD, мусор в old перетекает крайне не быстро. Что, возможно объясняется тем, что класс Node очень маленький.

Но скачкообразно. Минут 5-10 график медленно полз, потом внезапно в Old сразу 2 метра мусора насыпалось. Ну и вообще график в JConsole какой-то странный, первый раз такое вижу.

Eden нормально "пилой", а old gen резкими прыжками, а servivour вообще не знаю как описать, прыжки но наоборот /от полного к пустому, в противофазе к old gen/.

Похоже, первый раз servivour накопил мусора на 2 Mb и выкинул в old gen, после чего вообще отключился ))) типа нафига мне работать, пускай все сразу в old gen уходит ))) что в принципе и правильно ))) нафиг servivour нужен )))

Занимательно одного. Первый раз вижу график в JConsole, когда servivour работает в режиме "прямотока"

IMHO Я уже кусок из книги прочитал.

В данном коде, не может быть ситуации "Поток 2 добавляет A обратно на стек".
Так как в данном коде НЕТ никакой возможности извлечь Node из стека и потом тот же Node положить обратно. Т.к. Node каждый раз создается разным

Но в данном коде есть "два финта ушами"

1.
Обращение к объекту, хотя мы не уверены, что этот объект нам принадлежит

Вида "newHead = oldHead.next" /// а oldHead == top

Для Java это безопасно, для C не очень ))) Т.к. в этот момент top доступен нескольких потокам и никто не может гарантировать, что другой поток в этот момент не освободит данный блок памяти. Как минимум для C это грязный код.

IMHO В качестве "маловероятной жести" : например другой поток на C в этот момент извлек top из стека, освободил данный блок памяти, вернул его операционной системе, операционная система освободила всю страницу операционной памяти и заодно пометила ее как ни используемой и запрещенной для доступа. И первый поток, попытавшись обратиться к ней, получит ошибку GPF / доступ запрещен ))) Вероятность такого конечно крайне низка, тем приятнее такие ошибки отлаживать IMHO.

Т.е. на Java так делать можно, на C, в общем случае, это не корректно.

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

А вот здесь внимание! Легкое передергивание! Да, на Java мы можем так делать и можем "не думать" об удалении объектов. Как написано в книжке "letting the garbage collector manage link nodes for you"

Но хорошо ли это?

И ответ на данный вопрос НЕТ. Даже в Java, лучше все же за собой мусор убирать. А особенно в долго живущих объектах приложения. И в других коллекциях его убирают.

2.
Собственно исходный постулат, если "вершина не менялась, то коллекция не менялся"

Постулат полностью правдив. Так как любой Node находящаяся в коллекцию по определению уникальна (она создается) и нет никакой возможно "извлечь ее и положить обратно"

===
Т.ч. данной придуманной проблемы в данном коде нет.

Зато есть другая проблема! Объект Node не очищается. Если коллекция долго живущая, это может порождать связанный мусор!

Т.е. достаточно одному объекты Node попасть в OldGen область память, как все остальные Node, с которыми работает коллекция, оказывается не возможно очистить через Minor Garbage Collector и пофиг, насколько они короткоживущие. Их от удаления защищает мусор лежащий в OldGen'е !

А вот об этой особенности алгоритма, я в книжке не прочел. Да и в JavaDoc об этом вроде ни одним словом. (((

Offtopic: Как на сайт опубликовать картинку с локального диска ?

За что купил, за то и продаю.

http://psy-lob-saw.blogspot.ru/2016/03/gc-nepotism-and-linked-queues.html

Но на графике от JConsole я вижу не то, что хотел бы. Сильно не уверен, что виной коллекция (((

Код от psy-lob-saw однозначно содержит данный эффект. Через JConsole это видно не однозначно, но если добавить банальный подсчет кол-во выделенной памяти и кол-во освобожденной (добавив метод finalize() ), то хорошо видно, minor GC объекты Node чистить отказывается.

На графиках от JConsole можно увидеть все, что хочешь ((( Это как чернильную кляксу рассматривать или на кофейной гуще гадать (((

Плюс видны утечки памяти, которые вообще с коллекциями не связаны. Возможно проистекают от работы JConsole. На моем компе где-то под 10 Mb в oldGen забивается.

На реализации ConcurrentLinkedQueue от JDK 1.8.65 лично я эффект не наблюдаю. Или просто его не заметил. Или в JDK 1.8 исправили.

В общем, х.з.

questioner...
Но если будет такой сценарий:
ABC-> DABC->ABC

Подозреваю "будет фиолетово". Т.е. работать алгоритму стека это не помещает (а для связанного списка, подозреваю, и такая ситуация не возможна).

questioner...
Точнее как Си может создать объект с таким же адресом
delete ptr;
ptr = new SomeType();

При некоторой доли везения (или невезения) адрес в ptr останется тот же самый, а объект будет другим.

IMHO

questionerНа чем основаны подозрения?

Лениво такую ситуацию на листочке рассматривать.

questionerА в джаве всё то же самое, только без delete, всё ещё не понимаю в чем разница
Нет. Без delete такого не получится.
Нет delete - нет и проблемы (что в C, что в Java).