block: Adding ROW scheduling algorithm

This patch adds the implementation of a new scheduling algorithm - ROW.
The policy of this algorithm is to prioritize READ requests over WRITE
as much as possible without starving the WRITE requests.
The requests are kept in queues according to their priority. The dispatch
is done in a Round Robin manner with a different slice for each queue.
READ request queues get bigger dispatch quantum than the write requests.

Signed-off-by: Tatyana Brokhman <tlinder@xxxxxxxxxxxxxx>
---
v4:
  - Fix bug in idling mechanism:
    -- Fix the delay passed to scedule_delayed_work
    -- Change the idle delay and idling-trigger frequency to be HZ dependent
  - Destroy idle_workqueue on queue exit
  - Update the documentation

v3:
  - Fix bug in forced dispatch: Don't idle if forced dispatch

v2:
  No changes. Resend.

v1: Initial version
row-iosched: Backport to 3.0
compile with row
Revert "cgroups: introduce timer slack subsystem"

This reverts commit 3d67f97ab0566f3b425e8b0f666ca24d713e9cc7.
Introduce timer slack controller

From: "Kirill A. Shutemov" <kirill@shutemov.name>

task_get_effective_timer_slack() returns timer slack value to be used
to configure per-task timers. It can be equal or higher than task's
timer slack value.

For now task_get_effective_timer_slack() returns timer_slack_ns of the
task. Timer slack cgroup controller will implement a bit more
sophisticated logic.

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>

From: "Kirill A. Shutemov" <kirill@shutemov.name>

PR_GET_EFFECTIVE_TIMERSLACK allows process to know its effective timer
slack value.

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>

From: "Kirill A. Shutemov" <kirill@shutemov.name>

Every task_struct has timer_slack_ns value. This value uses to round up
poll() and select() timeout values. This feature can be useful in
mobile environment where combined wakeups are desired.

Originally, prctl() was the only way to change timer slack value of
a process. So you was not able change timer slack value of another
process.

cgroup subsys "timer_slack" implements timer slack controller. It
provides a way to set minimal timer slack value for a group of tasks.
If a task belongs to a cgroup with minimal timer slack value higher than
task's value, cgroup's value will be applied.

Timer slack controller allows to implement setting timer slack value of
a process based on a policy. For example, you can create foreground and
background cgroups and move tasks between them based on system state.

Idea-by: Jacob Pan <jacob.jun.pan@linux.intel.com>
Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>

From: "Kirill A. Shutemov" <kirill@shutemov.name>

Changelog:

v10 [7 month later, thanks to A Plumber's Wish List]:
 - rebased to linux-next-20111011
v9:
 - update documentation
 - minor cleanup
v8:
 - change hiearchy rules
 - introduce timer_slack.effective_slack_ns
 - get_task_timer_slack() -> task_get_effective_timer_slack()
 - task_get_effective_timer_slack() splited in separate patch
 - implement PR_GET_EFFECTIVE_TIMERSLACK
v7:
 - totally reworked interface and rewritten from scratch
   (See Documentation/cgroups/timer_slack.txt for more information)
v6:
 - add documentation
 - use notifier_call_chain() instead of check hook
 - fix validate_change()
 - cleanup
v5:
 - -EBUSY on writing to timer_slack.min_slack_ns/max_slack_ns if a child has
   wider min-max range
v4:
 - hierarchy support
 - drop dummy_timer_slack_check()
 - workaround lockdep false (?) positive
 - allow 0 as timer slack value
v3:
 - rework interface
 - s/EXPORT_SYMBOL/EXPORT_SYMBOL_GPL/
v2:
 - fixed with CONFIG_CGROUP_TIMER_SLACK=y
v1:
 - initial revision

Kirill A. Shutemov (3):
  hrtimer: introduce effective timer slack
  hrtimer: implement PR_GET_EFFECTIVE_TIMERSLACK
  cgroups: introduce timer slack controller

 Documentation/cgroups/timer_slack.txt |   72 +++++++++++++++++++
 fs/select.c                           |    7 +--
 include/linux/cgroup_subsys.h         |    7 ++
 include/linux/prctl.h                 |    6 ++
 include/linux/sched.h                 |   10 +++
 init/Kconfig                          |    8 ++
 kernel/Makefile                       |    1 +
 kernel/cgroup_timer_slack.c           |  124 +++++++++++++++++++++++++++++++++
 kernel/fork.c                         |    4 +
 kernel/futex.c                        |    4 +-
 kernel/hrtimer.c                      |    2 +-
 kernel/sys.c                          |    3 +
 12 files changed, 240 insertions(+), 8 deletions(-)
 create mode 100644 Documentation/cgroups/timer_slack.txt
 create mode 100644 kernel/cgroup_timer_slack.c
removed unused code