Ясно, спасибо

Есть вопрос по поводу многопоточности. Занимаюсь самописным компилятором, который изначально был задуман для однопоточных программ, то есть он не генерирует код с read и write барьерами. Создаю несколько потоков в Windows при помощи CreateThread, которые должны разделять общую структуру данных: двусвязный список с указателями на начало и конец списка. Взаимоисключение реализовано на основе алгоритма Деккера, то есть busy wait. В некоторых случаях происходят ошибки при добавлении в этот двусвязный список. Там простые команды и их внимательно просмотрел. Логических ошибок там нет. Ошибки связываю с тем, что хотя один поток изменил список, для другого потока эти изменения оказались еще не видимы. Какие есть варианты, кроме добавления команд процессора: read и write барьеров. Возможно, есть какая-нибудь WinApi команда, которая заставит процессор скинуть все данные из кэша в основную память. Может быть есть какие-нибудь хитрости, например, изменить указатель, а затем считать этот указать, и при этом должно произойти обновление в памяти.

What about atomic values/types and CAS?

В WinApi по-любому должны быть conditional (signal) variables — можно их подключить, но будет больше костылей в данном случае, КМК.

По поводу CAS (Compare and Swap) это все равно надо добавлять новую инструкцию в компилятор. Может быть можно как-нибудь обойтись без добавления новых инструкций. А с использованием простых средств достичь. Только что подумал, может быть добавить еще одно поле в запись: номер версии. И если другой поток видит, что номер версии не поменялся, то значит и указатели не обновились и надо немного подождать.

Или что-то типа lock-free списка реализовать, тогда как мне кажется, если какие-то изменения еще не отразились, то это не должно приводить к ошибкам в работе с очередью.

вроде без lock-free уже не модно?

а насколько иммутабельные структуры Окасаки (Clojure) являются cache-friendly?

По поводу lock-free и double list пишут: "Например, double linked list на сегодняшний день не имеет неблокирующего алгоритма реализации. Во вторых это очень сложно даже для экспертов. Можно написать неблокирующий код, который работает, но очень сложно написать его правильно и оптимально." http://cppjournal.blogspot.com/2010/11/lock-free-1.html

atomics and CAS есть в C11 stdlib. Наверное и в других библиотеках есть.

В том самописном компиляторе stdlib не используется, только голый x86 и WinApi.

Но похоже на то, что нужно взять нормальную библиотеку и очередь из неё.

На эту тему есть классическая статья Боема "Threads Cannot be implemented as a library". Обязательное чтение https://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf

Можно, наверно, и реализовать самому. Зачем тащить целую библиотеку, если нужен только один алгоритм.

TL;DR: Многопоточность должна учитываться в дизайне языка и компилятора. Нельзя только полагаться на внешние библиотеки которые реализуют всякие "мнопоточные примитивы".

LMGTFY: https://docs.microsoft.com/en-us/windows/win32/procthread/synchronizing-execution-of-multiple-threads

Так алгоритм Деккера не корректен на x86, и тем более на всяких ARM-ах. Самое простое что можно сделать, это воткнуть mfence после каждой записи. Тогда у вас будет гарантироваться  sequential consistency, правда ценой перформанса кода.

Непонятно почему вы просто не хотите использовать критические секции если уж вы говорите о WinAPI

Спасибо, Роман за статьи. Почитаю. По поводу того, что Деккер не корректен н x86. Есть какой-нибудь алгоритм аналогичный Деккеру, который можно достаточно легко реализовать и который будет корректен на x86?

В принципе, можно использовать и критические секции. Но решат ли они проблему со списком. Вообще у меня проблема не во взаимоисключении. И алгоритм Деккера в моем случае нормально работает, ошибок там я не замечал.