Time to dream the solution to the dreams puzzle. As a reminder, here’s the challenge:
package sleep; import dream.Dream; public class Sleeper { private int level; public synchronized int enter(Dream dream) { level++; try { dream.dream(this); } finally { level--; } return level; } }
package sleep; import dream.Dream; public class Main { public static void main(String[] args) { if (new Sleeper().enter(new Dream()) != 0) { // The goal is to reach this line System.out.println("Am I still dreaming?"); } } }
Solution
The synchronized
on the dream
method means that it takes the monitor (lock) of the Sleeper object when we enter it, and it releases it again when we leave it. No other thread can enter the method while the monitor is held.
But here’s the catch: the monitor isn’t necessarily held all the time while the method is running. With Object.wait
you can release a monitor in the middle of a synchronized
method.
How do we apply that to solve this puzzle? When we enter the outer dream, we use wait
to release the monitor. But first we launch a separate thread, that will also enter a dream. Entering that inner dream makes the second thread take the monitor. So in the inner dream, we use wait
a second time to release the monitor. That allows the main thread stop waiting, take the monitor back, and leave the outer dream. And there we are: we have woken up from the outer dream, back where we started in main
, but the dream within the dream goes on in the second thread.
package dream; import sleep.Sleeper; public class Dream { private static void doWait(Sleeper s) { try { s.wait(200); } catch (InterruptedException e) { } } public void dream(final Sleeper s) { new Thread() { public void run() { s.enter(new Dream() { @Override public void dream(Sleeper s) { doWait(s); } }); } }.start(); doWait(s); } }
And the winner is…
I got more answers than I expected. The first one came from David Shay. Congrats!
It’s a bit repetitive, but as promised, you can see and compare all dreams as comments below this post.
Conclusion
The moral of the story: synchronized
on a method doesn’t mean two different threads can’t be in it at the same time. It only ensures that such threads cannot execute concurrently; at least one of them must be waiting.
You can prevent this kind of abuse and other problems, by using a private object as monitor:
public class Sleeper { private final Object lock = new Object(); public int dream(Dream dream) { synchronized(lock) { ... } } }
But that still leaves me unsure if I actually woke up this morning.
This one wasn’t that hard…
(slightly more succinct than previous entry)
Another solution
I hope this one is valid.
My solution uses the fact that Object.wait releases the sleeper’s monitor, allowing another Thread to call the enter method and wait as well allowing the main Thread to continue:
This will result in an infinite loop until Sleeper.java:11 throws java.lang.IllegalArgumentException. By then, level should have a value of Integer.MAX_VALUE, decrement it will return value of Integer.MAX_VALUE-1
Alternatively, it would have recursed so such that Sleeper.java:11 actually throws java.lang.StackOverflowError. When this happens the value of level is likely to be a value more than 2. Decrementing it will return a value more than 0
This doesn’t work. See also comment from Usman a little lower. Does it work for you, or did you not even try to run it?
This is some nice brain teaser. It took me quite a while.
The key idea is to release the lock obtained when entering the synchronized dream method.
Recursively overflow int value.
However had to increase stack size -Xss. However, this makes my machine extremely slow to respond
. Will try to come up with some alternate mechanism.
Doesn’t work for me.
I don’t see how it can work; because even in case of an overflow, counter– undoes what counter++ did.
Please find my solution below:
In the Dream, recursively enter the same dream again in a second thread, using wait and notify on the Sleeper to work around it’s synchronized block. Then release the master dream before the recursive dream is done.
I found this one much easier to solve than the clowns puzzle, but once I did I was ably to apply a similar multi-threaded solution for that one.
Here is my proposed solution, taking advantage that Sleeper synchronizes on himself.
The trick is that s.wait() will release the monitor that Java uses to synchronize the Sleeper.enter() call.
The idea is that
wait
releases the current monitor, thus we can enter a new dream on a new thread.too eager to make proper formatting – here we go again:
There, did it (but not in 15 minutes)
Release the lock with wait()!
Hi, last night I posted an idea. Here’s code too:
Sleeper is actually exposing an undocumented API: synchronization on itself. Sleeper could fix this by using an internal Object for synchronization.
The bug is that the class is synchronizing on an object reference that is passes to untrusted code. The Dream implementation can release the lock, enter the enter(Dream) method on another thread, and then wake up the initial thread. At this point, the Sleeper class will have entered the enter(Dream) method twice, and exited it once.
Here’s an implementation:
This code seems to work, creates an inner dream that never ends in another thread:
Rough and unpolished (and probably creates extra unneeded thread, but who cares
).
Hello,
it indeed took me a while to get this done, but here is my solution:
The Trick is to have a second that will increase the level but will not end, i therefore chose the name EndlessDream (we’ll see the code later). The first dream howewer needs to end, so the sleeper method will return and the required line will be printed.
At first sight, this seems imposisble with the synchronized method, but i then remembered, that you can temporarily leave a monitor using wait.
First we start our second endless dream in a new thread. The endless dream will however block because its synchronized on the sleeper object and our first dream has the lock.
We therefore need to give the endless dream a chance
to start, which we do by using s.wait() in our first dream after starting the thread. The endless dream will then wake up and increase the level. We then use notify inside the endless dream to wake up our first dream. Here we need do consider that the notify will not give control to our first dream but continue our endless dream. Therefore a call to s.wait() is also needed in our endless dream.
Lots of explanations but i hope that made it clear. Finally, here is the code:
I forgot to mention, that this code will indeed make the second dream an endless one, as no one ever wakes the thread up again.
Here’s my solution:
It can be done by two simple threads.
This is really a cool puzzle. Thanks for it!
My solution uses a separate thread which lets the sleeper enter a second dream which endures while the first dream ends.
The trick is to let the threads yield the lock, so that the synchronized method can be entered twice. Object.wait() does allow that.
I guess a counter-measure would be for the Sleeper to use a private lock object instead of synchronizing on the instance itself.
Regards,
Andreas
The key seems to be to make sure that the DreamForever thread gets access to the monitor and then never exits.
Thanks for these puzzles, really enjoyed the first one, and this was also fun. I’m with Heinz – more hard ones please, don’t bother with the easy ones!
My solution for the Sleeper:
That was cool – tried various options on killing the other thread, while eventually it appeared not necessary procedure
Probably (almost definitely) not the best solution but seems to work. Spent ages trying to get the second thread to exit/interrupt so that it wouldn’t execute the finally block in Sleeper but didn’t seem to work.
Welcome any feedback.
Cheers,
Nick.
Correction – should have pasted in the whole class: