Неблокируемая очередь сообщений для двух потоков

[gribozavr]

Процессоры переставляют местами записи и чтения в память так, как им удобно. Поэтому то, что вы написали, ориентируясь на строго последовательную семантику памяти не сработает в реальности. И только не нужно говорить, что на вашем x86 всё работает.

[amarao]

для этого и существуют write barriers. На x86 они в nop ассемблируются (или вообще в пустой оператор, выкидываемый компилятор), а на более других архитектурах — вполне защищает от подобной самодеятельности.

[amirul]

Write barriers решают ровно половину проблемы, а у x86 есть три разных memory barrier-а: mfence, lfence и sfence. Что еще печальнее, оптимизирующие компиляторы переставляют инструкции независимо от того будет ли целевой процессор переставлять их в рантайме.

[HaronK]

Можно использовать volatile, как было предложено в обсуждении на rsdn или, например, переписать основную часть на ассемблере с memory battier-ами. Это не поможет?
Вообще-то я практически не рабртаю с низкоуровневым программированием и мне было интересно услышать чужое мнение о своей идее.
На выходных постараюсь посмотреть информацию по ссылкам из коментариев и попробую потестировать и сравнить с бустовской реализацией очереди.

[amirul]

volatile (теоретически) ставит полный memory barrier перед и после обращения. Практически же, компиляторы уже достаточно умны, чтоб осознавать, где OOE быть не может: в частности x86/amd64 не переставляют операции чтения относительно других операций чтения, операции записи относительно других операций записи и, если мне не изменяет память, операции чтения и записи к одному адресу, что делает IA ПОЧТИ in-order и это самое опасное как раз потому, что баги вылазят крайне редко и в крайне специфичных условиях.

Более того, существует опасность, что OOE политика изменится в будущих версиях процессора (что уже случалось во времена пентиума про) или что придется перекомпилировать исходник под архитектуру, с гораздо более агрессивным переставлением инструкций (Windows 8 on ARM, например или там на Xbox).

Вместо собственного велосипеда я бы опять таки посоветовал использовать ConcRT (ну или Intel TBB если хочется кроссплатформенности). Причем явное использование неблокирующей очереди чаще всего не нужно. В ConcRT есть Asynchronous Agents Library с message passing-ом (как data-flow ориентированные message block-и, так и control-flow ориентированные agent-ы), в TBB есть пайплайны и флоуграфы.

Серьезно, самописная синхронизация — это настолько же опасно, как и самописная криптография. Начинать велосипедостроение стоит только если не осталось ну совсем никаких других вариантов.

[amirul]

Как уже было отмечено, код некорректный. И да, на x86 он тоже не будет работать на моделях, выпущенных в последние 16 лет (исключая текущие атомы — будущие вполне возможно будут иметь OOE). Этот код можно попробовать «починить» очень аккуратным расставлением lfence/sfence на практически все обращения к writerTop/readerTop, при этом малейшая ошибка будет приводить к «гонкам», принципиально невоспроизводимым в отладчике (отладчики всегда исполняют инструкции по порядку). Кроме того, даже если текущие x86 поддерживают когерентность кеша автоматически, это совершенно не означает, что так будет всегда.

«Никогда не пытайтесь реализовать собственные примитивы синхронизации, если только у Вас нет хотя бы 5-тилетнего опыта, связанного с анализом чужих» (с) Я, только что

«Фраза, оформленная в виде цитаты, выглядит более авторитетно» (с) Я, только что

Что же до «не нашел ничего похожего». Простейший запрос возвращает 7 миллионов результатов. Если это Windows приложение, советую использовать ConcRT

[mt_]

Тем не менее, я очень благодарен автору за то, что он поднял крайне важную и интересную тему. Если Вы так хорошо разбираетесь в многопоточности, могу я попросить Вас написать хотя бы коротенькую статью насчёт корректных (и желательно кросс-платформенных) неблокируемых очередей?

[HaronK]

К сожалению я пока не настолько хорошо разбираюсь в этой области, чтоб написать статью. Возможно позже, когда почитаю дополнительную информацию, то созрею для этого.

[blabla]

Зачем делать lock free алгоритмы? Для производительности? Тогда где тесты сравнения например с std::queue с мьютексом?

[ixSci]

А зачем тесты? Я Вам и без тестов скажу, что код который не лезет в kernel mode работает гораздо быстрее.

[GraD_Kh]

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

[ixSci]

Ну там комментарий про мьютекс был. Так то можно и критические секции использовать, которые user mode. Это я про Windows, если что. Не знаю как в *nix системах это устроено.

[GraD_Kh]

Когда возникает блокировка — то классическая критическая секция обращается к объекту ядра.

[ixSci]

В конечном итоге — да. Но kernel object будет использован только если блокировка произошла, и не будет использован в противном случае. И даже в случае блокировки не будет использован если во время spin lock ресурс был освобожден. Так работает реализация от MS

