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

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

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

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