threads

[Marlene Miller]

class Test extends Thread {
   static int x;
   public void run() {
      m();
   }
   synchronized void m() {
      x++;
      System.out.println(x);
   }
   public static void main(String[] args) {
      new Test().start();
      new Test().start();
   }
}
What are possible output?
a. 11
b. 12
c. 21
d. 22

[Andres Gonzalez]

hmm... B?
Since "x" is static and m is synchronized, only 1 thread can access it at a time.
am I right?

[Andres Gonzalez]

I'm starting to get the feeling that all answers are possible.
stay tuned.

[Alton Hernandez]

class Test extends Thread {
   static int x;
   public void run() {
      m();
   }
   synchronized void m() {
      x++;
      System.out.println(x);
   }
   public static void main(String[] args) {
      new Test().start();
      new Test().start();
   }
}
What are possible output?
a. 11
b. 12
c. 21
d. 22

The answer is 'None of the Above'. A <CR> will appear between displays, like

b. 1
   2
c. 2
   1

But seriously, I think the answers are 12 and 22. Although the method m() is synchronized, there are still 2 instances running so the synchronized clause doesn't really matter. However, the variable being displayed is static so when one thread updates its value, the other thread will be affected.
My explanations are(assuming the output buffers are flushed immediately):
a. 11
- this is not possible because Java guarantees an atomic operations on primitive types. If the 2 threads tries to update the variable x at the same time(this is possible because there are 2 instances of Test), one still has to wait.
b. 12
- this is likely what most people would get when they run the program.
c. 21
- the value that any thread will display is the current value of x when print() is invoked. If 2 is printed first, then the next print() should also display 2.
d. 22
- it is possible that after the 1st thread increments x to 1, it is swapped out. The 2nd thread could then increment it to 2 and prints its value. When the 1st thread returns, the value it will now prints is 2 because that is its curent value.
Are my explanations correct?
[ September 11, 2003: Message edited by: Alton Hernandez ]

[Andres Gonzalez]

Good point Alton. I got really lost with that one.
What does our Java Guru Marlene have to say?

[Barkat Mardhani]

I think only possible output is:
12
Reasons:
1. There are two threads.
2. At most one thread can access one of the synchronized methods.
3. One of the thread will get to synchronized method first. The other will wait.
4. The first method will increase the variable and print it. That will be 1. remember other thread has to wait.
5. After first thread is done with synchronized method, second thread will enter that method. Increase its value to 2 and print it.
6. The run methods of both thread will return.
7. The end.

[Kashif Memon]

I m also agry with Alton Hernandez
If we call sleep() in m() after x++ then the result will be:
2
2

  
class Test extends Thread {
   static int x;
   public void run() {
      m();
   }
   synchronized void m() {
      x++;
      try{
       sleep(100L);
      }
      catch(InterruptedException e){}
    System.out.println(x);
       
   }
   public static void main(String[] args) {
      new Test().start();
      new Test().start();
   }
}

this code will give the result:
2
2
Regards,
Kashif Memon

[Andres Gonzalez]

Originally posted by Barkat Mardhani:
I think only possible output is:
12
Reasons:
1. There are two threads.
2. At most one thread can access one of the synchronized methods.
3. One of the thread will get to synchronized method first. The other will wait.
4. The first method will increase the variable and print it. That will be 1. remember other thread has to wait.
5. After first thread is done with synchronized method, second thread will enter that method. Increase its value to 2 and print it.
6. The run methods of both thread will return.
7. The end.

That was my first impression. But look at closely at the code.

[Barkat Mardhani]

That was my first impression. But look at closely at the code.

Please lead me. Because I can not see anything contradictory to my explanation....

[Kashif Memon]

Originally posted by Barkat Mardhani:
I think only possible output is:
12
Reasons:
1. There are two threads.
2. At most one thread can access one of the synchronized methods.
3. One of the thread will get to synchronized method first. The other will wait.
4. The first method will increase the variable and print it. That will be 1. remember other thread has to wait.
5. After first thread is done with synchronized method, second thread will enter that method. Increase its value to 2 and print it.
6. The run methods of both thread will return.
7. The end.

There r 2 objects created in main therefore, both threads can execute method m() simultaneously.
the possible output can be either b(12) or d(22).
Regards,
Kashif Memon

[Gopal Shah]

synchronized static void m() ...
If the method m() would have been static, then I think the answer (b)12, wud have been the only correct answer.

[Barkat Mardhani]

synchronized static void m() ...
If the method m() would have been static, then I think the answer (b)12, wud have been the only correct answer.

