Предположим, 2 потока параллельно обращаются к массиву из int. А в одном int хранится не одно значение, а 32 значения длиной в 1 бит. Поток обратившись, меняет там только 1 бит (обычный or или and), поэтому результат его действия (измененный int) зависит от того, какой был прочитанный. Синхронизация потоков нужна, т.к. если на этапе изменения int (который в регистре процессора), произойдет прерывание, то обработчик прерывания отправит значение регистра с помощью push в стек. Потом если произойдет переключение потоков, а 2-й поток перезапишет этот же int, и отправит в ОП, 1-й поток этого знать не будет (для него этот int находится в регистре, т.к. на момент прерывания он был там). Он будет восстановлен из стека и 1-й поток затрет изменения 2-го потока (пропадет перезаписанный 2-м потоком один бит).

Для изменения всего лишь одного бита вводить ВСЕГДА критические секции совсем неэффективно. Ведь реально — РЕДКИЙ СЛУЧАЙ, когда оба потока будут ломиться именно к одному значению int в массиве. Поэтому, зачем лишние блокировки? Я решил синхронизировать потоки так — сначала поток записывает в специальную переменную тот номер int из массива который он намерен "захватить", и только потом его меняет. 2-й поток будет приостановлен только в РЕДКИХ случаях когда оба потока одновременно захотят изменить это значение. Т.е. 2-й поток увидев что значение захвачено и используется, сбросит свою метку,(он же тоже уже пометил, что хочет захватывать это значение), и заснет на какое-то время. Потом снова пометит, что он хочет менять, снова проверит, не захвачено ли значение другим потоком и т.д. С таким подходом взаимной блокировки потоков быть не может, правда, теоретически возможно, что заснут оба потока со сброшенными метками, но здесь проблем нет — один из них проснется через константное время и продолжит работу. Я протестировал такой подход — ошибок пока не возникло ни одной, да и производительность возросла в 2 раза по сравнению с критическими секциями для всех обращений. И именно в этом месте крайне важна для меня производительность программы иначе бы я так не парился. Будет ли программа всегда работать правильно, и при всех изменениях архитектуры будущих компьютеров не будет ли сбоев?

Я не могу быть уверенным стопроцентно, т.к. не знаю толком, как работает аппаратура, память-проц-кэш-стек, как маппится в кэше процессора общая в ОП область памяти для разных потоков и т.д. Не запишет ли обработчик прерываний в стек чего лишнего, которое может быть потом затерто другим потоком? И могу ли я быть уверен, что после выполнения ВСЕГО "дизассемблерного" кода который я могу видеть, соответствующего моему common_value_for_thread1 = N; при любых состояниях системы и прерываниях, 2-й поток обратившись к common_value_for_thread1 действительно увидит там знчение N.

Не проще ли использовать функции InterlockedAnd,InterlockedOr?

Здравствуйте, axxie, Вы писали:

A>Не проще ли использовать функции InterlockedAnd,InterlockedOr?


И как система с ними будет работать?

<skipped>

Мой совет — поиск в групп-гугле (а можно и по rsdn) по ключевым словам lock-free. То, что описали вы, не может работать без атомарных операций сравнения\записи А если их ввести — получится банальный спинлок, который (сюрприз) уже есть в критической секции — InitializeCriticalSectionAndSpinCount. Ну и стОит подумать, возможно, в данном случае самый правильный способ — использовать уже существующие lock-free контейнеры.

Здравствуйте, Skipper_N, Вы писали:

A>>Не проще ли использовать функции InterlockedAnd,InterlockedOr?
S_N>И как система с ними будет работать?

Тупо. Выполнять неделимую атомарную операцию над целым. Точнее, над LONG. Поддерживаю и рекомендую!

Здравствуйте, Skipper_N, Вы писали:

S_N>И как система с ними будет работать?

