My latch experiment

[Andrew Cane]

public class MyLatch {

	private final Object lock = new Object();
	private int count;
	
	public MyLatch(int nThreads){
		
		count = nThreads;
		
	}
	
	public void awaitZero() throws InterruptedException{
		
		synchronized (lock) {
			
			System.out.println("inside awaitzero");
			while(count > 0) lock.wait();
			
		}
		
	}
	
	public void countDown(int id){
		
		synchronized (lock) {
			
			System.out.println("inside countDown " + id);
			if(--count <= 0) lock.notifyAll();
			
		}
		
	}
	
}

public class ChildThread extends Thread {

	private MyLatch myLatch;
	private int id;
	
	public ChildThread(MyLatch latch, int id){
		
		myLatch = latch;
		this.id = id;
		
	}
	
	@Override
	public void run(){
		
		try {
			
			System.out.println(id);
			
		} finally {
			
			myLatch.countDown(id);
			
		}
		
	}
	
}

public class Main {

	public static void main(String[] args) throws InterruptedException{
		
		MyLatch latch = new MyLatch(5);
		
		for(int i=0 ; i < 5 ; i++){
			
			Thread j = new ChildThread(latch, i);
			j.start();
			
		}
		
		latch.awaitZero();
		
		new Thread() {
			
			@Override
			public void run() {

				System.out.println("last");
				
			}
		}.start();
		
	}
	
}

This is the output:
0
inside countDown 0
2
inside countDown 2
inside awaitzero
4
inside countDown 4
1
inside countDown 1
3
inside countDown 3
last

The following are my assumptions. please verify if they're correct or not:

1. System.out.println WON'T mess up with synchronization. if it will, what's the recommended way to observe the program flow when testing synchronization?
2. The thread that prints "last" is guaranteed to always be executed AFTER the previous 5 threads finished executing.
3. It is always guaranteed that countdown() in each thread will always be called AFTER all the code inside try block executes. This is because of the try-finally construct, and has nothing to do with synchronization. However it's possible for JVM to reorder the lines of code inside the try block (when there are multiple lines of code) so long it doesn't violate happens-before relationship of said lines of code
4. There are total 7 threads here : main, 5 initiated inside for loop, and the thread that prints "last".
5. Control may switch to another even when the thread hasn't finished executing a looping construct (looping construct in itself is not atomic). This is proven by the call of thread 1 and 3 (printing 0 and 2 respectively) which then followed by a call to awaitzero() in main.
Thanks

[Steve Luke]

Andrew Cane wrote:1. System.out.println WON'T mess up with synchronization. if it will, what's the recommended way to observe the program flow when testing synchronization?

It won't 'mess up' synchronization, but System.out.printlns must follow the same rules as all other calls regarding synchronization. That means they must be in synchronized blocks to be observed properly. So the ones inside the latch are okay, but the ones inside the Thread subclass may show up out of order relative to the ones in the latch, or with each other.

2. The thread that prints "last" is guaranteed to always be executed AFTER the previous 5 threads finished executing.

Correct (at least as written above).

3. It is always guaranteed that countdown() in each thread will always be called AFTER all the code inside try block executes. This is because of the try-finally construct, and has nothing to do with synchronization. However it's possible for JVM to reorder the lines of code inside the try block (when there are multiple lines of code) so long it doesn't violate happens-before relationship of said lines of code

That depends on perspective. From inside the same thread - yes, the countdown() will be called after the try, because in a single-threaded model the observable programming order must be maintained. From the perspective of another thread, there is no such guarantee.

4. There are total 7 threads here : main, 5 initiated inside for loop, and the thread that prints "last".

The ones under your control, yes. There are likely more actually running (garbage collector, perhaps others as well that the JVM creates and uses).

5. Control may switch to another even when the thread hasn't finished executing a looping construct (looping construct in itself is not atomic). This is proven by the call of thread 1 and 3 (printing 0 and 2 respectively) which then followed by a call to awaitzero() in main.

You shouldn't really consider 'control switching' as the only means of parallelism. In a multi core processor it is possible that all the threads are running in parallel without need for thread context switches. In this situation a working thread which reaches a wait() or synchronized block it can't get the lock for will simply block, and no context switch will be necessary (and the main thread where the loop runs will continue without any need for switching). Switching is really only needed under architectures which do not allow Java threads to run on different processors, or when there are more actively running threads than there are processors available. Rather than thinking about control switching (which is one method of concurrency) and true parallelism (another form of concurrency) just think about concurrency in the general sense.

