Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Deadlock Empire: An Interactive Guide to Locks

deadlockempire.github.io

Post reply on HN
Print view View original

21–30 of 44 posts

Re: The Deadlock Empire: An Interactive Guide to Locks

#21

Post by tialaramex »

Emjayen wrote: post #7
throwup238 wrote: post #2

My main takeaway from this excellent guide is that I suck at multithreaded reasoning and should stick to single threaded languages. There go my dreams of being a C-slinging kernel ninja master.

If it's any consolation: the vast, vast majority programmers should stick to single-threaded design, as is evident from all the atrocious multithreaded software out there of which 99% of the time would be faster without multiple threads (and surely far less complex) Unless you know what you're doing, just pick the real low-hanging fruit, like throwing some threads at file block decompression.

It so happens, even though I don't like C++ that I entirely agree with the rationale behind the C++ 26 introduction of structured concurrency to the language.

About sixty years ago structured control flow was rare or non-existent in most languages. Want to do X fifteen times? Well, try setting a counter N to zero, do X, increment the counter N, and if N is less than fifteen jump back to the start of your "do-X" routine. Simple.

Oh wait, sorry, somebody else who wanted to do X is also jumping to the start of that routine, and they didn't set N so now everything is on fire.

Today your programming language has structured control flow. You write a loop, the loop does X fifteen times, it's not possible for some unrelated code to just wander into part of your loop unsuspecting and cause mayhem since it wasn't prepared to count up to fifteen. New keywords appeared like "for" and "while" and "return". It's not that somehow a new tool magically fixed the problem, but instead programmers learned to write software in a more structured way using the better tools.

Structured concurrency is the same idea again, but for concurrency.

It took some time between Dijkstra writing a letter and languages delivering the nice for-each loop we're familiar with today in many languages, and so likewise what we have today as the state of the art for structured concurrency is likely nowhere close to what will be developed over coming decades, but it's already nicer to work with that the chaos of unstructured concurrent programming.

Re: The Deadlock Empire: An Interactive Guide to Locks

#22

Post by jstimpfle »

YZF wrote: post #8
throwup238 wrote: post #2

My main takeaway from this excellent guide is that I suck at multithreaded reasoning and should stick to single threaded languages. There go my dreams of being a C-slinging kernel ninja master.

I'll give you one tip that covers a large portion of deadlocks I've seen in my career. A lock should be used to lock a data structure, that's it. Corollary: Never hold a lock while calling a function. Most common deadlocking scenario is people taking a lock, calling a function, that they don't know takes a different lock. If you can't get by just taking a lock, touching some data structure (lightly), and releasing th…

That sounds good in principle but is it practical? As long as you have something to do while holding the lock, chances are that implementing that something requires calling a function. That or code duplication.

Re: The Deadlock Empire: An Interactive Guide to Locks

#23

Post by jstimpfle »

tialaramex wrote: post #20
loeg wrote: post #15

Earlier quoted context omitted.

> The big win in Rust is that the mutexes are tied to the data they protect. The compiler won't let you access data until it's locked. You can get this kind of behavior in C++ with, e.g., folly::Synchronized .

Rust's borrow checker will of course check that if you borrowed the protected item you've given it back before unlocking, whereas all Folly and similar C++ libraries can do here is caution you that this footgun exists and is loaded and pointed at your foot so please don't.

That's just the usual resource ownership management problem that Rust is supposed to solve.

But a simple templated type like GP proposed does indeed fix the issue discussed here. To access the thing in the first place you need to lock the correct mutex. Looking at Folly::Synchronized, locking doesn't even return the protected item itself directly. In most cases -- unless the bare pointer is needed -- you will access the item through the returned "locked view" object which does the unlocking in its destructor.

Re: The Deadlock Empire: An Interactive Guide to Locks

#24

Post by g15jv2dp »

throwup238 wrote: post #2

My main takeaway from this excellent guide is that I suck at multithreaded reasoning and should stick to single threaded languages. There go my dreams of being a C-slinging kernel ninja master.

The problem with almost every example, as far as I can tell, stems from variables having multiple writers without being properly locked.

Re: The Deadlock Empire: An Interactive Guide to Locks

#25

Post by tialaramex »

jstimpfle wrote: post #23
tialaramex wrote: post #20

Earlier quoted context omitted.

Rust's borrow checker will of course check that if you borrowed the protected item you've given it back before unlocking, whereas all Folly and similar C++ libraries can do here is caution you that this footgun exists and is loaded and pointed at your foot so please don't.

That's just the usual resource ownership management problem that Rust is supposed to solve. But a simple templated type like GP proposed does indeed fix the issue discussed here. To access the thing in the first place you need to lock the correct mutex. Looking at Folly::Synchronized, locking doesn't even return the protected item itself directly. In most cases -- unless the bare pointer is needed -- you will access…

Sure, Rust "just" enforces type safety. But without type safety a type can't help us much more than the textual advice did so I think that's a really big difference, especially at scale.

