The problem is from question paper at Stanford. The description of it is as follows:
Suppose two threads execute the following C code concurrently, accessing shared variables a, b, and c:
Initialization
int a = 4;
int b = 0;
int c = 0;
Thread 1:
if (a < 0) {
c = b - a;
} else {
c = b + a;
}
Thread 2:
b = 10;
a = -3
What are the possible values for c
after both threads complete? You can assume that reads and
writes of the variables are atomic, and that the order of statements within each thread is preserved in the code generated by the C compiler.
Answer : 4,7,14,13,-3
I understood the first four outputs as follows, but I'm not able to understand how the output -3 can occur given that order of statements within the thread is preserved.
4: Execute thread 1 completely, then execute thread 2.
7: Interrupt thread 1 before c = b + a
, and then execute thread 2, followed by executing thread 1 again.
14: Execute thread 2 till b = 10
is done, then interrupt it, and execute thread 1 completely.
13: Execute thread 2 completely, then thread 1.
Now I'm stuck on how to obtain -3 as a final value of c
? -3 is only possible when b=0
, and a=-3
, and thread 1 starts its execution from c = b + a
. I don't see -3 to be possible in any other case. But as mentioned in question, order of statements is maintained, so the value of a can not be -3, unless we change the value of b to 10.
Can someone explain how the output -3 is possible in this case?
In the same multithreaded process in a shared-memory multiprocessor environment, each thread in the process can run concurrently on a separate processor, resulting in parallel execution, which is true simultaneous execution.
On a single core microprocessor (uP), it is possible to run multiple threads, but not in parallel. Although conceptually the threads are often said to run at the same time, they are actually running consecutively in time slices allocated and controlled by the operating system.
Even though the variable is not currently being written to, previous writes to the variable may not yet be visible to all threads. This means two threads can read the same value and get different results creating a race condition.
A race condition occurs when two threads access a shared variable at the same time. The first thread reads the variable, and the second thread reads the same value from the variable.
You can get -3
as follows:
a < 0
, which is false. This takes you to the else condition. Read the value of b
, which is 0
.a
is now -3
.a
, which is -3
. Then, add and assign -3
to c
.If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With