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

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

		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: это кросс-публикация с моего блога. Перепечатал, потому что на Хабре аудитория больше, чем у моего блога (: а материал, думаю, интересен.