Re: [POC][RFC][PATCH] sched: Extended Scheduler Time Slice

[Mathieu Desnoyers]

On 2023-10-25 13:17, Steven Rostedt wrote:
> On Wed, 25 Oct 2023 18:24:35 +0200
> Mateusz Guzik <mjguzik@xxxxxxxxx> wrote:
>
> > On Wed, Oct 25, 2023 at 11:42:34AM -0400, Mathieu Desnoyers wrote:
> > > On 2023-10-25 10:31, Steven Rostedt wrote:
> > > > On Wed, 25 Oct 2023 15:55:45 +0200
> > > > Peter Zijlstra <peterz@xxxxxxxxxxxxx> wrote:
[...]
> No, I wouldn't say it's the same as priority inheritance, which is to help
> with determinism and not performance. PI adds overhead but removes
> unbounded latency. On average, a non PI mutex is faster than PI mutex, but
> can suffer from unbounded priority inversion.

AFAIU, this is because PI mutex as implemented by sys futex only boosts the
priority of the lock owner. In my proposal here the owner would be able to
borrow scheduler slices from the waiters as well.

[...]

> > > Hopefully I'm not oversimplifying if I state that we have mainly two
> > > actors to consider:
> > >
> > > [A] the lock owner thread
> > >
> > > [B] threads that block trying to acquire the lock
> > >
> > > The fast-path here is [A]. [B] can go through a system call, I don't
> > > think it matters at all.
>
> No, B going into a system call can be just as devastating. Adaptive
> spinning helps with that. The thing here is that if A gets preempted, there
> will be a lot more B's getting stuck.

I would indeed combine this with an adaptive spinning scheme to allow waiters to
stay in userspace if contention is short. As you know, rseq can also help there:

https://lore.kernel.org/lkml/20230529191416.53955-1-mathieu.desnoyers@xxxxxxxxxxxx/

Therefore, it's only the blocking case that would call into the kernel, which
should not be so devastating.

> I implemented the test with futexes (where you go to sleep on contention)
> and the performance dropped considerably, where the benefits of not having
> A get preempted made no difference at all. Sure, adaptive spinning helps in
> that case, but adaptive spinning would only make it as good as my spinning
> in user space logic is without any changes.

I'm not sure what you are arguing here.

My overall idea would be to combine:

1) Adaptive spinning in userspace,
2) Priority inheritance,
3) Scheduler slices inheritance.

> > > Those lock addresses could then be used as keys for private locks,
> > > or transformed into inode/offset keys for shared-memory locks. Threads
> > > [B] blocking trying to acquire the lock can call a system call which
> > > would boost the lock owner's slice and/or priority for a given lock key.
>
> Do you mean that this would be done in user space? Going into the kernel to
> do any of this would make it already lost.

Going to the kernel only happens when threads need to block, which means
that the typical contended half-happy path should be busy-spinning in userspace
(adaptive spinning).

I see why blocking in a scenario where busy-spinning would be better is
inefficient, but I don't see how going to the kernel for the _blocking_
case is bad.

> > > When the scheduler preempts [A], it would check whether the rseq
> > > per-thread area has a "held locks" field set and use this information
> > > to find the slice/priority boost which are currently active for each
> > > lock, and use this information to boost the task slice/priority
> > > accordingly.
>
> Why do we care about locks here? Note, I'm looking at using this same
> feature for VMs on interrupt handlers. The only thing user space needs to
> tell the kernel is "It's not a good time to preempt me, but it will be
> shortly".

Quoting https://lore.kernel.org/lkml/20231024103426.4074d319@xxxxxxxxxxxxxxxxxx/

"The goal is to prevent a thread / vCPU being preempted while holding a lock
or resource that other threads / vCPUs will want. That is, prevent
contention, as that's usually the biggest issue with performance in user
space and VMs."

We care about locks here because this is in fact your own problem statement.
If you want to consider the different problem of making VM interrupt handlers
go fast, then you should state it up front. Those two distinct problems may
or may not require entirely different solutions.

> > > A scheme like this should allow lock priority inheritance without
> > > requiring system calls on the userspace lock/unlock fast path.
>
> Priority inheritance doesn't make sense when everything is running.

I should have also said that this scheme should allow the lock owner to
borrow scheduler time slices from waiters (in addition to PI).

[...]

Thanks,

Mathieu

--
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com