4 ms·

Deferred scheduling for user-space critical sections

60 points by signa11 3y ago

topspin 3y ago
Seems like a natural and necessary adaptation. This is fundamentally a consequence of the fact that today there are many cores. Kernel schedulers originated in a world where cores were precious and the kernel had to aggressively preclude user space from monopolizing them, and so no provision was made to allow user space to defer preemption. Hardware evolves faster than software.
- saagarjha 3y ago
  Needing to prevent applications from monopolizing the hardware is as necessary as it's ever been. The question is whether userspace can voluntarily promise that it'll be a good little process and behave in exchange for better performance, and corresponding penalties to institute for when that trust is broken.
hamilyon2 3y ago
Wow, this feels wrong way to do it. The way i see it, threads and processes waiting on some resource should be able to update some piece if metadata pointing to the thing they are waiting for. This will allow "donating" their priority and cpu share to the other process/thread. This can be a general mechanism, which can be incorporated in the things kernel already know, creating a chain of dependencies and giving priority to something at the end of chain.
- jorlow 3y ago
  I think you're describing traditional scheduling. The point is that sometimes overheads from cache thrashing and context switches are worse than just spinning.
  - hamilyon2 3y ago
    My information about locking and scheduling is dated and naiive. What is preventing per-thread structure of two identifiers "I am waiting for thing X, give it priority" and "I am in posession of X"? Identifiers are random numbers. System call is not necessary, some writable location is enough.
- gpderetta 3y ago
  > threads and processes waiting on some resource should be able to update some piece if metadata pointing to the thing they are waiting for This will allow "donating" their priority and cpu share to the other process/thread. That's what, for example, futexes are for. But the "donating" part can be expensive, so short spins can actually be beneficial for overall system efficiency.
EdSchouten 3y ago
I don't know how I should feel about changes like this. My concern with 'spinlocks in userspace' (i.e., locks that don't just call into the futex API when they run into contention) is that they merely try to optimize for their own performance. Sure, the futex API has more overhead, but it does mean that other processes on your system can run in the meantime. It's sort of similar to using a TCP congestion algorithm that's overly aggressive. Your own network connections might become faster as a result of them, but at the same time your flatmates won't be able to check their mail.
- saagarjha 3y ago
  Generally unbounded spins are terrible in userspace, but bounded spins as part of "hybrid" locks generally strike a good balance between performance and system impact. When a system call is hundreds or thousands of cycles it can be quite effective to try spending some fraction of that yourself if it'll get you the lock without the syscall. Like, not just from a pure throughput perspective: a yield to the kernel is not "free", it takes time just to park yourself. So it's good to make a gamble usually.
  - amelius 3y ago
    Could the implementation of the lock perhaps take the thread priority into account?
    - saagarjha 3y ago
      What would it do differently?
      - amelius 3y ago
        Give up earlier when the priority is low, so performance impact is low for low-priority threads.
dpc_01234 3y ago
Without digging into details: this seems like a a great idea. It's a cooperative, advisory optimization that can't really be gamed for permanent cpu time gain. A hint to scheduler that indicates that letting a process run just a tiny moment more might be good for overall system performance.
saagarjha 3y ago
This is an interesting idea. The core of it seems to be that the most efficient way to write locks today is to spin for a bit on contention, then yield to the kernel if you've been waiting to long. The goal, of course, is that if the lock is quickly released you don't take the full cost of a kernel call and can just keep going in userspace. Darwin's os_unfair_lock (and the closely related WebKit WTF::Lock) both use this strategy. Interestingly, XNU already has an implementation of this that is somewhat similar in spirit: preemption free zones (https://github.com/search?q=repo%3Aapple-oss-distributions%2Fxnu%20pfz&type=code https://github.com/search?q=repo%3Aapple-oss-distributions%2...). As far as I can tell os_atomic_lock does not use it for this purpose. Instead, it exists to allow OSAtomicFifoEnqueue/OSAtomicFifoDequeue to be lock-free, and in the typical Apple fashion solves the problem of "what if a userspace application uses this for evil" by implementing it in the kernel and mapping it via the commpage (think vDSO), so there isn't really any room for anyone but Apple to put code there. Apple being Apple, they could have absolutely added PFZ to os_atomic_lock (for themselves, of course). One wonders why they didn't; perhaps it just turns out that it isn't worth the complexity. (Look, I'm sorry all I talk about is Apple stuff, that's all I know.)
- spacechild1 3y ago
  > The core of it seems to be that the most efficient way to write locks today is to spin for a bit on contention, then yield to the kernel if you've been waiting to long. This is an old idea and many real-world mutex implementation have been doing this since forever. Some even let you configure the spin count: https://learn.microsoft.com/en-us/windows/win32/api/synchapi/nf-synchapi-initializecriticalsectionandspincount https://learn.microsoft.com/en-us/windows/win32/api/synchapi...
  - saagarjha 3y ago
    Yeah this is nothing new, I'm just saying that Linux is looking to service this better.
    - spacechild1 3y ago
      Alright, I was just tripping over the word "today", since this has already been true 20 years ago :)
