Комментарии 60
pthread_join(t, NULL);
…
Внимательный читатель заметит, что данные передаются между потоками без единой блокировки
WAT? pthread_join перестал ожидать завершения треда?
поток 1При операции pthread_join поток 1 будет ждать завершения потока 2 (который в этот момент может выполнять, например, ввод-вывод). Чем это отличается от блокировки? Или в контексте этой статьи «неблокирующее программирование» следует понимать как «программирование без использования явных механизмов блокировки»?
pthread_join(t, NULL);
Вот схватили меня с aamonster (комментарий) за руку.
Меня тоже смущает, как я перевёл эту фразу, но у меня временно закончилась фантазия, так что бросил как есть.
Здесь и далее в серии «неблокирующий» = «lock-free», что несколько отличается от «wait-free», но «X без использования мьютексов и спин-локов» — это не так коротко, как «неблокирующий X», что является более-менее традиционным способом говорить lock-free по-русски.
Я ещё подумаю над вариантами, честное слово, и принимаю советы.
Это смотря, насколько глубоко закапываться. В самой строке pthread_join() — действительно no lock involved, но внутри pthread_join() — ещё как involved.
Я его читал на lwn'е, но я не могу уследить за его языком, очень, очень трудно. Однако, на seqlock я посмотрел с превеликим интересом.
В примере с pthread как уже говорили мы явно ждем завершения потока.
А что понимается под синхронизацией во втором примере? Мы просто используя барьеры гарантируем, что к моменту, когда произойдет
message = &a;
в a.x гарантированно будет 1, как-бы требуя и от компилятора и от проца, что-бы с учетом переупорядочивания это условие было соблюдено. И если каким-то чудом поток 2 в этот момент прочитает message (как сказано никакого ожидания в потоке 2 нет) и он будет не равен NULL, то гарантированно message->a будет равен 1.
Поправьте если не прав…
Мне кажется, или два примера (с pthread и с паттерном) несколько разные по сути?
Да, они разные. Но урок здесь больше в том, что в подходе с join не пришлось использовать мьютексы ради побочных эффектов синхронизации (вроде того, что вы увидите обновлённым не только непосредственно защищаемое мьютексом значение, но и всё, что через него видно). Если знать, какие гарантии предоставляются примитивами, то можно знать, когда дополнительные блокировки не нужны. Несмотря на то, что s вроде как общая для потоков и максима «все разделяемые данные должны быть обмазаны мьютексами» подсказывает, что мьютекс вроде как нужен.
А что понимается под синхронизацией во втором примере?
То же, что на самом деле подразумевается под «синхронизацией потоков» — «сделай что-нибудь, чтобы не было неопределённого поведения, а было определённое и предсказуемое». Здесь предсказуемым поведением будет то, что если поток 1 передаёт сообщение в виде указателя на данные, то в потоке 2 через этот указатель всегда считается то же, что и было видно в потоке 1. Вы всё правильно поняли: smp-операции здесь гарантируют только то, что если в message считается &a, то в message->x будет видно 1. Без smp, строго говоря, это не гарантируется: второй процессор может увидеть в message адрес &a, но в его кеше всё ещё лежит старое значение x. Или компилятор решит присваивание вставить попозже. О радостях data dependency будет в следующих частях.
Какой-то сумбур и каша :( Напоминает ситуацию когда студентов начинают учить языку С, не обучив основам программирования.
Так все же, что такое lock-free алгоритмы? В чем их особенность? Какие задачи решают эти алгоритмы? и зачем здесь барьеры? И насколько корректно переводить "lock-free" как неблокирующие? non-blocking и lock-free кажется несколько разные вещи, нет?
Статья — не учебник, но я отвечу как могу своим мнением.
Так все же, что такое lock-free алгоритмы? В чем их особенность?
Особенность неблокирующих алгортимов в их структуре, которая гарантирует отсутствие дедлоков (нет локов — не будет и дедлоков, *прикладывает палец к голове*). Это бывает полезным свойством в ядре ОС, где дедлоки негативно сказываются на всей машине сразу, а не являются проблемой отдельного процесса.
Какие задачи решают эти алгоритмы? и зачем здесь барьеры?
Синхронизация и координация работы в многопоточной среде. Барьеры — способ реализации этого.
И насколько корректно переводить "lock-free" как неблокирующие? non-blocking и lock-free кажется несколько разные вещи, нет?
Есть только один способ узнать, насколько это корректно: будут ли люди путаться или нет. Non-blocking, lock-free, wait-free, obstruction-free — это всё разные слова. Но есть также контекст, и из контекста может быть понятно, какой именно нюанс неблокируемости имеется в виду. Без превращения этого слова в целый оборот, или проталкивания неологизимов вроде безмьютексных или там прогрессивных алгоритмов. Боже, да в русском даже нет отдельного точного слова-аналога для lock. Только калька: «лок».
или проталкивания неологизимов вроде безмьютексных или там прогрессивных алгоритмов
Как будто что-то плохое? Слова «дедлок» в русском тоже не было.
Да нет, не плохое. Если бы был какой-то меткий вариант, который мне бы нравился, то я бы его и использовал. Потому что именно так новые слова и приживаются: некоторые носители языка начинают их последовательно использовать, потом все вокруг сначала кривят носом на эти ваши смешные новые слова, а потом начинают других гонять за «невыносимые англицизмы», ведь есть «исконное» же.
Но вот «неблокирующий» хотя бы перекликается с «блокирующей синхронизацией». Всё остальное как-то не перекликается ни с чем.
Да нет, не плохое. Если бы был какой-то меткий вариант, который мне бы нравился, то я бы его и использовал.
В литературе буквально до 2000-х использовалось слово "клинч" как перевод deadlock — это борцовский термин, когда двое захватят друг друга так, что не могут выпутаться без посторонней помощи. Сейчас я его очень редко встречаю.
wait-free — это lock-free алгоритмы + свободны от ожидания, так как они НЕ ЖДУТ результата от другого потока, и каждый шаг продвигаются к своему завершению.
Т.е. для wait-free алгоритма — можно всегда сказать — сколько шагов займёт ёго выполнение.
lock-free пример указан в комментарии
wait-free — обычный атомарный счётчик — если вам надо просто его увеличить
std::atomic<int> count = {0};
void add()
{
for (int n = 0; n < 1000; ++n) {
count.fetch_add(1, std::memory_order_relaxed);
}
}
int main()
{
std::vector<std::thread> v;
for (int n = 0; n < 10; ++n) {
v.emplace_back(add);
}
for (auto& t : v) {
t.join();
}
}
lock-free — алгоритмы — не используют примитивы синхронизации (типа mutex), которые сильно замедляют работу <...> lock-free пример указан в комментарии
Нет, это не так: lock-freedom вообще не про выбор используемых примитивов. Посмотрите определение на en.wikipedia.org/wiki/Non-blocking_algorithm#Lock-freedom — в вашем примере очевидно, что если засаспендить dataProducer, то встанет колом вся программа.
Без блокировок (англ. lock-free)
Для алгоритмов без блокировок гарантируется системный прогресс по крайней мере одного потока. Например, поток, выполняющий операцию «сравнение с обменом» в цикле, теоретически может выполняться бесконечно, но каждая его итерация означает, что какой-то другой поток совершил прогресс, то есть система в целом совершает прогресс.
Более того — эти примеры, приведены в книгах C++ Concurrency in Action и Concurrency with Modern C++ именно как вид lock_free алгоритмов.
Не вижу причин не доверять авторам этих книг, тем более один из них -член комитета по стандартизации С++ :)
Я их не вижу (примитивов) и в коде, который привёл в качестве примера
Их там нет, но lock-freedom не требует их отсутствия, и не обеспечивается их отсутствием — викистатья, на которую вы сослались, не утверждает ни того ни другого.
если dataConsumer простаивает в цикле, значит происходит прогресс dataProducer
Это не так: dataConsumer будет простаивать в цикле и если dataProducer засаспенжен.
Вот здесь хорошо написано: http://www.1024cores.net/home/in-russian/lock--wait--obstruction--atomic-free-algorithms
smp_wmb();
WRITE_ONCE(message, &a); datum = READ_ONCE(message);
smp_rmb();Интересно как эти операции (WRITE_ONCE/READ_ONCE) или же (smp_wmb()/smp_rmb()), реализованы — ведь если нет цикла — которой синхронизирует release/acquire — не может получиться так, что поток2 прочитает значение раньше, чем оно будет записано потоком1? Либо в этом примере это не важно, а просто главное чтобы не было data race между потоками?
Или в ядре немного хитрее реализовано, чем в stdlibc++?
В прикладных задачах обычно делают так:
std::vector<int> mySharedWork;
std::atomic<bool> dataProduced(false);
void dataProducer(){
mySharedWork={1,0,3};
dataProduced.store(true, std::memory_order_release);
}
void dataConsumer(){
while( !dataProduced.load(std::memory_order_acquire) ); // <== без этого цикла синхронизации не будет, т.к. второй поток, может выполниться перед первым
mySharedWork[1]= 2;
}
int main(){
std::cout << std::endl;
std::thread t1(dataConsumer);
std::thread t2(dataProducer);
t1.join();
t2.join();
for (auto v: mySharedWork){
std::cout << v << " ";
}
std::cout << "\n\n";
}
не может получиться так, что поток2 прочитает значение раньше, чем оно будет записано потоком1?
Значение
message? Да, может.Либо в этом примере это не важно, а просто главное чтобы не было data race между потоками?
Цель в том, чтобы не было data race между обращениями одного потока к памяти.
Конкретно, в коде
datum = READ_ONCE(message);
smp_rmb();
if (datum != NULL)
printk("%x\n", datum->x);— без
smp_rmb() могло бы оказаться, что datum прочитан из общей памяти, а datum->x — из локального кэша, и в нём не отразилось значение, записанное первым потоком.В прикладных задачах обычно делают так:
Цикл в вашем коде — та самая блокировка, обойтись без которой является целью lock-free алгоритмов.
Цикл в вашем коде — та самая блокировка, обойтись без которой является целью lock-free алгоритмов.
Это неблокирующая синхронизация. Мне кажется вы путаете Lock-free и Wait-free.
Интересно как эти операции (WRITE_ONCE/READ_ONCE) или же (smp_wmb()/smp_rmb()), реализованы
Или в ядре немного хитрее реализовано, чем в stdlibc++?
Если переводить на C++:
- READ_ONCE(p) — это std::atomic_load_explicit(p, std::memory_order_relaxed)
- WRITE_ONCE(p, v) — это std::atomic_store_explicit(p, v, std::memory_order_relaxed)
- smp_rmb() и smp_wmb() — это std::atomic_thread_fence(std::memory_order_acq_rel)
Это примерные аналоги, так как у Linux модель памяти чуть отличается от той, что прописано в стандартах C и C++ (в более свободную сторону), и позволяет больше, чем гарантирует std::atomic. От “барьеров”, например, ожидается, что они распространяются только на чтение/запись, а у C++ есть только “fences”, которые сразу на всё.
ведь если нет цикла — которой синхронизирует release/acquire — не может получиться так, что поток2 прочитает значение раньше, чем оно будет записано потоком1? Либо в этом примере это не важно, а просто главное чтобы не было data race между потоками?
Да, может. Да, в этом узком кусочке кода не важно: сообщение в этот раз «не дошло» — дойдёт в следующий.
Это примерные аналоги, так как у Linux модель памяти чуть отличается от той, что прописано в стандартах C и C++ (в более свободную сторону), и позволяет больше, чем гарантирует std::atomic.
Про "в более свободную", насколько мне известно, неверно (или я не понял, что тут "свобода" значит). Например, код вида
x.store(1, std::memory_order_relaxed);
x.store(2, std::memory_order_relaxed);
без других действий между ними — может быть оптимизирован компилятором так, что будет только одна запись числа 2. Операции в таком виде — с relaxed — гарантируют только атомарность каждой операции, но не выставляют барьеры — так что это ничуть не отличается от того, как если бы было
x = 1;
x = 2;
Современные компиляторы, которые я вижу, не склеивают relaxed-операции такого рода — но они имеют право это делать (и когда-нибудь наверняка начнут делать).
Если это не так — прошу уточнить (но с подробным обоснованием).
А вот если у нас есть
WRITE_ONCE(x, 1);
WRITE_ONCE(x, 2);
то оптимизация подобного рода явно запрещена — между этими операциями всегда есть порядок выполнения согласно исходному коду (sequentially consistent), что реализуется через volatile-доступ.
Это примерные аналоги, так как у Linux модель памяти чуть отличается от той, что прописано в стандартах C и C++ (в более свободную сторону), и позволяет больше, чем гарантирует std::atomic.
Про «в более свободную», насколько мне известно, неверно (или я не понял, что тут «свобода» значит).
Более свободная для программиста, тем самым менее свободная для компилятора и процессора :)
Это видно в т.ч. по фразе «позволяет больше, чем гарантирует std::atomic» — бо́льшая свобода для компилятора и процессора описывалась бы как «позволяет больше, чем требует std::atomic»
Пришел почитать про неблокирующие алгоритмы, а увидел только бардак из linux-core-специфических примеров.
Терять суть я начал с вот этого момента:
Для этого существуют операции “store-release” и “load-acquire”, выполняемые парами. Store-release операция P помимо записи в память синхронизирована сload-acquireоперацией Q, если Q читает значение, записанное P. Корректный код используетsmp_store_release()иsmp_load_acquire():
поток 1 поток 2 -------------------------------- ------------------------ a.x = 1; smp_store_release(&message, &a); datum = smp_load_acquire(&message); if (datum != NULL) printk("%x\n", datum->x);
Теперь, если вdatumреально лежит&a, мы можем быть уверены, что записьa.x = 1произошла перед чтениемdatum->x.
Во-первых, мне кажется что вот здесь пропущен важный кусок:
Store-release операция P помимо записи в память синхронизирована с load-acquire операцией Q, если Q читает значение, записанное PИмелось ли в виду что-то вроде
запись вaсинхронизирована с вызовомsmp_store_release(&message, &a); в то же время вызовsmp_store_release(&message, &a)синхронизирован с вызовомsmp_load_acquire(&message).
т.е. в данном случаеa.x = 1естьP1, аsmp_store_release(&message, &a)естьQ1для операции записи в память, в то время какsmp_store_release(&message, &a)естьP2, аsmp_load_acquire(&message)естьQ2для операции чтения из памяти
?
Потому что мне кажется вполне реальным последовательность
a.x = 1; ---> datum = smp_load_acquire(&message);
|
|
smp_store_release(&message, &a); <-
|
|
-> if (datum != NULL)
printk("%x\n", datum->x);И это похоже на блокирующий алгоритм (т.к. smp_load_acquire() вроде как должен бы дождаться соответствующего smp_store_release()).
По-моему, "передача сообщений" в данном случае была бы правильнее ~реализована~ показана как передача ссылки на копию сообщения, а не как запись в глобальную переменную.
Что-то вроде
поток 1 поток 2
-------------------------------- ------------------------
datum_t b = datum_t(a);
b.x = 1;
smp_store_release(&message, &b); datum = smp_load_acquire(&message);
if (datum != NULL)
printk("%x\n", datum->x);И все равно меня не покидает ощущение, что message выступает в роли лока (поток 2 должен дождаться пока все записи в message закончатся), так что пример выше тоже скорее неправильный.
Ну или я вообще не понимаю специфики ядра линукса и просто был привлечен кликбейтовым заголовком.
С момента про smp_rmb() / smp_wmb() и WRITE_ONCE() / READ_ONCE() я полностью потерял всякое понимание о чем речь.
Потому что мне кажется вполне реальным последовательность
Да, вполне.
И это похоже на блокирующий алгоритм
Зависит от того, что наворочено вокруг операции чтения в потоке 2. Если в случае
datum == NULL поток не делает ничего и в цикле возвращается к чтению message, то блокирующий. Если находит себе какое-то полезное занятие, то неблокирующий.По-моему, «передача сообщений» в данном случае была бы правильнее ~реализована~ показана как передача ссылки на копию сообщения, а не как запись в глобальную переменную.
Не вижу никакой разницы — ссылка на копию ведь всё равно передаётся посредством записи в глобальную переменную?
И все равно меня не покидает ощущение, что message выступает в роли лока (поток 2 должен дождаться пока все записи в message закончатся), так что пример выше тоже скорее неправильный.
Не совсем: невозможна ситуация, когда
message заблокирована на неопределённый срок, т.е. smp_load_acquire гарантированно завершается с успехом за известное заранее время. При использовании локов таких гарантий нет.Не вижу никакой разницы — ссылка на копию ведь всё равно передаётся посредством записи в глобальную переменную?
Да, в моем примере нужно было как-нибудь подчеркнуть что message в каждом потоке — свой объект.
невозможна ситуация, когда message заблокирована на неопределённый срок, т.е. smp_load_acquire гарантированно завершается с успехом за известное заранее времяа вот здесь можно поподробнее? каким образом система знает сколько времени smp_load_acquire будет ожидать?
Да, в моем примере нужно было как-нибудь подчеркнуть что message в каждом потоке — свой объект.
Тогда какой магией значение, записанное первым потоком в свой
message, телепортируется в message второго потока?а вот здесь можно поподробнее? каким образом система знает сколько времени smp_load_acquire будет ожидать?
Во-первых, системе это не нужно знать, это нужно знать программисту :)
Во-вторых, у вас может быть представление, будто
smp_load_acquire дожидается записи в message другим потоком (это не так) или получает «гарантированно самое свежее» значение, записанное в message (это не так). load_acquire(x) может прочитать любое значение, записанное в x неким потоком T, вместе со всеми значениями, записанными T перед выполнением store_release(x). Записей потоком T, ещё не дошедших до общей памяти, может быть известное конечное количество, и каждая запись отразится в общей памяти за известное конечное время. Конкретные значения, конечно, в каждой системе свои.Тогда какой магией значение, записанное первым потоком в свойmessage, телепортируется вmessageвторого потока?
Другая ссылка, другой объект, очередь сообщений (inbox), модель акторов — как-то так.
Во-первых, системе это не нужно знать, это нужно знать программисту :)
А вот это и есть то что вы описали как
заблокирована на неопределённый срок
Thread 1:
---
scanf("%d", &x);
message.x = x;
store_release(message);
Thread 2:
---
load_acquire(message);сколько, по-вашему, времени будет ждать load_acquire?
Во-вторых, у вас может быть представление, будто smp_load_acquire дожидается записи в message другим потоком (это не так) или получает «гарантированно самое свежее» значение, записанное в message (это не так).
нет, у меня представление, что load_acquire дожидается соответствующего store_release (с таким же первым аргументом, я полагаю). что в моем понимании — абсолютно то же самое, что и среднестатистический lock.lock() и lock.unlock()
было, промелькнула мысль, мол это все похоже на incrementAndGet vs getAndIncrement — поток либо сперва читает значение, а потом изменяет, либо сначала изменяет а потом читает результат. но тогда все равно не хватает контекста в коде:
┌───────────────┐
│ message.x = 0 │
└───────┬───────┘
│
┌────────────┴───────────┐
│ │
┌───────┴───────┐ ┌───────┴───────┐
│ join() │ │ join() │
└───────┬───────┘ └───────┬───────┘
│ │
│ ┌───────┴───────┐ ┌───────────────┐
│ │ load_acquire()◄──────────┤ message.x==0 │
│ └───────────────┘ └───────────────┘
│
┌───────┴───────┐
│ message.x = 1 │
└───────┬───────┘
│
┌───────┴───────┐
│store_release()│◄─────────┐
└───────────────┘ │
┌───────┴───────┐
│ message.x==1 │
└───────────────┘но тогда вообще не понятно, зачем store_release и load_acquire — банальное чтение и запись в память дадут тот же эффект.
ну или должно быть что-то вроде
Global scope:
---
init_message(&message); // writes(&message) = 0, reads(&message) = 0
Thread 1:
---
message.x = 1;
store_release(&message); // writes(&message)++
Thread 2:
---
load_acquire(&message); // ждет пока reads(&message) == writes(&message)т.е. message работает как fence из directx или vulkan
у меня представление, что load_acquire дожидается соответствующего store_release (с таким же первым аргументом, я полагаю).
Это не так. Выше я объяснил, как на самом деле.
Если вы про
load_acquire(x)может прочитать любое значение, записанное вxнеким потокомT, вместе со всеми значениями, записаннымиTперед выполнениемstore_release(x). Записей потокомT, ещё не дошедших до общей памяти, может быть известное конечное количество, и каждая запись отразится в общей памяти за известное конечное время.
то я совсем ничего не понял.
конкретно:
load_acquire(x)может прочитать любое значение, записанное вxнеким потокомT
так а где тогда синхронизация? чем это отличается от банального чтения из памяти без load_acquire и store_release?
вместе со всеми значениями, записаннымиTперед выполнениемstore_release(x)
какими "всеми" значениями? если load_acquire не дожидается соответствующего вызова store_release, как он прочитает "все" что записалось в память до него?
Записей потоком T, ещё не дошедших до общей памяти, может быть известное конечное количество, и каждая запись отразится в общей памяти за известное конечное время.но в таком случае, load_acquire должен ждать конечное время, правильно? что делает его очень даже блокирующим вызовом, насколько я понимаю. и с другой стороны, чтобы знать сколько ждать, где-то должен храниться счетчик количества записей (даже два — "дошедших" и "не дошедших"), я полагаю?
так а где тогда синхронизация?
Без
load_acquire могло бы прочитаться новое значение datum (из общей памяти) и при этом старое значение datum->x (из локального кэша).если load_acquire не дожидается соответствующего вызова store_release, как он прочитает «все» что записалось в память до него?
Прочитанное им значение кем-то когда-то было записано, верно? Даже если неделю назад. Вот команда, его записавшая, и окажется «соответствующим вызовом store_release».
но в таком случае, load_acquire должен ждать конечное время, правильно? что делает его очень даже блокирующим вызовом, насколько я понимаю
И вот здесь проявляется терминологическая засада :) он ждёт конечное время, и поэтому его нельзя назвать non-blocking, но при этом он lock-free в том смысле, что всегда достигает успеха за ограниченное время.
и с другой стороны, чтобы знать сколько ждать, где-то должен храниться счетчик количества записей (даже два — «дошедших» и «не дошедших»), я полагаю?
Внутри процессора(ов): memory coherence protocol реализован аппаратно, а
load_acquire — это просто команда LDAR в современных процессорах. В более старых — это пара из fence на всю память, и обычного load.И вот здесь проявляется терминологическая засада :) он ждёт конечное время, и поэтому его нельзя назвать non-blocking, но при этом он lock-free в том смысле, что всегда достигает успеха за ограниченное время.
Ну, насколько я понимаю, не совсем ограниченное время — вполне возможно, что пока этот тред думал о чём-то, другой выдернул поступившие данные, и первому надо снова ждать, а потом есть какая-то вероятность, что снова кто-то успеет раньше, и в общем случае вероятность вечного ожидания хоть и асимптотически стремится к нулю, но не равна нулю… В подобных multi-consumer дизайнах это неизбежно, если не формировать явную очередь потребителей.
load_acquire прочтут разные данные.Гарантии и не требуется, зато есть возможность, которую надо учитывать.
(Возможно, вы имеете в виду
load_acquire не самого по себе, а обёрнутого в цикл, лишающий его lock-freedom?)(Возможно, вы имеете в виду load_acquire не самого по себе, а обёрнутого в цикл, лишающий его lock-freedom?)
В цикл — да. А иначе я и не вижу смысла рассматривать.
lock-freedom тут никак не исчезает от оборачивания в цикл — как раз множество (если не все) lock-free алгоритмов содержат цикл "не шмогла — идём на следующую попытку". Вы, вероятно, путаете с wait-free (или используете старые смыслы терминов?)
A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress.
An algorithm is lock-free if infinitely often operation by some processors will succeed in a finite number of steps. For instance, if N processors are trying to execute an operation, some of the N processes will succeed in finishing the operation in a finite number of steps and others might fail and retry on failure. The difference between wait-free and lock-free is that wait-free operation by each process is guaranteed to succeed in a finite number of steps, regardless of the other processors.
Ну и так далее.
так а где тогда синхронизация? чем это отличается от банального чтения из памяти без load_acquire и store_release?
Ничем не отличается — они и есть работа с памятью, но чуть-чуть особенная.
Если бы в процессорах не было никаких кешей, а память была бы атомарной, то и не было бы и никаких «проблем» с нелинейностью работы с памятью — память-то у вас одна и атомарная. Но сделать всю память атомарной очень дорого: либо пропускать только один процессор в один момент времени во всю память и блокировать остальные (прощай масштабируемость), либо делать то же самое для каждого байта (прощай эффективность).
Acquire и release позволяют координировать обновление памяти и кешей между процессорами только там, где это необходимо, а не для каждой записи и чтения из памяти безусловно, что очень дорого обходится.
но в таком случае, load_acquire должен ждать конечное время, правильно? что делает его очень даже блокирующим вызовом, насколько я понимаю.
Смотря насколько глубоко вы закапываетесь. Любая процессорная инструкция в некотором смысле блокирующая: пока процессор занят LOAD, вы данных из памяти не получите, это занимает какое-то время и блокирует исполнение инструкций, которые зависят от этих данных. На уровне отдельных инструкций эта операция выполняется за конечное, ограниченное сверху время.
Смотря насколько глубоко вы закапываетесь. Любая процессорная инструкция в некотором смысле блокирующая
Да, но разные инструкции в разной мере: время выполнения
ADD зависит только от происходящего внутри процессора; LDR — ещё и от внешних факторов; WFI — только от внешних факторов. На мой взгляд, WFI более уместно называть блокирующей, чем ADD.нет, у меня представление, что load_acquire дожидается соответствующего store_release (с таким же первым аргументом, я полагаю). что в моем понимании — абсолютно то же самое, что и среднестатистический lock.lock() и lock.unlock()
Дожидаться оно не может, если вокруг него не построить цикл.
Само понятие synchronized-with описывает, по сути, то, что если так сложились звёзды, что store-release в треде 1 случился раньше load-acquire в треде 2, то все данные, записанные до этого store-release, опубликованы для всех так, что операции в треде 2 после этого load-acquire будут читать уже эти обновлённые данные; и если load-acquire показал, что есть что читать, то данные будут полезными. Чуть неформально, но таки это то, ради чего строится синхронизация. А уже дело процессоров сделать так, что, чтобы это работало, все чтения-записи треда 1 до store-release публикуются остальным участникам до её (store-release) завершения, и все чтения треда 2 после load-acquire делаются после выполнения этого load-acquire.
А по результату load-acquire, повторюсь, определяется, есть ли там что-то полезное (например, если мы сумели поменять 0 на 1 в ячейке спинлока, мы захватили его и можем теперь работать с данными). Если же нет — мы просто не лезем к защищаемым данным (ну, можно прочитать для отладки;)), а дальше — можем подождать, пока нам дадут правильные данные, или перейти к другому действию.
было, промелькнула мысль, мол это все похоже на incrementAndGet vs getAndIncrement — поток либо сперва читает значение, а потом изменяет, либо сначала изменяет а потом читает результат. но тогда все равно не хватает контекста в коде:
Там другое. Например, x86 инструкция xadd возвращает старое значение, и если getAndIncrement транслируется напрямую в xadd, то incrementAndGet само корректирует результат, типа:
int tmp = xadd(addr, incr);
return tmp + incr;
но к данным методам синхронизации это не относится.
но тогда вообще не понятно, зачем store_release и load_acquire — банальное чтение и запись в память дадут тот же эффект.
Именно чтобы процессор (ядро, харт...) опубликовал другим участникам результаты предыдущих операций до собственно записи по store_release. Ну и симметрично для load_acquire.
Тут однако есть хитрый момент — если операция представляет собой compare-and-swap для захвата права доступа, то запись по адресу приобретает acquire-признак (барьер между ней и последующими чтениями-записями) даже несмотря на то, что это запись, а не чтение. Как это сделано в процессорах — зависит от архитектуры.
Поехали дальше. Вторая часть: атомарные операции и частичные барьеры памяти. Что такое гонки данных, зачем нужны атомарные операции, как барьеры могут помочь с синхронизацией на примере seqlocks.
Следующая часть про compare-and-swap и неблокирующие списки.
В общем, как "введение", статья — полный провал (по крайней мере, для человека далекого от ядра Linux). Пришлось пересмотреть кучу материалов, пока суть начала слабо доходить.
Дисклеймер: все написанное ниже — исключительно мое понимание материалов, поэтому если я не прав в каком-либо из пунктов — прошу исправить меня.
Сперва стоит отметить часть, которая абсолютно от меня ускользала при прочтении статьи — алгоритмы затронутые в статье подразумевают общую память, используемую несколькими потоками. К примеру — различные конкуррентные (от англ. concurrency) структуры данных — очереди, стеки и т.п., используемые в бóльших системах — к примеру, индекс в СУБД, или очередь в каком-нибудь обработчике событий. Это не просто перекидывание сообщений (читай: результатов работы) между потоками.
С вот этим пониманием, советую следующим шагом посмотреть доклад Introduction to Lock-free Programming — Tony van Eerd с NDC. Там достаточно понятно объясняется проблемма, которую решают вот эти неблокирующие алгоритмы.
Достаточно важный момент — "читать между строк", то есть подразумевать что любые две строчки программы (даже в виде комманд процессора) могут быть выполнены с достаточно большим промежутком (mov rax, [addr]; {пауза в 3 секунды}; add rax, rcx). Поэтому ветвления могут работать с устаревшими данными (во промежутке между коммандами, другой поток мог изменить данные).
И даже там есть несколько скользкий момент — в описании ABA докладчик очень быстро проскакивает достаточно важный момент, когда (на примере стека) память, освобождаемая одним потоком, переиспользуется другим потоком для создания нового объекта — с тем же адресом, но другой начинкой (данными, значением, смыслом — в общем, два разных объекта, но адреса в памяти у них однинаковые — это важно).
Следующий шаг (и да, это все чтобы банально понимать о чем в статье речь) — информация о том, что такое memory barrier (aka fence) — статья с modernsescpp.
Один из не совсем понятных моментов в статье — что вот эти все (read / load / acquire) и (write / store / release) — группы синонимов и ссылаются они на операции процессора mov — соотв., чтение из общей памяти (write / store / release / mov rax, [addr]) и запись в общую память (write / store / release / mov [addr], rax). В контексте барьеров (LoadLoad / LoadStore / StoreLoad / StoreStore) имеется в виду последовательность двух последовательных операций процессора по одному и тому же адресу (например, LoadLoad — mov rax, [addr]; mov rbx, [addr]). Операции над разными участками памяти (mov rax, [addr1]; mov rbx, [addr2]) и операции в промеждутке (mov rax, [addr1]; inc rcx; mov [addr1], rcx) не будут учтены барьером.
Возможно ускользающий момент — процессор может переупорядочивать операции в программе для ускорения работы. Насколько я понимаю, это связано с аппаратным кешированием. Поэтому барьеры используются для синхронизации (насильственного упорядочивания) операций над одним и тем же участком памяти, даже между разными потоками.
По сути последняя статья — подробности реализации CAS (compare and swap), о которой говорится в докладе Tony van Eerd (ссылка в начале комментария).
алгоритмы затронутые в статье подразумевают общую память, используемую несколькими потоками. К примеру — различные конкуррентные (от англ. concurrency) структуры данных — очереди, стеки и т.п., используемые в бóльших системах — к примеру, индекс в СУБД, или очередь в каком-нибудь обработчике событий. Это не просто перекидывание сообщений (читай: результатов работы) между потоками.
И то, и то: перекидывание сообщений между потоками тоже не может выполняться иначе чем через общую память. Но классическую модель producer-consumer, когда одному из потоков нечего делать, пока он не получит результаты работы другого потока, действительно невозможно реализовать в рамках lock-free. (Стандартный обходной путь — если результаты ещё не готовы, то consumer превращается в producer и пытается произвести нужные себе результаты сам.)
вот эти все (read / load / acquire) и (write / store / release) — группы синонимов и ссылаются они на операции процессора mov
Мир не ограничивается x86 :-) В AArch64 для каждой из этих операций есть отдельный опкод (
LDR, LDAR, STR, STLR) — и отдельно есть MOV, не работающий с памятью.перекидывание сообщений между потоками тоже не может выполняться иначе чем через общую память
Пытаюсь сообразить как может быть реализована на низком уровне модель акторов, но кроме как выделение нового куска памяти и передачи его адреса не могу придумать лучше.
В AArch64 для каждой из этих операций есть отдельный опкод (LDR,LDAR,STR,STLR) — и отдельно естьMOV, не работающий с памятью.
Ну эт я для простоты =)
С другой стороны, если внимательно дослушать доклад из предыдущего комментария до конца, то окажется что release и acquire — это не про store / load, как я написал, а как раз ближе к тому что описано в данной статье — если я правильно понял, то это больше про сигнализирование другим потокам, что все операции перед текущей закончились.
Ну и пример соответствующий хороший — если представить, что потоки не на одной машине, а на разных машинах в разных концах света (Япония, Австралия и США), когда поток из Японии поменяет кусок общей памяти и сообщит об этом потоку в Австралии, это не значит что поток из США не влез "между строк" и не поменял этот же кусок памяти на что-то еще.
Введение в неблокирующие алгоритмы