[click] adaptive scheduler

[Eddie Kohler]

Hi all,

So Petros Zerfos's adaptive scheduler is checked in to Click 1.3pre1,
finally at last! It is active if you compile with --enable-adaptive.

The adaptive scheduler improves the way that Click and other Linux tasks
share the CPU on a uniprocessor machine, and provides more fine-grained
control over that sharing. In particular:

* A new Click parameter, 'min_cpu_share', specifies the *minimum* fraction
  of the CPU that Click will take.

  Another new parameter, 'max_cpu_share', specifies Click's *maximum* CPU
  fraction. (1 - max_cpu_share) of the CPU will always be available for
  other applications, such as tcpdump.

  The defaults for these parameters are 0.005 and 0.8, respectively (.5%
  and 80%).

* Click monitors how much "work" the router is accomplishing. Every task
  now indicates whether it successfully accomplished a unit of work. A
  task's "employment" for a given run equals the number of times it
  accomplished work, divided by the number of times it ran. 

* After every run, Click adjusts its CPU share to equal the maximum
  employment for any task, pinned to the range [min_cpu_share,
  max_cpu_share]. So if one task was 100% busy, Click will use
  max_cpu_share; if no task is busy, Click will use min_cpu_share; and if
  the busiest task was 40% busy, Click will use 40% of the CPU (pinned).

* Linux gets (1 - click_cpu_share) CPU share.

* A stride scheduling algorithm is used to schedule Click and Linux
  according to the resulting CPU share.

So if Click is taking up too much CPU, lower max_cpu_share. If it's
reacting slowly to changing network events, raise min_cpu_share. (Both are
handlers in /click; read 'man 8 click.o'.)

Relevant code in task.hh, routerthread.hh, and routerthread.cc.

Please let us know if you have trouble with this scheduler, or have ideas
for better parameters or scheduling algorithms.

Thanks Petros!
Eddie