CODEWITHSUNDEEP
multithreadingoperating-system
Suzana
Suzana

Reputation: 67

thread in single processor system

these two thread run concurrently in a shared memory (all variables are shared between the two threads):
Thread A 

for (i=0; i<5; i++) {
  x = x + 1;
}

Thread B

for (j=0; j<5; j++) {
   x = x + 2;
}

Assume a single-processor system
a- Give a concise proof why x≤15 when both threads have completed.
b- Suppose we replace x = x+2 in Thread B with x = x-1 what will be the value of X.

I do not understand this question and I google it and I found answer but I can not get it I wanna some explanation for it.

Upvotes: 0

Views: 321

Answers (2)

Grijesh Chauhan
Grijesh Chauhan

Reputation: 58271

a) Instruction x=x+1 is not single instruction at low level and It consist of sequence of read x, then add 1 to x and then update x's memory . Hence it may be happen two threads read same value of x.

Suppose, if two threads read same value of x variable then update x and write back to x this cause x < 15.

b) For the same reason value of x may be between 0 to 5 if your instruction is x=x-1.

Try this you will learn more!
compile your c code with -S option it will create a compiled assemble code for your program. Then you can understand x = x + 1 is not a single instruction. And switching between threads can be possible before completion of x = x + 1 instruction hence its not atomic.

Upvotes: 2

Kirk Backus
Kirk Backus

Reputation: 4866

If the threading works perfectly, the highest value 'x' can have is 15. This all depends on the scheduler of the operating system.

Note that I am assuming the initial value of x is 0! Lets say that Thread A and Thread B are serialized. The value of x after Thread A is complete will be 5.

 i | x
-------
 0 | 1
 1 | 2
 2 | 3
 3 | 4
 4 | 5

The value of x going into Thread B will be 5, resulting x to be a final value of 15

 i | x
-------
 0 | 7
 1 | 9
 2 | 11
 3 | 13
 4 | 15

Now, things typically don't happen this way, and a thread will both read an initial value of x and do their addition, then write their modified value back into memory. The following can happen.

Thread A reads the value 'x' as 0
Thread B reads the value 'x' as 0
Thread A adds 1 to x making its local copy of x, 1
Thread B adds 2 to x making its local copy of x, 2
Thread A writes its modified value of x as 1
Thread B writes its modified value of x as 2 (overwriting Thread A's modification)

Therefore, x will be no more than 15, but depending on the scheduler, will be less!

Upvotes: 4

Related Questions