changeset 67:992a411c98b6

History of the process scheduler, notes about cross compiling, and some tweaks.
author Rob Landley <rob@landley.net>
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=http://mirell.org/kernel-traffic/kernel-traffic/kt20020107_149.html#1>came to a head</a> in December 2001.</p>
+
+<p>In January 2002, Ingo Molnar
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20020114_150.html#4>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=http://mirell.org/kernel-traffic/kernel-traffic/kt20020513_166.html#4>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
+Traffic.</p>
+
+<p>During 2002 this work included
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20020121_151.html#8>preemption</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20020121_151.html#9>User Mode Linux support</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20020211_153.html#2>new drops</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20020211_153.html#7>runtime tuning</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20020304_156.html#6>NUMA support</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20020429_164.html#4>cpu affinity</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20020617_171.html#4>scheduler hints</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20020701_173.html#1>64-bit support</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20020715_175.html#5>backports to the 2.4 kernel</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20020715_175.html#4>SCHED_IDLE</a>,
+discussion of <a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20020729_177.html#1>gang scheduling</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20021014_188.html#4>more NUMA</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20021118_192.html#9>even more NUMA</a>).  By the end of 2002, the O(1) scheduler was becoming
+the standard <a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20021223_197.html#1>even in the 2.4 series</a>.</p>
+
+<p>2003 saw support added for
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20030124_202.html#14>hyperthreading as a NUMA variant</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20030330_211.html#3>interactivity bugfix</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20030616_219.html#4>starvation and affinity bugfixes</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20030616_219.html#8>more NUMA improvements</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20030811_227.html#2>interactivity improvements</a>,
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20030811_227.html#8>even more NUMA improvements</a>,
+a proposal for <a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20031026_237.html#7>Variable Scheduling Timeouts</a> (the first rumblings of what
+would later come to be called "dynamic ticks"),
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20031201_243.html#10>more on hyperthreading</a>...</p>
+
+<p>In 2004 there was work on <a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20040120_248.html#2>load balancing and priority handling</a>, and
+<a href=http://mirell.org/kernel-traffic/kernel-traffic/kt20040212_252.html#5>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=http://lwn.net/Articles/80911/>domain-based scheduler</a>
+and Con Colivas' <a href=http://lwn.net/Articles/87729/>staircase scheduler</a>.  The follow-up article <a href=http://lwn.net/Articles/96554/>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>
+
+<ul>
+<li><a href=http://lwn.net/Articles/83633/>Filtered wakeups</a></li>
+<li><a href=http://lwn.net/Articles/105366/>When should a process be migrated</a></li>
+<li><a href=http://lwn.net/Articles/109458/>Pluggable and realtime schedulers</a></li>
+<li><a href=http://lwn.net/Articles/120797/>Low latency for audio applications:</a></li>
+<li><a href=http://lwn.net/Articles/176635/>Solving starvation problems in the scheduler:</a></li>
+<li><a href=http://lwn.net/Articles/186438/>SMPnice</a></li>
+</ul>
+
+<p>In 2007, Con Colivas proposed a new scheduler, <a href=http://lwn.net/Articles/224865/>The Rotating Staircase Deadline Scheduler</a>, which
+<a href=http://lwn.net/Articles/226054/>hit a snag</a>.  Ingo
+Molnar came up with a new scheduler, which he named the
+<a href=http://lwn.net/Articles/230501/>Completely Fair Scheduler</a>,
+described in the LWN writeups
+<a href=http://lwn.net/Articles/230574/>Schedulers: the plot thickens</a>,
+<a href=http://lwn.net/Articles/231672/>this week in the scheduling discussion</a>, and
+<a href=http://lwn.net/Articles/240474/>CFS group scheduling</a>.</p>
+
+<p>The CFS scheduler was merged into 2.6.23.</p>
+</span>
+
     <span id="fork, exec">
     </span>
     <span id="sleep">
     </span>
+  </span>
   <span id="Timers">
     <span id="Interrupt handling">
     </span>
@@ -343,6 +424,8 @@
   </span>
 
   <span id="Hotplug">
+    http://kernel.org/ols/2001/hotplug.pdf
+    local/hotplug-history.html
   </span>
   <span id="Input core">
   </span>
@@ -385,12 +468,69 @@
 </span>
 
 <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=http://landley.net/writing/docs/cross-compiling.html>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>
+
   <span id="Architectures">
 <pre>
-ls arch/*
+alpha
+arm
+avr32
+blackfin
+cris
+frv
+h8300
+i386
+ia64
+m32r
+m68k
+m68knommu
+mips
+parisc
+powerpc
+ppc
+s390
+sh
+sh64
+sparc
+sparc64
+um
+v850
+x86_64
+xtensa
+
 include/asm-generic
 uml
-x86, x86-64 powerpc/ppc arm mips sparc sh 68k/coldfire
 </pre>
   </span>
   <span id="DMA, IRQ, MMU (mmap), IOMMU, port I/O">
@@ -401,8 +541,6 @@
   </span>
 </span>
 
-</span>
-
 <span id="Following Linux development">
   <span id="Distibutions.">
   </span>