5 ms·

Maybe someone can educate me. I've studied them for a while, but I don't get the fascination with lock- or wait-free queues. If you actually care about real-t

Maybe someone can educate me. I've studied them for a while, but I don't get the fascination with lock- or wait-free queues. If you actually care about real-time guarantees enough to look into lock-free solutions, you already ought to have non-preemptive workers (i.e. cooperative multitasking). This then allows you to have only one queue per CPU (since exclusive access is guaranteed), simplifying the problem. With one queue per CPU, multi-producer becomes trivial (atomic doorbell + round robin), and multi-consumer is easy (CAS to acquire a work item). You don't have fairness guarantees for consumers, but who cares, only when they are not saturated can they not be fair and then that's a good thing. Application stalls don't happen (one non-preemptible queue per CPU), application crashes are managed at a higher level, and IRQs can be disabled for the 5 cycles you spend in the critical sections. I assume I'm missing something, since I'm somewhat new at this, and lock-freedom is clearly in vogue, but I don't know what it is.

kitsuac 10y ago
Cooperative multi-tasking doesn't always mean a per-worker queue is feasible. Really the only time I could see that being feasible is if the work queue is constantly saturated. Often times you just don't know in advance which worker to queue up with which task.
- colanderman 10y ago
  I mean to choose a queue by producer, not consumer.
eloff 10y ago
Go is a language exactly like that, but I still use lock free algorithms. The reason is even with a private per thread data structure you don't have atomic higher level operations like enqueue. So you need to disable interrupts around the data structure methods, both for the OS and the Go runtime. That will cost you more than a lock would, and afaik it's not possible from userspace on Linux (if it is I would love to know how!)
beagle3 10y ago
> If you actually care about real-time guarantees enough to look into lock-free solutions, lock free does not give any real time guarantee for any specific task (and neither does wait free, a much stronger and harder to achieve constraint) The reason I use it when I do, is that it guarantees that a problem in one thread/worker/process, e.g. a stall due to a database commit, does not make others stall as well. > (CAS to acquire a work item) Most likely, you've just described a lock free implementation. > I assume I'm missing something, since I'm somewhat new at this, and lock-freedom is clearly in vogue, but I don't know what it is. Lock freedom is the property that, at any instant, at least one thread/worker/process is making some progress independently of the others. It is a useful definitions because it doesn't care whether locks are explicit (e.g. mutex, semaphore, critical section) or implicit (polling or spinning or whatever)
ww520 10y ago
One lock-free queue is just simpler to work with than multiple queues. And the one queue nicely decouples the producers and the consumers, where they don't need to know each other's load and scheduling. > multi-producer becomes trivial (atomic doorbell + round robin) This implements all the work units consumes the same load for the consumers. Otherwise, the producer needs more logic to figure out which queue to enqueue. Accessing the consumers' statistics again becomes the problem of accessing shared data.
haberman 10y ago
If you can make your system lock-free, it will have a bunch of nice properties: - deadlock-free - obstruction-free (one thread getting scheduled out in the middle of a critical section doesn't block the whole system) - OS-independent, so the same code can run in kernel space or user space, regardless of OS or lack thereof (basically any lock besides a spin-lock needs OS support) These properties are especially nice if you are writing a library that you want to be as unassuming and unimposing as possible about the surrounding environment. Given two libraries, one that depends on locks and one that is lock-free, I'll go for the lock-free one if at all possible.
- MichaelMoser123 10y ago
  Are you sure that you get rid of deadlocks? Instead of a lock it loops on an atomic variable if there is some contention. Granted, you have some more control over the priority of tasks and it will be more efficient - if you are smart enough (still it gets very tricky), but the essence is that you are rolling your own locks with atomic variables.
  - gpderetta 10y ago
    > but the essence is that you are rolling your own locks with atomic variables. Such an algorithm wouldn't even be obstruction-free.
  - RossBencina 10y ago
    > Are you sure that you get rid of deadlocks? By definition, a lock-free algorithm guarantees at least one thread makes forward progress at each time step. So yes, there is no chance of deadlock. If you want to guarantee that all threads make progress per unit time, you need wait-free.
    - MichaelMoser123 10y ago
      there is the lock-free circular buffer, where the buffer is linear and the indexes are atomic variables; now once the buffer is full, the indexes act like locks - the producer can't insert anything unless the consumer removes entries, now the 'locks' have the crucial role in maintaining the data structure. what am i missing?
RossBencina 10y ago
Your architecture proposal seems sound assuming that you have that much control over the whole system, and you don't need to integrate with any legacy components. In the common case, you need to deal with limited control (e.g. in a userspace app) and you have legacy components (e.g. a consumer OS, a Java VM, etc). If you're doing best-effort soft-real-time on a consumer OS then you probably don't have control over thread affinity to _guarantee_ one thread per CPU, and you certainly can't disable IRQs. Even on servers, you can get Linux to set up your thread-per-CPU thing, but still no IRQ masking. Also, you'd need your whole stack to do cooperative multitasking in a fully composable way before you could do as you propose. Maybe that's plausible in Go, but if you're in Java (as a lot of the HFT people seem to be, for reasons I don't understand) then probably only _some_ of your system is structured as one-thread-per-CPU cooperative multitasking, and you may still need to offload high-latency work using lock-free queues. In my domain (real-time audio on desktop OSes), neither Windows nor macOS have working deterministic priority inversion mitigation. So using lock-free queues between priority domains (e.g. between GUI thread and real-time audio thread) avoids priority inversion risk (compared to using mutexes). Granted, this is a rather specialised use-case. Another reason people are interested in these things is that there's a perception that lock-free algorithms perform better for inter-thread queuing than the alternatives. In particular, there are claims that they scale better when there are a large number of producer and consumer threads/cores. I think this is the most controversial area, since the queue algorithms may scale better than e.g. a single mutex on a single queue, but it's not necessarily the case that an application architecture that uses a MPMC queue is the best fit for purpose.
- valarauca1 10y ago
  If you're doing best-effort soft-real-time on a consumer OS then you probably don't have control over thread affinity to _guarantee_ one thread per CPU Which consumer OS? FreeBSD, OpenBSD, Linux, and Windows all offer the functionality. To my knowledge MacOS is the only consumer OS that doesn't. and you certainly can't disable IRQs This has been in Linux for over a decade. You can modify IRQ affinity from the root shell via the proc-fs [1]. [1] https://www.kernel.org/doc/Documentation/IRQ-affinity.txt https://www.kernel.org/doc/Documentation/IRQ-affinity.txt
