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

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

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

	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. Строка «цикл» показывает номер итерации. Изменения значений на текущем шаге выделены для лучшего восприятия.

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