Comments 21
UFO just landed and posted this here
Ещё из надавно прочитанного о потокобезопасных структурах данных, правда здесь речь о списках, но всё равно, надеюсь будет интересно www.tbray.org/ongoing/When/201x/2010/07/13/Lock-Free-Array-Update
+1
Используейте подсветку кода. Лучше всего вот эту: highlight.hohli.com/ — она максимально подходит для Хабра.
А в целом неплохо — хорошая статья.
А в целом неплохо — хорошая статья.
+1
Эта фиговина ж по сути обычный динамический массив… Да и при использовании более одного потока для чтения или записи без блокировок все равно не обойтись. И особенно непонятно, зачем оставлять в очереди один пустой элемент.
+4
Хм странное изобретение. Действительно годно только когда один пишет и один читает. Хотя вроде ничего, было подозрение на один момент. Со списками в данном случае лучше т.к. если сделать массив то возникнет ползание тела очереди по памяти, => придётся делать кольцевой буфер и там элегантность решения потеряется.
0
Похоже, классиков вы не читали. Думаю, эта статья тоже пригодится.
+5
Все бы хорошо, но в c# присвоение не атомарно, поэтому все-равно могут возникать неприятные ситуации.
Поискали бы лучше готовые lock-free контейнеры, чем плодили такие велосипеды
Поискали бы лучше готовые lock-free контейнеры, чем плодили такие велосипеды
0
Я конечно понимаю шарп и всё такое, но такие вещи делают на C++ для гарантированного времени исполнения, чтоб быть уверенным что за 1000000 итераций цикла записи-чтения отклонения по времени исполнения будут минимальны, и шарп тут совсем не подходящий инструмент. Вообще проблема и явы и дотнета и всего полуинтерпритируемого — остутствие стабильности по времени исполнения. Для медиа(об этом упомянул автор) это не совсем подходит.
0
Извиняюсь, что-то меня заело и показалось что примеры кода на C#. Однако неатомарность по умолчанию операторов касается и C++ и вообще многих языков;
+2
Смотря что присваиваете, для указателей(а именно они тут и используются) и простых типов (int и подобные) атомарность вроде даже стандартом гарантируется. Точно сейчас не скажу, мозг отдыхает и искать не хочет. Естественно при присваивании классов с соответствующим вызовом оператора атомарность гарантировать невозможно.
-1
Атомарность присваивания есть (на отдельно взятой архитектуре, а, стандартом не гарантируется, стандарт вообще потоки не обсуждает). Но есть проблема race condition. Ваша реализация подходит только для одного записывающего и одного читающего. Если будет два записывающих — они независимо друг от друга создадут два новых элемента очереди, а потом каждый атомарно (и в неизвестном порядке) присвоит указателю tail адрес хвоста — каждый своего. Второй затрёт то, что записал первый.
0
Реализация не моя, это раз. Про один поток чтения и один записи упомянул и автор и я. Естественно возникнет гонка если будут писать несколько потоков, тогда нужно синхронизировать весь блок добавления айтема. Что такое гонки и прочие многопоточные неприятности я прекрасно знаю.
0
Реализация не моя, это раз.
Извините, перепутал.
Естественно возникнет гонка если будут писать несколько потоков, тогда нужно синхронизировать весь блок добавления айтема.
А вот и не обязательно! Можно делать оптимистичное предположение, что второго пишущего потока нет. Но записывать указатель не присваиванием, а compare and swap. Если CAS провалился, то значит второй поток был, и он успел быстрее нашего. Не страшно, мы повторим. Такая стратегия работает намного быстрее блокировок при условии не очень частой записи (тысячи записей в секунду). См. en.wikipedia.org/wiki/Software_transactional_memory
+2
Simple reads and writes to properly-aligned 32-bit variables are atomic operations.
http://msdn.microsoft.com/en-us/library/ms684122(VS.85).aspx
http://msdn.microsoft.com/en-us/library/ms684122(VS.85).aspx
-1
Очень узкоспециализированный велосипед.
Интересно, но, к сожалению, не практично.
Интересно, но, к сожалению, не практично.
-1
а если нужен стек?
0
Огромное спасибо за статью и всем кто прокомментировал по существу. Очень полезно для изучения.
Сам пользуюсь межпотоковыми очередями (вместо объектов синхронизации), при этом количество проблем с отладкой уменьшается на два порядка. Если удастся сделать универсальную и неблокируемую очередь — будет вообще шикарно. Буду изучать материалы.
Сам пользуюсь межпотоковыми очередями (вместо объектов синхронизации), при этом количество проблем с отладкой уменьшается на два порядка. Если удастся сделать универсальную и неблокируемую очередь — будет вообще шикарно. Буду изучать материалы.
0
опасный код — тут же даже memory barrierов нету.
на двух процессорах такое использовать — реально может взорваться.
на двух процессорах такое использовать — реально может взорваться.
+2
вот как правильно делать — software.intel.com/en-us/articles/single-producer-single-consumer-queue/
+1
Sign up to leave a comment.
Потокобезопасная очередь без блокировок