Потокобезопасная очередь без блокировок

[michurin]

Ещё из надавно прочитанного о потокобезопасных структурах данных, правда здесь речь о списках, но всё равно, надеюсь будет интересно www.tbray.org/ongoing/When/201x/2010/07/13/Lock-Free-Array-Update

[DangerT]

Используейте подсветку кода. Лучше всего вот эту: highlight.hohli.com/ — она максимально подходит для Хабра.

А в целом неплохо — хорошая статья.

[ertaquo]

Эта фиговина ж по сути обычный динамический массив… Да и при использовании более одного потока для чтения или записи без блокировок все равно не обойтись. И особенно непонятно, зачем оставлять в очереди один пустой элемент.

[Aquahawk]

Хм странное изобретение. Действительно годно только когда один пишет и один читает. Хотя вроде ничего, было подозрение на один момент. Со списками в данном случае лучше т.к. если сделать массив то возникнет ползание тела очереди по памяти, => придётся делать кольцевой буфер и там элегантность решения потеряется.

[kureimoru]

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

[Nekuromento]

Все бы хорошо, но в c# присвоение не атомарно, поэтому все-равно могут возникать неприятные ситуации.
Поискали бы лучше готовые lock-free контейнеры, чем плодили такие велосипеды

[Aquahawk]

Я конечно понимаю шарп и всё такое, но такие вещи делают на C++ для гарантированного времени исполнения, чтоб быть уверенным что за 1000000 итераций цикла записи-чтения отклонения по времени исполнения будут минимальны, и шарп тут совсем не подходящий инструмент. Вообще проблема и явы и дотнета и всего полуинтерпритируемого — остутствие стабильности по времени исполнения. Для медиа(об этом упомянул автор) это не совсем подходит.

[Nekuromento]

Извиняюсь, что-то меня заело и показалось что примеры кода на C#. Однако неатомарность по умолчанию операторов касается и C++ и вообще многих языков;

[Aquahawk]

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

[gribozavr]

Атомарность присваивания есть (на отдельно взятой архитектуре, а, стандартом не гарантируется, стандарт вообще потоки не обсуждает). Но есть проблема race condition. Ваша реализация подходит только для одного записывающего и одного читающего. Если будет два записывающих — они независимо друг от друга создадут два новых элемента очереди, а потом каждый атомарно (и в неизвестном порядке) присвоит указателю tail адрес хвоста — каждый своего. Второй затрёт то, что записал первый.

[Aquahawk]

Реализация не моя, это раз. Про один поток чтения и один записи упомянул и автор и я. Естественно возникнет гонка если будут писать несколько потоков, тогда нужно синхронизировать весь блок добавления айтема. Что такое гонки и прочие многопоточные неприятности я прекрасно знаю.

[gribozavr]

Реализация не моя, это раз.

Извините, перепутал.

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

А вот и не обязательно! Можно делать оптимистичное предположение, что второго пишущего потока нет. Но записывать указатель не присваиванием, а compare and swap. Если CAS провалился, то значит второй поток был, и он успел быстрее нашего. Не страшно, мы повторим. Такая стратегия работает намного быстрее блокировок при условии не очень частой записи (тысячи записей в секунду). См. en.wikipedia.org/wiki/Software_transactional_memory

[Aquahawk]

Simple reads and writes to properly-aligned 32-bit variables are atomic operations.
http://msdn.microsoft.com/en-us/library/ms684122(VS.85).aspx

[Aquahawk]

Не стандарт конечно, да и не совсем понятно относительно каких языков сказано, но вполне подойдёт.

[qehgt]

Это API операционной системы, к языкам не имеет отношения.

[Tujh]

Очень узкоспециализированный велосипед.
Интересно, но, к сожалению, не практично.

[tenshi]

а если нужен стек?

[mt_]

Огромное спасибо за статью и всем кто прокомментировал по существу. Очень полезно для изучения.
Сам пользуюсь межпотоковыми очередями (вместо объектов синхронизации), при этом количество проблем с отладкой уменьшается на два порядка. Если удастся сделать универсальную и неблокируемую очередь — будет вообще шикарно. Буду изучать материалы.

[mraleph]

опасный код — тут же даже memory barrierов нету.

на двух процессорах такое использовать — реально может взорваться.

[mraleph]

вот как правильно делать — software.intel.com/en-us/articles/single-producer-single-consumer-queue/