[PATCH 00/18 v3] Improving latency of short slice tasks

[Vincent Guittot]

This is another round of scheduling latency improvements which fix
some remaining corner cases and start to fix somes cases when multi
short slice tasks are running simultaneously on the system.

This patchset gathers 5 different parts:
- Patch 1-4 implement decay of positive lag
- Patch 5-6 take into account slice when selecting CPU
- Patch 7-12 add push callback for fair
- Patch 13-15 use push for migrating short slice task that failed
  to run at enqueue
- Patch 16-19 modify feec to take into account slice when selecting CPU
- Patch 20 handles case where several tasks select the same idle CPU

I run my usual set of scheduling latency tests on dragonboard rb5
- cyclictest with a 3777us period and a 8ms slice alone
- cyclictest with a 3777us period and a 8ms slice. 2xNR_CPUS rt-app
  tasks that run (8177us) and sleep (17777us) with a 16ms slice.
- cyclictest with a 3777us period and a 8ms slice. Hackbench with
  1 group using thread and pipe and a 16ms slice.

NB: periods and run duration have been chosen to minimize alignment
with tick or other periodic activities.

Each test is 130 seconds long

scheduling latency (us) for cyclictest
                   tip/sched/core| this patchset
slice                 8ms        |  8ms         
99th Percentile               91 |    92 (- 1 %)
99.9th Percentile            128 |   161 (-26 %)
Maximum                      273 |   223 (+18 %)

scheduling latency (us) for cyclictest and rt-app
                   tip/sched/core| this patchset
slice                 8ms / 16ms |  8ms  / 16 ms
99th Percentile               65 |    68 (- 5 %)
99.9th Percentile            986 |   913 (+ 7 %)
Maximum                     6229 |  5715 (+ 8 %)

scheduling latency (us) for cyclictest and hackbench
                   tip/sched/core| this patchset
slice                 8ms / 16ms |  8ms  / 16 ms
99th Percentile               74 |    90 (-22 %)
99.9th Percentile	     643 |   997 (-55 %)
Maximum			   13501 |  4454 (+67 %)

The 99.9th percentile are a bit worse mainly because of the decay/reset of
positive lag. Eternal positive lag was beneficial for cyclictest which
doesn't do anything while running and slowly decrease its large positive
lag. Now its positive lag elapses while sleeping and cyclictest is
enqueued with a null lag most of the time. On the other side this reduces
cases where long sleeping task with large positive lag can preempt or
prevent short task to run first.

For testing cases w/ multi short slice tasks, I run a new rt-app test that
wakes up simultaneously 4 short slice tasks while 16 normal tasks are
also enqueued. All tasks wants to run 1ms every 7777ms. The 4 short tasks
have an uclamp min of 512 to target the high and mid cores on my system
(1 task per core)
(SIS_UTIL is not disabled unlike for v2)

tip/sched/core
			Task-O		Task-1		Task-2		Task-3		
Average              |	1051		  52		1051		1093
Median (P50)         |	1091		  53		1091		1092
90th Percentile      |	2133		  53		2132		2133
99th Percentile      |	2400		  53		2398		2394
99.9th Percentile    |	2519		 120		2518		2408
Maximum              |	2523		1327		3097		2415

+ The patchset
			Task-O		Task-1		Task-2		Task-3		
Average              |	61		61		60		61
Median (P50)         |	60		60		60		60
90th Percentile      |	62		62		62		62
99th Percentile      |	62		62		62		62
99.9th Percentile    |	1839		2012		63		2175
Maximum              |	2175		2066		2176		2689

On tip/sched/core, the 4 tasks tends to wake up on the same CPU whereas
this patchset pushes the tasks which aren't picked on another CPU.

Beside the results above I noticed significants performance improvements
for hackbench with pipe which were not expected.
"sched/eevdf: Decay positive lag of sleeping entities" is the patch that
provides most of the performance improvements

The test were run with the default 2.8ms slice to check for some
performance regressions

hackbench             tip/sched/core   this patchset
 1 group process pipe 0,862(+/-3.9%)   0,839(+/-1.3%) (+ 3%)
 4 group process pipe 0,725(+/-1.5%)   0,593(+/-1.3%) (+18%)
 8 group process pipe 0,640(+/-4.2%)   0,546(+/-2.2%) (+15%)
16 group process pipe 0,620(+/-3.9%)   0,528(+/-0.8%) (+15%)
 1 group thread  pipe 0,917(+/-2.8%)   0,907(+/-2.2%) (+ 1%)
 4 group thread  pipe 0,838(+/-4.5%)   0,697(+/-3.6%) (+17%)
 8 group thread  pipe 0,774(+/-1.5%)   0,583(+/-2.5%) (+25%)
16 group thread  pipe 0,628(+/-2.9%)   0,548(+/-2.1%) (+13%)

Those tests have been run with perf scheduler (Using schedutil and EAS
provides similar results)

Changes since v2:
- Remove min_slice comparison during wake_affine which didn't provide
  benefit at the end
- Added reset lag when migrating
- Fixing stacking on idle cpu case
- Tried to cover all the comments I received in v2 and more while running
more test and reviewing the changes

Changes since v1:
- Change decay_entity_lag to take into account cfs load but not
  migrated task yet.
- Reset lag if the CPU entered idle while task was sleeping.
- Move lockless min_slice in struct rq and use usigned long
  which is enough for slice which stays in range [100us:100ms]
- Merge min_slice rq selection in select_idle_capacity() and
  select_idle_cpu()
- Add push callback mecanism for cfs
- Push short slice tasks that are not selected at wakeup
- Update feec() to take into accoun slice when selecting a CPU

Vincent Guittot (20):
  sched/eevdf: Decay positive lag of sleeping entities
  sched/eevdf: Reset lag at wakeup when prev CPU has been idle
  sched/eevdf: Reset lag at wakeup when migrating and prev has been idle
  sched/eevdf: Reset lag when waking up on idle cpu
  sched/eevdf: Add per cpu cached min_slice
  sched/eevdf: Add min slice check when selecting CPU
  sched/fair: Prepare select_task_rq_fair() to be called for new cases
  sched/fair: Add push task mechanism for fair
  sched/fair: Optimize push task mechanism for fair
  sched/core: Add rq flag to tick parameters
  sched/fair: Add force push task mechanism for fair
  sched/fair: Support not wakeup case in select_idle_sibling
  sched/eevdf: Try to push short slice task on a better CPU
  sched/eevdf: Push short slice task that are not picked
  sched/fair: Enable push task for preempt short
  energy model: Add a get previous state function
  sched/fair: Rework feec() to use cost instead of spare capacity
  energy model: Remove unused em_cpu_energy()
  sched/fair: Take into account slice in EAS
  sched/fair: Fix tasks stacking on same idle CPU

 include/linux/energy_model.h |  109 +--
 include/linux/sched.h        |    1 +
 kernel/sched/core.c          |    8 +-
 kernel/sched/deadline.c      |    2 +-
 kernel/sched/ext/ext.c       |    2 +-
 kernel/sched/fair.c          | 1244 ++++++++++++++++++++++++----------
 kernel/sched/idle.c          |    2 +-
 kernel/sched/rt.c            |    2 +-
 kernel/sched/sched.h         |    8 +-
 kernel/sched/stop_task.c     |    2 +-
 kernel/sched/topology.c      |    3 +
 11 files changed, 938 insertions(+), 445 deletions(-)

-- 
2.53.0