[PATCH 14/14] sched: add sched_dl documentation.

[PATCH 14/14] sched: add sched_dl documentation.

[Juri Lelli]

From: Dario Faggioli <raistlin@linux.it>

Add in Documentation/scheduler/ some hints about the design
choices, the usage and the future possible developments of the
sched_dl scheduling class and of the SCHED_DEADLINE policy.

Signed-off-by: Dario Faggioli <raistlin@linux.it>
Signed-off-by: Juri Lelli <juri.lelli@gmail.com>
---
 Documentation/scheduler/sched-deadline.txt |  196 ++++++++++++++++++++++++++++
 kernel/sched/deadline.c                    |    3 +-
 2 files changed, 198 insertions(+), 1 deletion(-)
 create mode 100644 Documentation/scheduler/sched-deadline.txt

diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
new file mode 100644
index 0000000..4d1ed52
--- /dev/null
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -0,0 +1,196 @@
+			  Deadline Task Scheduling
+			  ------------------------
+
+CONTENTS
+========
+
+0. WARNING
+1. Overview
+2. Task scheduling
+2. The Interface
+3. Bandwidth management
+  3.1 System-wide settings
+  3.2 Task interface
+  3.4 Default behavior
+4. Tasks CPU affinity
+  4.1 SCHED_DEADLINE and cpusets HOWTO
+5. Future plans
+
+
+0. WARNING
+==========
+
+ Fiddling with these settings can result in an unpredictable or even unstable
+ system behavior. As for -rt (group) scheduling, it is assumed that root users
+ know what they're doing.
+
+
+1. Overview
+===========
+
+ The SCHED_DEADLINE policy contained inside the sched_dl scheduling class is
+ basically an implementation of the Earliest Deadline First (EDF) scheduling
+ algorithm, augmented with a mechanism (called Constant Bandwidth Server, CBS)
+ that makes it possible to isolate the behavior of tasks between each other.
+
+
+2. Task scheduling
+==================
+
+ The typical -deadline task is composed of a computation phase (instance)
+ which is activated on a periodic or sporadic fashion. The expected (maximum)
+ duration of such computation is called the task's runtime; the time interval
+ by which each instance needs to be completed is called the task's relative
+ deadline. The task's absolute deadline is dynamically calculated as the
+ time instant a task (or, more properly) activates plus the relative
+ deadline.
+
+ The EDF[1] algorithm selects the task with the smallest absolute deadline as
+ the one to be executed first, while the CBS[2,3] ensures that each task runs
+ for at most its runtime every period, avoiding any interference between
+ different tasks (bandwidth isolation).
+ Thanks to this feature, also tasks that do not strictly comply with the
+ computational model described above can effectively use the new policy.
+ IOW, there are no limitations on what kind of task can exploit this new
+ scheduling discipline, even if it must be said that it is particularly
+ suited for periodic or sporadic tasks that need guarantees on their
+ timing behavior, e.g., multimedia, streaming, control applications, etc.
+
+ References:
+  1 - C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogram-
+      ming in a hard-real-time environment. Journal of the Association for
+      Computing Machinery, 20(1), 1973.
+  2 - L. Abeni , G. Buttazzo. Integrating Multimedia Applications in Hard
+      Real-Time Systems. Proceedings of the 19th IEEE Real-time Systems
+      Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf
+  3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab
+      Technical Report. http://xoomer.virgilio.it/lucabe72/pubs/tr-98-01.ps
+
+3. Bandwidth management
+=======================
+
+ In order for the -deadline scheduling to be effective and useful, it is
+ important to have some method to keep the allocation of the available CPU
+ bandwidth to the tasks under control.
+ This is usually called "admission control" and if it is not performed at all,
+ no guarantee can be given on the actual scheduling of the -deadline tasks.
+
+ Since when RT-throttling has been introduced each task group has a bandwidth
+ associated, calculated as a certain amount of runtime over a period.
+ Moreover, to make it possible to manipulate such bandwidth, readable/writable
+ controls have been added to both procfs (for system wide settings) and cgroupfs
+ (for per-group settings).
+ Therefore, the same interface is being used for controlling the bandwidth
+ distrubution to -deadline tasks and task groups, i.e., new controls but with
+ similar names, equivalent meaning and with the same usage paradigm are added.
+
+ However, more discussion is needed in order to figure out how we want to manage
+ SCHED_DEADLINE bandwidth at the task group level. Therefore, SCHED_DEADLINE
+ uses (for now) a less sophisticated, but actually very sensible, mechanism to
+ ensure that a certain utilization cap is not overcome per each root_domain.
+
+ Another main difference between deadline bandwidth management and RT-throttling
+ is that -deadline tasks have bandwidth on their own (while -rt ones don't!),
+ and thus we don't need an higher level throttling mechanism to enforce the
+ desired bandwidth.
+
+3.1 System wide settings
+------------------------
+
+ The system wide settings are configured under the /proc virtual file system.
+
+ The control knob that is added to the /proc virtual file system is
+ /proc/sys/kernel/sched_dl_runtime_us. It accepts (if written) and provides (if
+ read) the new runtime for each CPU in each root_domain. The period control knob
+ is instead shared with -rt settings (/proc/sys/kernel/sched_rt_period_us). 
+
+ The CPU bandwidth available to -deadline tasks is actually a sub-quota of
+ the -rt bandwidth. By default 95% of system bandwidth is allocate to -rt tasks;
+ among this, a 40% quota is reserved for -dl tasks. To have the actual quota a
+ simple multiplication is needed: .95 * .40 = .38 (38% of system bandwidth for
+ deadline tasks).
+
+ This means that, for a root_domain comprising M CPUs, -deadline tasks
+ can be created until the sum of their bandwidths stay below:
+
+   M * (sched_dl_runtime_us * rt_bw)
+
+ It is also possible to disable this bandwidth management logic, and
+ be thus free of oversubscribing the system up to any arbitrary level.
+ This is done by writing -1 in /proc/sys/kernel/sched_dl_runtime_us or
+ in /proc/sys/kernel/sched_rt_runtime_us.
+
+
+3.2 Task interface
+------------------
+
+ Specifying a periodic/sporadic task that executes for a given amount of
+ runtime at each instance, and that is scheduled according to the urgency of
+ its own timing constraints needs, in general, a way of declaring:
+  - a (maximum/typical) instance execution time,
+  - a minimum interval between consecutive instances,
+  - a time constraint by which each instance must be completed.
+
+ Therefore:
+  * a new struct sched_param2, containing all the necessary fields is
+    provided;
+  * the new scheduling related syscalls that manipulate it, i.e.,
+    sched_setscheduler2(), sched_setparam2() and sched_getparam2()
+    are implemented.
+
+
+3.3 Default behavior
+---------------------
+
+The default value for SCHED_DEADLINE bandwidth is to have dl_runtime equal to
+40000. Being rt_period equal to 1000000, by default, it means that -deadline
+tasks can use at most 40%, multiplied by the number of CPUs that compose the
+root_domain, for each root_domain.
+
+A -deadline task cannot fork.
+
+4. Tasks CPU affinity
+=====================
+
+-deadline tasks cannot have an affinity mask smaller that the entire
+root_domain they are created on. However, affinities can be specified
+through the cpuset facility (Documentation/cgroups/cpusets.txt).
+
+4.1 SCHED_DEADLINE and cpusets HOWTO
+------------------------------------
+
+An example of a simple configuration (pin a -deadline task to CPU0)
+follows (rt-app is used to create a -deadline task).
+
+mkdir /dev/cpuset
+mount -t cgroup -o cpuset cpuset /dev/cpuset
+cd /dev/cpuset
+mkdir cpu0
+echo 0 > cpu0/cpuset.cpus
+echo 0 > cpu0/cpuset.mems
+echo 1 > cpuset.cpu_exclusive
+echo 0 > cpuset.sched_load_balance
+echo 1 > cpu0/cpuset.cpu_exclusive
+echo 1 > cpu0/cpuset.mem_exclusive
+echo $$ > cpu0/tasks
+rt-app -t 100000:10000:d:0 -D5 (it is now actually superfluous to specify
+task affinity)
+
+5. Future plans
+===============
+
+Still missing:
+
+ - refinements to deadline inheritance, especially regarding the possibility
+   of retaining bandwidth isolation among non-interacting tasks. This is
+   being studied from both theoretical and practical point of views, and
+   hopefully we should be able to produce some demonstrative code soon;
+ - (c)group based bandwidth management, and maybe scheduling;
+ - access control for non-root users (and related security concerns to
+   address), which is the best way to allow unprivileged use of the mechanisms
+   and how to prevent non-root users "cheat" the system?
+
+As already discussed, we are planning also to merge this work with the EDF
+throttling patches [https://lkml.org/lkml/2010/2/23/239] but we still are in
+the preliminary phases of the merge and we really seek feedback that would
+help us decide on the direction it should take.
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 9c1fd55..2e762b5 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -350,7 +350,8 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se,
  * disrupting the schedulability of the system. Otherwise, we should
  * refill the runtime and set the deadline a period in the future,
  * because keeping the current (absolute) deadline of the task would
- * result in breaking guarantees promised to other tasks.
+ * result in breaking guarantees promised to other tasks (refer to
+ * Documentation/scheduler/sched-deadline.txt for more informations).
  *
  * This function returns true if:
  *
-- 
1.7.9.5

Re: [PATCH 14/14] sched: add sched_dl documentation.

[Randy Dunlap]

Hi,

Just a few minor edits...


On 11/07/13 05:47, Juri Lelli wrote:
> From: Dario Faggioli <raistlin@linux.it>
> 
> Add in Documentation/scheduler/ some hints about the design
> choices, the usage and the future possible developments of the
> sched_dl scheduling class and of the SCHED_DEADLINE policy.
> 
> Signed-off-by: Dario Faggioli <raistlin@linux.it>
> Signed-off-by: Juri Lelli <juri.lelli@gmail.com>
> ---
>  Documentation/scheduler/sched-deadline.txt |  196 ++++++++++++++++++++++++++++
>  kernel/sched/deadline.c                    |    3 +-
>  2 files changed, 198 insertions(+), 1 deletion(-)
>  create mode 100644 Documentation/scheduler/sched-deadline.txt
> 
> diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
> new file mode 100644
> index 0000000..4d1ed52
> --- /dev/null
> +++ b/Documentation/scheduler/sched-deadline.txt
> @@ -0,0 +1,196 @@
> +			  Deadline Task Scheduling
> +			  ------------------------
> +
> +CONTENTS
> +========
> +
> +0. WARNING
> +1. Overview
> +2. Task scheduling
> +2. The Interface
> +3. Bandwidth management
> +  3.1 System-wide settings
> +  3.2 Task interface
> +  3.4 Default behavior
> +4. Tasks CPU affinity
> +  4.1 SCHED_DEADLINE and cpusets HOWTO
> +5. Future plans
> +
> +
> +0. WARNING
> +==========
> +
> + Fiddling with these settings can result in an unpredictable or even unstable
> + system behavior. As for -rt (group) scheduling, it is assumed that root users
> + know what they're doing.
> +
> +
> +1. Overview
> +===========
> +
> + The SCHED_DEADLINE policy contained inside the sched_dl scheduling class is
> + basically an implementation of the Earliest Deadline First (EDF) scheduling
> + algorithm, augmented with a mechanism (called Constant Bandwidth Server, CBS)
> + that makes it possible to isolate the behavior of tasks between each other.
> +
> +
> +2. Task scheduling
> +==================
> +
> + The typical -deadline task is composed of a computation phase (instance)
> + which is activated on a periodic or sporadic fashion. The expected (maximum)
> + duration of such computation is called the task's runtime; the time interval
> + by which each instance needs to be completed is called the task's relative
> + deadline. The task's absolute deadline is dynamically calculated as the
> + time instant a task (or, more properly) activates plus the relative
> + deadline.
> +
> + The EDF[1] algorithm selects the task with the smallest absolute deadline as
> + the one to be executed first, while the CBS[2,3] ensures that each task runs
> + for at most its runtime every period, avoiding any interference between
> + different tasks (bandwidth isolation).
> + Thanks to this feature, also tasks that do not strictly comply with the
> + computational model described above can effectively use the new policy.
> + IOW, there are no limitations on what kind of task can exploit this new
> + scheduling discipline, even if it must be said that it is particularly
> + suited for periodic or sporadic tasks that need guarantees on their
> + timing behavior, e.g., multimedia, streaming, control applications, etc.
> +
> + References:
> +  1 - C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogram-
> +      ming in a hard-real-time environment. Journal of the Association for
> +      Computing Machinery, 20(1), 1973.
> +  2 - L. Abeni , G. Buttazzo. Integrating Multimedia Applications in Hard
> +      Real-Time Systems. Proceedings of the 19th IEEE Real-time Systems
> +      Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf
> +  3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab
> +      Technical Report. http://xoomer.virgilio.it/lucabe72/pubs/tr-98-01.ps
> +
> +3. Bandwidth management
> +=======================
> +
> + In order for the -deadline scheduling to be effective and useful, it is
> + important to have some method to keep the allocation of the available CPU
> + bandwidth to the tasks under control.
> + This is usually called "admission control" and if it is not performed at all,
> + no guarantee can be given on the actual scheduling of the -deadline tasks.
> +
> + Since when RT-throttling has been introduced each task group has a bandwidth
> + associated, calculated as a certain amount of runtime over a period.
> + Moreover, to make it possible to manipulate such bandwidth, readable/writable
> + controls have been added to both procfs (for system wide settings) and cgroupfs
> + (for per-group settings).
> + Therefore, the same interface is being used for controlling the bandwidth
> + distrubution to -deadline tasks and task groups, i.e., new controls but with
> + similar names, equivalent meaning and with the same usage paradigm are added.
> +
> + However, more discussion is needed in order to figure out how we want to manage
> + SCHED_DEADLINE bandwidth at the task group level. Therefore, SCHED_DEADLINE
> + uses (for now) a less sophisticated, but actually very sensible, mechanism to
> + ensure that a certain utilization cap is not overcome per each root_domain.
> +
> + Another main difference between deadline bandwidth management and RT-throttling
> + is that -deadline tasks have bandwidth on their own (while -rt ones don't!),
> + and thus we don't need an higher level throttling mechanism to enforce the
> + desired bandwidth.
> +
> +3.1 System wide settings
> +------------------------
> +
> + The system wide settings are configured under the /proc virtual file system.
> +
> + The control knob that is added to the /proc virtual file system is
> + /proc/sys/kernel/sched_dl_runtime_us. It accepts (if written) and provides (if
> + read) the new runtime for each CPU in each root_domain. The period control knob
> + is instead shared with -rt settings (/proc/sys/kernel/sched_rt_period_us). 
> +
> + The CPU bandwidth available to -deadline tasks is actually a sub-quota of
> + the -rt bandwidth. By default 95% of system bandwidth is allocate to -rt tasks;
> + among this, a 40% quota is reserved for -dl tasks. To have the actual quota a

s/among/within/

> + simple multiplication is needed: .95 * .40 = .38 (38% of system bandwidth for
> + deadline tasks).
> +
> + This means that, for a root_domain comprising M CPUs, -deadline tasks
> + can be created until the sum of their bandwidths stay below:

                   while                             stays

> +
> +   M * (sched_dl_runtime_us * rt_bw)
> +
> + It is also possible to disable this bandwidth management logic, and
> + be thus free of oversubscribing the system up to any arbitrary level.
> + This is done by writing -1 in /proc/sys/kernel/sched_dl_runtime_us or
> + in /proc/sys/kernel/sched_rt_runtime_us.
> +
> +
> +3.2 Task interface
> +------------------
> +
> + Specifying a periodic/sporadic task that executes for a given amount of
> + runtime at each instance, and that is scheduled according to the urgency of
> + its own timing constraints needs, in general, a way of declaring:
> +  - a (maximum/typical) instance execution time,
> +  - a minimum interval between consecutive instances,
> +  - a time constraint by which each instance must be completed.
> +
> + Therefore:
> +  * a new struct sched_param2, containing all the necessary fields is
> +    provided;
> +  * the new scheduling related syscalls that manipulate it, i.e.,
> +    sched_setscheduler2(), sched_setparam2() and sched_getparam2()
> +    are implemented.
> +
> +
> +3.3 Default behavior
> +---------------------
> +
> +The default value for SCHED_DEADLINE bandwidth is to have dl_runtime equal to
> +40000. Being rt_period equal to 1000000, by default, it means that -deadline

          With rt_period equal to 1000000,

> +tasks can use at most 40%, multiplied by the number of CPUs that compose the
> +root_domain, for each root_domain.
> +
> +A -deadline task cannot fork.
> +
> +4. Tasks CPU affinity
> +=====================
> +
> +-deadline tasks cannot have an affinity mask smaller that the entire
> +root_domain they are created on. However, affinities can be specified
> +through the cpuset facility (Documentation/cgroups/cpusets.txt).
> +
> +4.1 SCHED_DEADLINE and cpusets HOWTO
> +------------------------------------
> +
> +An example of a simple configuration (pin a -deadline task to CPU0)
> +follows (rt-app is used to create a -deadline task).
> +
> +mkdir /dev/cpuset
> +mount -t cgroup -o cpuset cpuset /dev/cpuset
> +cd /dev/cpuset
> +mkdir cpu0
> +echo 0 > cpu0/cpuset.cpus
> +echo 0 > cpu0/cpuset.mems
> +echo 1 > cpuset.cpu_exclusive
> +echo 0 > cpuset.sched_load_balance
> +echo 1 > cpu0/cpuset.cpu_exclusive
> +echo 1 > cpu0/cpuset.mem_exclusive
> +echo $$ > cpu0/tasks
> +rt-app -t 100000:10000:d:0 -D5 (it is now actually superfluous to specify
> +task affinity)
> +
> +5. Future plans
> +===============
> +
> +Still missing:
> +
> + - refinements to deadline inheritance, especially regarding the possibility
> +   of retaining bandwidth isolation among non-interacting tasks. This is
> +   being studied from both theoretical and practical point of views, and

                                                        points of view,

> +   hopefully we should be able to produce some demonstrative code soon;
> + - (c)group based bandwidth management, and maybe scheduling;
> + - access control for non-root users (and related security concerns to
> +   address), which is the best way to allow unprivileged use of the mechanisms
> +   and how to prevent non-root users "cheat" the system?
> +
> +As already discussed, we are planning also to merge this work with the EDF
> +throttling patches [https://lkml.org/lkml/2010/2/23/239] but we still are in
> +the preliminary phases of the merge and we really seek feedback that would
> +help us decide on the direction it should take.


-- 
~Randy

Re: [PATCH 14/14] sched: add sched_dl documentation.

[Juri Lelli]

Hi,

On 11/07/2013 05:44 PM, Randy Dunlap wrote:
> Hi,
> 
> Just a few minor edits...
> 

Thanks!

Best,

- Juri

> On 11/07/13 05:47, Juri Lelli wrote:
>> From: Dario Faggioli <raistlin@linux.it>
>>
>> Add in Documentation/scheduler/ some hints about the design
>> choices, the usage and the future possible developments of the
>> sched_dl scheduling class and of the SCHED_DEADLINE policy.
>>
>> Signed-off-by: Dario Faggioli <raistlin@linux.it>
>> Signed-off-by: Juri Lelli <juri.lelli@gmail.com>
>> ---
>>  Documentation/scheduler/sched-deadline.txt |  196 ++++++++++++++++++++++++++++
>>  kernel/sched/deadline.c                    |    3 +-
>>  2 files changed, 198 insertions(+), 1 deletion(-)
>>  create mode 100644 Documentation/scheduler/sched-deadline.txt
>>
>> diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
>> new file mode 100644
>> index 0000000..4d1ed52
>> --- /dev/null
>> +++ b/Documentation/scheduler/sched-deadline.txt
>> @@ -0,0 +1,196 @@
>> +			  Deadline Task Scheduling
>> +			  ------------------------
>> +
>> +CONTENTS
>> +========
>> +
>> +0. WARNING
>> +1. Overview
>> +2. Task scheduling
>> +2. The Interface
>> +3. Bandwidth management
>> +  3.1 System-wide settings
>> +  3.2 Task interface
>> +  3.4 Default behavior
>> +4. Tasks CPU affinity
>> +  4.1 SCHED_DEADLINE and cpusets HOWTO
>> +5. Future plans
>> +
>> +
>> +0. WARNING
>> +==========
>> +
>> + Fiddling with these settings can result in an unpredictable or even unstable
>> + system behavior. As for -rt (group) scheduling, it is assumed that root users
>> + know what they're doing.
>> +
>> +
>> +1. Overview
>> +===========
>> +
>> + The SCHED_DEADLINE policy contained inside the sched_dl scheduling class is
>> + basically an implementation of the Earliest Deadline First (EDF) scheduling
>> + algorithm, augmented with a mechanism (called Constant Bandwidth Server, CBS)
>> + that makes it possible to isolate the behavior of tasks between each other.
>> +
>> +
>> +2. Task scheduling
>> +==================
>> +
>> + The typical -deadline task is composed of a computation phase (instance)
>> + which is activated on a periodic or sporadic fashion. The expected (maximum)
>> + duration of such computation is called the task's runtime; the time interval
>> + by which each instance needs to be completed is called the task's relative
>> + deadline. The task's absolute deadline is dynamically calculated as the
>> + time instant a task (or, more properly) activates plus the relative
>> + deadline.
>> +
>> + The EDF[1] algorithm selects the task with the smallest absolute deadline as
>> + the one to be executed first, while the CBS[2,3] ensures that each task runs
>> + for at most its runtime every period, avoiding any interference between
>> + different tasks (bandwidth isolation).
>> + Thanks to this feature, also tasks that do not strictly comply with the
>> + computational model described above can effectively use the new policy.
>> + IOW, there are no limitations on what kind of task can exploit this new
>> + scheduling discipline, even if it must be said that it is particularly
>> + suited for periodic or sporadic tasks that need guarantees on their
>> + timing behavior, e.g., multimedia, streaming, control applications, etc.
>> +
>> + References:
>> +  1 - C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogram-
>> +      ming in a hard-real-time environment. Journal of the Association for
>> +      Computing Machinery, 20(1), 1973.
>> +  2 - L. Abeni , G. Buttazzo. Integrating Multimedia Applications in Hard
>> +      Real-Time Systems. Proceedings of the 19th IEEE Real-time Systems
>> +      Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf
>> +  3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab
>> +      Technical Report. http://xoomer.virgilio.it/lucabe72/pubs/tr-98-01.ps
>> +
>> +3. Bandwidth management
>> +=======================
>> +
>> + In order for the -deadline scheduling to be effective and useful, it is
>> + important to have some method to keep the allocation of the available CPU
>> + bandwidth to the tasks under control.
>> + This is usually called "admission control" and if it is not performed at all,
>> + no guarantee can be given on the actual scheduling of the -deadline tasks.
>> +
>> + Since when RT-throttling has been introduced each task group has a bandwidth
>> + associated, calculated as a certain amount of runtime over a period.
>> + Moreover, to make it possible to manipulate such bandwidth, readable/writable
>> + controls have been added to both procfs (for system wide settings) and cgroupfs
>> + (for per-group settings).
>> + Therefore, the same interface is being used for controlling the bandwidth
>> + distrubution to -deadline tasks and task groups, i.e., new controls but with
>> + similar names, equivalent meaning and with the same usage paradigm are added.
>> +
>> + However, more discussion is needed in order to figure out how we want to manage
>> + SCHED_DEADLINE bandwidth at the task group level. Therefore, SCHED_DEADLINE
>> + uses (for now) a less sophisticated, but actually very sensible, mechanism to
>> + ensure that a certain utilization cap is not overcome per each root_domain.
>> +
>> + Another main difference between deadline bandwidth management and RT-throttling
>> + is that -deadline tasks have bandwidth on their own (while -rt ones don't!),
>> + and thus we don't need an higher level throttling mechanism to enforce the
>> + desired bandwidth.
>> +
>> +3.1 System wide settings
>> +------------------------
>> +
>> + The system wide settings are configured under the /proc virtual file system.
>> +
>> + The control knob that is added to the /proc virtual file system is
>> + /proc/sys/kernel/sched_dl_runtime_us. It accepts (if written) and provides (if
>> + read) the new runtime for each CPU in each root_domain. The period control knob
>> + is instead shared with -rt settings (/proc/sys/kernel/sched_rt_period_us). 
>> +
>> + The CPU bandwidth available to -deadline tasks is actually a sub-quota of
>> + the -rt bandwidth. By default 95% of system bandwidth is allocate to -rt tasks;
>> + among this, a 40% quota is reserved for -dl tasks. To have the actual quota a
> 
> s/among/within/
> 
>> + simple multiplication is needed: .95 * .40 = .38 (38% of system bandwidth for
>> + deadline tasks).
>> +
>> + This means that, for a root_domain comprising M CPUs, -deadline tasks
>> + can be created until the sum of their bandwidths stay below:
> 
>                    while                             stays
> 
>> +
>> +   M * (sched_dl_runtime_us * rt_bw)
>> +
>> + It is also possible to disable this bandwidth management logic, and
>> + be thus free of oversubscribing the system up to any arbitrary level.
>> + This is done by writing -1 in /proc/sys/kernel/sched_dl_runtime_us or
>> + in /proc/sys/kernel/sched_rt_runtime_us.
>> +
>> +
>> +3.2 Task interface
>> +------------------
>> +
>> + Specifying a periodic/sporadic task that executes for a given amount of
>> + runtime at each instance, and that is scheduled according to the urgency of
>> + its own timing constraints needs, in general, a way of declaring:
>> +  - a (maximum/typical) instance execution time,
>> +  - a minimum interval between consecutive instances,
>> +  - a time constraint by which each instance must be completed.
>> +
>> + Therefore:
>> +  * a new struct sched_param2, containing all the necessary fields is
>> +    provided;
>> +  * the new scheduling related syscalls that manipulate it, i.e.,
>> +    sched_setscheduler2(), sched_setparam2() and sched_getparam2()
>> +    are implemented.
>> +
>> +
>> +3.3 Default behavior
>> +---------------------
>> +
>> +The default value for SCHED_DEADLINE bandwidth is to have dl_runtime equal to
>> +40000. Being rt_period equal to 1000000, by default, it means that -deadline
> 
>           With rt_period equal to 1000000,
> 
>> +tasks can use at most 40%, multiplied by the number of CPUs that compose the
>> +root_domain, for each root_domain.
>> +
>> +A -deadline task cannot fork.
>> +
>> +4. Tasks CPU affinity
>> +=====================
>> +
>> +-deadline tasks cannot have an affinity mask smaller that the entire
>> +root_domain they are created on. However, affinities can be specified
>> +through the cpuset facility (Documentation/cgroups/cpusets.txt).
>> +
>> +4.1 SCHED_DEADLINE and cpusets HOWTO
>> +------------------------------------
>> +
>> +An example of a simple configuration (pin a -deadline task to CPU0)
>> +follows (rt-app is used to create a -deadline task).
>> +
>> +mkdir /dev/cpuset
>> +mount -t cgroup -o cpuset cpuset /dev/cpuset
>> +cd /dev/cpuset
>> +mkdir cpu0
>> +echo 0 > cpu0/cpuset.cpus
>> +echo 0 > cpu0/cpuset.mems
>> +echo 1 > cpuset.cpu_exclusive
>> +echo 0 > cpuset.sched_load_balance
>> +echo 1 > cpu0/cpuset.cpu_exclusive
>> +echo 1 > cpu0/cpuset.mem_exclusive
>> +echo $$ > cpu0/tasks
>> +rt-app -t 100000:10000:d:0 -D5 (it is now actually superfluous to specify
>> +task affinity)
>> +
>> +5. Future plans
>> +===============
>> +
>> +Still missing:
>> +
>> + - refinements to deadline inheritance, especially regarding the possibility
>> +   of retaining bandwidth isolation among non-interacting tasks. This is
>> +   being studied from both theoretical and practical point of views, and
> 
>                                                         points of view,
> 
>> +   hopefully we should be able to produce some demonstrative code soon;
>> + - (c)group based bandwidth management, and maybe scheduling;
>> + - access control for non-root users (and related security concerns to
>> +   address), which is the best way to allow unprivileged use of the mechanisms
>> +   and how to prevent non-root users "cheat" the system?
>> +
>> +As already discussed, we are planning also to merge this work with the EDF
>> +throttling patches [https://lkml.org/lkml/2010/2/23/239] but we still are in
>> +the preliminary phases of the merge and we really seek feedback that would
>> +help us decide on the direction it should take.
> 
> 

[PATCH 00/14] sched: SCHED_DEADLINE v8

[Juri Lelli]

Hello everyone,

here we go with a new version of the SCHED_DEADLINE patchset (v8). I know that
it has been a while since I released last version [1], but I thought not to
spam the mailing list with simple updates. Well... this IS basically an update
to 3.12-rc5, but it comes right before the next Kernel Summit and Real Time
Linux Workshop and, since I'll be present at both events, it is probably time
to fire-up the discussion again.

Moreover, interesting news:

 - a better mechanism for coordinating mutually exclusive access to critical
   sections is coming soon (we wrote a paper about it for RTLWS15 [2]);
 - the patchset is now available in the 3.4 and 3.10 Yocto kernels [3] (thanks
   a lot for this to Bruce Ashfield and Insop Song); even though it is hard to
   say how many new users we got with this, we can say that having
   SCHED_DEADLINE in Yocto provides availabily to OSVs like Wind River and
   others;
 - a european project has started (JUNIPER [4]) for which we will provide
   kernel level support based on this patchset (and we will soon have a real
   use case for it! yayyy! :)).

The development is taking place at:
   https://github.com/jlelli/sched-deadline

branch: sched-dl-V8 (this patchset on top of tip/master).

Check the repositories frequently if you're interested, and feel free to
e-mail me for any issue you run into.

Test applications:
  https://github.com/gbagnoli/rt-app 
  https://github.com/jlelli/schedtool-dl

Development mailing list: linux-dl; you can subscribe from here:
http://feanor.sssup.it/mailman/listinfo/linux-dl
or via e-mail (send a message to linux-dl-request@retis.sssup.it with
just the word `help' as subject or in the body to receive info).

The code was being jointly developed by ReTiS Lab (http://retis.sssup.it)
and Evidence S.r.l (http://www.evidence.eu.com) in the context of the ACTORS
EU-funded project (http://www.actors-project.eu) and the S(o)OS EU-funded
project (http://www.soos-project.eu/). Development is now supported by the
JUNIPER EU-funded project [4].

As usual, any kind of feedback is welcome and appreciated.

Thanks in advice and regards,

 - Juri

[1] http://lwn.net/Articles/376502, http://lwn.net/Articles/353797,
    http://lwn.net/Articles/412410, http://lwn.net/Articles/490944,
    http://lwn.net/Articles/498472, http://lwn.net/Articles/521091,
    http://lwn.net/Articles/537388

[2] https://www.osadl.org/?id=1743

[3] https://www.yoctoproject.org/

[4] http://www.juniper-project.org/page/overview

Dario Faggioli (9):
  sched: add sched_class->task_dead.
  sched: add extended scheduling interface.
  sched: SCHED_DEADLINE structures & implementation.
  sched: SCHED_DEADLINE avg_update accounting.
  sched: add schedstats for -deadline tasks.
  sched: add latency tracing for -deadline tasks.
  sched: drafted deadline inheritance logic.
  sched: add bandwidth management for sched_dl.
  sched: add sched_dl documentation.

Harald Gustafsson (1):
  sched: add period support for -deadline tasks.

Juri Lelli (3):
  sched: SCHED_DEADLINE SMP-related data structures & logic.
  sched: make dl_bw a sub-quota of rt_bw
  sched: speed up -dl pushes with a push-heap.

Peter Zijlstra (1):
  rtmutex: turn the plist into an rb-tree.

 Documentation/scheduler/sched-deadline.txt |  196 ++++
 arch/arm/include/asm/unistd.h              |    2 +-
 arch/arm/include/uapi/asm/unistd.h         |    3 +
 arch/arm/kernel/calls.S                    |    3 +
 arch/x86/syscalls/syscall_32.tbl           |    3 +
 arch/x86/syscalls/syscall_64.tbl           |    3 +
 include/linux/init_task.h                  |   10 +
 include/linux/rtmutex.h                    |   18 +-
 include/linux/sched.h                      |  122 +-
 include/linux/sched/deadline.h             |   24 +
 include/linux/sched/rt.h                   |    3 +-
 include/linux/sched/sysctl.h               |   11 +
 include/linux/syscalls.h                   |    7 +
 include/uapi/linux/sched.h                 |    1 +
 kernel/fork.c                              |    8 +-
 kernel/futex.c                             |    2 +
 kernel/hrtimer.c                           |    3 +-
 kernel/rtmutex-debug.c                     |    8 +-
 kernel/rtmutex.c                           |  164 ++-
 kernel/rtmutex_common.h                    |   22 +-
 kernel/sched/Makefile                      |    4 +-
 kernel/sched/core.c                        |  660 ++++++++++-
 kernel/sched/cpudeadline.c                 |  216 ++++
 kernel/sched/cpudeadline.h                 |   33 +
 kernel/sched/deadline.c                    | 1658 ++++++++++++++++++++++++++++
 kernel/sched/debug.c                       |   46 +
 kernel/sched/rt.c                          |    2 +-
 kernel/sched/sched.h                       |  150 +++
 kernel/sched/stop_task.c                   |    2 +-
 kernel/sysctl.c                            |    7 +
 kernel/trace/trace_sched_wakeup.c          |   45 +-
 kernel/trace/trace_selftest.c              |   28 +-
 32 files changed, 3343 insertions(+), 121 deletions(-)
 create mode 100644 Documentation/scheduler/sched-deadline.txt
 create mode 100644 include/linux/sched/deadline.h
 create mode 100644 kernel/sched/cpudeadline.c
 create mode 100644 kernel/sched/cpudeadline.h
 create mode 100644 kernel/sched/deadline.c

-- 
1.7.9.5

[PATCH 14/14] sched: add sched_dl documentation.

[Juri Lelli]

From: Dario Faggioli <raistlin@linux.it>

Add in Documentation/scheduler/ some hints about the design
choices, the usage and the future possible developments of the
sched_dl scheduling class and of the SCHED_DEADLINE policy.

Signed-off-by: Dario Faggioli <raistlin@linux.it>
Signed-off-by: Juri Lelli <juri.lelli@gmail.com>
---
 Documentation/scheduler/sched-deadline.txt |  196 ++++++++++++++++++++++++++++
 kernel/sched/deadline.c                    |    3 +-
 2 files changed, 198 insertions(+), 1 deletion(-)
 create mode 100644 Documentation/scheduler/sched-deadline.txt

diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
new file mode 100644
index 0000000..4d1ed52
--- /dev/null
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -0,0 +1,196 @@
+			  Deadline Task Scheduling
+			  ------------------------
+
+CONTENTS
+========
+
+0. WARNING
+1. Overview
+2. Task scheduling
+2. The Interface
+3. Bandwidth management
+  3.1 System-wide settings
+  3.2 Task interface
+  3.4 Default behavior
+4. Tasks CPU affinity
+  4.1 SCHED_DEADLINE and cpusets HOWTO
+5. Future plans
+
+
+0. WARNING
+==========
+
+ Fiddling with these settings can result in an unpredictable or even unstable
+ system behavior. As for -rt (group) scheduling, it is assumed that root users
+ know what they're doing.
+
+
+1. Overview
+===========
+
+ The SCHED_DEADLINE policy contained inside the sched_dl scheduling class is
+ basically an implementation of the Earliest Deadline First (EDF) scheduling
+ algorithm, augmented with a mechanism (called Constant Bandwidth Server, CBS)
+ that makes it possible to isolate the behavior of tasks between each other.
+
+
+2. Task scheduling
+==================
+
+ The typical -deadline task is composed of a computation phase (instance)
+ which is activated on a periodic or sporadic fashion. The expected (maximum)
+ duration of such computation is called the task's runtime; the time interval
+ by which each instance needs to be completed is called the task's relative
+ deadline. The task's absolute deadline is dynamically calculated as the
+ time instant a task (or, more properly) activates plus the relative
+ deadline.
+
+ The EDF[1] algorithm selects the task with the smallest absolute deadline as
+ the one to be executed first, while the CBS[2,3] ensures that each task runs
+ for at most its runtime every period, avoiding any interference between
+ different tasks (bandwidth isolation).
+ Thanks to this feature, also tasks that do not strictly comply with the
+ computational model described above can effectively use the new policy.
+ IOW, there are no limitations on what kind of task can exploit this new
+ scheduling discipline, even if it must be said that it is particularly
+ suited for periodic or sporadic tasks that need guarantees on their
+ timing behavior, e.g., multimedia, streaming, control applications, etc.
+
+ References:
+  1 - C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogram-
+      ming in a hard-real-time environment. Journal of the Association for
+      Computing Machinery, 20(1), 1973.
+  2 - L. Abeni , G. Buttazzo. Integrating Multimedia Applications in Hard
+      Real-Time Systems. Proceedings of the 19th IEEE Real-time Systems
+      Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf
+  3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab
+      Technical Report. http://xoomer.virgilio.it/lucabe72/pubs/tr-98-01.ps
+
+3. Bandwidth management
+=======================
+
+ In order for the -deadline scheduling to be effective and useful, it is
+ important to have some method to keep the allocation of the available CPU
+ bandwidth to the tasks under control.
+ This is usually called "admission control" and if it is not performed at all,
+ no guarantee can be given on the actual scheduling of the -deadline tasks.
+
+ Since when RT-throttling has been introduced each task group has a bandwidth
+ associated, calculated as a certain amount of runtime over a period.
+ Moreover, to make it possible to manipulate such bandwidth, readable/writable
+ controls have been added to both procfs (for system wide settings) and cgroupfs
+ (for per-group settings).
+ Therefore, the same interface is being used for controlling the bandwidth
+ distrubution to -deadline tasks and task groups, i.e., new controls but with
+ similar names, equivalent meaning and with the same usage paradigm are added.
+
+ However, more discussion is needed in order to figure out how we want to manage
+ SCHED_DEADLINE bandwidth at the task group level. Therefore, SCHED_DEADLINE
+ uses (for now) a less sophisticated, but actually very sensible, mechanism to
+ ensure that a certain utilization cap is not overcome per each root_domain.
+
+ Another main difference between deadline bandwidth management and RT-throttling
+ is that -deadline tasks have bandwidth on their own (while -rt ones don't!),
+ and thus we don't need an higher level throttling mechanism to enforce the
+ desired bandwidth.
+
+3.1 System wide settings
+------------------------
+
+ The system wide settings are configured under the /proc virtual file system.
+
+ The control knob that is added to the /proc virtual file system is
+ /proc/sys/kernel/sched_dl_runtime_us. It accepts (if written) and provides (if
+ read) the new runtime for each CPU in each root_domain. The period control knob
+ is instead shared with -rt settings (/proc/sys/kernel/sched_rt_period_us). 
+
+ The CPU bandwidth available to -deadline tasks is actually a sub-quota of
+ the -rt bandwidth. By default 95% of system bandwidth is allocate to -rt tasks;
+ among this, a 40% quota is reserved for -dl tasks. To have the actual quota a
+ simple multiplication is needed: .95 * .40 = .38 (38% of system bandwidth for
+ deadline tasks).
+
+ This means that, for a root_domain comprising M CPUs, -deadline tasks
+ can be created until the sum of their bandwidths stay below:
+
+   M * (sched_dl_runtime_us * rt_bw)
+
+ It is also possible to disable this bandwidth management logic, and
+ be thus free of oversubscribing the system up to any arbitrary level.
+ This is done by writing -1 in /proc/sys/kernel/sched_dl_runtime_us or
+ in /proc/sys/kernel/sched_rt_runtime_us.
+
+
+3.2 Task interface
+------------------
+
+ Specifying a periodic/sporadic task that executes for a given amount of
+ runtime at each instance, and that is scheduled according to the urgency of
+ its own timing constraints needs, in general, a way of declaring:
+  - a (maximum/typical) instance execution time,
+  - a minimum interval between consecutive instances,
+  - a time constraint by which each instance must be completed.
+
+ Therefore:
+  * a new struct sched_param2, containing all the necessary fields is
+    provided;
+  * the new scheduling related syscalls that manipulate it, i.e.,
+    sched_setscheduler2(), sched_setparam2() and sched_getparam2()
+    are implemented.
+
+
+3.3 Default behavior
+---------------------
+
+The default value for SCHED_DEADLINE bandwidth is to have dl_runtime equal to
+40000. Being rt_period equal to 1000000, by default, it means that -deadline
+tasks can use at most 40%, multiplied by the number of CPUs that compose the
+root_domain, for each root_domain.
+
+A -deadline task cannot fork.
+
+4. Tasks CPU affinity
+=====================
+
+-deadline tasks cannot have an affinity mask smaller that the entire
+root_domain they are created on. However, affinities can be specified
+through the cpuset facility (Documentation/cgroups/cpusets.txt).
+
+4.1 SCHED_DEADLINE and cpusets HOWTO
+------------------------------------
+
+An example of a simple configuration (pin a -deadline task to CPU0)
+follows (rt-app is used to create a -deadline task).
+
+mkdir /dev/cpuset
+mount -t cgroup -o cpuset cpuset /dev/cpuset
+cd /dev/cpuset
+mkdir cpu0
+echo 0 > cpu0/cpuset.cpus
+echo 0 > cpu0/cpuset.mems
+echo 1 > cpuset.cpu_exclusive
+echo 0 > cpuset.sched_load_balance
+echo 1 > cpu0/cpuset.cpu_exclusive
+echo 1 > cpu0/cpuset.mem_exclusive
+echo $$ > cpu0/tasks
+rt-app -t 100000:10000:d:0 -D5 (it is now actually superfluous to specify
+task affinity)
+
+5. Future plans
+===============
+
+Still missing:
+
+ - refinements to deadline inheritance, especially regarding the possibility
+   of retaining bandwidth isolation among non-interacting tasks. This is
+   being studied from both theoretical and practical point of views, and
+   hopefully we should be able to produce some demonstrative code soon;
+ - (c)group based bandwidth management, and maybe scheduling;
+ - access control for non-root users (and related security concerns to
+   address), which is the best way to allow unprivileged use of the mechanisms
+   and how to prevent non-root users "cheat" the system?
+
+As already discussed, we are planning also to merge this work with the EDF
+throttling patches [https://lkml.org/lkml/2010/2/23/239] but we still are in
+the preliminary phases of the merge and we really seek feedback that would
+help us decide on the direction it should take.
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 1499381..00b550b 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -348,7 +348,8 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se,
  * disrupting the schedulability of the system. Otherwise, we should
  * refill the runtime and set the deadline a period in the future,
  * because keeping the current (absolute) deadline of the task would
- * result in breaking guarantees promised to other tasks.
+ * result in breaking guarantees promised to other tasks (refer to
+ * Documentation/scheduler/sched-deadline.txt for more informations).
  *
  * This function returns true if:
  *
-- 
1.7.9.5

[PATCH 00/14] sched: SCHED_DEADLINE v7

[Juri Lelli]

Hello everyone,

several changes, some bugfixes and a major testing effort bring me to
release a new version of the SCHED_DEADLINE patchset (v7). In addition,
given the fact that the project has been around for quite some time with
always a positive feedback from the community and since we have reached
a stable and tested set of functionalities, I think it is time to remove
the RFC tag. However, I consider this as another intermediate release as
I would like even more testing from the community itself and I'm also
working to ship a motivating use case with next releases. I had many
interactions with users, especially from industry, after past releases.
Some of them seem to confirm their interest proposing enhancements and
modifications (e.g., http://bit.ly/XVQWrb); some others are willing to
collaborate directly. This makes me confident that such a use case is
on the way. 

If you missed the whole story[1], this patchset introduces a new deadline
based real-time task scheduling policy --called SCHED_DEADLINE-- with
bandwidth isolation (aka "resource reservation") capabilities. It supports
global/clustered multiprocessor scheduling through dynamic task migrations.

>From the previous releases[1]:

  - rebase on top of 3.8-rc7;
  - comments and fixes coming from the reviews we got have been considered
    and applied;
  - u128 support has been removed and internal math has been restricted
    to microseconds resolution (to avoid overflows);
  - dl.c, cpudl.{c,h} renamed as deadline.c, cpudeadline.{c,h};
  - documentation fixed and extended (how to pin -dl tasks to CPUs via
    cpusets example added).

The development is taking place at:
   https://github.com/jlelli/sched-deadline

Main branches:

 - sched-dl-V7: this patchset on top of tip/master.
 - mainline-dl: tracking tip/master (raw commits);

Check the repositories frequently if you're interested, and feel free to
e-mail me for any issue you run into.

Test applications:
  https://github.com/gbagnoli/rt-app 
  https://github.com/jlelli/schedtool-dl

Development mailing list: linux-dl; you can subscribe from here:
http://feanor.sssup.it/mailman/listinfo/linux-dl
or via e-mail (send a message to linux-dl-request@retis.sssup.it with
just the word `help' as subject or in the body to receive info).

The code was being jointly developed by ReTiS Lab (http://retis.sssup.it)
and Evidence S.r.l (http://www.evidence.eu.com) in the context of the ACTORS
EU-funded project (http://www.actors-project.eu). It is now supported by
the S(o)OS EU-funded project (http://www.soos-project.eu/).
It has also some users, both in academic and applied research. We got
positive feedbacks from Ericsson, Wind River, Porto (ISEP), Trento,
Lund and Malardalen universities.

As usual, any kind of feedback is welcome and appreciated.

Thanks in advice and regards,

 - Juri

[1] http://lwn.net/Articles/376502, http://lwn.net/Articles/353797,
    http://lwn.net/Articles/412410, http://lwn.net/Articles/490944,
    http://lwn.net/Articles/498472, http://lwn.net/Articles/521091

Dario Faggioli (9):
  sched: add sched_class->task_dead.
  sched: add extended scheduling interface.
  sched: SCHED_DEADLINE structures & implementation.
  sched: SCHED_DEADLINE avg_update accounting.
  sched: add schedstats for -deadline tasks.
  sched: add latency tracing for -deadline tasks.
  sched: drafted deadline inheritance logic.
  sched: add bandwidth management for sched_dl.
  sched: add sched_dl documentation.

Harald Gustafsson (1):
  sched: add period support for -deadline tasks.

Juri Lelli (3):
  sched: SCHED_DEADLINE SMP-related data structures & logic.
  sched: make dl_bw a sub-quota of rt_bw
  sched: speed up -dl pushes with a push-heap.

Peter Zijlstra (1):
  rtmutex: turn the plist into an rb-tree.

 Documentation/scheduler/sched-deadline.txt |  195 ++++
 arch/arm/include/asm/unistd.h              |    2 +-
 arch/arm/include/uapi/asm/unistd.h         |    3 +
 arch/arm/kernel/calls.S                    |    3 +
 arch/x86/syscalls/syscall_32.tbl           |    3 +
 arch/x86/syscalls/syscall_64.tbl           |    3 +
 include/linux/init_task.h                  |   10 +
 include/linux/rtmutex.h                    |   18 +-
 include/linux/sched.h                      |  152 ++-
 include/linux/syscalls.h                   |    7 +
 include/uapi/linux/sched.h                 |    1 +
 kernel/fork.c                              |    8 +-
 kernel/futex.c                             |    2 +
 kernel/hrtimer.c                           |    2 +-
 kernel/rtmutex-debug.c                     |    8 +-
 kernel/rtmutex.c                           |  163 ++-
 kernel/rtmutex_common.h                    |   22 +-
 kernel/sched/Makefile                      |    4 +-
 kernel/sched/core.c                        |  657 ++++++++++-
 kernel/sched/cpudeadline.c                 |  208 ++++
 kernel/sched/cpudeadline.h                 |   33 +
 kernel/sched/deadline.c                    | 1658 ++++++++++++++++++++++++++++
 kernel/sched/debug.c                       |   46 +
 kernel/sched/rt.c                          |    2 +-
 kernel/sched/sched.h                       |  146 +++
 kernel/sched/stop_task.c                   |    2 +-
 kernel/sysctl.c                            |    7 +
 kernel/trace/trace_sched_wakeup.c          |   44 +-
 kernel/trace/trace_selftest.c              |   28 +-
 29 files changed, 3317 insertions(+), 120 deletions(-)
 create mode 100644 Documentation/scheduler/sched-deadline.txt
 create mode 100644 kernel/sched/cpudeadline.c
 create mode 100644 kernel/sched/cpudeadline.h
 create mode 100644 kernel/sched/deadline.c

-- 
1.7.9.5

[PATCH 14/14] sched: add sched_dl documentation.

[Juri Lelli]

From: Dario Faggioli <raistlin@linux.it>

Add in Documentation/scheduler/ some hints about the design
choices, the usage and the future possible developments of the
sched_dl scheduling class and of the SCHED_DEADLINE policy.

Signed-off-by: Dario Faggioli <raistlin@linux.it>
Signed-off-by: Juri Lelli <juri.lelli@gmail.com>
---
 Documentation/scheduler/sched-deadline.txt |  195 ++++++++++++++++++++++++++++
 kernel/sched/deadline.c                    |    3 +-
 2 files changed, 197 insertions(+), 1 deletion(-)
 create mode 100644 Documentation/scheduler/sched-deadline.txt

diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
new file mode 100644
index 0000000..9ba02631
--- /dev/null
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -0,0 +1,195 @@
+			  Deadline Task Scheduling
+			  ------------------------
+
+CONTENTS
+========
+
+0. WARNING
+1. Overview
+2. Task scheduling
+2. The Interface
+3. Bandwidth management
+  3.1 System-wide settings
+  3.2 Task interface
+  3.4 Default behavior
+4. Tasks CPU affinity
+  4.1 SCHED_DEADLINE and cpusets HOWTO
+5. Future plans
+
+
+0. WARNING
+==========
+
+ Fiddling with these settings can result in an unpredictable or even unstable
+ system behavior. As for -rt (group) scheduling, it is assumed that root users
+ know what they're doing.
+
+
+1. Overview
+===========
+
+ The SCHED_DEADLINE policy contained inside the sched_dl scheduling class is
+ basically an implementation of the Earliest Deadline First (EDF) scheduling
+ algorithm, augmented with a mechanism (called Constant Bandwidth Server, CBS)
+ that makes it possible to isolate the behavior of tasks between each other.
+
+
+2. Task scheduling
+==================
+
+ The typical -deadline task is composed of a computation phase (instance)
+ which is activated on a periodic or sporadic fashion. The expected (maximum)
+ duration of such computation is called the task's runtime; the time interval
+ by which each instance needs to be completed is called the task's relative
+ deadline. The task's absolute deadline is dynamically calculated as the
+ time instant a task (or, more properly) activates plus the relative
+ deadline.
+
+ The EDF[1] algorithm selects the task with the smallest absolute deadline as
+ the one to be executed first, while the CBS[2,3] ensures that each task runs
+ for at most its runtime every period, avoiding any interference between
+ different tasks (bandwidth isolation).
+ Thanks to this feature, also tasks that do not strictly comply with the
+ computational model described above can effectively use the new policy.
+ IOW, there are no limitations on what kind of task can exploit this new
+ scheduling discipline, even if it must be said that it is particularly
+ suited for periodic or sporadic tasks that need guarantees on their
+ timing behavior, e.g., multimedia, streaming, control applications, etc.
+
+ References:
+  1 - C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogram-
+      ming in a hard-real-time environment. Journal of the Association for
+      Computing Machinery, 20(1), 1973.
+  2 - L. Abeni , G. Buttazzo. Integrating Multimedia Applications in Hard
+      Real-Time Systems. Proceedings of the 19th IEEE Real-time Systems
+      Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf
+  3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab
+      Technical Report. http://xoomer.virgilio.it/lucabe72/pubs/tr-98-01.ps
+
+3. Bandwidth management
+=======================
+
+ In order for the -deadline scheduling to be effective and useful, it is
+ important to have some method to keep the allocation of the available CPU
+ bandwidth to the tasks under control.
+ This is usually called "admission control" and if it is not performed at all,
+ no guarantee can be given on the actual scheduling of the -deadline tasks.
+
+ Since when RT-throttling has been introduced each task group has a bandwidth
+ associated, calculated as a certain amount of runtime over a period.
+ Moreover, to make it possible to manipulate such bandwidth, readable/writable
+ controls have been added to both procfs (for system wide settings) and cgroupfs
+ (for per-group settings).
+ Therefore, the same interface is being used for controlling the bandwidth
+ distrubution to -deadline tasks and task groups, i.e., new controls but with
+ similar names, equivalent meaning and with the same usage paradigm are added.
+
+ However, more discussion is needed in order to figure out how we want to manage
+ SCHED_DEADLINE bandwidth at the task group level. Therefore, SCHED_DEADLINE
+ uses (for now) a less sophisticated, but actually very sensible, mechanism to
+ ensure that a certain utilization cap is not overcome per each root_domain.
+
+ Another main difference between deadline bandwidth management and RT-throttling
+ is that -deadline tasks have bandwidth on their own (while -rt ones don't!),
+ and thus we don't need an higher level throttling mechanism to enforce the
+ desired bandwidth.
+
+3.1 System wide settings
+------------------------
+
+ The system wide settings are configured under the /proc virtual file system.
+
+ The control knob that is added to the /proc virtual file system is
+ /proc/sys/kernel/sched_dl_runtime_us. It accepts (if written) and provides (if
+ read) the new runtime for each CPU in each root_domain. The period control knob
+ is instead shared with -rt settings (/proc/sys/kernel/sched_rt_period_us). 
+
+ The CPU bandwidth available to -deadline tasks is actually a sub-quota of
+ the -rt bandwidth. By default 95% of system bandwidth is allocate to -rt tasks;
+ among this, a 40% quota is reserved for -dl tasks. To have the actual quota a
+ simple multiplication is needed: .95 * .40 = .38 (38% of system bandwidth for
+ deadline tasks).
+
+ This means that, for a root_domain comprising M CPUs, -deadline tasks
+ can be created until the sum of their bandwidths stay below:
+
+   M * (sched_dl_runtime_us / sched_rt_period_us)
+
+ It is also possible to disable this bandwidth management logic, and
+ be thus free of oversubscribing the system up to any arbitrary level.
+ This is done by writing -1 in /proc/sys/kernel/sched_dl_runtime_us.
+
+
+3.2 Task interface
+------------------
+
+ Specifying a periodic/sporadic task that executes for a given amount of
+ runtime at each instance, and that is scheduled according to the urgency of
+ its own timing constraints needs, in general, a way of declaring:
+  - a (maximum/typical) instance execution time,
+  - a minimum interval between consecutive instances,
+  - a time constraint by which each instance must be completed.
+
+ Therefore:
+  * a new struct sched_param2, containing all the necessary fields is
+    provided;
+  * the new scheduling related syscalls that manipulate it, i.e.,
+    sched_setscheduler2(), sched_setparam2() and sched_getparam2()
+    are implemented.
+
+
+3.3 Default behavior
+---------------------
+
+The default value for SCHED_DEADLINE bandwidth is to have dl_runtime equal to
+40000. Being rt_period equal to 1000000, by default, it means that -deadline
+tasks can use at most 40%, multiplied by the number of CPUs that compose the
+root_domain, for each root_domain.
+
+A -deadline task cannot fork.
+
+4. Tasks CPU affinity
+=====================
+
+-deadline tasks cannot have an affinity mask smaller that the entire
+root_domain they are created on. However, affinities can be specified
+through the cpuset facility (Documentation/cgroups/cpusets.txt).
+
+4.1 SCHED_DEADLINE and cpusets HOWTO
+------------------------------------
+
+An example of a simple configuration (pin a -deadline task to CPU0)
+follows (rt-app is used to create a -deadline task).
+
+mkdir /dev/cpuset
+mount -t cgroup -o cpuset cpuset /dev/cpuset
+cd /dev/cpuset
+mkdir cpu0
+echo 0 > cpu0/cpuset.cpus
+echo 0 > cpu0/cpuset.mems
+echo 1 > cpuset.cpu_exclusive
+echo 0 > cpuset.sched_load_balance
+echo 1 > cpu0/cpuset.cpu_exclusive
+echo 1 > cpu0/cpuset.mem_exclusive
+echo $$ > cpu0/tasks
+rt-app -t 100000:10000:d:0 -D5 (it is now actually superfluous to specify
+task affinity)
+
+5. Future plans
+===============
+
+Still missing:
+
+ - refinements to deadline inheritance, especially regarding the possibility
+   of retaining bandwidth isolation among non-interacting tasks. This is
+   being studied from both theoretical and practical point of views, and
+   hopefully we should be able to produce some demonstrative code soon;
+ - (c)group based bandwidth management, and maybe scheduling;
+ - access control for non-root users (and related security concerns to
+   address), which is the best way to allow unprivileged use of the mechanisms
+   and how to prevent non-root users "cheat" the system?
+
+As already discussed, we are planning also to merge this work with the EDF
+throttling patches [https://lkml.org/lkml/2010/2/23/239] but we still are in
+the preliminary phases of the merge and we really seek feedback that would
+help us decide on the direction it should take.
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 0ece746..e7a1d34 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -348,7 +348,8 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se,
  * disrupting the schedulability of the system. Otherwise, we should
  * refill the runtime and set the deadline a period in the future,
  * because keeping the current (absolute) deadline of the task would
- * result in breaking guarantees promised to other tasks.
+ * result in breaking guarantees promised to other tasks (refer to
+ * Documentation/scheduler/sched-deadline.txt for more informations).
  *
  * This function returns true if:
  *
-- 
1.7.9.5