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.
The Deadlock Empire
11–20 of 21 posts
Re: The Deadlock Empire
#12Nice 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.
Re: The Deadlock Empire
#13I'm one of authors (Michael Pokorny), nice to see someone posting this again :)
This was a lot of fun, thanks for building it!
Re: The Deadlock Empire
#14This is really cool! Great puzzles.
Re: The Deadlock Empire
#15You 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!
Re: The Deadlock Empire
#16I'm one of authors (Michael Pokorny), nice to see someone posting this again :)
I enjoyed this game quite a bit, thank you.
Re: The Deadlock Empire
#17Past 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)
Re: The Deadlock Empire
#18the evil scheduler would be useful for catching deadlock bugs early
Coyote is a great tool/library from Microsoft for testing large numbers of schedules in .NET programs: https://microsoft.github.io/coyote/
Re: The Deadlock Empire
#19Nice 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.
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.
Re: The Deadlock Empire
#20the 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.