lkml.org 
[lkml]   [2016]   [Oct]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Subject[RFC v3 0/6] CPU reclaiming for SCHED_DEADLINE
Date
Hi all,

this patchset implements CPU reclaiming (using the GRUB algorithm[1])
for SCHED_DEADLINE: basically, this feature allows SCHED_DEADLINE tasks
to consume more than their reserved runtime, up to a maximum fraction
of the CPU time (so that other tasks are left some spare CPU time to
execute), if this does not break the guarantees of other SCHED_DEADLINE
tasks.
The patchset applies on top of tip/master.


The implemented CPU reclaiming algorithm is based on tracking the
utilization U_act of active tasks (first 2 patches), and modifying the
runtime accounting rule (see patch 0004). The original GRUB algorithm is
modified as described in [2] to support multiple CPUs (the original
algorithm only considered one single CPU, this one tracks U_act per
runqueue) and to leave an "unreclaimable" fraction of CPU time to non
SCHED_DEADLINE tasks (see patch 0005: the original algorithm can consume
100% of the CPU time, starving all the other tasks).
Patch 0003 uses the newly introduced "inactive timer" (introduced in
patch 0002) to fix dl_overflow() and __setparam_dl().
Patch 0006 allows to enable CPU reclaiming only on selected tasks.


Changes since v2:
in general, I tried to address all the comments I received, and to add
some more comments in "critical" parts of the code. In particular, I:
- Updated to latest tip/master. This required some changes (for example,
using "struct rq_flags" instead of "unsigned long" for task_rq_lock())
- Merged patches 0001 and 0002, as suggested by Juri
- Added some comments about GRUB in the changelog of the patch adding
GRUB accounting
- Exchanged the order of two patches ("Make GRUB a task's flag" and
"Do not reclaim the whole CPU bandwidth"), as suggested by Juri
- Removed unused code ("if (task_on_rq_queued(p))" in task_dead_dl(),
noticed by Peter) from patch 0001
- Properly consider the migrations of queued dl tasks when updating
the active utilization. This should address Peter's concern from
http://lkml.iu.edu/hypermail/linux/kernel/1604.0/02612.html
- Simplified the code for setting up the inactive timer, as suggested
by Peter: http://lkml.iu.edu/hypermail/linux/kernel/1604.0/02620.html
- Use hrtimer_is_queued() instead of "(hrtimer_active() &&
!hrtimer_callback_running())", as pointed out by Peter:
http://lkml.iu.edu/hypermail/linux/kernel/1604.0/02805.html
- Fix select_task_rq_dl() (using "task_cpu(p) != cpu" instead
of "rq != cpu_rq(cpu)"), as pointed out by Peter:
http://lkml.iu.edu/hypermail/linux/kernel/1604.0/02822.html
I also changed the logic used in select_task_rq_dl()
(that now does not increase the active utilization in the selected
runqueue)
- Because of the changes in the code, I am not sure if the race condition
pointed out by Peter can still happen. I tried to trigger it in many ways,
but I failed... If it turns out that the race is still possible, I'll fix
it in the next round of patches, by introducing a new "is_contending" field
(protected by pi_mutex) in the dl scheduling entity.


[1] Lipari, G., & Baruah, S. (2000). Greedy reclamation of unused bandwidth in constant-bandwidth servers. In Real-Time Systems, 2000. Euromicro RTS 2000. 12th Euromicro Conference on (pp. 193-200). IEEE.
[2] Abeni, L., Lelli, J., Scordino, C., & Palopoli, L. (2014, October). Greedy CPU reclaiming for SCHED DEADLINE. In Proceedings of the Real-Time Linux Workshop (RTLWS), Dusseldorf, Germany.



Luca Abeni (6):
Track the active utilisation
Improve the tracking of active utilisation
Fix the update of the total -deadline utilization
GRUB accounting
Do not reclaim the whole CPU bandwidth
Make GRUB a task's flag

include/linux/sched.h | 1 +
include/uapi/linux/sched.h | 1 +
kernel/sched/core.c | 44 ++++-----
kernel/sched/deadline.c | 220 ++++++++++++++++++++++++++++++++++++++++-----
kernel/sched/sched.h | 13 +++
5 files changed, 234 insertions(+), 45 deletions(-)

--
2.7.4

\
 
 \ /
  Last update: 2016-10-24 16:07    [W:0.200 / U:0.700 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site