Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Possible value of Variable when given two threads are running parallely?

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?

like image 492
Ruchit Patel Avatar asked Feb 26 '20 21:02

Ruchit Patel


People also ask

What can occur if two threads are executing at the same time?

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.

Do threads run parallely?

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.

Can two threads read the same variable?

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.

When two threads access a shared variable at the same time it is called?

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.


1 Answers

You can get -3 as follows:

  1. In thread 1, check a < 0, which is false. This takes you to the else condition. Read the value of b, which is 0.
  2. Switch to thread 2, execute it completely. a is now -3.
  3. Switch back to thread 1, read a, which is -3. Then, add and assign -3 to c.
like image 200
GoodDeeds Avatar answered Oct 19 '22 02:10

GoodDeeds