Mercurial > hg > kdocs
diff master.idx @ 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 | eb75b1bfc3d1 |
children | 1f41643cfe8e |
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>