linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [RFC][PATCH 00/16] sched: SCHED_DEADLINE v4
@ 2012-04-06  7:14 Juri Lelli
  2012-04-06  7:14 ` [PATCH 01/16] sched: add sched_class->task_dead Juri Lelli
                   ` (18 more replies)
  0 siblings, 19 replies; 129+ messages in thread
From: Juri Lelli @ 2012-04-06  7:14 UTC (permalink / raw)
  To: peterz, tglx
  Cc: mingo, rostedt, cfriesen, oleg, fweisbec, darren, johan.eker,
	p.faure, linux-kernel, claudio, michael, fchecconi,
	tommaso.cucinotta, juri.lelli, nicola.manica, luca.abeni,
	dhaval.giani, hgu1972, paulmck, raistlin, insop.song,
	liming.wang

Hello everyone,

This is the take 4 for the SCHED_DEADLINE patchset.

Just to recap, the patchset introduces a new deadline based real-time
task scheduling policy --called SCHED_DEADLINE-- with bandwidth
isolation (aka "resource reservation") capabilities. It now supports
global/clustered multiprocessor scheduling through dynamic task
migrations.


 From the previous releases[1]:
  - all the comments and the fixes coming from the reviews we got have
    been considered and applied;
  - better handling of rq selection for dynamic task migration, by means
    of a cpupri equivalent for -deadline tasks (cpudl). The mechanism
    is simple and straightforward, but showed nice performance figures[2].
  - this time we sit on top of PREEMPT_RT (3.2.13-rt23); we continue to aim
    at mainline inclusion, but we also see -rt folks as immediate and
    interested users.

Still missing/incomplete:
  - (c)group based bandwidth management, and maybe scheduling. It seems
    some more discussion on what precisely we want is *really* needed
    for this point;
  - bandwidth inheritance (to replace deadline/priority inheritance).
    What's in the patchset is just very few more than a simple
    placeholder. More discussion on the right way to go is needed here.
    Some work has already been done, but it is still not ready for
    submission.

The development is taking place at:
   https://github.com/jlelli/sched-deadline

Check the repositories frequently if you're interested, and feel free to
e-mail me for any issue you run into.

Furthermore, we developed an application that you can use to test this
patchset:
  https://github.com/gbagnoli/rt-app 