I do not think so. Still there two separate objects. Two separate locks.

[Kashif Memon]

Originally posted by Gopal Shah:
synchronized static void m() ...
If the method m() would have been static, then I think the answer (b)12, wud have been the only correct answer.

I think you are right because the same method will be available for all the objects of class Test.

class Test extends Thread {
   static int x;
   public void run() {
      m();
   }
   synchronized void m() {
      x++;
      System.out.println(x);
   }
   public static void main(String[] args) {
      new Test().start();
      new Test().start();
   }
}
  

In the above code, 2 threads are created and working on 2 different objects therefore, they have concurrent access on the method m() of class Test.
possible output for the above code is:
b. 12
d. 22
Have a look at the code below:

class Test implements Runnable {
   static int x;
   public void run() {
     m();
   }
   synchronized void m() {
      x++;
      System.out.println(x);
    }
 
   public static void main(String[] args) {
     Test test= new Test();
     Thread t1= new Thread(test); 
     Thread t2= new Thread(test);   
     t1.start();
     t2.start();
       
   }
}

guarenteed output is:
12
In the main method of class Test 2 threads are created and they both are working on the object "test" therefore, they can not access method m() of the class Test simultaneously.

plz help me understand it if I m wrong.
___________________
Kashif Memon

[Alton Hernandez]

Originally posted by Barkat Mardhani:

I do not think so. Still there two separate objects. Two separate locks.

But there is only one class. The lock is now on the class level(class locks and object locks are two different thing).
If you run this code, you will notice that there is only one output at the beginning. This is because the other thread is waiting for the 1st thread to complete.

class t15 extends Thread {
  public void run() {
     aStaticMethod();
  }
  public synchronized static void aStaticMethod() {
     System.out.println(currentThread().getName());
     try {
       sleep(10000);
     } catch (InterruptedException e) {}
  }
  public static void main(String [] args) {
     new t15().start();
     new t15().start();
  }
}

[RaviKumar Golagani]

I think the possible output is 12
Reasons:
1.There are 2 threads started simultaniously in the order the start() method called.
2.As everyone know only one thread accessing the synchronized method.
3.First Thread accesses the synchronized method and prints the value of x as 1.
4.After that control returns to run() from where the synchronized method called.
5.Now the second thread eventhough started earlier,the run() method is called now only, after the first thread releases the synchronized method..
6.Now second thread prints the value of x as 2, since it is an static variable.

Cheers,
Ravi

[Marlene Miller]

Wow, lots of ideas. Thank you Andres, Alton, Barkat, Kashif, Gopal, RaviKumar for thinking about my question and expressing your views so clearly and in detail.
I think the possible output is 11 or 12 or 21 or 22. Here is why.
1. Each thread acquires the lock of its own Thread object. The two threads are synchronizing on different locks. The locks are useless.

class Test extends Thread {
   public void run() { m(); }
   synchronized void m() {
      System.out.println(Thread.currentThread().getName() +
         " this.hashCode= " + this.hashCode() +
         " holdsLock(this)= " + Thread.holdsLock(this));
   }
   public static void main(String[] args) {
      new Test().start();
      new Test().start();
   }
}
Thread-1 this.hashCode= 28980466 holdsLock(this)= true
Thread-2 this.hashCode= 32124414 holdsLock(this)= true

All bets are off without synchronization. Well, that was the lesson to be reminded of and reinforced by the question.
2. Alton thought more deeply than I did. [Oops, print not println.] Now, I will expand on his ideas.

Thread-1   Thread-2    Class     Output
                       x == 0
x++                    x == 1
print(x)                           1
           x++         x == 2
           print(x)                2

Thread-1   Thread-2    Class     Output
                       x == 0
x++                    x == 1
           x++         x == 2
print(x)                           2
           print(x)                2

3. Evaluating x++ requires a read and a write. Read the value of x from the class data on the heap, write the sum of x+1 to the class data on the heap. Executing print(x) also requires a read and a write. Read the value of x again from the class data on the heap, print. (see footnote *)

Method void m()
   0 getstatic #3 <Field int x>                 // READ
   3 iconst_1
   4 iadd
   5 putstatic #3 <Field int x>                 // WRITE
   8 getstatic #4 <Field java.io.PrintStream out>
  11 getstatic #3 <Field int x>                 //READ
  14 invokevirtual #5 <Method void print(int)>  //WRITE
  17 return

Thread-1      Thread-2      Class       Output
Read 0                      x == 0            
              Read 0        x == 0
Write 1                     x == 1
              Write 1       x == 1
Read 1                      x == 1   
Print 1                                    1
              Read 1        x == 1
              Print 1                      1

Thread-1      Thread-2      Class       Output
Read 0                      x == 0
Write 1                     x == 1
Read 1                      x == 1
              Read 1        x == 1
              Write 2       x == 2
              Read 2        x == 2
              Print 2                     2
Print 1                                   1

It�s also possible each thread could read the value of x == 0 from main memory into its working memory and update working memory sometime before leaving the synchronized method. I suppose the result would be 11.
Thank you again to everyone. I appreciate your help very much. I hope it helped you as much as it helped me.
(footnote *) Doug Lea, Concurrent Programming In Java, 2.2 describes execution of ++n without locking in terms of the bytecodes for putfields and getfields.
[ September 12, 2003: Message edited by: Marlene Miller ]

[Deep Chand]

So, is the final answer is that all the values are possible i.e. 11, 12, 21, 22. OR am i wrong?
Deep

[Marlene Miller]

My answer is 11 or 12 or 21 or 22. Any of the four choices could occur.
I cannot prove this with a program. I cannot generate the output. But I verified the lack of synchronization with a similar program that uses two variables and some random Thread.yield()s in strategic places. And I checked the read/write business with Doug Lea's book.

[Andres Gonzalez]

Originally posted by Andres Gonzalez:
I'm starting to get the feeling that all answers are possible.
stay tuned.

nice feelings

[Gopal Shah]

I would like to add to this result.
If the variable x would have been like
static volatile int x;
Then Alton's explanation would have been correct, ie b (12) and d(22).

[Marlene Miller]

Volatile. Another interesting idea. Time to do some research.
2.2.7.4 Volatile, Concurrent Programming in Java, Doug Lea
In terms of atomicity, visibility, and ordering, declaring a field as volatile is nearly identical in effect to using a little fully synchronized class protecting only that field via get/set methods, as in:

final class Vfloat {
  private float value;
  final synchronized void set(float f) { value = f; }
  final synchronized float get() { return value; }
}

Declaring a field as volatile differs only in that no locking is involved. In particular, composite read/write operations such at the �++� operation on volatile variables are not performed atomically.

[Lalitha Chandran]

Hi all,
If we modify the program to insert sleep we get the output as 2 2
class Test extends Thread {
static int x;
public void run() {
m();
}
synchronized void m() {
x++;
try
{
Thread.currentThread().sleep(100);
}
catch(InterruptedException e)
{
}
System.out.println(x);
}
public static void main(String[] args) {
new Test().start();
new Test().start();
}
}
So indeed 2 2 is possible. I also agree with Marlene's explanation regarding the possbility of 1 1 being a possible output. But I don't think 2 1 can be an output. Because the mehod
System.out.println(x)
is atomic.
Lalitha Chandran

[Lalitha Chandran]

Hi all,
If we modify the program to insert sleep we get the output as 2 2
class Test extends Thread {
static int x;
public void run() {
m();
}
synchronized void m() {
x++;
try
{
Thread.currentThread().sleep(100);
}
catch(InterruptedException e)
{
}
System.out.println(x);
}
public static void main(String[] args) {
new Test().start();
new Test().start();
}
}
So indeed 2 2 is possible. I also agree with Marlene's explanation regarding the possbility of 1 1 being a possible output. But I don't think 2 1 can be an output. Because the mehod
System.out.println(x)
is atomic.
Lalitha Chandran

[Marlene Miller]

Hi Lalitha, thank you for showing us your experiment with the sleep method.
In my opinion System.out.println(x) is not atomic. Here are the byte codes. The first instruction loads the reference to the PrintStream object from memory. The second instruction loads the value of x from memory. Then the print method is invoked. The scheduler could swap out Thread-1 after value of x is loaded from memory and before the print method is invoked.

System.out.print(x);
//
   8 getstatic #4 <Field java.io.PrintStream out>
  11 getstatic #3 <Field int x>
  14 invokevirtual #5 <Method void print(int)>

[Alton Hernandez]

Originally posted by Marlene Miller:

In my opinion System.out.println(x) is not atomic. Here are the byte codes. The first instruction loads the reference to the PrintStream object from memory.

I've been thinking about this for a few days. I was wondering what the word 'operations' means from this statement taken from the book "Inside the Java Virtual Machine" by Bill Venner.

..one rule states that all operations on primitive types, except in some case long and doubles, are atomic.