На однопроцессорных системах заблокирует переключение потока на время изменения переменной, на многопроцессорных дополнительно выставит на шине блокировку доступа к конкретному адресу в памяти, что заставит другие процессоры ожидать, если им вдруг понадобится таже переменная.
Если кратко, то ось гарантирует, что никто не помешает изменить переменную. Таких функций достаточно много. Начинаются они с InterlockedXXXXX. InterlockedIncrement, InterlockedDecrement, InterlockedExchage, InterlockedAdd и т.д. Смотрите в гугле или мсдн, ищущий да обрящет
Что касается CRITICAL_SECTION, то хоть они и содержат теже атомарные операции, они содержат еще много чего. Таже секция debug и прочее. Так городить огород ради 1-го бита явно не разумно. Присоеденяюсь к axxie, имхо InterlockedOr и InterlockedAdd лучшее решение.

S_N>Для изменения всего лишь одного бита вводить ВСЕГДА критические секции совсем неэффективно. Ведь реально — РЕДКИЙ СЛУЧАЙ, когда оба потока будут ломиться именно к одному значению int в массиве. Поэтому, зачем лишние блокировки? Я решил синхронизировать потоки так — сначала поток записывает в специальную переменную тот номер int из массива который он намерен "захватить", и только потом его меняет. 2-й поток будет приостановлен только в РЕДКИХ случаях когда оба потока одновременно захотят изменить это значение. Т.е. 2-й поток увидев что значение захвачено и используется, сбросит свою метку,(он же тоже уже пометил, что хочет захватывать это значение), и заснет на какое-то время. Потом снова пометит, что он хочет менять, снова проверит, не захвачено ли значение другим потоком и т.д

Т.е. спинлок, хранящий в себе указатель на данные. Что ж... первый шаг к lock-free data structures выглядит именно так, только писать надо очень аккуратно и вдумчиво.

Здравствуйте, Maxim S. Shatskih, Вы писали:

S_N>>Для изменения всего лишь одного бита вводить ВСЕГДА критические секции совсем неэффективно. Ведь реально — РЕДКИЙ СЛУЧАЙ, когда оба потока будут ломиться именно к одному значению int в массиве. Поэтому, зачем лишние блокировки? Я решил синхронизировать потоки так — сначала поток записывает в специальную переменную тот номер int из массива который он намерен "захватить", и только потом его меняет. 2-й поток будет приостановлен только в РЕДКИХ случаях когда оба потока одновременно захотят изменить это значение. Т.е. 2-й поток увидев что значение захвачено и используется, сбросит свою метку,(он же тоже уже пометил, что хочет захватывать это значение), и заснет на какое-то время. Потом снова пометит, что он хочет менять, снова проверит, не захвачено ли значение другим потоком и т.д

MSS>Т.е. спинлок, хранящий в себе указатель на данные. Что ж... первый шаг к lock-free data structures выглядит именно так, только писать надо очень аккуратно и вдумчиво.


Я вот тщательно все обдумал и пришел к выводу, что мой подход, несмотря на то, что операции записи-чтения меток (которые показывают то, что именно потоки "захватывают") и атомарны, все равно может дать ошибку, но ТОЛЬКО на многопроцессорных машинах. Это теоретически может произойти если планировщик потоков назначит эти два потока на разные CPU. Тогда 1-й поток сделает пометку чтобы 2-й поток приостановился, если ему нужен определенный элемент... Но процессор сразу не отправит в ОП а запишет в кэш процессора. 2-й поток на другом процессоре, будет читать или из своего кэша или из ОП, и в обоих случаях он не увидит ЧТО МЕТКА ИЗМЕНИЛАСЬ, ХОТЯ 1-й ПОТОК ДЕЙСТВИТЕЛЬНО ЕЕ УЖЕ ИЗМЕНИЛ!

