Добрый вечер.

Пусть есть вот такой самописный мьютекс:

class TSpinlockMutex {
private:
   std::atomic_flag LockFlag{ATOMIC_FLAG_INIT};

public:
   void Lock() noexcept {
      while( LockFlag.test_and_set(std::memory_order_acquire) )
         ;
   }
   void Unlock() noexcept {
      LockFlag.clear(std::memory_order_release);
   }
};

Правильно ли я понимаю, что при такой реализации его одновременно могут захватить несколько потоков,
т.к. если один установил значение c memory_order_acquire, то не факт, что остальные потоки это увидят.


А если в test_and_set указать флаг memory_order_acq_rel, то всё будет работать правильно.

Я прав?

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


DTF>А если в test_and_set указать флаг memory_order_acq_rel, то всё будет работать правильно.
Если под правильностью понимать, что lock захватить может одновременно не более одного потока, то будет работать правильно при любых допустимых параметрах в test_and_set и clear.

DTF>Правильно ли я понимаю, что при такой реализации его одновременно могут захватить несколько потоков,
Нет, не могут.

DTF>т.к. если один установил значение c memory_order_acquire, то не факт, что остальные потоки это увидят.
Увидят — это факт.
memory_order на это не влияет. Он нужен вообще не для самой установки atomic_flag, а чтобы показать как с этой установкой должны взаимодействовать другие операции чтения и записи в память. В твоём коде таких операций вообще нет — тут просто нечему ломаться.

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

W>Увидят — это факт.

Т.е. изменение (атомарной) переменной все потоки видят одновременно независимо от memory_order?
А почему тогда происходит так, что разные потоки могут видеть изменение значений переменных в разном порядке?

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

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

W>>Увидят — это факт.

DTF>Т.е. изменение (атомарной) переменной все потоки видят одновременно независимо от memory_order?
Не обязательно одновременно. Просто видят. Когда-нибудь.
Главное что операции с атомарной переменной происходят всегда атомарно.

DTF>А почему тогда происходит так, что разные потоки могут видеть изменение значений переменных в разном порядке?
Потому что процессор так может работать. Либо быстро, но с меньшими гарантиями, либо медленнее, но с большим соблюдением порядка.
Задание memory order как раз и позволяет программисту выбрать требуемый уровень ограничений на порядок видимости.

Например, если ты отпустил lock с memory_order_relaxed, то не факт, что изменения сделанные под lock'ом доедут до других потоков к моменту как они его захватят.
Если же отпускать lock с memory_order_release, то гарантируется, что сначала будут зафиксированы все изменения и лишь затем lock будет освобождён.

DTF>>Т.е. изменение (атомарной) переменной все потоки видят одновременно независимо от memory_order?
W>Не обязательно одновременно. Просто видят. Когда-нибудь.

Так почему не может быть ситуации, когда один поток сделал test_and_set(std::memory_order_acquire), а второй этого еще не увидел и тоже сделал test_and_set(std::memory_order_acquire)?
Т.е. для второго потока это "когда-нибудь" еще не наступило, а он уже решил захватить блокировку.

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

DTF>>>Т.е. изменение (атомарной) переменной все потоки видят одновременно независимо от memory_order?
W>>Не обязательно одновременно. Просто видят. Когда-нибудь.

DTF>Так почему не может быть ситуации, когда один поток сделал test_and_set(std::memory_order_acquire), а второй этого еще не увидел и тоже сделал test_and_set(std::memory_order_acquire)?
DTF>Т.е. для второго потока это "когда-нибудь" еще не наступило, а он уже решил захватить блокировку.

если по простому, то все эти, поначалу мутные, memory orderingи относятся к тому, когда нужно зафорсить камень/ядро, чтобы он выполнил насильную синхронизацию памяти со своими кешами: а именно, грубо говоря, "до" или/и "после" необходимого действия...

