The Deadlock Empire(deadlockempire.github.io)
deadlockempire.github.io
The Deadlock Empire
https://deadlockempire.github.io/
20 comments
I'm one of authors (Michael Pokorny), nice to see someone posting this again :)
Thank you for this, the game did a lot for my understanding of concurrency.
This was a lot of fun, thanks for building it!
I enjoyed this game quite a bit, thank you.
You made an awesome game that really hits home the concept that arbitrary execution interleavings throws a wrench in poorly designed concurrent algorithms.
I was teaching some people about threading recently. Some materials I used include https://inst.eecs.berkeley.edu/~cs61b/fa15/book1/java.pdf#pa... (4 examples of the producer-consumer problem) and https://pages.cs.wisc.edu/~remzi/OSTEP/threads-cv.pdf (even more examples of broken producer-consumer). I would love to see these textbook examples incorporated into the game as new levels!
I was teaching some people about threading recently. Some materials I used include https://inst.eecs.berkeley.edu/~cs61b/fa15/book1/java.pdf#pa... (4 examples of the producer-consumer problem) and https://pages.cs.wisc.edu/~remzi/OSTEP/threads-cv.pdf (even more examples of broken producer-consumer). I would love to see these textbook examples incorporated into the game as new levels!
Very cool!
I found a TLA+ implementation of the problems https://github.com/cobusve/TLAPLUS_DeadlockEmpire that I've been meaning to look at more carefully for a while.
Past related threads:
The Deadlock Empire – Slay Dragons, Master Concurrency (2016) - https://news.ycombinator.com/item?id=22040117 - Jan 2020 (4 comments)
The Deadlock Empire: A game that teaches locking and concurrency (2016) - https://news.ycombinator.com/item?id=19411641 - March 2019 (4 comments)
Show HN: The Deadlock Empire – Slay dragons, master concurrency - https://news.ycombinator.com/item?id=11064507 - Feb 2016 (30 comments)
The Deadlock Empire – Slay Dragons, Master Concurrency (2016) - https://news.ycombinator.com/item?id=22040117 - Jan 2020 (4 comments)
The Deadlock Empire: A game that teaches locking and concurrency (2016) - https://news.ycombinator.com/item?id=19411641 - March 2019 (4 comments)
Show HN: The Deadlock Empire – Slay dragons, master concurrency - https://news.ycombinator.com/item?id=11064507 - Feb 2016 (30 comments)
Really like the gamification, reverse presentation/adversarial mode of thinking.
I now generally avoid concurrency mechanisms that don't compose but this could have been useful for learning and communicating issues that aren't otherwise easy to illustrate to someone who doesn't already 'get it'.
I now generally avoid concurrency mechanisms that don't compose but this could have been useful for learning and communicating issues that aren't otherwise easy to illustrate to someone who doesn't already 'get it'.
Nice work!
I wish this had at least one more problem that it could highlight: synchronization using sleep() without atomics. A call to sleep() isn't guaranteed to flush cache and so the classic problem is that you could have two threads waiting on a bool and neither of them seeing updates from the other thread.
I wish this had at least one more problem that it could highlight: synchronization using sleep() without atomics. A call to sleep() isn't guaranteed to flush cache and so the classic problem is that you could have two threads waiting on a bool and neither of them seeing updates from the other thread.
Can you give a concrete example?
Cache coherency is almost never the right thing to think about with shared memory concurrency. It's all about interleaving of instruction execution and possible reordering of memory reads or writes.
If by sleep(), you mean a spin loop, its possible that the compiler has reordered a write past an empty loop that appears to have no side effects. If you're talking about an OS API to delay execution, then sleep should allow other threads to see the writes done before the sleep. It's just not a great way to synchronize compared to a condition variable since sleep waits for some arbitrary amount of time rather than exactly as much as is needed to observe a change.
Cache coherency is almost never the right thing to think about with shared memory concurrency. It's all about interleaving of instruction execution and possible reordering of memory reads or writes.
If by sleep(), you mean a spin loop, its possible that the compiler has reordered a write past an empty loop that appears to have no side effects. If you're talking about an OS API to delay execution, then sleep should allow other threads to see the writes done before the sleep. It's just not a great way to synchronize compared to a condition variable since sleep waits for some arbitrary amount of time rather than exactly as much as is needed to observe a change.
I loved these puzzles. I was reminded of the famous book by Tony Hoare "Communicating Sequential Processes". In that book, he describes the trace of a parallel program as all possible interleaving of the traces of the individual programs
It looks like this game uses a very strong memory model. Loads and stores cannot be re-ordered and are immediately visible to all threads. Many languages and architectures have weaker memory models than that.
the evil scheduler would be useful for catching deadlock bugs early
There's also https://www.microsoft.com/en-us/research/project/cuzz-concur.... This is part of the Windows App Verifier, so it should be usable for any Windows app.
Coyote is a great tool/library from Microsoft for testing large numbers of schedules in .NET programs: https://microsoft.github.io/coyote/
I don't doubt someone has built something like that for testing, though perhaps not as a library. I'm reminded of a networking service that does the same at a higher level, given its easy to remember name : https://github.com/tylertreat/comcast
https://github.com/tokio-rs/loom perhaps? It also models weak memory reordering, but takes some work to integrate into existing apps.
For triggering race conditions in compiled binaries, you could try https://robert.ocallahan.org/2016/02/introducing-rr-chaos-mo....
For triggering race conditions in compiled binaries, you could try https://robert.ocallahan.org/2016/02/introducing-rr-chaos-mo....
This is really cool! Great puzzles.
Cool logic and a nice layout.
[0] https://erlang-in-anger.com/