In a small problem the textual advice is enough, I've written gnarly C with locks that "belong" to an object and so you need to make sure you take the right lock before calling certain functions which touch the object. The textual advice (locks are associated with objects) was good enough for that code to be correct -- which is good because C has no idea how to reflect this nicely in the language itself nor does it have adequate type safety enforcement.

But in a large problem enforcement makes all the difference. I had maybe two kinds of lock, a total of a dozen functions which need locking, it was all in my head as the sole programmer on that part of the system. But if we'd scaled up to a handful of people working on that code, ten kinds of lock, a hundred functions needing locking I'd be astonished if it didn't begin to have hard to debug issues or run into scaling challenges as everybody tries to "keep it simple" when that's no longer enough.

Re: The Deadlock Empire: An Interactive Guide to Locks

#26

Post by mrkeen »

lordnacho wrote: post #19

This thing is great. The deeper lesson seems to be not to try any of these things in any kind of complicated program, you will fuck it up. Imagine writing something with dozens of threads, each running different programs with various threading primitives sprinkled around. You would never be able to debug it, because just conjuring each case of "if this thread gets to here and that thread gets to there" in a test woul…

In the mainstream languages, synchronisation seems to be a means (locking code) to an end (locking data).

The programmer usually does not care that only one thread can enter a method at a time - that's just the 'how'. The 'why' is that the programmer wants to reason about reads and writes in a multithreaded environment as easily as one would do in a single-threaded environment.

Compare lock management to memory management. Method synchronisation is analogous to using stack variables - you don't have to do the work manually, but you can't work across method boundaries.

Manually locking/unlocking a resource is analogous to malloc and free. It's prone to error, unless you adopt draconian rules preventing flexibility.

What's the GC of lock management?

Re: The Deadlock Empire: An Interactive Guide to Locks

#27

Post by zbentley »

mrkeen wrote: post #26
lordnacho wrote: post #19

This thing is great. The deeper lesson seems to be not to try any of these things in any kind of complicated program, you will fuck it up. Imagine writing something with dozens of threads, each running different programs with various threading primitives sprinkled around. You would never be able to debug it, because just conjuring each case of "if this thread gets to here and that thread gets to there" in a test woul…

In the mainstream languages, synchronisation seems to be a means (locking code) to an end (locking data). The programmer usually does not care that only one thread can enter a method at a time - that's just the 'how'. The 'why' is that the programmer wants to reason about reads and writes in a multithreaded environment as easily as one would do in a single-threaded environment. Compare lock management to memory manag…

Channel-based programming, perhaps? From Go style to Erlang shared-nothing, those approaches offer some of the properties you’re looking for.

Or maybe the holy grail hasn’t been created yet in this category: a compiler that can transform arbitrary computations or expressions of computational goals into their maximally parallel form, where locks etc. are compiler output artifacts a la assembly instructions rather than things programmers regularly interact with. Some academic languages and frameworks have made strides in this direction, but I don’t know of any that have caught on.

Re: The Deadlock Empire: An Interactive Guide to Locks

#28

Post by neonsunset »

mrkeen wrote: post #26
lordnacho wrote: post #19

This thing is great. The deeper lesson seems to be not to try any of these things in any kind of complicated program, you will fuck it up. Imagine writing something with dozens of threads, each running different programs with various threading primitives sprinkled around. You would never be able to debug it, because just conjuring each case of "if this thread gets to here and that thread gets to there" in a test woul…

In the mainstream languages, synchronisation seems to be a means (locking code) to an end (locking data). The programmer usually does not care that only one thread can enter a method at a time - that's just the 'how'. The 'why' is that the programmer wants to reason about reads and writes in a multithreaded environment as easily as one would do in a single-threaded environment. Compare lock management to memory manag…

In the context of C#, most code does not actively share mutable state even if it's vastly concurrent and/or parallel via Tasks or explicit threading.

In case the state is still shared, most common scenarios are usually addressed by applying concurrent data structures (ConcurrentDictionary/Stack/Queue) or using a barrier/semaphoreslim.

In case where more complex mutable state must be shared in a non-thread-safe way, it is nowadays easily addressed by using Channel where a single reader owns the instance of a particular class and handles concurrently submitted requests in a serialized way.

Otherwise, I agree that correctly writing non-blocking code or code with granular locking strategy is extremely non-trivial, and the state space that must be handled for even most trivial cases is enormous and makes my head hurt.

Some scenarios can be addressed by https://github.com/microsoft/coyote which simplifies the task, but it is still challenging.

Other than above, there exists an F# implementation of Concurrent ML that solves the problem in a CSP-style fashion, similar to Channel above: https://github.com/Hopac/Hopac/blob/master/Docs/Programming....

Re: The Deadlock Empire: An Interactive Guide to Locks

#29

Post by cjfd »

Hmmmm.... I think the general lesson here is to use concurrency classes the way they are intended as opposed to the way they are not intended. I mean, more or less every code example here is clearly wrong and completely counter to how these classes should be used. Also, don't make things complicated. If your use of concurrency is complicated the chances of being incorrect are about 1000%.
Post reply on HN