We also set up a development mailing list: linux-dl[3].
You can subscribe from here:
http://feanor.sssup.it/mailman/listinfo/linux-dl
or via e-mail (send a message to linux-dl-request@retis.sssup.it with
just the word `help' as subject or in the body to receive info).

As already discussed we are planning to merge this work with the EDF
throttling patches [https://lkml.org/lkml/2010/2/23/239] but we still are in
the preliminary phases of the merge and we intend to use the feedback to this
post to help us decide on the direction it should take.

As said, patchset is on top of PREEMPT_RT (as of today). However, Insop
Song (from Ericsson) is maintaining a parallel branch for the current
tip/master (https://github.com/insop/sched-deadline2). Ericsson is in fact
evaluating the use of SCHED_DEADLINE for CPE (Customer Premise Equipment)
devices in order to reserve CPU bandwidth to processes.

The code was being jointly developed by ReTiS Lab (http://retis.sssup.it)
and Evidence S.r.l (http://www.evidence.eu.com) in the context of the ACTORS
EU-funded project (http://www.actors-project.eu). It is now also supported by
the S(o)OS EU-funded project (http://www.soos-project.eu/).
It has also some users, both in academic and applied research. Even if our
last release dates back almost a year we continued to get feedback
from Ericsson (see above), Wind River, Porto (ISEP), Trento and Malardalen
universities :-).

As usual, any kind of feedback is welcome and appreciated.

Thanks in advice and regards,

 - Juri

[1] http://lwn.net/Articles/376502, http://lwn.net/Articles/353797,
    http://lwn.net/Articles/412410
[2] http://retis.sssup.it/~jlelli/papers/Ospert11Lelli.pdf
[3] from the first linux-dl message:
    -linux-dl should become the place where discussions about real-time
     deadline scheduling on Linux take place (not only SCHED_DEADLINE).
     We felt the lack of a place where we can keep in touch with each
     other; we are all working on the same things, but probably from
     different viewpoints, and this is surely a point of strength.
     Anyway, our efforts need to be organized in some way, or at least it
     is important to know on what everyone is currently working as to not
     end up with "duplicate-efforts".-

Dario Faggioli (10):
      sched: add extended scheduling interface.
      sched: SCHED_DEADLINE data structures.
      sched: SCHED_DEADLINE policy implementation.
      sched: SCHED_DEADLINE avg_update accounting.
      sched: add schedstats for -deadline tasks.
      sched: add resource limits for -deadline tasks.
      sched: add latency tracing for -deadline tasks.
      sched: drafted deadline inheritance logic.
      sched: add bandwidth management for sched_dl.
      sched: add sched_dl documentation.

Juri Lelli (3):
      sched: SCHED_DEADLINE SMP-related data structures.
      sched: SCHED_DEADLINE push and pull logic
      sched: speed up -dl pushes with a push-heap.

Harald Gustafsson (1):
      sched: add period support for -deadline tasks.

Peter Zijlstra (1):
      rtmutex: turn the plist into an rb-tree.

 Documentation/scheduler/sched-deadline.txt |  147 +++
 arch/arm/include/asm/unistd.h              |    3 +
 arch/arm/kernel/calls.S                    |    3 +
 arch/x86/ia32/ia32entry.S                  |    3 +
 arch/x86/include/asm/unistd_32.h           |    5 +-
 arch/x86/include/asm/unistd_64.h           |    6 +
 arch/x86/kernel/syscall_table_32.S         |    3 +
 include/asm-generic/resource.h             |    7 +-
 include/linux/init_task.h                  |   10 +
 include/linux/rtmutex.h                    |   18 +-
 include/linux/sched.h                      |  154 +++-
 include/linux/syscalls.h                   |    7 +
 kernel/Makefile                            |    1 +
 kernel/fork.c                              |    8 +-
 kernel/hrtimer.c                           |    2 +-
 kernel/rtmutex-debug.c                     |   10 +-
 kernel/rtmutex.c                           |  162 +++-
 kernel/rtmutex_common.h                    |   24 +-
 kernel/sched.c                             |  866 ++++++++++++++-
 kernel/sched_cpudl.c                       |  208 ++++
 kernel/sched_cpudl.h                       |   34 +
 kernel/sched_debug.c                       |   43 +
 kernel/sched_dl.c                          | 1585 ++++++++++++++++++++++++++++
 kernel/sched_rt.c                          |    3 +-
 kernel/sched_stoptask.c                    |    2 +-
 kernel/sysctl.c                            |   14 +
 kernel/trace/trace_sched_wakeup.c          |   41 +-
 kernel/trace/trace_selftest.c              |   30 +-
 28 files changed, 3266 insertions(+), 133 deletions(-)

^ permalink raw reply	[flat|nested] 129+ messages in thread
* [RFC][PATCH 00/16] sched: SCHED_DEADLINE v6
@ 2012-10-24 21:53 Juri Lelli
  2012-10-24 21:53 ` [PATCH 08/16] sched: add period support for -deadline tasks Juri Lelli
  0 siblings, 1 reply; 129+ messages in thread
From: Juri Lelli @ 2012-10-24 21:53 UTC (permalink / raw)
  To: peterz, tglx
  Cc: mingo, rostedt, oleg, fweisbec, darren, johan.eker, p.faure,
	linux-kernel, claudio, michael, fchecconi, tommaso.cucinotta,
	juri.lelli, nicola.manica, luca.abeni, dhaval.giani, hgu1972,
	paulmck, raistlin, insop.song, liming.wang, jkacur,
	harald.gustafsson, vincent.guittot

Hello everyone,

This is the take 6 for the SCHED_DEADLINE patchset.

The patchset introduces a new deadline based real-time task scheduling
policy --called SCHED_DEADLINE-- with bandwidth isolation (aka "resource
reservation") capabilities. It supports global/clustered multiprocessor
scheduling through dynamic task migrations.

 From the previous releases[1]:
  - comments and fixes coming from the reviews we got have been considered
    and applied;

  - the use of nr_cpus_allowed has been unified;
 
  - this release is on top of tip/master (as of today), so this is also
    a rebase on top of 3.7-rc2;

  - patch 14/16 modifies real-time bandwidth management and makes dl_bw
    a subquota of rt_bw (comments on this are very welcome!);

  - tested on ARM (thanks to Claudio Scordino for testing and and patches).

(My) TODOs:
  - keep up with mainline (as usual);
  - rebase on top of 3.6.2-rt4 PREEMPT_RT patchset;
  - provide details and numbers about possible use-cases;
  - power aware scheduling for HMP (some code is there, but not yet
    ready for submission);
  - setup a website to collect all information regarding the project
    in just one single place.

The development is taking place at:
   https://github.com/jlelli/sched-deadline

Main branches:

 - mainline-dl: tracking tip/master (raw commits);
 - linux-rt-dl: tracking PREEMPT_RT releases (outdated);
 - sched-dl-V6: this patchset on top of tip/master.

Check the repositories frequently if you're interested, and feel free to
e-mail me for any issue you run into.

Test application:
  https://github.com/gbagnoli/rt-app 

Development mailing list: linux-dl; you can subscribe from here:
http://feanor.sssup.it/mailman/listinfo/linux-dl
or via e-mail (send a message to linux-dl-request@retis.sssup.it with
just the word `help' as subject or in the body to receive info).

There is also a parallel branch maintained by Insop Song (from Ericsson)
(https://github.com/insop/sched-deadline2). Ericsson is in fact evaluating
the use of SCHED_DEADLINE for CPE (Customer Premise Equipment) devices in
order to reserve CPU bandwidth to processes.

The code was being jointly developed by ReTiS Lab (http://retis.sssup.it)
and Evidence S.r.l (http://www.evidence.eu.com) in the context of the ACTORS
EU-funded project (http://www.actors-project.eu). It is now also supported by
the S(o)OS EU-funded project (http://www.soos-project.eu/).
It has also some users, both in academic and applied research. We got
positive feedbacks from Ericsson (see above), Wind River, Porto (ISEP), Trento,
Lund and Malardalen universities.

Acknowledgements:
  I owe special thanks to Fabio Checconi and Dario Faggioli for technical (and
  moral :P) support. Thanks to Peter Zijlstra, Steven Rostedt and all the others
  that reviewed and/or contributed to improve the patchset quality. Thanks also
  to Insop Song for trying to give the project an "industrial" use case and to
  Claudio Scordino for testing and advertisement.

As usual, any kind of feedback is welcome and appreciated.

Thanks in advice and regards,

 - Juri

Dario Faggioli (9):
  sched: add sched_class->task_dead.
  sched: add extended scheduling interface.
  sched: SCHED_DEADLINE structures & implementation.
  sched: SCHED_DEADLINE avg_update accounting.
  sched: add schedstats for -deadline tasks.
  sched: add latency tracing for -deadline tasks.
  sched: drafted deadline inheritance logic.
  sched: add bandwidth management for sched_dl.
  sched: add sched_dl documentation.

Harald Gustafsson (1):
  sched: add period support for -deadline tasks.

Juri Lelli (3):
  sched: SCHED_DEADLINE SMP-related data structures & logic.
  sched: make dl_bw a sub-quota of rt_bw
  sched: speed up -dl pushes with a push-heap.

Peter Zijlstra (3):
  math128: Introduce various 128bit primitives
  math128, x86_64: Implement {mul,add}_u128 in 64bit asm
  rtmutex: turn the plist into an rb-tree.

 Documentation/scheduler/sched-deadline.txt |  164 +++
 arch/alpha/include/asm/Kbuild              |    1 +
 arch/arm/include/asm/Kbuild                |    1 +
 arch/arm/include/asm/unistd.h              |    2 +-
 arch/arm/include/uapi/asm/unistd.h         |    3 +
 arch/arm/kernel/calls.S                    |    3 +
 arch/avr32/include/asm/Kbuild              |    2 +
 arch/blackfin/include/asm/Kbuild           |    1 +
 arch/c6x/include/asm/Kbuild                |    1 +
 arch/cris/include/asm/Kbuild               |    1 +
 arch/frv/include/asm/Kbuild                |    3 +
 arch/h8300/include/asm/Kbuild              |    1 +
 arch/hexagon/include/asm/Kbuild            |    1 +
 arch/ia64/include/asm/Kbuild               |    1 +
 arch/m32r/include/asm/Kbuild               |    1 +
 arch/m68k/include/asm/Kbuild               |    1 +
 arch/microblaze/include/asm/Kbuild         |    1 +
 arch/mips/include/asm/Kbuild               |    1 +
 arch/mn10300/include/asm/Kbuild            |    1 +
 arch/openrisc/include/asm/Kbuild           |    1 +
 arch/parisc/include/asm/Kbuild             |    2 +-
 arch/powerpc/include/asm/Kbuild            |    1 +
 arch/s390/include/asm/Kbuild               |    2 +-
 arch/score/include/asm/Kbuild              |    1 +
 arch/sh/include/asm/Kbuild                 |    1 +
 arch/sparc/include/asm/Kbuild              |    1 +
 arch/tile/include/asm/Kbuild               |    1 +
 arch/um/include/asm/Kbuild                 |    2 +-
 arch/unicore32/include/asm/Kbuild          |    1 +
 arch/x86/include/asm/Kbuild                |    1 +
 arch/x86/include/asm/math128.h             |   39 +
 arch/x86/syscalls/syscall_32.tbl           |    3 +
 arch/x86/syscalls/syscall_64.tbl           |    4 +-
 arch/xtensa/include/asm/Kbuild             |    1 +
 include/asm-generic/math128.h              |    4 +
 include/linux/init_task.h                  |   10 +
 include/linux/math128.h                    |  180 +++
 include/linux/rtmutex.h                    |   18 +-
 include/linux/sched.h                      |  152 ++-
 include/linux/syscalls.h                   |    7 +
 include/uapi/linux/sched.h                 |    1 +
 kernel/fork.c                              |    8 +-
 kernel/futex.c                             |    2 +
 kernel/hrtimer.c                           |    2 +-
 kernel/rtmutex-debug.c                     |   10 +-
 kernel/rtmutex.c                           |  163 ++-
 kernel/rtmutex_common.h                    |   22 +-
 kernel/sched/Makefile                      |    4 +-
 kernel/sched/core.c                        |  645 ++++++++++-
 kernel/sched/cpudl.c                       |  208 ++++
 kernel/sched/cpudl.h                       |   33 +
 kernel/sched/debug.c                       |   46 +
 kernel/sched/dl.c                          | 1650 ++++++++++++++++++++++++++++
 kernel/sched/rt.c                          |    2 +-
 kernel/sched/sched.h                       |  139 +++
 kernel/sched/stop_task.c                   |    2 +-
 kernel/sysctl.c                            |    7 +
 kernel/trace/trace_sched_wakeup.c          |   44 +-
 kernel/trace/trace_selftest.c              |   28 +-
 lib/Makefile                               |    2 +-
 lib/math128.c                              |   40 +
 61 files changed, 3555 insertions(+), 125 deletions(-)
 create mode 100644 Documentation/scheduler/sched-deadline.txt
 create mode 100644 arch/x86/include/asm/math128.h
 create mode 100644 include/asm-generic/math128.h
 create mode 100644 include/linux/math128.h
 create mode 100644 kernel/sched/cpudl.c
 create mode 100644 kernel/sched/cpudl.h
 create mode 100644 kernel/sched/dl.c
 create mode 100644 lib/math128.c

-- 
1.7.9.5


^ permalink raw reply	[flat|nested] 129+ messages in thread

end of thread, other threads:[~2012-10-24 21:56 UTC | newest]

Thread overview: 129+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-04-06  7:14 [RFC][PATCH 00/16] sched: SCHED_DEADLINE v4 Juri Lelli
2012-04-06  7:14 ` [PATCH 01/16] sched: add sched_class->task_dead Juri Lelli
2012-04-08 17:49   ` Oleg Nesterov
2012-04-08 18:09     ` Juri Lelli
2012-04-06  7:14 ` [PATCH 02/16] sched: add extended scheduling interface Juri Lelli
2012-04-06  7:14 ` [PATCH 03/16] sched: SCHED_DEADLINE data structures Juri Lelli
2012-04-23  9:08   ` Peter Zijlstra
2012-04-23  9:47     ` Juri Lelli
2012-04-23  9:49       ` Peter Zijlstra
2012-04-23  9:55         ` Juri Lelli
2012-04-23 10:12           ` Peter Zijlstra
2012-04-23  9:13   ` Peter Zijlstra
2012-04-23  9:28     ` Juri Lelli
2012-04-23  9:30   ` Peter Zijlstra
2012-04-23  9:36     ` Juri Lelli
2012-04-23  9:39       ` Peter Zijlstra
2012-04-23  9:34   ` Peter Zijlstra
2012-04-23 10:16     ` Juri Lelli
2012-04-23 10:28       ` Peter Zijlstra
2012-04-23 10:33         ` Juri Lelli
2012-04-06  7:14 ` [PATCH 04/16] sched: SCHED_DEADLINE SMP-related " Juri Lelli
2012-04-06  7:14 ` [PATCH 05/16] sched: SCHED_DEADLINE policy implementation Juri Lelli
2012-04-11  3:06   ` Steven Rostedt
2012-04-11  6:54     ` Juri Lelli
2012-04-11 13:41   ` Steven Rostedt
2012-04-11 13:55     ` Juri Lelli
2012-04-23 10:15   ` Peter Zijlstra
2012-04-23 10:18     ` Juri Lelli
2012-04-23 10:31   ` Peter Zijlstra
2012-04-23 10:37     ` Juri Lelli
2012-04-23 21:25       ` Tommaso Cucinotta
2012-04-23 21:45         ` Peter Zijlstra
2012-04-23 23:25           ` Tommaso Cucinotta
2012-04-24  6:29             ` Dario Faggioli
2012-04-24  6:52               ` Juri Lelli
2012-04-23 11:32   ` Peter Zijlstra
2012-04-23 12:13     ` Juri Lelli
2012-04-23 12:22       ` Peter Zijlstra
2012-04-23 13:37         ` Juri Lelli
2012-04-23 14:01           ` Peter Zijlstra
2012-04-23 11:34   ` Peter Zijlstra
2012-04-23 11:57     ` Juri Lelli
2012-04-23 11:55   ` Peter Zijlstra
2012-04-23 14:43     ` Juri Lelli
2012-04-23 15:11       ` Peter Zijlstra
2012-04-23 21:55     ` Tommaso Cucinotta
2012-04-23 21:58       ` Peter Zijlstra
2012-04-23 23:21         ` Tommaso Cucinotta
2012-04-24  9:50           ` Peter Zijlstra
2012-04-24  1:03         ` Steven Rostedt
2012-04-23 14:11   ` Peter Zijlstra
2012-04-23 14:25   ` Peter Zijlstra
2012-04-23 15:34     ` Juri Lelli
2012-04-23 14:35   ` Peter Zijlstra
2012-04-23 15:39     ` Juri Lelli
2012-04-23 15:43       ` Peter Zijlstra
2012-04-23 16:41         ` Juri Lelli
     [not found]           ` <4F95D41F.5060700@sssup.it>
2012-04-24  7:21             ` Juri Lelli
2012-04-24  9:00               ` Peter Zijlstra
2012-05-15 10:10         ` Juri Lelli
2012-04-23 15:15   ` Peter Zijlstra
2012-04-23 15:37     ` Juri Lelli
2012-04-06  7:14 ` [PATCH 06/16] sched: SCHED_DEADLINE push and pull logic Juri Lelli
2012-04-06 13:39   ` Hillf Danton
2012-04-06 17:31     ` Juri Lelli
2012-04-07  2:32       ` Hillf Danton
2012-04-07  7:46         ` Dario Faggioli
2012-04-08 20:20         ` Juri Lelli
2012-04-09 12:28           ` Hillf Danton
2012-04-10  8:11             ` Juri Lelli
2012-04-11 15:57               ` Steven Rostedt
2012-04-11 16:00           ` Steven Rostedt
2012-04-11 16:09             ` Juri Lelli
2012-04-11 14:10     ` Steven Rostedt
2012-04-12 12:28       ` Hillf Danton
2012-04-12 12:51         ` Steven Rostedt
2012-04-12 12:56           ` Hillf Danton
2012-04-12 13:35             ` Steven Rostedt
2012-04-12 13:41               ` Hillf Danton
2012-04-11 16:07   ` Steven Rostedt
2012-04-11 16:11     ` Juri Lelli
2012-04-11 16:14   ` Steven Rostedt
2012-04-19 13:44     ` Juri Lelli
2012-04-11 16:21   ` Steven Rostedt
2012-04-11 16:24     ` Juri Lelli
2012-04-11 16:33   ` Steven Rostedt
2012-04-24 13:15     ` Peter Zijlstra
2012-04-24 18:50       ` Steven Rostedt
2012-04-24 18:53         ` Peter Zijlstra
2012-04-24 19:01           ` Steven Rostedt
2012-04-11 17:25   ` Steven Rostedt
2012-04-11 17:48     ` Juri Lelli
2012-04-06  7:14 ` [PATCH 07/16] sched: SCHED_DEADLINE avg_update accounting Juri Lelli
2012-04-06  7:14 ` [PATCH 08/16] sched: add period support for -deadline tasks Juri Lelli
2012-04-11 20:32   ` Steven Rostedt
2012-04-11 21:56     ` Juri Lelli
2012-04-11 22:13     ` Tommaso Cucinotta
2012-04-12  0:19       ` Steven Rostedt
2012-04-12  6:39     ` Luca Abeni
2012-04-06  7:14 ` [PATCH 09/16] sched: add schedstats " Juri Lelli
2012-04-06  7:14 ` [PATCH 10/16] sched: add resource limits " Juri Lelli
2012-04-24 15:07   ` Peter Zijlstra
2012-04-24 15:22     ` Juri Lelli
2012-04-24 16:27       ` Peter Zijlstra
2012-04-24 17:14         ` Juri Lelli
2012-04-06  7:14 ` [PATCH 11/16] sched: add latency tracing " Juri Lelli
2012-04-11 21:03   ` Steven Rostedt
2012-04-12  7:16     ` Juri Lelli
2012-04-16 15:51     ` Daniel Vacek
2012-04-16 19:56       ` Steven Rostedt
2012-04-16 21:31         ` Daniel Vacek
2012-04-06  7:14 ` [PATCH 12/16] rtmutex: turn the plist into an rb-tree Juri Lelli
2012-04-11 21:11   ` Steven Rostedt
2012-04-22 14:28     ` Juri Lelli
2012-04-23  8:33     ` Peter Zijlstra
2012-04-23 11:37       ` Steven Rostedt
2012-04-06  7:14 ` [PATCH 13/16] sched: drafted deadline inheritance logic Juri Lelli
2012-04-12  2:42   ` Steven Rostedt
2012-04-22 14:04     ` Juri Lelli
2012-04-23  8:39     ` Peter Zijlstra
2012-04-06  7:14 ` [PATCH 14/16] sched: add bandwidth management for sched_dl Juri Lelli
2012-04-06  7:14 ` [PATCH 15/16] sched: speed up -dl pushes with a push-heap Juri Lelli
2012-04-06  7:14 ` [PATCH 16/16] sched: add sched_dl documentation Juri Lelli
2012-04-06  8:25 ` [RFC][PATCH 00/16] sched: SCHED_DEADLINE v4 Luca Abeni
2012-04-07  9:25   ` Tadeus Prastowo
2012-04-06 11:07 ` Dario Faggioli
2012-04-11 14:17 ` Steven Rostedt
2012-04-11 14:28   ` Juri Lelli
2012-10-24 21:53 [RFC][PATCH 00/16] sched: SCHED_DEADLINE v6 Juri Lelli
2012-10-24 21:53 ` [PATCH 08/16] sched: add period support for -deadline tasks Juri Lelli

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).