«Детская» задачка для программистов

    В процессе разработки наших программных продуктов перед нами часто встают задачи для решения которых требуются глубокие знания языка C++, принципов работы компиляторов и процессоров.

    Нашей компании нужны программисты, которые умеют решать подобные задачи.

    Например одна из таких задач: не компилируя этот код (очень важно решить ее в голове) скажите сработает ли когда-нибудь вывод «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: обвязочный код пропущен за несущественностью и конечно же, речь идет об многоядерных процессорах.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 118

    • UFO just landed and posted this here
      • UFO just landed and posted this here
        • UFO just landed and posted this here
          • UFO just landed and posted this here
            • UFO just landed and posted this here
              • UFO just landed and posted this here
          0
          Тут слипов нет, поэтому тот поток, который будет запущен первым заберет все ресурсы и не даст второму ничего сделать — если запускаем первый поток сначала, то все ок. Если второй, то не выведется.

          Вроде как-то так.
            +1
            Нет, задача гораздо сложнее и глубже.
              +2
              Правда? Тогда либо у вас неправильная задача либо вы сами не понимаете того, что описали в заголовке поста:) Только что запустил на выполнение следующий код — приписал мейн к вашему, во второй поток так никто и не зашел, как я и говорил:

              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);
              }
              }
                0
                Небольшой апдейт для уточнения: речь идет об многоядерных процессорах.
                  0
                  у меня два ядра, если вам это поможет:) надо больше?
                    0
                    Может и больше. У меня 4 и выводится BINGO, в каком бы порядке я не запустил потоки.
                    +2
                    хотя нет, вы действительно правы, извините.
                      0
                      Вы напишите это в посте.
                      А то я тоже решил эту задачу для одноядерного процессора :)
                        0
                        Напишите это перед кодом :)
                    • UFO just landed and posted this here
                        0
                        если в моем способе сначала запустить второй, то тоже ничего не выведется:)
                        • UFO just landed and posted this here
                            0
                            Только под Linux. Под Windows потоки с одинаковым приоритетом, всё равно будут исполнятся. После некоторого интервала времени, если поток не освобождает процессор, система понизит его приоритет. Вот так они и будут работать по-очереди.
                      +4
                      А как же насчет того что хороший код должен быть нагляден и понятен любому программисту? И если кто-то не может продумать результат в голове то наверно проблема не у него :)
                      Уметь быстро разбираться в хацкакоде не сильно увеличит качество продукта, нужен рефакторинг, иначе ошибку все равно пропустите.
                        0
                        Глубоко не анализировал — нет времени.

                        Ответ — да, выводиться будет, вне зависимости от того, какой поток стартует первым, но выводиться будет не всегда.

                        Есть заковыка в том, что копирование в test_xx из xx осуществляется с противоположных концов, а запись единиц в xx происходит в обратном порядке.

                        Синхронизация (весьма оригинальная) приводит к тому, что лупы выполняются одновременно, а кроме синхронизации на x86 есть еще cache_line_size, который также влияет на доступ.

                        Для того, чтобы достичь стабильного результата синхронизация должна быть другой.
                    • UFO just landed and posted this here
                        0
                        Извините за неудобства — так получилось в первом сообщении с непривычки :)
                        • UFO just landed and posted this here
                      • UFO just landed and posted this here
                          +1
                          Но задача ведь ставится как «не компилируя этот код (очень важно решить ее в голове)». Если в уме не получится, то остается обвешивать инклудами и в отладчик…
                          0
                          Я думаю сработает из-за memory barriers, в test_aa будут писаться нули из aa, хотя на другом процессоре туда уже записали 1.
                            0
                            Точнее из-за их отсутствия в вышеприведённом коде
                              0
                              На x86 memory barriers есть всегда.
                                0
                                Не все возможные, одного нет и из-за этого возможна такая «засада».
                            0
                            условие 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)

                            чистая логика, хотя возможно я неправ так как неучитываю разнообразных низкоуровневых многозадачных прибамбасов.
                              +3
                              кстати не INTERATIONS а ITERATIONS. язык програмирования тоже язык и читают его тоже люди ;)
                              • UFO just landed and posted this here
                                0
                                Само собой это возможно тольно на машинах с двумя и более процессорами в случае выполнения записи не в оригинальном порядке.
                                  –5
                                  Думаю что
                                  if(test_aa[tt]==0 && test_bb[tt]==0) cout << «BINGO» << endl;
                                  никогда не выполнится, потому что любой элемент массива aa[tt]=1; равен 1, следовательно любой элемент массива test_aa[tt] тоже равен 1, также и с массива bb[tt]=1;…
                                  хоть у меня и сомнения на этот счёт…

                                    +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! будет выводиться.
                                    • UFO just landed and posted this here
                                        0
                                        да-да, точно, насчет ноликов в начале или конце действительно неверно — ошибся в рассуждениях.

                                        Ну с учетом той информации, которую вы представили, становится все понятно — просто когда циклы встречаются и один из них еще не успел записать в aa/bb единицу, то и получается BINGO
                                          0
                                          А зависимость этого от нагруженности первого или второго Ядра другими потоками :)
                                      • UFO just landed and posted this here
                                        • UFO just landed and posted this here
                                            0
                                            вы на примере INerations = 1 расмотрите — понятнее станет.
                                            • UFO just landed and posted this here
                                                –1
                                                нет, тут прикол в том, что иногда быстрее выполнится следующая операция, чем успеет записаться результат предыдущей.
                                                • UFO just landed and posted this here
                                                  • UFO just landed and posted this here
                                                      0
                                                      они не пересекаются — там же синхронизация стоит
                                                        +1
                                                        Еще как пересекаются. Такая синхронизация до фени. Тут прямая зависимость от того, как были зашедулены потоки, от загрузки ядер, от уровня оптимизации, от компилятора, от того, является машина NUMA или SMP и насколько хорошо выполняется когерентность кешей.
                                                          0
                                                          А как может возникнуть такая ситуация, ведь поток не может выйти из цикла до того, как второй доберется до строки sync=++sync2;
                                                        0
                                                        вы можете проверить то что я написал двумя постами выше если поставите слипы

                                                        bb[tt]=1;
                                                        Sleep(1);
                                                        test_aa[tt]=aa[tt];

                                                        aa[tt]=1;
                                                        Sleep(1);
                                                        test_bb[tt]=bb[tt];

                                                        Я с такой проблемой уже сталкивался три года назад, когда писал два приложения, которые работали через разделяемую память. Долго не мог допереть в чем дело.
                                                        • UFO just landed and posted this here
                                                          • UFO just landed and posted this here
                                                  +1
                                                  где же GarretUA который считает программирование потоков совсем несложным делом? он бы помог разобраться ;)

                                                  а вообще если результат программы не совпадает с логически ожидаемым и математически обоснованным значит в дизайне изъян(flaw). ну или изъян в программистах.
                                                    0
                                                    > где же GarretUA который считает программирование потоков совсем несложным делом? он бы помог разобраться ;)

                                                    Либо память хорошая, либо злой и все записываешь :D

                                                    > а вообще если результат программы не совпадает с логически ожидаемым и математически обоснованным значит в дизайне изъян(flaw). ну или изъян в программистах.

                                                    Поэтому этот пост таки о шаманстве, а не программировании.
                                                      +2
                                                      > Либо память хорошая, либо злой и все записываешь :D
                                                      да вот ноотропил принимать начал :)
                                                    –2
                                                    нет никогда потому что никто не запускает Thread1
                                                      +2
                                                      А задачи такого рода вы задаете сразу же на собеседовании?
                                                      Не так давно искал работу и даже думал пойти к вам.
                                                      После этого поста — както расхотелось :)

                                                      Дальше идет сугубо мое личное имхо.

                                                      Приведенный код просто страшен, причем названия переменных — это похоже только вершина айсберга(хотел бы посмотреть на «обвязочный код»).
                                                      Вы действительно именно эти знания цените в программистах? Т.е. не архитектурные, не «понимание принципов ООП», не умение работать в команде, а глубокие знания глубоких принципов языка С++, компиляторов и процессоров? Тогда стоит добавить этот пункт к вашему резюме( habrahabr.ru/job/748/ ) :)
                                                        –1
                                                        Уважаемый, Adelf!
                                                        В процессе рассмотрения кандидатов по открытым вакансиям в Компании сложилась определенная этапность:
                                                        1. Рассмотрение резюме и примеров кода на С++;
                                                        2. Небольшое тестовое задание, которое кандидат спокойно выполняет в удобное ему время дома;
                                                        3. Собеседование (продолжительность 1-1,5ч.);
                                                        4. Тестовый испытательный срок 1 месяц (оплачиваемый);
                                                        5. Трудоустройство.
                                                      • UFO just landed and posted this here
                                                          +2
                                                          так как эта комания делает экономическое ПО, то теперь мы знаем какой код виновен в сегодняшнем кризисе :)
                                                            –1
                                                            Это упрощенный код, где ничего не мешает основной задаче — разобрать определенную проблему.

                                                            Как раз для ломки мозга.
                                                              0
                                                              У вас не поставлена задача разбора проблемы, т.к. нет задания, что необходимо сделать в итоге (как исправить). Есть только вопрос — будет ли выводиться и почему без требований привести это к какому-либо предсказуемому результауту :)
                                                            0
                                                            volatile не помогает лазить в кэши другого ядра ;)
                                                            тем кто ещё ломает мозг над задачкой — посвятите это время прочтению этого материала What every programmer should know about memory
                                                              0
                                                              Если это правда, что даже volatile не помогает лазить в кеши другого ядра, то надо убивать либо того кто делал кеши, либо того кто делал компилятор, либо мне пора убиться.
                                                                0
                                                                https://www.securecoding.cert.org/confluence/display/cplusplus/MEM11-CPP.+Do+not+use+volatile+as+a+synchronization+primitive
                                                                  0
                                                                  Спасибо, полезная статья (про volatile, про память тоже почитаю). Вообще, тогда сложно представить как реализуются lock-free и wati-free алгоритмы и структуры данных — там же потоки должны обмениваться информацией. Как?
                                                                    0
                                                                      0
                                                                      Данными могут обмениваться либо через атомарные функции, либо с помощью механизмов синхронизации. Полностью lock-free параллельно выполняющийся код, который не использует мезанизмы синхронизации для обмена данных ведет к хаосу.
                                                                        0
                                                                        Да, понятно. Это у меня временное помутнение разума было — забыл что lock-free делаются на атомарных операциях.
                                                                0
                                                                Оффтоп: MetaQuotes! С почином вас :)) рад видеть на хабре.
                                                                Сейчас как раз MT4 ставим :)
                                                                  –1
                                                                  Спасибо! Скоро выпустим МТ5 :)
                                                                  +6
                                                                  В этой задаче нет особенностей языка «C++», т.к. Стандарт насколько я помню не говорит ничего о потоках (мы не говорим об C++0x ?).
                                                                  Решение этой задачи нужно искать в плоскости исследования оптимизации компиляции (грубо говоря, Debug/Release будут давать разные результаты), особенности работы кешей 1 уровня на различных процессорах.
                                                                  Так как эти условия (компилятор, его ключи, процессор) не указаны, то краткий ответ — неопределенное поведение.
                                                                    0
                                                                    Можно уточнить: Visual Studio C++ 2005/2008, обычная релизная сборка.
                                                                      0
                                                                      Отдаю должное тщательности подбора примера. Будь там хоть одна lock-операция между записью и чтением — и ошибка исчезла бы. А так получился пример, к которому не подкопаться ссылкой на компилятор. На x86 чтение/запись volatile переменной происходит одной командой и поэтому проблема не в компиляторе, а именно в логической перестановке записи и чтения на SMP.
                                                                        0
                                                                        В целом согласен, но все-таки можно подкопаться —
                                                                        1. компиляторы при оптимизации могут менять порядок операций. Как — зависит от версии и ключей.
                                                                        2. не смотря на то, что чтение-запись volatile выглядит, как 1 команда, это не равносильно атомарной операции. Объяснения со ссылками уже приводились в этом треде. Хотя в этом примере возможные значение только 0 и 1, так что данный факт частично маскируется.

                                                                        В этом примере используется конкурентное чтение-запись одного участка памяти без использования lock'ов или atomic операций. Это — неопределенное поведение. Дальше практического смысла исследовать код нет. Можно только проанализировать его на конкретной машине разобрав по косточкам конкретную ситуацию. Еще одно применение — показывать упорным юниорам, которые уверены, что синхронизировать разделяемую переменную типа bool или даже int не надо :)

                                                                        Примерно так бы и ответил бы на собеседовании, кстати ;)
                                                                          0
                                                                          Согласен, что без отсылки к существующей реальности и конкретному процессору (типа x86) этот пример не может быть разобран по существу и согласен с тем, что абстрактно (без жесткой необходимости выжать последние такты и без учета специфики железа) такой стиль программирования вообще некорректен и логическим образом ведет к разнообразным ловушкам. Но, как я понимаю, автор примера хотел бы получить конкретное объяснение причины некорректного поведения программы конкретно на x86.
                                                                          По Вашим комментариям:
                                                                          1. Обращения к переменным, объявленным как volatile, не должны переставляться за пределами sequence point по стандарту языка C. В этом примере все важные переменные описаны как volatile.
                                                                          2. Просто чтение или запись volatile на всех существующих mainstream процессорах это действительно одна команда. Не путать с операциями типа x++.
                                                                      0
                                                                      На x86 проблемы возможны с любым реальным компилятором, так как они идут от возможности reorder-а команды записи и команды чтения на SMP/при нескольких ядрах.
                                                                      +1
                                                                      Я многопоточным программированием не занимался, но рассуждал вот так:
                                                                      Секции с меткой
                                                                      //--- 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] — это две операции: взять из памяти, положить в память, т.е. вполне может быть неатомичным.
                                                                      Учитывая, что фокус работает только с несколькими ядрами, виноват, видимо, не компилятор, а процессорные кэши. Ну а если вставить критическую секцию, то фокус испортится :)
                                                                        0
                                                                        Брр, атомарный конечно, а не атомичный, как-то я не по-русски :-Х
                                                                        –1
                                                                        как переключать конекст между потоками — в любом случае решает ОСь, поэтому может да а может и нет. И многоядерность не должна сыграть существенной роли, разве что увеличить вероятность увидеть это самое бинго.
                                                                        А вообще если пользоваться нормальными средствами синхронизации потоков, ака pthread_cond_wait и иже с ним — таких проблем можно избежать на корню ( да да — меня безумно порадовал ваш метод синхронизции грузящий процессор на 100% ).
                                                                          +1
                                                                          Типичный пример data race. Вот только зачем?
                                                                            0
                                                                            А Вы знаете толк в извращениях :)
                                                                            Если предположить, что все операции в циклах атомарны и результат их работы доступен всем потокам сразу, то BINGO мы никогда не увидим.
                                                                            Почему на практике иначе уже сказали здесь habrahabr.ru/company/metaquotes/blog/50417/#comment_1329798
                                                                              +2
                                                                              В вашей компании часто возникают задачи подобные этой и вашим программистам приходится их решать? Вы считаете, что способность решать такие задачи как-то говорит о глубоких знаниях языка?

                                                                              По-моему, Вы пытаетесь сделать антирекламу своей компании. Больше мне ничего в голову по поводу этой «задачки» не приходит. Нормальный программист должен решать другие задачи, в частности как сделать так, чтобы не приходилось «решать» такие «задачки».
                                                                                +3
                                                                                Абсолютно верно. Два потока, работающих с одними данными без объектов синхронизации (переменные sync — это самообман) дают абсолютно хаотичные результаты. Если автор думает, что верен какой-либо другой ответ на эту задачу — он ошибается.
                                                                                  –3
                                                                                  Это тренирующая мозголомка.

                                                                                  А так как мы написали множество многопоточных серверов разнообразных уровней, где одновременно обслуживаются тысячи подключенных клиентов, то для нас это близко.

                                                                                  Важно, чтобы программисты знали не только основные условия синхронизации, но и имели детальное представление об особенностях низкоуровневых операций на многоядерных процессорах.
                                                                                    +1
                                                                                    Если вы хотите четкого поведения от куска кода, да еще чтобы не было всяческих unexpected behaviour — пользуйтесь примитивами синхронизации ОС. Писать велосипеды с volatile и надеятся, что они будут работать коррентно под разными ОС на разных платформах — глупо.
                                                                                      0
                                                                                      Мы не хотим «четкого поведения», а хотим задать хитрую задачку и посмотреть на ответы.

                                                                                      Пример ведь специально создан ради того, чтобы программисты могли докопаться до реального разбора механизмов исполнения операций _без_защитной_синхронизации_ (критических секций или мутексов).
                                                                                      0
                                                                                      Те, кто в этом разбиается на достаточном уровне — обычно не пользуются готовыми решениями, которые представляет компилятор, а пишут свой код на ASM под конкретную платформу, которую необходимо поддерживать. У нас такое реализовано для x86 и PPC.

                                                                                      Ну и по крайней мере volatile это уж точно не барьеры, а совет копилятору, в каком порядке производить вычисления. На платформе отличной от x86 барьеры необходимо выставлять ручками в коде :)
                                                                                    0
                                                                                    Странно вообще пытаться это решать без точного указания версии ОС (в каждой алгоритмы планировщика потоков свои) и версии компилятора ( у всех своих подходы ко всему что хоть чуть-чуть позволяет двоякость толкования).
                                                                                      0
                                                                                      Да, и еще без указания того, каким именно макаром и в каком порядке Вы эти потоки стартуете.
                                                                                      +5
                                                                                      Ба! MetaQuotes! Авторы самого популярного софта для лохотронов в Рунете :)

                                                                                      И задачка под стать — на демке всё работает, советник торгует, барыши идут, а стоит запустить реал, как сплошные убытки, никакого Bingo :)
                                                                                        –5
                                                                                        Называть форекс «лохотроном» могут только не умеющие на нем работать люди.
                                                                                          +4
                                                                                          Форекс — это FOREX, сокращение от FOReign EXchange, обозначает обмен свободно конвертируемых валют.
                                                                                          А лохотронами я назвал множество кухонь-«дилинговых центров» в России и бывших братских республиках, заманивающих лохов обещаниями быстрой наживы, бесплатными двухнедельными курсами обучения торговле, предлагающими начать «зарабатывать» со 100 баксов или даже 100 рублей :) — посмотрите рекламу любого такого «центра».
                                                                                            0
                                                                                            Спасибо за ликбез по Форексу, но я и так в теме :D

                                                                                            Yадеюсь, скоро все помойки вычистят. За Форекс-Клуб уже взялись недавно — лицензии лишили. А нормальные брокеры останутся (а они и в России есть).
                                                                                        +4
                                                                                        Разбирал, как работает этот участок кода. Вы простите, но это — леденящий душу ппц.

                                                                                        Во-первых 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 в сетевом драйвере в ядре — приятного мало, и поощрять подобный стиль — плохая привычка.
                                                                                          +1
                                                                                          Кстати, в конструкции:
                                                                                          int sync=++sync2;
                                                                                          while(sync1<sync);

                                                                                          Компилятор может легко выкинуть промежуточный sync, ради оптимизации, в итоге будут сравниваться два volatile, и какой из них раньше инкрементируется — вопрос случая :)
                                                                                            0
                                                                                            Я еще тут подумал. Если компилятор решит заоптимизировать код, и засунет sync1 и sync2 в регистры, тоооо каждый поток будет работать со своей копией sync1 и sync2, поскольку каждый поток имеет свой контекст и свой стек, а значит копия РОН у каждого из потоков — будет своя, т.е. эти попытки синхронизации будут просто пшиком, который просто для красоты :)
                                                                                              0
                                                                                              Поставившему минус — прошу аргументировать. Такое действительно бывает при высокой степени оптимизации.
                                                                                                0
                                                                                                volatile переменные не должны помещаться компилятором в регистры (хотя я минус не ставил). Скорее всего, дело в когерентности кешей.
                                                                                                  0
                                                                                                  Но он очень даже может это сделать: https://www.securecoding.cert.org/confluence/display/cplusplus/MEM11-CPP.+Do+not+use+volatile+as+a+synchronization+primitive
                                                                                                    0
                                                                                                    Я читал эту штуку. Как я понял, там всё-таки не говорится что volatile может быть помещён в регистр (или хотя бы что помещается хотя бы одним компилятором). У volatile другие проблемы. В частности, не гарантирован порядок вычислений, если участвуют volatile и не-volatile, но здесь вроде всё volatile. Конкретного объяснения для этой задачки из этой статейки я так и не почерпнул.
                                                                                              0
                                                                                              а что плохого будет если возникнет ситуация, что
                                                                                              sync == sync1 == sync2?

                                                                                              вроде ничего тогда не будет в цикле крутиться(у нас же условие sync1<sync, оно нарушится и поток выыйдет из цикла), или я вас не понял?
                                                                                                0
                                                                                                Глаза кривые, недосмотрел, торопился :)
                                                                                                0
                                                                                                Быть может, здесь небольшая хитрость, связанная с тем, что как volatile помечен указатель на массив, а элементы этого массива не являются защищенными от кеширования в процессоре. Тогда вполне может возникнуть ситуация, когда один поток присвоит элементу первого массива единицу, прочитает нуль из второго (второй массив еще не был изменен вторым потоком). А во время обработки этого индекса вторым потоком поток бы рад прочитать единицу (как логически правильное значение, ведь первый поток уже занес туда 1), да кеш процессора подсовывает ему нуль, и в результате оба значения остаются нулевыми, а потоки шагают дальше (расходятся, потому что первый поток шагает от начала к концу массивов, а второй — наоборот).
                                                                                                  0
                                                                                                  На однопроцессорных машинах такое навряд ли случится благодаря механизму синхронизации кешей, но именно на многоядерных вполне вероятно, поскольку, если я не ошибаюсь, в многоядерных процессорах проблема синхронизации кешей отодвинута на второй план в угоду производительности (т.к. каждое ядро имеет свой кеш), и синхронизацию необходимо осуществлять специальным образом.
                                                                                                  –2
                                                                                                  Не забывайте название темы — это мозголомка для анализа.

                                                                                                  Код специально написан для того, чтобы программист был вынужден докопаться до сути проблемы.
                                                                                                    +2
                                                                                                    Я вам скажу какая суть: это нестабильный код подверженный рейс кондишнс и прочим «радостям» многопоточного программирования. Это первый кандидат на рефакторинг. А специалист его писавший — не должен иметь право комита без код ревью. Вот и вся суть, а разгребать и пояснять почему он выполнился так или иначе — пустая трата времени.
                                                                                                  +1
                                                                                                  не пойду я к вам работать, не дай бог придется такой код за кем-то из ваших оптимизировать.
                                                                                                    +1
                                                                                                    Стиль ужасен, синхронизация вообще молчу. Задачи такие решать (хвала кому-нибудь) пока не приходилось, тем более в голове. Хотя… есть опыт отладки монструозного многопоточного модуля, который писали люди, давно уволившиеся, фиксили люди давно уволившиеся и половина тех несчастных кто работает сейчас… ну вобщем понятно )
                                                                                                    Такой код — путь в темнейшую и глубочайшую жопу.
                                                                                                    ЗЫ как докозательство — модуль переписываем заново, с новой архитектурой, на COM-Singleton с ком-евентами, ибо пофиксить тот кусок говна уже не представляется возможным =)
                                                                                                      –3
                                                                                                      Никто не предлагает фиксить код — он специально написан в качестве задачи.
                                                                                                        0
                                                                                                        В качестве какой задачи? :) Задача подразумевает достижения определенного результата — например, добиться стабильного выведения BINGO или наоборот.

                                                                                                        Объяснить почему и будет ли в текущем варианте — это может сделать любой, кто глубоко разбирался в подобных вещах на уровне CPU/кэшей и т.п.

                                                                                                        Тот, для кого синхронизация ограничивается *_mutex_lock() или *CriticalSection() — никогда не сможет объяснить, почему так происходит, т.к. у него подобных проблем просто не должно возникать ;)
                                                                                                      0
                                                                                                      Стиль ужасен конечно, я бы уволился, если бы от меня требовали такое поддерживать.
                                                                                                      Но всё-таки интересен точный квалифицированный ответ от авторов задачи. Тут объяснений много, но я не нашёл ни одно, которое бы меня полностью удовлетворило. Разбираться лень именно потому что непрактично — скорее всего никогда с таким в практике не столкнусь, а ответ знать интересно :)
                                                                                                        0
                                                                                                        фишка в том, что нету тут решения! код будет работать по-разному в зависимости от компилятора/процессора. Как именно — поможет дизассемблирование скомпилированного кода.
                                                                                                        Задача напомнила мне совсем недавнее обращение коллеги — после перехода с VS 6.0 на VS 2005 код
                                                                                                        func(a[++cnt], a[++cnt], a[++cnt]) стал работать по-другому :)
                                                                                                        Вопрос коллеги был такой же — «почему?».
                                                                                                        Правда, эта проблема относится к C++ и имеет формальное объяснение.
                                                                                                          0
                                                                                                          Не надо всё запутывать. Какой бы ни был код, он запускается, работает и народ говорит, что BINGO печатается, хотя не должен бы, как ожидается.
                                                                                                          В условии задачи сказано, что процессора минимум 2. Возможно этого достаточно и, независимо от платформы, BINGO печатается. О том, что оно не печатается на двух процессорах никто не заявлял.
                                                                                                          Но и конкретного объяснения — пример выполнения с последовательными состояниями памяти и кешей ядер никто не привёл.
                                                                                                        0
                                                                                                        ИМХО синхронизация потоков здесь «неправильная» и в таком коде будет рейс кондишн, а значит есть вероятность БИНГО выводиться будет.
                                                                                                          +2
                                                                                                          Задача тривиальна для тех, кто знает про 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, например, можно придумать гораздо более сложные ситуации. Там все еще более запущено, например:
                                                                                                          int volatile a = 0;
                                                                                                          int volatile sync = 0;

                                                                                                          Thread1:
                                                                                                          a = 1;
                                                                                                          sync = 1;

                                                                                                          Thread2:
                                                                                                          while (sync == 0) {};
                                                                                                          printf(“a = %u\n”, a);
                                                                                                          иногда напечатает a = 0.
                                                                                                            0
                                                                                                            БИНГО! Абсолютно правильный ответ, очень подробно и развернуто!

                                                                                                            От себя немного добавим:
                                                                                                            Текущие современные процессоры (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».

                                                                                                            Спасибо, всем кто обратил свое внимание на данную задачку и искал решение.
                                                                                                              +1
                                                                                                              Спасибо!

                                                                                                            Only users with full accounts can post comments. Log in, please.