Минимальный размер INT переменной для атомарных операций R/W, многопоточность
От: neokoder  
Дата: 08.12.14 13:18
Оценка:
Привет.
Хотелось бы уточнить такой вопрос. Какой минимальный размер INT переменной(1,2,4,8 байт) которую можно использовать как флаг или параметр при многопоточном программировании с условием что чтение и запись в эту переменную на уровне машинных инструкций будут происходит атомарно, т.е. за одну машиннную инструкцию? Независимо от архитектуры — 32bit или 64bit.

Я не спец в ассемблере, но насколько я знаю 1 байт, т.е. тип char можно точно считать таковым, потому что и запись и чтение одного байта в памяти точно происходит за одну машинную инструкцию. Не уверен точно на счет 2-х и 4-х байтовой, но скорее всего также, т.е. скажем двинуть 4-х байтовое значение в память или считать также можно за одну машинную инструкцию, не важно при этом что предварительно адрес памяти должен быть занесен в регистр и может значение также. А вот с 8-ю байтами наверняка есть варианты, для 32-битных компов точно. Поэтому собственно вопрос в итоге такой: 1 или 2 или 4 байт (чтобы не зависеть от архитектуры процессора)?
Re: Минимальный размер INT переменной для атомарных операций R/W, многопоточност
От: EreTIk EreTIk's Box
Дата: 08.12.14 13:26
Оценка: 20 (3) +1
N>Хотелось бы уточнить такой вопрос. Какой минимальный размер INT переменной(1,2,4,8 байт) которую можно использовать как флаг или параметр при многопоточном программировании с условием что чтение и запись в эту переменную на уровне машинных инструкций будут происходит атомарно, т.е. за одну машиннную инструкцию? Независимо от архитектуры — 32bit или 64bit.

"Атомарно" и "за одну машинную инструкцию" не эквивалентные понятия. Недавно на хабре проскакивал интересный перевод:

Например, в наборе инструкций ARMv7 есть инструкция strd, которая сохраняет содержимое двух 32-битных регистров в 64-битной переменной в памяти.

strd r0, r1, [r2]


На некоторых ARMv7 процессорах эта инструкция не является атомарной. Когда процессор видит такую инструкцию, он на самом деле выполняет две отдельные операции


Другой пример, всем известная операция архитектуры x86, 32-битная операция mov атомарна в том случае, когда операнд в памяти выровнен, и не атомарна в противном случае

Re: Минимальный размер INT переменной для атомарных операций R/W, многопоточност
От: smeeld  
Дата: 08.12.14 13:29
Оценка: 12 (1)
Здравствуйте, neokoder, Вы писали:

Цитата из Intel Developer Manual

The Intel486 processor (and newer processors since) guarantees that the following basic memory operations will
always be carried out atomically:
Reading or writing a byte
Reading or writing a word aligned on a 16-bit boundary
Reading or writing a doubleword aligned on a 32-bit boundary
The Pentium processor (and newer processors since) guarantees that the following additional memory operations
will always be carried out atomically:

Reading or writing a quadword aligned on a 64-bit boundary
16-bit accesses to uncached memory locations that fit within a 32-bit data bus
The P6 family processors (and newer processors since) guarantee that the following additional memory operation
will always be carried out atomically:

Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within a cache line
Accesses to cacheable memory that are split across cache lines and page boundaries are not guaranteed to be
atomic by the Intel Core 2 Duo, Intel ® AtomTM, Intel Core Duo, Pentium M, Pentium 4, Intel Xeon, P6 family,
Pentium, and Intel486 processors. The Intel Core 2 Duo, Intel Atom, Intel Core Duo, Pentium M, Pentium 4, Intel
Xeon, and P6 family processors provide bus control signals that permit external memory subsystems to make split
accesses atomic; however, nonaligned data accesses will seriously impact the performance of the processor and
should be avoided.

Re: Минимальный размер INT переменной для атомарных операций R/W, многопоточност
От: Sinix  
Дата: 08.12.14 13:41
Оценка: 12 (1)
Здравствуйте, neokoder, Вы писали:

