4 ms·

There was a paper long ago that showed duality between semaphore/locking code and message-queuing code. So folks figured they were the same. Not so! semaphore/

There was a paper long ago that showed duality between semaphore/locking code and message-queuing code. So folks figured they were the same. Not so! semaphore/locking is very hard if more than one semaphore exists. Look at the 'dining philosophers problem' and so on. But queuing! Done right, that can be proved correct through static analysis. Do threads that consume one queue, block on another queue? Draw the graph of queue-blocking - does it loop anywhere? Then you could have a problem. I.e. if your message-consumers don't block at all, then you cannot have a problem with deadlock. You CAN have a problem with messages stalling however - languishing on a list waiting for something to complete that might never complete. But at runtime this can be debugged fairly easily - if all your queues are visible to the debugger. In the semaphore implementation, the locking situation depends on the state of threads and their stacks, which all have to be frisked and back-executed to find out who holds what lock etc. Not always debugger-friendly to do. 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.

Etheryte 4y ago
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?
- JoeAltmaier 4y ago
  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.
anonymousDan 4y ago
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.
- hinkley 4y ago
  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.
syrrim 4y ago
Dining philosophers is solved by always acquiring locks in the same order.
- deleted 4y ago
  [deleted]
- chrisseaton 4y ago
  ...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.
  - JoeAltmaier 4y ago
    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.
  - syrrim 4y ago
    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.
    - chrisseaton 4y ago
      > 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-irregular-parallelism-poster.pdf https://chrisseaton.com/research-symposium-2012/seaton-irreg...
    - anonymoushn 4y ago
itsmemattchung 4y ago
One of my _favorite_ threading papers published in 1982, written by Andrew Birrell: https://s3.amazonaws.com/content.udacity-data.com/courses/ud923/references/ud923-birrell-paper.pdf 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
convolvatron 4y ago
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
btilly 4y ago
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.)
- lostcolony 4y ago
  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.
- fmajid 4y ago
  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 http://www.usingcsp.com
dekhn 4y ago
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.
- JoeAltmaier 4y ago
  Particularly network activity! At the lowest levels the creaky old TCP/IP stack not amenable to non-blocking.
morelisp 4y ago
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 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!
- JoeAltmaier 4y ago
  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.
- toast0 4y ago
  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)
bluGill 4y ago
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.
throwawaymaths 4y ago
> 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.
rstuart4133 4y ago
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.
- JoeAltmaier 4y ago
  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.

Etheryte 4y ago

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?

JoeAltmaier 4y ago
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.

anonymousDan 4y ago

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.

hinkley 4y ago
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.

syrrim 4y ago

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

deleted 4y ago
[deleted]
chrisseaton 4y ago
...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.
- JoeAltmaier 4y ago
  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.
- syrrim 4y ago
  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.
  - chrisseaton 4y ago
    > 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-irregular-parallelism-poster.pdf https://chrisseaton.com/research-symposium-2012/seaton-irreg...
  - anonymoushn 4y ago

itsmemattchung 4y ago

One of my _favorite_ threading papers published in 1982, written by Andrew Birrell: https://s3.amazonaws.com/content.udacity-data.com/courses/ud923/references/ud923-birrell-paper.pdf 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

convolvatron 4y ago

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

btilly 4y ago

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

lostcolony 4y ago
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.
fmajid 4y ago
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 http://www.usingcsp.com

dekhn 4y ago

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.

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

morelisp 4y ago

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

JoeAltmaier 4y ago
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.
toast0 4y ago
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)

bluGill 4y ago

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.

throwawaymaths 4y ago

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

rstuart4133 4y ago

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.

JoeAltmaier 4y ago
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.