LINUX.ORG.RU
Форум — Development  

Lock-free Circular Fifo Buffer - возможно ли такое?

 , , ,


1

1

Вот есть CircularFifoBuffer.
Его можно обернуть в BufferUtils.synchronizedBuffer(), тогда он будет синхронизованным, но, как я понимаю, не будет lock-free?

Возможно ли его сделать lock-free (CAS, как в AtomicInteger.incrementAndGet(), только здесь будет что-то вроде addAndRemove())?
Правильно ли я понимаю, что невозможно сделать атомарной операцию удаления одного элемента + добавление другого?

★★★★★

Последнее исправление: kovrik (всего исправлений: 1)
← рекурсивный прототип
С++ Проверка доступа в интернет с помощью библиотеки curl →

Ответ на: комментарий от maxcom

Ну я так понял, что да, они используют у себя RingBuffer.
Но, хотелось бы нативную реализацию, без привязки к какому-либо фреймворку.
Судя по всему, такого стандартного класса нет, а глядя на код RingBuffer'а в Disruptor'е - не так просто сделать самому такой класс «на коленке».

kovrik ★★★★★
() автор топика
Ответ на: комментарий от maxcom

Вообще, я правильно понимаю, что все lock-free алгоритмы применимы только к одному объекту (увеличить значение и вернуть/ сравнить и заменить и тд)?
Если нужно, например, взять содержимое RingBuffer'а, произвести вычисление, потом добавить результат в RingBuffer, то такая процедура требует как минимум трех операций и сделать ее атомарной никак не получится (при этом, она будет зависеть от содержимого RingBuffer'а т.е. от состояния нескольких объектов - и тут без lock'ов не обойтись)?

kovrik ★★★★★
() автор топика
Последнее исправление: kovrik (всего исправлений: 1)
Ответ на: комментарий от kovrik

Думаю можно что-то придумать, с использованием spin-lock'а

maxcom ★★★★★
()
Ответ на: комментарий от kovrik

Если нужно, например, взять содержимое RingBuffer'а, произвести вычисление, потом добавить результат в RingBuffer, то такая процедура требует как минимум трех операций и сделать ее атомарной никак не получится (при этом, она будет зависеть от содержимого RingBuffer'а т.е. от состояния нескольких объектов - и тут без lock'ов не обойтись)?

Atomic != Lock-free. Точнее то что Lock Free не обязательно Atomic. Насчет обратного, тут сложнее.

Атомарные операции в принципе редко бывают. Чаще всего все упирается в Optimistic Locking, Compare and Swap цикл. Берешь данные, запоминаешь, модифицируешь, пытаешься поменять. Вышло - успех. Если кто-то значение заменил уже - заново. Так работает AtomicLong (atomic как моя жопа) между прочим, и никакой магии. И ад начинается когда потоков много. В Java 8 вот LongAdder придумали, который использует хеш-код потока чтобы добавлять значения в одельные buckets/cells. А сумма там вообще без синхронизаций, как попало, гарантий нет. Есть только гарантия что не будет порваных Long, потому что они volatile

vertexua ★★★★★
()
Последнее исправление: vertexua (всего исправлений: 1)
Ответ на: комментарий от vertexua

Для одного producer-а и одного consumer-а обычный RingBuffer будет идеальным lockfree-решением.

Если участников больше, то настоящий lockfree тут (увы) не получится. Могут быть варианты со spinlock и двумя CAS с dirty-state посередине, но не настоящий lockfree. Второй вариант можете подсмотреть в dpdk.org, там так очереди сделаны.

Ну и потролльте организаторов, а то вот думают брать http://www.highload.ru/2013/abstracts/1250.html или нет :)

ly ★
()
Последнее исправление: ly (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← рекурсивный прототип
Development
С++ Проверка доступа в интернет с помощью библиотеки curl →