На собеседовании в ИТ-компании было предложено ответить на следующий вопрос.
Задача. Дано такой код:
Процедуру
Немного теории. Нити — это параллельно-исполняемые задачи в пределах одного процесса. Основное различие между процессами и нитями такое, что все нити одного процесса работают в общем адресном пространстве своего процесса.
Я не называю нити потоками, что бы не путать потоки выполнения (thread) и потоки данных (stream).
Вариант ответа № 1. Переменная
Проблема в том, что данный код никак не защищён от рассинхронизации. Каждая нить работает независимо друг от друга и не подозревает, что общие данные (переменная
Вариант № 2. Всё же зная основы работы процессора, ОС и компилятора можно более точно предположить какой результат мы получим.
Подпрограмма
Теперь код настолько тривиален, что первая нить может успеть закончить его выполнение ещё до того как запустится вторая нить. Таким образом мы получим число 20.
Возможен и такой случай. Нити прочтут из оперативной памяти значение переменной
Значения 10 и 20 наиболее вероятны в реальной практике, но и это ещё не полный ответ.
Вариант № 3. Давайте представим потенциально реальную, но максимально неэффективную схему работы. Так каждая итерация цикла будет одинаково повторять три атомарных действия: чтение значения
Теперь на временной шкале в виде таблицы рассмотрим возможность получения двойки. Шаг 0 — изначальное состояние. Операции «→n», «n+» и «n→» соответственно представляют чтение из памяти в регистр, инкремент регистра и запись значения регистра в память в контексте нити № n. Строка «цикл» показывает номер итерации. Изменения значений на текущем шаге выделены для лучшего восприятия.
(Добавлено: по просьбе читателя вот вариант таблицы растровым изображением.)
Шаги 1—2: первая нить заносит в регистр ноль и увеличивает его на единицу. 3—29: управление передаётся второй нити, которая тоже считывает ноль и выполняет девять полных итераций. 30: первая нить завершает первую итерацию цикла и заносит посчитанную единицу в память (перетирая девятку). 31—32: вторая нить начинает последнюю (десятую) итерацию, читает и инкриминирует единицу. 33—59: первая нить полностью выполняет девять оставшихся итераций и заканчивает свою работу. 60: вторая нить записывает в память посчитанную двойку и заканчивает свою работу.
_________
NB: это кросс-публикация с моего блога. Перепечатал, потому что на Хабре аудитория больше, чем у моего блога (: а материал, думаю, интересен.
Задача. Дано такой код:
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: это кросс-публикация с моего блога. Перепечатал, потому что на Хабре аудитория больше, чем у моего блога (: а материал, думаю, интересен.