So in terms of concurrency the question would be: "5. A thread may run concurrently to another thread even when that thread hasn't finished executing a looping construct..." And the answer is yes, that is correct. Once a thread is started it will begin to run independently and concurrent to all other threads.

[Andrew Cane]

For the sake of clarity, I'll be using a single-core machine when executing my programs, so the concurrency behavior can be observed properly. so every post from this moment on will always assume that the codes are run on single-core machine (to observe control switch).

Steve Luke wrote:
That depends on perspective. From inside the same thread - yes, the countdown() will be called after the try, because in a single-threaded model the observable programming order must be maintained. From the perspective of another thread, there is no such guarantee.

this is where I want to test my assumption on control switching. so it's possible for the control to switch to another thread on any moment? the JVM guarantees that it will finish executing each line of code on one thread before switching control to another thread. so, for example, if thread 1 encounters a method call which has 20 lines of code, does this mean JVM will ALWAYS execute those 20 lines before switching to another thread, or it's possible for JVM to switch to another thread in between those 20 lines?

I wish to refresh my understanding about reordering:

x=5;
System.out.println(x);
System.out.println("abc");

in the code above, here are my assumptions:
1. x assignment and printing of x value has a happens-before relationship, so JVM will NEVER change the order of line 1 and 2
2. it's possible for JVM to put line 3 as the first line or slip it between x=5; and System.out.println(x); This is because the printing of "abc" has no happens-before relationship with any other lines of code

thanks

[Steve Luke]

Andrew Cane wrote:For the sake of clarity, I'll be using a single-core machine when executing my programs, so the concurrency behavior can be observed properly. so every post from this moment on will always assume that the codes are run on single-core machine (to observe control switch).

I refuse to accept that assumption or limitation. Correct concurrency is observable in multi core true parallelism and your application should be ignorant of what type it is run on. You should not consider, question, or assume either type of concurrency. Nor should you spend too much time trying to figure out how one specific type works.

Steve Luke wrote:
That depends on perspective. From inside the same thread - yes, the countdown() will be called after the try, because in a single-threaded model the observable programming order must be maintained. From the perspective of another thread, there is no such guarantee.

this is where I want to test my assumption on control switching. so it's possible for the control to switch to another thread on any moment?

True

the JVM guarantees that it will finish executing each line of code on one thread before switching control to another thread.

False. The context switch can happen mid 'line' as well. For example i++; is a complex statement where a value is incremented and re-assigned to the same variable. A context switch can happen between the increment and the assignment.

so, for example, if thread 1 encounters a method call which has 20 lines of code, does this mean JVM will ALWAYS execute those 20 lines before switching to another thread, or it's possible for JVM to switch to another thread in between those 20 lines?

Possible to switch at any point in those 20 lines.

I wish to refresh my understanding about reordering:

x=5;
System.out.println(x);
System.out.println("abc");

in the code above, here are my assumptions:
1. x assignment and printing of x value has a happens-before relationship, so JVM will NEVER change the order of line 1 and 2