sleepingeights 10y ago
A real-time OS/app wouldn't benefit even with a 5 cycle Crit-section. Most, if not all, "true" real-time OSes require "real-time" data coming in from IRQs. Sure, there can be some complex synchronization if an IRQ line requires a certain number of cycles to read/write data where some queue logic can happen.
mfukar 10y ago
Real time systems with preemption exist. Non-preemption is not always a feasible choice - its disadvantages are too many.
gpderetta 10y ago
One benefit of wait free algorithms is that allow realtime threads to communicate with non-realtime threads without risking unbounded waits. Similarly priority inversion is no longer an issue.
adekok 10y ago
> Maybe someone can educate me. I've studied them for a while, but I don't get the fascination with lock- or wait-free queues. Let's say you're running a multi-threaded program. The threads (at some point) need to talk to each other. Perhaps to exchange data. The simplest solution is to use a mutex. It's simple. Just take your existing single-threaded queue / list / tree code, and slap a mutex around it. Maybe 10 lines of code changed. It will work. Then you do profiling... you discover that when 30 threads exchanged 10's of 1000's of messages per second, mutex contention is a huge problem. You can easily have 30% of wall-clock time spent waiting for contented mutexes. When you move to lock-free algorithms, you give up a little, and gain a lot. If you're willing to relax some requirements, even better. e.g. I care that the other thread gets a message... but it doesn't have to be now. It could be a millisecond in the future. A lock-free queue means that you can just dump messages to another thread, and they'll show up in the other thread. (Eventually, when it gets around to looking at the queue). And mutex contention does way down. Especially because you're no longer using mutexes! There can still be some contention on CAS in lock-free algorithms, especially for MPMC queues. The solution there (as is done in the linked project) is to move to single-producer single-consumer queues as much as possible. The contention goes down to pretty much zero, and performance goes up. I've spent a good chunk of the last few months re-designing the core of FreeRADIUS to avoid mutexes, shared memory, etc. The old code would get ~40K packets/s with multiple highly contended mutexes. The new test code is getting 3-4M packets/s with a lock-free queue / message passing system. i.e. mutexes were killing performance in the old system. They're gone in the new system. And performance is substantially higher.

kitsuac 10y ago

Cooperative multi-tasking doesn't always mean a per-worker queue is feasible. Really the only time I could see that being feasible is if the work queue is constantly saturated. Often times you just don't know in advance which worker to queue up with which task.

colanderman 10y ago
I mean to choose a queue by producer, not consumer.

eloff 10y ago

Go is a language exactly like that, but I still use lock free algorithms. The reason is even with a private per thread data structure you don't have atomic higher level operations like enqueue. So you need to disable interrupts around the data structure methods, both for the OS and the Go runtime. That will cost you more than a lock would, and afaik it's not possible from userspace on Linux (if it is I would love to know how!)

beagle3 10y ago

> If you actually care about real-time guarantees enough to look into lock-free solutions, lock free does not give any real time guarantee for any specific task (and neither does wait free, a much stronger and harder to achieve constraint) The reason I use it when I do, is that it guarantees that a problem in one thread/worker/process, e.g. a stall due to a database commit, does not make others stall as well. > (CAS to acquire a work item) Most likely, you've just described a lock free implementation. > I assume I'm missing something, since I'm somewhat new at this, and lock-freedom is clearly in vogue, but I don't know what it is. Lock freedom is the property that, at any instant, at least one thread/worker/process is making some progress independently of the others. It is a useful definitions because it doesn't care whether locks are explicit (e.g. mutex, semaphore, critical section) or implicit (polling or spinning or whatever)

ww520 10y ago

One lock-free queue is just simpler to work with than multiple queues. And the one queue nicely decouples the producers and the consumers, where they don't need to know each other's load and scheduling. > multi-producer becomes trivial (atomic doorbell + round robin) This implements all the work units consumes the same load for the consumers. Otherwise, the producer needs more logic to figure out which queue to enqueue. Accessing the consumers' statistics again becomes the problem of accessing shared data.

haberman 10y ago

If you can make your system lock-free, it will have a bunch of nice properties: - deadlock-free - obstruction-free (one thread getting scheduled out in the middle of a critical section doesn't block the whole system) - OS-independent, so the same code can run in kernel space or user space, regardless of OS or lack thereof (basically any lock besides a spin-lock needs OS support) These properties are especially nice if you are writing a library that you want to be as unassuming and unimposing as possible about the surrounding environment. Given two libraries, one that depends on locks and one that is lock-free, I'll go for the lock-free one if at all possible.

MichaelMoser123 10y ago
Are you sure that you get rid of deadlocks? Instead of a lock it loops on an atomic variable if there is some contention. Granted, you have some more control over the priority of tasks and it will be more efficient - if you are smart enough (still it gets very tricky), but the essence is that you are rolling your own locks with atomic variables.
- gpderetta 10y ago
  > but the essence is that you are rolling your own locks with atomic variables. Such an algorithm wouldn't even be obstruction-free.
- RossBencina 10y ago
  > Are you sure that you get rid of deadlocks? By definition, a lock-free algorithm guarantees at least one thread makes forward progress at each time step. So yes, there is no chance of deadlock. If you want to guarantee that all threads make progress per unit time, you need wait-free.
  - MichaelMoser123 10y ago
    there is the lock-free circular buffer, where the buffer is linear and the indexes are atomic variables; now once the buffer is full, the indexes act like locks - the producer can't insert anything unless the consumer removes entries, now the 'locks' have the crucial role in maintaining the data structure. what am i missing?

RossBencina 10y ago

Your architecture proposal seems sound assuming that you have that much control over the whole system, and you don't need to integrate with any legacy components. In the common case, you need to deal with limited control (e.g. in a userspace app) and you have legacy components (e.g. a consumer OS, a Java VM, etc). If you're doing best-effort soft-real-time on a consumer OS then you probably don't have control over thread affinity to _guarantee_ one thread per CPU, and you certainly can't disable IRQs. Even on servers, you can get Linux to set up your thread-per-CPU thing, but still no IRQ masking. Also, you'd need your whole stack to do cooperative multitasking in a fully composable way before you could do as you propose. Maybe that's plausible in Go, but if you're in Java (as a lot of the HFT people seem to be, for reasons I don't understand) then probably only _some_ of your system is structured as one-thread-per-CPU cooperative multitasking, and you may still need to offload high-latency work using lock-free queues. In my domain (real-time audio on desktop OSes), neither Windows nor macOS have working deterministic priority inversion mitigation. So using lock-free queues between priority domains (e.g. between GUI thread and real-time audio thread) avoids priority inversion risk (compared to using mutexes). Granted, this is a rather specialised use-case. Another reason people are interested in these things is that there's a perception that lock-free algorithms perform better for inter-thread queuing than the alternatives. In particular, there are claims that they scale better when there are a large number of producer and consumer threads/cores. I think this is the most controversial area, since the queue algorithms may scale better than e.g. a single mutex on a single queue, but it's not necessarily the case that an application architecture that uses a MPMC queue is the best fit for purpose.

valarauca1 10y ago
If you're doing best-effort soft-real-time on a consumer OS then you probably don't have control over thread affinity to _guarantee_ one thread per CPU Which consumer OS? FreeBSD, OpenBSD, Linux, and Windows all offer the functionality. To my knowledge MacOS is the only consumer OS that doesn't. and you certainly can't disable IRQs This has been in Linux for over a decade. You can modify IRQ affinity from the root shell via the proc-fs [1]. [1] https://www.kernel.org/doc/Documentation/IRQ-affinity.txt https://www.kernel.org/doc/Documentation/IRQ-affinity.txt

sleepingeights 10y ago

A real-time OS/app wouldn't benefit even with a 5 cycle Crit-section. Most, if not all, "true" real-time OSes require "real-time" data coming in from IRQs. Sure, there can be some complex synchronization if an IRQ line requires a certain number of cycles to read/write data where some queue logic can happen.

mfukar 10y ago

Real time systems with preemption exist. Non-preemption is not always a feasible choice - its disadvantages are too many.

gpderetta 10y ago

One benefit of wait free algorithms is that allow realtime threads to communicate with non-realtime threads without risking unbounded waits. Similarly priority inversion is no longer an issue.

adekok 10y ago

> Maybe someone can educate me. I've studied them for a while, but I don't get the fascination with lock- or wait-free queues. Let's say you're running a multi-threaded program. The threads (at some point) need to talk to each other. Perhaps to exchange data. The simplest solution is to use a mutex. It's simple. Just take your existing single-threaded queue / list / tree code, and slap a mutex around it. Maybe 10 lines of code changed. It will work. Then you do profiling... you discover that when 30 threads exchanged 10's of 1000's of messages per second, mutex contention is a huge problem. You can easily have 30% of wall-clock time spent waiting for contented mutexes. When you move to lock-free algorithms, you give up a little, and gain a lot. If you're willing to relax some requirements, even better. e.g. I care that the other thread gets a message... but it doesn't have to be now. It could be a millisecond in the future. A lock-free queue means that you can just dump messages to another thread, and they'll show up in the other thread. (Eventually, when it gets around to looking at the queue). And mutex contention does way down. Especially because you're no longer using mutexes! There can still be some contention on CAS in lock-free algorithms, especially for MPMC queues. The solution there (as is done in the linked project) is to move to single-producer single-consumer queues as much as possible. The contention goes down to pretty much zero, and performance goes up. I've spent a good chunk of the last few months re-designing the core of FreeRADIUS to avoid mutexes, shared memory, etc. The old code would get ~40K packets/s with multiple highly contended mutexes. The new test code is getting 3-4M packets/s with a lock-free queue / message passing system. i.e. mutexes were killing performance in the old system. They're gone in the new system. And performance is substantially higher.