т.е. одно дело это атомарные операции, которые читают и меняют что-то в памяти не давая никому "встрять" в середине этого процесса. Но CPU меняет сначала свой кеш, при том не один... и только "когда-нибудь" это значение дойдет до реальной памяти, откуда его смогут прочитать и\или обновить свои кеши другие камни/ядра. в тоже самое время, как ты справедливо заметил, в других потоках могут происходить аналогичные попытки... и вот тут то и нужны эти самые "насильственные" действия! т.е. чтобы такой mutex работал, не нужно ни чего делать на unlock -- пусть это новое значение "когда-нибудь" само пролезет из кеша CPU, который выполнял этот CAS, в реальную память... но если в других потоках делается lock, то "когда-нибудь" нас не устраивает (ибо может случиться описанная тобой неприятность) -- вот за то, чтобы сделать насильственную синхронизацию "до" того как текущий камень будет делать CAS над atomic flagом, как раз и отвечает memory_order_acquire. таким образом описанной тобой ситуации не возникает, ибо к этому моменту гарантируется, что если кто-то пытался чего-то писать в этот флаг (как и все другие места с relaxed или release memory orderingом), то в памяти и кэшах "заинтересованных" в этих данных камнях, все обновилось...

западло в том, что такой вот enforce довольно дорогая операция, поэтому без надобности ее вызывать не прикольно... собственно ради этой "экономии" (потому что enforcится синхронизация всех кэшей всех камней/ядер) нужны, эти memory ordering, чтобы ты мог явно управлять, когда тебе нужен этот enforce, а когда можно и подождать...

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

DTF>Так почему не может быть ситуации, когда один поток сделал test_and_set(std::memory_order_acquire), а второй этого еще не увидел и тоже сделал test_and_set(std::memory_order_acquire)?
У тебя вопрос про что? Про memory_order_acquire или про работу с атомарными переменными? Просто это немного разные вещи и непонятно что тебе именно непонятно.

В описанной ситуации, когда много потоков делают test_and_set(...) над одним и тем же атомарным флагом, будет всегда один итог: флаг будет установлен, ровно один вызов вернёт 0 (в том потоке, которому повезёт захватить блокировку), остальные вернут 1. И это не зависит от того, какой аргумент стоит внутри скобок на месте ...

Почему? Потому что флаг не простой, а атомарный. И действия с ним будут именно что атомарные — именно это является самым важным. И С++ это гарантирует. А как эти гарантии будет реализовывать компилятор, или как там процессор будет кеши синхронизировать, — это уже несколько другие вопросы.

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

Попробую спросить по-другому.

Вот есть страница про memory_ordering: http://en.cppreference.com/w/cpp/atomic/memory_order
(стандарт я пока что не переварил )

Про memory_order_acquire там написано буквально следующее:

A load operation with this memory order performs the acquire operation on the affected memory location: no reads or writes in the current thread can be reordered before this load. All writes in other threads that release the same atomic variable are visible in the current thread

Т.е., грубо говоря, если поток A пишет атомарную переменную с memory_order_release, то поток В, который прочитает эту же переменную с memory_order_acquire, увидит всё, что A записал в память до операции memory_order_release включительно.

Т.е., еще более грубо, если один поток вышел из критической секции, то следующий поток в этой секции увидит изменения первого потока.


Но я спрашиваю немного про другой случай.
А именно, два потока ОДНОВРЕМЕННО пытаются войти в секцию (получить блокировку с memory_order_acquire). Пока что ни одной операции с memory_order_release еще нет.
Какой конкретно пункт в стандарте запрещает потоку A получить блокировку, но никому об этом не сказать?
Соответственно, поток B читает переменную, но видит там предыдущее состояние и тоже получает блокировку.

Почему такого никогда не будет? Или таки будет?

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

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

DTF>>Так почему не может быть ситуации, когда один поток сделал test_and_set(std::memory_order_acquire), а второй этого еще не увидел и тоже сделал test_and_set(std::memory_order_acquire)?
W>У тебя вопрос про что? Про memory_order_acquire или про работу с атомарными переменными? Просто это немного разные вещи и непонятно что тебе именно непонятно.

W>В описанной ситуации, когда много потоков делают test_and_set(...) над одним и тем же атомарным флагом, будет всегда один итог: флаг будет установлен, ровно один вызов вернёт 0 (в том потоке, которому повезёт захватить блокировку), остальные вернут 1. И это не зависит от того, какой аргумент стоит внутри скобок на месте ...

W>Почему? Потому что флаг не простой, а атомарный. И действия с ним будут именно что атомарные — именно это является самым важным. И С++ это гарантирует. А как эти гарантии будет реализовывать компилятор, или как там процессор будет кеши синхронизировать, — это уже несколько другие вопросы.

