http://cppjournal.blogspot.com/
Здесь есть статья про lock_free программирование. Для асинхронного удаления элемента используются весьма сложные конструкции. Я вижу решение таким. Довольно просто, и эффективно. Но, может bыть я что-то недопонимаю, и на самом деле здесь bаги?
неbольшой тест LWS


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

Вроде bы раbотает, даже если сперва запустить потоки, которые выкидывают элементы из стека...http://liveworkspace.org/code/394a8b9144ffe5cb97781cc55598cdb9

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

там их несколько. о какой именно идет речь?
второе - есть либа relacy. о ней тоже говорится в третьей статье.

Леопольд

Ну для начала скажу, что тут есть проблемы не только с очисткой памяти, здесь не предусмотрен pop() на пустом стеке.
Что касается проблемы очистки памяти, опишу ситуацию.
В стеке 10 элементов, 2 потока одновременно выполняют pop().

1 поток выполняет все строчки до 4-ой. Выполняет конструкцию
while (!m_head.compare_exchange_weak(old_head, old_head->next));
compare_exchange_weak возвращает false, т.е. ожидается еще одна итерация и поток передает управеление другому потоку
2 поток входит в pop(), выполняет все действия, удаляет head (так-как old_head != &end), возвращает значение и передает управление 1-ому потоку.
1 поток пытается выполнить еще одну итерацию в цикле while (!m_head.compare_exchange_weak(old_head, old_head->next));
но old_head указывает на удаленную область памяти и old_head->next - обращение к ней, что ведет за собой неопределенное поведение.

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

Это сообщение отредактировал(а) azesmcar - 28.11.2010, 07:04

забавно-то как  

Отвлекся..вернемся к делу

http://liveworkspace.org/code/b6e8617b670b...85227a2cb07ea49
всего лишь несколько последовательных запусков и...
вообще непонятен смысл этой статической переменной, в ее роли мог бы выступать 0, и не надо было бы проверять при удалении.

boostcoder

Ну разве что для логирования может сгодиться, другого применения я не вижу  


Такой тест придется запускать ни один раз, чтобы проверить работоспособность. Лучше использовать 

правда придется немного модифицировать код, но эта жертва, на которую стоит пойти  

Это сообщение отредактировал(а) azesmcar - 28.11.2010, 07:56

Это "для сеbя", надо разоbраться с relacy, а это время.

Так и знал, что что-то упустил. Спасиbо!

Для этого end и нужна. Она зацикливает конец списка на сеbя.


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

  
Полегчало?

Лучший спосоb разоbраться - сделать свой, возможно уbогий, вариант.


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

Да, не заметил



Пожалуйста.

поbорол при помощи статического указателя (только это уже не lock_free, а wait_free):Недостаток, много раbоты в холостую (spin lock). Достоинство, простота реализации. Теперь пора вторую статью читать. 

Рельна ли ситуация, когда поток подменил указатель и внезапно умер, не завершив раbоту? Если да, то bудет deadlock.

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

А в чем замысел? Почему compare_exchange заменен на if и exchange?
Вообще комментарии бы не помешали, не знаю будет работать или нет, детально не смотрел, но насколько я понял

  
и эта работа в холостую по сути лишает преимущества перед блокировками.


дедлока тут по определению быть не может. Дедлок может возникнуть только при блокировании, а тут нет блокирования.

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

Когда смотришь с уровня новичка, всё выглядит весьма запутанно. Пытаюсь распутать. Здесь получился spin lock. 
compare_exchange сложнее читать, он неинтуитивно записывает новое значение атомарной переменной по ссылке в первый аргумент. 

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

spin lock - тоже lock, но в user-mode и никак не может быть wait-free.
wait-free функция означает, что любой поток, начавший выполнять эту функцию закончит выполнение за N-ое количество шагов, и N никак не зависит от других потоков.

Там слишком мало информации, это всего лишь базовые сведения, если интересует тема могу подкинуть литературу, но только на английском.

Это сообщение отредактировал(а) azesmcar - 28.11.2010, 17:22