[GraD_Kh]

Именно, поэтому за счет правильного выбора количества холостых ходов можно сделать обращение к объектам ядра маловероятным. Хотя мы оба пишем про Windows, что происходит в Линуксе с блокировкой я не знаю.

[revol0ution]

В Linux'е POSIX Mutex'ы уже несколько лет как основаны на фьютексах. Механизм работы fast userspace mutex — аналогичен critical section в Windows.

[Harkonnen]

На одноядерном компе. На многоядерном только после спин-лока, длину которого можно явно задать для критической секции.

[blabla]

Lock free не всегда быстрее. Я не про конкретный пример, а в целом. Хотелось бы узнать сколько выйгрыша мы получим при переходе от отлаженного и универсального механизма мьютексов к lock free алгоритмам.

[Ryadovoy]

Главное — сколько геморроя мы получим от lock-free алгоритмов?

[HaronK]

Постараюсь на выходных потестировать.

[adontz]

Добавлю к словам предыдущих комментаторов, что множество полезной и корректной информации можно найти по адресу www.1024cores.net/
Есть англоязычный и русскоязычный разделы, а сам автор русскоязычный.

[afiskon]

Вы исходите из неверного предположения, что операция a = b; атомарна, потому код и неверен (хотя, быть может, это и проявится лишь в 1 случае из 10 000). Тем не менее, обойтись без мьютексов в данной задаче можно. Вот небольшая подборка материалов по теме: afiskon.blogspot.com/2011/06/blog-post_06.html

[ixSci]

Можете посмотреть как эту задачу решил Герб Саттер:
для 2 потоков
общий случай

[jcmvbkbc]

Циклический буфер с двумя указателями (на начало валидных данных и на начало невалидных данных), которыми владеют поток-читатель и поток-писатель — классическое решение этой проблемы.

[kuda78]

В свое время при решении аналогичной проблемы воспользовался Interlocked SList которые реализует односвязанный список.

Добавление данных при помощи метода InterlockedPushEntrySList.

Выборка данных путем очистки выборки и одновременной очистки всего стека и последующего его переворота.

Ниже приведен кусок часть delphi кода по реализации добавления и выборки данных.

function T_InterlockedQueue.PopAll: I_IntrefaceEnumerator;
var
  head: PInterlockedQueueItem;
begin
  head := RevertSList(PInterlockedQueueItem(InterlockedFlushSList(FHeader)));
  Result := T_InterfaceEnumerator.Create(head);
end;

procedure T_InterlockedQueue.Push(const AItem: IInterface);
var
  listItem: PInterlockedQueueItem;
begin
  listItem := GetMemory(sizeof(T_InterlockedQueueItem));
  ZeroMemory(listItem, sizeof(T_InterlockedQueueItem));
  listItem.Data := AItem;
  InterlockedPushEntrySList(FHeader, PSLIST_ENTRY(listItem));
end;

[kuda78]

Надо приучить себя читать сообщения, прежде чем нажать «написать»…

Выборка данных путем полной выборки и одновременной очистки всего стека и последующего переворота выбранных данных.

[kuda78]

В данном случае была задача один читатель множество писателей.

[artemaliev]

1. ОЧЕНЬ редко встречается нагрузка, при которой, lock-free queue работает быстрее чем написанная с использованием mutex/spin-locks. Код для двух потоков точно бесполезен. (хотя есть нюансы, там где скорость не главное)
2. Microsoft VC генерирует mfence для volotile переменных, gcc нет. но лучше их руками расставлять. Java тоже обещает аналог mfence для volotile.
3. mfence почти так же дорого как и lock cmpxchg (тот что в spin locks)
4. a=b атомарна для 64bit на 64 битной intel платформе (и почти везде :)

[amirul]

Согласен со всеми пунктами, но по п.2 небольшое уточнение: MSVC вставляет «заборы» только там, где действительно может произойти переупорядочение.

[Colwin]

Код не является потокобезопасным.

Вот пример:

template<class TYPE>
void LockFreeQueue2<TYPE>::Enqueue(TYPE* data)
{
...
    if (writerTop) // Если очередь Писателя уже существует, добавляем елемент в ее конец
    {
        // Здесь сейчас первый поток
        writerBottom->next = data;
        writerBottom = data;
    }
...
}

template<class TYPE>
bool LockFreeQueue2<TYPE>::Dequeue(volatile TYPE*& data)
{
...
         if (isWriterFinished && writerTop) // Проверяем Писетельскую очередь, если он закончил свою работу
        {
            readerTop = writerTop;
            // Здесь сейчас второй поток
            writerTop = NULL;
        }
}

template<class TYPE>
bool LockFreeQueue2<TYPE>::Flush()
{
    ...
    if (!readerTop) // Проверяем можно ли сбросить Читателю свой остаток
    {
        // Здесь сейчас третий поток
        readerTop = writerTop;
        return true;
    }
}