The story of two threads

At the interview in the IT company was asked to answer the following question.

Task. Given the code:

		 static int counter = 0;

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

')
The worker() procedure is run from two threads. What value will the counter variable contain when both threads are completed and why?

A bit of theory. Threads are parallel-executable tasks within a single process. The main difference between processes and threads is such that all threads of a process work in the common address space of their process.

I do not call threads as threads, so as not to confuse threads ( thread ) and data streams ( stream ).



Variant of answer No. 1. The variable counter will contain the number 20 - this is the most desirable result, but also the most incorrect answer.

The problem is that this code is not protected from out of sync. Each thread works independently of each other and does not suspect that the common data ( counter variable) can be changed by someone else. Therefore, the more correct answer is this: this is an insecure code and the value of the counter variable will be undefined .

Option number 2. Yet knowing the basics of the processor, OS and compiler, you can more accurately assume what result we get.

The worker() routine is fairly simple. Therefore, at the optimization stage, the compiler can expand the for-loop into such a structure:

	 counter + = 10; 

Now the code is so trivial that the first thread can manage to finish its execution even before the second thread starts. So we get the number 20.

Possible and such a case. The threads read the value of the counter variable (zero) from the RAM and put it into the processor register. Since each thread operates in its own processor context, each has its own independent set of registers. Thus, the first thread in its context will increase the value of the register from zero to ten and then bring the result back into memory. And then the second thread will do the same and rewrite that ten of its own. As a result, we get the number 10.

Values ​​of 10 and 20 are most likely in real practice , but this is not the complete answer.

Option number 3. Let's imagine a potentially real, but the most inefficient scheme of work. So each iteration of the cycle will repeat three atomic actions in the same way: reading the counter value in the processor register, increment of this register, writing the new value from the register back to memory. (I do not consider the implementation of the cycle itself, since it does not play any role.) Plus, the thread execution context switching will occur when we want it. Under such conditions, we can get a result from 2 to 20.

Now on the timeline in the form of a table, consider the possibility of obtaining a two. Step 0 is the original state. The operations "→ n ", " n +" and " n →" respectively represent reading from memory into a register, register increment and writing the register value to memory in the context of thread No. n . The “loop” line shows the iteration number. Changes to the values ​​in the current step are highlighted for better perception.

Step		0		one	2		3	four	five	...	27	28	29		thirty		31	32		33	34	35	...	57	58	59		60
Operation		-		→ 1	1+		→ 2	2+	2 →		→ 2	2+	2 →		1 →		→ 2	2+		→ 1	1+	1 →		→ 1	1+	1 →		2 →
Thread number 1	Register	-		0	one		one	one	one		one	one	one		one		one	one		one	2	2	...	9	ten	ten		ten
	Cycle	one		one	one		one	one	one		one	one	one		one		one	one		2	2	2		ten	ten	ten		ten
Thread number 2	Register	-		-	-		0	one	one	...	eight	9	9		9		one	2		2	2	2		2	2	2		2
	Cycle	one		one	one		one	one	one		9	9	9		9		ten	ten		ten	ten	ten		ten	ten	ten		ten
Memory		0		0	0		0	0	one		eight	eight	9		one		one	one		one	one	2		9	9	ten		2

(Added: at the request of the reader, here is the raster version of the table .)

Steps 1-2: the first thread enters the register zero and increments it by one. 3-29: control is transferred to the second thread, which also reads zero and performs nine complete iterations. 30: The first thread completes the first iteration of the loop and puts the counted unit into memory (by grinding the nine). 31—32: the second thread starts the last (tenth) iteration, reads and incriminates the unit. 33-59: the first thread completely performs the nine remaining iterations and finishes its work. 60: the second thread memorizes the counted deuce and finishes its work.

_________
NB: This is a cross-post from my blog. I reprinted because the audience at Habré is larger than that of my blog (: I think the material is interesting.