weinzierl 3y ago
"This feature might seem like a way for a malicious thread to get more than its share of the available CPU time. The EEVDF scheduler that will be featured in the 6.6 kernel release, though, will note that a thread has gotten more than its share of CPU time and penalize it thereafter." This talks about fairness between threads, and is from my understanding also how the current CFS scheduler approaches fairness. I also understand that fairness on a process level might be difficult to obtain. But doesn't this thread level fairness render the point of a "malicous thread" moot? Fairness of threads within a process is pointless anyway, because this is all in the hands of the programmer and all they can do is shoot themselves in their own feet. Fairness between processes would be interesting but we don't have it anyway, so deferred scheduling doesn't make the situation worse in that regard?
samsquire 3y ago
Thanks for this article. LWN articles are good quality. I think locks, parallelism, multithreading, async is difficult. I would like some visualisations to visualise locking behaviours and obvious bottlenecks. Being able to visually see a lock convoy or priority inversion would be helpful. The kernel-userspace transition seems to be expensive and if you have 90 threads all contending for the same resource, then you cannot scale memory write/mutation access by 90 times by locking. If the holder of the lock is not scheduled and is preempted then the lock attempter shall spin, potentially preventing the holder of the lock from being scheduled. I wonder if there's lessons from static and dynamic scheduling here? If you know the lock hierarchy in the kernel, couldn't you intelligently schedule? I read a really good comment on HN by jcranmer about VLIW architecture recently. [1] [1]: https://news.ycombinator.com/item?id=38118441 https://news.ycombinator.com/item?id=38118441

60 points by signa11 3y ago

Seems like a natural and necessary adaptation. This is fundamentally a consequence of the fact that today there are many cores. Kernel schedulers originated in a world where cores were precious and the kernel had to aggressively preclude user space from monopolizing them, and so no provision was made to allow user space to defer preemption. Hardware evolves faster than software.

saagarjha 3y ago
Needing to prevent applications from monopolizing the hardware is as necessary as it's ever been. The question is whether userspace can voluntarily promise that it'll be a good little process and behave in exchange for better performance, and corresponding penalties to institute for when that trust is broken.

hamilyon2 3y ago

Wow, this feels wrong way to do it. The way i see it, threads and processes waiting on some resource should be able to update some piece if metadata pointing to the thing they are waiting for. This will allow "donating" their priority and cpu share to the other process/thread. This can be a general mechanism, which can be incorporated in the things kernel already know, creating a chain of dependencies and giving priority to something at the end of chain.

jorlow 3y ago
I think you're describing traditional scheduling. The point is that sometimes overheads from cache thrashing and context switches are worse than just spinning.
- hamilyon2 3y ago
  My information about locking and scheduling is dated and naiive. What is preventing per-thread structure of two identifiers "I am waiting for thing X, give it priority" and "I am in posession of X"? Identifiers are random numbers. System call is not necessary, some writable location is enough.
gpderetta 3y ago
> threads and processes waiting on some resource should be able to update some piece if metadata pointing to the thing they are waiting for This will allow "donating" their priority and cpu share to the other process/thread. That's what, for example, futexes are for. But the "donating" part can be expensive, so short spins can actually be beneficial for overall system efficiency.

EdSchouten 3y ago

I don't know how I should feel about changes like this. My concern with 'spinlocks in userspace' (i.e., locks that don't just call into the futex API when they run into contention) is that they merely try to optimize for their own performance. Sure, the futex API has more overhead, but it does mean that other processes on your system can run in the meantime. It's sort of similar to using a TCP congestion algorithm that's overly aggressive. Your own network connections might become faster as a result of them, but at the same time your flatmates won't be able to check their mail.