N>Хотелось бы уточнить такой вопрос. Какой минимальный размер INT переменной(1,2,4,8 байт) которую можно использовать как флаг или параметр при многопоточном программировании с условием что чтение и запись в эту переменную на уровне машинных инструкций будут происходит атомарно, т.е. за одну машиннную инструкцию? Независимо от архитектуры — 32bit или 64bit.


intel — регистр, см test-and-set/compare and swap.
arm — извращения типа такого. В сумме — тож регистр.

Хинт: для большинства языков уже есть готовые решения. Лучше не изобретать велосипед, а поискать решение конкретной проблемы на конкретном языке.
Re[2]: Минимальный размер INT переменной для атомарных операций R/W, многопоточн
От: Sinix  
Дата: 08.12.14 13:44
Оценка:
Здравствуйте, smeeld, Вы писали:

S>The Intel486 processor (and newer processors since) guarantees that the following basic memory operations will

S>always be carried out atomically:

Топикстартеру нужно не просто атомарное чтение/запись а test-set или CAS, он флаги на них делает.
Re: Минимальный размер INT переменной для атомарных операций R/W, многопоточност
От: Pzz Россия https://github.com/alexpevzner
Дата: 08.12.14 14:11
Оценка: 12 (1) +1
Здравствуйте, neokoder, Вы писали:

N>Хотелось бы уточнить такой вопрос. Какой минимальный размер INT переменной(1,2,4,8 байт) которую можно использовать как флаг или параметр при многопоточном программировании с условием что чтение и запись в эту переменную на уровне машинных инструкций будут происходит атомарно, т.е. за одну машиннную инструкцию? Независимо от архитектуры — 32bit или 64bit.


Там больше нюансов, чем вы думаете.

Работа с памятью обычно идет не байтами/словами, а блоками размером где-то примерно 16-32 байта, в зависимости от процессора, которые называются cache line.

Атомарность обычно обеспечивается для типов данных, размером от одного байта, до размера регистра, и при этом размер должен быть степенью двойки (т.е., на 64-битном x86 будут доступны атомарные операции для переменных, размером 1, 2, 4 и 8 байт). При этом переменная не должна пересекать границы cache line (если переменная выровнена на свой размер, то это гарантированно обеспечивается).

Однако не всякая операция атомарна. Наличие в процессоре 1-байтовых атомарных операций не означае, что всякое сишное i++, с i правильного размера, будет атомарным. Компилятор может выбрать для реализации такого инкремента операции, атомарность которых не обеспечивается процессором.

Кроме того, нежелательно пихать в один cache line несколько несвязанных таких переменных. Это будет работать корректно, но неоптимально по скорости, потому что аппаратура синхронизирыет доступ к памяти именно на уровне cache line. Впрочем, если вы не теребите такую переменную миллион раз в секунду, разница будет малозаметна.

В общем, проще использовать предоставляемые данной платформой средства для работы с атомарными переменными (типа ImterlockedIncrement в венде) и отталкиваться от того, с какими типами данных они умеют работать.
Re[2]: Минимальный размер INT переменной для атомарных операций R/W, многопоточн
От: neokoder  
Дата: 08.12.14 14:25
Оценка:
Здравствуйте, EreTIk, Вы писали:

ETI>"Атомарно" и "за одну машинную инструкцию" не эквивалентные понятия. Недавно на хабре проскакивал интересный перевод:

Ok. Буду иметь ввиду на будущее. Но в моем вопросе ключевым словом является — атомарно. Т.е. без разницы как формулировать.

ETI>

ETI>Например, в наборе инструкций ARMv7 есть инструкция strd, которая сохраняет содержимое двух 32-битных регистров в 64-битной переменной в памяти.
ETI>

ETI>strd r0, r1, [r2]
ETI>

ETI>На некоторых ARMv7 процессорах эта инструкция не является атомарной. Когда процессор видит такую инструкцию, он на самом деле выполняет две отдельные операции


Понятно. Но данный случай не важен поскольку я же свел свой вопрос к 1,2 или 4. В принципе 4 байтового значения вполне достаточно.

ETI>

ETI>Другой пример, всем известная операция архитектуры x86, 32-битная операция mov атомарна в том случае, когда операнд в памяти выровнен, и не атомарна в противном случае

Ну во-первых естественно мы обязательно объявляем эту переменную как volatile, чтобы избежать всяких там проблем с оптимизацией компилятором.
Ну а насчет выравнивания так это само собой разумеющееся что все INT-переменные выровнены в памяти по умолчанию, неважно статические они или под них выделяется память динамически. Это заботы компилятора и странно если бы это было иначе, зачем создавать такой код в котором будут явные alignment faults.
Re[3]: Минимальный размер INT переменной для атомарных операций R/W, многопоточн
От: neokoder  
Дата: 08.12.14 14:29
Оценка:
Здравствуйте, Sinix, Вы писали:

S>Топикстартеру нужно не просто атомарное чтение/запись а test-set или CAS, он флаги на них делает.

Так атомарное чтение/запись и будет гарантировать такое безопасное применение переменных при многопоточном программировании. Флаг или параметр, т.е. установка/чтение значения и проверка условия из разных потоков.
Re[4]: Минимальный размер INT переменной для атомарных операций R/W, многопоточн
От: Sinix  
Дата: 08.12.14 14:37
Оценка:
Здравствуйте, neokoder, Вы писали:

S>>Топикстартеру нужно не просто атомарное чтение/запись а test-set или CAS, он флаги на них делает.

N>Так атомарное чтение/запись и будет гарантировать такое безопасное применение переменных при многопоточном программировании. Флаг или параметр, т.е. установка/чтение значения и проверка условия из разных потоков.

Нет. Представьте себе гонку вида (псевдокод).
if (lock == 0) // (0)
{
  lock = 1;
  // do work; lock = 0;
}

Атомарная запись/чтение никак не спасёт от ситуации "n потоков пришли к (0)".

В цитате, что приводил smeeld выше, речь шла о другом (псевдокод):
a = 0x00000000;

// Thread 1:
a = 0xFFFFFFFF;

// Thread 2:
b = a;

атомарное чтение/запись гарантирует, что в B окажется или 0x00000000, или 0xFFFFFFFF, но никак не 0xFFFF0000 или рандомный мусор.
Re[2]: Минимальный размер INT переменной для атомарных операций R/W, многопоточн
От: neokoder  
Дата: 08.12.14 14:43
Оценка:
Здравствуйте, Pzz, Вы писали:


Pzz>Работа с памятью обычно идет не байтами/словами, а блоками размером где-то примерно 16-32 байта, в зависимости от процессора, которые называются cache line.

Pzz>Атомарность обычно обеспечивается для типов данных, размером от одного байта, до размера регистра, и при этом размер должен быть степенью двойки (т.е., на 64-битном x86 будут доступны атомарные операции для переменных, размером 1, 2, 4 и 8 байт). При этом переменная не должна пересекать границы cache line (если переменная выровнена на свой размер, то это гарантированно обеспечивается).
Ну то есть если у нас есть 4-х байтовая int переменная, которая само собой выровнена как надо, плюс ещё объявлена как volatile, значит она не будет пересекать границу cache line, правильно я понимаю? Ну тогда 4-х байтовая INT как раз и является ответом на мой вопрос.

Pzz>Однако не всякая операция атомарна. Наличие в процессоре 1-байтовых атомарных операций не означае, что всякое сишное i++, с i правильного размера, будет атомарным. Компилятор может выбрать для реализации такого инкремента операции, атомарность которых не обеспечивается процессором.

Пример для однобайтовой можно, где атомарность не обеспечивается процессором?
А насчет правильности написания кода, то как я уже здесь отвечал естественно мы даём указанию компилятору и объявляем переменную как: volatile __int32 flag1;

Pzz>Кроме того, нежелательно пихать в один cache line несколько несвязанных таких переменных. Это будет работать корректно, но неоптимально по скорости, потому что аппаратура синхронизирыет доступ к памяти именно на уровне cache line. Впрочем, если вы не теребите такую переменную миллион раз в секунду, разница будет малозаметна.

