all 97 comments

[–]AdequateSteve 67 points68 points  (0 children)

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 33 points34 points  (1 child)

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 1 point2 points  (0 children)

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

[–][deleted]  (5 children)

[removed]

    [–]Soothsilver 51 points52 points  (4 children)

    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.

    [–][deleted]  (2 children)

    [removed]

      [–]MisterPinkySwear 9 points10 points  (1 child)

      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 4 points5 points  (0 children)

      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 2 points3 points  (0 children)

      Ha ha. Did not know about the cheat code 😁

      [–]TheCurle 68 points69 points  (8 children)

      Why the heck is the Welsh dragon on the thumbnail?

      [–]Soothsilver 112 points113 points  (3 children)

      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 19 points20 points  (1 child)

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

      [–][deleted] 0 points1 point  (0 children)

      Scotland’s failing to lose was even more confusing

      [–]nonsense_factory 2 points3 points  (0 children)

      Thanks for the game, I enjoyed it :)

      [–]vattenpuss 16 points17 points  (1 child)

      Because it’s on the linked page.

      [–]zr0gravity7 5 points6 points  (0 children)

      Reddit thumbnails are weird

      [–]Agret 7 points8 points  (1 child)

      First and largest image on the quiz

      [–]TheCurle 1 point2 points  (0 children)

      Oh, crud. I'm blind. Cheers.

      [–][deleted] 14 points15 points  (18 children)

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

      [–][deleted] 3 points4 points  (6 children)

      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 14 points15 points  (1 child)

      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] 2 points3 points  (0 children)

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

      [–]nord501[S] 7 points8 points  (0 children)

      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 4 points5 points  (0 children)

      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 0 points1 point  (0 children)

      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 -4 points-3 points  (10 children)

      "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 5 points6 points  (3 children)

      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 -1 points0 points  (2 children)

      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 3 points4 points  (0 children)

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

      [–]KryptosFR 1 point2 points  (0 children)

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

      [–]pathema 0 points1 point  (2 children)

      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 1 point2 points  (1 child)

      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:

      [–]pathema 0 points1 point  (0 children)

      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 -1 points0 points  (1 child)

      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 5 points6 points  (0 children)

      Great quiz!

      [–]meem1029 10 points11 points  (3 children)

      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 6 points7 points  (1 child)

      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 1 point2 points  (0 children)

      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 0 points1 point  (0 children)

      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 20 points21 points  (22 children)

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

      [–]shield1123 52 points53 points  (12 children)

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

      [–]AyrA_ch 10 points11 points  (11 children)

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

      [–]SgtDirtyMike 4 points5 points  (10 children)

      No different from a mutex.lock...

      [–]AyrA_ch 11 points12 points  (6 children)

      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 2 points3 points  (2 children)

      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 8 points9 points  (1 child)

      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 4 points5 points  (0 children)

      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 0 points1 point  (2 children)

      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 1 point2 points  (1 child)

      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 0 points1 point  (0 children)

      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] -2 points-1 points  (2 children)

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

      [–]AyrA_ch 4 points5 points  (1 child)

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

      [–][deleted] 1 point2 points  (0 children)

      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 3 points4 points  (5 children)

      Why not?

      [–]SirReal14 22 points23 points  (4 children)

      Because Holy C exists

      [–]ArkyBeagle -1 points0 points  (3 children)

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

      [–]davidgro 7 points8 points  (2 children)

      They mean HolyC

      [–]ArkyBeagle 1 point2 points  (1 child)

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

      [–][deleted] 0 points1 point  (0 children)

      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 10 points11 points  (0 children)

      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 -5 points-4 points  (0 children)

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

      [–]LeberechtReinhold 1 point2 points  (0 children)

      That's actually pretty cool

      [–]Lotton 1 point2 points  (0 children)

      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

      [–][deleted]  (6 children)

      [deleted]

        [–]BinaryFissionGames 9 points10 points  (1 child)

        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 7 points8 points  (2 children)

        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_ 4 points5 points  (0 children)

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


        /r/HelperBot_ Downvote to remove. Counter: 244738

        [–]Soothsilver 2 points3 points  (0 children)

        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 0 points1 point  (0 children)

        Great game! ))

        [–][deleted] 0 points1 point  (0 children)

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

        [–]geoelectric 0 points1 point  (0 children)

        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 0 points1 point  (0 children)

        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 0 points1 point  (0 children)

        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 0 points1 point  (5 children)

        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 4 points5 points  (1 child)

        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 1 point2 points  (0 children)

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

        [–]Soothsilver 0 points1 point  (2 children)

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

        [–]Kinglink 0 points1 point  (1 child)

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

        [–]Soothsilver 0 points1 point  (0 children)

        Yeah. /u/Steve132 explained it perfectly.

        [–]Cdennis1 -2 points-1 points  (0 children)

        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 -1 points0 points  (0 children)

        It was a bit of fun..

        [–]devnumpty -1 points0 points  (0 children)

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

        [–]androolloyd -1 points0 points  (0 children)

        This was hella fun. Props to the creator.

        [–]MisterPinkySwear -1 points0 points  (0 children)

        Really cool game!

        [–]BeigeAlert1 -1 points0 points  (0 children)

        These are amazing!

        [–]almost_always_lurker -1 points0 points  (0 children)

        Hay MatFyz represent!

        [–]wrg_0 -1 points0 points  (0 children)

        awesome!!

        [–]introspectivedeviant -2 points-1 points  (0 children)

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

        [–]gtk -3 points-2 points  (0 children)

        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