Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752650AbdCWTw6 (ORCPT ); Thu, 23 Mar 2017 15:52:58 -0400 Received: from mail.santannapisa.it ([193.205.80.99]:26882 "EHLO mail.santannapisa.it" rhost-flags-OK-FAIL-OK-OK) by vger.kernel.org with ESMTP id S1750952AbdCWTw5 (ORCPT ); Thu, 23 Mar 2017 15:52:57 -0400 From: luca abeni To: linux-kernel@vger.kernel.org Cc: Peter Zijlstra , Ingo Molnar , Juri Lelli , Claudio Scordino , Steven Rostedt , Tommaso Cucinotta , Daniel Bristot de Oliveira , Joel Fernandes , Mathieu Poirier , Luca Abeni Subject: [RFC v5 0/9] CPU reclaiming for SCHED_DEADLINE Date: Fri, 24 Mar 2017 04:52:53 +0100 Message-Id: <1490327582-4376-1-git-send-email-luca.abeni@santannapisa.it> X-Mailer: git-send-email 2.7.4 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3693 Lines: 72 From: Luca Abeni Hi all, here is yet another version of the patchset implementing 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 patches 0004 and 0008). 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 my last 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. Changes since v4: the most important change is the addition of patches 0007, 0008 and 0009 to solve the fairness problem highlighted by Daniel: http://lkml.iu.edu/hypermail/linux/kernel/1701.0/01290.html I added this fix in the last 3 patches for easier reviewing (up to patch 0006, the patches are similar to the previous ones), but I can merge / reorder patches if needed. I also performed some additional testing, finding and fixing some bugs in the first 6 patches. Daniel and Claudio also stress-tested the patchset, finding some other bugs that have been fixed. Other than this, I tried to address all the comments I received, and to add comments requested in the previous reviews. 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.. Luca Abeni (9): sched/deadline: track the active utilization sched/deadline: improve the tracking of active 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: base GRUB reclaiming on the inactive utilization sched/deadline: also reclaim bandwidth not used by dl tasks sched/deadline: fix the update of the total -deadline utilization sched/deadline: track the "total rq utilization" too include/linux/sched.h | 17 +++ include/uapi/linux/sched.h | 1 + kernel/sched/core.c | 65 ++++---- kernel/sched/deadline.c | 366 ++++++++++++++++++++++++++++++++++++++++++--- kernel/sched/sched.h | 62 +++++++- 5 files changed, 454 insertions(+), 57 deletions(-) -- 2.7.4