sched: SCHED_DEADLINE v9
Subsystems (10)
tip-bot for Peter Zijlstra
merge bot[tip:sched/core] rtmutex: Turn the plist into an rb-tree
In reply to Juri Lellirtmutex: Turn the plist into an rb-tree
Commit-ID: fb00aca474405f4fa8a8519c3179fed722eabd83 Gitweb: http://git.kernel.org/tip/fb00aca474405f4fa8a8519c3179fed722eabd83 Author: Peter Zijlstra <[email protected]> AuthorDate: Thu, 7 Nov 2013 14:43:43 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 13 Jan 2014 13:41:50 +0100
rtmutex: Turn the plist into an rb-tree
Turn the pi-chains from plist to rb-tree, in the rt_mutex code, and provide a proper comparison function for -deadline and -priority tasks.
This is done mainly because:
- classical prio field of the plist is just an int, which might not be enough for representing a deadline;
- manipulating such a list would become O(nr_deadline_tasks), which might be to much, as the number of -deadline task increases.
Therefore, an rb-tree is used, and tasks are queued in it according to the following logic:
- among two -priority (i.e., SCHED_BATCH/OTHER/RR/FIFO) tasks, the one with the higher (lower, actually!) prio wins;
- among a -priority and a -deadline task, the latter always wins;
- among two -deadline tasks, the one with the earliest deadline wins.
Queueing and dequeueing functions are changed accordingly, for both the list of a task's pi-waiters and the list of tasks blocked on a pi-lock.
--- include/linux/init_task.h | 10 +++ include/linux/rtmutex.h | 18 ++--- include/linux/sched.h | 4 +- kernel/fork.c | 3 +- kernel/futex.c | 2 + kernel/locking/rtmutex-debug.c | 8 +-- kernel/locking/rtmutex.c | 151 ++++++++++++++++++++++++++++++++-------- kernel/locking/rtmutex_common.h | 22 +++--- kernel/sched/core.c | 4 -- 9 files changed, 157 insertions(+), 65 deletions(-)
include/linux/init_task.h +10 -0
@@ -11,6 +11,7 @@#include <linux/user_namespace.h> #include <linux/securebits.h> #include <linux/seqlock.h> +#include <linux/rbtree.h> #include <net/net_namespace.h> #include <linux/sched/rt.h>
@@ -154,6 +155,14 @@ extern struct task_group root_task_group;#define INIT_TASK_COMM "swapper" +#ifdef CONFIG_RT_MUTEXES +# define INIT_RT_MUTEXES (tsk) \ + .pi_waiters = RB_ROOT, \ + .pi_waiters_leftmost = NULL, +#else +# define INIT_RT_MUTEXES (tsk) +#endif +/* * INIT_TASK is used to set up the first task table, touch at * your own risk!. Base=0, limit=0x1fffff (=2MB)
@@ -221,6 +230,7 @@ extern struct task_group root_task_group; INIT_TRACE_RECURSION \ INIT_TASK_RCU_PREEMPT(tsk) \ INIT_CPUSET_SEQ(tsk) \ + INIT_RT_MUTEXES(tsk) \ INIT_VTIME(tsk) \ }
include/linux/rtmutex.h +6 -12
@@ -13,7 +13,7 @@#define __LINUX_RT_MUTEX_H#include <linux/linkage.h> -#include <linux/plist.h> +#include <linux/rbtree.h> #include <linux/spinlock_types.h> extern int max_lock_depth;/* for sysctl */
@@ -22,12 +22,14 @@ extern int max_lock_depth; /* for sysctl */* The rt_mutex structure * * @wait_lock: spinlock to protect the structure -* @wait_list: pilist head to enqueue waiters in priority order +* @waiters: rbtree root to enqueue waiters in priority order +* @waiters_leftmost: top waiter * @owner: the mutex owner */ struct rt_mutex {raw_spinlock_t wait_lock; -struct plist_head wait_list; +struct rb_root waiters; +struct rb_node *waiters_leftmost;struct task_struct *owner;#ifdef CONFIG_DEBUG_RT_MUTEXES int save_state;
@@ -66,7 +68,7 @@ struct hrtimer_sleeper;#define __RT_MUTEX_INITIALIZER (mutexname) \ { .wait_lock = __RAW_SPIN_LOCK_UNLOCKED(mutexname.wait_lock) \ - , .wait_list = PLIST_HEAD_INIT(mutexname.wait_list) \ + , .waiters = RB_ROOT \ , .owner = NULL \ __DEBUG_RT_MUTEX_INITIALIZER(mutexname)}
@@ -98,12 +100,4 @@ extern int rt_mutex_trylock(struct rt_mutex *lock);extern void rt_mutex_unlock (struct rt_mutex *lock); -#ifdef CONFIG_RT_MUTEXES -# define INIT_RT_MUTEXES (tsk) \ - .pi_waiters = PLIST_HEAD_INIT(tsk.pi_waiters), \ - INIT_RT_MUTEX_DEBUG(tsk) -#else -# define INIT_RT_MUTEXES (tsk) -#endif -#endif
include/linux/sched.h +3 -1
@@ -16,6 +16,7 @@ struct sched_param {#include <linux/types.h> #include <linux/timex.h> #include <linux/jiffies.h> +#include <linux/plist.h> #include <linux/rbtree.h> #include <linux/thread_info.h> #include <linux/cpumask.h>
@@ -1354,7 +1355,8 @@ struct task_struct {#ifdef CONFIG_RT_MUTEXES /* PI waiters blocked on a rt_mutex held by this task */ -struct plist_head pi_waiters; +struct rb_root pi_waiters; +struct rb_node *pi_waiters_leftmost;/* Deadlock detection and priority inheritance handling */ struct rt_mutex_waiter *pi_blocked_on;#endif
kernel/fork.c +2 -1
@@ -1087,7 +1087,8 @@ static void rt_mutex_init_task(struct task_struct *p) {raw_spin_lock_init (&p->pi_lock);#ifdef CONFIG_RT_MUTEXES -plist_head_init (&p->pi_waiters); + p->pi_waiters =RB_ROOT ; + p->pi_waiters_leftmost =NULL ; p->pi_blocked_on =NULL ;#endif }
kernel/futex.c +2 -0
@@ -2316,6 +2316,8 @@ static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,* code while we sleep on uaddr. */ debug_rt_mutex_init_waiter (&rt_waiter); +RB_CLEAR_NODE (&rt_waiter.pi_tree_entry); +RB_CLEAR_NODE (&rt_waiter.tree_entry); rt_waiter.task =NULL ; ret =get_futex_key (uaddr2, flags &FLAGS_SHARED , &key2,VERIFY_WRITE );
kernel/locking/rtmutex-debug.c +2 -6
@@ -24,7 +24,7 @@#include <linux/kallsyms.h> #include <linux/syscalls.h> #include <linux/interrupt.h> -#include <linux/plist.h> +#include <linux/rbtree.h> #include <linux/fs.h> #include <linux/debug_locks.h>
@@ -57,7 +57,7 @@ static void printk_lock(struct rt_mutex *lock, int print_owner)void rt_mutex_debug_task_free (struct task_struct *task) { -DEBUG_LOCKS_WARN_ON (!plist_head_empty (&task->pi_waiters)); +DEBUG_LOCKS_WARN_ON (!RB_EMPTY_ROOT (&task->pi_waiters));DEBUG_LOCKS_WARN_ON (task->pi_blocked_on); }
@@ -154,16 +154,12 @@ void debug_rt_mutex_proxy_unlock(struct rt_mutex *lock)void debug_rt_mutex_init_waiter (struct rt_mutex_waiter *waiter) {memset (waiter,0x11 ,sizeof (*waiter)); -plist_node_init (&waiter->list_entry,MAX_PRIO ); -plist_node_init (&waiter->pi_list_entry,MAX_PRIO ); waiter->deadlock_task_pid =NULL ; }void debug_rt_mutex_free_waiter (struct rt_mutex_waiter *waiter) {put_pid (waiter->deadlock_task_pid); -DEBUG_LOCKS_WARN_ON (!plist_node_empty (&waiter->list_entry)); -DEBUG_LOCKS_WARN_ON (!plist_node_empty (&waiter->pi_list_entry));memset (waiter,0x22 ,sizeof (*waiter)); }
kernel/locking/rtmutex.c +121 -30
275 lines not on this page · raw message
kernel/locking/rtmutex_common.h +11 -11
@@ -40,13 +40,13 @@ extern void schedule_rt_mutex_test(struct rt_mutex *lock);* This is the control structure for tasks blocked on a rt_mutex, * which is allocated on the kernel stack on of the blocked task. * -* @list_entry: pi node to enqueue into the mutex waiters list -* @pi_list_entry: pi node to enqueue into the mutex owner waiters list +* @tree_entry: pi node to enqueue into the mutex waiters tree +* @pi_tree_entry: pi node to enqueue into the mutex owner waiters tree * @task: task reference to the blocked task */ struct rt_mutex_waiter { -struct plist_node list_entry; -struct plist_node pi_list_entry; +struct rb_node tree_entry; +struct rb_node pi_tree_entry;struct task_struct *task;struct rt_mutex *lock;#ifdef CONFIG_DEBUG_RT_MUTEXES
@@ -57,11 +57,11 @@ struct rt_mutex_waiter { };/* -* Various helpers to access the waiters-plist: +* Various helpers to access the waiters-tree: */ static inline int rt_mutex_has_waiters (struct rt_mutex *lock) { -return !plist_head_empty (&lock->wait_list); +return !RB_EMPTY_ROOT (&lock->waiters); } static inline struct rt_mutex_waiter *
@@ -69,8 +69,8 @@ rt_mutex_top_waiter(struct rt_mutex *lock) {struct rt_mutex_waiter *w; - w = plist_first_entry(&lock->wait_list, struct rt_mutex_waiter, - list_entry); + w = rb_entry(lock->waiters_leftmost, struct rt_mutex_waiter, + tree_entry);BUG_ON (w->lock != lock);return w;
@@ -78,14 +78,14 @@ rt_mutex_top_waiter(struct rt_mutex *lock)static inline int task_has_pi_waiters (struct task_struct *p) { -return !plist_head_empty (&p->pi_waiters); +return !RB_EMPTY_ROOT (&p->pi_waiters); }static inline struct rt_mutex_waiter *task_top_pi_waiter (struct task_struct *p) { - return plist_first_entry(&p->pi_waiters, struct rt_mutex_waiter, - pi_list_entry); + return rb_entry(p->pi_waiters_leftmost, struct rt_mutex_waiter, + pi_tree_entry); }/*
kernel/sched/core.c +0 -4
@@ -6635,10 +6635,6 @@ void __init sched_init(void)INIT_HLIST_HEAD (&init_task.preempt_notifiers);#endif -#ifdef CONFIG_RT_MUTEXES -plist_head_init (&init_task.pi_waiters); -#endif -/* * The boot idle thread does lazy MMU switching as well: */
PATCH 10/14 sched: drafted deadline inheritance logic.
In reply to Juri LelliFrom: Dario Faggioli <[email protected]>
Some method to deal with rt-mutexes and make sched_dl interact with the current PI-coded is needed, raising all but trivial issues, that needs (according to us) to be solved with some restructuring of the pi-code (i.e., going toward a proxy execution-ish implementation).
This is under development, in the meanwhile, as a temporary solution, what this commits does is:
- ensure a pi-lock owner with waiters is never throttled down. Instead, when it runs out of runtime, it immediately gets replenished and it's deadline is postponed;
- the scheduling parameters (relative deadline and default runtime) used for that replenishments --during the whole period it holds the pi-lock-- are the ones of the waiting task with earliest deadline.
Acting this way, we provide some kind of boosting to the lock-owner, still by using the existing (actually, slightly modified by the previous commit) pi-architecture.
We would stress the fact that this is only a surely needed, all but clean solution to the problem. In the end it's only a way to re-start discussion within the community. So, as always, comments, ideas, rants, etc.. are welcome! :-)
--- include/linux/sched.h | 8 +++- include/linux/sched/rt.h | 1 + kernel/fork.c | 1 + kernel/rtmutex.c | 14 +++++- kernel/sched/core.c | 36 ++++++++++++--- kernel/sched/deadline.c | 91 +++++++++++++++++++++---------------- kernel/sched/sched.h | 14 ++++++ kernel/trace/trace_sched_wakeup.c | 1 + 8 files changed, 119 insertions(+), 47 deletions(-)
include/linux/sched.h +7 -1
@@ -1099,8 +1099,12 @@ struct sched_dl_entity {* @dl_new tells if a new instance arrived. If so we must * start executing it with full runtime and reset its absolute * deadline; +* +* @dl_boosted tells if we are boosted due to DI. If so we are +* outside bandwidth enforcement mechanism (but only until we +* exit the critical section). */ -int dl_throttled, dl_new; +int dl_throttled, dl_new, dl_boosted;/* * Bandwidth enforcement timer. Each -deadline task has its
@@ -1345,6 +1349,8 @@ struct task_struct {struct rb_node *pi_waiters_leftmost;/* Deadlock detection and priority inheritance handling */ struct rt_mutex_waiter *pi_blocked_on; +/* Top pi_waiters task */ +struct task_struct *pi_top_task;#endif #ifdef CONFIG_DEBUG_MUTEXES
include/linux/sched/rt.h +1 -0
@@ -35,6 +35,7 @@ static inline int rt_task(struct task_struct *p)#ifdef CONFIG_RT_MUTEXES extern int rt_mutex_getprio (struct task_struct *p);extern void rt_mutex_setprio (struct task_struct *p,int prio); +extern struct task_struct *rt_mutex_get_top_task (struct task_struct *task);extern void rt_mutex_adjust_pi (struct task_struct *p);static inline bool tsk_is_pi_blocked (struct task_struct *tsk) {
kernel/fork.c +1 -0
@@ -1092,6 +1092,7 @@ static void rt_mutex_init_task(struct task_struct *p) p->pi_waiters =RB_ROOT ; p->pi_waiters_leftmost =NULL ; p->pi_blocked_on =NULL ; + p->pi_top_task =NULL ;#endif }
kernel/rtmutex.c +12 -2
@@ -14,6 +14,7 @@#include <linux/export.h> #include <linux/sched.h> #include <linux/sched/rt.h> +#include <linux/sched/deadline.h> #include <linux/timer.h> #include "rtmutex_common.h"
@@ -200,6 +201,14 @@ int rt_mutex_getprio(struct task_struct *task) task->normal_prio); } +struct task_struct *rt_mutex_get_top_task (struct task_struct *task) +{ +if (likely (!task_has_pi_waiters (task))) +return NULL ; + +return task_top_pi_waiter (task)->task; +} +/* * Adjust the priority of a task, after its pi_waiters got modified. *
@@ -209,7 +218,7 @@ static void __rt_mutex_adjust_prio(struct task_struct *task) {int prio =rt_mutex_getprio (task); -if (task->prio != prio) +if (task->prio != prio ||dl_prio (prio))rt_mutex_setprio (task, prio); }
@@ -652,7 +661,8 @@ void rt_mutex_adjust_pi(struct task_struct *task)raw_spin_lock_irqsave (&task->pi_lock, flags); waiter = task->pi_blocked_on; -if (!waiter || waiter->task->prio == task->prio) { +if (!waiter || (waiter->task->prio == task->prio && + !dl_prio (task->prio))) {raw_spin_unlock_irqrestore (&task->pi_lock, flags);return ; }
kernel/sched/core.c +30 -6
@@ -951,7 +951,7 @@ static inline void check_class_changed(struct rq *rq, struct task_struct *p,if (prev_class->switched_from) prev_class->switched_from (rq, p); p->sched_class->switched_to (rq, p); - }else if (oldprio != p->prio) + }else if (oldprio != p->prio ||dl_task (p)) p->sched_class->prio_changed (rq, p, oldprio); }
@@ -3042,7 +3042,7 @@ EXPORT_SYMBOL(sleep_on_timeout);*/ void rt_mutex_setprio (struct task_struct *p,int prio) { -int oldprio, on_rq, running; +int oldprio, on_rq, running, enqueue_flag =0 ;struct rq *rq;const struct sched_class *prev_class;
@@ -3069,6 +3069,7 @@ void rt_mutex_setprio(struct task_struct *p, int prio) }trace_sched_pi_setprio (p, prio); + p->pi_top_task =rt_mutex_get_top_task (p); oldprio = p->prio; prev_class = p->sched_class; on_rq = p->on_rq;
@@ -3078,19 +3079,42 @@ void rt_mutex_setprio(struct task_struct *p, int prio)if (running) p->sched_class->put_prev_task (rq, p); -if (dl_prio (prio)) +/* +* Boosting condition are: +* 1. -rt task is running and holds mutex A +* --> -dl task blocks on mutex A +* +* 2. -dl task is running and holds mutex A +* --> -dl task blocks on mutex A and could preempt the +* running task +*/ +if (dl_prio (prio)) { +if (!dl_prio (p->normal_prio) || (p->pi_top_task && +dl_entity_preempt (&p->pi_top_task->dl, &p->dl))) { + p->dl.dl_boosted =1 ; + p->dl.dl_throttled =0 ; + enqueue_flag =ENQUEUE_REPLENISH ; + }else + p->dl.dl_boosted =0 ; p->sched_class = &dl_sched_class; -else if (rt_prio (prio)) + }else if (rt_prio (prio)) { +if (dl_prio (oldprio)) + p->dl.dl_boosted =0 ; +if (oldprio < prio) + enqueue_flag =ENQUEUE_HEAD ; p->sched_class = &rt_sched_class; -else + }else { +if (dl_prio (oldprio)) + p->dl.dl_boosted =0 ; p->sched_class = &fair_sched_class; + } p->prio = prio;if (running) p->sched_class->set_curr_task (rq);if (on_rq) -enqueue_task (rq, p, oldprio < prio ?ENQUEUE_HEAD :0 ); +enqueue_task (rq, p, enqueue_flag);check_class_changed (rq, p, prev_class, oldprio); out_unlock:
kernel/sched/deadline.c +53 -38
208 lines not on this page · raw message
kernel/sched/sched.h +14 -0
@@ -105,6 +105,20 @@ static inline int task_has_dl_policy(struct task_struct *p)return dl_policy (p->policy); } +static inline int dl_time_before (u64 a,u64 b) +{ +return (s64)(a - b) <0 ; +} + +/* +* Tells if entity @a should preempt entity @b. +*/ +static inline +int dl_entity_preempt (struct sched_dl_entity *a,struct sched_dl_entity *b) +{ +return dl_time_before (a->deadline, b->deadline); +} +/* * This is the priority-queue data structure of the RT scheduling class: */
kernel/trace/trace_sched_wakeup.c +1 -0
@@ -16,6 +16,7 @@#include <linux/uaccess.h> #include <linux/ftrace.h> #include <linux/sched/rt.h> +#include <linux/sched/deadline.h> #include <trace/events/sched.h> #include "trace.h"
Signature · 1 line
1.7.9.5
tip-bot for Dario Faggioli
merge bot[tip:sched/core] sched/deadline: Add SCHED_DEADLINE inheritance logic
sched/deadline: Add SCHED_DEADLINE inheritance logic
Commit-ID: 2d3d891d3344159d5b452a645e355bbe29591e8b Gitweb: http://git.kernel.org/tip/2d3d891d3344159d5b452a645e355bbe29591e8b Author: Dario Faggioli <[email protected]> AuthorDate: Thu, 7 Nov 2013 14:43:44 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 13 Jan 2014 13:42:56 +0100
sched/deadline: Add SCHED_DEADLINE inheritance logic
Some method to deal with rt-mutexes and make sched_dl interact with the current PI-coded is needed, raising all but trivial issues, that needs (according to us) to be solved with some restructuring of the pi-code (i.e., going toward a proxy execution-ish implementation).
This is under development, in the meanwhile, as a temporary solution, what this commits does is:
- ensure a pi-lock owner with waiters is never throttled down. Instead, when it runs out of runtime, it immediately gets replenished and it's deadline is postponed;
- the scheduling parameters (relative deadline and default runtime) used for that replenishments --during the whole period it holds the pi-lock-- are the ones of the waiting task with earliest deadline.
Acting this way, we provide some kind of boosting to the lock-owner, still by using the existing (actually, slightly modified by the previous commit) pi-architecture.
We would stress the fact that this is only a surely needed, all but clean solution to the problem. In the end it's only a way to re-start discussion within the community. So, as always, comments, ideas, rants, etc.. are welcome! :-)
--- include/linux/sched.h | 8 +++- include/linux/sched/rt.h | 5 +++ kernel/fork.c | 1 + kernel/locking/rtmutex.c | 31 +++++++++---- kernel/locking/rtmutex_common.h | 1 + kernel/sched/core.c | 36 +++++++++++++--- kernel/sched/deadline.c | 91 +++++++++++++++++++++++---------------- kernel/sched/sched.h | 14 ++++++ kernel/trace/trace_sched_wakeup.c | 1 + 9 files changed, 134 insertions(+), 54 deletions(-)
include/linux/sched.h +7 -1
@@ -1124,8 +1124,12 @@ struct sched_dl_entity {* @dl_new tells if a new instance arrived. If so we must * start executing it with full runtime and reset its absolute * deadline; +* +* @dl_boosted tells if we are boosted due to DI. If so we are +* outside bandwidth enforcement mechanism (but only until we +* exit the critical section). */ -int dl_throttled, dl_new; +int dl_throttled, dl_new, dl_boosted;/* * Bandwidth enforcement timer. Each -deadline task has its
@@ -1359,6 +1363,8 @@ struct task_struct {struct rb_node *pi_waiters_leftmost;/* Deadlock detection and priority inheritance handling */ struct rt_mutex_waiter *pi_blocked_on; +/* Top pi_waiters task */ +struct task_struct *pi_top_task;#endif #ifdef CONFIG_DEBUG_MUTEXES
include/linux/sched/rt.h +5 -0
@@ -35,6 +35,7 @@ static inline int rt_task(struct task_struct *p)#ifdef CONFIG_RT_MUTEXES extern int rt_mutex_getprio (struct task_struct *p);extern void rt_mutex_setprio (struct task_struct *p,int prio); +extern struct task_struct *rt_mutex_get_top_task (struct task_struct *task);extern void rt_mutex_adjust_pi (struct task_struct *p);static inline bool tsk_is_pi_blocked (struct task_struct *tsk) {
@@ -45,6 +46,10 @@ static inline int rt_mutex_getprio(struct task_struct *p) {return p->normal_prio; } +static inline struct task_struct *rt_mutex_get_top_task (struct task_struct *task) +{ +return NULL ; +}# define rt_mutex_adjust_pi (p) do { } while (0)static inline bool tsk_is_pi_blocked (struct task_struct *tsk) {
kernel/fork.c +1 -0
@@ -1090,6 +1090,7 @@ static void rt_mutex_init_task(struct task_struct *p) p->pi_waiters =RB_ROOT ; p->pi_waiters_leftmost =NULL ; p->pi_blocked_on =NULL ; + p->pi_top_task =NULL ;#endif }
kernel/locking/rtmutex.c +22 -9
@@ -96,13 +96,16 @@ static inline int rt_mutex_waiter_less(struct rt_mutex_waiter *left, struct rt_mutex_waiter *right) { -if (left->task->prio < right->task->prio) +if (left->prio < right->prio)return 1 ;/* -* If both tasks are dl_task(), we check their deadlines. +* If both waiters have dl_prio(), we check the deadlines of the +* associated tasks. +* If left waiter has a dl_prio(), and we didn't return 1 above, +* then right waiter has a dl_prio() too. */ -if (dl_prio (left->task->prio) &&dl_prio (right->task->prio)) +if (dl_prio (left->prio))return (left->task->dl.deadline < right->task->dl.deadline);return 0 ;
@@ -197,10 +200,18 @@ int rt_mutex_getprio(struct task_struct *task)if (likely (!task_has_pi_waiters (task)))return task->normal_prio; -return min (task_top_pi_waiter (task)->task->prio, +return min (task_top_pi_waiter (task)->prio, task->normal_prio); } +struct task_struct *rt_mutex_get_top_task (struct task_struct *task) +{ +if (likely (!task_has_pi_waiters (task))) +return NULL ; + +return task_top_pi_waiter (task)->task; +} +/* * Adjust the priority of a task, after its pi_waiters got modified. *
@@ -210,7 +221,7 @@ static void __rt_mutex_adjust_prio(struct task_struct *task) {int prio =rt_mutex_getprio (task); -if (task->prio != prio) +if (task->prio != prio ||dl_prio (prio))rt_mutex_setprio (task, prio); }
@@ -328,7 +339,7 @@ static int rt_mutex_adjust_prio_chain(struct task_struct *task,* When deadlock detection is off then we check, if further * priority adjustment is necessary. */ -if (!detect_deadlock && waiter->task->prio == task->prio) +if (!detect_deadlock && waiter->prio == task->prio) goto out_unlock_pi; lock = waiter->lock;
@@ -350,7 +361,7 @@ static int rt_mutex_adjust_prio_chain(struct task_struct *task,/* Requeue the waiter */ rt_mutex_dequeue (lock, waiter); - waiter->task->prio = task->prio; + waiter->prio = task->prio;rt_mutex_enqueue (lock, waiter);/* Release the task */
@@ -448,7 +459,7 @@ static int try_to_take_rt_mutex(struct rt_mutex *lock, struct task_struct *task,* 3) it is top waiter */ if (rt_mutex_has_waiters (lock)) { -if (task->prio >=rt_mutex_top_waiter (lock)->task->prio) { +if (task->prio >=rt_mutex_top_waiter (lock)->prio) {if (!waiter || waiter !=rt_mutex_top_waiter (lock))return 0 ; }
@@ -508,6 +519,7 @@ static int task_blocks_on_rt_mutex(struct rt_mutex *lock,__rt_mutex_adjust_prio (task); waiter->task = task; waiter->lock = lock; + waiter->prio = task->prio;/* Get the top priority waiter on the lock */ if (rt_mutex_has_waiters (lock))
@@ -653,7 +665,8 @@ void rt_mutex_adjust_pi(struct task_struct *task)raw_spin_lock_irqsave (&task->pi_lock, flags); waiter = task->pi_blocked_on; -if (!waiter || waiter->task->prio == task->prio) { +if (!waiter || (waiter->prio == task->prio && + !dl_prio (task->prio))) {raw_spin_unlock_irqrestore (&task->pi_lock, flags);return ; }
kernel/locking/rtmutex_common.h +1 -0
@@ -54,6 +54,7 @@ struct rt_mutex_waiter {struct pid *deadlock_task_pid;struct rt_mutex *deadlock_lock;#endif +int prio; };/*
kernel/sched/core.c +30 -6
@@ -947,7 +947,7 @@ static inline void check_class_changed(struct rq *rq, struct task_struct *p,if (prev_class->switched_from) prev_class->switched_from (rq, p); p->sched_class->switched_to (rq, p); - }else if (oldprio != p->prio) + }else if (oldprio != p->prio ||dl_task (p)) p->sched_class->prio_changed (rq, p, oldprio); }
@@ -2781,7 +2781,7 @@ EXPORT_SYMBOL(sleep_on_timeout);*/ void rt_mutex_setprio (struct task_struct *p,int prio) { -int oldprio, on_rq, running; +int oldprio, on_rq, running, enqueue_flag =0 ;struct rq *rq;const struct sched_class *prev_class;
@@ -2808,6 +2808,7 @@ void rt_mutex_setprio(struct task_struct *p, int prio) }trace_sched_pi_setprio (p, prio); + p->pi_top_task =rt_mutex_get_top_task (p); oldprio = p->prio; prev_class = p->sched_class; on_rq = p->on_rq;
@@ -2817,19 +2818,42 @@ void rt_mutex_setprio(struct task_struct *p, int prio)if (running) p->sched_class->put_prev_task (rq, p); -if (dl_prio (prio)) +/* +* Boosting condition are: +* 1. -rt task is running and holds mutex A +* --> -dl task blocks on mutex A +* +* 2. -dl task is running and holds mutex A +* --> -dl task blocks on mutex A and could preempt the +* running task +*/ +if (dl_prio (prio)) { +if (!dl_prio (p->normal_prio) || (p->pi_top_task && +dl_entity_preempt (&p->pi_top_task->dl, &p->dl))) { + p->dl.dl_boosted =1 ; + p->dl.dl_throttled =0 ; + enqueue_flag =ENQUEUE_REPLENISH ; + }else + p->dl.dl_boosted =0 ; p->sched_class = &dl_sched_class; -else if (rt_prio (prio)) + }else if (rt_prio (prio)) { +if (dl_prio (oldprio)) + p->dl.dl_boosted =0 ; +if (oldprio < prio) + enqueue_flag =ENQUEUE_HEAD ; p->sched_class = &rt_sched_class; -else + }else { +if (dl_prio (oldprio)) + p->dl.dl_boosted =0 ; p->sched_class = &fair_sched_class; + } p->prio = prio;if (running) p->sched_class->set_curr_task (rq);if (on_rq) -enqueue_task (rq, p, oldprio < prio ?ENQUEUE_HEAD :0 ); +enqueue_task (rq, p, enqueue_flag);check_class_changed (rq, p, prev_class, oldprio); out_unlock:
kernel/sched/deadline.c +53 -38
208 lines not on this page · raw message
kernel/sched/sched.h +14 -0
@@ -107,6 +107,20 @@ static inline int task_has_dl_policy(struct task_struct *p)return dl_policy (p->policy); } +static inline int dl_time_before (u64 a,u64 b) +{ +return (s64)(a - b) <0 ; +} + +/* +* Tells if entity @a should preempt entity @b. +*/ +static inline +int dl_entity_preempt (struct sched_dl_entity *a,struct sched_dl_entity *b) +{ +return dl_time_before (a->deadline, b->deadline); +} +/* * This is the priority-queue data structure of the RT scheduling class: */
kernel/trace/trace_sched_wakeup.c +1 -0
@@ -16,6 +16,7 @@#include <linux/uaccess.h> #include <linux/ftrace.h> #include <linux/sched/rt.h> +#include <linux/sched/deadline.h> #include <trace/events/sched.h> #include "trace.h"
PATCH 11/14 sched: add bandwidth management for sched_dl.
In reply to Juri LelliFrom: Dario Faggioli <[email protected]>
In order of -deadline scheduling to be effective and useful, it is important that some method of having the allocation of the available CPU bandwidth to tasks and task groups 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 have a bandwidth associated to itself, 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, this patch adds a less sophisticated, but actually very sensible, mechanism to ensure that a certain utilization cap is not overcome per each root_domain (the single rq for !SMP configurations).
Another main difference between deadline bandwidth management and RT-throttling is that -deadline tasks have bandwidth on their own (while -rt ones doesn't!), and thus we don't need an higher level throttling mechanism to enforce the desired bandwidth.
This patch, therefore:
- adds system wide deadline bandwidth management by means of:
* /proc/sys/kernel/sched_dl_runtime_us,
* /proc/sys/kernel/sched_dl_period_us,
that determine (i.e., runtime / period) the total bandwidth available on each CPU of each root_domain for -deadline tasks;
- couples the RT and deadline bandwidth management, i.e., enforces that the sum of how much bandwidth is being devoted to -rt -deadline tasks to stay below 100%.
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_dl_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.
--- include/linux/sched.h | 1 + include/linux/sched/sysctl.h | 13 ++ kernel/sched/core.c | 431 +++++++++++++++++++++++++++++++++++++++--- kernel/sched/deadline.c | 50 ++++- kernel/sched/sched.h | 74 +++++++- kernel/sysctl.c | 14 ++ 6 files changed, 549 insertions(+), 34 deletions(-)
include/linux/sched.h +1 -0
@@ -1079,6 +1079,7 @@ struct sched_dl_entity {u64 dl_runtime;/* maximum runtime for each instance */ u64 dl_deadline;/* relative deadline of each instance */ u64 dl_period;/* separation of two instances (period) */ +u64 dl_bw;/* dl_runtime / dl_deadline */ /* * Actual scheduling parameters. Initialized with the values above,
include/linux/sched/sysctl.h +13 -0
@@ -83,6 +83,15 @@ static inline unsigned int get_sysctl_timer_migration(void)extern unsigned int sysctl_sched_rt_period;extern int sysctl_sched_rt_runtime; +/* +* control SCHED_DEADLINE reservations: +* +* /proc/sys/kernel/sched_dl_period_us +* /proc/sys/kernel/sched_dl_runtime_us +*/ +extern unsigned int sysctl_sched_dl_period; +extern int sysctl_sched_dl_runtime; +#ifdef CONFIG_CFS_BANDWIDTH extern unsigned int sysctl_sched_cfs_bandwidth_slice;#endif
@@ -101,4 +110,8 @@ extern int sched_rt_handler(struct ctl_table *table, int write, void __user *buffer, size_t *lenp, loff_t *ppos); +int sched_dl_handler (struct ctl_table *table,int write, +void __user *buffer,size_t *lenp, +loff_t *ppos); +#endif /* _SCHED_SYSCTL_H */
kernel/sched/core.c +406 -25
560 lines not on this page · raw message
kernel/sched/deadline.c +44 -6
98 lines not on this page · raw message
kernel/sched/sched.h +71 -3
131 lines not on this page · raw message
kernel/sysctl.c +14 -0
@@ -414,6 +414,20 @@ static struct ctl_table kern_table[] = { .mode = 0644, .proc_handler = sched_rr_handler, }, + { + .procname = "sched_dl_period_us", + .data = &sysctl_sched_dl_period, + .maxlen = sizeof(unsigned int), + .mode = 0644, + .proc_handler = sched_dl_handler, + }, + { + .procname = "sched_dl_runtime_us", + .data = &sysctl_sched_dl_runtime, + .maxlen = sizeof(int), + .mode = 0644, + .proc_handler = sched_dl_handler, + }, #ifdef CONFIG_SCHED_AUTOGROUP { .procname = "sched_autogroup_enabled",
Signature · 1 line
1.7.9.5
tip-bot for Dario Faggioli
merge bot[tip:sched/core] sched/deadline: Add bandwidth management for SCHED_DEADLINE tasks
sched/deadline: Add bandwidth management for SCHED_DEADLINE tasks
Commit-ID: 332ac17ef5bfcff4766dfdfd3b4cdf10b8f8f155 Gitweb: http://git.kernel.org/tip/332ac17ef5bfcff4766dfdfd3b4cdf10b8f8f155 Author: Dario Faggioli <[email protected]> AuthorDate: Thu, 7 Nov 2013 14:43:45 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 13 Jan 2014 13:46:42 +0100
sched/deadline: Add bandwidth management for SCHED_DEADLINE tasks
In order of deadline scheduling to be effective and useful, it is important that some method of having the allocation of the available CPU bandwidth to tasks and task groups 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 have a bandwidth associated to itself, 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, this patch adds a less sophisticated, but actually very sensible, mechanism to ensure that a certain utilization cap is not overcome per each root_domain (the single rq for !SMP configurations).
Another main difference between deadline bandwidth management and RT-throttling is that -deadline tasks have bandwidth on their own (while -rt ones doesn't!), and thus we don't need an higher level throttling mechanism to enforce the desired bandwidth.
This patch, therefore:
- adds system wide deadline bandwidth management by means of:
* /proc/sys/kernel/sched_dl_runtime_us,
* /proc/sys/kernel/sched_dl_period_us,
that determine (i.e., runtime / period) the total bandwidth available on each CPU of each root_domain for -deadline tasks;
- couples the RT and deadline bandwidth management, i.e., enforces that the sum of how much bandwidth is being devoted to -rt -deadline tasks to stay below 100%.
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_dl_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.
--- include/linux/sched.h | 1 + include/linux/sched/sysctl.h | 13 ++ kernel/sched/core.c | 441 ++++++++++++++++++++++++++++++++++++++++--- kernel/sched/deadline.c | 46 ++++- kernel/sched/sched.h | 76 +++++++- kernel/sysctl.c | 14 ++ 6 files changed, 555 insertions(+), 36 deletions(-)
include/linux/sched.h +1 -0
@@ -1104,6 +1104,7 @@ struct sched_dl_entity {u64 dl_runtime;/* maximum runtime for each instance */ u64 dl_deadline;/* relative deadline of each instance */ u64 dl_period;/* separation of two instances (period) */ +u64 dl_bw;/* dl_runtime / dl_deadline */ /* * Actual scheduling parameters. Initialized with the values above,
include/linux/sched/sysctl.h +13 -0
@@ -81,6 +81,15 @@ static inline unsigned int get_sysctl_timer_migration(void)extern unsigned int sysctl_sched_rt_period;extern int sysctl_sched_rt_runtime; +/* +* control SCHED_DEADLINE reservations: +* +* /proc/sys/kernel/sched_dl_period_us +* /proc/sys/kernel/sched_dl_runtime_us +*/ +extern unsigned int sysctl_sched_dl_period; +extern int sysctl_sched_dl_runtime; +#ifdef CONFIG_CFS_BANDWIDTH extern unsigned int sysctl_sched_cfs_bandwidth_slice;#endif
@@ -99,4 +108,8 @@ extern int sched_rt_handler(struct ctl_table *table, int write, void __user *buffer, size_t *lenp, loff_t *ppos); +int sched_dl_handler (struct ctl_table *table,int write, +void __user *buffer,size_t *lenp, +loff_t *ppos); +#endif /* _SCHED_SYSCTL_H */
kernel/sched/core.c +414 -27
574 lines not on this page · raw message
kernel/sched/deadline.c +40 -6
94 lines not on this page · raw message
kernel/sched/sched.h +73 -3
133 lines not on this page · raw message
kernel/sysctl.c +14 -0
@@ -414,6 +414,20 @@ static struct ctl_table kern_table[] = { .mode = 0644, .proc_handler = sched_rr_handler, }, + { + .procname = "sched_dl_period_us", + .data = &sysctl_sched_dl_period, + .maxlen = sizeof(unsigned int), + .mode = 0644, + .proc_handler = sched_dl_handler, + }, + { + .procname = "sched_dl_runtime_us", + .data = &sysctl_sched_dl_runtime, + .maxlen = sizeof(int), + .mode = 0644, + .proc_handler = sched_dl_handler, + }, #ifdef CONFIG_SCHED_AUTOGROUP { .procname = "sched_autogroup_enabled",
PATCH 12/14 sched: make dl_bw a sub-quota of rt_bw
In reply to Juri LelliChange real-time bandwidth management as to make dl_bw a sub-quota of rt_bw. This patch leaves rt_bw at its default value and sets dl_bw at 40% of rt_bw. It also remove sched_dl_period_us control knob using sched_rt_period_us as common period for both rt_bw and dl_bw.
Checks are made when the user tries to change dl_bw sub-quota as to not fall below what currently used. Since dl_bw now depends upon rt_bw, similar checks are performed when the users modifies rt_bw and dl_bw is changed accordingly. Setting rt_bw sysctl variable to -1 (actually disabling rt throttling) disables dl_bw checks as well.
--- include/linux/sched/deadline.h | 2 + include/linux/sched/sysctl.h | 2 - kernel/sched/core.c | 322 ++++++++++++++++++++-------------------- kernel/sched/deadline.c | 13 +- kernel/sched/sched.h | 24 ++- kernel/sysctl.c | 7 - 6 files changed, 173 insertions(+), 197 deletions(-)
include/linux/sched/deadline.h +2 -0
@@ -21,4 +21,6 @@ static inline int dl_task(struct task_struct *p) return dl_prio(p->prio); } +extern inline struct dl_bw *dl_bw_of (int i); +#endif /* _SCHED_DEADLINE_H */
include/linux/sched/sysctl.h +0 -2
@@ -86,10 +86,8 @@ extern int sysctl_sched_rt_runtime;/* * control SCHED_DEADLINE reservations: * -* /proc/sys/kernel/sched_dl_period_us * /proc/sys/kernel/sched_dl_runtime_us */ -extern unsigned int sysctl_sched_dl_period;extern int sysctl_sched_dl_runtime;#ifdef CONFIG_CFS_BANDWIDTH
kernel/sched/core.c +157 -165
457 lines not on this page · raw message
kernel/sched/deadline.c +4 -9
@@ -48,10 +48,9 @@ static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq)return dl_rq->rb_leftmost == &dl_se->rb_node; } -void init_dl_bandwidth (struct dl_bandwidth *dl_b,u64 period,u64 runtime) +void init_dl_bandwidth (struct dl_bandwidth *dl_b,u64 runtime) {raw_spin_lock_init (&dl_b->dl_runtime_lock); - dl_b->dl_period = period; dl_b->dl_runtime = runtime; }
@@ -62,9 +61,9 @@ void init_dl_bw(struct dl_bw *dl_b)raw_spin_lock_init (&dl_b->lock);raw_spin_lock (&def_dl_bandwidth.dl_runtime_lock);if (global_dl_runtime () ==RUNTIME_INF ) - dl_b->bw =-1 ; + dl_b->bw =ULLONG_MAX ;else - dl_b->bw =to_ratio (global_dl_period (),global_dl_runtime ()); + dl_b->bw =to_ratio (global_rt_period (),global_dl_runtime ());raw_spin_unlock (&def_dl_bandwidth.dl_runtime_lock); dl_b->total_bw =0 ; }
@@ -1061,11 +1060,7 @@ static void task_fork_dl(struct task_struct *p)static void task_dead_dl (struct task_struct *p) {struct hrtimer *timer = &p->dl.dl_timer; -#ifdef CONFIG_SMP -struct dl_bw *dl_b = &task_rq (p)->rd->dl_bw; -#else -struct dl_bw *dl_b = &task_rq (p)->dl.dl_bw; -#endif +struct dl_bw *dl_b =dl_bw_of (task_cpu (p));/* * Since we are TASK_DEAD we won't slip out of the domain!
kernel/sched/sched.h +10 -14
@@ -142,20 +142,20 @@ struct rt_bandwidth {struct hrtimer rt_period_timer; };/* -* To keep the bandwidth of -deadline tasks and groups under control -* we need some place where: -* - store the maximum -deadline bandwidth of the system (the group); +* To keep the bandwidth of -deadline tasks under control we need some +* place where: +* - store the maximum -deadline bandwidth of the system; * - cache the fraction of that bandwidth that is currently allocated. * * This is all done in the data structure below. It is similar to the * one used for RT-throttling (rt_bandwidth), with the main difference * that, since here we are only interested in admission control, we -* do not decrease any runtime while the group "executes", neither we +* do not decrease any runtime while the task "executes", neither we * need a timer to replenish it. * * With respect to SMP, the bandwidth is given on a per-CPU basis, * meaning that: -* - dl_bw (< 100%) is the bandwidth of the system (group) on each CPU; +* - dl_bw (< 100%) is the bandwidth of the system on each CPU; * - dl_total_bw array contains, in the i-eth element, the currently * allocated bandwidth on the i-eth CPU. * Moreover, groups consume bandwidth on each CPU, while tasks only
@@ -168,7 +168,6 @@ struct rt_bandwidth {struct dl_bandwidth {raw_spinlock_t dl_runtime_lock;u64 dl_runtime; -u64 dl_period; };static inline int dl_bandwidth_enabled (void )
@@ -178,10 +177,12 @@ static inline int dl_bandwidth_enabled(void)struct dl_bw {raw_spinlock_t lock; -u64 bw, total_bw; +/* default value */ +u64 bw; +/* allocated */ +u64 total_bw; }; -static inline u64 global_dl_period (void );static inline u64 global_dl_runtime (void );extern struct mutex sched_domains_mutex;
@@ -924,11 +925,6 @@ static inline u64 global_rt_runtime(void)return (u64 )sysctl_sched_rt_runtime *NSEC_PER_USEC ; } -static inline u64 global_dl_period (void ) -{ -return (u64 )sysctl_sched_dl_period *NSEC_PER_USEC ; -} -static inline u64 global_dl_runtime (void ) {if (sysctl_sched_dl_runtime <0 )
@@ -1192,7 +1188,7 @@ extern struct rt_bandwidth def_rt_bandwidth;extern void init_rt_bandwidth (struct rt_bandwidth *rt_b,u64 period,u64 runtime);extern struct dl_bandwidth def_dl_bandwidth; -extern void init_dl_bandwidth (struct dl_bandwidth *dl_b,u64 period,u64 runtime); +extern void init_dl_bandwidth (struct dl_bandwidth *dl_b,u64 runtime);extern void init_dl_task_timer (struct sched_dl_entity *dl_se);unsigned long to_ratio (u64 period,u64 runtime);
kernel/sysctl.c +0 -7
@@ -415,13 +415,6 @@ static struct ctl_table kern_table[] = { .proc_handler = sched_rr_handler, }, { - .procname = "sched_dl_period_us", - .data = &sysctl_sched_dl_period, - .maxlen = sizeof(unsigned int), - .mode = 0644, - .proc_handler = sched_dl_handler, - }, - { .procname = "sched_dl_runtime_us", .data = &sysctl_sched_dl_runtime, .maxlen = sizeof(int),
Signature · 1 line
1.7.9.5
PATCH 13/14 sched: speed up -dl pushes with a push-heap.
In reply to Juri LelliData from tests confirmed that the original active load balancing logic didn't scale neither in the number of CPU nor in the number of tasks (as sched_rt does).
Here we provide a global data structure to keep track of deadlines of the running tasks in the system. The structure is composed by a bitmask showing the free CPUs and a max-heap, needed when the system is heavily loaded.
The implementation and concurrent access scheme are kept simple by design. However, our measurements show that we can compete with sched_rt on large multi-CPUs machines [1].
Only the push path is addressed, the extension to use this structure also for pull decisions is straightforward. However, we are currently evaluating different (in order to decrease/avoid contention) data structures to solve possibly both problems. We are also going to re-run tests considering recent changes inside cpupri [2].
[1] http://retis.sssup.it/~jlelli/papers/Ospert11Lelli.pdf
[2] http://www.spinics.net/lists/linux-rt-users/msg06778.html
--- kernel/sched/Makefile | 2 +- kernel/sched/core.c | 3 + kernel/sched/cpudeadline.c | 216 ++++++++++++++++++++++++++++++++++++++++++++ kernel/sched/cpudeadline.h | 33 +++++++ kernel/sched/deadline.c | 53 +++-------- kernel/sched/sched.h | 2 + 6 files changed, 269 insertions(+), 40 deletions(-) create mode 100644 kernel/sched/cpudeadline.c create mode 100644 kernel/sched/cpudeadline.h
kernel/sched/Makefile +1 -1
@@ -12,7 +12,7 @@ CFLAGS_core.o := $(PROFILING) -fno-omit-frame-pointer endif obj-y += core.o proc.o clock.o cputime.o idle_task.o fair.o rt.o deadline.o stop_task.o -obj-$(CONFIG_SMP) += cpupri.o +obj-$(CONFIG_SMP) += cpupri.o cpudeadline.o obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o obj-$(CONFIG_SCHEDSTATS) += stats.o obj-$(CONFIG_SCHED_DEBUG) += debug.o
kernel/sched/core.c +3 -0
@@ -5398,6 +5398,7 @@ static void free_rootdomain(struct rcu_head *rcu) struct root_domain *rd = container_of(rcu, struct root_domain, rcu);cpupri_cleanup (&rd->cpupri); +cpudl_cleanup (&rd->cpudl);free_cpumask_var (rd->dlo_mask);free_cpumask_var (rd->rto_mask);free_cpumask_var (rd->online);
@@ -5456,6 +5457,8 @@ static int init_rootdomain(struct root_domain *rd) goto free_dlo_mask;init_dl_bw (&rd->dl_bw); +if (cpudl_init (&rd->cpudl) !=0 ) + goto free_dlo_mask;if (cpupri_init (&rd->cpupri) !=0 ) goto free_rto_mask;
kernel/sched/cpudeadline.c new file +216 -0
216 lines not on this page · raw message
kernel/sched/cpudeadline.h new file +33 -0
@@ -0,0 +1,33 @@ +#ifndef _LINUX_CPUDL_H +#define _LINUX_CPUDL_H + +#include <linux/sched.h> + +#define IDX_INVALID -1 + +struct array_item { +u64 dl; +int cpu; +}; + +struct cpudl { +raw_spinlock_t lock; +int size; +int cpu_to_idx[NR_CPUS ]; +struct array_item elements[NR_CPUS ]; +cpumask_var_t free_cpus; +}; + + +#ifdef CONFIG_SMP +int cpudl_find (struct cpudl *cp,struct task_struct *p, +struct cpumask *later_mask); +void cpudl_set (struct cpudl *cp,int cpu,u64 dl,int is_valid); +int cpudl_init (struct cpudl *cp); +void cpudl_cleanup (struct cpudl *cp); +#else +#define cpudl_set (cp, cpu, dl) do { } while (0) +#define cpudl_init () do { } while (0) +#endif /* CONFIG_SMP */ + +#endif /* _LINUX_CPUDL_H */
kernel/sched/deadline.c +14 -39
119 lines not on this page · raw message
kernel/sched/sched.h +2 -0
@@ -9,6 +9,7 @@#include <linux/tick.h> #include "cpupri.h" +#include "cpudeadline.h" #include "cpuacct.h" struct rq ;
@@ -507,6 +508,7 @@ struct root_domain {cpumask_var_t dlo_mask;atomic_t dlo_count;struct dl_bw dl_bw; +struct cpudl cpudl;/* * The "RT overload" flag: it gets set if a CPU has more than
Signature · 1 line
1.7.9.5
tip-bot for Juri Lelli
merge bot[tip:sched/core] sched/deadline: speed up SCHED_DEADLINE pushes with a push-heap
sched/deadline: speed up SCHED_DEADLINE pushes with a push-heap
Commit-ID: 6bfd6d72f51c51177676f2b1ba113fe0a85fdae4 Gitweb: http://git.kernel.org/tip/6bfd6d72f51c51177676f2b1ba113fe0a85fdae4 Author: Juri Lelli <[email protected]> AuthorDate: Thu, 7 Nov 2013 14:43:47 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 13 Jan 2014 13:46:46 +0100
sched/deadline: speed up SCHED_DEADLINE pushes with a push-heap
Data from tests confirmed that the original active load balancing logic didn't scale neither in the number of CPU nor in the number of tasks (as sched_rt does).
Here we provide a global data structure to keep track of deadlines of the running tasks in the system. The structure is composed by a bitmask showing the free CPUs and a max-heap, needed when the system is heavily loaded.
The implementation and concurrent access scheme are kept simple by design. However, our measurements show that we can compete with sched_rt on large multi-CPUs machines [1].
Only the push path is addressed, the extension to use this structure also for pull decisions is straightforward. However, we are currently evaluating different (in order to decrease/avoid contention) data structures to solve possibly both problems. We are also going to re-run tests considering recent changes inside cpupri [2].
[1] http://retis.sssup.it/~jlelli/papers/Ospert11Lelli.pdf
[2] http://www.spinics.net/lists/linux-rt-users/msg06778.html
--- kernel/sched/Makefile | 2 +- kernel/sched/core.c | 3 + kernel/sched/cpudeadline.c | 216 +++++++++++++++++++++++++++++++++++++++++++++ kernel/sched/cpudeadline.h | 33 +++++++ kernel/sched/deadline.c | 53 +++-------- kernel/sched/sched.h | 2 + 6 files changed, 269 insertions(+), 40 deletions(-)
kernel/sched/Makefile +1 -1
@@ -14,7 +14,7 @@ endif obj-y += core.o proc.o clock.o cputime.o obj-y += idle_task.o fair.o rt.o deadline.o stop_task.o obj-y += wait.o completion.o -obj-$(CONFIG_SMP) += cpupri.o +obj-$(CONFIG_SMP) += cpupri.o cpudeadline.o obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o obj-$(CONFIG_SCHEDSTATS) += stats.o obj-$(CONFIG_SCHED_DEBUG) += debug.o
kernel/sched/core.c +3 -0
@@ -5287,6 +5287,7 @@ static void free_rootdomain(struct rcu_head *rcu) struct root_domain *rd = container_of(rcu, struct root_domain, rcu);cpupri_cleanup (&rd->cpupri); +cpudl_cleanup (&rd->cpudl);free_cpumask_var (rd->dlo_mask);free_cpumask_var (rd->rto_mask);free_cpumask_var (rd->online);
@@ -5345,6 +5346,8 @@ static int init_rootdomain(struct root_domain *rd) goto free_dlo_mask;init_dl_bw (&rd->dl_bw); +if (cpudl_init (&rd->cpudl) !=0 ) + goto free_dlo_mask;if (cpupri_init (&rd->cpupri) !=0 ) goto free_rto_mask;
kernel/sched/cpudeadline.c new file +216 -0
216 lines not on this page · raw message
kernel/sched/cpudeadline.h new file +33 -0
@@ -0,0 +1,33 @@ +#ifndef _LINUX_CPUDL_H +#define _LINUX_CPUDL_H + +#include <linux/sched.h> + +#define IDX_INVALID -1 + +struct array_item { +u64 dl; +int cpu; +}; + +struct cpudl { +raw_spinlock_t lock; +int size; +int cpu_to_idx[NR_CPUS ]; +struct array_item elements[NR_CPUS ]; +cpumask_var_t free_cpus; +}; + + +#ifdef CONFIG_SMP +int cpudl_find (struct cpudl *cp,struct task_struct *p, +struct cpumask *later_mask); +void cpudl_set (struct cpudl *cp,int cpu,u64 dl,int is_valid); +int cpudl_init (struct cpudl *cp); +void cpudl_cleanup (struct cpudl *cp); +#else +#define cpudl_set (cp, cpu, dl) do { } while (0) +#define cpudl_init () do { } while (0) +#endif /* CONFIG_SMP */ + +#endif /* _LINUX_CPUDL_H */
kernel/sched/deadline.c +14 -39
119 lines not on this page · raw message
kernel/sched/sched.h +2 -0
@@ -10,6 +10,7 @@#include <linux/slab.h> #include "cpupri.h" +#include "cpudeadline.h" #include "cpuacct.h" struct rq ;
@@ -503,6 +504,7 @@ struct root_domain {cpumask_var_t dlo_mask;atomic_t dlo_count;struct dl_bw dl_bw; +struct cpudl cpudl;/* * The "RT overload" flag: it gets set if a CPU has more than