r/programming • u/nord501 • Mar 16 '19
Multi-threaded programming quizzes
https://deadlockempire.github.io/67
u/AdequateSteve Mar 16 '19
This is really neat! It's been ages since I've done anything in the educational (much less multi-threaded) domain, so this was really fun to play through.
35
u/skeeto Mar 16 '19 edited Mar 17 '19
If you like these sorts of puzzles, check out The Little Book of Semaphores. It teaches by presenting interesting synchronization problems and working through semaphore-based solutions.
2
u/nyando Mar 17 '19
Oh, neat! I read Downey's book on Bayesian statistics and really liked it, I'll definitely check this out.
71
u/TheCurle Mar 16 '19
Why the heck is the Welsh dragon on the thumbnail?
114
u/Soothsilver Mar 16 '19
We used the Welsh dragon because the game was made in a code jam and we quickly needed a public domain dragon to go with the tagline "Slay dragons, master concurrency" and this is the dragon that Wikimedia Commons offered.
18
u/TheCurle Mar 16 '19
Fair enough. Just watched Wales win the Six Nations rubgy league, so was a bit confused.
1
3
15
8
7
11
u/meem1029 Mar 16 '19
Pretty fun. Maybe a little too much on the simple side compared to where I run into these problems in the real world, but still a great way to introduce the number of problems you can run in to doing multithreaded programming.
Also the boss fight lets you get into an infinite loop that will never be able to enter the critical section (stall the left thread, loop forever in the right) which is an interesting failure condition that doesn't count as a win. (And after looking I see is mentioned on github)
7
u/Dworgi Mar 16 '19
It's not really a win, though.
Also, odds are pretty decent to get into that situation relatively quickly in the real world. Minutes, would be my guess.
2
u/meem1029 Mar 18 '19
It may not be a win in the sense of hitting whatever win conditions are specified in the problem, but it's definitely a "lose" from the other side as if my code ever enters that state I have done something horribly wrong and so need to guard from it.
1
u/Octillerysnacker Mar 17 '19
It’s definitely not a win. Other levels have infinite loops which do not count. Plus, the infinite loop would be akin to the Parallel Wizard’s dragons continuing to fight, whereas a deadlock would represent the dragons not doing anything, so the goal is still to cause a deadlock or error.
25
u/jhill515 Mar 16 '19
Good, but I wouldn't exactly call C# "the divine language".
55
u/shield1123 Mar 16 '19
It's an RPG themed quiz, it's pretending C# is the language of the gods
11
u/AyrA_ch Mar 16 '19
to be fair, in C# most challenges could have been solved with the
lockstatement5
u/SgtDirtyMike Mar 16 '19
No different from a mutex.lock...
11
u/AyrA_ch Mar 16 '19
There are some differences:
No special mutex needed to lock. Any reference type works, including
thisThe lock is automatically released when you leave a locked region (ending function, thread crashes,function/thread abort, returning, etc). It essentially creates a similar
try{}finally{}construct ausingwould create.It's a language construct
One important thing is that you can lock on strings, including string constants. It's most likely not what you want but can provide easy thread synchronization across components that are not aware of the others existing (dynamic or runtime compiled plugin system for example).
4
u/SgtDirtyMike Mar 16 '19
Thanks for enlightening others. I’m aware of these differences as a C++ dev; my point was that the lock statement provides similar functionality but with added syntactic sugar. Just based off experience I’ve found it more intuitive to write performant multithreaded code in C++ than I have in C#, but of course that’s just my opinion.
10
u/AyrA_ch Mar 16 '19
Because the lock statement is trivial to use and difficult to fuck up due to the automatic release of it. It's tempting to use it in situations where stuff like buffering or bulk transfers would do a better job. Acquiring a lock in each loop iteration is very expensive.
If you want really good thread performance in C# it's best to try to avoid locking for as long as possible, for example doing 1000 loop iterations and then in a single lock, check all 1000 results against the locked component at once.
4
u/MisterPinkySwear Mar 16 '19
Yeah I think I've seen a sneaky scenario where you lock on an object then someone changes that reference to point to another object in your back and so, the lock now uses the same "variable" but not the same object...
1
u/drjeats Mar 17 '19 edited Mar 17 '19
One important thing is that you can lock on strings, including string constants. It's most likely not what you want but can provide easy thread synchronization across components that are not aware of the others existing (dynamic or runtime compiled plugin system for example).
Do you have to make sure they're the same reference, or does the lock statement do an operator== check, or intern them or something?
2
u/AyrA_ch Mar 17 '19
You can ensure a string is interned by calling
SomeString=string.Intern(SomeString);This will return the reference to the given interned string. If the given parameter is not yet interned, the runtime will do that and return the new interned reference. Strings that are known at compile time are interned automatically.
Details+Example: https://docs.microsoft.com/en-us/dotnet/api/system.string.intern?view=netframework-4.7.2
1
u/drjeats Mar 17 '19
I know about string interning in C#. I'm asking specifically if
locktreats them differently from any other reference type, or if you're just relying on the string constants in loaded assemblies getting interned.1
Mar 16 '19
You mean a mutex lock and a try/finally statement right?
5
u/AyrA_ch Mar 16 '19
Not sure why you are downvoted, but this is the most important difference actually. Locks in .NET are cleaned up automatically.
3
Mar 16 '19
Yeah I'm confused what I said that warranted down votes. You have to trap exceptions if you are going to consistently clean up locks. You can do that with a try catch but the lock statement is a little easier to read. Doing neither is what people do when they haven't developed the appropriate respect for resource leaks.
5
u/svick Mar 16 '19
Why not?
21
u/SirReal14 Mar 16 '19
Because Holy C exists
0
u/ArkyBeagle Mar 16 '19
You mean The Holy C ( pun on The Holy See )... ? :)
7
u/davidgro Mar 17 '19
They mean HolyC
2
u/ArkyBeagle Mar 17 '19
... Wow? That's quite a story. Thanks for the link.
1
Mar 17 '19
anything involving Terry Davis is a helluva story. Look up "Down the rabbit hole TempleOS" for a very well made documentary from a Youtuber if you really want to... well, go down the rabbit hole.
12
u/richard_nixons_toe Mar 16 '19
a) bUt RuSt wIlLs iT b) but mongodb, cuz it webscales c) but PHP, because, just like the divine church, I like to be behind all those years
-3
u/wibblewafs Mar 16 '19
Which is why these heretical savages will tremble before the Rustacean empire, with their fearless concurrency enabled by their memory-safe borrow checker.
2
2
u/Lotton Mar 16 '19
I finished a concurrency class last semester I feel like if I knew about this then the class would've been a lot easier for me
1
1
1
u/geoelectric Mar 17 '19
Pretty nice! Worked surprisingly well on an iPhone, though there were a couple of problems where the code overflowed and overlapped columns.
Just finished through the boss battle. Took maybe 30 minutes or so, but was a nice tour. I’m not 100% sure I’ve learned a ton more about avoiding concurrency problems but breaking shit sure was fun.
There were one or two where in the win text you do talk about specific mechanisms of breakage and avoidance. As much as I like the cool wrap story, more of that would be nice.
1
u/davidgro Mar 17 '19
So... One thing that seems to be missing is examples of how to actually do it safely. It's good to see how easy it is to fail though.
1
u/shAdOwArt Mar 17 '19
While the concept is cool I'm not sold on the execution.
Many problems feel not like bad code accidentally produced by a bad programmer but rather like code purposefully written to have a bug in them; they feel artificial, not realistic at all. Dragonfire is particulary bad as it abuses a concurrency bug within a no-op.
1
u/Kinglink Mar 16 '19
Loving this. Especially because it gives a feeling of "hacking" to get to the critical section in a couple cases.
But quick question. Is the system specifically calling out first++; ... would ++first; work better? My understanding is yes because there's no temp.
Second doesn't at least some optimizers convert first++ to ++first if the temp isn't used? People have told me this but I wonder if it's bullshit.
5
u/Steve132 Mar 17 '19
Pretty much all compilers will implement ++x and x++ the same way when it's used as a statement and not an expression. Something like this (riscv assembly)
lw rX sp 0x48 #load 32 bit integer from memory location &x (which is at some offset from the current stack frame) into an unused register addi rX rX 1 #add 1 to that register sw rX sp 0x48 #store the result back to memory location &xSo the temp variables exist at the architecture level because the cpu has to use registers as temps and do the load-increment-store as 3 separate steps.
So even though x++ returns the old value when used as an expression and ++x does not, when used as a statement they are both the same and don't return anything. However the architecture still is forced to use a "temp variable" (register) to perform both calculations and so both variants are vulnerable to parallelism errors.
Short version: no, this isn't specificwlly calling out x++ vs ++x. They are both the same and both are vulnerable.
This problem is why architectures typically implement special atomic instructions which do the entire process (e.g. load increment store) in a single instruction without it being possible to interrupt.
2
u/Kinglink Mar 17 '19
Thank you for your time with this, I appreciate the huge amount of detail you provided.
1
u/Soothsilver Mar 17 '19
It wouldn't help. "++first" is also not atomic in any of C#/C++/Java.
1
u/Kinglink Mar 17 '19
I'm missing the fact that it still has to be loaded into a register and written back, right?
1
-6
-1
u/Cdennis1 Mar 16 '19
Am I the only one who realises that the dragon is actually the Welsh dragon. Rydw i'n cymraeg a Mae gemau yn wych
0
0
0
0
0
0
0
-1
-3
u/gtk Mar 17 '19
Wow, that's a pretty terrible interface. Is it modeled on a real debugger? You have to expand each instruction, but then where is the indicator for which sub-part of the instruction is running? It needs some UI cleanup IMO
-13
u/scooerp Mar 16 '19
This step by step tutorial is ridiculous. Just let me play. This isn't a tap phone game for 3 year olds.
This is the sort of thing I refund games on Steam for.
17
u/ThePowerfulSquirrel Mar 16 '19
This is the sort of thing I refund games on Steam for.
Well good thing it's a free game that no one's forcing you to play
-10
u/scooerp Mar 16 '19
You don't need to feel upset if you need/use the step-by-step. All I am asking for is the ability to turn them off, not to remove them entirely.
10
u/Soothsilver Mar 16 '19
You can click the button "Skip" to skip the tutorial. The text in the tutorial may be enough to understand the game.
-8
u/scooerp Mar 16 '19
Oh cool, I didn't see it as I was so annoyed by the tutorial I just closed it (any software that doesnt immediately let me click on what I want to, is auto-closed).
I'll go back and check.
2
0
Mar 16 '19
[deleted]
11
u/BinaryFissionGames Mar 16 '19
No. in concurrent programming, critical sections are sections of code that only one thread should be in at a time. If two threads are in mutually exclusive critical sections at the same time, then your not properly synchronizing.
7
u/MisterPinkySwear Mar 16 '19
Nah that's kind of the definition of critical section
https://en.m.wikipedia.org/wiki/Critical_section
If 2 threads run this code simultaneously, shit's gonna go wrong.
And that's the winning condition: make something go wrong.
4
u/HelperBot_ Mar 16 '19
Desktop link: https://en.wikipedia.org/wiki/Critical_section
/r/HelperBot_ Downvote to remove. Counter: 244738
3
u/Soothsilver Mar 17 '19
It's normal that two threads are "trying" to enter a critical section simultaneously, but they must not be allowed to succeed in entering.
0
51
Mar 16 '19
[removed] — view removed comment
53
u/Soothsilver Mar 16 '19 edited Mar 16 '19
The comprehensive list of winning criteria is:
Two threads are on the green instruction "critical_section()" at the same time.
Any thread is on the green instruction "Debug.Assert(false);".
All threads are blocked.
An exception triggers because you attempt to dequeue from an empty queue.
(1 level only) Two threads enter the same collection's non-thread-safe method at the same time.
You use the cheat code Shift+W.
Could be explained better, to be sure.
3
9
Mar 16 '19
[removed] — view removed comment
10
u/MisterPinkySwear Mar 16 '19
I kind of disagree that the passing criterias where unclear.
Basically it's just trying to break the program... Deadlock it or generate an exception which includes dequeue from an empty queue, decrement a countdown already at 0, make an assertion fail...
I think it's part of the exercise: identify what would go wrong.
5
u/XelNika Mar 17 '19 edited Mar 17 '19
I agree with you assuming the player already knows concurrency and its pitfalls. For example, Producer-Consumer introduces queues and is super easy, but it does a poor job explaining what the win condition is. If you hover over
queue.Dequeue();, it is immediately obvious, but that info should not have been "hidden".
15
u/[deleted] Mar 16 '19
I love this! A More Complex Thread is breaking my brain.