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.
Thanks for these great puzzles!
Here’s a commented solution. As always with concurrency, I find it hard to prove whether the solution is safe, but I think it is. I’m not sure though, whether “volatile” is necessary.
That was fun – hadn’t really thought of the relationship between synchronized methods and wait and notify before!
My version.
http://pastebin.com/7E5Prbgd
Great puzzle!! Thanks.
Oh, I guess that you don’t really need separate Dream classes (especially if you don’t mind infinite loops & threads, though you could implement a static counter to limit them)
Hi,
I’m a bit late with my entry but here it comes: it’s a dream that spawns another dream and waits for the second dream to start which will then cause the first dream to finish and then the night is over before the second dream came to its end. Don’t we all know this strange feeling when waking up and having some unfinished matters still on our minds?
Actually I found this puzzle a lot easier than the one with the clowns. Maybe because it is closer to what I have to deal with (i.e. debug) during my daily work.
BTW, I love this kind of puzzles, thank you!
Kind regards,
Thomas
You can fool the Sleeper by doing a ping-pong with another thread, stealing Sleeper’s lock to insert an extra dream:
I should probably add a Thread.sleep() after the wait in StrangeDream.dream(Sleeper) – I think there’s a race as it stands.
Dream of unlimited depth can be created. The limit depends on your resources only, i.e. on how many threads can your JVM create under you OS with its default RAM. In this example it is set to 100. You can see the level, if you add one logging line to the Main class.
If smb wants to check the real level, logging can be added as follows:
… and to get the better feeling about what is going on, a single logging line can be added to the Sleeper:
synchronized does indeed keep multiple threads from running at once inside a given method – but it doesn’t stop one thread from running while others are waiting. This code works on my machine:
https://github.com/dlikhten/dreams
That contains the solution. You can’t use the security manager via intellij (it’s all set to go) but you can see that it is unnecessary as I don’t need the features of setAccessible. And it runs from command line
Pretty simple actually, especially when you use drugs when you go sleep.
This seems to work.
Hi,
I used a supplementary thread in order to increment the level counter and wait 2 seconds meanwhile the primary calling thread is waiting only 1 second. In this way the check on the level variable will be done while the supplementary thread is still waiting on a wait condition: A a result we will have the level counter with a value of 2.
actually lower synchronized block is not needed…
Sleeping other this problem was a good idea. I found a solution:
@Ludo : t’es un grand malade!
@Wouter : thank you for sharing thoses puzzles! Had a nice time burning some neurons on them, will have another nice time bashing some colleagues and friends tomorrow
=======================================================
Any comments above these line were made before the solution came out. Anything below comes after.
If there is anything between the lines, clean your monitor.
If you make this change to the Sleeper class, none of the posted solutions will work anymore…
I wonder if it is still possible to break it like this?
I don’t expect it’s possible to break that. But I’d love to be surprised.
If you use Project Lombok, you can write:
The @Synchronized will create the lock field for you and wraps the entire method content in a synchronized block.
See http://projectlombok.org/features/Synchronized.html for more information.
Disclaimer, I’m one of the Project Lombok developers.
Simply awesome! I wish we could do this daily not weekly!!!
Concurrency devils are disturbing your dreams
The “official” solution is not guaranteed to reach the goal line. Just set a breakpoint on line 16 at
s.enter(new Dream() {
and debug.
You’ll always wake up in the cold reality.
If you remove the timeout from
s.wait(200);
and inserts.notify();
before
doWait(s);
in the inner dream and afterdoWait(s);
in Dream#dream(..), then you get the sweet dream in many more cases.But to be completely safe, every invocation of wait(..) needs to be performed inside a loop (see the Javadoc).
You’re right.
I was being lazy, and something that works 99.99% of the time unless you intentionally make it not work (by setting a breakpoint) seems good enough for this puzzle. I also didn’t want to make the sequence diagram any more complicated than it already is.
It needs an extra “Kids, don’t write code like this for real” disclaimer.
I can only agree with this comment ;P
Guys,
It seems that almost all of you forget to wrap wait calls in a cycle. It seems to be wrong.
It has many more things wrong with it.
It relies on an implementation detail of the locking of the Sleeper; it does a frick’n
.wait()
on someone else’s lock. It also does complicated things without commenting why, it’s lacking javadoc and unit tests.Solutions to previous and next puzzles have done and will do things that make my wrongness-meter go much more into the red then any of that.
The whole point of these puzzles is to break the conventional rules. The usual wrong or correct don’t apply here. All that matters is that it’s fun, it seems to work when you run it, and that others can understand why it works.
And in my opinion, it also leads to a whole different kind of code beauty.
Thanks for the exercise for concurrency programming in Java.
I think the original task is a bit confusing because of the “// TODO implement me” in the dream method. I thought this is the only location you may modify but in your solution you added a method to the class.
It doesn’t really change anything to the puzzle; you can just as easily do it without that extra method.
I’m happy ! I found the solution !
Not easy but It was interesting.
Thanks.