Взято отсюда.

не компилируя этот код (очень важно решить ее в голове) скажите сработает ли когда-нибудь вывод «BINGO»?

enum { INTERATIONS=100 };

LONG volatile sync1=0;
LONG volatile sync2=0;

int volatile aa[INTERATIONS]={0};
int volatile bb[INTERATIONS]={0};

int volatile test_aa[INTERATIONS]={0};
int volatile test_bb[INTERATIONS]={0};

DWORD WINAPI Thread1(void *arg)
 {
  while(1)
   {
   //--- synchronization
   int sync=++sync1;
   while(sync2<sync);
   //---
   for(int tt=0; tt<INTERATIONS; tt++)
    {
     bb[tt]=1;
     test_aa[tt]=aa[tt];
    }
   //--- synchronization
   sync=++sync1;
   while(sync2<sync);
   //--- testing
   for(int tt=0; tt<INTERATIONS; tt++)
    {
     aa[tt]=bb[tt]=0;
     if(test_aa[tt]==0 && test_bb[tt]==0) cout << "BINGO" << endl;
    }
   //---
   }
  //---
  return(0);
 }
 
DWORD WINAPI Thread2(void *arg)
 {
  while(1)
   {
   int sync=++sync2;
   while(sync1<sync);
   //---
   for(int tt=INTERATIONS-1; tt>=0; tt--)
    {
     aa[tt]=1;
     test_bb[tt]=bb[tt];
    }
   //--- synchronization
   sync=++sync2;
   while(sync1<sync);
   }
  //---
  return(0);
 }

Объясните причину такого поведения?

Upd: обвязочный код пропущен за несущественностью и конечно же, речь идет об многоядерных процессорах

от себя: та как изначально в задаче не описанно полное окружение, чтобы не начинать рассуждение о компиляторах/ОС, пусть будет MSVC 2005/2008 и не особо загруженный процессор core duo/quad с WindowsXP/Vista.

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

D>Объясните причину такого поведения?

UB объясняет всё!

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

D>Взято отсюда.

D>не компилируя этот код (очень важно решить ее в голове) скажите сработает ли когда-нибудь вывод «BINGO»?

Выкинул весь этот кромешный п....ц.

То, что громко названо "synchronization" — хурма полнейшая.

D>Объясните причину такого поведения?

Здесь будут гонки, если кому-то на хабре хочется гадать — пусть идут в казино.

D>Upd: обвязочный код пропущен за несущественностью и конечно же, речь идет об многоядерных процессорах

Ну конечно! Эти метаквотеры — крутые ребята!

D>от себя: та как изначально в задаче не описанно полное окружение, чтобы не начинать рассуждение о компиляторах/ОС, пусть будет MSVC 2005/2008 и не особо загруженный процессор core duo/quad с WindowsXP/Vista.

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

не дай бог такое поддерживать, ну да ладно.

меня интересует зачем указатель объявили volatile?

D>Объясните причину такого поведения?

Два предположения, или из-за out of order execution на самом деле операция чтения в том цикле выполняется одновременно с операцией записи, и так в обоих потоках. Или, я не знаю, L1 кэши в двух разных ядрах синхронизуются?

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

R>То, что громко названо "synchronization" — хурма полнейшая.

Как я понял, там просто синхронизация для запуска 2 потоков одновременно (что бы они вошли в циклы "сильно" одновременно), такой "своеобразный" обратный спин-лок.

D>>от себя: та как изначально в задаче не описанно полное окружение, чтобы не начинать рассуждение о компиляторах/ОС, пусть будет MSVC 2005/2008 и не особо загруженный процессор core duo/quad с WindowsXP/Vista.

R>Вот эта информация вообще пох. Можно только посоветовать изучить как все современные ОС потоки квантуют. Ни к языку, ни к компилятору, ни к загруженности процессора эта "задача" никакого отношения не имеет.

это чтоб лишних вопросов не было...

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

D>не компилируя этот код (очень важно решить ее в голове) скажите сработает ли когда-нибудь вывод «BINGO»?

В голове — не очень, а на бумажке — пожалуйста.

Перепишем на двумерном питоне, для компакнтости.
Также мы можем отказаться от массивов, поскольку между их элементами нет зависимостей.

def body1() :                               def body2() :            
  barrier()                                   barrier()
  bb = 1                                      aa = 1
  test_aa = aa                                test_bb = bb
  barrier()                                   barrier()
  aa = 0
  bb = 0
  if test_aa==0 and test_bb==0 :
    print "bingo!"

Если бы записи в aa,bb,test_aa,test_bb были атомарными, то никакие перетасовки между двумя барьерами не могли бы привести к сочетанию (0,0).

Неатомарность же ведёт к неопределённому поведению, в частности, к возможности записать 0 в результате двух записей 1 в одну ячейку. На 16-битном процессоре такое сделать легко (достаточно, чтобы один поток писал в порядке HI,LO, а второй LO,HI).

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

S>Два предположения, или из-за out of order execution на самом деле операция чтения в том цикле выполняется одновременно с операцией записи, и так в обоих потоках. Или, я не знаю, L1 кэши в двух разных ядрах синхронизуются?

Да похоже на out of order execution, только не одновременно, а чтение раньше записи.

Просто в коде (ассемблер), нету никаких програмных race condition, а когерентность кешей обеспечивает x86 архитектура.

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

К>В голове — не очень, а на бумажке — пожалуйста.

К>Перепишем на двумерном питоне, для компакнтости.
К>Также мы можем отказаться от массивов, поскольку между их элементами нет зависимостей.
К>

К>def body1() :                               def body2() :            
К>  barrier()                                   barrier()
К>  bb = 1                                      aa = 1
К>  test_aa = aa                                test_bb = bb
К>  barrier()                                   barrier()
К>  aa = 0
К>  bb = 0
К>  if test_aa==0 and test_bb==0 :
К>    print "bingo!"
К>

К>Если бы записи в aa,bb,test_aa,test_bb были атомарными, то никакие перетасовки между двумя барьерами не могли бы привести к сочетанию (0,0).

К>Неатомарность же ведёт к неопределённому поведению, в частности, к возможности записать 0 в результате двух записей 1 в одну ячейку. На 16-битном процессоре такое сделать легко (достаточно, чтобы один поток писал в порядке HI,LO, а второй LO,HI).

А они и атомарны если выровнены по 4 байта (здесь именно так), нету на x86 префикса lock на MOV'ах, этот префикс нужен только если комманда внутри процессора разбивается на две: чтение и запись (пример INC — сначало считаем из памяти предыдущее значение, увеличим на 1, потом запишем в память).

а здеся, что-то вроде:

mov [AA],1
mov eax,[BB]
mov [TEST_BB],eax

все операции атомарны и кеши процесссоров не могут влиять друг на друга на x86 (когерентность кешей).

D>mov [AA],1
D>mov eax,[BB]
D>mov [TEST_BB],eax

D>все операции атомарны и кеши процесссоров не могут влиять друг на друга на x86 (когерентность кешей).

такое может возникнуть только если выполнить инструкции в другом порядке
mov eax,[BB]
mov [AA],1
mov [TEST_BB],eax

а такого нет в исходном листинге кода (ассемблер), однозначно Out of Order Execution

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

D>а здеся, что-то вроде:

D>mov [AA],1
D>mov eax,[BB]
D>mov [TEST_BB],eax

Точнее, что-то вроде

  xor eax, eax
@loop:
  mov [aa+eax*4], 1
  mov ebx, [bb+eax*4]
  mov [test_bb+eax*4], ebx
  inc eax
  cmp eax, 100
  jb  @loop

Это при включенной оптимизации. При выключенной tt-eax кладется в переменную и достается оттуда всякий раз.

Кто знает, как работает Core Duo, особенно интересно декодирование инструкций? По идее действительно может быть такой вариант, что чтение выполняется одновременно с записью, это если обе инструкции будут декодироваться одновременно к моменту выполнения начала цикла. Варианта, что они выполняются не одновременно, а вторая (чтение) до первой (записи) имхо нет — там есть хвостик цикла такта на 4, инструкции чтения-записи успевают отработать и новые начинаются на следующем обороте максимум одновременно, потому что они обе зависят от измененного значения eax.

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

Ovl>не дай бог такое поддерживать, ну да ладно.

Ovl>меня интересует зачем указатель объявили volatile?
Ты не представляешь, что ты только что сделал.

S>Точнее, что-то вроде
S>

S>  xor eax, eax
S>@loop:
S>  mov [aa+eax*4], 1
S>  mov ebx, [bb+eax*4]
S>  mov [test_bb+eax*4], ebx
S>  inc eax
S>  cmp eax, 100
S>  jb  @loop
S>

S>Это при включенной оптимизации. При выключенной tt-eax кладется в переменную и достается оттуда всякий раз.

S>Кто знает, как работает Core Duo, особенно интересно декодирование инструкций? По идее действительно может быть такой вариант, что чтение выполняется одновременно с записью, это если обе инструкции будут декодироваться одновременно к моменту выполнения начала цикла. Варианта, что они выполняются не одновременно, а вторая (чтение) до первой (записи) имхо нет — там есть хвостик цикла такта на 4, инструкции чтения-записи успевают отработать и новые начинаются на следующем обороте максимум одновременно, потому что они обе зависят от измененного значения eax.

нашел ответ, кому интересно ответ тут Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A: System Programming Guide, Part 1 пункт 7.2.3.4

задача очень интересна, более всего меня поразила "неграмотность" людей которые пишут на хабре, котрые судят не по сути задачи, а стереотипами (неправильная синхронизация, неправильное кеширование процами, вообще все неправильно и так не должно быть), а объяснить почему-да-как не могут .

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

D>нашел ответ, кому интересно ответ тут Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A: System Programming Guide, Part 1 пункт 7.2.3.4

Гугл дает такую ссылку
http://www.intel.com/design/processor/manuals/253668.pdf

Там нет пункта 7.2.3.4, есть только 7.2.3 и он не про это.

А что там, собственно, написано, нельзя ли это в кратце написать?

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

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

D>>нашел ответ, кому интересно ответ тут Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A: System Programming Guide, Part 1 пункт 7.2.3.4

S>Гугл дает такую ссылку
S>http://www.intel.com/design/processor/manuals/253668.pdf

S>Там нет пункта 7.2.3.4, есть только 7.2.3 и он не про это.

S>А что там, собственно, написано, нельзя ли это в кратце написать?

как нету, только что скачал — все есть Loads May Be Reordered with Earlier Stores to Different Locations, вот даже скиншот с текстом приатачил (там защита, не скопипируешь).

скрин

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

D>как нету, только что скачал — все есть Loads May Be Reordered with Earlier Stores to Different Locations, вот даже скиншот с текстом приатачил (там защита, не скопипируешь).

Странно, у меня оно выглядит так:

http://i39.tinypic.com/33w7jac.png

S>>А что там, собственно, написано, нельзя ли это в кратце написать?

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

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

D>нашел ответ, кому интересно ответ тут Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A: System Programming Guide, Part 1 пункт 7.2.3.4

D>задача очень интересна, более всего меня поразила "неграмотность" людей которые пишут на хабре, котрые судят не по сути задачи, а стереотипами (неправильная синхронизация, неправильное кеширование процами, вообще все неправильно и так не должно быть), а объяснить почему-да-как не могут .

Ты издеваешься что-ли? Тебе в 4-х ответах из первых 5-и объяснили что к чему. Один человек даже на псевдокоде разжевал.
И ты до сих так и не понял, что дело как раз в синхронизации?
Ну колись — твоя бага?
Сознайся — думал, что выполняться будет в том порядке, как асм нагенерился?

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

R>Ты издеваешься что-ли? Тебе в 4-х ответах из первых 5-и объяснили что к чему. Один человек даже на псевдокоде разжевал.
R>И ты до сих так и не понял, что дело как раз в синхронизации?
R>Ну колись — твоя бага?
R>Сознайся — думал, что выполняться будет в том порядке, как асм нагенерился?

Это вы издеваетесь надо мной, эадача не моя и я даже не вижу смысла в этом коде, она, имхо, как уже замеченно написанна по мануалу интела.

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

Ткните мне пальцем где в 4 ответах указана что причина в out of order execution по причине того что современные x86 процессоры позволяют читать до записи, из памяти отличной от записываемой ?

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

D>Это вы издеваетесь надо мной, эадача не моя и я даже не вижу смысла в этом коде, она, имхо, как уже замеченно написанна по мануалу интела.

D>Извините меня но тут, блин, и ежу понятна что дело в синхронизации, раз речь пошла о двух процессорах и проблемах с ними, но вот что действительно неправильно в это синхронизации вы нифига мне не помогли понять.

D>Ткните мне пальцем где в 4 ответах указана что причина в out of order execution по причине того что современные x86 процессоры позволяют читать до записи, из памяти отличной от записываемой ?

На от меня:
Здесь будут гонки, если кому-то на хабре хочется гадать — пусть идут в казино.

На от Кодт:
Если бы записи в aa,bb,test_aa,test_bb были атомарными, то никакие перетасовки между двумя барьерами не могли бы привести к сочетанию (0,0).
Неатомарность же ведёт к неопределённому поведению...

А subdmitry вообще сразу про out of order написал.

Ты ответы внимательно читаешь?

Если мы все поняли, объясните мне, почему на хабре, где пробовали запускать эту программу, сообщают о несрабатывании бинго в где-то 20-30% случаев.