In a single thread, this behavior is true. But a different thread could see that '5' was printed to the output stream, but when it inspects the variable x it could see its previous value. Happens-before is a pretty strict statement in regards to the Java Memory Model. It applies to multi-threaded code. In your example, the first two statements are guaranteed to run in programmatic order (in order as written in a single thread's view) but do not have happens-before relationship because there is no apparent synchronization border to enforce it.

2. it's possible for JVM to put line 3 as the first line or slip it between x=5; and System.out.println(x); This is because the printing of "abc" has no happens-before relationship with any other lines of code

I don't think so. In re-ordering a single thread must not be able to observe a difference in the reordering. Since both the System.out.println(x) and System.out.println("abc") both affect the same resource (the output stream) the two statements can not be re-ordered since the single thread would be able to observe "abc" being printed in the output stream before observing "5" being printed.

Reordering is most likely to happen when you have resources that are independent, and so re-ordering is unobservable in a single thread:

a = 3;

account = "Name " + a;
b = 8;
c = b * 7;
serialNumber = "1-405-" + b + "-" + c;

This could easily be re-ordered to:

b = 8;
a = 3;
c = b * 7;
serialNumber = "1-405-" + b + "-" + c;
account = "Name " + a;

One of the best things to come from so much attention on Singletons is long discussions on Reordering. If you search google for Java Double Checked Locking broken you are sure to get some examples of when an how reordering are likely to happen. You can also read the Java Memory Model for examples and detailed explanation

[Andrew Cane]

Now, I'm having doubts about my understanding on reordering. in oracle docs about memory model you gave me, could you explain how it's possible for r2 == 2 and r1 == 1 might occur (table 17.1 under section 17.4)? and again, is this result possible only in multi-core machine, or is it also possible in single-core machine? but then again, I don't see how it's possible even if the code is run on multi-core machine.
thanks

[Steve Luke]

Here is the example:

Consider, for example, the example program traces shown in Table 17.1. This program uses local variables r1 and r2 and shared variables A and B. Initially, A == B == 0.

Table 17.1. Surprising results caused by statement reordering - original code

Thread 1 -------- Thread 2
1: r2 = A; ------ 3: r1 = B;
2: B = 1; ------- 4: A = 2;
It may appear that the result r2 == 2 and r1 == 1 is impossible.

Remember I said that reordering is likely to happen in a thread when you have independent resources that don't interact? In this scenario, in thread 1, A and r2 are dependent and related by assignment, but B is independent of both of those. So it is possible that the following reorder could occur:
Thread 1 -------- Thread 2
1: B = 1; ------- 3: r1 = B;
2: r2 = A; ------ 4: A = 2;

With the same resoning, thread 2 could be reorder so the two threads look like this:
Thread 1 -------- Thread 2
1: B = 1; ------- 3: A = 2;
2: r2 = A; ------ 4: r1 = B;

Since execution can happen in any order between the threads, it is possible that the order of operation becomes:
3 -> 1 -> 2-> 4
Since A = 2 happened before r2 = A then r2 would have a value of 2. And because B = 1 happened before r1 = B r1 would have a value of 1.

As I said before, this is a general concurrency issue, and is not specific to context switching or true parallelism.

[Andrew Cane]

okay, I see. I have some questions:
1. what are the criteria that JVM follows when reordering lines of code?
2. basically, reordering happens per thread?
3. let's say there are multiple threads that run the exact same method, is JVM permitted to perform different reordering on those threads (each thread may have different reordering of lines of code)? or JVM must reorder the lines of code exactly the same way for those threads since they're invoking the same methods?
4. what about the control switching you mentioned in your post?
5. what's true parallelism you mentioned? it's only possible in multi-core machine right? in single-core, only pseudo-parallelism is possible (where execution keeps switching from one thread to another and creating illusion of parallelism, when in truth, only one thread is running at any time)?
thanks

[Steve Luke]

Andrew Cane wrote:okay, I see. I have some questions:
1. what are the criteria that JVM follows when reordering lines of code?

Undefined. The only defined criteria is that it is allowed and that the mechanics of the reordering can not be visible in a single thread scope. Add to that some restrictions on crossing synchronization barriers. Otherwise it is up to the implementation to determine the criteria in which reordering may haeppen.

2. basically, reordering happens per thread?
3. let's say there are multiple threads that run the exact same method, is JVM permitted to perform different reordering on those threads (each thread may have different reordering of lines of code)? or JVM must reorder the lines of code exactly the same way for those threads since they're invoking the same methods?

That I am not sure. In a naive instance, I would say reordering is done on the code, and so will happen once and be the same for all threads as they reach the method. But it could be the stack frames which are reordered (I guess) and so perhaps reordering could be optimized per thread. I would guess this isn't the case, though.

4. what about the control switching you mentioned in your post?

What question do you have about it?

5. what's true parallelism you mentioned? it's only possible in multi-core machine right? in single-core, only pseudo-parallelism is possible (where execution keeps switching from one thread to another and creating illusion of parallelism, when in truth, only one thread is running at any time)?

Right. True parallelism would be any means by which the threads could run simultaneously - usually multiple cores on a computer (but also in some scenarios parallelism can be achieved by distributing the work to multiple computers). The sibling of true parallelism is the thread context switching which puts one thread on hold to give another thread a chance to run. In a real world scenario concurrency is a mixture of both - you will have multiple threads running in parallel, but sometimes more threads than available processors will be running and so context switching will begin to give all threads some bit of CPU time.