Hacker News Reader

One trick I used to use when writing multithreaded java code for debugging purposes was to never use the built in synchronized/implicit object lock, since that made it quite difficult to understand from a stack trace what object was being locked. Instead, we would define an explicit inner lock and lock on that explicitly. The class name would then show up in stack traces making it much easier to track down.

In cases where not all operations on the objects necessitate the same lock semantics, this is also handy because you can split or nest locks to reduce write-blocks-read and read-blocks-write situations.

But if you're finding yourself using this more than a couple of times in a project, you're probably uncovering violations of the Single Responsibility Principle. Especially if you're splitting locks.

One of my _favorite_ threading papers published in 1982, written by Andrew Birrell:

https://s3.amazonaws.com/content.udacity-data.com/courses/ud...

Reading about that paper in graduate school cleared up a lot of misconceptions I had about threads

But ... semaphores and queues are indeed very similar, and everything you said about a queue is also true for a semaphore. A queue has two fundamental operations:

    trait Queue<T> {
        fn push(t: T)
        fn pop() -> T    // waits until the queue isn't empty, then does the pop()
    }

A semaphore is is just a Queue where T is a constant (typically the unit type, which has zero size). Since it's always the the same thing there is no need to store the actual items as pop() can just create copies as needed, which also means push() can just discard it's argument. That means you can get away with just storing a count of how many items are in the queue, not the items themselves. Now rename:

    push --> signal
    pop --> wait

And bingo, we have a semaphore. Which also means if you are having difficulty reasoning about semaphores but find queues easy to think about, just reverse the name transformation above and semaphores become just as easy.

Rust exploits a similar equivalence with a mapping and a set: a set is just a mapping that maps every key to the unit type.

The other half of it is, thread blocking on a single queue. And system message queues being a debugger friendly concept (not just a declared local). Code discipline is 2/3 of the solution.

I mean that's a nice theoretical argument, but the empirical results are not so clear.

https://dl.acm.org/doi/10.1145/3297858.3304069

Surprisingly, our study shows that it is as easy to make concurrency bugs with message passing as with shared memory, sometimes even more. For example, around 58% of blocking bugs are caused by message passing.

...

Our study found that message passing does not necessarily make multithreaded programs less error-prone than shared memory. In fact, message passing is the main cause of blocking bugs. To make it worse, when combined with traditional synchronization primitives or with other new language features and libraries, message passing can cause blocking bugs that are very hard to detect.

I'd also add that in the modern world we've "solved" many multi-threading problems by splitting the queues and data stores out into multiple services. Now we don't have any threading problems - only "distributed system" problems, and if there's a bug there that's the architect's fault, not the programmer's!

Yeah so many services APIs are blocking, it's hard to keep threads non-blocking. Often there is a way, but you have to dig for it.

The results of concurrency bugs with message passing tend to be less bad than the results of concurrency bugs with semaphore/locking code; although this is often because message passing tends to not be shared memory semaphore/locking tends to be shared memory.

Blocking bugs are a service issue, but incorrect locking can lead to deadlock or unprotected writes that corrupt data.

