Apply BFS 406 patch. Minor manual edits by myself for 3.0.31 compatibility

BFS - The Brain Fuck Scheduler by Con Kolivas.

Goals.

The goal of the Brain Fuck Scheduler, referred to as BFS from here on, is to
completely do away with the complex designs of the past for the cpu process
scheduler and instead implement one that is very simple in basic design.
The main focus of BFS is to achieve excellent desktop interactivity and
responsiveness without heuristics and tuning knobs that are difficult to
understand, impossible to model and predict the effect of, and when tuned to
one workload cause massive detriment to another.

Design summary.

BFS is best described as a single runqueue, O(n) lookup, earliest effective
virtual deadline first design, loosely based on EEVDF (earliest eligible virtual
deadline first) and my previous Staircase Deadline scheduler. Each component
shall be described in order to understand the significance of, and reasoning for
it. The codebase when the first stable version was released was approximately
9000 lines less code than the existing mainline linux kernel scheduler (in
2.6.31). This does not even take into account the removal of documentation and
the cgroups code that is not used.

Design reasoning.

The single runqueue refers to the queued but not running processes for the
entire system, regardless of the number of CPUs. The reason for going back to
a single runqueue design is that once multiple runqueues are introduced,
per-CPU or otherwise, there will be complex interactions as each runqueue will
be responsible for the scheduling latency and fairness of the tasks only on its
own runqueue, and to achieve fairness and low latency across multiple CPUs, any
advantage in throughput of having CPU local tasks causes other disadvantages.
This is due to requiring a very complex balancing system to at best achieve some
semblance of fairness across CPUs and can only maintain relatively low latency
for tasks bound to the same CPUs, not across them. To increase said fairness
and latency across CPUs, the advantage of local runqueue locking, which makes
for better scalability, is lost due to having to grab multiple locks.

A significant feature of BFS is that all accounting is done purely based on CPU
used and nowhere is sleep time used in any way to determine entitlement or
interactivity. Interactivity "estimators" that use some kind of sleep/run
algorithm are doomed to fail to detect all interactive tasks, and to falsely tag
tasks that aren't interactive as being so. The reason for this is that it is
close to impossible to determine that when a task is sleeping, whether it is
doing it voluntarily, as in a userspace application waiting for input in the
form of a mouse click or otherwise, or involuntarily, because it is waiting for
another thread, process, I/O, kernel activity or whatever. Thus, such an
estimator will introduce corner cases, and more heuristics will be required to
cope with those corner cases, introducing more corner cases and failed
interactivity detection and so on. Interactivity in BFS is built into the design
by virtue of the fact that tasks that are waking up have not used up their quota
of CPU time, and have earlier effective deadlines, thereby making it very likely
they will preempt any CPU bound task of equivalent nice level. See below for
more information on the virtual deadline mechanism. Even if they do not preempt
a running task, because the rr interval is guaranteed to have a bound upper
limit on how long a task will wait for, it will be scheduled within a timeframe
that will not cause visible interface jitter.

Design details.

Task insertion.

BFS inserts tasks into each relevant queue as an O(1) insertion into a double
linked list. On insertion, *every* running queue is checked to see if the newly
queued task can run on any idle queue, or preempt the lowest running task on the
system. This is how the cross-CPU scheduling of BFS achieves significantly lower
latency per extra CPU the system has. In this case the lookup is, in the worst
case scenario, O(n) where n is the number of CPUs on the system.

Data protection.

BFS has one single lock protecting the process local data of every task in the
global queue. Thus every insertion, removal and modification of task data in the
global runqueue needs to grab the global lock. However, once a task is taken by
a CPU, the CPU has its own local data copy of the running process' accounting
information which only that CPU accesses and modifies (such as during a
timer tick) thus allowing the accounting data to be updated lockless. Once a
CPU has taken a task to run, it removes it from the global queue. Thus the
global queue only ever has, at most,

	(number of tasks requesting cpu time) - (number of logical CPUs) + 1

tasks in the global queue. This value is relevant for the time taken to look up
tasks during scheduling. This will increase if many tasks with CPU affinity set
in their policy to limit which CPUs they're allowed to run on if they outnumber
the number of CPUs. The +1 is because when rescheduling a task, the CPU's
currently running task is put back on the queue. Lookup will be described after
the virtual deadline mechanism is explained.

Read the full documentation for BFS in the documentation section of the src.

Please enter the commit message for your changes. Lines starting