вот правильная:
http://forum.vingrad.ru/act-ST/f-92/t-3162.../p-2258868.html

здесь она же, но bез relacy модификаций
http://liveworkspace.org/code/81347b6f4ba2...09c75a0fbcc31a5

Добавлено @ 18:54
bыло bы неплохо  Но оно просто падает.

Вот, уронил (2 потока вставляют, 2 выкидывают): http://liveworkspace.org/code/34a83f493245...44fb349a193814d


Это сообщение отредактировал(а) Леопольд - 4.12.2010, 09:01

Подумал что можно попроbовать аллокатор написать. В lock free это, наверное, очень сложная штука (а может просто нереальная). Память фрагментируется совершенно непредсказуемо. Может в этом и проbлема...

Решил попроbовать malloc из libatomic-ops-dev
http://manpages.ubuntu.com/manpages/lucid/...c-malloc.3.html
Отпишусь, когда bудут результаты.
судя по описанию, не подходит
Попроbую почитать это когда время bудет (автор Maged M. Michael).



Это сообщение отредактировал(а) Леопольд - 4.12.2010, 10:10

Леопольд

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

Эквивалентна проверке

Но почему тут проверяется на единицу? При входе в pop значение инкрементируется 1 раз, а тут декрементируется (тоже один раз). Т.е. После операции fetch_sub(1) переменная указывает на количество потоков в функции pop на данный момент (не считая текущего потока). А значит проверка на 1 означает, что там есть еще один поток, который может создать проблемы  
Исправлять естественно вот так

azesmcar, fetch_sub возвращает предыдущее значение. Т.е. 1 в данном случае. Если только тут где-то ABA спряталась. Но я не вижу.

Скорее всего, проbлема в аллокации памяти. По отдельности push и pop выполняются bез нареканий, но если смешать...

Везде пишут что стандартные malloc и free раbотают на мьютексе.

Это сообщение отредактировал(а) Леопольд - 8.12.2010, 19:39

Да? Не помню..посмотрел в документации, действительно так и есть..


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

Добавлено через 59 секунд

каким образом это может помешать работать алгоритму? Это может сказаться на производительности, это может лишить структуру статуса lock-free, но никак не должно мешать ей работать правильно.

Согласен, алгоритм просто перестаёт bыть lock free.

Вероятнее всего, проbлема во фрагментации памяти. Если выделять память bлоками одинакового размера, то перестаёт падать:
http://liveworkspace.org/code/3e95623f8da7...1b146a08dd3a6e7


Это сообщение отредактировал(а) Леопольд - 8.12.2010, 19:43

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

Леопольд

Провел несколько тестов. Что-то здесь не так..  пример из книги тоже не работает. Довольно странно, надо поработать над вопросом поглубже.

Добавлено через 1 минуту и 22 секунды
имеется ввиду на gcc 4.5, к сожалению другой библиотеки для тестов у меня нет.

Леопольд

Нашел..в общем аллокатор тут не причем, точнее причем, но не он источник проблемы. Это ABA  
Поигрался с алокатором, в итоге

практически всегда выводит одно и тоже, т.е. если запрашивать память после удаления, системный аллокатор скорее всего вернет ту же область памяти, которую недавно освободил. Это прекрасно объясняет почему разделение push и pop избавляют от проблемы а также то, почему без delete -а все работает - аллокатор не может вернуть старый адрес, так-как тот еще не освобожден.
Позже попробую исправить.

Это сообщение отредактировал(а) azesmcar - 9.12.2010, 09:52

К сожалению далеко не все еще реализовано в GCC  
пробую исправить добавлением счетчика-а, но std::atomic<used-defined-type> еще не реализован.

идея в том, чтобы инкрементировать значение счетчика, тем самым делая указатели на тот же участок памяти разным в разное время. DCAS по идее должен быть Lock-free на всех современных платформах.

Это сообщение отредактировал(а) azesmcar - 9.12.2010, 10:38

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

А вот по поводу ABA, это, наверное оно самое! Надо понять только как 


Это сообщение отредактировал(а) Леопольд - 9.12.2010, 11:01

Посмотри этот пример

выделяется память, возвращается адрес
память освобождается и при следующем выделение памяти аллокатор снова возвращает тот же самый указатель, т.е. выделяет память на том же участке. Тут и возникает ABA, CAS думает, что это тот же указатель, а он другой. В качестве решения можно как-то уникально идентифицировать каждую аллокацию используя счетчик, но тут сложность с реализацией (писал выше об этом). Можно сделать через std::atomic<long long> - его размер 8 байтов, туда можно поместить и счетчик и указатель. Не сильно переносимо конечно, но для теста сойдет  


Не понял причем тут мутекс? Это уже блокировка, мы про неблокирующие алгоритмы говорим.


Это сообщение отредактировал(а) azesmcar - 9.12.2010, 11:09

Это я понял. Я про то предложение, которое процитировал.

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

Не могу понять, где здесь ABA. Но оно вероятнее чем баги в gcc. У меня, кстати, тоже только gcc 4.5.1 под рукой, и на работе и дома.

Это я про стандартные malloc и free. Пока гуглил, не раз попадалось что в gcc они не lock free, т.е. работают с мьютексом.


Можно попробовать проверить, надо добавить std::set<void *> и блокировки при работе с ним. Выделил память, запихнул туда адрес, если он уже там, значит ABA имеет место быть. Освободил память, выкинул адрес из сета. Только вот получится ли воспроизвести ошибку? Блокировка может сделать так, что ошибка пропадёт навсегда. 

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

Это сообщение отредактировал(а) Леопольд - 9.12.2010, 12:06

Леопольд

Проблема та, которую я описывал еще в первом или во втором предположении  

Вот код

Представь, что 1 поток останавливается на выполнении строки

к этому моменту количество потоков в функции pop уже декрементировано и равно 0.
до того, как произойдет сравнение другой поток может изменить этот список, на что ты вполне логично ответил

т.е. если кто-то изменял список, то проверка

не пройдет.

это верно, разве что, если другой поток не изменил этот список, в конце добавив туда элемент с тем же адресом  
представь, что твой код остановился на выполнении этой проверки, в head загужен узел A, а потом другой поток удалил несколько элементов, очистил за ними память, добавил еще один, удалил, и последний удаленный имеет тот же адрес, который на данный момент загружен в head в твоем первом потоке. Это возможно, так-как когда твой первый поток остановится на выполнении проверки, счетчик равен нулю, твой узел (A) в списке to_be_deleted и другой поток волен удалить этот элемент.

Вроде бы так..надо подумать еще раз попозже, на свежую голову  


Это сообщение отредактировал(а) azesmcar - 9.12.2010, 16:25

Наверное, это оно. Попроbую оbойти...

Это сообщение отредактировал(а) Леопольд - 9.12.2010, 19:05