Does the word operation pertains to 1 opcode? Or does it mean one statement(which can be made up of a number of opcodes)? My first interpretation was the latter.
Any thoughts?

[Barkat Mardhani]

Posted by Alton

quote:
--------------------------------------------------------------------------------
Originally posted by Barkat Mardhani:
I do not think so. Still there two separate objects. Two separate locks.

--------------------------------------------------------------------------------
But there is only one class. The lock is now on the class level(class locks and object locks are two different thing).
If you run this code, you will notice that there is only one output at the beginning. This is because the other thread is waiting for the 1st thread to complete.

code:
--------------------------------------------------------------------------------
class t15 extends Thread { public void run() { aStaticMethod(); } public synchronized static void aStaticMethod() { System.out.println(currentThread().getName()); try { sleep(10000); } catch (InterruptedException e) {} } public static void main(String [] args) { new t15().start(); new t15().start(); }}

Thanks Alton. I was not aware of it.

[Marlene Miller]

Does the word operation pertains to 1 opcode? Or does it mean one statement(which can be made up of a number of opcodes)?

Hi Alton, I am going to quote from Doug Lea and you can decide for yourself.
1. Concurrent Programming in Java, Doug Lea, Section 2.2.7 The Java Memory Model
Atomicity. Which instruction must have indivisible effects. For purposes of the model, these rules need to be stated only for simple reads and writes of memory cells representing fields -- instance and static variables, also including array elements, but not including local variables inside methods.
2. Concurrent Programming in Java, Doug Lea, Subsection 2.2.7.1 Atomicity
Access and updates to the memory cells corresponding to field of any type except long or double are guaranteed to be atomic. This includes fields serving as references to other objects. Additionally, atomicity extends to volatile long and double.
Atomicity guarantees ensure that when a non-long/double field is used in an expression, you will obtain either its initial value or some value that was written by some thread, but not some jumble of bits resulting from two or more threads both trying to write values at the same time.

[Marlene Miller]

Alton - in the world of processes (instead of threads)...
1. The famous atomic instruction is TLS (Test and Set Lock) used to coordinate access to shared memory.
TSL RX, LOCK
It reads the contents of the memory word LOCK into register RX and then stores a nonzero value at the memory address LOCK. The operations of reading the word and storing into it are guaranteed to be indivisible--no other processor can access the memory word until the instruction is finished. The CPU executing the TSL instruction locks the memory bus to prohibit other CPUs from accessing memory until done.
(credits - Tanenbaum, Modern Operating Systems)
2. Atomic means indivisible, so an atomic swap means the processor can both read a location and set it in the same bus operation, preventing any other processor or I/O device from reading or writing memory until the swap completes.
(credits - Paterson & Hennessey, Computer Organization & Design)
In my opinion, in the world of Java threads, atomic does not mean the CPU locks the memory bus. It is at a higher level - the so-called actions read, write, lock and unlock of JLS 17.1. But certainly at a lower level than Java statements.
[ September 15, 2003: Message edited by: Marlene Miller ]

[Jose Botella]

Unless a method is declared synchronized cannot be called atomic: there are potentially a huge amount of bytecodes waiting to be executed inside the body of the method.
Atomicity means that the content of a variable cannot be corrupted by several threads accesing it. That is, the content of the variable will be one of the values the threads are writing, not a mix of them.

[Anupam Sinha]

Here are a few codes. I wonder would it be possible to have the output as

2
1

because the println(int) method is synchronized on this.

println(int)
    public void println(int x) {
synchronized (this) {
    print(x);
    newLine();
}
    }
print(int)
public void print(int i) {
write(String.valueOf(i));
    }

write(String)
private void write(String s) {
try {
    synchronized (this) {
ensureOpen();
textOut.write(s);
textOut.flushBuffer();
charOut.flushBuffer();
if (autoFlush && (s.indexOf('\n') >= 0))
    out.flush();
    }
}
catch (InterruptedIOException x) {
    Thread.currentThread().interrupt();
}
catch (IOException x) {
    trouble = true;
}
    }

[Jose Botella]

It seems that the goal of the synchronization of println's body is to avoid having the printing of end of line mixed with the printing of other thread.
Anupam, dou you mean that because print(x) occurs in a synchronized block the executing thread should read the value of x from memory?
You are right. However this does not mean that the previous thread had written the value of 2 to memory, even if it printed 2. This implies that 21 is possible.
[ September 15, 2003: Message edited by: Jose Botella ]
[ September 15, 2003: Message edited by: Jose Botella ]
[ September 16, 2003: Message edited by: Jose Botella ]