Я отписался в соседней ветке. Этого сообщения тогда еще не увидел.
ТО, что флаг атомарный (в том смысле, что у него нет промежуточных состояний), это ясно.

Неясно, кто гарантирует, что если один поток что-то в эту переменную написал, то другие это что-то видят.
Т.е. почему не будет сиуации, когда один поток записал значение, а другой видит состояние переменной, которое было ДО записи.

Еще раз, не во время записи (т.к. запись атомарна, то у нее нет состояния "во время"), а именно ДО.

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

DTF>Я понимаю, что вся эта движуха нужна для устранения лишней синхронизации кешей.

Скорее как раз для создания этой "лишней" (на самом деле нужной) синхронизации.

DTF>Но я спрашиваю немного про другой случай.
DTF>А именно, два потока ОДНОВРЕМЕННО пытаются войти в секцию (получить блокировку с memory_order_acquire). Пока что ни одной операции с memory_order_release еще нет.
DTF>Какой конкретно пункт в стандарте запрещает потоку A получить блокировку, но никому об этом не сказать?

Тебе watchmaker уже ответил — собственно захват лока не имеет отношения к memory order, это сама по себе (без ансамбля в лице синхронизации с остальными операциями) атомарная операция.

В зависимости от архитектуры этот test_and_set реализован по-разному, но, например, как он может быть сделан на x86 (пока что acquire не учитываем, указатель на переменную лока в ebx):

1:  mov eax, 1
    xchg [ebx]. eax
    test eax, eax
    jnz 1b

xchg на x86 атомарен (без префикса lock). Мы всегда пытаемся туда записать 1, но если там уже была 1, то действие фактически превращается в nop (заменили 1 на него же), обнаруживаем это и идём на следующий заход. Но если было 0, а мы обменяли его с 1, то после xchg будет в eax ноль и мы будем знать, что лок таки захватили.

(Реально так грубо делали разве что до Pentium 1. Сейчас и кэш щадят, и процессору снижают нагрузку через mwait, но для иллюстрации схемы это годится.)

DTF>Соответственно, поток B читает переменную, но видит там предыдущее состояние и тоже получает блокировку.
DTF>Почему такого никогда не будет? Или таки будет?

Не будет в силу построения самой операции атомарного чтения-записи.
В x86, Sparc, многих других это шинный цикл compare-and-swap (если без кэша) или операция над строкой кэша после договора об её монопольном захвате.
В большинстве RISC это LL/SC пара операций, тогда процессор (ядро, тред, харт...) следит за тем, чтобы никто не успел вмешаться, а во многих реализациях также забирает строку кэша в монопольное владение и после этого несколько тактов запрещает забирать её другим.
В любом из этих вариантов эти меры приводят к тому, что атомарность комбинации чтения и записи или гарантирована, или надёжно проверяется.

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

DTF>Но я спрашиваю немного про другой случай.
DTF>А именно, два потока ОДНОВРЕМЕННО пытаются войти в секцию (получить блокировку с memory_order_acquire). Пока что ни одной операции с memory_order_release еще нет.

Тут небольшая путаница. memory_order ты задаешь синхронизацию до/после атомарной операции, а не самой операции.

DTF>Какой конкретно пункт в стандарте запрещает потоку A получить блокировку, но никому об этом не сказать?
DTF>Соответственно, поток B читает переменную, но видит там предыдущее состояние и тоже получает блокировку.

DTF>Почему такого никогда не будет? Или таки будет?

Потому что тогда переменная не будет атомарной, в ней будет смысла не больше, чем в volatile bool.

Попробуем так.
Операция над атомарной переменной всегда видна всем процессорам сразу. В этом ее смысл. Достигается это с помощью lock xaddl (или чем другим для флагов) или ll/sc для всяких риск-архитектур.

В memory_order ты указываешь как будут синхронизироваться все изменения до/после атомарной операции.
Т.е. в своем коде ты можешь поставить relaxed модель и код будет работать в том смысле, что никто никакие два потока не захватят твой спинлок одновременно. Однако, все, что будет поменяно между lock() и unlock() в одном потоке не обязательно будет видно между lock() и unlock() в другом.
Для этого в твоем коде и стоит модель acquire/release.
Грубо говоря, acquire означает "давай сейчас загрузим все, что там другой поток наменял", а release означает "давай сейчас отдадим все, что мы наменяли другому потоку".
Если в терминах процессора, то acquire — это объявить все поменяные другим потоком строки кэша недействительными (invalidate), что приведет к их загрузки из памяти при следующем обращении, а release — это сбросить все поменяные строки из кэша в память. На многоядерных архитектурах с общим кэшем, очевидно, release/acquire ничего не делает. С разными кэшами будут дикие пляски.