Вроде как не совсем. Нет переключения контекста, но тоже есть куча минусов.

Не откажусь от ссылок на признанных авторов в данной теме. Спасиbо! Английский даже лучше, иногда перевод тяжелее понять.

Добавлено @ 17:35
 Действительно, показалось что по смыслу подходит, только перепутал одно с другим...


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

Получается, что compare_exchange тот же spin lock.

Завтра пришлю.


Нет, spin-lock - пустая итерация в ожидании, пока другой поток не изменит состояния некой переменной, т.е. это блокировка, mutex работает точно также, просто ожидание не тратит процессорных ресурсов, а compare_exchange ничего не блокирует, он атомарно производит некое действие, никакой другой поток не дожидается его завершения, чтобы продолжить свою работу.

Это сообщение отредактировал(а) azesmcar - 28.11.2010, 21:03

если в личку, просьба и мне выслать 

выложу сюда 

Добавлено через 40 секунд
просто много ссылок в закладках на работе, лень снова искать.

Я, конечно, имел ввиду в цикле. Если, груbо говоря, 300 процессов bудут постоянно менять переменную, кто-то из них может начать голодать. 
Здесь за флажок принимается не какое-то, заранее определённое значение, а смена значения. Если не изменилось, то поменять, но только один процесс сможет это сделать. Остальные, перейдут на следующую итерацию. 

Т.е., наверное, можно сказать, что это spin lock наоbорот - пустая итерация (а может и не пустая) в ожидании, пока другие, bолее удачливые потоки не перестанут изменять состояние переменной.

Получается, что если spin lock затрагивает такое же количество тактов, то производительность не упадёт, и шансы на голодание останутся на том же уровне.

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

Это не делает из любой итерации блокировку. Эта итерация не блокирует другие потоки, как это делает spin lock, но количество итераций все таки зависит от того, что делают другие потоки, потому эта функция не wait-free.

Статьи
эта статья на русском, не помешает ознакомиться
Что такое модель памяти?
немного википедии
http://en.wikipedia.org/wiki/Non-blocking_algorithm
и далее все на языке Шекспира
Herb Sutter - Lock-Free Code: A False Sense of Security
Andrei Alexandrescu - Lock-Free Data Structures
Andrei Alexandrescu, Maged Michael - Lock-Free Data Structures with Hazard Pointers
Thomas Edward Hart Thesis
Maged Michael - Hazard Pointers
Herb Sutter - A Principle-Based Sequential Memory Model for Microsoft Native Code Platforms
Geoff Langdale - Lock-Free programming
ABA problem


Это сообщение отредактировал(а) azesmcar - 29.11.2010, 08:43

azesmcar, премного благодарен!

Бывает такой бред пишу... 
На spin lock'е при вытесняющей (preemptive) многозадачности, очень легко dead lock получить. Когда процесс с более низким приоритетом был прерван сразу после того, как он сделал spin lock. В lock free это невозможная ситуация.

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

это называется live-lock.

Добавлено через 34 секунды
deadlock не тратит процессорные ресурсы.

azesmcar, ясно, спасибо.

deleted

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

Не могу скачать relacy... 

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

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

На гугле запретили выкладывать zip файлы.
Качать надо отсюда, добавлю в статью.
http://sites.google.com/site/1024cores/downloads

azesmcar, спасибо!

Так вроде работает, теперь надо с relacy попробовать протестить.

Не, нифига, здесь утечка памяти...

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

relacy не помог...   
http://liveworkspace.org/code/8ed457a04766...847bee388deb79b


запустил на ночь, для 200000 операций push/pop параллельно.

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

где? на LWS ?! 

Добавлено через 1 минуту и 24 секунды
и relacy на LWS нет. хотя подумываю установить. карман ведь не тянет 

Добавлено через 2 минуты и 48 секунд
Леопольд, скажи, у тебя есть где реально применить сие?

Нет конечно, локально.
Уменьшил до 200000, bоюсь к утру LIVELOCK напишет иначе...

Добавлено @ 23:11
Пока нет. Просто проbую свои силы. Потом хеш-таbлицу хочу написать и распараллелить A* 
Статью Тиграна прочёл и, неожиданно увлёкся. Кажется мне что в ИИ, bудущее за lock free алгоритмами.


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

установил relacy.
вот тест: http://liveworkspace.org/code/08782ad50b2d...3c7ef1f00810096

Добавлено @ 23:24
только не понимаю что там выводится, и что должно выводится  

Это сообщение отредактировал(а) boostcoder - 1.12.2010, 23:25

чем именно он должен был помочь?


если нужно куда-то применить, советую взглянуть на libcds


О! Отлично.

Леопольд

Александреску в одной из статей использует такой трюк.
Инкапсулируется некий тип (например map)
Чтение - wait-free безо всяких итераций, просто возвращение объекта.
Запись - создание копии, добавление новой записи и замена внутреннего объекта.
Ну и конечно же опять встает вопрос удаления старой копии.
Это можно построить на шаблоне и применять эту технику для любого типа, но естественно, это эффективно только тогда, когда запись является редким явлением. Упор делается на  скорость чтения высокая.

Это сообщение отредактировал(а) azesmcar - 1.12.2010, 23:43

Что значить throughput в relacy? Почему-то только в ночных тестах равен нулю.

Добавлено @ 06:46
Где-то, видимо двойной delete. Не могу понять где... 
Мне, вроде бы, удалось обойти добавление эелементов обратно в очередь на удаление. Это может сильно поднять производительность.
http://liveworkspace.org/code/8ed457a04766...847bee388deb79b

Добавлено @ 06:49
Поток не успел завершить раbоту до достижения  Это, как я понял, количество ($) через которые он прошёл.


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

Этого не знаю...  

Оно, кстати, иногда работает, хотя нагрузка серьёзная. Два потока "выкидывают" элементы другие два "вставляют", в сумме 2000000 элементов.
http://liveworkspace.org/code/705bf2998c43...9a3bced3e591522
Сперва пытался сделать вариант с возвратом элементов обратно. Но он просто "вешался" под такой нагрузкой.

Может я как-то неправильно тестирую? Не получается воспроизвести...


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

Леопольд

Добавь хоть комментарии и опиши алгоритм.

Он похож на тот, который в статье. Основное отличие, работа с очередью удалённых - m_deleted_head:

1. Загружаю m_deleted_head (указатель на начало очереди на удаление)
2. умешьшаю счётчик потоков и если он стал равен нулю (значит нет потоков, которые работают с тем же m_head - указатель на "выкидываемый" элемент).
3. пытаюсь сделать один strong CAS указателя m_deleted_head и зацикленного на себя указателя &end (признак конца очереди).
Рассчёт на то, что если удалось подменить m_deleted_head с первого раза, значит ни один поток не успел его поменять и список можно спокойно удалять.

Если не удалось подменить, то пихаю удаляемый элемент в очередь на удаление.

Ещё, возможно, одно отличие (точно не уверен, может в статье так же). Попытка освободить  ненужную занятую память происходит каждый раз, даже если сам стек оказался пустым.

накидал это в виде комментариев в предыдущий пост
http://forum.vingrad.ru/act-ST/f-92/t-3162.../p-2258093.html



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

Заработало!   (поменял 1. и 2. местами  и бага "прибил")
8000000 элементов, 4 потока: 2 удаляют, 2 добавляют.
http://liveworkspace.org/code/a1e0bde56b2e...720510a50a6379c

relacy тоже удовлетворён...
Да и показатели улучшились.

Если всего 2 потока удаляют то, average length of non deleted queues = 0.09.

P.S. Пожалуй этот вариант уже не так "убог"...
P.S.S А вообще, очень даже ничего! 

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

блин  убогая фигня, опять падает... 
на одноядерном процессоре, почти сразу.

бага "прибил". Всё чудесно!   


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

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

Леопольд

Сколько всего изменилось  я не успеваю.


Мало того, что нашел..так еще и прибил  