Это знаю. Понятно.

Pzz>В общем, проще использовать предоставляемые данной платформой средства для работы с атомарными переменными (типа ImterlockedIncrement в венде) и отталкиваться от того, с какими типами данных они умеют работать.

Я знаю про Interlocked. Но вот в том то и весь вопрос, чтобы без Interlocked.

Ну вот, я так думаю что после всего сказанного уже, 4-х байтовая переменная INT объявленная как volatile __int32 flag1; вполне может использоваться безопасно в многопоточном приложении. Я прав?
Re[5]: Минимальный размер INT переменной для атомарных операций R/W, многопоточн
От: neokoder  
Дата: 08.12.14 14:55
Оценка:
Здравствуйте, Sinix, Вы писали:

S>Нет. Представьте себе гонку вида (псевдокод).

S>
S>if (lock == 0) // (0)
S>{
S>  lock = 1;
S>  // do work; lock = 0;
S>}
S>

S>Атомарная запись/чтение никак не спасёт от ситуации "n потоков пришли к (0)".
Не, не. В плане использования я точно не имел ввиду такие конструкции
Требуется только о чем вы и написали далее.
Т.е. условно говоря. Несколько потоков пишут и читают некоторую переменную, проверки условия есть, но не для синхронизации, а только для присвоения значения.


S>атомарное чтение/запись гарантирует, что в B окажется или 0x00000000, или 0xFFFFFFFF, но никак не 0xFFFF0000 или рандомный мусор.

Именно это и требуется.
Re[2]: Минимальный размер INT переменной для атомарных операций R/W, многопоточн
От: neokoder  
Дата: 08.12.14 15:02
Оценка:
Здравствуйте, smeeld, Вы писали:

S>Цитата из Intel Developer Manual

S>

S>The Intel486 processor (and newer processors since) guarantees that the following basic memory operations will
S>always be carried out atomically:
S>Reading or writing a byte
S>Reading or writing a word aligned on a 16-bit boundary
S>Reading or writing a doubleword aligned on a 32-bit boundary


Написанному верим!

После всего сказанного делаю вывод, что 4 байтовая INT переменная ответ на мой вопрос. Правильно?
Re[3]: Минимальный размер INT переменной для атомарных операций R/W, многопоточн
От: Pzz Россия https://github.com/alexpevzner
Дата: 08.12.14 15:41
Оценка: 12 (1) +1
Здравствуйте, neokoder, Вы писали:

N>Ну то есть если у нас есть 4-х байтовая int переменная, которая само собой выровнена как надо, плюс ещё объявлена как volatile, значит она не будет пересекать границу cache line, правильно я понимаю? Ну тогда 4-х байтовая INT как раз и является ответом на мой вопрос.


volatile тут вообще не при чем.

Я вам еще про memory barrier забыл рассказать. Процессор может выполнять фактические обращения к памяти не в том порядке, в каком они написаны в программе (в ассемблерной программе). Memory barrier говорит процессору, "сначала доделай все отложенные обращения к памяти (чтения/записи/все), потом ехай дальше". У некоторых инструкций на некоторых процессорах эта семантика является побочным эффектом в дополнение к основному назначению инстукции, в других случаях такая инструкция только это и делает. Компилятор про это вообще ничего не знает.

N>Пример для однобайтовой можно, где атомарность не обеспечивается процессором?


mov al, var
inc al
mov var, al


N>А насчет правильности написания кода, то как я уже здесь отвечал естественно мы даём указанию компилятору и объявляем переменную как: volatile __int32 flag1;


volatile не обеспечивает атомарности.

Pzz>>В общем, проще использовать предоставляемые данной платформой средства для работы с атомарными переменными (типа ImterlockedIncrement в венде) и отталкиваться от того, с какими типами данных они умеют работать.

N>Я знаю про Interlocked. Но вот в том то и весь вопрос, чтобы без Interlocked.

Зачем?

N>Ну вот, я так думаю что после всего сказанного уже, 4-х байтовая переменная INT объявленная как volatile __int32 flag1; вполне может использоваться безопасно в многопоточном приложении. Я прав?


Нет.
Re[4]: Минимальный размер INT переменной для атомарных операций R/W, многопоточн
От: smeeld  
Дата: 08.12.14 16:29
Оценка:
Здравствуйте, Pzz, Вы писали:


Pzz>Я вам еще про memory barrier забыл рассказать.


Просто заостряемся под специфику

unsigned long a1=2345, a2;
__asm__ __volatile__(
 "movnti %1, %0 \t\n"
 : "=m" (a2)
 : "r" (a1)
 :
 );


The non-temporal hint is implemented by using a write combining (WC) memory type protocol when writing the
data to memory. Using this protocol, the processor does not write the data into the cache hierarchy, nor does it
fetch the corresponding cache line from memory into the cache hierarchy. The memory type of the region being
written to can override the non-temporal hint, if the memory address specified for the non-temporal store is in an
uncacheable (UC) or write protected (WP) memory region. For more information on non-temporal stores, see
“Caching of Temporal vs. Non-Temporal Data” in Chapter 10 in the Intel® 64 and IA-32 Architectures Software
Developer’s Manual, Volume 1.

Re[3]: Минимальный размер INT переменной для атомарных операций R/W, многопоточн
От: EreTIk EreTIk's Box
Дата: 08.12.14 17:03
Оценка:
N>Ok. Буду иметь ввиду на будущее. Но в моем вопросе ключевым словом является — атомарно. Т.е. без разницы как формулировать.
Не соглашусь: мы можем долго рассуждать об операции за одну машинную инструкцию, при этом я буду говорить о любых инструкциях, а вы понимать про атомарные.

N>Понятно. Но данный случай не важен поскольку я же свел свой вопрос к 1,2 или 4. В принципе 4 байтового значения вполне достаточно.

N>Ну во-первых естественно мы обязательно объявляем эту переменную как volatile, чтобы избежать всяких там проблем с оптимизацией компилятором.
N>Ну а насчет выравнивания так это само собой разумеющееся что все INT-переменные выровнены в памяти по умолчанию, неважно статические они или под них выделяется память динамически. Это заботы компилятора и странно если бы это было иначе, зачем создавать такой код в котором будут явные alignment faults.
Разные ситуации бывают: поля SDK-структур со своим выравниваем, кастомные компактные аллокаторы и т.п. Да и архитектуры не ограничиваются i386 и AMD64.

Если стандарт не говорит, что операция будет атомарной, то ради чего рисковать? Чем использование стандартных atomic или Interlocked не устраивает?
Re[4]: Минимальный размер INT переменной для атомарных операций R/W, многопоточн
От: neokoder  
Дата: 08.12.14 17:12
Оценка:
Pzz>volatile тут вообще не при чем.
в асме может и да но в С причем.

Pzz>volatile не обеспечивает атомарности.

я этого не говорил
Я использую его в связи с его назначением:

The volatile keyword is a type qualifier used to declare that an object can be modified in the program by something such as the operating system, the hardware, or a concurrently executing thread.



N>>Пример для однобайтовой можно, где атомарность не обеспечивается процессором?

Pzz>
Pzz>mov al, var
Pzz>inc al
Pzz>mov var, al
Pzz>

Типа i++?
Ну в данном случае как раз нет ничего страшного поскольку переменная не будет использоваться для синхронизации. Я ж обозначил это уже несколько раз.
Пусть inc увеличит уже измененную переменную, какие проблемы то?
Вы видимо до сих не поймете что я спрашиваю не про использование переменной, а про атомарность совершения операции для переменной состоящей из нескольких байт.

N>>Ну вот, я так думаю что после всего сказанного уже, 4-х байтовая переменная INT объявленная как volatile __int32 flag1; вполне может использоваться безопасно в многопоточном приложении. Я прав?

Pzz>Нет.
Почему нет то? Выше прочитайте и ещё раз ответьте.

Pzz>Я вам еще про memory barrier забыл рассказать. Процессор может выполнять фактические обращения к памяти не в том порядке, в каком они написаны в программе (в ассемблерной программе). Memory barrier говорит процессору, "сначала доделай все отложенные обращения к памяти (чтения/записи/все), потом ехай дальше". У некоторых инструкций на некоторых процессорах эта семантика является побочным эффектом в дополнение к основному назначению инстукции, в других случаях такая инструкция только это и делает. Компилятор про это вообще ничего не знает.

Это может привести к тому что нарушится гарантия о которой говорил Sinix:

атомарное чтение/запись гарантирует, что в B окажется или 0x00000000, или 0xFFFFFFFF, но никак не 0xFFFF0000 или рандомный мусор.

Если нет, тогда о чём вы вообще?
Re[4]: Минимальный размер INT переменной для атомарных операций R/W, многопоточн
От: neokoder  
Дата: 08.12.14 17:14
Оценка:
ETI>Если стандарт не говорит, что операция будет атомарной, то ради чего рисковать?
Как раз говорит вроде:

The Intel486 processor (and newer processors since) guarantees that the following basic memory operations will
always be carried out atomically:
Reading or writing a byte
Reading or writing a word aligned on a 16-bit boundary
Reading or writing a doubleword aligned on a 32-bit boundary


ETI>Чем использование стандартных atomic или Interlocked не устраивает?

Зачем? Если можно обойтись обычной переменной.
Re[5]: Минимальный размер INT переменной для атомарных опера
От: neokoder  
Дата: 08.12.14 17:20
Оценка: +1
N>>>Пример для однобайтовой можно, где атомарность не обеспечивается процессором?
Pzz>>
Pzz>>mov al, var
Pzz>>inc al
Pzz>>mov var, al
Pzz>>

N>Типа i++?
N>Ну в данном случае как раз нет ничего страшного поскольку переменная не будет использоваться для синхронизации. Я ж обозначил это уже несколько раз.
N>Пусть inc увеличит уже измененную переменную, какие проблемы то?

Написал, а сам уже думаю а если перед вторым mov изменится... Да, заморочки получатся. Выходит вы правы надо Interlocked использовать
Отредактировано 08.12.2014 17:21 neokoder . Предыдущая версия .
Re[4]: Минимальный размер INT переменной для атомарных опера
От: neokoder  
Дата: 08.12.14 17:27
Оценка:
ETI>Если стандарт не говорит, что операция будет атомарной, то ради чего рисковать? Чем использование стандартных atomic или Interlocked не устраивает?
Ну получается вы правы, только стандарт(как его назвать то не "процессорный", а "компиляторный" Получается если процессор на уровне инструкций может обеспечить атомарность, то это совсем ещё не означает что его сможет обеспечить компилятор через обычные операнды. В общем надо использовать функции специальные в С. Или писать ассемблерные вставки самому. Проще конечно будет первое. Хотя может для некоторых операций и вообще инструкций даже нет соответствующих или не на всех процах.

Так что вывод такой. Хотел я не использовать Interlocked для простоты, но не получится!

Всем спасибо за беседу и ответы.
Отредактировано 08.12.2014 17:32 neokoder . Предыдущая версия . Еще …
Отредактировано 08.12.2014 17:29 neokoder . Предыдущая версия .
Re[5]: Минимальный размер INT переменной для атомарных операций R/W, многопоточн
От: bnk СССР http://unmanagedvisio.com/
Дата: 08.12.14 17:52
Оценка:
Здравствуйте, neokoder, Вы писали:

Pzz>>volatile не обеспечивает атомарности.

N>я этого не говорил
N>Я использую его в связи с его назначением:
N>

The volatile keyword is a type qualifier used to declare that an object can be modified in the program by something such as the operating system, the hardware, or a concurrently executing thread.


volatile блокирует оптимизации компиятора для переменной.
То есть гарантируется, что переменная будет реально существовать (а не будет выброшена оптимизатором), и в нее реально будет осуществляться запись-чтение.
Но это никак не влияет на атомарность.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.