[PATCH] Staircase cpu scheduler 2.6.8-rc2-mm1

• Previous message: Hiroshi Miura: "[PATCH][ACPI] Panasonic Hotkey Driver"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date:	Sun, 01 Aug 2004 00:20:04 +1000
To: linux kernel mailing list <linux-kernel@vger.kernel.org>

This is a rewrite of the scheduler policy for 2.6, based on the current
O(1) scheduler. It removes a lot of complexity and replaces it with an
obvious and simple design

Aims:

   - Simple predictable design.
   - Good scalability.
   - Interactive by design rather than have complicated interactivity
     heuristics
   - Maintain fairer cpu distribution with load
   - Low scheduling latency for SCHED_NORMAL tasks.
   - Low overhead.
   - Making renicing processes actually matter for CPU distribution
     (nice 0 gets 19 times what nice +19 gets)
   - Easily configured for different workloads (compute server,
     non-interactive)

Summary of design:
   A descending foreground-background single runqueue per cpu priority
   array

Details:
   This patch takes advantage of the existing infrastructure but has no
   expired array. Real time tasks are treated simiilary as the current
   fixed priority & timeslice system. The details are in the management
   of normal policy (SCHED_NORMAL) tasks.

   Normal policy tasks have a dynamic priority that drops by one every
   RR_INTERVAL which equals 10ms. Once they drop to lowest priority they
   are requeued at their top dynamic priority again.

   Every time a task sleeps it gains "burst" which allows them to stay at
   their highest priority for an extra interval per burst before dropping
   priority.

   The sub-jiffy case is handled specially to prevent it fooling this
   system, by continuing their current timeslice next wakeup. Tasks that
   have just forked are also treated the same way.

   Yield()ing is implemented by putting tasks to the end of the lowest
   priority queue, but once scheduled the task wakes up to it's normal
   first wake up priority.

Use a fixed font to see clearly:

ie
RR_INTERVALs nice 0 task
20<-------------->40 PRI
11111111111111111111
21111111111111111110
31111111111111111100
and so on

nice +10 task
30<---->40 PRI
1111111111
2111111110
3111111100
and so on

   This is how cpu distribution is kept proportional while optimising
   latency for interactive tasks (which wake frequently).

Features:
   This scheduler has coded in 2 simple sysctl configuration options.

/proc/sys/kernel/interactive

   is a sysctl which when set to 0 disables the burst mechanism entirely
   making all tasks descend the staircase in a more rigid manner and thus
   maintaining much stricter cpu distribution (ie suitable to multi-user
   setups, servers and non gui machines.) Since the design remains
   foreground-background descending interactivity is maintained but
   response becomes slower/proportional to load.

/proc/sys/kernel/compute

   is a sysctl which puts the cpu scheduler in "computational" mode which
   is designed for optimal cpu throughput at the expense of latency. It
   enlarges timeslices to 10 times larger than default and introduces
   delayed preemption of normal tasks to optimise cpu cache utilisation.
   This mode effectively sets interactive to 0 as well.

With thanks to William Lee Irwin III and Zwane Mwaikambo for patches and
debugging and Peter Williams for useful suggestions.

Patch against 2.6.8-rc2-mm1
Signed-off-by: Con Kolivas <kernel@kolivas.org>

  fs/proc/array.c | 4
  include/linux/sched.h | 15
  include/linux/sysctl.h | 2
  init/main.c | 1
  kernel/exit.c | 1
  kernel/sched.c | 865
++++++++++++++-----------------------------------
  kernel/sysctl.c | 16
  7 files changed, 283 insertions(+), 621 deletions(-)

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

• text/x-fortran attachment: from_2.6.8-rc2-mm1_to_staircase7.F

• application/pgp-signature attachment: OpenPGP digital signature

• Previous message: Hiroshi Miura: "[PATCH][ACPI] Panasonic Hotkey Driver"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]