public inbox for linux-kernel@vger.kernel.org
 help / color / mirror / Atom feed
* Re: [Announce] [patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]
@ 2007-04-15 18:47 Tim Tassonis
  0 siblings, 0 replies; 304+ messages in thread
From: Tim Tassonis @ 2007-04-15 18:47 UTC (permalink / raw)
  To: linux-kernel

> +	printk("Fair Scheduler: Copyright (c) 2007 Red Hat, Inc., Ingo Molnar\n");

So that's what all the fuss about the staircase scheduler is all about 
then! At last, I see your point.


>    i'd like to give credit to Con Kolivas for the general approach here:
>    he has proven via RSDL/SD that 'fair scheduling' is possible and that
>    it results in better desktop scheduling. Kudos Con!
> 

How pathetic can you get?

Tim, really looking forward to the CL final where Liverpool will beat 
the shit out of Scum (and there's a lot to be beaten out).


^ permalink raw reply	[flat|nested] 304+ messages in thread
* [Announce] [patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]
@ 2007-04-13 20:21 Ingo Molnar
  2007-04-13 20:27 ` Bill Huey
                   ` (13 more replies)
  0 siblings, 14 replies; 304+ messages in thread
From: Ingo Molnar @ 2007-04-13 20:21 UTC (permalink / raw)
  To: linux-kernel
  Cc: Linus Torvalds, Andrew Morton, Con Kolivas, Nick Piggin,
	Mike Galbraith, Arjan van de Ven, Thomas Gleixner

[announce] [patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]

i'm pleased to announce the first release of the "Modular Scheduler Core
and Completely Fair Scheduler [CFS]" patchset:

   http://redhat.com/~mingo/cfs-scheduler/sched-modular+cfs.patch

This project is a complete rewrite of the Linux task scheduler. My goal
is to address various feature requests and to fix deficiencies in the
vanilla scheduler that were suggested/found in the past few years, both
for desktop scheduling and for server scheduling workloads.

[ QuickStart: apply the patch to v2.6.21-rc6, recompile, reboot. The
  new scheduler will be active by default and all tasks will default
  to the new SCHED_FAIR interactive scheduling class. ]

Highlights are:

 - the introduction of Scheduling Classes: an extensible hierarchy of
   scheduler modules. These modules encapsulate scheduling policy
   details and are handled by the scheduler core without the core
   code assuming about them too much.

 - sched_fair.c implements the 'CFS desktop scheduler': it is a
   replacement for the vanilla scheduler's SCHED_OTHER interactivity
   code.

   i'd like to give credit to Con Kolivas for the general approach here:
   he has proven via RSDL/SD that 'fair scheduling' is possible and that
   it results in better desktop scheduling. Kudos Con!

   The CFS patch uses a completely different approach and implementation
   from RSDL/SD. My goal was to make CFS's interactivity quality exceed
   that of RSDL/SD, which is a high standard to meet :-) Testing
   feedback is welcome to decide this one way or another. [ and, in any
   case, all of SD's logic could be added via a kernel/sched_sd.c module
   as well, if Con is interested in such an approach. ]

   CFS's design is quite radical: it does not use runqueues, it uses a
   time-ordered rbtree to build a 'timeline' of future task execution,
   and thus has no 'array switch' artifacts (by which both the vanilla
   scheduler and RSDL/SD are affected).

   CFS uses nanosecond granularity accounting and does not rely on any
   jiffies or other HZ detail. Thus the CFS scheduler has no notion of
   'timeslices' and has no heuristics whatsoever. There is only one
   central tunable:

         /proc/sys/kernel/sched_granularity_ns

   which can be used to tune the scheduler from 'desktop' (low
   latencies) to 'server' (good batching) workloads. It defaults to a
   setting suitable for desktop workloads. SCHED_BATCH is handled by the
   CFS scheduler module too.

   due to its design, the CFS scheduler is not prone to any of the
   'attacks' that exist today against the heuristics of the stock
   scheduler: fiftyp.c, thud.c, chew.c, ring-test.c, massive_intr.c all
   work fine and do not impact interactivity and produce the expected
   behavior.

   the CFS scheduler has a much stronger handling of nice levels and
   SCHED_BATCH: both types of workloads should be isolated much more
   agressively than under the vanilla scheduler.

   ( another rdetail: due to nanosec accounting and timeline sorting,
     sched_yield() support is very simple under CFS, and in fact under
     CFS sched_yield() behaves much better than under any other
     scheduler i have tested so far. )

 - sched_rt.c implements SCHED_FIFO and SCHED_RR semantics, in a simpler
   way than the vanilla scheduler does. It uses 100 runqueues (for all
   100 RT priority levels, instead of 140 in the vanilla scheduler)
   and it needs no expired array.

 - reworked/sanitized SMP load-balancing: the runqueue-walking
   assumptions are gone from the load-balancing code now, and
   iterators of the scheduling modules are used. The balancing code got
   quite a bit simpler as a result.

the core scheduler got smaller by more than 700 lines:

 kernel/sched.c | 1454 ++++++++++++++++------------------------------------------------
 1 file changed, 372 insertions(+), 1082 deletions(-)

and even adding all the scheduling modules, the total size impact is
relatively small:

 18 files changed, 1454 insertions(+), 1133 deletions(-)

most of the increase is due to extensive comments. The kernel size
impact is in fact a small negative:

   text    data     bss     dec     hex filename
  23366    4001      24   27391    6aff kernel/sched.o.vanilla
  24159    2705      56   26920    6928 kernel/sched.o.CFS

(this is mainly due to the benefit of getting rid of the expired array
and its data structure overhead.)

thanks go to Thomas Gleixner and Arjan van de Ven for review of this
patchset.

as usual, any sort of feedback, bugreports, fixes and suggestions are
more than welcome,

	Ingo

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

end of thread, other threads:[~2007-04-21 14:10 UTC | newest]

Thread overview: 304+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2007-04-15 18:47 [Announce] [patch] Modular Scheduler Core and Completely Fair Scheduler [CFS] Tim Tassonis
  -- strict thread matches above, loose matches on Subject: below --
2007-04-13 20:21 Ingo Molnar
2007-04-13 20:27 ` Bill Huey
2007-04-13 20:55   ` Ingo Molnar
2007-04-13 21:21     ` William Lee Irwin III
2007-04-13 21:35       ` Bill Huey
2007-04-13 21:39       ` Ingo Molnar
2007-04-13 21:50 ` Ingo Molnar
2007-04-13 21:57 ` Michal Piotrowski
2007-04-13 22:15 ` Daniel Walker
2007-04-13 22:30   ` Ingo Molnar
2007-04-13 22:37     ` Willy Tarreau
2007-04-13 23:59     ` Daniel Walker
2007-04-14 10:55       ` Ingo Molnar
2007-04-13 22:21 ` William Lee Irwin III
2007-04-13 22:52   ` Ingo Molnar
2007-04-13 23:30     ` William Lee Irwin III
2007-04-13 23:44       ` Ingo Molnar
2007-04-13 23:58         ` William Lee Irwin III
2007-04-14 22:38   ` Davide Libenzi
2007-04-14 23:26     ` Davide Libenzi
2007-04-15  4:01     ` William Lee Irwin III
2007-04-15  4:18       ` Davide Libenzi
2007-04-15 23:09     ` Pavel Pisa
2007-04-16  5:47       ` Davide Libenzi
2007-04-17  0:37         ` Pavel Pisa
2007-04-13 22:31 ` Willy Tarreau
2007-04-13 23:18   ` Ingo Molnar
2007-04-14 18:48     ` Bill Huey
2007-04-13 23:07 ` Gabriel C
2007-04-13 23:25   ` Ingo Molnar
2007-04-13 23:39     ` Gabriel C
2007-04-14  2:04 ` Nick Piggin
2007-04-14  6:32   ` Ingo Molnar
2007-04-14  6:43     ` Ingo Molnar
2007-04-14  8:08       ` Willy Tarreau
2007-04-14  8:36         ` Willy Tarreau
2007-04-14 10:53           ` Ingo Molnar
2007-04-14 13:01             ` Willy Tarreau
2007-04-14 13:27               ` Willy Tarreau
2007-04-14 14:45                 ` Willy Tarreau
2007-04-14 16:14                   ` Ingo Molnar
2007-04-14 16:19                 ` Ingo Molnar
2007-04-14 17:15                   ` Eric W. Biederman
2007-04-14 17:29                     ` Willy Tarreau
2007-04-14 17:44                       ` Eric W. Biederman
2007-04-14 17:54                         ` Ingo Molnar
2007-04-14 18:18                           ` Willy Tarreau
2007-04-14 18:40                             ` Eric W. Biederman
2007-04-14 19:01                               ` Willy Tarreau
2007-04-15 17:55                             ` Ingo Molnar
2007-04-15 18:06                               ` Willy Tarreau
2007-04-15 19:20                                 ` Ingo Molnar
2007-04-15 19:35                                   ` William Lee Irwin III
2007-04-15 19:57                                     ` Ingo Molnar
2007-04-15 23:54                                       ` William Lee Irwin III
2007-04-16 11:24                                         ` Ingo Molnar
2007-04-16 13:46                                           ` William Lee Irwin III
2007-04-15 19:37                                   ` Ingo Molnar
2007-04-14 17:50                       ` Linus Torvalds
2007-04-15  7:54               ` Mike Galbraith
2007-04-15  8:58                 ` Ingo Molnar
2007-04-15  9:11                   ` Mike Galbraith
2007-04-19  9:01               ` Ingo Molnar
2007-04-19 12:54                 ` Willy Tarreau
2007-04-19 15:18                   ` Ingo Molnar
2007-04-19 17:34                     ` Gene Heskett
2007-04-19 18:45                     ` Willy Tarreau
2007-04-21 10:31                       ` Ingo Molnar
2007-04-21 10:38                         ` Ingo Molnar
2007-04-21 10:45                         ` Ingo Molnar
2007-04-21 11:07                           ` Willy Tarreau
2007-04-21 11:29                             ` Björn Steinbrink
2007-04-21 11:51                               ` Willy Tarreau
2007-04-19 23:52                     ` Jan Knutar
2007-04-20  5:05                       ` Willy Tarreau
2007-04-19 17:32                 ` Gene Heskett
2007-04-14 15:17             ` Mark Lord
2007-04-14 19:48           ` William Lee Irwin III
2007-04-14 20:12             ` Willy Tarreau
2007-04-14 10:36         ` Ingo Molnar
2007-04-14 15:09 ` S.Çağlar Onur
2007-04-14 16:09   ` Ingo Molnar
2007-04-14 16:59     ` S.Çağlar Onur
2007-04-15  3:27 ` Con Kolivas
2007-04-15  5:16   ` Bill Huey
2007-04-15  8:44     ` Ingo Molnar
2007-04-15  9:51       ` Bill Huey
2007-04-15 10:39         ` Pekka Enberg
2007-04-15 12:45           ` Willy Tarreau
2007-04-15 13:08             ` Pekka J Enberg
2007-04-15 17:32               ` Mike Galbraith
2007-04-15 17:59                 ` Linus Torvalds
2007-04-15 19:00                   ` Jonathan Lundell
2007-04-15 22:52                     ` Con Kolivas
2007-04-16  2:28                       ` Nick Piggin
2007-04-16  3:15                         ` Con Kolivas
2007-04-16  3:34                           ` Nick Piggin
2007-04-15 15:26             ` William Lee Irwin III
2007-04-16 15:55               ` Chris Friesen
2007-04-16 16:13                 ` William Lee Irwin III
2007-04-17  0:04                 ` Peter Williams
2007-04-17 13:07                 ` James Bruce
2007-04-17 20:05                   ` William Lee Irwin III
2007-04-15 15:39             ` Ingo Molnar
2007-04-15 15:47               ` William Lee Irwin III
2007-04-16  5:27               ` Peter Williams
2007-04-16  6:23                 ` Peter Williams
2007-04-16  6:40                   ` Peter Williams
2007-04-16  7:32                     ` Ingo Molnar
2007-04-16  8:54                       ` Peter Williams
2007-04-15 15:16           ` Gene Heskett
2007-04-15 16:43             ` Con Kolivas
2007-04-15 16:58               ` Gene Heskett
2007-04-15 18:00                 ` Mike Galbraith
2007-04-16  0:18                   ` Gene Heskett
2007-04-15 16:11     ` Bernd Eckenfels
2007-04-15  6:43   ` Mike Galbraith
2007-04-15  8:36     ` Bill Huey
2007-04-15  8:45       ` Mike Galbraith
2007-04-15  9:06       ` Ingo Molnar
2007-04-16 10:00         ` Ingo Molnar
2007-04-15 16:25       ` Arjan van de Ven
2007-04-16  5:36         ` Bill Huey
2007-04-16  6:17           ` Nick Piggin
2007-04-17  0:06     ` Peter Williams
2007-04-17  2:29       ` Mike Galbraith
2007-04-17  3:40         ` Nick Piggin
2007-04-17  4:01           ` Mike Galbraith
2007-04-17  4:14             ` Nick Piggin
2007-04-17  6:26               ` Peter Williams
2007-04-17  9:51               ` Ingo Molnar
2007-04-17 13:44                 ` Peter Williams
2007-04-17 23:00                   ` Michael K. Edwards
2007-04-17 23:07                     ` William Lee Irwin III
2007-04-17 23:52                       ` Michael K. Edwards
2007-04-18  0:36                         ` Bill Huey
2007-04-18  2:39                     ` Peter Williams
2007-04-20 20:47                 ` Bill Davidsen
2007-04-21  7:39                   ` Nick Piggin
2007-04-21  8:33                   ` Ingo Molnar
2007-04-20 20:36             ` Bill Davidsen
2007-04-17  4:17           ` Peter Williams
2007-04-17  4:29             ` Nick Piggin
2007-04-17  5:53               ` Willy Tarreau
2007-04-17  6:10                 ` Nick Piggin
2007-04-17  6:09               ` William Lee Irwin III
2007-04-17  6:15                 ` Nick Piggin
2007-04-17  6:26                   ` William Lee Irwin III
2007-04-17  7:01                     ` Nick Piggin
2007-04-17  8:23                       ` William Lee Irwin III
2007-04-17 22:23                         ` Davide Libenzi
2007-04-17 21:39                       ` Matt Mackall
2007-04-17 23:23                         ` Peter Williams
2007-04-17 23:19                           ` Matt Mackall
2007-04-18  3:15                         ` Nick Piggin
2007-04-18  3:45                           ` Mike Galbraith
2007-04-18  3:56                             ` Nick Piggin
2007-04-18  4:29                               ` Mike Galbraith
2007-04-18  4:38                           ` Matt Mackall
2007-04-18  5:00                             ` Nick Piggin
2007-04-18  5:55                               ` Matt Mackall
2007-04-18  6:37                                 ` Nick Piggin
2007-04-18  6:55                                   ` Matt Mackall
2007-04-18  7:24                                     ` Nick Piggin
2007-04-21 13:33                                     ` Bill Davidsen
2007-04-18 13:08                                 ` William Lee Irwin III
2007-04-18 19:48                                   ` Davide Libenzi
2007-04-18 14:48                                 ` Linus Torvalds
2007-04-18 15:23                                   ` Matt Mackall
2007-04-18 17:22                                     ` Linus Torvalds
2007-04-18 17:49                                       ` Ingo Molnar
2007-04-18 17:59                                         ` Ingo Molnar
2007-04-18 19:40                                           ` Linus Torvalds
2007-04-18 19:43                                             ` Ingo Molnar
2007-04-18 20:07                                             ` Davide Libenzi
2007-04-18 21:48                                               ` Ingo Molnar
2007-04-18 23:30                                                 ` Davide Libenzi
2007-04-19  8:00                                                   ` Ingo Molnar
2007-04-19 15:43                                                     ` Davide Libenzi
2007-04-21 14:09                                                     ` Bill Davidsen
2007-04-19 17:39                                                   ` Bernd Eckenfels
2007-04-19  6:52                                                 ` Mike Galbraith
2007-04-19  7:09                                                   ` Ingo Molnar
2007-04-19  7:32                                                     ` Mike Galbraith
2007-04-19 16:55                                                       ` Davide Libenzi
2007-04-20  5:16                                                         ` Mike Galbraith
2007-04-19  7:14                                                   ` Mike Galbraith
2007-04-18 21:04                                             ` Ingo Molnar
2007-04-18 19:23                                         ` Linus Torvalds
2007-04-18 19:56                                           ` Davide Libenzi
2007-04-18 20:11                                             ` Linus Torvalds
2007-04-19  0:22                                               ` Davide Libenzi
2007-04-19  0:30                                                 ` Linus Torvalds
2007-04-18 18:02                                       ` William Lee Irwin III
2007-04-18 18:12                                         ` Ingo Molnar
2007-04-18 18:36                                       ` Diego Calleja
2007-04-19  0:37                                       ` Peter Williams
2007-04-18 19:05                                     ` Davide Libenzi
2007-04-18 19:13                                     ` Michael K. Edwards
2007-04-19  3:18                                   ` Nick Piggin
2007-04-19  5:14                                     ` Andrew Morton
2007-04-19  6:38                                       ` Ingo Molnar
2007-04-19  7:57                                         ` William Lee Irwin III
2007-04-19 11:50                                           ` Peter Williams
2007-04-20  5:26                                             ` William Lee Irwin III
2007-04-20  6:16                                               ` Peter Williams
2007-04-19  8:33                                         ` Nick Piggin
2007-04-21 13:40                                   ` Bill Davidsen
2007-04-17  6:50                   ` Davide Libenzi
2007-04-17  7:09                     ` William Lee Irwin III
2007-04-17  7:22                       ` Peter Williams
2007-04-17  7:23                       ` Nick Piggin
2007-04-17  7:27                       ` Davide Libenzi
2007-04-17  7:33                         ` Nick Piggin
2007-04-17  7:33                       ` Ingo Molnar
2007-04-17  7:40                         ` Nick Piggin
2007-04-17  7:58                           ` Ingo Molnar
2007-04-17  9:05                         ` William Lee Irwin III
2007-04-17  9:24                           ` Ingo Molnar
2007-04-17  9:57                             ` William Lee Irwin III
2007-04-17 10:01                               ` Ingo Molnar
2007-04-17 11:31                               ` William Lee Irwin III
2007-04-17 22:08                             ` Matt Mackall
2007-04-17 22:32                               ` William Lee Irwin III
2007-04-17 22:39                                 ` Matt Mackall
2007-04-17 22:59                                   ` William Lee Irwin III
2007-04-17 22:57                                     ` Matt Mackall
2007-04-18  4:29                                       ` William Lee Irwin III
2007-04-18  4:42                                         ` Davide Libenzi
2007-04-18  7:29                                       ` James Bruce
2007-04-17  7:11                     ` Nick Piggin
2007-04-17  7:21                       ` Davide Libenzi
2007-04-17  6:23               ` Peter Williams
2007-04-17  6:44                 ` Nick Piggin
2007-04-17  7:48                   ` Peter Williams
2007-04-17  7:56                     ` Nick Piggin
2007-04-17 13:16                       ` Peter Williams
2007-04-18  4:46                         ` Nick Piggin
2007-04-17  8:44                 ` Ingo Molnar
2007-04-19  2:20                   ` Peter Williams
2007-04-15 15:05   ` Ingo Molnar
2007-04-15 20:05     ` Matt Mackall
2007-04-15 20:48       ` Ingo Molnar
2007-04-15 21:31         ` Matt Mackall
2007-04-16  3:03           ` Nick Piggin
2007-04-16 14:28             ` Matt Mackall
2007-04-17  3:31               ` Nick Piggin
2007-04-17 17:35                 ` Matt Mackall
2007-04-16 15:45           ` William Lee Irwin III
2007-04-15 23:39         ` William Lee Irwin III
2007-04-16  1:06           ` Peter Williams
2007-04-16  3:04             ` William Lee Irwin III
2007-04-16  5:09               ` Peter Williams
2007-04-16 11:04                 ` William Lee Irwin III
2007-04-16 12:55                   ` Peter Williams
2007-04-16 23:10                     ` Michael K. Edwards
2007-04-17  3:55                       ` Nick Piggin
2007-04-17  4:25                         ` Peter Williams
2007-04-17  4:34                           ` Nick Piggin
2007-04-17  6:03                             ` Peter Williams
2007-04-17  6:14                               ` William Lee Irwin III
2007-04-17  6:23                               ` Nick Piggin
2007-04-17  9:36                               ` Ingo Molnar
2007-04-17  8:24                         ` William Lee Irwin III
     [not found]                     ` <20070416135915.GK8915@holomorphy.com>
     [not found]                       ` <46241677.7060909@bigpond.net.au>
     [not found]                         ` <20070417025704.GM8915@holomorphy.com>
     [not found]                           ` <462445EC.1060306@bigpond.net.au>
     [not found]                             ` <20070417053147.GN8915@holomorphy.com>
     [not found]                               ` <46246A7C.8050501@bigpond.net.au>
     [not found]                                 ` <20070417064109.GP8915@holomorphy.com>