Здравствуйте, netch80, Вы писали:
N>В любом из этих вариантов эти меры приводят к тому, что атомарность комбинации чтения и записи или гарантирована, или надёжно проверяется.

То, что архитектура гарантирует, это хорошо, но хотелось бы узнать в формальных терминах модели памяти.

N>Не будет в силу построения самой операции атомарного чтения-записи.
Но ведь есть же классический пример (взят с http://en.cppreference.com/w/cpp/atomic/memory_order#Release-Acquire_ordering):

#include <thread>
#include <atomic>
#include <cassert>
 
std::atomic<bool> x = {false};
std::atomic<bool> y = {false};
std::atomic<int> z = {0};
 
void write_x()
{
    x.store(true, std::memory_order_seq_cst);
}
 
void write_y()
{
    y.store(true, std::memory_order_seq_cst);
}
 
void read_x_then_y()
{
    while (!x.load(std::memory_order_seq_cst))
        ;
    if (y.load(std::memory_order_seq_cst)) {
        ++z;
    }
}
 
void read_y_then_x()
{
    while (!y.load(std::memory_order_seq_cst))
        ;
    if (x.load(std::memory_order_seq_cst)) {
        ++z;
    }
}
 
int main()
{
    std::thread a(write_x);
    std::thread b(write_y);
    std::thread c(read_x_then_y);
    std::thread d(read_y_then_x);
    a.join(); b.join(); c.join(); d.join();
    assert(z.load() != 0);  // will never happen
}

В данном случае все операции упорядочены как memory_order_seq_cst, поэтому ассерт не сработает.
Но если бы было, например, упорядочивание memory_order_acquire/memory_order_release, то могла бы произойти следующая ситуация:

Потоки a и b записали true в x и y соответственно (атомарно записали!)
После этого:
Поток c увидел true в x, а в y увидел предыдущее значение (false), и, соответственно, z не увеличил
Поток d увидел true в y, а в x увидел предыдущее значение (false), и, соответственно, z не увеличил

Т.е. z никто не увеличил и сработал assert.
В этом примере тоже работают с атомарными переменными, но все-таки возможна ситуация, когда поток не видит нового значения в переменной.
Почему тогда в моем примере это невозможно? В чем разница?

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

DTF>Т.е. z никто не увеличил и сработал assert.
DTF>В этом примере тоже работают с атомарными переменными, но все-таки возможна ситуация, когда поток не видит нового значения в переменной.
DTF>Почему тогда в моем примере это невозможно? В чем разница?

Потому что при relaxed модели порядок увиденного не определен. Отсутствуе "барьерность" этой операции. Хоть сами переменные атомарны и видны сразу после изменения, операции над ними могут быть переупорядочены.

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

DTF>Здравствуйте, netch80, Вы писали:
N>>В любом из этих вариантов эти меры приводят к тому, что атомарность комбинации чтения и записи или гарантирована, или надёжно проверяется.

DTF>То, что архитектура гарантирует, это хорошо, но хотелось бы узнать в формальных терминах модели памяти.

Это разные понятия. Атомарность операции ортогональна связи этой операции с другими, предыдущими или последующими, операциями.

Возможно, тебя сбивает с толку то, что указание memory ordering приписано к самой операции. Но это скорее оптимизация, чем прямая необходимость. Вместо этого для захвата мьютекса можно было дописать ещё одно чтение уже захваченного мьютекса с acquire semantics, но это было бы лишнее чтение.

N>>Не будет в силу построения самой операции атомарного чтения-записи.
DTF>Но ведь есть же классический пример (взят с http://en.cppreference.com/w/cpp/atomic/memory_order#Release-Acquire_ordering):

Обрати внимание, что в этом примере все операции — просто load или store.

DTF>Почему тогда в моем примере это невозможно? В чем разница?

Это атомарная операция над одним и тем же адресом. Не над разными.

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

AD>Достигается это с помощью lock xaddl (или чем другим для флагов) или ll/sc для всяких риск-архитектур.
Давай обсуждать в терминах абстрактной машины, которую описывает стандарт? Я, к сожалению, не разбираюсь в архитектурах процессоров и компиляторов.


AD>Операция над атомарной переменной всегда видна всем процессорам сразу. В этом ее смысл.
А можно ссылку на стандарт? Потому что, кажется, это ключевой момент, который я понимаю неправильно.

Мне как раз казалось, что смысл атомарной переменной — обеспечить
1. Собственно неделимость операции (отсутствие промежуточных стадий, т.е. операция либо еще не начата, либо уже завершена)
2. Обеспечить, чтобы все операции для данной ячейки памяти были видны всем потокам в одном и том же порядке.

Однако, из этого совсем не следует, что все потоки видят последнее записанное в атомарную переменную значение.


Я в стандарте утонул и не нашел ни подтверждения, ни опровержения того, что все потоки видят последнее значение атомарной переменной.


Однако, в книжке "Параллельное программирование на С++ в действии" (которую я сейчас пытаюсь читать),
приводится метафора человека в боксе с телефоном (стр. 195, глава "Механизм ослабленного упорядочения").

Так вот, там прямым текстом говорится, что (в случае relaxed_ordering) разные потоки могут видеть разные значения одной и той же переменной в один и тот же момент реального времени.

Поэтому я и прошу ссылку на место в стандарте, где бы этот момент прояснялся.

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

AD>>Операция над атомарной переменной всегда видна всем процессорам сразу. В этом ее смысл.
DTF>А можно ссылку на стандарт? Потому что, кажется, это ключевой момент, который я понимаю неправильно.

Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.

DTF>Так вот, там прямым текстом говорится, что (в случае relaxed_ordering) разные потоки могут видеть разные значения одной и той же переменной в один и тот же момент реального времени.

Это если простые load и store. Для них определено вот так:

Implementations should make atomic stores visible to atomic loads within a reasonable amount of time.

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

DTF>>А можно ссылку на стандарт? Потому что, кажется, это ключевой момент, который я понимаю неправильно.

AD>

AD>Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.

DTF>>Так вот, там прямым текстом говорится, что (в случае relaxed_ordering) разные потоки могут видеть разные значения одной и той же переменной в один и тот же момент реального времени.

AD>Это если простые load и store. Для них определено вот так:
AD>

AD>Implementations should make atomic stores visible to atomic loads within a reasonable amount of time.

Спасибо. Теперь понятно.

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

DTF>Однако, из этого совсем не следует, что все потоки видят последнее записанное в атомарную переменную значение.

Видимость (visibility). Под видимостью понимается то, через какое время другие потоки увидят изменения, сделанные данным потоком, и увидят ли вообще. Многие почему-то считают это свойство очень важным, и порываются что-то предпринимать для его обеспечения. На практике, это — как раз самое неинтересное свойство для программиста и ничего предпринимать для его обеспечения не надо. Ну точнее так, ничего не надо предпринимать на кэш-когерентных архитектурах (коими являются все распространённые архитектуры: x86, Itanium, PPC, SPARC и т.д.). Когерентный кэш обеспечивает автоматическое и немедленное распространение всех изменений всем заинтересованным процессорам/ядрам. Т.е. можно считать, что любая запись в память становится немедленно видимой всем остальным потокам.

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

http://rsdn.org/forum/philosophy/3181311.1

Автор: remark
Дата: 20.11.08

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

DTF>Вот есть страница про memory_ordering: http://en.cppreference.com/w/cpp/atomic/memory_order
DTF>(стандарт я пока что не переварил )

DTF>Про memory_order_acquire там написано буквально следующее:
DTF>

DTF>A load operation with this memory order performs the acquire operation on the affected memory location: no reads or writes in the current thread can be reordered before this load. All writes in other threads that release the same atomic variable are visible in the current thread

вы читаете плохой источник. в нём совсем не в тему употребили слово "visible" и вас это сбивает с толку. рекомендую другие источники: Concurrency in action, C++ standard
memory_ordering про упорядочивание, а не про видимость

про видимость корректно написали здесь: http://rsdn.org/forum/cpp/6692169

Автор: andrey.desman
Дата: 09.02.17

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

U>вы читаете плохой источник. в нём совсем не в тему употребили слово "visible" и вас это сбивает с толку.
А что конкретно там неправильно?