Комментарии 118
НЛО прилетело и опубликовало эту надпись здесь
Тут слипов нет, поэтому тот поток, который будет запущен первым заберет все ресурсы и не даст второму ничего сделать — если запускаем первый поток сначала, то все ок. Если второй, то не выведется.
Вроде как-то так.
Вроде как-то так.
Нет, задача гораздо сложнее и глубже.
Правда? Тогда либо у вас неправильная задача либо вы сами не понимаете того, что описали в заголовке поста:) Только что запустил на выполнение следующий код — приписал мейн к вашему, во второй поток так никто и не зашел, как я и говорил:
void main()
{
DWORD dwId;
HANDLE hThread = CreateThread(NULL, 0, Thread1, NULL, 0, &dwId);
hThread = CreateThread(NULL, 0, Thread2, NULL, 0, &dwId);
while(1)
{
Sleep(10);
}
}
void main()
{
DWORD dwId;
HANDLE hThread = CreateThread(NULL, 0, Thread1, NULL, 0, &dwId);
hThread = CreateThread(NULL, 0, Thread2, NULL, 0, &dwId);
while(1)
{
Sleep(10);
}
}
А как же насчет того что хороший код должен быть нагляден и понятен любому программисту? И если кто-то не может продумать результат в голове то наверно проблема не у него :)
Уметь быстро разбираться в хацкакоде не сильно увеличит качество продукта, нужен рефакторинг, иначе ошибку все равно пропустите.
Уметь быстро разбираться в хацкакоде не сильно увеличит качество продукта, нужен рефакторинг, иначе ошибку все равно пропустите.
Глубоко не анализировал — нет времени.
Ответ — да, выводиться будет, вне зависимости от того, какой поток стартует первым, но выводиться будет не всегда.
Есть заковыка в том, что копирование в test_xx из xx осуществляется с противоположных концов, а запись единиц в xx происходит в обратном порядке.
Синхронизация (весьма оригинальная) приводит к тому, что лупы выполняются одновременно, а кроме синхронизации на x86 есть еще cache_line_size, который также влияет на доступ.
Для того, чтобы достичь стабильного результата синхронизация должна быть другой.
Ответ — да, выводиться будет, вне зависимости от того, какой поток стартует первым, но выводиться будет не всегда.
Есть заковыка в том, что копирование в test_xx из xx осуществляется с противоположных концов, а запись единиц в xx происходит в обратном порядке.
Синхронизация (весьма оригинальная) приводит к тому, что лупы выполняются одновременно, а кроме синхронизации на x86 есть еще cache_line_size, который также влияет на доступ.
Для того, чтобы достичь стабильного результата синхронизация должна быть другой.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Я думаю сработает из-за memory barriers, в test_aa будут писаться нули из aa, хотя на другом процессоре туда уже записали 1.
условие test_aa[i] == test_bb[i] == 0 не может выполниться.
доказательство от противоположного — пусть условие выполнено, тогда должен был исполнится следующий код(1):
bb[i] = 1;
test_aa[i] = aa[i]; // 0
поскольку в bb[i] у нас уже 1, значит 0 оттуда считывался перед выполнением этого кода в таком куске:
aa[i] = 1;
test_bb[i] = bb[i]; // 0
но это невозможно, так как из aa[i] считалось бы 1 в куске кода (1)
чистая логика, хотя возможно я неправ так как неучитываю разнообразных низкоуровневых многозадачных прибамбасов.
доказательство от противоположного — пусть условие выполнено, тогда должен был исполнится следующий код(1):
bb[i] = 1;
test_aa[i] = aa[i]; // 0
поскольку в bb[i] у нас уже 1, значит 0 оттуда считывался перед выполнением этого кода в таком куске:
aa[i] = 1;
test_bb[i] = bb[i]; // 0
но это невозможно, так как из aa[i] считалось бы 1 в куске кода (1)
чистая логика, хотя возможно я неправ так как неучитываю разнообразных низкоуровневых многозадачных прибамбасов.
кстати не INTERATIONS а ITERATIONS. язык програмирования тоже язык и читают его тоже люди ;)
НЛО прилетело и опубликовало эту надпись здесь
Думаю что
if(test_aa[tt]==0 && test_bb[tt]==0) cout << «BINGO» << endl;
никогда не выполнится, потому что любой элемент массива aa[tt]=1; равен 1, следовательно любой элемент массива test_aa[tt] тоже равен 1, также и с массива bb[tt]=1;…
хоть у меня и сомнения на этот счёт…
if(test_aa[tt]==0 && test_bb[tt]==0) cout << «BINGO» << endl;
никогда не выполнится, потому что любой элемент массива aa[tt]=1; равен 1, следовательно любой элемент массива test_aa[tt] тоже равен 1, также и с массива bb[tt]=1;…
хоть у меня и сомнения на этот счёт…
Все, я кажется допер до решения.
Во-первых такие вот шутки делят программу на блоки
sync=++sync1;
while(sync2<sync);
причем начинают эти блоки эти потоки одновременно.
Во-вторых такие вот циклы
for(int tt=0; tt<INTERATIONS; tt++)
{
bb[tt]=1;
test_aa[tt]=aa[tt];
}
заполняют массив нулями примерно на середину — так как в разных потоках они идут в разных направлениях.
ну и главная фишка — потоки не могу закончить выполнение этого цила одновременно — следовательно либо у первого в конце, либо у второго в начале будет нолик (это я про массивы test_aa и test_bb), т.к. какой-то заполнит ячейку раньше, чем другой присвоит ему значение массива(aa или bb). Если у второго в начале ноль, то он будет равен первому элементу test_aa. Если у первого в конце, то он будет равен последнему test_bb. В обоих случаях имеем BINGO!..
BINGO не будет выведено только если циклы for закончатся одновременно, при этом на последней итерации сначала будут выполнены команды bb[tt]=1; aa[tt]=1; (в любой последовательности), а потом — test_aa[tt]=aa[tt]; test_bb[tt]=bb[tt]; Осуществление всех этих условий маловероятно, поэтому почти всегда надпись BINGO! будет выводиться.
Во-первых такие вот шутки делят программу на блоки
sync=++sync1;
while(sync2<sync);
причем начинают эти блоки эти потоки одновременно.
Во-вторых такие вот циклы
for(int tt=0; tt<INTERATIONS; tt++)
{
bb[tt]=1;
test_aa[tt]=aa[tt];
}
заполняют массив нулями примерно на середину — так как в разных потоках они идут в разных направлениях.
ну и главная фишка — потоки не могу закончить выполнение этого цила одновременно — следовательно либо у первого в конце, либо у второго в начале будет нолик (это я про массивы test_aa и test_bb), т.к. какой-то заполнит ячейку раньше, чем другой присвоит ему значение массива(aa или bb). Если у второго в начале ноль, то он будет равен первому элементу test_aa. Если у первого в конце, то он будет равен последнему test_bb. В обоих случаях имеем BINGO!..
BINGO не будет выведено только если циклы for закончатся одновременно, при этом на последней итерации сначала будут выполнены команды bb[tt]=1; aa[tt]=1; (в любой последовательности), а потом — test_aa[tt]=aa[tt]; test_bb[tt]=bb[tt]; Осуществление всех этих условий маловероятно, поэтому почти всегда надпись BINGO! будет выводиться.
НЛО прилетело и опубликовало эту надпись здесь
да-да, точно, насчет ноликов в начале или конце действительно неверно — ошибся в рассуждениях.
Ну с учетом той информации, которую вы представили, становится все понятно — просто когда циклы встречаются и один из них еще не успел записать в aa/bb единицу, то и получается BINGO
Ну с учетом той информации, которую вы представили, становится все понятно — просто когда циклы встречаются и один из них еще не успел записать в aa/bb единицу, то и получается BINGO
А зависимость этого от нагруженности первого или второго Ядра другими потоками :)
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
вы на примере INerations = 1 расмотрите — понятнее станет.
НЛО прилетело и опубликовало эту надпись здесь
нет, тут прикол в том, что иногда быстрее выполнится следующая операция, чем успеет записаться результат предыдущей.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
они не пересекаются — там же синхронизация стоит
вы можете проверить то что я написал двумя постами выше если поставите слипы
bb[tt]=1;
Sleep(1);
test_aa[tt]=aa[tt];
aa[tt]=1;
Sleep(1);
test_bb[tt]=bb[tt];
Я с такой проблемой уже сталкивался три года назад, когда писал два приложения, которые работали через разделяемую память. Долго не мог допереть в чем дело.
bb[tt]=1;
Sleep(1);
test_aa[tt]=aa[tt];
aa[tt]=1;
Sleep(1);
test_bb[tt]=bb[tt];
Я с такой проблемой уже сталкивался три года назад, когда писал два приложения, которые работали через разделяемую память. Долго не мог допереть в чем дело.
где же GarretUA который считает программирование потоков совсем несложным делом? он бы помог разобраться ;)
а вообще если результат программы не совпадает с логически ожидаемым и математически обоснованным значит в дизайне изъян(flaw). ну или изъян в программистах.
а вообще если результат программы не совпадает с логически ожидаемым и математически обоснованным значит в дизайне изъян(flaw). ну или изъян в программистах.
> где же GarretUA который считает программирование потоков совсем несложным делом? он бы помог разобраться ;)
Либо память хорошая, либо злой и все записываешь :D
> а вообще если результат программы не совпадает с логически ожидаемым и математически обоснованным значит в дизайне изъян(flaw). ну или изъян в программистах.
Поэтому этот пост таки о шаманстве, а не программировании.
Либо память хорошая, либо злой и все записываешь :D
> а вообще если результат программы не совпадает с логически ожидаемым и математически обоснованным значит в дизайне изъян(flaw). ну или изъян в программистах.
Поэтому этот пост таки о шаманстве, а не программировании.
нет никогда потому что никто не запускает Thread1
А задачи такого рода вы задаете сразу же на собеседовании?
Не так давно искал работу и даже думал пойти к вам.
После этого поста — както расхотелось :)
Дальше идет сугубо мое личное имхо.
Приведенный код просто страшен, причем названия переменных — это похоже только вершина айсберга(хотел бы посмотреть на «обвязочный код»).
Вы действительно именно эти знания цените в программистах? Т.е. не архитектурные, не «понимание принципов ООП», не умение работать в команде, а глубокие знания глубоких принципов языка С++, компиляторов и процессоров? Тогда стоит добавить этот пункт к вашему резюме( habrahabr.ru/job/748/ ) :)
Не так давно искал работу и даже думал пойти к вам.
После этого поста — както расхотелось :)
Дальше идет сугубо мое личное имхо.
Приведенный код просто страшен, причем названия переменных — это похоже только вершина айсберга(хотел бы посмотреть на «обвязочный код»).
Вы действительно именно эти знания цените в программистах? Т.е. не архитектурные, не «понимание принципов ООП», не умение работать в команде, а глубокие знания глубоких принципов языка С++, компиляторов и процессоров? Тогда стоит добавить этот пункт к вашему резюме( habrahabr.ru/job/748/ ) :)
Уважаемый, Adelf!
В процессе рассмотрения кандидатов по открытым вакансиям в Компании сложилась определенная этапность:
1. Рассмотрение резюме и примеров кода на С++;
2. Небольшое тестовое задание, которое кандидат спокойно выполняет в удобное ему время дома;
3. Собеседование (продолжительность 1-1,5ч.);
4. Тестовый испытательный срок 1 месяц (оплачиваемый);
5. Трудоустройство.
В процессе рассмотрения кандидатов по открытым вакансиям в Компании сложилась определенная этапность:
1. Рассмотрение резюме и примеров кода на С++;
2. Небольшое тестовое задание, которое кандидат спокойно выполняет в удобное ему время дома;
3. Собеседование (продолжительность 1-1,5ч.);
4. Тестовый испытательный срок 1 месяц (оплачиваемый);
5. Трудоустройство.
НЛО прилетело и опубликовало эту надпись здесь
volatile не помогает лазить в кэши другого ядра ;)
тем кто ещё ломает мозг над задачкой — посвятите это время прочтению этого материала What every programmer should know about memory
тем кто ещё ломает мозг над задачкой — посвятите это время прочтению этого материала What every programmer should know about memory
Если это правда, что даже volatile не помогает лазить в кеши другого ядра, то надо убивать либо того кто делал кеши, либо того кто делал компилятор, либо мне пора убиться.
https://www.securecoding.cert.org/confluence/display/cplusplus/MEM11-CPP.+Do+not+use+volatile+as+a+synchronization+primitive
Спасибо, полезная статья (про volatile, про память тоже почитаю). Вообще, тогда сложно представить как реализуются lock-free и wati-free алгоритмы и структуры данных — там же потоки должны обмениваться информацией. Как?
>Как?
Atomic Builtins
Atomic Builtins
Данными могут обмениваться либо через атомарные функции, либо с помощью механизмов синхронизации. Полностью lock-free параллельно выполняющийся код, который не использует мезанизмы синхронизации для обмена данных ведет к хаосу.
Оффтоп: MetaQuotes! С почином вас :)) рад видеть на хабре.
Сейчас как раз MT4 ставим :)
Сейчас как раз MT4 ставим :)
В этой задаче нет особенностей языка «C++», т.к. Стандарт насколько я помню не говорит ничего о потоках (мы не говорим об C++0x ?).
Решение этой задачи нужно искать в плоскости исследования оптимизации компиляции (грубо говоря, Debug/Release будут давать разные результаты), особенности работы кешей 1 уровня на различных процессорах.
Так как эти условия (компилятор, его ключи, процессор) не указаны, то краткий ответ — неопределенное поведение.
Решение этой задачи нужно искать в плоскости исследования оптимизации компиляции (грубо говоря, Debug/Release будут давать разные результаты), особенности работы кешей 1 уровня на различных процессорах.
Так как эти условия (компилятор, его ключи, процессор) не указаны, то краткий ответ — неопределенное поведение.
Можно уточнить: Visual Studio C++ 2005/2008, обычная релизная сборка.
Отдаю должное тщательности подбора примера. Будь там хоть одна lock-операция между записью и чтением — и ошибка исчезла бы. А так получился пример, к которому не подкопаться ссылкой на компилятор. На x86 чтение/запись volatile переменной происходит одной командой и поэтому проблема не в компиляторе, а именно в логической перестановке записи и чтения на SMP.
В целом согласен, но все-таки можно подкопаться —
1. компиляторы при оптимизации могут менять порядок операций. Как — зависит от версии и ключей.
2. не смотря на то, что чтение-запись volatile выглядит, как 1 команда, это не равносильно атомарной операции. Объяснения со ссылками уже приводились в этом треде. Хотя в этом примере возможные значение только 0 и 1, так что данный факт частично маскируется.
В этом примере используется конкурентное чтение-запись одного участка памяти без использования lock'ов или atomic операций. Это — неопределенное поведение. Дальше практического смысла исследовать код нет. Можно только проанализировать его на конкретной машине разобрав по косточкам конкретную ситуацию. Еще одно применение — показывать упорным юниорам, которые уверены, что синхронизировать разделяемую переменную типа bool или даже int не надо :)
Примерно так бы и ответил бы на собеседовании, кстати ;)
1. компиляторы при оптимизации могут менять порядок операций. Как — зависит от версии и ключей.
2. не смотря на то, что чтение-запись volatile выглядит, как 1 команда, это не равносильно атомарной операции. Объяснения со ссылками уже приводились в этом треде. Хотя в этом примере возможные значение только 0 и 1, так что данный факт частично маскируется.
В этом примере используется конкурентное чтение-запись одного участка памяти без использования lock'ов или atomic операций. Это — неопределенное поведение. Дальше практического смысла исследовать код нет. Можно только проанализировать его на конкретной машине разобрав по косточкам конкретную ситуацию. Еще одно применение — показывать упорным юниорам, которые уверены, что синхронизировать разделяемую переменную типа bool или даже int не надо :)
Примерно так бы и ответил бы на собеседовании, кстати ;)
Согласен, что без отсылки к существующей реальности и конкретному процессору (типа x86) этот пример не может быть разобран по существу и согласен с тем, что абстрактно (без жесткой необходимости выжать последние такты и без учета специфики железа) такой стиль программирования вообще некорректен и логическим образом ведет к разнообразным ловушкам. Но, как я понимаю, автор примера хотел бы получить конкретное объяснение причины некорректного поведения программы конкретно на x86.
По Вашим комментариям:
1. Обращения к переменным, объявленным как volatile, не должны переставляться за пределами sequence point по стандарту языка C. В этом примере все важные переменные описаны как volatile.
2. Просто чтение или запись volatile на всех существующих mainstream процессорах это действительно одна команда. Не путать с операциями типа x++.
По Вашим комментариям:
1. Обращения к переменным, объявленным как volatile, не должны переставляться за пределами sequence point по стандарту языка C. В этом примере все важные переменные описаны как volatile.
2. Просто чтение или запись volatile на всех существующих mainstream процессорах это действительно одна команда. Не путать с операциями типа x++.
На x86 проблемы возможны с любым реальным компилятором, так как они идут от возможности reorder-а команды записи и команды чтения на SMP/при нескольких ядрах.
Я многопоточным программированием не занимался, но рассуждал вот так:
Секции с меткой
//--- synchronization
действительно будут синхронизовать потоки, потому что там всего лишь ожидание изменения volatile переменной, которое не может быть «выоптимизировано» компилятором из-за volatile.
Для того, чтобы возникло BINGO, нужно, чтобы одновременно test_aa[x] и test_bb[x] были нулями, потоки идут навстречу друг другу, значит x — это их «точка встречи».
Касательно этой точки, у нас есть по две инструкции в каждом потоке:
bb[x]=1;
test_aa[x]=aa[x];
и
aa[x]=1;
test_bb[x]=bb[x];
Если представить, что все операции атомичны, хоть и могут перемешиваться, то одновременно получить нули не получится. Но например копирование aa[x] в test_aa[x] — это две операции: взять из памяти, положить в память, т.е. вполне может быть неатомичным.
Учитывая, что фокус работает только с несколькими ядрами, виноват, видимо, не компилятор, а процессорные кэши. Ну а если вставить критическую секцию, то фокус испортится :)
Секции с меткой
//--- synchronization
действительно будут синхронизовать потоки, потому что там всего лишь ожидание изменения volatile переменной, которое не может быть «выоптимизировано» компилятором из-за volatile.
Для того, чтобы возникло BINGO, нужно, чтобы одновременно test_aa[x] и test_bb[x] были нулями, потоки идут навстречу друг другу, значит x — это их «точка встречи».
Касательно этой точки, у нас есть по две инструкции в каждом потоке:
bb[x]=1;
test_aa[x]=aa[x];
и
aa[x]=1;
test_bb[x]=bb[x];
Если представить, что все операции атомичны, хоть и могут перемешиваться, то одновременно получить нули не получится. Но например копирование aa[x] в test_aa[x] — это две операции: взять из памяти, положить в память, т.е. вполне может быть неатомичным.
Учитывая, что фокус работает только с несколькими ядрами, виноват, видимо, не компилятор, а процессорные кэши. Ну а если вставить критическую секцию, то фокус испортится :)
как переключать конекст между потоками — в любом случае решает ОСь, поэтому может да а может и нет. И многоядерность не должна сыграть существенной роли, разве что увеличить вероятность увидеть это самое бинго.
А вообще если пользоваться нормальными средствами синхронизации потоков, ака pthread_cond_wait и иже с ним — таких проблем можно избежать на корню ( да да — меня безумно порадовал ваш метод синхронизции грузящий процессор на 100% ).
А вообще если пользоваться нормальными средствами синхронизации потоков, ака pthread_cond_wait и иже с ним — таких проблем можно избежать на корню ( да да — меня безумно порадовал ваш метод синхронизции грузящий процессор на 100% ).
Типичный пример data race. Вот только зачем?
А Вы знаете толк в извращениях :)
Если предположить, что все операции в циклах атомарны и результат их работы доступен всем потокам сразу, то BINGO мы никогда не увидим.
Почему на практике иначе уже сказали здесь habrahabr.ru/company/metaquotes/blog/50417/#comment_1329798
Если предположить, что все операции в циклах атомарны и результат их работы доступен всем потокам сразу, то BINGO мы никогда не увидим.
Почему на практике иначе уже сказали здесь habrahabr.ru/company/metaquotes/blog/50417/#comment_1329798
В вашей компании часто возникают задачи подобные этой и вашим программистам приходится их решать? Вы считаете, что способность решать такие задачи как-то говорит о глубоких знаниях языка?
По-моему, Вы пытаетесь сделать антирекламу своей компании. Больше мне ничего в голову по поводу этой «задачки» не приходит. Нормальный программист должен решать другие задачи, в частности как сделать так, чтобы не приходилось «решать» такие «задачки».
По-моему, Вы пытаетесь сделать антирекламу своей компании. Больше мне ничего в голову по поводу этой «задачки» не приходит. Нормальный программист должен решать другие задачи, в частности как сделать так, чтобы не приходилось «решать» такие «задачки».
Абсолютно верно. Два потока, работающих с одними данными без объектов синхронизации (переменные sync — это самообман) дают абсолютно хаотичные результаты. Если автор думает, что верен какой-либо другой ответ на эту задачу — он ошибается.
Это тренирующая мозголомка.
А так как мы написали множество многопоточных серверов разнообразных уровней, где одновременно обслуживаются тысячи подключенных клиентов, то для нас это близко.
Важно, чтобы программисты знали не только основные условия синхронизации, но и имели детальное представление об особенностях низкоуровневых операций на многоядерных процессорах.
А так как мы написали множество многопоточных серверов разнообразных уровней, где одновременно обслуживаются тысячи подключенных клиентов, то для нас это близко.
Важно, чтобы программисты знали не только основные условия синхронизации, но и имели детальное представление об особенностях низкоуровневых операций на многоядерных процессорах.
Если вы хотите четкого поведения от куска кода, да еще чтобы не было всяческих unexpected behaviour — пользуйтесь примитивами синхронизации ОС. Писать велосипеды с volatile и надеятся, что они будут работать коррентно под разными ОС на разных платформах — глупо.
Те, кто в этом разбиается на достаточном уровне — обычно не пользуются готовыми решениями, которые представляет компилятор, а пишут свой код на ASM под конкретную платформу, которую необходимо поддерживать. У нас такое реализовано для x86 и PPC.
Ну и по крайней мере volatile это уж точно не барьеры, а совет копилятору, в каком порядке производить вычисления. На платформе отличной от x86 барьеры необходимо выставлять ручками в коде :)
Ну и по крайней мере volatile это уж точно не барьеры, а совет копилятору, в каком порядке производить вычисления. На платформе отличной от x86 барьеры необходимо выставлять ручками в коде :)
Странно вообще пытаться это решать без точного указания версии ОС (в каждой алгоритмы планировщика потоков свои) и версии компилятора ( у всех своих подходы ко всему что хоть чуть-чуть позволяет двоякость толкования).
Ба! MetaQuotes! Авторы самого популярного софта для лохотронов в Рунете :)
И задачка под стать — на демке всё работает, советник торгует, барыши идут, а стоит запустить реал, как сплошные убытки, никакого Bingo :)
И задачка под стать — на демке всё работает, советник торгует, барыши идут, а стоит запустить реал, как сплошные убытки, никакого Bingo :)
Называть форекс «лохотроном» могут только не умеющие на нем работать люди.
Форекс — это FOREX, сокращение от FOReign EXchange, обозначает обмен свободно конвертируемых валют.
А лохотронами я назвал множество кухонь-«дилинговых центров» в России и бывших братских республиках, заманивающих лохов обещаниями быстрой наживы, бесплатными двухнедельными курсами обучения торговле, предлагающими начать «зарабатывать» со 100 баксов или даже 100 рублей :) — посмотрите рекламу любого такого «центра».
А лохотронами я назвал множество кухонь-«дилинговых центров» в России и бывших братских республиках, заманивающих лохов обещаниями быстрой наживы, бесплатными двухнедельными курсами обучения торговле, предлагающими начать «зарабатывать» со 100 баксов или даже 100 рублей :) — посмотрите рекламу любого такого «центра».
Разбирал, как работает этот участок кода. Вы простите, но это — леденящий душу ппц.
Во-первых volatile — не гарантирует того, что компилятор не будет кешировать данную переменную. Вам бы ее положить в регистр, было бы точнее.
Во-вторых эта переменная может кешироватся как в кеше одного ядра, так и другого. Также играет роль когерентность кешей, т.е. если потоки будут выполнятся параллельно, то тот же sync1 может быть равен разным значениям в каждом из потоков, попросту потому, что кеши процессоров могут быть не когерентны.
В-третьих, ваш механизм синхронизации… За это надо отбивать руки. Результат выполнения этого зависит напрямую от приоритета потоков в системе, многоядерная машина или нет, и т.д. Т.е. он слабо предсказуем, а в отдельном случае может залочить оба потока:
— Инкремент sync1 в первом потоке.
— Одновременный инкремент sync2 во втором потоке.
— sync == sync1 == sync2 — такое вполне может случится, и я думаю случается. Потоки крутятся в цыклах.
Если же мы бы выполняли это все на однопроцессорной машине, и первый поток зашедулился раньше, имели бы вот что:
Первый поток:
Инкремент sync1 в первом потоке, sync2 = 0. sync = 1
Проходит условия синхронизации (sync2 < sync, 0 < 1)
Второй поток:
Инкремент sync2. sync = 1, sync2 = 1, sync1 = 1
Поскольку 1 == 1, то условие синхронизации не выполняется и второй поток крутится в цыкле отжирая все процессорное время.
Первый поток:
bb заполняется единицами
test_aa заполняется нулями
Инкремент sync1. sync1 = 2, sync2 = 1, sync=2
1 < 2, идем дальше
aa и bb заполняется нулями
test_aa был заполненен нулями ранее, test_bb тоже, увидим bingo
А вообще, дурацкая задача, ужасный код. Я 2 недели сидел и вылавливал race conditions в сетевом драйвере в ядре — приятного мало, и поощрять подобный стиль — плохая привычка.
Во-первых volatile — не гарантирует того, что компилятор не будет кешировать данную переменную. Вам бы ее положить в регистр, было бы точнее.
Во-вторых эта переменная может кешироватся как в кеше одного ядра, так и другого. Также играет роль когерентность кешей, т.е. если потоки будут выполнятся параллельно, то тот же sync1 может быть равен разным значениям в каждом из потоков, попросту потому, что кеши процессоров могут быть не когерентны.
В-третьих, ваш механизм синхронизации… За это надо отбивать руки. Результат выполнения этого зависит напрямую от приоритета потоков в системе, многоядерная машина или нет, и т.д. Т.е. он слабо предсказуем, а в отдельном случае может залочить оба потока:
— Инкремент sync1 в первом потоке.
— Одновременный инкремент sync2 во втором потоке.
— sync == sync1 == sync2 — такое вполне может случится, и я думаю случается. Потоки крутятся в цыклах.
Если же мы бы выполняли это все на однопроцессорной машине, и первый поток зашедулился раньше, имели бы вот что:
Первый поток:
Инкремент sync1 в первом потоке, sync2 = 0. sync = 1
Проходит условия синхронизации (sync2 < sync, 0 < 1)
Второй поток:
Инкремент sync2. sync = 1, sync2 = 1, sync1 = 1
Поскольку 1 == 1, то условие синхронизации не выполняется и второй поток крутится в цыкле отжирая все процессорное время.
Первый поток:
bb заполняется единицами
test_aa заполняется нулями
Инкремент sync1. sync1 = 2, sync2 = 1, sync=2
1 < 2, идем дальше
aa и bb заполняется нулями
test_aa был заполненен нулями ранее, test_bb тоже, увидим bingo
А вообще, дурацкая задача, ужасный код. Я 2 недели сидел и вылавливал race conditions в сетевом драйвере в ядре — приятного мало, и поощрять подобный стиль — плохая привычка.
Кстати, в конструкции:
int sync=++sync2;
while(sync1<sync);
Компилятор может легко выкинуть промежуточный sync, ради оптимизации, в итоге будут сравниваться два volatile, и какой из них раньше инкрементируется — вопрос случая :)
int sync=++sync2;
while(sync1<sync);
Компилятор может легко выкинуть промежуточный sync, ради оптимизации, в итоге будут сравниваться два volatile, и какой из них раньше инкрементируется — вопрос случая :)
Я еще тут подумал. Если компилятор решит заоптимизировать код, и засунет sync1 и sync2 в регистры, тоооо каждый поток будет работать со своей копией sync1 и sync2, поскольку каждый поток имеет свой контекст и свой стек, а значит копия РОН у каждого из потоков — будет своя, т.е. эти попытки синхронизации будут просто пшиком, который просто для красоты :)
Поставившему минус — прошу аргументировать. Такое действительно бывает при высокой степени оптимизации.
volatile переменные не должны помещаться компилятором в регистры (хотя я минус не ставил). Скорее всего, дело в когерентности кешей.
Но он очень даже может это сделать: https://www.securecoding.cert.org/confluence/display/cplusplus/MEM11-CPP.+Do+not+use+volatile+as+a+synchronization+primitive
Я читал эту штуку. Как я понял, там всё-таки не говорится что volatile может быть помещён в регистр (или хотя бы что помещается хотя бы одним компилятором). У volatile другие проблемы. В частности, не гарантирован порядок вычислений, если участвуют volatile и не-volatile, но здесь вроде всё volatile. Конкретного объяснения для этой задачки из этой статейки я так и не почерпнул.
а что плохого будет если возникнет ситуация, что
sync == sync1 == sync2?
вроде ничего тогда не будет в цикле крутиться(у нас же условие sync1<sync, оно нарушится и поток выыйдет из цикла), или я вас не понял?
sync == sync1 == sync2?
вроде ничего тогда не будет в цикле крутиться(у нас же условие sync1<sync, оно нарушится и поток выыйдет из цикла), или я вас не понял?
Быть может, здесь небольшая хитрость, связанная с тем, что как volatile помечен указатель на массив, а элементы этого массива не являются защищенными от кеширования в процессоре. Тогда вполне может возникнуть ситуация, когда один поток присвоит элементу первого массива единицу, прочитает нуль из второго (второй массив еще не был изменен вторым потоком). А во время обработки этого индекса вторым потоком поток бы рад прочитать единицу (как логически правильное значение, ведь первый поток уже занес туда 1), да кеш процессора подсовывает ему нуль, и в результате оба значения остаются нулевыми, а потоки шагают дальше (расходятся, потому что первый поток шагает от начала к концу массивов, а второй — наоборот).
На однопроцессорных машинах такое навряд ли случится благодаря механизму синхронизации кешей, но именно на многоядерных вполне вероятно, поскольку, если я не ошибаюсь, в многоядерных процессорах проблема синхронизации кешей отодвинута на второй план в угоду производительности (т.к. каждое ядро имеет свой кеш), и синхронизацию необходимо осуществлять специальным образом.
Не забывайте название темы — это мозголомка для анализа.
Код специально написан для того, чтобы программист был вынужден докопаться до сути проблемы.
Код специально написан для того, чтобы программист был вынужден докопаться до сути проблемы.
Я вам скажу какая суть: это нестабильный код подверженный рейс кондишнс и прочим «радостям» многопоточного программирования. Это первый кандидат на рефакторинг. А специалист его писавший — не должен иметь право комита без код ревью. Вот и вся суть, а разгребать и пояснять почему он выполнился так или иначе — пустая трата времени.
не пойду я к вам работать, не дай бог придется такой код за кем-то из ваших оптимизировать.
Стиль ужасен, синхронизация вообще молчу. Задачи такие решать (хвала кому-нибудь) пока не приходилось, тем более в голове. Хотя… есть опыт отладки монструозного многопоточного модуля, который писали люди, давно уволившиеся, фиксили люди давно уволившиеся и половина тех несчастных кто работает сейчас… ну вобщем понятно )
Такой код — путь в темнейшую и глубочайшую жопу.
ЗЫ как докозательство — модуль переписываем заново, с новой архитектурой, на COM-Singleton с ком-евентами, ибо пофиксить тот кусок говна уже не представляется возможным =)
Такой код — путь в темнейшую и глубочайшую жопу.
ЗЫ как докозательство — модуль переписываем заново, с новой архитектурой, на COM-Singleton с ком-евентами, ибо пофиксить тот кусок говна уже не представляется возможным =)
Никто не предлагает фиксить код — он специально написан в качестве задачи.
В качестве какой задачи? :) Задача подразумевает достижения определенного результата — например, добиться стабильного выведения BINGO или наоборот.
Объяснить почему и будет ли в текущем варианте — это может сделать любой, кто глубоко разбирался в подобных вещах на уровне CPU/кэшей и т.п.
Тот, для кого синхронизация ограничивается *_mutex_lock() или *CriticalSection() — никогда не сможет объяснить, почему так происходит, т.к. у него подобных проблем просто не должно возникать ;)
Объяснить почему и будет ли в текущем варианте — это может сделать любой, кто глубоко разбирался в подобных вещах на уровне CPU/кэшей и т.п.
Тот, для кого синхронизация ограничивается *_mutex_lock() или *CriticalSection() — никогда не сможет объяснить, почему так происходит, т.к. у него подобных проблем просто не должно возникать ;)
Стиль ужасен конечно, я бы уволился, если бы от меня требовали такое поддерживать.
Но всё-таки интересен точный квалифицированный ответ от авторов задачи. Тут объяснений много, но я не нашёл ни одно, которое бы меня полностью удовлетворило. Разбираться лень именно потому что непрактично — скорее всего никогда с таким в практике не столкнусь, а ответ знать интересно :)
Но всё-таки интересен точный квалифицированный ответ от авторов задачи. Тут объяснений много, но я не нашёл ни одно, которое бы меня полностью удовлетворило. Разбираться лень именно потому что непрактично — скорее всего никогда с таким в практике не столкнусь, а ответ знать интересно :)
фишка в том, что нету тут решения! код будет работать по-разному в зависимости от компилятора/процессора. Как именно — поможет дизассемблирование скомпилированного кода.
Задача напомнила мне совсем недавнее обращение коллеги — после перехода с VS 6.0 на VS 2005 код
func(a[++cnt], a[++cnt], a[++cnt]) стал работать по-другому :)
Вопрос коллеги был такой же — «почему?».
Правда, эта проблема относится к C++ и имеет формальное объяснение.
Задача напомнила мне совсем недавнее обращение коллеги — после перехода с VS 6.0 на VS 2005 код
func(a[++cnt], a[++cnt], a[++cnt]) стал работать по-другому :)
Вопрос коллеги был такой же — «почему?».
Правда, эта проблема относится к C++ и имеет формальное объяснение.
Не надо всё запутывать. Какой бы ни был код, он запускается, работает и народ говорит, что BINGO печатается, хотя не должен бы, как ожидается.
В условии задачи сказано, что процессора минимум 2. Возможно этого достаточно и, независимо от платформы, BINGO печатается. О том, что оно не печатается на двух процессорах никто не заявлял.
Но и конкретного объяснения — пример выполнения с последовательными состояниями памяти и кешей ядер никто не привёл.
В условии задачи сказано, что процессора минимум 2. Возможно этого достаточно и, независимо от платформы, BINGO печатается. О том, что оно не печатается на двух процессорах никто не заявлял.
Но и конкретного объяснения — пример выполнения с последовательными состояниями памяти и кешей ядер никто не привёл.
ИМХО синхронизация потоков здесь «неправильная» и в таком коде будет рейс кондишн, а значит есть вероятность БИНГО выводиться будет.
Задача тривиальна для тех, кто знает про memory barriers, как тут уже сказали многие люди выше. Народу просто лень разбираться в деталях, что именно там происходит. И это понятно — ошибка уже в самом факте написания подобного кода.
Но, так как я много раз сталкивался с проблемой memory barriers, то скажу, в чем тут конкретно дело. Дело в том, что на x86 в SMP-режиме отсутствует (на современных вариантах процессоров) один-единственный, но очень важный «классический» барьер — между записью и последующим чтением. WR-барьер, не путать с RW-барьером (хотя не люблю вообще эту терминологию «барьеров» a-la Linux Kernel, так как она не отражает всего многообразия современных средств синхронизации в CPU).
В результате чтение aa[tt] и bb[tt] в операторах test_aa[tt] = aa[tt] и test_bb[tt] = bb[tt] может быть выполнено раньше записи bb[tt] = 1 и aa[tt] = 1 (соответственно). Фактически команда записи может формально выполниться раньше (на уровне очередей в ядре CPU), но записанные данные не уйдут в реальную память, задержавшись в буфере записи или в кэше. Поэтому и возникает ситуация, что оба элемента test_aa[tt] и test_bb[tt] равны нулю.
Эта ситуация действительно принципиальна и не зависит от компилятора.
Вам повезло, что Вы имеете дело с процессорами x86, на которых нет конфликтов вида RR, WW, RW (если не брать старые процессоры типа Pentium Pro или варианты программирования памяти в out-of-order stores режиме). Для PowerPC, например, можно придумать гораздо более сложные ситуации. Там все еще более запущено, например:
Но, так как я много раз сталкивался с проблемой memory barriers, то скажу, в чем тут конкретно дело. Дело в том, что на x86 в SMP-режиме отсутствует (на современных вариантах процессоров) один-единственный, но очень важный «классический» барьер — между записью и последующим чтением. WR-барьер, не путать с RW-барьером (хотя не люблю вообще эту терминологию «барьеров» a-la Linux Kernel, так как она не отражает всего многообразия современных средств синхронизации в CPU).
В результате чтение aa[tt] и bb[tt] в операторах test_aa[tt] = aa[tt] и test_bb[tt] = bb[tt] может быть выполнено раньше записи bb[tt] = 1 и aa[tt] = 1 (соответственно). Фактически команда записи может формально выполниться раньше (на уровне очередей в ядре CPU), но записанные данные не уйдут в реальную память, задержавшись в буфере записи или в кэше. Поэтому и возникает ситуация, что оба элемента test_aa[tt] и test_bb[tt] равны нулю.
Эта ситуация действительно принципиальна и не зависит от компилятора.
Вам повезло, что Вы имеете дело с процессорами x86, на которых нет конфликтов вида RR, WW, RW (если не брать старые процессоры типа Pentium Pro или варианты программирования памяти в out-of-order stores режиме). Для PowerPC, например, можно придумать гораздо более сложные ситуации. Там все еще более запущено, например:
int volatile a = 0;
int volatile sync = 0;
Thread1:
a = 1;
sync = 1;
Thread2:
while (sync == 0) {};
printf(“a = %u\n”, a);
БИНГО! Абсолютно правильный ответ, очень подробно и развернуто!
От себя немного добавим:
Текущие современные процессоры (P4,Core Duo) поддерживают out-of-order execution (memory-ordering model), в большей части пользовательского адресного пространства действует именно этот режим, режимы контролируются дополнительными флагами кеширования памяти.
В данном случае мы видим именно эту ситуацию, процессору позволено выполнять чтение для след. инструкции, до завершения текущей с записью (для данных с разными адресами), соответственно чтение aa[tt] происходит до записи bb[tt].
Упрощенно, процессор иногда выполняет инструкции вот так:
int temp=aa[tt];
bb[tt]=1;
test_aa[tt]=temp;
но в коде того нет, там четко написано:
bb[tt]=1;
test_aa[tt]=aa[tt];
Такой механизм оптимизации без проблемно работает для одного процессора, но в очень редких случаях на многопроцессорной машине это приводит вот к таким артефактам:
См. Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3A: System Programming Guide, Part 1, 7.2.3.4 «Loads May Be Reordered with Earlier Stores to Different Locations».
Спасибо, всем кто обратил свое внимание на данную задачку и искал решение.
От себя немного добавим:
Текущие современные процессоры (P4,Core Duo) поддерживают out-of-order execution (memory-ordering model), в большей части пользовательского адресного пространства действует именно этот режим, режимы контролируются дополнительными флагами кеширования памяти.
В данном случае мы видим именно эту ситуацию, процессору позволено выполнять чтение для след. инструкции, до завершения текущей с записью (для данных с разными адресами), соответственно чтение aa[tt] происходит до записи bb[tt].
Упрощенно, процессор иногда выполняет инструкции вот так:
int temp=aa[tt];
bb[tt]=1;
test_aa[tt]=temp;
но в коде того нет, там четко написано:
bb[tt]=1;
test_aa[tt]=aa[tt];
Такой механизм оптимизации без проблемно работает для одного процессора, но в очень редких случаях на многопроцессорной машине это приводит вот к таким артефактам:
См. Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3A: System Programming Guide, Part 1, 7.2.3.4 «Loads May Be Reordered with Earlier Stores to Different Locations».
Спасибо, всем кто обратил свое внимание на данную задачку и искал решение.
Спасибо!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
«Детская» задачка для программистов