2007-04-17  8:00                                   ` Peter Williams
2007-04-17 10:41                                     ` William Lee Irwin III
2007-04-17 13:48                                       ` Peter Williams
2007-04-18  0:27                                         ` Peter Williams
2007-04-18  2:03                                           ` William Lee Irwin III
2007-04-18  2:31                                             ` Peter Williams
2007-04-16 17:22             ` Chris Friesen
2007-04-17  0:54               ` Peter Williams
2007-04-17 15:52                 ` Chris Friesen
2007-04-17 23:50                   ` Peter Williams
2007-04-18  5:43                     ` Chris Friesen
2007-04-18 13:00                       ` Peter Williams
2007-04-16  5:16     ` Con Kolivas
2007-04-16  5:48       ` Gene Heskett
2007-04-15 12:29 ` Esben Nielsen
2007-04-15 13:04   ` Ingo Molnar
2007-04-16  7:16     ` Esben Nielsen
2007-04-15 22:49 ` Ismail Dönmez
2007-04-15 23:23   ` Arjan van de Ven
2007-04-15 23:33     ` Ismail Dönmez
2007-04-16 11:58   ` Ingo Molnar
2007-04-16 12:02     ` Ismail Dönmez
2007-04-16 22:00 ` Andi Kleen
2007-04-16 21:05   ` Ingo Molnar
2007-04-16 21:21     ` Andi Kleen
2007-04-17  7:56 ` Andy Whitcroft
2007-04-17  9:32   ` Nick Piggin
2007-04-17  9:59     ` Ingo Molnar
2007-04-17 11:11       ` Nick Piggin
2007-04-18  8:55       ` Nick Piggin
2007-04-18  9:33         ` Con Kolivas
2007-04-18 12:14           ` Nick Piggin
2007-04-18 12:33             ` Con Kolivas
2007-04-18 21:49               ` Con Kolivas
2007-04-18  9:53         ` Ingo Molnar
2007-04-18 12:13           ` Nick Piggin
2007-04-18 12:49             ` Con Kolivas
2007-04-19  3:28               ` Nick Piggin
2007-04-18 10:22   ` Ingo Molnar

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox