Measuring mutexes, spinlocks and how bad the Linux scheduler is

> SCHEDULING

> high-priority= Renice the daemon after startup to become a high-priority process. This a good idea if you experience drop-outs during playback. However, this is a certain security issue, since it works when called SUID root only, or RLIMIT_NICE is used. root is dropped immediately after gaining the nice level on startup, thus it is presumably safe. See pulseaudio(1) for more information.

> Takes a boolean argument, defaults to yes. The --high-priority command line option takes precedence.

> realtime-scheduling= Try to acquire SCHED_FIFO scheduling for the IO threads. The same security concerns as mentioned above apply. However, if PA enters an endless loop, realtime scheduling causes a system lockup. Thus, realtime scheduling should only be enabled on trusted machines for now. Please note that only the IO threads of PulseAudio are made real-time. The controlling thread is left a normally scheduled thread. Thus enabling the high-priority option is orthogonal. See pulseaudio(1) for more information.

> Takes a boolean argument, defaults to yes. The --realtime command line option takes precedence.

That seems unlikely to me and doesn't match any experience I've ever had or known anyone to have. Can you explain what you mean by that?

Speaking of which, do you know of a tool that would allow to ensure that e.g. your RT threads won't do bad things - short of putting a breakpoint on every syscall-like thing ? I wonder if at that point the audio community should not look into developing some clang-based static analyzer to enforce that.

Plus highly contended critical sections should really really be avoided. So I'm not sure the author's benchmark even make any sense: if all of your workload is serialized, use a single thread.

Spinlocks assume the critical section is fast and non-blocking, so when the spinning lasts longer than expected, throwing in a yield can help by handing some CPU time to something else.

The lock-holder might be getting scheduled on the same CPU and waiting for this thread to yield, or there might just be excessive threads runnable right now and burning cycles pointlessly spinning isn't helping get the lock-holder to run and release the lock any sooner.

In a situation where you have exactly as many threads as there are CPUs, and they've been assigned their own respective CPUs, and there's nothing else running on the system, I wouldn't expect the yield to help. But that ideal isn't how things generally look in practice.

I think your characterization of sched_yield() is a bit off. The man page is clear:

"sched_yield() causes the calling thread to relinquish the CPU. The thread is moved to the end of the queue for its static priority and a new thread gets to run."

and

"If the calling thread is the only thread in the highest priority list at that time, it will continue to run after a call to sched_yield()."

In particular, it does not say "I’m not actually waiting for anything visible to the scheduler and, um, run me again soon maybe?".

So assuming that the threads are running at some relatively high priority, I'm struggling to see how delays on the order of 60ms could arise.

EDIT: reading further:

"sched_yield() is intended for use with real-time scheduling policies (i.e., SCHED_FIFO or SCHED_RR). Use of sched_yield() with nondeterministic scheduling policies such as SCHED_OTHER is unspecified and very likely means your application design is broken."

So maybe that's it.

[1] http://man7.org/linux/man-pages/man2/sched_yield.2.html

A mutex can also refer to a particular group of “mutual exclusion” methods where in the current process/thread is suspended until the condition is true.

Hope this helps.

The difference is actually in the implementation of the mutual exclusion. A mutex is generally a system call which often starts as a spin lock before the system call is invoked (which is an assembly routine that changes the process privilege level and cedes control to the host operating system). A spinlock literally "spins" in a loop until an atomic flag or semaphore indicates that it can enter the protected region. When it does, it atomically sets the flag so that it has exclusive access. Because a spinlock does not interact directly with the OS scheduler, it needs a pause instruction or yield syscall at some point in its loop (or every few interations). Failure to do so introduces pathological scheduling problems as outlined in the article.

Spinlocks are sometimes used because it is believed that the odds of a collision are very low, and the cost of a syscall is perceived as being high to the developer. However, it's something that should only be used if you know what you're doing, and its behavior is subject to not only the OS, but also the hardware you run on.

Problem

1. We have a process with multiple threads of execution (e.g. A and B).

2. A and B will at some point act on the same data or object state.

3. Both A and B can't operate on the same data at the same time.

Mutexes function more or less as locks. They lock up your data to prevent unwanted race conditions. In multithreaded environments, a thread of execution has to acquire a mutex prior to accessing the data. Once it's done operating on the data, it releases the mutex so that another thread of execution can acquire it.

Mutexes are again, simply locks. But not all locks are the same. Locks come in different shapes and sizes and work in different ways. Same with mutexes, they can have different semantics.

Spinlocks are a kind of mutex that cause threads trying to acquire them to spin or loop around while waiting for the resource to be available.

Spinlock is a mutex algorithm based on spinning until the mutex is available.

Mutex is a MUTual EXclusion abstraction. A spinlock is one implementation. But spinlocks are problematic (for lots of reasons) so most of the time when someone says they’ve got a mutex it’s actually an adaptive lock:

- It has a fast path to acquire the lock.

- It may or may not be fair.

- It has a slow path that may enqueue the thread and deschedule it, but that slow path may have some adaptive spinning for a finite amount of time.

The spinlocking child will react to his arrival faster, but the sleeping (mutex) child makes a more efficient use of your attention.

Of course you can roll your own proper mutex if you want to get your hands dirty with futexes. IIRC you only need two bits (one waiter bit and one locked bit).

What "longest wait" measures is (b_i - a_i) in:

    Time a_0
    lock
    Time b_0
    unlock
    Time a_1
    lock
    Time b_1
    unlock
    ...

    lock
    Time a_0
    unlock
    lock
    Time b_0
    Time a_1
    unlock
    lock
    Time b_1
    ...

The fact that the timings are supposedly different on a millisecond scale is therefore quite suspicious.

Perhaps the chosen clock ends up calling a syscall, which can end up in the scheduler on syscall return occasionally and throw off the measurements that way? Or just the fact that there's one extra syscall in the critical section sometimes causes other threads to make different yielding decisions which throws off the scheduling?

More generally, it would have been great to see a deeper investigation into scheduling behavior, which is possible on Linux using the tracing infrastructure and visualizing with different tools like Hotspot.

Getting a worst-case delay of ~1.5ms with a naive ticket_spinlock that can yield is really not surprising, to be honest. All it takes is for patterns like:

1. 3 threads pull their tickets in order. 2. The middle thread yields and something else is chosen to run by the scheduler, or perhaps the scheduler decides not to run anything for a short while on the off-chance that something else becomes runnable, which is a fair choice because after all, you yielded. 3. The last thread is then blocked by the middle thread.

It just boils down to the fact that "yield" is a bad primitive. You should fall back to futex-based synchronization instead so that the kernel has a better idea of what you're trying to do. The article comes to the same conclusion anyway, in the form of "just use std::mutex".

That said, his conclusion is in fact just as you stated, if you read in between the lines. (This paper is really about the scheduler, so it's not exactly that conclusion.)

Sigh. From the article itself:

> I hope to have convinced you to avoid spinlocks, even for very short sections. Spinlocks are only a benefit if you really really care about the fast path and are certain that the lock will essentially always be free to take. On my computer the fast path on a spinlock is roughly 7ns and on a mutex it’s roughly 14ns, so both of those numbers are very fast. But when spinlocks go bad, the scheduler can be really confused, at least on Linux.

If you have a simple REST web server, single-thread is simply not a realistic option. The next simplest thing is to do shared memory parallelism, which works perfectly for a few dozens to low hundreds of threads. That already covers a lot of scale for many realistic problems. Moving from that to a distributed system design is a significant jump in implementation complexity, and will likely increase per-request latency with most straight-forward implementations.