5 ms·

The Deadlock Empire

150 points by jasonpeacock 5y ago

CodesInChaos 5y ago
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.
thghtihadanacct 5y ago
Cool logic and a nice layout.
prvak 5y ago
I'm one of authors (Michael Pokorny), nice to see someone posting this again :)
- hyperpape 5y ago
  Thank you for this, the game did a lot for my understanding of concurrency.
- suresk 5y ago
  This was a lot of fun, thanks for building it!
- mindfulplay 5y ago
  I enjoyed this game quite a bit, thank you.
gfody 5y ago
the evil scheduler would be useful for catching deadlock bugs early
- reubenbond 5y ago
  Coyote is a great tool/library from Microsoft for testing large numbers of schedules in .NET programs: https://microsoft.github.io/coyote/ https://microsoft.github.io/coyote/
- neerajsi 5y ago
  There's also https://www.microsoft.com/en-us/research/project/cuzz-concurrency-fuzzing/ 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.
- Nzen 5y ago
  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/tylertreat/comcast
- nyanpasu64 5y ago
  https://github.com/tokio-rs/loom 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-mode.html https://robert.ocallahan.org/2016/02/introducing-rr-chaos-mo....
karmakaze 5y ago
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'.
grantjpowell 5y ago
I've worked in Erlang/Elixir for the past few years and I haven't had the opportunity to work "in anger"[0] with languages with traditional threads/mutexes/sempahores. This game was a blast and made me appreciate the Erlang's approach to concurrency. The best beginner resouce I've read on Erlang's concurrency model is here https://learnyousomeerlang.com/the-hitchhikers-guide-to-concurrency#dont-panic https://learnyousomeerlang.com/the-hitchhikers-guide-to-conc... [0] https://erlang-in-anger.com/ https://erlang-in-anger.com/
2sk21 5y ago
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
philzook 5y ago
Very cool! I found a TLA+ implementation of the problems https://github.com/cobusve/TLAPLUS_DeadlockEmpire https://github.com/cobusve/TLAPLUS_DeadlockEmpire that I've been meaning to look at more carefully for a while.
inetknght 5y ago
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.
- neerajsi 5y ago
  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.
nrclark 5y ago
This is really cool! Great puzzles.
nayuki 5y ago
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#page=245 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 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!
dang 5y ago
Past related threads: The Deadlock Empire – Slay Dragons, Master Concurrency (2016) - https://news.ycombinator.com/item?id=22040117 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 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 https://news.ycombinator.com/item?id=11064507 - Feb 2016 (30 comments)

150 points by jasonpeacock 5y ago

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.

thghtihadanacct 5y ago

Cool logic and a nice layout.

prvak 5y ago

I'm one of authors (Michael Pokorny), nice to see someone posting this again :)

hyperpape 5y ago
Thank you for this, the game did a lot for my understanding of concurrency.
suresk 5y ago
This was a lot of fun, thanks for building it!
mindfulplay 5y ago
I enjoyed this game quite a bit, thank you.

gfody 5y ago

the evil scheduler would be useful for catching deadlock bugs early

reubenbond 5y ago
Coyote is a great tool/library from Microsoft for testing large numbers of schedules in .NET programs: https://microsoft.github.io/coyote/ https://microsoft.github.io/coyote/
neerajsi 5y ago
There's also https://www.microsoft.com/en-us/research/project/cuzz-concurrency-fuzzing/ 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.
Nzen 5y ago
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/tylertreat/comcast
nyanpasu64 5y ago
https://github.com/tokio-rs/loom 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-mode.html https://robert.ocallahan.org/2016/02/introducing-rr-chaos-mo....

karmakaze 5y ago

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'.

grantjpowell 5y ago

I've worked in Erlang/Elixir for the past few years and I haven't had the opportunity to work "in anger"[0] with languages with traditional threads/mutexes/sempahores. This game was a blast and made me appreciate the Erlang's approach to concurrency. The best beginner resouce I've read on Erlang's concurrency model is here https://learnyousomeerlang.com/the-hitchhikers-guide-to-concurrency#dont-panic https://learnyousomeerlang.com/the-hitchhikers-guide-to-conc... [0] https://erlang-in-anger.com/ https://erlang-in-anger.com/

2sk21 5y ago

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

philzook 5y ago

Very cool! I found a TLA+ implementation of the problems https://github.com/cobusve/TLAPLUS_DeadlockEmpire https://github.com/cobusve/TLAPLUS_DeadlockEmpire that I've been meaning to look at more carefully for a while.

inetknght 5y ago

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.

neerajsi 5y ago
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.

nrclark 5y ago

This is really cool! Great puzzles.

nayuki 5y ago

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#page=245 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 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!

dang 5y ago

Past related threads: The Deadlock Empire – Slay Dragons, Master Concurrency (2016) - https://news.ycombinator.com/item?id=22040117 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 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 https://news.ycombinator.com/item?id=11064507 - Feb 2016 (30 comments)