Deadlock on CertPal question

[Ariel Chelsau]

Hi,

I've encountered a question on certpal.com site at the exam from all topics no. 3 for Java 6. The question number is 34.
Here's the code snippet:

import java.util.ArrayList;
import java.util.List;

public class Toza extends Thread {
	static int rabbit = 0;
	static boolean shifter = false;
	Toza toza;

	public Toza() {
	}

	public Toza(Toza q) {
		toza = q;
	}

	public static void main(String[] args) throws Exception {
		Toza tozax = new Toza();
		List<Toza> stinger = new ArrayList<Toza>();
		Toza toza = new Toza(tozax);
		stinger.add(toza);
		toza = new Toza(tozax);
		stinger.add(toza);
		toza = new Toza(tozax);
		stinger.add(toza);
		toza = new Toza(tozax);
		stinger.add(toza);
		for (Object x : stinger) {
			((Toza) x).start();
		}
		for (Toza q : stinger) {
			q.hunter();
		}
	}

	public synchronized void hunter() throws Exception {
		while (!shifter) {
			waiter();
		}
		System.out.println(rabbit);
	}

	public synchronized void run() {
		rabbit++;
		if (rabbit > 3) {
			shifter = true;
		}
	}

	public void waiter() throws Exception {
		Thread.sleep(100);
	}
}

They say that the correct answer is the first one: the fact that the output is guarenteed to be 4444.

But, when running the above code it seems like deadlock is an usual issue. In my opinion, this happens because the Main thread acquires a lock for one of the 4 objects(let's say A) and then the A thread can't call its run() method since the lock is taken away by Main.

I'd rather go for "The ouput is not guarenteed".

What do you think?

[jamil lusa]

At first glance, i will guess the answer is "not guarantee", but after i have read this code for more than 10 minutes ( i swear i will skip this kind of question directly when i am sitting exam! crazy to understand!).

I think main thread is not taking any lock as you said. each thread is taking their own lock, but they are not dislaying anything, until the 'while' loop is false. and in order the 'while' loop to be false, 'rabbit' must be greater than 3. 'rabbit' only can be greater than 3 when the last thread (which is forth) finished the increment.

anyway, have you run the code, you get any deadlock?

[Ariel Chelsau]

Yes, I've run it and encountered deadlock several times.

When I say that the main thread acquires a lock, I refer to the point when the hunter method is called from the main thread.

Correct me if I'm wrong, but as far as I understand this, the lock for the thread referenced by 'q' may be taken by either thread 'q' itself when running run() method or the main thread when calling hunter() method.

[jamil lusa]

Ermmm, you are right that when q.hunter is called, it will check for its OWN run method to ensure that the OWN lock is realesed.

If the hunter method run too fast before the 4's thread 'run' has finished. It does not matter and not causing any deadlock. because the 'while' loop inside the hunter method will loop (and wait) until 4's thread 'run' finish.

anyway, what tools you are using to compile and run? i am using jdk 1.6 from http://ideone.com/ i do not have compiler in my pc i run the program at least 5 times, it never gives me any deadlock. Maybe you have to check again.

[Jeffrey Tian]

I tried many times, deadlock happens. I think the deadlock is caused by synchronized methods run() and hunter.
There're 4 Toza objects. Take one of them, says t1, as an example:
In main thread, t1 gets the lock and enters method hunter(). If shifter is false, it'll wait and check shifter again and again until shifter becomes true;
At the same time, in some thread, t1 tries to enter run() method. Since the lock is unavailable(the lock has been taken by t1 in main thread), it has to wait there until the lock is available.
Deadlock occurs.

If the synchronized modifier of method hunter() is removed, there won't be deadlock.