Depending on what they mean by 'detect', I've found it's actually quite easy to detect blocking issues in a message passing environment (Erlang, specifically), if a process has a blocking issue, it will end up stuck waiting for a message that will never arrive; however its mailbox will be growing as new requests are added. Scanning for large mailboxes, as well as growing mailboxes is easily automated and detects the issue. Of course, that's runtime detection; it's hard to detect these with code analysis (because it's not exactly a code problem. It's a system problem, and the system is an emergent property of the running code, it's not explicitly described anywhere, at least in Erlang; this is simultaneously amazingly powerful and limiting)

Interesting - in other words you are saying that message passing concurrency bugs tends to result in liveness violations whereas locking bugs tend to violate safety?

Yeah, that's a nice restatement. Additionally, it's a lot easier to find liveness violations than safety violations. If your system deadlocks, it's obvious (not so much if it livelocks), and you can see which parts are deadlocked. If your system corrupts data, it's not always obvious, and even when it is obvious that there was corruption, it's not always obvious where it happened.

Although that's true, I found in the past that a pure queues/actors based approach didn't work well for some kinds of app. I had to introduce locks again and ended up with a hybrid solution.

The problem was that the app had a mix of low latency requests to access some parts of a large data structure, but the actor had to do a combination of fast and slow requests, so low latency requests would end up sitting in the queues for unacceptably long periods even when they needed access to only a small and stable part of the overall data. A related problem was the code size and complexity increase that came from having to make immutable snapshots of the underlying mutable data structures. Adding locking fixed all that and it didn't lead to any noticeable increase in bugginess. If anything the code was simpler, because the readers could simply access the data when it was in an immutable (locked) state, get what they needed and get out as quickly as possible, with RW locks ensuring good scalability and memory locality.

The actors approach also ran into circular deadlock when increasing the granularity of the actors, but unlike with locks there was no tooling support to find the issues (Guava has cycle-detecting lock classes).

The experience soured me on anything claiming to be a silver bullet for concurrency. It felt like the problems had been transformed into different shapes but not actually decreased in volume. Since then I use whatever approach feels intuitively right at the time.

I mostly agree with you, but it feels a bit handwave-y. That such bugs are less serious is maybe true for a particular class of idioms and a particular class of problems that, say, dominate CRUD application design.

Unsynchronized writes are also detectable at runtime, I would guess (having done no production Erlang work) with around the same order of false negatives as a stuck mailbox. TSan will only find the race if it occurs relatively close temporally; mailbox scanning will only find the stuck message if the send rate is sufficiently high. TSan is a lot more expensive but can be productively used during test suites. Mailbox scanning seems likely to fire false positives and only works in a complete running system.

In the end, only simpler program design can save us.

the only model I use with threads is either pre-static (start a function on each thread with unique parameters, result is returned to a driving function at the end) or message-queue (each thread is blocking, waiting for a message). For the former, I use shared memory, but it's read only and guaranteed to live longer than any of the worker threads that use it (passing a consted ref_ptr). For the latter, I don't share any memory at all; the message itself contains the parameters, fully materialized.

I can ensure all my queues are loop-free (directed acyclic graph of workers reading from their parent nodes and writing to their children nodes). IIRC one of the complaints about the petri net model is that it was unprovable that any problem could finish, even trivial ones.

This has worked pretty well for me and I usually don't have to debug any truly nasty thread problems. My biggest problem tends to be thread pools where one of the workers gets wedged, and there's no way to cleanly kill the worker thread and steal the work onto another thread.

Particularly network activity! At the lowest levels the creaky old TCP/IP stack not amenable to non-blocking.

> I favor a multi-threading environment of threads dedicated to queues, and all the queues visible to the debugger. That kind of setup has never done me dirty.

This is a basic description of Erlang, and by extension elixir, gleam, caramel, etc.

Plus at least some of them get default access to (useful for 80% of use cases) implementations of backpressure, deadlock timeouts, etc.

This sounds interesting and I've implemented simple ideas similar to the pattern you describe before, however I haven't read about its use in depth. Do you happen know of an article/book/resource that describes this along with real world experiences? If not, would you mind writing a blog post or article on it please?

I had the benefit of cutting my teeth at my first job, working on a message-passing OS. CTOS, based on RMX/86 used messages for everything. It was a very early networked computing system. Diskless workstations where file messages simply got forwarded to a server etc. And all the messages and queues were visible in the debugger!

So I learned good thread hygiene right out of school.

I favor that too, but lock free algorithms can in some cases perform perform enough better in the real world.

I've also had to implement my own message queue based on lock free to get data out of an implement handler.

Dining philosophers is solved by always acquiring locks in the same order.

...if it's possible to do that for your application! It isn't always, if what lock you need next depends on the value of a previously locked value.

Right, perhaps in a nested call or library, maybe even a semaphore you didn't know about!

Multithreading with semaphores/locks is about as dirty as it can get.

The top level comments strategy with queues seems similar, in that it isn't always possible. It requires the queues form a DAG, which is another word for partial ordering. Thus, requiring the locks form a partial ordering doesn't seem like a comparatively excessive restriction.

> doesn't seem like a comparatively excessive restriction

I think there are some applications and algorithms that we just don't know a way to create an ordering for realistically fine-grained locks.

For example airline seat reservation. Someone clicking on seats to reserve them. You can't apply locks in a total order because... you can't read the person's mind on what seat they're going to click next.

Or Lee's algorithm.

(I wrote the first half a PhD on this.)

https://chrisseaton.com/research-symposium-2012/seaton-irreg...

You don't need a DAG. It's fine to have a complete graph!

I favor a multi-threading environment of threads dedicated to queues, and all the queues visible to the debugger. That kind of setup has never done me dirty.

You mean like Go does with channels? (Not sure how good their visibility is to the debugger though.)

Probably more like Elixir/Erlang, if we're talking programming language. Though even there, BEAM processes are the unit of execution, and are multiplexed on threads. Parent references OS development elsewhere.

Go has a couple of deviations; channels aren't queues unless you are careful to size them > the number of things you'll ever put in them (else the thing trying to put something on a channel deadlocks; you can of course timeout on it, but it presents tight coupling in that case, the goroutine sending has to care about the state of the thing receiving), goroutines aren't dedicated to channels (that is, there is an m-n relationship between channels and goroutines which can lead to a lot of incidental complexity), and, you can see what is on a channel if you have a breakpoint, but that assumes you can get the code to break inside of something containing a reference to the channel.

It's based on Tony Hoare's Communicating Sequential Processes, and is far more comprehensible and possible to reason about than primitives like mutexes and semaphores that are too close to the underlying hardware implementation.

http://www.usingcsp.com

its a _little_ more costly depending, but otherwise I agree with you. it also clearly delineates what data is shared and everything else can be assumed private...so it helps make the overall architecture more explicit