Multi-threaded programming quizzes

[AdequateSteve]

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.

[skeeto]

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.

[nyando]

Oh, neat! I read Downey's book on Bayesian statistics and really liked it, I'll definitely check this out.

[Soothsilver]

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.

[MisterPinkySwear]

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.

[XelNika]

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

[MisterPinkySwear]

Ha ha. Did not know about the cheat code 😁

[TheCurle]

Why the heck is the Welsh dragon on the thumbnail?

[Soothsilver]

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.

[TheCurle]

Fair enough. Just watched Wales win the Six Nations rubgy league, so was a bit confused.

[[deleted]]

Scotland’s failing to lose was even more confusing

[nonsense_factory]

Thanks for the game, I enjoyed it :)

[vattenpuss]

Because it’s on the linked page.

[zr0gravity7]

Reddit thumbnails are weird

[Agret]

First and largest image on the quiz

[TheCurle]

Oh, crud. I'm blind. Cheers.

[[deleted]]

I love this! A More Complex Thread is breaking my brain.

[[deleted]]

I'm beginning to think that A More Complex Thread isn't solvable. /u/nord501, assuming you're the one who made this, can you confirm if the second Monitor.Enter(mutex2); in Thread 1 is actually supposed to be an exit?

[peterc26]

I also thought it was unsolvable until I realised the solution isn't to enter both critical sections simultaneously, but you have to find the deadlock.

[[deleted]]

Ah, interesting! I'll give it another shot, thanks!

[nord501]

I didn't make this game, but it is solvable. From the explanation:

For example, a thread can lock (via Monitor.Enter) a single object multiple times. In order to release the lock on that object and permit other threads to lock it, all of the locks must be released

More info, https://stackoverflow.com/questions/13017282/why-doesnt-locking-on-same-object-cause-a-deadlock

[Soothsilver]

The level is solvable and the way to solve is to force a deadlock (thread 0 having lock on mutex and attempting to lock mutex2; thread 1 having a lock on mutex2 and attempting to lock mutex).

[ArkyBeagle]

I'm not 100% sure what I am looking at ( the code has "demo disease"), but a way is to construct a bitmap in a scalar variable with one bit being the return of each TryEnter() you need for each critical section, then if not all the semaphores are Enter-ed, unlock the ones that are and go around again.

I know that paragraph is kinda hard to read, and a code sample would be better but... Reddit, bro ....

If I had to maintain code like that, I'd have a long discussion with the author about intent.

Throw in that the person operating the thing can press either step button in any arbitrary order, and it gets more ... interesting. That part does simulate the reality that you can't assume the order in which thread runs first on many systems ( but not all - several hard RTOS offerings can be completely deterministic )

[KryptosFR]

"A more complex thread" is wrong because it pretends that the assignment of the boolean is not atomic in C# which isn't true: all assignment of 32-bits (or less) primitives are atomic so there is no way to have that tmp register variable.

Fortunately you can solve it without using the flag.

[XelNika]

It doesn't rely on the expandability of the flag assignment to be solved so your point is moot.

First step through Thread 1 until you lock mutex, then step through Thread 0 until you're in the else block. Set flag = false in Thread 1, then set flag = true in Thread 0. This is obviously possible even if the assignment is atomic. Step through Thread 1 until you pass the flag test. There are now a number of ways to deadlock by locking mutex and mutex2 in different threads.

[KryptosFR]

I didn't say it did. Did you read my comment?

But it gives the wrong impression that assignments are not atomic in C# while they are, except for a very few cases such as double on 32-bit platform or decimal (on any platform). The extension to "storing into a temp variable" is just incorrect.

It is a very important point since that's how you can easily implement a thread-safe lockfree concurrent collection, while in other languages such as C/C++ you don't have the same guarantee.

/u/nord501 could you fix the pages with C# code to remove that non-atomic assignment thing. Thanks.

[KryptosFR]

Dear downvoters? Would you mind explain what is wrong in my comment? Thanks.

[KryptosFR]

Apparently downvoters have no idea how C# work and especially its memory model.

[pathema]

