changeset 67:992a411c98b6

History of the process scheduler, notes about cross compiling, and some tweaks.
author Rob Landley <>
date Wed, 10 Oct 2007 04:51:31 -0500
parents b661eca51591
children 1f41643cfe8e
files master.idx
diffstat 1 files changed, 142 insertions(+), 4 deletions(-) [+]
line wrap: on
line diff
--- a/master.idx	Tue Oct 09 17:08:23 2007 -0500
+++ b/master.idx	Wed Oct 10 04:51:31 2007 -0500
@@ -231,10 +231,91 @@
 <span id="Kernel infrastructure">
   <span id="Process Scheduler">
+<span id="History of the Linux Process Scheduler">
+<p>The original Linux process scheduler was a simple design based on
+a goodness() function that recalculated the priority of every task at every
+context switch, to find the next task to switch to.  This served almost
+unchanged through the 2.4 series, but didn't scale to large numbers of
+processes, nor to SMP.  By 2001 there were calls for
+change (such as <a href=ols/2001/elss.pdf>this OLS paper</a>), and the
+issue <a href=>came to a head</a> in December 2001.</p>
+<p>In January 2002, Ingo Molnar
+<a href=>introduced the "O(1)" process scheduler</a> for the 2.5 kernel series, a design
+based on separate "active" and "expired" arrays, one per processor.  As the name
+implied, this found the next task to switch to in constant time no matter
+how many processes the system was running.</p>
+<p>Other developers (<a href=>such as Con Colivas</a>) started working on it,
+and began a period of extensive scheduler development.  The early history
+of Linux O(1) scheduler development was covered by the website Kernel
+<p>During 2002 this work included
+<a href=>preemption</a>,
+<a href=>User Mode Linux support</a>,
+<a href=>new drops</a>,
+<a href=>runtime tuning</a>,
+<a href=>NUMA support</a>,
+<a href=>cpu affinity</a>,
+<a href=>scheduler hints</a>,
+<a href=>64-bit support</a>,
+<a href=>backports to the 2.4 kernel</a>,
+<a href=>SCHED_IDLE</a>,
+discussion of <a href=>gang scheduling</a>,
+<a href=>more NUMA</a>,
+<a href=>even more NUMA</a>).  By the end of 2002, the O(1) scheduler was becoming
+the standard <a href=>even in the 2.4 series</a>.</p>
+<p>2003 saw support added for
+<a href=>hyperthreading as a NUMA variant</a>,
+<a href=>interactivity bugfix</a>,
+<a href=>starvation and affinity bugfixes</a>,
+<a href=>more NUMA improvements</a>,
+<a href=>interactivity improvements</a>,
+<a href=>even more NUMA improvements</a>,
+a proposal for <a href=>Variable Scheduling Timeouts</a> (the first rumblings of what
+would later come to be called "dynamic ticks"),
+<a href=>more on hyperthreading</a>...</p>
+<p>In 2004 there was work on <a href=>load balancing and priority handling</a>, and
+<a href=>still more work on hyperthreading</a>...</p>
+<p>In 2004 developers proposed several extensive changes to the O(1) scheduler.
+Linux Weekly News wrote about Nick Piggin's
+<a href=>domain-based scheduler</a>
+and Con Colivas' <a href=>staircase scheduler</a>.  The follow-up article <a href=>Scheduler tweaks get serious</a> covers both.  Nick's scheduling domains
+were merged into the 2.6 series.</p>
+<p>Linux Weekly News also wrote about other scheduler work:</p>
+<li><a href=>Filtered wakeups</a></li>
+<li><a href=>When should a process be migrated</a></li>
+<li><a href=>Pluggable and realtime schedulers</a></li>
+<li><a href=>Low latency for audio applications:</a></li>
+<li><a href=>Solving starvation problems in the scheduler:</a></li>
+<li><a href=>SMPnice</a></li>
+<p>In 2007, Con Colivas proposed a new scheduler, <a href=>The Rotating Staircase Deadline Scheduler</a>, which
+<a href=>hit a snag</a>.  Ingo
+Molnar came up with a new scheduler, which he named the
+<a href=>Completely Fair Scheduler</a>,
+described in the LWN writeups
+<a href=>Schedulers: the plot thickens</a>,
+<a href=>this week in the scheduling discussion</a>, and
+<a href=>CFS group scheduling</a>.</p>
+<p>The CFS scheduler was merged into 2.6.23.</p>
     <span id="fork, exec">
     <span id="sleep">
+  </span>
   <span id="Timers">
     <span id="Interrupt handling">
@@ -343,6 +424,8 @@
   <span id="Hotplug">
+    local/hotplug-history.html
   <span id="Input core">
@@ -385,12 +468,69 @@
 <span id="Hardware">
+<span id="Cross compiling vs native compiling">
+<p>By default, Linux builds for the same architecture the host system is
+running.  This is called "native compiling".  An x86 system building an x86
+kernel, x86-64 building x86-64, or powerpc building powerpc are all examples
+of native compiling.</p>
+<p>Building different binaries than the host runs is called cross compiling.
+<a href=>Cross
+compiling is hard</a>.  The build system for the Linux kernel supports cross
+compiling via a two step process: 1) Specify a different architecture (ARCH)
+during the configure, make, and install stages.  2) Supply a cross compiler
+(CROSS) which can output the correct kind of binary code.</p>
+<p>To specify a different architecture than the host, either define the "ARCH"
+environment variable or else add "ARCH=xxx" to the make command line for each
+of the make config, make, and make install stages.  The acceptable values for
+ARCH are the names of the directories in the "arch" subdirectory of the Linux
+kernel source code.  All stages of the build must use the same architecture.
+(Building a second architecture in the same source directory requires "make
+distclean"; just "make clean" isn't sufficient.)</p>
+<p>To specify a cross compiler prefix, define the CROSS environment variable
+(or add CROSS= to each make command line).  Native compiler tools, which output
+code aimed at the environment they're running in, usually have a simple name
+("gcc", "ld", "strip").  Cross compilers usually add a prefix to
+the name of each tool, indicating the target they produce code for.  To tell
+the Linux kernel build to use a cross compiler named "armv4l-gcc" (and
+corresponding "armv4l-ld" and "armv4l-strip") specify "CROSS=armv4l-".
+(Prefixes ending in a dash are common, and forgetting the trailing dash in
+CROSS is a common mistake.  Don't forget to add the cross compiler tools to
+your $PATH.)</p>
   <span id="Architectures">
-ls arch/*
-x86, x86-64 powerpc/ppc arm mips sparc sh 68k/coldfire
   <span id="DMA, IRQ, MMU (mmap), IOMMU, port I/O">
@@ -401,8 +541,6 @@
 <span id="Following Linux development">
   <span id="Distibutions.">