💾 Archived View for dioskouroi.xyz › thread › 29431308 captured on 2021-12-04 at 18:04:22. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

The Deadlock Empire

Author: jasonpeacock

Score: 144

Comments: 20

Date: 2021-12-03 15:48:48

Web Link

________________________________________________________________________________

grantjpowell wrote at 2021-12-03 21:01:58:

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

[0]

https://erlang-in-anger.com/

prvak wrote at 2021-12-03 18:22:17:

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

hyperpape wrote at 2021-12-03 20:54:16:

Thank you for this, the game did a lot for my understanding of concurrency.

suresk wrote at 2021-12-03 23:42:27:

This was a lot of fun, thanks for building it!

mindfulplay wrote at 2021-12-04 02:49:00:

I enjoyed this game quite a bit, thank you.

nayuki wrote at 2021-12-04 00:32:45:

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!

philzook wrote at 2021-12-03 21:59:52:

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.

CodesInChaos wrote at 2021-12-04 15:39:44:

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.

dang wrote at 2021-12-04 04:05:17:

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)

inetknght wrote at 2021-12-03 22:33:10:

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 wrote at 2021-12-04 07:57:17:

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.

karmakaze wrote at 2021-12-03 20:28:51:

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

2sk21 wrote at 2021-12-03 21:34:24:

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

gfody wrote at 2021-12-03 19:06:11:

the evil scheduler would be useful for catching deadlock bugs early

Nzen wrote at 2021-12-03 19:34:48:

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

neerajsi wrote at 2021-12-04 08:00:17:

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.

reubenbond wrote at 2021-12-04 07:34:00:

Coyote is a great tool/library from Microsoft for testing large numbers of schedules in .NET programs:

https://microsoft.github.io/coyote/

nyanpasu64 wrote at 2021-12-03 19:50:54:

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

nrclark wrote at 2021-12-04 00:26:50:

This is really cool! Great puzzles.

thghtihadanacct wrote at 2021-12-03 17:42:52:

Cool logic and a nice layout.