Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1550037 > unrolled thread

[RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks

Back to article view | Back to linux.kernel

Contents

  [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks Waiman Long <longman@redhat.com> - 2017-01-03 19:10 +0100
    Re: [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks Peter Zijlstra <peterz@infradead.org> - 2017-01-04 14:10 +0100
      Re: [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks Waiman Long <longman@redhat.com> - 2017-01-04 16:30 +0100
        Re: [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks Steven Rostedt <rostedt@goodmis.org> - 2017-01-04 17:00 +0100
          Re: [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks Waiman Long <longman@redhat.com> - 2017-01-04 21:10 +0100
            Re: [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks Steven Rostedt <rostedt@goodmis.org> - 2017-01-05 19:50 +0100
        Re: [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks Daniel Bristot de Oliveira <bristot@redhat.com> - 2017-01-05 10:30 +0100
        Re: [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks Peter Zijlstra <peterz@infradead.org> - 2017-01-05 10:50 +0100
          Re: [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks Peter Zijlstra <peterz@infradead.org> - 2017-01-05 17:10 +0100
            Re: [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks Waiman Long <longman@redhat.com> - 2017-01-05 18:10 +0100
              Re: [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks Steven Rostedt <rostedt@goodmis.org> - 2017-01-05 20:00 +0100
                Re: [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks Waiman Long <longman@redhat.com> - 2017-01-05 20:30 +0100
            Re: [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks Daniel Bristot de Oliveira <bristot@redhat.com> - 2017-01-05 19:10 +0100
          Re: [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks Waiman Long <longman@redhat.com> - 2017-01-05 17:10 +0100

#1550037 — [RFC PATCH 0/7] locking/rtqspinlock: Realtime queued spinlocks

This patchset introduces a new variant of queued spinlocks - the
realtime queued spinlocks. The purpose of this new variant is to
support real spinlock in a realtime environment where high priority
RT tasks should be allowed to complete its work ASAP. This means as
little waiting time for spinlocks as possible.

Non-RT tasks will wait for spinlocks in the MCS waiting queue as
usual. RT tasks and interrupts will spin directly on the spinlocks
and use the priority value in the pending byte to arbitrate who get
the lock first.

Patch 1 removes the unused spin_lock_bh_nested() API.

Patch 2 introduces the basic realtime queued spinlocks where the
pending byte is used for storing the priority of the highest priority
RT task that is waiting on the spinlock. All the RT tasks will spin
directly on the spinlock instead of waiting in the queue.

Patch 3 moves all interrupt context lock waiters to RT spinning.

Patch 4 overrides the spin_lock_nested() call with special code to
enabled RT lock spinning for nested spinlock.

Patch 5 handles priority boosting by periodically checking its priority
and unqueuing from the waiting queue and do RT spinning if applicable.

Patch 6 allows voluntary CPU preemption to happen when a CPU is
waiting for a spinlock.

Patch 7 enables event counts to be collected by the qspinlock stat
package so that we could monitor what have happened within the kernel.

With a locking microbenchmark running on a 2-socket 36-core E5-2699
v3 system, the elapsed times to complete 2M locking loop per non-RT
thread were as follows:

   # of threads   qspinlock   rt-qspinlock  % change
   ------------   ---------   ------------  --------
        2           0.29s        1.97s       +580%
	3           1.46s        2.05s        +40%
	4           1.81s        2.38s        +31%
	5           2.36s        2.87s        +22%
	6           2.73s        3.58s        +31%
	7           3.17s        3.74s        +18%
	8           3.67s        4.70s        +28%
	9           3.89s        5.28s        +36%
       10           4.35s        6.58s        +51%

The RT qspinlock is slower than the non-RT qspinlock which is expected.

This patchset hasn't included any patch to modify the call sites of
spin_lock_nested() to include the outer lock of the nest spinlock
pair yet. That will be included in a later version of this patchset
once it is determined that RT qspinlocks is worth pursuing.

Only minimal testing to build and boot the patched kernel was
done. More extensive testing will be done with later versions of
this patchset.

Waiman Long (7):
  locking/spinlock: Remove the unused spin_lock_bh_nested API
  locking/rtqspinlock: Introduce realtime queued spinlocks
  locking/rtqspinlock: Use static RT priority when in interrupt context
  locking/rtqspinlock: Override spin_lock_nested with special RT variants
  locking/rtqspinlock: Handle priority boosting
  locking/rtqspinlock: Voluntarily yield CPU when need_sched()
  locking/rtqspinlock: Enable collection of event counts

 arch/x86/Kconfig                 |  18 +-
 include/linux/spinlock.h         |  43 +++-
 include/linux/spinlock_api_smp.h |   9 +-
 include/linux/spinlock_api_up.h  |   1 -
 kernel/Kconfig.locks             |   9 +
 kernel/locking/qspinlock.c       |  51 +++-
 kernel/locking/qspinlock_rt.h    | 543 +++++++++++++++++++++++++++++++++++++++
 kernel/locking/qspinlock_stat.h  |  81 +++++-
 kernel/locking/spinlock.c        |   8 -
 9 files changed, 721 insertions(+), 42 deletions(-)
 create mode 100644 kernel/locking/qspinlock_rt.h

-- 
1.8.3.1

[toc] | [next] | [standalone]

#1550752

On Tue, Jan 03, 2017 at 01:00:23PM -0500, Waiman Long wrote:
> This patchset introduces a new variant of queued spinlocks - the
> realtime queued spinlocks. The purpose of this new variant is to
> support real spinlock in a realtime environment where high priority
> RT tasks should be allowed to complete its work ASAP. This means as
> little waiting time for spinlocks as possible.
> 
> Non-RT tasks will wait for spinlocks in the MCS waiting queue as
> usual. RT tasks and interrupts will spin directly on the spinlocks
> and use the priority value in the pending byte to arbitrate who get
> the lock first.
> 
> Patch 1 removes the unused spin_lock_bh_nested() API.
> 
> Patch 2 introduces the basic realtime queued spinlocks where the
> pending byte is used for storing the priority of the highest priority
> RT task that is waiting on the spinlock. All the RT tasks will spin
> directly on the spinlock instead of waiting in the queue.
> 


OK, so a single numerical field isn't sufficient to describe priority
anymore, since we added DEADLINE support things have gotten a lot more
complex.

Also, the whole approach worries me, it has the very real possibility of
re-introducing a bunch of starvation cases avoided by the fair lock.


Is there a real problem with -RT that inspired these patches?

[toc] | [prev] | [next] | [standalone]

#1550914

On 01/04/2017 07:49 AM, Peter Zijlstra wrote:
> On Tue, Jan 03, 2017 at 01:00:23PM -0500, Waiman Long wrote:
>> This patchset introduces a new variant of queued spinlocks - the
>> realtime queued spinlocks. The purpose of this new variant is to
>> support real spinlock in a realtime environment where high priority
>> RT tasks should be allowed to complete its work ASAP. This means as
>> little waiting time for spinlocks as possible.
>>
>> Non-RT tasks will wait for spinlocks in the MCS waiting queue as
>> usual. RT tasks and interrupts will spin directly on the spinlocks
>> and use the priority value in the pending byte to arbitrate who get
>> the lock first.
>>
>> Patch 1 removes the unused spin_lock_bh_nested() API.
>>
>> Patch 2 introduces the basic realtime queued spinlocks where the
>> pending byte is used for storing the priority of the highest priority
>> RT task that is waiting on the spinlock. All the RT tasks will spin
>> directly on the spinlock instead of waiting in the queue.
>>
>
> OK, so a single numerical field isn't sufficient to describe priority
> anymore, since we added DEADLINE support things have gotten a lot more
> complex.

From what I read from the code, DL tasks all have the same priority that
is higher than any of the RT tasks. So you mean DL tasks have other
property that kind of categorizing them into different sub-priorities
that is not being reflected in their priority level. Is that right?

> Also, the whole approach worries me, it has the very real possibility of
> re-introducing a bunch of starvation cases avoided by the fair lock.

Starvation can happen when there is a constant stream of RT or DL tasks
grabbing the lock, or when there is an interrupt storm. However I am
making the assumption that RT systems should have sufficient resource
available that the RT tasks won't saturate the hardware or we can't have
RT guarantee in this case.

> Is there a real problem with -RT that inspired these patches?

I know that in -RT kernel, all the non-raw spinlocks are replaced by
rtmutex which is a sleeping lock. This can have a real performance
impact on systems with more than a few cores. The rtmutex isn't fair either.

Do you think it is better to keep the raw spinlocks fair and only have
the non-raw spinlocks use the RT version?

Cheers,
Longman

[toc] | [prev] | [next] | [standalone]

#1550948

On Wed, 4 Jan 2017 10:25:14 -0500
Waiman Long <longman@redhat.com> wrote:

 
> I know that in -RT kernel, all the non-raw spinlocks are replaced by
> rtmutex which is a sleeping lock. This can have a real performance
> impact on systems with more than a few cores. The rtmutex isn't fair either.

We do fine on 80+ CPUs. Is that enough cores for you ;-)

Note, it's not a true sleeping lock, because of the adaptive nature.
That is, it spins unless the owner of the lock is sleeping, in which
case, it too will sleep (why spin waiting for a task that isn't
running). But if the owner is running, it will spin too.

We also have tricks to keep normal preemption (like SCHED_OTHER tasks
running out of their time slot) when they have a lock. This keeps
contention down on tasks owning locks while sleeping.

> 
> Do you think it is better to keep the raw spinlocks fair and only have
> the non-raw spinlocks use the RT version?

Yes.

Note, I also want to get rt_mutex into the kernel first for all sleeping
locks. That is, get the logic in before we convert spin_locks to
sleeping locks.

-- Steve

[toc] | [prev] | [next] | [standalone]

#1551151

On 01/04/2017 10:55 AM, Steven Rostedt wrote:
> On Wed, 4 Jan 2017 10:25:14 -0500
> Waiman Long <longman@redhat.com> wrote:
>
>  
>> I know that in -RT kernel, all the non-raw spinlocks are replaced by
>> rtmutex which is a sleeping lock. This can have a real performance
>> impact on systems with more than a few cores. The rtmutex isn't fair either.
> We do fine on 80+ CPUs. Is that enough cores for you ;-)

It depends on what you mean fine. I haven't done the actual benchmark
yet, but I believe that a -RT system with 80+ CPUs will feel noticeably
slower for non-RT tasks than a system with non-RT kernel. I am not
saying that the system will slow down significantly, but the slow down
will certainly be noticeable.

> Note, it's not a true sleeping lock, because of the adaptive nature.
> That is, it spins unless the owner of the lock is sleeping, in which
> case, it too will sleep (why spin waiting for a task that isn't
> running). But if the owner is running, it will spin too.

I think this is a recent change by Davidlohr. However, the spinning is
limited to the top waiter. The rests will still go to sleep.

> We also have tricks to keep normal preemption (like SCHED_OTHER tasks
> running out of their time slot) when they have a lock. This keeps
> contention down on tasks owning locks while sleeping.

Yes, that certainly help.

>> Do you think it is better to keep the raw spinlocks fair and only have
>> the non-raw spinlocks use the RT version?
> Yes.

OK, I can certainly do that.

>
> Note, I also want to get rt_mutex into the kernel first for all sleeping
> locks. That is, get the logic in before we convert spin_locks to
> sleeping locks.
>
> -- Steve

The rtmutex code is already in the upstream kernel. It is just that
there isn't any code yet that can let you flip a switch (a config
option) and change all sleeping locks to use rtmutex.

Cheers,
Longman

[toc] | [prev] | [next] | [standalone]

#1552222

On Wed, 4 Jan 2017 15:02:23 -0500
Waiman Long <longman@redhat.com> wrote:

> On 01/04/2017 10:55 AM, Steven Rostedt wrote:
> > On Wed, 4 Jan 2017 10:25:14 -0500
> > Waiman Long <longman@redhat.com> wrote:
> >
> >    
> >> I know that in -RT kernel, all the non-raw spinlocks are replaced by
> >> rtmutex which is a sleeping lock. This can have a real performance
> >> impact on systems with more than a few cores. The rtmutex isn't fair either.  
> > We do fine on 80+ CPUs. Is that enough cores for you ;-)  
> 
> It depends on what you mean fine. I haven't done the actual benchmark
> yet, but I believe that a -RT system with 80+ CPUs will feel noticeably
> slower for non-RT tasks than a system with non-RT kernel. I am not
> saying that the system will slow down significantly, but the slow down
> will certainly be noticeable.

Really matters what the work load is. Yes, java apps will be much
slower, because java runs 1000s of threads, and the real bottle neck is
with the read-writer locks (the mmap rwsem causes issues here).

But, really, I've done kernel builds on these large boxes running -rt,
and those still do well.

> 
> > Note, it's not a true sleeping lock, because of the adaptive nature.
> > That is, it spins unless the owner of the lock is sleeping, in which
> > case, it too will sleep (why spin waiting for a task that isn't
> > running). But if the owner is running, it will spin too.  
> 
> I think this is a recent change by Davidlohr. However, the spinning is
> limited to the top waiter. The rests will still go to sleep.

No, adaptive spinlocks were there for some time. It's copyright in 2008
by Gregory Haskins, Sven Dietrich and Peter Morreale.

As for the top waiter, that could probably be optimized to not do so.
Good project to try out and see how that speeds things up.

> >
> > Note, I also want to get rt_mutex into the kernel first for all sleeping
> > locks. That is, get the logic in before we convert spin_locks to
> > sleeping locks.

> 
> The rtmutex code is already in the upstream kernel. It is just that
> there isn't any code yet that can let you flip a switch (a config
> option) and change all sleeping locks to use rtmutex.

The pi code is upstream, but it's only used by futexes and maybe even
rcu boosting. But normal kernel mutexes don't have pi.

-- Steve

[toc] | [prev] | [next] | [standalone]

#1551805

On 01/04/2017 04:25 PM, Waiman Long wrote:
>> OK, so a single numerical field isn't sufficient to describe priority
>> anymore, since we added DEADLINE support things have gotten a lot more
>> complex.
> From what I read from the code, DL tasks all have the same priority that
> is higher than any of the RT tasks. So you mean DL tasks have other
> property that kind of categorizing them into different sub-priorities
> that is not being reflected in their priority level. Is that right?

DL tasks are scheduled according to their absolute deadline, which
stored in the u64 curr->dl.deadline.

It is more complex because the priority of a deadline task is always
changing. The priority of a DL task changes on every new
periodic/sporadic replenishment/activation.


-- Daniel

[toc] | [prev] | [next] | [standalone]

#1551828

On Wed, Jan 04, 2017 at 10:25:14AM -0500, Waiman Long wrote:
> On 01/04/2017 07:49 AM, Peter Zijlstra wrote:
> > On Tue, Jan 03, 2017 at 01:00:23PM -0500, Waiman Long wrote:
> >> This patchset introduces a new variant of queued spinlocks - the
> >> realtime queued spinlocks. The purpose of this new variant is to
> >> support real spinlock in a realtime environment where high priority
> >> RT tasks should be allowed to complete its work ASAP. This means as
> >> little waiting time for spinlocks as possible.
> >>
> >> Non-RT tasks will wait for spinlocks in the MCS waiting queue as
> >> usual. RT tasks and interrupts will spin directly on the spinlocks
> >> and use the priority value in the pending byte to arbitrate who get
> >> the lock first.
> >>
> >> Patch 1 removes the unused spin_lock_bh_nested() API.
> >>
> >> Patch 2 introduces the basic realtime queued spinlocks where the
> >> pending byte is used for storing the priority of the highest priority
> >> RT task that is waiting on the spinlock. All the RT tasks will spin
> >> directly on the spinlock instead of waiting in the queue.
> >>
> >
> > OK, so a single numerical field isn't sufficient to describe priority
> > anymore, since we added DEADLINE support things have gotten a lot more
> > complex.
> 
> From what I read from the code, DL tasks all have the same priority that
> is higher than any of the RT tasks. So you mean DL tasks have other
> property that kind of categorizing them into different sub-priorities
> that is not being reflected in their priority level. Is that right?

Correct, primarily their deadline. That is, the scheduling function for
the class picks the task with the earliest deadline.

> > Also, the whole approach worries me, it has the very real possibility of
> > re-introducing a bunch of starvation cases avoided by the fair lock.
> 
> Starvation can happen when there is a constant stream of RT or DL tasks
> grabbing the lock, or when there is an interrupt storm. However I am
> making the assumption that RT systems should have sufficient resource
> available that the RT tasks won't saturate the hardware or we can't have
> RT guarantee in this case.

That only works on UP, on SMP you only need a combined utilization of 1
to completely saturate a lock.
> 
> > Is there a real problem with -RT that inspired these patches?
> 
> I know that in -RT kernel, all the non-raw spinlocks are replaced by
> rtmutex which is a sleeping lock. This can have a real performance
> impact on systems with more than a few cores. The rtmutex isn't fair either.
> 
> Do you think it is better to keep the raw spinlocks fair and only have
> the non-raw spinlocks use the RT version?

I don't get what you're saying here. Are you proposing to replace the
rtmutex with this rtspinlock? That will very fundamentally not work. The
important part of the conversion of spinlock -> rtmutex is acquiring the
preemptability. Using this rtspinlock looses that and breaks the
entirety of what -rt is about.

[toc] | [prev] | [next] | [standalone]

#1552083

On Thu, Jan 05, 2017 at 10:55:55AM -0500, Waiman Long wrote:
> What I am saying that we don't need to change spinlock to rtmutex in a
> -RT kernel. Instead, we can use rtqspinlock for this purpose. All the
> sleeping locks will still be converted to rtmutex.

No-no-no..

> Conversion of rtmutex does allow forced CPU preemption when there is a
> need for that. What rtqspinlock can provide is voluntary preemption
> where the lock waiters explicitly yield the CPU while waiting for the
> lock. I use the need_resched() to detect if CPU yielding is necessary.
> However, if the CPU was in a preempt disabled region before the
> spin_lock() call, we can't yield the CPU. The only way is to raise its
> priority and try to get the lock ASAP.

And here you've lost your finger because the saw-blade didn't stop in
time.

RT very fundamentally relies on the spinlock->rtmutex conversion to
allow preempting things when a higher priority task comes along. A
spinlock, of any kind, requires having preemption disabled while holding
the lock. If the critical section is of unbounded latency, you have
unbounded preemption latency and RT is no more.

Its not about PI on contention, although that helps inversion scenarios.
Its about allowing preemption, which fundamentally requires a sleeping
lock to be used.

Many of the spinlock sections of mainline are not well behaved in an RT
sense and therefore must not disable preemption. Similar for the IRQ
disable regions and hence we have the whole threaded interrupt stuff.

Please stop writing code and read up on things..

[toc] | [prev] | [next] | [standalone]

#1552123

On 01/05/2017 11:08 AM, Peter Zijlstra wrote:
> On Thu, Jan 05, 2017 at 10:55:55AM -0500, Waiman Long wrote:
>> What I am saying that we don't need to change spinlock to rtmutex in a
>> -RT kernel. Instead, we can use rtqspinlock for this purpose. All the
>> sleeping locks will still be converted to rtmutex.
> No-no-no..
>
>> Conversion of rtmutex does allow forced CPU preemption when there is a
>> need for that. What rtqspinlock can provide is voluntary preemption
>> where the lock waiters explicitly yield the CPU while waiting for the
>> lock. I use the need_resched() to detect if CPU yielding is necessary.
>> However, if the CPU was in a preempt disabled region before the
>> spin_lock() call, we can't yield the CPU. The only way is to raise its
>> priority and try to get the lock ASAP.
> And here you've lost your finger because the saw-blade didn't stop in
> time.

Well, I lost my virtual fingers all the time;-)

This is one way that I learn and become stronger.

> RT very fundamentally relies on the spinlock->rtmutex conversion to
> allow preempting things when a higher priority task comes along. A
> spinlock, of any kind, requires having preemption disabled while holding
> the lock. If the critical section is of unbounded latency, you have
> unbounded preemption latency and RT is no more.
>
> Its not about PI on contention, although that helps inversion scenarios.
> Its about allowing preemption, which fundamentally requires a sleeping
> lock to be used.
>
> Many of the spinlock sections of mainline are not well behaved in an RT
> sense and therefore must not disable preemption. Similar for the IRQ
> disable regions and hence we have the whole threaded interrupt stuff.

I do make the assumption that spinlock critical sections are behaving
well enough. Apparently, that is not a valid assumption. I sent these
RFC patches out to see if it was an idea worth pursuing. If not, I can
drop these patches. Anyway, thanks for the feedback.

Cheers,
Longman

[toc] | [prev] | [next] | [standalone]

#1552227

On Thu, 5 Jan 2017 12:07:21 -0500
Waiman Long <longman@redhat.com> wrote:


> I do make the assumption that spinlock critical sections are behaving
> well enough. Apparently, that is not a valid assumption. I sent these
> RFC patches out to see if it was an idea worth pursuing. If not, I can
> drop these patches. Anyway, thanks for the feedback.

Yes, the assumption is incorrect. There are places that can hold a spin
lock for several hundreds of microseconds. If you can't preempt them,
you'll never get below several hundreds of microseconds in latency.

And it would be hard to pick and choose (we already do this to decide
what can be a raw_spin_lock), because you need to audit all use cases
of a spin_lock as well as all the locks taken while holding that
spin_lock.

-- Steve

[toc] | [prev] | [next] | [standalone]

#1552268

On 01/05/2017 01:50 PM, Steven Rostedt wrote:
> On Thu, 5 Jan 2017 12:07:21 -0500
> Waiman Long <longman@redhat.com> wrote:
>
>
>> I do make the assumption that spinlock critical sections are behaving
>> well enough. Apparently, that is not a valid assumption. I sent these
>> RFC patches out to see if it was an idea worth pursuing. If not, I can
>> drop these patches. Anyway, thanks for the feedback.
> Yes, the assumption is incorrect. There are places that can hold a spin
> lock for several hundreds of microseconds. If you can't preempt them,
> you'll never get below several hundreds of microseconds in latency.
>
> And it would be hard to pick and choose (we already do this to decide
> what can be a raw_spin_lock), because you need to audit all use cases
> of a spin_lock as well as all the locks taken while holding that
> spin_lock.
>
> -- Steve

Thank for the information.

It has come to my attention that scalability problem may be present in
the -RT kernel because of the longer wait time in the raw_spin_lock side
as the number of CPUs increases. I will look into this some more to see
if my patch set can help under those circumstances.

Cheers,
Longman

[toc] | [prev] | [next] | [standalone]

#1552187

On 01/05/2017 05:08 PM, Peter Zijlstra wrote:
> RT very fundamentally relies on the spinlock->rtmutex conversion to
> allow preempting things when a higher priority task comes along. A
> spinlock, of any kind, requires having preemption disabled while holding
> the lock. If the critical section is of unbounded latency, you have
> unbounded preemption latency and RT is no more.
> 
> Its not about PI on contention, although that helps inversion scenarios.
> Its about allowing preemption, which fundamentally requires a sleeping
> lock to be used.

2 cents complementing this:

Spinlocks algorithms which disable the preemption while holding the lock
resembles a theoretical algorithm named Immediate Priority Ceiling
Protocol. The immediate priority ceiling protocol avoids unbounded
priority inversion, like the Priority Inheritance Protocol used on rt
mutex. However, although the Immediate Priority Ceiling Protocol may
help to reduce the response time of tasks, it causes penalty on the
activation/scheduling delay (latency on linux -rt dictionary) of tasks
with the priority higher than the task holding the lock, but lower than
the Ceiling priority. As it is not possible to know on beforehand the
Ceiling priority of a lock on Linux, the implementation needs to use the
highest priority, that is only possible by disabling the preemption on
Linux, causing scheduling latency even for the highest -rt task.

Hence, the penalty of the immediate priority ceiling protocol is right
in the main metric of the PREEMPT_RT: the scheduling latency.

This is an old article:

http://www.jsoftware.us/vol7/jsw0703-03.pdf

for uni processors... so it does not completely fit in this case but it
shows some results of using immediate priority ceiling rather than PI on
rt-mutex. It shows that the immediate priority ceiling causes scheduling
delays/latency

This paper mentions the Multicore Priority Ceiling Protocol causing
scheduling latency as well:

https://people.mpi-sws.org/~bbb/papers/pdf/rtlws12.pdf

That is why RT Mutex with PIP is better for the PREEMPT than any
protocol that disables preemption.

-- Daniel

[toc] | [prev] | [next] | [standalone]

#1552085

On 01/05/2017 04:44 AM, Peter Zijlstra wrote:
> On Wed, Jan 04, 2017 at 10:25:14AM -0500, Waiman Long wrote:
>> On 01/04/2017 07:49 AM, Peter Zijlstra wrote:
>>> On Tue, Jan 03, 2017 at 01:00:23PM -0500, Waiman Long wrote:
>>>> This patchset introduces a new variant of queued spinlocks - the
>>>> realtime queued spinlocks. The purpose of this new variant is to
>>>> support real spinlock in a realtime environment where high priority
>>>> RT tasks should be allowed to complete its work ASAP. This means as
>>>> little waiting time for spinlocks as possible.
>>>>
>>>> Non-RT tasks will wait for spinlocks in the MCS waiting queue as
>>>> usual. RT tasks and interrupts will spin directly on the spinlocks
>>>> and use the priority value in the pending byte to arbitrate who get
>>>> the lock first.
>>>>
>>>> Patch 1 removes the unused spin_lock_bh_nested() API.
>>>>
>>>> Patch 2 introduces the basic realtime queued spinlocks where the
>>>> pending byte is used for storing the priority of the highest priority
>>>> RT task that is waiting on the spinlock. All the RT tasks will spin
>>>> directly on the spinlock instead of waiting in the queue.
>>>>
>>> OK, so a single numerical field isn't sufficient to describe priority
>>> anymore, since we added DEADLINE support things have gotten a lot more
>>> complex.
>> From what I read from the code, DL tasks all have the same priority that
>> is higher than any of the RT tasks. So you mean DL tasks have other
>> property that kind of categorizing them into different sub-priorities
>> that is not being reflected in their priority level. Is that right?
> Correct, primarily their deadline. That is, the scheduling function for
> the class picks the task with the earliest deadline.

OK, I need to rethink how to deal with those DL tasks.

>>> Also, the whole approach worries me, it has the very real possibility of
>>> re-introducing a bunch of starvation cases avoided by the fair lock.
>> Starvation can happen when there is a constant stream of RT or DL tasks
>> grabbing the lock, or when there is an interrupt storm. However I am
>> making the assumption that RT systems should have sufficient resource
>> available that the RT tasks won't saturate the hardware or we can't have
>> RT guarantee in this case.
> That only works on UP, on SMP you only need a combined utilization of 1
> to completely saturate a lock.

An RT task in a spinlock loop won't be able to completely monopolize the
lock because of the small window between unlock and lock that others can
come in and get the lock. You will need at least 2 RT tasks in lockstep
to completely own the lock and starve the others.

We could implement some kind of policy to increase the dynamic priority
of a task the longer it waits for the lock to make sure that there will
be no lock starvation.

>>> Is there a real problem with -RT that inspired these patches?
>> I know that in -RT kernel, all the non-raw spinlocks are replaced by
>> rtmutex which is a sleeping lock. This can have a real performance
>> impact on systems with more than a few cores. The rtmutex isn't fair either.
>>
>> Do you think it is better to keep the raw spinlocks fair and only have
>> the non-raw spinlocks use the RT version?
> I don't get what you're saying here. Are you proposing to replace the
> rtmutex with this rtspinlock? That will very fundamentally not work. The
> important part of the conversion of spinlock -> rtmutex is acquiring the
> preemptability. Using this rtspinlock looses that and breaks the
> entirety of what -rt is about.

What I am saying that we don't need to change spinlock to rtmutex in a
-RT kernel. Instead, we can use rtqspinlock for this purpose. All the
sleeping locks will still be converted to rtmutex.

Conversion of rtmutex does allow forced CPU preemption when there is a
need for that. What rtqspinlock can provide is voluntary preemption
where the lock waiters explicitly yield the CPU while waiting for the
lock. I use the need_resched() to detect if CPU yielding is necessary.
However, if the CPU was in a preempt disabled region before the
spin_lock() call, we can't yield the CPU. The only way is to raise its
priority and try to get the lock ASAP. I still have some work to do in
this area and I need to figure out how to convey the information about
the priority of the task that is waiting for the CPU.

Cheers,
Longman

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web