saagarjha 3y ago
Generally unbounded spins are terrible in userspace, but bounded spins as part of "hybrid" locks generally strike a good balance between performance and system impact. When a system call is hundreds or thousands of cycles it can be quite effective to try spending some fraction of that yourself if it'll get you the lock without the syscall. Like, not just from a pure throughput perspective: a yield to the kernel is not "free", it takes time just to park yourself. So it's good to make a gamble usually.
- amelius 3y ago
  Could the implementation of the lock perhaps take the thread priority into account?
  - saagarjha 3y ago
    What would it do differently?
    - amelius 3y ago
      Give up earlier when the priority is low, so performance impact is low for low-priority threads.

dpc_01234 3y ago

Without digging into details: this seems like a a great idea. It's a cooperative, advisory optimization that can't really be gamed for permanent cpu time gain. A hint to scheduler that indicates that letting a process run just a tiny moment more might be good for overall system performance.

saagarjha 3y ago

This is an interesting idea. The core of it seems to be that the most efficient way to write locks today is to spin for a bit on contention, then yield to the kernel if you've been waiting to long. The goal, of course, is that if the lock is quickly released you don't take the full cost of a kernel call and can just keep going in userspace. Darwin's os_unfair_lock (and the closely related WebKit WTF::Lock) both use this strategy. Interestingly, XNU already has an implementation of this that is somewhat similar in spirit: preemption free zones (https://github.com/search?q=repo%3Aapple-oss-distributions%2Fxnu%20pfz&type=code https://github.com/search?q=repo%3Aapple-oss-distributions%2...). As far as I can tell os_atomic_lock does not use it for this purpose. Instead, it exists to allow OSAtomicFifoEnqueue/OSAtomicFifoDequeue to be lock-free, and in the typical Apple fashion solves the problem of "what if a userspace application uses this for evil" by implementing it in the kernel and mapping it via the commpage (think vDSO), so there isn't really any room for anyone but Apple to put code there. Apple being Apple, they could have absolutely added PFZ to os_atomic_lock (for themselves, of course). One wonders why they didn't; perhaps it just turns out that it isn't worth the complexity. (Look, I'm sorry all I talk about is Apple stuff, that's all I know.)

spacechild1 3y ago
> The core of it seems to be that the most efficient way to write locks today is to spin for a bit on contention, then yield to the kernel if you've been waiting to long. This is an old idea and many real-world mutex implementation have been doing this since forever. Some even let you configure the spin count: https://learn.microsoft.com/en-us/windows/win32/api/synchapi/nf-synchapi-initializecriticalsectionandspincount https://learn.microsoft.com/en-us/windows/win32/api/synchapi...
- saagarjha 3y ago
  Yeah this is nothing new, I'm just saying that Linux is looking to service this better.
  - spacechild1 3y ago
    Alright, I was just tripping over the word "today", since this has already been true 20 years ago :)

weinzierl 3y ago

"This feature might seem like a way for a malicious thread to get more than its share of the available CPU time. The EEVDF scheduler that will be featured in the 6.6 kernel release, though, will note that a thread has gotten more than its share of CPU time and penalize it thereafter." This talks about fairness between threads, and is from my understanding also how the current CFS scheduler approaches fairness. I also understand that fairness on a process level might be difficult to obtain. But doesn't this thread level fairness render the point of a "malicous thread" moot? Fairness of threads within a process is pointless anyway, because this is all in the hands of the programmer and all they can do is shoot themselves in their own feet. Fairness between processes would be interesting but we don't have it anyway, so deferred scheduling doesn't make the situation worse in that regard?

samsquire 3y ago

Thanks for this article. LWN articles are good quality. I think locks, parallelism, multithreading, async is difficult. I would like some visualisations to visualise locking behaviours and obvious bottlenecks. Being able to visually see a lock convoy or priority inversion would be helpful. The kernel-userspace transition seems to be expensive and if you have 90 threads all contending for the same resource, then you cannot scale memory write/mutation access by 90 times by locking. If the holder of the lock is not scheduled and is preempted then the lock attempter shall spin, potentially preventing the holder of the lock from being scheduled. I wonder if there's lessons from static and dynamic scheduling here? If you know the lock hierarchy in the kernel, couldn't you intelligently schedule? I read a really good comment on HN by jcranmer about VLIW architecture recently. [1] [1]: https://news.ycombinator.com/item?id=38118441 https://news.ycombinator.com/item?id=38118441