Как можно на C++ ЗАСТАВИТЬ процессор отправить переменную, которая только что изменилась, НЕМЕДЛЕННО (!) в оперативную память? Чтобы она не попадала предварительно в кэш. И второе — как заставить (для второго процессора) прочитав переменную, не хранить ее в кэше, т.е. при каждой попытке чтения — чтобы она читалась именно из оперативной памяти? На C# такое, я читал, можно сделать. А можно ли на C++ ?

И еще... По видимому, даже InterlockedAnd, InterlockedOr не спасут от такой проблемы. Ведь, InterlockedAnd гарантирует вроде, только, что операция "чтения + AND + присваивание" выполнятся без переключения потоков. Ну выполнились и что? Если значение в кэше процессора и второй поток выполняется на другом процессоре, то он не увидит изменений, и затрет изменения 1-го потока. Вообще непонятно, как синхронизировать потоки на многопроцессорных машинах, если не запрещать кэшировать в CPU общие для потоков участки памяти.

Здравствуйте, Skipper_N, Вы писали:

S_N>И еще... По видимому, даже InterlockedAnd, InterlockedOr не спасут от такой проблемы.
учите матчасть (в частности мануал от Интела), все Ваши измышления выдуманы и не имеют никого отношения к действительности.
InterlockedXXX операции атомарны поскольку выполняются с префиксом "lock", что блокирует доступ других процессоров к системной шине.

Здравствуйте, Mickey, Вы писали:

M>Здравствуйте, Skipper_N, Вы писали:

S_N>>И еще... По видимому, даже InterlockedAnd, InterlockedOr не спасут от такой проблемы.
M>учите матчасть (в частности мануал от Интела), все Ваши измышления выдуманы и не имеют никого отношения к действительности.
M>InterlockedXXX операции атомарны поскольку выполняются с префиксом "lock", что блокирует доступ других процессоров к системной шине.


После выполнения InterlockedXXX измененная переменная гарантированно оказывается в ОП а не в кэше процессора? Это точно так? Я порылся по докам но такого утверждения нигде не видел.

Здравствуйте, Skipper_N, Вы писали:

S_N>После выполнения InterlockedXXX измененная переменная гарантированно оказывается в ОП а не в кэше процессора? Это точно так? Я порылся по докам но такого утверждения нигде не видел.

Весь COM построен на операциях InterlockIncrement и InterlockDecrement (в AddRef и Release), найдите там ошибку и заработайте на этом кучу денег

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

Я не знаю как работает аппаратная часть... Это целая наука, архитектуры вычислительных систем. Мне нужно всего лишь правильно синхронизировать потоки, а так я низкоуровневым программированием почти не занимался...

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Skipper_N, Вы писали:

S_N>>После выполнения InterlockedXXX измененная переменная гарантированно оказывается в ОП а не в кэше процессора? Это точно так? Я порылся по докам но такого утверждения нигде не видел.

А>Весь COM построен на операциях InterlockIncrement и InterlockDecrement

Хорошо, предположим что после выполнения "атомарной" операции в ОП гарантированно хранится уже нужное нам значение. вся программа разделяется на атомарные операции. Чем тогда забивается кэш процессора? Какой смысл там что-то хранить, если ЭТО ЖЕ должно присутствовать в ОП после всех банальных операций, таких как присваивание...

S_N>Как можно на C++ ЗАСТАВИТЬ процессор отправить переменную, которая только что изменилась, НЕМЕДЛЕННО (!) в оперативную память? Чтобы она не попадала предварительно в кэш.

Кэш как раз не проблема, автоматически синхронизится.

Проблема а) реордеринг команд в рантайме железом процессора, от которого нужно делать т.н. memory barriers — на x86/x64 любая interlocked операция такова — и б) реордеринг команд компилятором при построении, от которого спасает volatile.

S_N>Я не знаю как работает аппаратная часть...

Надо забыть слово "кэш" в этом вопросе. Он тут прозрачен для софта.

Он непрозрачен только про обращении к адресам, под которым память _железки_ — вот там начинаются веселухи типа prefetchable и write combining.

При работе с обычной RAM кэш прозрачен.