Messages in this thread | | | From | luca abeni <> | Subject | [PATCH 00/10] CPU reclaiming for SCHED_DEADLINE | Date | Thu, 18 May 2017 22:13:27 +0200 |
| |
From: Luca Abeni <luca.abeni@santannapisa.it>
Hi all,
here is the next iteration of my patchset implementing CPU reclaiming (using the GRUB algorithm[1]) for SCHED_DEADLINE (since I think the patchset is now mature enough, I removed the "RFC" keyword from the emails subjects). 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 patches 0004, 0008 and 0009). The original GRUB algorithm is modified as described in [2,3] 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. Patches 0007, 0008 and 0009 fix an issue found by Daniel in a previous submission, by basing the GRUB reclaiming algorithm on the inactive utilization U_inact as shown in [3]. Here, U_inact is computed as the difference between the "rq utilization" (see patch 0007) and U_act. Patch 0010 adds some documentation contributed by Claudio.
The changes respect to v5 are mostly cosmetic and about comments or documentation: - I rearranged some code to avoid eccessive indentation, as requested by Peter (http://lkml.iu.edu/hypermail/linux/kernel/1703.3/00291.html) - I modified dl_non_contending() to avoid doubts about use-after-free (http://lkml.iu.edu/hypermail/linux/kernel/1703.3/00291.html) - I added a comment to migrate_task_rq_dl() explaining the locking (http://lkml.iu.edu/hypermail/linux/kernel/1703.3/00291.html) - I added some braces to be compliant with the coding rules - I renamed some functions and structure fields according to the feedback I received - I added a big comment to document the GRUB states transition - I changed grub_reclaim() (and the comments to that function) to make it more understandable - I added some documentation by Claudio
Finally, I updated the patches to apply on top of tip/master.
[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 [3] Abeni, L., Lipari, G., Parri, A., & Sun, Y. (2016, April). Multicore CPU reclaiming: parallel or sequential?. In Proceedings of the 31st Annual ACM Symposium on Applied Computing (pp. 1877-1884). ACM..
Claudio Scordino (1): sched/deadline: documentation about GRUB reclaiming
Luca Abeni (9): sched/deadline: track the active utilization sched/deadline: improve the tracking of active utilization sched/deadline: fix the update of the total -deadline utilization sched/deadline: implement GRUB accounting sched/deadline: do not reclaim the whole CPU bandwidth sched/deadline: make GRUB a task's flag sched/deadline: track the "total rq utilization" too sched/deadline: base GRUB reclaiming on the inactive utilization sched/deadline: also reclaim bandwidth not used by dl tasks
Documentation/scheduler/sched-deadline.txt | 168 +++++++++++ include/linux/sched.h | 17 ++ include/uapi/linux/sched.h | 1 + kernel/sched/core.c | 74 ++--- kernel/sched/deadline.c | 448 +++++++++++++++++++++++++++-- kernel/sched/sched.h | 66 ++++- 6 files changed, 709 insertions(+), 65 deletions(-)
-- 2.7.4
| |