ага, посмотрю.


Добавь в relacy количество потоков и итераций и оставь на ночь.

Плохо приbил...   Надо передохнуть, уже не сооbражаю ничего...
http://liveworkspace.org/code/1d1704acbdea...fc11a835f900d4e

Леопольд

Я бы хорошенько пересмотрел этот код. Это и так сложно, а у тебя усложнено еще больше. Комментарии нужны в первую очередь для себя, раздели все на мелкие функции, это заметно облегчит и чтение и понимание того, что происходит. Представить в уме возможные варианты выполнения для нескольких потоков, которые в любой момент могут делать все, что угодно и так сложно, а это еще усложняется кодом. Для начала напиши список, который работает, но с утечками, протестируй, а потом добавляй очистку памяти отдельными функциями. Отдели как нибудь ту часть, которая потенциально может содержать ошибку (т.е. часть очистки памяти) от той, которая протестирована и работает. На данный момент код функции pop слишком большой, чтобы можно было найти в нем ошибку.

azesmcar, пытаюсь рафинировать, потихоньку...

И прихожу к вывод что нельзя использовать обычную связку malloc/free
Запускаю два потока, один добавляет, другой удаляет. Между собой у них только одна атомарная переменная (указатель на голову стека), relacy тесты проходят с опцией (p.search_type = rl::fair_full_search_scheduler_type;) которая всё пространство состояний тестирует. Всё ок.
Но, как только пытаюсь запустить на одноядерной машине (Ubuntu 10.04, g++ 4.5.1): Это, видимо, если вызвать malloc до того как free закончит работу.

Сейчас соображу спин лок на выделение памяти и проверю. Google говорит что есть такая штука как lock free malloc



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

Вот рафинированный код.
LWS relacy


Не получается уронить (если не увеличивать количество потоков), видимо на сервере несколько ядер:
http://liveworkspace.org/code/260469bbd4f7...d03e4ad1d4b26e7
на работа одноядерная машина, на ней падает почти сразу.


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

С таким спин локом, тоже падает...
Может я зря грешу на malloc/free?

P.S.
Временами, relacy на спин локе зависает наглухо...

P.P.S Пока malloc не отработает, память в список не записывается. Но он может быть вызван до того, как free закончит работать (а может ещё операционка что-то делает с ОЗУ?).
Что ж, это за зверь такой: "lock free malloc"?

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

Очевидно что отдельно от push, pop отрабатывает нормально:
сперва забиваю стек (10 миллионов элементов), потом 100 потоков начинают дёргать pop
что радует, когда последний поток закончил работать, вся память полностью освободилась (в отличие от предыдущих "кривоногих" версий).
Шанс получить "хвост" в конце работы всех потоков пренебрежительно мал. И чем больше потоков, тем меньше шансов. Самый невезучий подчищает за всеми.

http://liveworkspace.org/code/1d76fb72fafa...af5403f5ae0b02e

На одноядерной (Ubuntu 10.04 g++4.5.1) тоже работает без сбоев.



Тут вывод поинтереснее: http://liveworkspace.org/code/81347b6f4ba2...09c75a0fbcc31a5


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

Леопольд

Добавил немного комментариев, теперь давай прочитаем код

начнем со строки 24.
тут ты сперва проверяешь, что это единственный поток в функции pop (кстати все время хочу спросить почему value - 1 == 0 а не value == 1?).
потом проверяешь, что никто не менял m_deleted_head и он все еще равен head-у, т.е. поменять может в том случае, если в этом промежутке создался другой поток.
дальше, если ничего менялось ты удаляешь все элементы.
Вот тут то и проблема. Представь, что 1 твой поток дошел до строки 33, удали элемент, на который на данный момент указывает m_deleted_head (так как m_deleted_head и head указывают на ту же область памяти) и передал управление второму, который пытается добавить следующий элемент в список на удаление, но натыкается на UB на строке 20.
В примере я не зря очищал m_deleted_head и отделял от него весь список в локальный указатель, это делалось для того, чтобы другой поток в это время не смог с ним работать.