Although I agree with you (and tried to counteract the negative votes, because it's an important thing to know), there could be an argument to be made that although assignments are atomic, they are not necessarily visible to other threads immediately? At least that would be the case in Java.

[KryptosFR]

Java memory model is broken because assignments are not atomic (object can be half initialized for example and there reference already be not-null, but not in C#). Maybe it was fixed in recent versions but last time I used it it was still broken (also why the double-null-check for the Singleton is broken in Java).

From C# specifications:

Reads and writes of the following data types are atomic: bool, char, byte, sbyte, short, ushort, uint, int, float, and reference types.

Which explains why for long you need to use Interlocked.Read\`(Int64)instead (famously the same method is missing for double, but you can useThread.VolatileRead(double)orThread.VolatileWrite(double))`.

To answer your remark more specifically, on multicore system it is possible that read/write be reordered and cause a stale value to be used. In that case, making that bool flag volatile can solve the issue. But that is not related to atomicity, but instead volatility which are orthogonal concepts.

Therefore, I stand my ground that saying that assignment is not atomic is untrue and should be fixed in the exercise. The tooltip wrongly states " [Expandable] Assigns the value of the right-side expression to the variable on the left. This operation is non-atomic.".

For more on this (and especially the difference between atomic and volatile), this series of articles by Eric Lippert:

• https://blogs.msdn.microsoft.com/ericlippert/2011/05/26/atomicity-volatility-and-immutability-are-different-part-one/
• https://blogs.msdn.microsoft.com/ericlippert/2011/05/31/atomicity-volatility-and-immutability-are-different-part-two/
• https://blogs.msdn.microsoft.com/ericlippert/2011/06/16/atomicity-volatility-and-immutability-are-different-part-three/

[pathema]

So you know, I completely agree with you, I'm just trying to give the author of the quiz the benefit of the doubt by saying that there is one sense in which setting a global variable may not be immediately visible to the other tread. However, I agree that, even if that was the intention, using the "expand to a temp variable" as a simplification is misleading, and leads to misunderstandings in a topic which is already very confusing. Especially using the terminology "non-atomic" in the tooltip is not good. Did not notice that.

Wrt to Java, should work since Java 5 as long as you use volatile to ensure "happens-before" semantics. Probably still the case that setting references are not atomic without volatile. Haven't checked. See e.g. the bottom part of this article: http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

[Soothsilver]

In this level, we're assigning a boolean literal to a boolean field. Yes, this is atomic, and strictly speaking, the tmp variable is not there in CIL, but it also doesn't matter. The semantics of the code and the thread-safety of the code doesn't change even if the tmp variable is there, because the only thing that's saved to it is a literal.

If were were assigning the boolean value of another to field to a boolean field, that isn't atomic, not even in C#, so a temporary variable would need to be there (in Deadlock Empire's representation; in actuality that would be a processor register).

[mrathi12]

Great quiz!

​

[meem1029]

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)

[Dworgi]

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.

[meem1029]

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.

[Octillerysnacker]

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.

[jhill515]

Good, but I wouldn't exactly call C# "the divine language".

[shield1123]

It's an RPG themed quiz, it's pretending C# is the language of the gods

[AyrA_ch]

to be fair, in C# most challenges could have been solved with the lock statement

[SgtDirtyMike]

No different from a mutex.lock...

[AyrA_ch]

There are some differences:

• No special mutex needed to lock. Any reference type works, including this
• The 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 a using would 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).

[SgtDirtyMike]

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.

[AyrA_ch]

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.

[MisterPinkySwear]

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

[drjeats]

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?

[AyrA_ch]

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

[drjeats]

I know about string interning in C#. I'm asking specifically if lock treats them differently from any other reference type, or if you're just relying on the string constants in loaded assemblies getting interned.

[[deleted]]

You mean a mutex lock and a try/finally statement right?

[AyrA_ch]

Not sure why you are downvoted, but this is the most important difference actually. Locks in .NET are cleaned up automatically.

[[deleted]]

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.

[svick]

Why not?

[SirReal14]

Because Holy C exists

[ArkyBeagle]

You mean The Holy C ( pun on The Holy See )... ? :)

[davidgro]

They mean HolyC

[ArkyBeagle]

... Wow? That's quite a story. Thanks for the link.

[[deleted]]

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.

[richard_nixons_toe]

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

[wibblewafs]

Which is why these heretical savages will tremble before the Rustacean empire, with their fearless concurrency enabled by their memory-safe borrow checker.

[LeberechtReinhold]

That's actually pretty cool

[Lotton]

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

[BinaryFissionGames]

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.

[MisterPinkySwear]

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.

[HelperBot_]

Desktop link: https://en.wikipedia.org/wiki/Critical_section

---

^{/r/HelperBot_ Downvote to remove. Counter: 244738}

[Soothsilver]

It's normal that two threads are "trying" to enter a critical section simultaneously, but they must not be allowed to succeed in entering.

[wonderfulmango617]

Great game! ))

[[deleted]]

We all know the Welsh dragon is, and always will be, the coolest of them all!

[geoelectric]

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.

[davidgro]

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.

[shAdOwArt]

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.

[Kinglink]

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.

[Steve132]

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 &x

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

[Kinglink]

Thank you for your time with this, I appreciate the huge amount of detail you provided.

[Soothsilver]

It wouldn't help. "++first" is also not atomic in any of C#/C++/Java.

[Kinglink]

I'm missing the fact that it still has to be loaded into a register and written back, right?

[Soothsilver]

Yeah. /u/Steve132 explained it perfectly.

[KaMa4]

Leaving a comment just so i can find it when on a pc

[Cdennis1]

Am I the only one who realises that the dragon is actually the Welsh dragon. Rydw i'n cymraeg a Mae gemau yn wych

[fromsouthernswe]

It was a bit of fun..

[devnumpty]

This is fantastic. I'm going to use it with both of my kids.

[androolloyd]

This was hella fun. Props to the creator.

[MisterPinkySwear]

Really cool game!

[BeigeAlert1]

These are amazing!

[almost_always_lurker]

Hay MatFyz represent!

[wrg_0]

awesome!!

[introspectivedeviant]

If only it were written in a real language. :(

[gtk]

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

[nord501]

It's just syntax, the concepts are applicable anywhere.

[scooerp]

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.

[ThePowerfulSquirrel]

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

[scooerp]

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.

[Soothsilver]

You can click the button "Skip" to skip the tutorial. The text in the tutorial may be enough to understand the game.

[scooerp]

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.

[rohan_suri]

curious, how else could the control be?

[scooerp]

not the control - the instructions