VMWare Inc Interview Question
Member Technical StaffsCountry: United States
Interview Type: Phone Interview
If the var is 0 initially, min value can be 2 and max can be 200.
To answer Huwanda's question, here is what can happen to get the value of 2.
P1 and P2 both read var = 0 in their registers. P1 gets CPU, increments 99 times, so var = 99, cached value of var = 99, however, P2 register has this value = 0.
P1 gets context switched out and P2 gets CPU. Because P2 has already a copy of var in its register, it will increment it to make it 1. When P1 writes it in its cache, cache overwrites P1's value. Now cache contains var = 1.
P2 gets context switched out and P1 gets CPU. P1 reads var = 1 in its register from cache and gets context switched out.
P2 gets CPU, copies var in its register and increments it 100 times making var = 100 in cache. However, var value already copied in P1's register = 1.
P2 finishes, P1 gets CPU, already has var = 1 in its registers (if it reads from cache, it will read 100, but since it's already copied in register, it won''t consult cache). P1 increments var to 2, overwrites the value in the cache which was 100 before. Final value = 2.
Cache can be replaced with memory (RAM) in above analysis, because they are always kept coherent in hardware architecture. However, variables copied in registers can do the damage if memory locations are not properly synchronized.
@Hariharan. Do you mean
say initial value of var be var_ini
P1 copies var to reg_p1 (swap to P2)
P2 copies var to reg_p2 (swap to P1)
The copy instruction of P1 already got executed (here does not matter)
P1 increments reg_p1
stores it in var
does the following 3 steps 98 times
load var to reg_p1
P1 increments reg_p1
stores it in var
So the value is in var is var_ini + 99 (swap to P2)
The copy instruction of P2 already got executed
P2 increments reg_p2
stores it in var
So the value is in var is var_ini + 1 (swap to P1)
P1 comes and loads var to reg_p1
reg_p1 is now var_ini+1 (swap to P2)
Now P2 comes and does the following 3 steps 99 times
load var to reg_p2
increments reg_p2
stores it in var
Now P2 completed its turn, and P1 will get executed
The copy instruction of P1 already got executed and reg_p1 is now var_int+1
P1 increments reg_p1
stores it in var
now the var is var_ini+2
Now P1 also completed its turn.
And the final value of var is var_ini+2
I think it will depend on how may CPU processors are there. With single process min and mix both will be 200. with dual min will be 100.
Even in single processor there could be time sharing.
eg.
Threads T1 reads the number say "1". times up before it could actually increase the number. T1 waits for the next time slot.
Thread T2 reads the number "1". and increases the number and assign the new value to "2"
T1 gets the time slot. T1 had read the value to be 1. so assign the new value to be 2.
in this operation the value of the variable will be increase by just 1 even if 2 threads are working simultaneously.
Thus the minimum possible value in the will be 100 and max value will be 200
But as 2 threads belong to same program, program cannot be shared into 2 CPUs. Hence, min and max in any case will be 200.
public class TwoThreadAdding100Item {
public static void main(String args[]) {
new Thread(new MyRunnable(), "Thread 1").start();
new Thread(new MyRunnable(), "Thread 2").start();
}
static class MyRunnable implements Runnable {
//volatile int i = 20; //Min = 120 and Max = 120
//static int i = 20; //Min = 120 and Max = 220
int i = 20; //Min = 120 and Max = 120
@Override
public void run() {
for (int j = 0; j < 100; j++) {
i++;
}
System.out.println(i);
}
}
}
Max is 120 because each thread has their own copy of i. I have modified the code a bit and now Max = 220
public class TwoThreadAdding100Item {
public static void main(String args[]) {
Incrementor in = new Incrementor(20);
new Thread(new MyRunnable(in), "Thread 1").start();
new Thread(new MyRunnable(in), "Thread 2").start();
}
static class MyRunnable implements Runnable {
Incrementor in;
public MyRunnable(Incrementor in) {
this.in=in;
}
@Override
public void run()
{
System.out.println(Thread.currentThread().getName() + " : " + in.getvalue());
for (int j = 0; j < 100; j++) {
in.increment();
}
System.out.println(Thread.currentThread().getName() + " : " + in.getvalue());
}
}
static class Incrementor
{
Integer i ;
Incrementor(Integer i)
{
this.i=i;
}
public void increment()
{
i++;
}
public int getvalue()
{
return i;
}
}
}
Well answer really depends upon how compiler generates code, what CPU is executing code and how many CPUs are installed in host computer. Lets assume loop generates the following assembly code ( I generated through VS 2012) and if initial value of shared variable is 0 then it is not hard to prove that Min value can be 0 and Max value can be 200 (though it is highly unlikely you ever see these values)
for( int i = 0 ; i < 2 ; i++ )
012643DE mov dword ptr [ebp-8],0
012643E5 jmp odd_thread_cs+30h (012643F0h)
012643E7 mov eax,dword ptr [ebp-8]
012643EA add eax,1
012643ED mov dword ptr [ebp-8],eax
012643F0 cmp dword ptr [ebp-8],2
012643F4 jge odd_thread_cs+45h (01264405h)
{
shared_value++;
012643F6 mov eax,dword ptr ds:[0126F21Ch]
012643FB add eax,1
012643FE mov dword ptr ds:[0126F21Ch],eax
}
01264403 jmp odd_thread_cs+27h (012643E7h)
This questioj involves non-constant priorities of threads P1 and P2 - at beginning P1 has priority over P2 and later P2 has priority over P1, and in reality thread priorities will stay constant. So if P1 has priority over P2 then P2 will be not able to enter in the middle of running of P1. So maximal value is 200 (sequential run), but minimal value is 100 (thread with lower priority read initial value, than interrupted by thread with higher priority, than restored and overwrites value of thread with higher priority by value of 100).
max value: var + 200 (it is simple. so explaining only the below)
- Hariharan May 11, 2013min value: var + 2
P1 & P2 copy var
P1 increments 99 times. so var becomes var + 99
P2 increments once. so var becomes var + 1
P1 copies var (value is var + 1)
P2 increments 99 times. so var becomes var + 100
P1 increments once. so var becomes var + 2