Если поток1 находится на двадцатой строке, то m_threads_on_lap($).fetch_sub(1) - 1 == 0 не выполнится. Если потокN дошёл до 9-й строки, то он никак не может получить тот же указатель "head" из-за 10 строки.

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

Ты забываешь, что это две разные проверки и они НЕ атомарны. Потому я и отделил их в два отдельных if-а, чтобы было нагляднее.
Возможна такая ситуация: первая проверка выполняется, перед началом выполнения второй, другой поток входит в функцию pop.

Добавлено через 1 минуту и 56 секунд


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

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

Можно и сильнее нагрузить, результать будет тот же.
100 потоков удаляют 10000000 элементов из стека размером 100000001 элементов:
http://liveworkspace.org/code/81347b6f4ba2...09c75a0fbcc31a5

пусть выполняет. Он уже никак не сможет получить тот же указатель из m_head. Если потокY в этот момент заменит m_deleted_head, то у него указатель на начало очереди на удаление, в которой и "наш" сидит уже. Оставляем очищать ему.

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

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

Я пытался найти способ ответвить один поток в своё русло при помощи одного только стчётчика, но так и не смог. Но тут помогла compare_exchange_strong на m_deleted_head. Тот, кто смог её выполинть, гарантированно владеет списком указателей, с которыми больше никто не работает. Поэтому вся работа с указателями происходит до того как уменьшается счётчик. Я и имя ему такое дал, что бы с гонками ассоциировалось. Чистит хвосты самый нерадивый. 
Это, кстати, наглядно из логов видно (пару постов назад)


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

Леопольд

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

процитирую статью


описываю проблемную ситуацию, номера строк смотри в моем коде.
1-ый поток входит в pop
2-ой поток входит в pop
3-ий поток входит в pop
1-ый поток продолжает выполнение и доходит до строки 27, так-как остальные два потока пока не инкрементировали значение счетчика
2-ой поток начинает выполнение и доходит до строки 10
3-ий поток начинает выполнение и доходит до строки 10
2-ой поток удаляет элемент из списка и дойдя до строки 20 помещает его в список на удаление
1-ый поток продолжает работу и выделяет список в локальную переменную m_deleted_head
1-ый поток доходит до цикла на строке 30 и начинает удалять элементы, включая тот, который туда поместил 2-ой поток
3-ий поток просыпается и все еще ссылается на тот элемент, который поместил в список на удаление 2-ой поток
3-ий поток при попытке выполнить 10-ую строку вылетит с ошибкой

в двух словах: один поток удаляет объект, помещенный в список другим поток, на который ссылается третий.

Это сообщение отредактировал(а) azesmcar - 3.12.2010, 15:06

Этого не будет. 1-ый поток один раз попытается сделать strong CAS, но 2-ой поток изменил его, пэтому 1-ый поток получит false (не сможет выделить список в локальную переменную).

Но такая бага действительно имела место быть в предыдущих вариантах (по моему, relacy мне её показал).

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

Добавлено @ 15:31
Вариант из статьи форсирует алгоритм "гулять" по очереди туда-обратно. К тому же, он вставляет очередь обратно по одномоу элементу, постоянно мешая другим потокам, что очень негативно сказывается на производительности. С 10 миллионами элементов он будет работать очень долго. Сперва я пытался сделать что-бы он вставлял обратно очередь сразу всю целиком, но всё равно приходилось "гулять" из конца в конец. Именно поэтому, я решил попробовать сделать иначе. Обойти этот момент. Похоже удалось.

Но возникает какая-то загадочная проблема с выделением и освобождением памяти параллельно.


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

Да, верно..невнимательный я что-то, не обратил внимания на if. А тут точно есть проблема в функции pop? Я ничего другого не вижу, вроде все в порядке.

Похоже что нет. Я пришёл к мнению что с pop всё ОК. Пробовал под большой нагрузкой и relacy всё проверил. 


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

где и как это проявляется?

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

P.S. пора домой...


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