Действительно ли там такая вещь как незапертая очередь для нескольких потоки записи или чтение?
Я думал, действительно ли возможно иметь незапертую очередь, когда больше чем один поток читает или пишет? Я видел реализацию с незапертой очередью, которая работала с одним чтением и одним потоком записи, но никогда, чем один для также. Действительно ли это возможно? Я не думаю, что это. Могут / кто-либо хочет доказать его?
5 ответов
Доступно несколько алгоритмов, в итоге я реализовал Оптимистический подход к свободным от блокировок очередям FIFO , который позволяет избежать проблемы ABA за счет тегирования указателя (требуется инструкция CMPXCHG8B на x86 ), и он отлично работает в производственном приложении (написанном на Delphi). ( Другая версия, с кодом Java )
Тем не менее, чтобы быть действительно-действительно безблокировочным, вам также понадобится безблокирующий распределитель памяти - см. Scalable Lock-Free Dynamic Memory Allocation (реализовано в Concurrent Building Block ) или NBMalloc (но пока мне не удалось использовать один из них).
Вы также можете посмотреть ответы для оптимистичных безблокировочных очередей FIFO?
Реализация Lockless Queue в Java допускает как чтение, так и запись. Эта работа выполняется с помощью операции сравнения и установки (которая представляет собой одну инструкцию ЦП).
ConcurrentLinkedQueue использует метод, в котором потоки помогают друг другу читать (или опрашивать) объекты из очереди. Поскольку он связан, глава очереди может принимать записи, в то время как хвост очереди может принимать чтения (при условии, что места достаточно). Все это можно делать параллельно и полностью потокобезопасно.
В .NET 4.0 существует класс ConcurrentQueue (T) .
Согласно C # 4.0 в двух словах, это реализация без блокировок. См. Также эту запись в блоге .
Вам не нужна особая блокировка, а нужен атомарный способ удаления вещей из очереди. Это также возможно без блокировки и с помощью атомарной инструкции test-and-set .
В библиотеке OmniThreadLibrary от Primoz Gabrijelcic (the Delphi Geek) есть динамическая очередь без блокировки: http://www.thedelphigeek.com/2010/02/omnithreadlibrary-105.html