|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
05.01.2016, 16:54 | #1 |
Регистрация: 14.05.2011
Сообщений: 8
|
lock-free linked list
Я реализовал lock-free добавление и удаление в односвязный кольцевой список:
Код:
P.S.: Вопрос освобождения памяти после удаления элемента меня сейчас не интересует. У меня есть возможность убедиться, что элемент больше никто не попытается добавить в список перед его уничтожением. |
05.01.2016, 18:07 | #2 |
Старожил
Регистрация: 13.07.2012
Сообщений: 6,342
|
Вставка еще туда-сюда.
Удаление сломано, от слова "совсем". Начинаем от того, что идем по списку без синхронизации и кончаем ABA проблемой. Например при вызове CAS можете передать один item и item->next от другого. Ref: https://en.wikipedia.org/wiki/ABA_problem |
05.01.2016, 19:23 | #3 | |
Регистрация: 14.05.2011
Сообщений: 8
|
Цитата:
Про ABA проблему, насколько я понимаю, это когда нашу функцию прервали, освободили память из-под элемента и выделили её под новый, а адрес оказался такой же. Либо если элемент удалят и добавят в другой список. В моём случае список только один (элемент после удаления могут добавить только в тот же самый список), а освобождение памяти от элементов не происходит вообще (точнее происходит, но только тогда, когда все операции добавления/удаления уже давно окончены и никто элемент не тронет). Даже если элемент убрали из списка, его указатель next никто не затёр. Так что мы сможем пройти по нему дальше в цикле. Если его добавят в список заново, то мы просто перескочим с середины списка на начало (next указывает на старую голову списка после добавления). Небольшая потеря времени, но не критичная. |
|
05.01.2016, 20:13 | #4 |
Вредный кошак
Участник клуба
Регистрация: 14.10.2012
Сообщений: 1,159
|
1) Зачем volatile?
2) Если один поток позовет addToList, а другой в это время позовет removeFromList, то что получим? 3) Если пока выполняется addToList, другой поток изменит элемент, указатель на который передан? Ну и не знаю как там со списком, но вот Lock-free Dynamically Resizable Arrays от Страуструпа. Можно что-то почерпнуть Последний раз редактировалось Croessmah; 05.01.2016 в 20:17. |
05.01.2016, 20:41 | #5 |
Старожил
Регистрация: 13.07.2012
Сообщений: 6,342
|
|
06.01.2016, 00:02 | #6 |
Регистрация: 14.05.2011
Сообщений: 8
|
Код:
То, что память из-под элемента никто не освободит гарантирует отсутствие вызовов free в основном коде. Просто специфика задачи такова, что элементы не уничтожаются. |
06.01.2016, 01:01 | #7 |
Старожил
Регистрация: 13.07.2012
Сообщений: 6,342
|
Зачем делать CAS(prev->next, item, item->next))?
Если кто-то удаляет предыдущий элемент на next это не влияет а текущий элемент может удалять только один поток, так что вполне можно делать prev->next = item->next... Все это работает, потому что элементы не меняются а в таком случае зачем вообще их удалять... |
06.01.2016, 01:43 | #8 |
Регистрация: 14.05.2011
Сообщений: 8
|
Хм... тут вы правы. Можно немного оптимизировать код, убрав CAS. Однако на работоспособность это влиять не должно.
Вообще, в функции удаления есть какая-то проблема. Сейчас добавил захват mutex перед входом в функцию удаления и освобождение перед выходом. То есть функция добавления может прерывать саму себя и функцию удаления. А функция удаления сама себя прерывать не может, только функцию добавления. Тестирование я провожу следующим образом. Создаю N элементов и добавляю их все в список. Также указатели на все элементы сохраняются в массиве. Затем запускаю 4 потока. Каждый поток без всяких задержек и т. п., пока стоит глобальный флаг testing генерирует 2 случайных числа. Одно от 0 до N - 1, второе от 0 до 1. Если второе число равно 0, то он вызывает функцию добавления в список для элемента с выбранным номером. Иначе вызывает функцию удаления. И его совершенно не волнует есть элемент в списке или нет - это должно быть корректно отработано. Главный поток ждёт несколько сотен секунд, а затем убирает флаг testing и ожидает завершения всех потоков. Внутри функций удаления находится ряд assert, проверяющих, что данные не повреждены. Тест считается успешным, если не сработают assert и ни один поток не зависнет. При этом счётчики показывают, что функции вызываются несколько миллиардов раз (тест выполняется минут 5-10). Так вот. Если вызывать функции полностью lock-free, то срабатывает assert(head != item) в функции добавления в какой-то момент. Если вызывать добавление lock-free, в удаление разрешить только одно в один момент времени, то тест успешно проходится вне зависимости от количества итераций и N (пробовал маленькие значения типа 1 и 2 и большие типа 10 и 100). Получается, что единственная ситуация, которую мой код некорректно обрабатывает - когда во время удаления одного элемента запускается удаление другого. Надо копать в эту сторону... |
06.01.2016, 03:28 | #9 |
Регистрация: 14.05.2011
Сообщений: 8
|
Произвёл некоторое упрощение кода удаления.
Код:
Последний раз редактировалось kivkiv; 06.01.2016 в 03:37. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Linked List вопросы | Kengoo | Общие вопросы C/C++ | 2 | 26.10.2015 19:58 |
C# - Как изменить свойство элемента в list? List<MyClass> | kvi2994 | C# (си шарп) | 1 | 05.03.2015 18:28 |
Linked List. Не могу найти ошибку в коде:( | BroBoa | Общие вопросы по Java, Java SE, Kotlin | 1 | 31.01.2013 22:23 |
Вставка в развёрнутый связный список (Unrolled linked list) | Akron | Общие вопросы по Java, Java SE, Kotlin | 1 | 17.10.2011 07:28 |
Связанный список (Linked list). | lnter | Помощь студентам | 0 | 12.04.2010 17:58 |