Комментарии 21
НЛО прилетело и опубликовало эту надпись здесь
Ещё из надавно прочитанного о потокобезопасных структурах данных, правда здесь речь о списках, но всё равно, надеюсь будет интересно www.tbray.org/ongoing/When/201x/2010/07/13/Lock-Free-Array-Update
Используейте подсветку кода. Лучше всего вот эту: highlight.hohli.com/ — она максимально подходит для Хабра.
А в целом неплохо — хорошая статья.
А в целом неплохо — хорошая статья.
Эта фиговина ж по сути обычный динамический массив… Да и при использовании более одного потока для чтения или записи без блокировок все равно не обойтись. И особенно непонятно, зачем оставлять в очереди один пустой элемент.
Хм странное изобретение. Действительно годно только когда один пишет и один читает. Хотя вроде ничего, было подозрение на один момент. Со списками в данном случае лучше т.к. если сделать массив то возникнет ползание тела очереди по памяти, => придётся делать кольцевой буфер и там элегантность решения потеряется.
Похоже, классиков вы не читали. Думаю, эта статья тоже пригодится.
Все бы хорошо, но в c# присвоение не атомарно, поэтому все-равно могут возникать неприятные ситуации.
Поискали бы лучше готовые lock-free контейнеры, чем плодили такие велосипеды
Поискали бы лучше готовые lock-free контейнеры, чем плодили такие велосипеды
Я конечно понимаю шарп и всё такое, но такие вещи делают на C++ для гарантированного времени исполнения, чтоб быть уверенным что за 1000000 итераций цикла записи-чтения отклонения по времени исполнения будут минимальны, и шарп тут совсем не подходящий инструмент. Вообще проблема и явы и дотнета и всего полуинтерпритируемого — остутствие стабильности по времени исполнения. Для медиа(об этом упомянул автор) это не совсем подходит.
Извиняюсь, что-то меня заело и показалось что примеры кода на C#. Однако неатомарность по умолчанию операторов касается и C++ и вообще многих языков;
Смотря что присваиваете, для указателей(а именно они тут и используются) и простых типов (int и подобные) атомарность вроде даже стандартом гарантируется. Точно сейчас не скажу, мозг отдыхает и искать не хочет. Естественно при присваивании классов с соответствующим вызовом оператора атомарность гарантировать невозможно.
Атомарность присваивания есть (на отдельно взятой архитектуре, а, стандартом не гарантируется, стандарт вообще потоки не обсуждает). Но есть проблема race condition. Ваша реализация подходит только для одного записывающего и одного читающего. Если будет два записывающих — они независимо друг от друга создадут два новых элемента очереди, а потом каждый атомарно (и в неизвестном порядке) присвоит указателю tail адрес хвоста — каждый своего. Второй затрёт то, что записал первый.
Реализация не моя, это раз. Про один поток чтения и один записи упомянул и автор и я. Естественно возникнет гонка если будут писать несколько потоков, тогда нужно синхронизировать весь блок добавления айтема. Что такое гонки и прочие многопоточные неприятности я прекрасно знаю.
Реализация не моя, это раз.
Извините, перепутал.
Естественно возникнет гонка если будут писать несколько потоков, тогда нужно синхронизировать весь блок добавления айтема.
А вот и не обязательно! Можно делать оптимистичное предположение, что второго пишущего потока нет. Но записывать указатель не присваиванием, а compare and swap. Если CAS провалился, то значит второй поток был, и он успел быстрее нашего. Не страшно, мы повторим. Такая стратегия работает намного быстрее блокировок при условии не очень частой записи (тысячи записей в секунду). См. en.wikipedia.org/wiki/Software_transactional_memory
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
Очень узкоспециализированный велосипед.
Интересно, но, к сожалению, не практично.
Интересно, но, к сожалению, не практично.
а если нужен стек?
Огромное спасибо за статью и всем кто прокомментировал по существу. Очень полезно для изучения.
Сам пользуюсь межпотоковыми очередями (вместо объектов синхронизации), при этом количество проблем с отладкой уменьшается на два порядка. Если удастся сделать универсальную и неблокируемую очередь — будет вообще шикарно. Буду изучать материалы.
Сам пользуюсь межпотоковыми очередями (вместо объектов синхронизации), при этом количество проблем с отладкой уменьшается на два порядка. Если удастся сделать универсальную и неблокируемую очередь — будет вообще шикарно. Буду изучать материалы.
опасный код — тут же даже memory barrierов нету.
на двух процессорах такое использовать — реально может взорваться.
на двух процессорах такое использовать — реально может взорваться.
вот как правильно делать — software.intel.com/en-us/articles/single-producer-single-consumer-queue/
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Потокобезопасная очередь без блокировок