Add BFQ scheduler

PS3: Update kconfig to enable BFQ as a default scheduler

From 18bc095e952d31d5e07b88b8b89fb2ae8c3048ad Mon Sep 17 00:00:00 2001 From: Arianna Avanzini <avanzini.arianna@gmail.com> Date: Sat, 4 Feb 2012 10:55:51 +0100 Subject: [PATCH 1/2] block: cgroups, kconfig, build bits for BFQ-v5r1-3.4

Update Kconfig.iosched to include kernel configuration options
for BFQ. Add a Kconfig option and do the related Makefile changes
to compile the scheduler. Also let the cgroups subsystem know about
the BFQ I/O controller.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>

Conflicts:
	block/Kconfig.iosched
	block/Makefile

Change-Id: I4d8304c4888d4efe2185c9aa9421622c8bec0af7

rom 2ebfcb6f325e27261c80a5c3b3a9e9e5ba3749a8 Mon Sep 17 00:00:00 2001 From: Arianna Avanzini <avanzini.arianna@gmail.com> Date: Sun, 5 Feb 2012 01:04:27 +0100 Subject: [PATCH 2/2] block: introduce the BFQ-v5r1 I/O sched for 3.4

Add the BFQ-v5r1 I/O scheduler to 3.4.
The general structure is borrowed from CFQ, as much code. A (bfq_)queue is
associated to each task doing I/O on a device, and each time a scheduling
decision has to be taken a queue is selected and it is served until it expires.

    - Slices are given in the service domain: tasks are assigned budgets,
      measured in number of sectors. Once got the disk, a task must
      however consume its assigned budget within a configurable maximum time
      (by default, the maximum possible value of the budgets is automatically
      computed to comply with this timeout). This allows the desired latency
      vs "throughput boosting" tradeoff to be set.

    - Budgets are scheduled according to a variant of WF2Q+, implemented
      using an augmented rb-tree to take eligibility into account while
      preserving an O(log N) overall complexity.

    - A low-latency tunable is provided; if enabled, both interactive and soft
      real-time applications are guaranteed very low latency.

    - Latency guarantees are preserved also in presence of NCQ.

    - High throughput with flash-based devices, while still preserving
      latency guarantees.

    - Useful features borrowed from CFQ: cooperating-queues merging (with
      some additional optimizations with respect to the original CFQ version),
      static fallback queue for OOM.

    - BFQ supports full hierarchical scheduling, exporting a cgroups
      interface.  Each node has a full scheduler, so each group can
      be assigned its own ioprio and an ioprio_class.

    - If the cgroups interface is used, weights can be explictly assigned,
      otherwise ioprio values are mapped to weights using the relation
      weight = IOPRIO_BE_NR - ioprio.

    - ioprio classes are served in strict priority order, i.e., lower
      priority queues are not served as long as there are higher priority
      queues.  Among queues in the same class the bandwidth is distributed
      in proportion to the weights of each queue. A very thin extra bandwidth
      is however guaranteed to the Idle class, to prevent it from starving.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>

Change-Id: I4d8304c4888d4efe2185c9aa9421622c8bec0af8