История двух нитей

    На собеседовании в ИТ-компании было предложено ответить на следующий вопрос.

    Задача. Дано такой код:

    		static int counter = 0;
    
    		void worker()
    		{
    			for (int i = 1; i <= 10; i++)
    				counter++;
    		}
    


    Процедуру worker() запускают из двух нитей. Какое значение будет содержать переменная counter по завершении работы обеих нитей и почему?

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

    Я не называю нити потоками, что бы не путать потоки выполнения (thread) и потоки данных (stream).



    Вариант ответа № 1. Переменная counter будет содержать число 20 — это самый желаемый результат, но и самый неверный ответ.

    Проблема в том, что данный код никак не защищён от рассинхронизации. Каждая нить работает независимо друг от друга и не подозревает, что общие данные (переменная counter) могут быть изменены кем-то ещё. Поэтому более правильный ответ такой: это небезопасный код и значение переменной counter будет неопределённым.

    Вариант № 2. Всё же зная основы работы процессора, ОС и компилятора можно более точно предположить какой результат мы получим.

    Подпрограмма worker() достаточно простая. Поэтому компилятор на этапе оптимизации может развернуть for-цикл в такую конструкцию:

    	counter += 10;


    Теперь код настолько тривиален, что первая нить может успеть закончить его выполнение ещё до того как запустится вторая нить. Таким образом мы получим число 20.

    Возможен и такой случай. Нити прочтут из оперативной памяти значение переменной counter (ноль) и занесут его в регистр процессора. Так как каждая нить работает в своём контексте процессора, то у каждой есть «свой независимый» набор регистров. Таким образом первая нить в своём контексте увеличит значение регистра с нуля до десяти и потом занесёт полученный результат обратно в память. А потом вторая нить сделает тоже самое и перезапишет ту десятку своей. В результате получим число 10.

    Значения 10 и 20 наиболее вероятны в реальной практике, но и это ещё не полный ответ.

    Вариант № 3. Давайте представим потенциально реальную, но максимально неэффективную схему работы. Так каждая итерация цикла будет одинаково повторять три атомарных действия: чтение значения counter в регистр процессора, инкремент этого регистра, запись нового значения из регистра обратно в память. (Реализацию самого цикла я не рассматриваю, так как она не играет никакой роли.) Плюс к этому переключение контекста выполнения нитей будет происходить тогда, когда этого хочется нам. На таких условиях мы можем получить результат от 2 до 20.

    Теперь на временной шкале в виде таблицы рассмотрим возможность получения двойки. Шаг 0 — изначальное состояние. Операции «→n», «n+» и «n→» соответственно представляют чтение из памяти в регистр, инкремент регистра и запись значения регистра в память в контексте нити № n. Строка «цикл» показывает номер итерации. Изменения значений на текущем шаге выделены для лучшего восприятия.

    Шаг 0   1 2   3 4 5 27 28 29   30   31 32   33 34 35 57 58 59   60
    Операция   →1 1+   →2 2+ 2→   →2 2+ 2→   1→   →2 2+   →1 1+ 1→   →1 1+ 1→   2→
    Нить № 1 Регистр   0 1   1 1 1   1 1 1   1   1 1   1 2 2 9 10 10   10
    Цикл 1   1 1   1 1 1   1 1 1   1   1 1   2 2 2 10 10 10   10
    Нить № 2 Регистр     0 1 1 8 9 9   9   1 2   2 2 2   2 2 2   2
    Цикл 1   1 1   1 1 1 9 9 9   9   10 10   10 10 10   10 10 10   10
    Память 0   0 0   0 0 1   8 8 9   1   1 1   1 1 2   9 9 10   2

    (Добавлено: по просьбе читателя вот вариант таблицы растровым изображением.)

    Шаги 1—2: первая нить заносит в регистр ноль и увеличивает его на единицу. 3—29: управление передаётся второй нити, которая тоже считывает ноль и выполняет девять полных итераций. 30: первая нить завершает первую итерацию цикла и заносит посчитанную единицу в память (перетирая девятку). 31—32: вторая нить начинает последнюю (десятую) итерацию, читает и инкриминирует единицу. 33—59: первая нить полностью выполняет девять оставшихся итераций и заканчивает свою работу. 60: вторая нить записывает в память посчитанную двойку и заканчивает свою работу.

    _________
    NB: это кросс-публикация с моего блога. Перепечатал, потому что на Хабре аудитория больше, чем у моего блога (: а материал, думаю, интересен.
    Поделиться публикацией

    Комментарии 69

      +2
      Спасибо, третий вариант очень красиво иллюстрирует, как может получиться 2.
        +2
        В русскоязычной литературе threads всё же принято называть потоками. Нити — это fibers.
          +7
          Мне кажется, fibers — это волокна.
          Дело в том, что я читал некоторую литературу по устройству ОС, там также использовали термин «нить». Ещё я вчера прочитал на ВП вот это, что и стало окончательным решением по выбору термина.
          Спасибо за замечание. Про волокна не знал.
            +5
            Я сталкиваюсь с тем что threads называют нитями или потоками. Fibers — волокна.
              0
              Для определенности в Pascal объектные типы когда-то стали называть классами, в отличие от объектов-экземпляров. То же самое, поддерживаю в русском языке: Thread-ы — нити, Stream-ы — потоки.
                +1
                Самый адекватный перевод на русский для thread — путь или маршрут. Отдельные пути или маршруты выполнения команд процессором, которые могут пересекаться, а команды могут использовать общую память. Но увы, устоялись действительно потоки.

                А называть потоки нитями, лишь потому что таков словарный перевод — просто глупо.
              • НЛО прилетело и опубликовало эту надпись здесь
                  +5
                  На собеседовании в ИТ-компании было предложено ответить на следующий вопрос.

                  Какое значение будет содержать переменная counter по завершении работы обоих нитей и почему?
                    +1
                    умник :)
                    • НЛО прилетело и опубликовало эту надпись здесь
                      +2
                      Отвечать нужно по варианту №1 и не тратить собственное время и время интервьюера.
                          –1
                          я бы согласился, если бы речь шла о приеме на работу в research отделы ibm, sun, microsoft, etc, однако практик (инженер) должен знать правильные методы.
                            0
                            Еще неплохо бы понимать ПОЧЕМУ правильные методы лучше неправильных.
                        +2
                        ответ зависит еще и от языка и платформы, ++ — может быть атомарным
                          +2
                          на x86 он скорее всего и будет атомарным, если ++ оттранслируется в инструкцию inc которая как известно в качестве аргумента может принимать ссылку на область памяти
                            +2
                            Если код будет запущен на многопроцессорной или многоядерной системе, то инкремент будет неатомарной операцией из-за наличия процессорных кэшей.
                              0
                              … при условии, что нити будут расбросаны по разным ядрам.
                              То есть тут два условия должно сработать независимых.
                              +1
                              «скорее всего» — штука опасная Ж)
                                +1
                                это тестовое задание, и его цель — узнать, можете ли вы мыслить «широко» если ответ 20 — значит человек незнает про «гонки» если ответ — хз сколько, надо использовать семафоры — человек мыслит по шаблону
                                  +4
                                  >хз сколько, надо использовать семафоры — человек мыслит по шаблону
                                  Зачем впадать в рассуждалки когда есть простой и лаконичный ответ — Undefined behavior. Чтобы проверить логику человека есть совершенно другие вопросы…
                                    +22
                                    В данном случае шаблон не есть зло. В данном случае и нужно действовать по шаблону. Можно сколько угодно рассуждать о компиляторах и процессорах, поражая всех до глубины души, но программировать нужно с семафорами (мьютексами, критическими секциями).

                                    Лично я бы человека, ответившего «20» не взял бы на работе (ну вообще чувак не в теме).
                                    Но и людей, ответивших по вариантам 2 и 3 не взял бы тоже — они склонны к вот таким вот, узко-платформенным, вероятностным и ненадежным рассуждениям и будут писать такой же код. А человека, сказавшего «хз, это муть какая-то, надо написать вот так и вот так» — взял бы.
                                      0
                                      Собственно вариант 3 и есть «хз сколько». Только еще с пояснениями почему именно «хз».
                                0
                                Совершенно верно. Поэтому в задании и не было сказано о конкретных условиях. Оно больше рассчитано на проверку знаний о работе процессора и многопоточности. А также на возможность мыслить логически и, наверное даже, фантазировать (:
                                0
                                При 1280*1024 не виден правый край таблицы. Поправьте, пожалуйста (например, картинкой с превьюшкой).
                                  0
                                  Добавил для вас вариант таблицы в виде картинки. Ссылку найдёте сразу под таблицей. (У меня разрешение такое же, я просто уменьшил кегль.)
                                  +3
                                  Результатом такого кода должно быть увольнение написавшего.
                                    +2
                                    Это уже собеседование не программиста, а проджект-менеджера.
                                    –8
                                    static поля класса должны инициализироваться в первую очередь после загрузки класса.
                                    Если существует два потока, каждый из которых инкрементит статическую переменную на +10, то резт-т должен быть 20.
                                    Можете объяснить, в каком случае возможет вариант, отличный от 20?

                                    Да и вопрос сам по себе неграмотный. Не указан ни язык, ни платформа.
                                    Это точно было собеседование, а н есоревнование по риторике?
                                      +2
                                      Уже малёхо поднадоели тут на хабре эти задачи на параллельные потоки без объектов синхронизации. Уж топик пятый на моей памяти об этом. И комменты все по стандартному кругу: «так писать неверно...», «уволить программера...», «а я вот знаю как работает процессор и и на выходе может быть число N, а может и не быть» и т.д.
                                        0
                                        IMHO, область решения: 1..20.
                                        Атрибут volatile внес бы определенность.
                                          0
                                          volatile всего лишь не позволил бы компилятору соптимизировать цикл, однако не запретил бы одновременный доступ из двух нитей.
                                          +8
                                          42
                                            0
                                            Попробуйте для полноты картины написать код и скомпилить его в VS, Intel C++ и например gcc и потом объясните разницу :)
                                              +1
                                              при разных запусках одно и тогоже скомпилированного кода возможен разный вариант. автор просто указывает на очевидную проблему.
                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                –1
                                                Ваш пример про файлы совсем не в тему. Тут всё таки статическая переменная. По идее (в C#) использование статических переменных потокобезопасно. И я бы ответил 20
                                                  0
                                                  при чем тут статические? в дотнете нет гарантии атомарности инкремента.
                                                    –2
                                                    может я не догоняю. Ну допустим, один поток взял переменную, а второй получается будет ждать? Как неатомарность инкремента может повлиять на конечный результат? Пока один поток увеличивает на единицу, второй в это время тоже может увеличить на единицу? Ну и в итоге, как я понимаю, переменная увеличится на 2
                                                      0
                                                      3-й вариант в статье, инкремент — три операции: чтение, увеличение, запись. пока один увеличевает на единицу, второй увеличивает на единицу то-же, что и первый
                                                      0
                                                      хотя я понял о чем Вы:
                                                      т.е. ++ развернется в counter = counter + 1;
                                                      Получается, два потока возьмут одинаковое значение counter.
                                                        0
                                                        угу, сразу не заметил
                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                  0
                                                  нужно объяснить тому, кто принимает интервью, что в данном коде ошибка и результат, в общем случае, не предсказуем. думаю любому более/менее опытному системному программисту данный код режет глаз.
                                                    +3
                                                    Уже распечатал. Теперь куда идти на собеседование?
                                                      +1
                                                      > Какое значение будет содержать переменная counter по завершении работы обоих нитей и почему?

                                                      Правильно будет не «обоих нитей», а ОБЕИХ нитей…
                                                      –2
                                                      Забавное упражнение. Другое дело будет ли ситуация п3 возникать в реальности хотя когда либо.
                                                        0
                                                        Правильный вопрос — «когда такая ситуация возникать не будет?».
                                                          0
                                                          По закону Мёрфи — будет. См. ниже
                                                          0
                                                          Я бы наверно про себя подумал «что за фигня?» Но ответил бы скорее всего 20 :)
                                                            –2
                                                            семафоры решают…
                                                              +5
                                                              Чтобы не отпугнуть возможного «умного» собеседуемого от Вашей логики и подстегнуть к рассуждениям, я бы не стал так категорично формулировать задание:

                                                              > Какое значение будет содержать переменная counter по завершении работы обеих нитей и почему?

                                                              Вместо «будет» я бы использовал более нейтральное «может». Этим Вы задание не упростите (те, кто понимает проблему, грамотно ее ответят), но открываете дорогу к рассуждениями, а не к однозначному ответу на Ваш вопрос.
                                                              К сожалению, большинство известных мне тестов на разные квалификации — это закрытые тесты с определенным (одним) правильным вариантом ответа, и встречая такую задачу в резюме трудно отделить — где нужно проявить мышление, а где попытаться просто дать один ответ.
                                                                0
                                                                Достойное замечание, спасибо.
                                                                +9
                                                                #include <stdio.h>
                                                                #include <pthread.h>
                                                                
                                                                static int counter;
                                                                
                                                                void worker()
                                                                {
                                                                        int i;
                                                                        for (i = 1; i <= 10; i++)
                                                                                counter++;
                                                                }
                                                                
                                                                void* f(void *p)
                                                                {
                                                                        worker();
                                                                }
                                                                
                                                                int main()
                                                                {
                                                                        int i, r[22] = {};
                                                                
                                                                        for(i = 0; i < 1000000 && counter != 2; ++i)
                                                                        {
                                                                                pthread_t t1, t2;
                                                                                counter = 0;
                                                                                pthread_create(&t1, NULL, f, NULL);
                                                                                pthread_create(&t2, NULL, f, NULL);
                                                                                pthread_join(t1, NULL);
                                                                                pthread_join(t2, NULL);
                                                                                ++r[counter];
                                                                        }
                                                                        for(i = 0; i < 22; ++i)
                                                                                printf("%d:\t%d\n", i, r[i]);
                                                                }
                                                                


                                                                Цикл превратился в это:
                                                                worker:
                                                                .LFB0:
                                                                        .cfi_startproc
                                                                        pushq   %rbp
                                                                        .cfi_def_cfa_offset 16
                                                                        movq    %rsp, %rbp
                                                                        .cfi_offset 6, -16
                                                                        .cfi_def_cfa_register 6
                                                                        movl    $1, -4(%rbp)
                                                                        jmp     .L2
                                                                .L3:
                                                                        movl    counter(%rip), %eax
                                                                        addl    $1, %eax
                                                                        movl    %eax, counter(%rip)
                                                                        addl    $1, -4(%rbp)
                                                                .L2:
                                                                        cmpl    $10, -4(%rbp)
                                                                        jle     .L3
                                                                        leave
                                                                        ret
                                                                        .cfi_endproc
                                                                


                                                                Выводит:
                                                                0: 0
                                                                1: 0
                                                                2: 0
                                                                3: 0
                                                                4: 0
                                                                5: 0
                                                                6: 0
                                                                7: 0
                                                                8: 0
                                                                9: 0
                                                                10: 39
                                                                11: 3
                                                                12: 2
                                                                13: 2
                                                                14: 2
                                                                15: 3
                                                                16: 4
                                                                17: 3
                                                                18: 4
                                                                19: 9
                                                                20: 999929
                                                                21: 0
                                                                  0
                                                                  То есть чаще всего первая нить успевает выполниться до запуска второй.
                                                                  А если сделать счет не до 10, а до 10000. Или скажем ввести рандомные задержки на несколько миллисекунд после каждого инкремента.
                                                                    +3
                                                                    Добавил точную синхронизацию момента старта функции worker в потоках:

                                                                    static int together;
                                                                    
                                                                    void* f(void *p)
                                                                    {
                                                                            __sync_add_and_fetch(&together,1);
                                                                            while(__sync_add_and_fetch(&together,0) < 2);
                                                                            worker();
                                                                    }
                                                                    


                                                                    Это превратилось в такой код:

                                                                    f:
                                                                    .LFB1:
                                                                            .cfi_startproc
                                                                            pushq   %rbp
                                                                            .cfi_def_cfa_offset 16
                                                                            movq    %rsp, %rbp
                                                                            .cfi_offset 6, -16
                                                                            .cfi_def_cfa_register 6
                                                                            subq    $8, %rsp
                                                                            movq    %rdi, -8(%rbp)
                                                                            lock addl       $1, together(%rip)
                                                                    .L6:
                                                                            movl    $0, %edx
                                                                            movl    %edx, %eax
                                                                            lock xaddl      %eax, together(%rip)
                                                                            addl    %edx, %eax
                                                                            cmpl    $1, %eax
                                                                            jle     .L6
                                                                            movl    $0, %eax
                                                                            call    worker
                                                                            leave
                                                                            ret
                                                                            .cfi_endproc
                                                                    


                                                                    и замедлило работу ~ в 100 (!!!) раз.

                                                                    После укорачивания внешнего цикла в 100 раз результат такой:

                                                                    2:      1
                                                                    3:      1
                                                                    4:      1
                                                                    6:      4
                                                                    7:      1
                                                                    8:      9
                                                                    9:      5
                                                                    10:     7044
                                                                    11:     99
                                                                    12:     56
                                                                    13:     98
                                                                    14:     130
                                                                    15:     350
                                                                    16:     144
                                                                    17:     291
                                                                    18:     473
                                                                    19:     304
                                                                    20:     989
                                                                    


                                                                    Т.е. ответ: «да, 2 достижима на практике» (:
                                                                  +1
                                                                  Думаю, в итоге в русском языке закрепится термин «тред».
                                                                    0
                                                                    Условия задачи слишком неопределённы, чтобы дать обоснованный ответ. Надеюсь, интервьюером был не представитель отдела кадров, с которым на данную тему не поспоришь.
                                                                      0
                                                                      Почему же? Правильный ответ — «результат неопределен»
                                                                        0
                                                                        +1
                                                                          –6
                                                                          А кому нужен такой ответ? Программистов берут на работу решать конкретные задачи. То, как он решает оторванные от реальности задачи, ничего не скажет о нём как о практике.
                                                                            +1
                                                                            Чтобы знать как делать правильно, надо знать как не делать неправильно
                                                                              –1
                                                                              Выяснить как правильно и есть решение задачи. В данной задачи условий недостаточно, а следовательно нет критериев оценки правильности любого предложенного решения.

                                                                              Спорить тут не о чем, если хочется оставить последнее слово за собой, пожалуйста:
                                                                                0
                                                                                > Выяснить как правильно и есть решение задачи.

                                                                                Не верно. Задача была — выяснить у собеседуемого, что он знает как может себя вести некорректный код, представленный в задании.
                                                                                  0
                                                                                  Текст обсуждаемой задачи привёден в топике. Мотивы интервьюера не указаны. Моё высказывание относилось к решению задач вообще и являлось ответом на пространное замечание постом выше.

                                                                                  Мой исходный пост указывал на некорректность условий задачи из топика, как если бы на собеседовании предложили решить подобное уравнение:

                                                                                  Решите уравнение:

                                                                                  2? 3 = x
                                                                                  где? — какая-то операция

                                                                                  Чему будет равен x и почему?


                                                                                  Сразу остужу пыл — правильный ответ здесь один — «это не уравнение». Человек, взявшийся решать это «уравнение», очевидно считает себя телепатом и в таком случае ему лучше попробоваться в «Битве экстрасенсов» или в чём-то подобном.
                                                                                    0
                                                                                    > Мотивы интервьюера не указаны

                                                                                    В задаче стоял вопрос «почему», который, на мой взгляд, интерпретируется однозначно: интервьюер хотел предметных объяснений как будет работать приведенный код.

                                                                                    Так что с мотивами все в порядке.
                                                                              0
                                                                              Оценка поста негативная. Инвертируем утверждение из поста и получаем: «Программистов берут на работу кроссворды разгадывать.»

                                                                              До кризиса может и брали, сейчас нет.

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

                                                                        Самое читаемое