sched: Make Priority Inheritance POSIX compliant
cover sched: Make Priority Inheritance POSIX compliant
The current PI implementation violates POSIX scheduling semantics when a thread is deboosted. The following patch series adresses this.
Thanks and Kudos go to Mathias Weber and Carsten Emde for analysis, test cases and initial workaround patches.
Thanks,
tglx
PATCH 1/3 sched: Extend enqueue_task to allow head queueing
The ability of enqueueing a task to the head of a SCHED_FIFO priority list is required to fix some violations of POSIX scheduling policy.
Extend the related functions with a "head" argument.
--- include/linux/sched.h | 3 ++- kernel/sched.c | 13 +++++++------ kernel/sched_fair.c | 3 ++- kernel/sched_rt.c | 3 ++- 4 files changed, 13 insertions(+), 9 deletions(-)
include/linux/sched.h +2 -1
@@ -1075,7 +1075,8 @@ struct sched_domain;struct sched_class {const struct sched_class *next; -void (*enqueue_task) (struct rq *rq,struct task_struct *p,int wakeup); +void (*enqueue_task) (struct rq *rq,struct task_struct *p,int wakeup, +bool head);void (*dequeue_task) (struct rq *rq,struct task_struct *p,int sleep);void (*yield_task) (struct rq *rq);
kernel/sched.c +7 -6
@@ -1883,13 +1883,14 @@ static void update_avg(u64 *avg, u64 sam *avg += diff >>3 ; } -static void enqueue_task (struct rq *rq,struct task_struct *p,int wakeup) +static void +enqueue_task (struct rq *rq,struct task_struct *p,int wakeup,bool head) {if (wakeup) p->se.start_runtime = p->se.sum_exec_runtime;sched_info_queued (p); - p->sched_class->enqueue_task (rq, p, wakeup); + p->sched_class->enqueue_task (rq, p, wakeup, head); p->se.on_rq =1 ; }
@@ -1965,7 +1966,7 @@ static void activate_task(struct rq *rq,if (task_contributes_to_load (p)) rq->nr_uninterruptible--; -enqueue_task (rq, p, wakeup); +enqueue_task (rq, p, wakeup, false);inc_nr_running (rq); }
@@ -6065,7 +6066,7 @@ void rt_mutex_setprio(struct task_structif (running) p->sched_class->set_curr_task (rq);if (on_rq) { -enqueue_task (rq, p,0 ); +enqueue_task (rq, p,0 , false);check_class_changed (rq, p, prev_class, oldprio, running); }
@@ -6109,7 +6110,7 @@ void set_user_nice(struct task_struct *p delta = p->prio - old_prio;if (on_rq) { -enqueue_task (rq, p,0 ); +enqueue_task (rq, p,0 , false);/* * If the task increased its priority or is running and * lowered its priority, then reschedule its CPU:
@@ -10110,7 +10111,7 @@ void sched_move_task(struct task_structif (unlikely (running)) tsk->sched_class->set_curr_task (rq);if (on_rq) -enqueue_task (rq, tsk,0 ); +enqueue_task (rq, tsk,0 , false);task_rq_unlock (rq, &flags); }
kernel/sched_fair.c +2 -1
@@ -1053,7 +1053,8 @@ static inline void hrtick_update(struct* increased. Here we update the fair scheduling stats and * then put the task into the rbtree: */ -static void enqueue_task_fair (struct rq *rq,struct task_struct *p,int wakeup) +static void +enqueue_task_fair (struct rq *rq,struct task_struct *p,int wakeup,bool head) {struct cfs_rq *cfs_rq;struct sched_entity *se = &p->se;
kernel/sched_rt.c +2 -1
@@ -878,7 +878,8 @@ static void dequeue_rt_entity(struct sch/* * Adding/removing a task to/from a priority array: */ -static void enqueue_task_rt (struct rq *rq,struct task_struct *p,int wakeup) +static void +enqueue_task_rt (struct rq *rq,struct task_struct *p,int wakeup,bool head) {struct sched_rt_entity *rt_se = &p->rt;
[tip:sched/core] sched: Extend enqueue_task to allow head queueing
Commit-ID: ea87bb7853168434f4a82426dd1ea8421f9e604d Gitweb: http://git.kernel.org/tip/ea87bb7853168434f4a82426dd1ea8421f9e604d Author: Thomas Gleixner <[email protected]> AuthorDate: Wed, 20 Jan 2010 20:58:57 +0000 Committer: Thomas Gleixner <[email protected]> CommitDate: Fri, 22 Jan 2010 18:09:59 +0100
sched: Extend enqueue_task to allow head queueing
The ability of enqueueing a task to the head of a SCHED_FIFO priority list is required to fix some violations of POSIX scheduling policy.
Extend the related functions with a "head" argument.
LKML-Reference: <[email protected]>
--- include/linux/sched.h | 3 ++- kernel/sched.c | 13 +++++++------ kernel/sched_fair.c | 3 ++- kernel/sched_rt.c | 3 ++- 4 files changed, 13 insertions(+), 9 deletions(-)
include/linux/sched.h +2 -1
@@ -1067,7 +1067,8 @@ struct sched_domain;struct sched_class {const struct sched_class *next; -void (*enqueue_task) (struct rq *rq,struct task_struct *p,int wakeup); +void (*enqueue_task) (struct rq *rq,struct task_struct *p,int wakeup, +bool head);void (*dequeue_task) (struct rq *rq,struct task_struct *p,int sleep);void (*yield_task) (struct rq *rq);
kernel/sched.c +7 -6
@@ -1856,13 +1856,14 @@ static void update_avg(u64 *avg, u64 sample) *avg += diff >>3 ; } -static void enqueue_task (struct rq *rq,struct task_struct *p,int wakeup) +static void +enqueue_task (struct rq *rq,struct task_struct *p,int wakeup,bool head) {if (wakeup) p->se.start_runtime = p->se.sum_exec_runtime;sched_info_queued (p); - p->sched_class->enqueue_task (rq, p, wakeup); + p->sched_class->enqueue_task (rq, p, wakeup, head); p->se.on_rq =1 ; }
@@ -1892,7 +1893,7 @@ static void activate_task(struct rq *rq, struct task_struct *p, int wakeup)if (task_contributes_to_load (p)) rq->nr_uninterruptible--; -enqueue_task (rq, p, wakeup); +enqueue_task (rq, p, wakeup, false);inc_nr_running (rq); }
@@ -4236,7 +4237,7 @@ void rt_mutex_setprio(struct task_struct *p, int prio)if (running) p->sched_class->set_curr_task (rq);if (on_rq) { -enqueue_task (rq, p,0 ); +enqueue_task (rq, p,0 , false);check_class_changed (rq, p, prev_class, oldprio, running); }
@@ -4280,7 +4281,7 @@ void set_user_nice(struct task_struct *p, long nice) delta = p->prio - old_prio;if (on_rq) { -enqueue_task (rq, p,0 ); +enqueue_task (rq, p,0 , false);/* * If the task increased its priority or is running and * lowered its priority, then reschedule its CPU:
@@ -8230,7 +8231,7 @@ void sched_move_task(struct task_struct *tsk)if (unlikely (running)) tsk->sched_class->set_curr_task (rq);if (on_rq) -enqueue_task (rq, tsk,0 ); +enqueue_task (rq, tsk,0 , false);task_rq_unlock (rq, &flags); }
kernel/sched_fair.c +2 -1
@@ -1053,7 +1053,8 @@ static inline void hrtick_update(struct rq *rq)* increased. Here we update the fair scheduling stats and * then put the task into the rbtree: */ -static void enqueue_task_fair (struct rq *rq,struct task_struct *p,int wakeup) +static void +enqueue_task_fair (struct rq *rq,struct task_struct *p,int wakeup,bool head) {struct cfs_rq *cfs_rq;struct sched_entity *se = &p->se;
kernel/sched_rt.c +2 -1
@@ -878,7 +878,8 @@ static void dequeue_rt_entity(struct sched_rt_entity *rt_se)/* * Adding/removing a task to/from a priority array: */ -static void enqueue_task_rt (struct rq *rq,struct task_struct *p,int wakeup) +static void +enqueue_task_rt (struct rq *rq,struct task_struct *p,int wakeup,bool head) {struct sched_rt_entity *rt_se = &p->rt;
PATCH 2/3 sched: Implement head queueing for sched_rt
In reply to Thomas GleixnerThe ability of enqueueing a task to the head of a SCHED_FIFO priority list is required to fix some violations of POSIX scheduling policy.
Implement the functionality in sched_rt.
--- kernel/sched_rt.c | 19 +++++++++++-------- 1 file changed, 11 insertions(+), 8 deletions(-)
kernel/sched_rt.c +11 -8
@@ -194,7 +194,7 @@ static inline struct rt_rq *group_rt_rq(return rt_se->my_q; } -static void enqueue_rt_entity (struct sched_rt_entity *rt_se); +static void enqueue_rt_entity (struct sched_rt_entity *rt_se,bool head);static void dequeue_rt_entity (struct sched_rt_entity *rt_se);static void sched_rt_rq_enqueue (struct rt_rq *rt_rq)
@@ -204,7 +204,7 @@ static void sched_rt_rq_enqueue(struct rif (rt_rq->rt_nr_running) {if (rt_se && !on_rt_rq (rt_se)) -enqueue_rt_entity (rt_se); +enqueue_rt_entity (rt_se, false);if (rt_rq->highest_prio.curr < curr->prio)resched_task (curr); }
@@ -803,7 +803,7 @@ void dec_rt_tasks(struct sched_rt_entitydec_rt_group (rt_se, rt_rq); } -static void __enqueue_rt_entity (struct sched_rt_entity *rt_se) +static void __enqueue_rt_entity (struct sched_rt_entity *rt_se,bool head) {struct rt_rq *rt_rq =rt_rq_of_se (rt_se);struct rt_prio_array *array = &rt_rq->active;
@@ -819,7 +819,10 @@ static void __enqueue_rt_entity(struct sif (group_rq && (rt_rq_throttled (group_rq) || !group_rq->rt_nr_running))return ; -list_add_tail (&rt_se->run_list, queue); +if (head) +list_add (&rt_se->run_list, queue); +else +list_add_tail (&rt_se->run_list, queue);__set_bit (rt_se_prio (rt_se), array->bitmap);inc_rt_tasks (rt_se, rt_rq);
@@ -856,11 +859,11 @@ static void dequeue_rt_stack(struct sche } } -static void enqueue_rt_entity (struct sched_rt_entity *rt_se) +static void enqueue_rt_entity (struct sched_rt_entity *rt_se,bool head) {dequeue_rt_stack (rt_se);for_each_sched_rt_entity (rt_se) -__enqueue_rt_entity (rt_se); +__enqueue_rt_entity (rt_se, head); }static void dequeue_rt_entity (struct sched_rt_entity *rt_se)
@@ -871,7 +874,7 @@ static void dequeue_rt_entity(struct schstruct rt_rq *rt_rq =group_rt_rq (rt_se);if (rt_rq && rt_rq->rt_nr_running) -__enqueue_rt_entity (rt_se); +__enqueue_rt_entity (rt_se, false); } }
@@ -886,7 +889,7 @@ enqueue_task_rt(struct rq *rq, struct taif (wakeup) rt_se->timeout =0 ; -enqueue_rt_entity (rt_se); +enqueue_rt_entity (rt_se, head);if (!task_current (rq, p) && p->rt.nr_cpus_allowed >1 )enqueue_pushable_task (rq, p);
[tip:sched/core] sched: Implement head queueing for sched_rt
Commit-ID: 37dad3fce97f01e5149d69de0833d8452c0e862e Gitweb: http://git.kernel.org/tip/37dad3fce97f01e5149d69de0833d8452c0e862e Author: Thomas Gleixner <[email protected]> AuthorDate: Wed, 20 Jan 2010 20:59:01 +0000 Committer: Thomas Gleixner <[email protected]> CommitDate: Fri, 22 Jan 2010 18:09:59 +0100
sched: Implement head queueing for sched_rt
The ability of enqueueing a task to the head of a SCHED_FIFO priority list is required to fix some violations of POSIX scheduling policy.
Implement the functionality in sched_rt.
LKML-Reference: <[email protected]>
--- kernel/sched_rt.c | 19 +++++++++++-------- 1 files changed, 11 insertions(+), 8 deletions(-)
kernel/sched_rt.c +11 -8
@@ -194,7 +194,7 @@ static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)return rt_se->my_q; } -static void enqueue_rt_entity (struct sched_rt_entity *rt_se); +static void enqueue_rt_entity (struct sched_rt_entity *rt_se,bool head);static void dequeue_rt_entity (struct sched_rt_entity *rt_se);static void sched_rt_rq_enqueue (struct rt_rq *rt_rq)
@@ -204,7 +204,7 @@ static void sched_rt_rq_enqueue(struct rt_rq *rt_rq)if (rt_rq->rt_nr_running) {if (rt_se && !on_rt_rq (rt_se)) -enqueue_rt_entity (rt_se); +enqueue_rt_entity (rt_se, false);if (rt_rq->highest_prio.curr < curr->prio)resched_task (curr); }
@@ -803,7 +803,7 @@ void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)dec_rt_group (rt_se, rt_rq); } -static void __enqueue_rt_entity (struct sched_rt_entity *rt_se) +static void __enqueue_rt_entity (struct sched_rt_entity *rt_se,bool head) {struct rt_rq *rt_rq =rt_rq_of_se (rt_se);struct rt_prio_array *array = &rt_rq->active;
@@ -819,7 +819,10 @@ static void __enqueue_rt_entity(struct sched_rt_entity *rt_se)if (group_rq && (rt_rq_throttled (group_rq) || !group_rq->rt_nr_running))return ; -list_add_tail (&rt_se->run_list, queue); +if (head) +list_add (&rt_se->run_list, queue); +else +list_add_tail (&rt_se->run_list, queue);__set_bit (rt_se_prio (rt_se), array->bitmap);inc_rt_tasks (rt_se, rt_rq);
@@ -856,11 +859,11 @@ static void dequeue_rt_stack(struct sched_rt_entity *rt_se) } } -static void enqueue_rt_entity (struct sched_rt_entity *rt_se) +static void enqueue_rt_entity (struct sched_rt_entity *rt_se,bool head) {dequeue_rt_stack (rt_se);for_each_sched_rt_entity (rt_se) -__enqueue_rt_entity (rt_se); +__enqueue_rt_entity (rt_se, head); }static void dequeue_rt_entity (struct sched_rt_entity *rt_se)
@@ -871,7 +874,7 @@ static void dequeue_rt_entity(struct sched_rt_entity *rt_se)struct rt_rq *rt_rq =group_rt_rq (rt_se);if (rt_rq && rt_rq->rt_nr_running) -__enqueue_rt_entity (rt_se); +__enqueue_rt_entity (rt_se, false); } }
@@ -886,7 +889,7 @@ enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup, bool head)if (wakeup) rt_se->timeout =0 ; -enqueue_rt_entity (rt_se); +enqueue_rt_entity (rt_se, head);if (!task_current (rq, p) && p->rt.nr_cpus_allowed >1 )enqueue_pushable_task (rq, p);
PATCH 3/3 sched: Queue a deboosted task to the head of the RT priority queue
In reply to Thomas Gleixnerrtmutex_set_prio() is used to implement priority inheritance for futexes. When a task is deboosted it gets enqueued at the tail of its RT priority list. This is violating the POSIX scheduling semantics:
rt priority list X contains two runnable tasks A and B
task A runs with priority X and holds mutex M
task C preempts A and is blocked on mutex M
-> task A is boosted to priority of task C (Y)
task A unlocks the mutex M and deboosts itself
-> A is dequeued from rt priority list Y
-> A is enqueued to the tail of rt priority list Xtask C schedules away
task B runs
This is wrong as task A did not schedule away and therefor violates the POSIX scheduling semantics.
Enqueue the task to the head of the priority list instead.
--- kernel/sched.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched.c +1 -1
@@ -6066,7 +6066,7 @@ void rt_mutex_setprio(struct task_structif (running) p->sched_class->set_curr_task (rq);if (on_rq) { -enqueue_task (rq, p,0 , false); +enqueue_task (rq, p,0 , oldprio < prio);check_class_changed (rq, p, prev_class, oldprio, running); }
[tip:sched/core] sched: Queue a deboosted task to the head of the RT prio queue
Commit-ID: 60db48cacb9b253d5607a5ff206112a59cd09e34 Gitweb: http://git.kernel.org/tip/60db48cacb9b253d5607a5ff206112a59cd09e34 Author: Thomas Gleixner <[email protected]> AuthorDate: Wed, 20 Jan 2010 20:59:06 +0000 Committer: Thomas Gleixner <[email protected]> CommitDate: Fri, 22 Jan 2010 18:09:59 +0100
sched: Queue a deboosted task to the head of the RT prio queue
rtmutex_set_prio() is used to implement priority inheritance for futexes. When a task is deboosted it gets enqueued at the tail of its RT priority list. This is violating the POSIX scheduling semantics:
rt priority list X contains two runnable tasks A and B
task A runs with priority X and holds mutex M
task C preempts A and is blocked on mutex M
-> task A is boosted to priority of task C (Y)
task A unlocks the mutex M and deboosts itself
-> A is dequeued from rt priority list Y
-> A is enqueued to the tail of rt priority list Xtask C schedules away
task B runs
This is wrong as task A did not schedule away and therefor violates the POSIX scheduling semantics.
Enqueue the task to the head of the priority list instead.
LKML-Reference: <[email protected]>
--- kernel/sched.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)
kernel/sched.c +1 -1
@@ -4237,7 +4237,7 @@ void rt_mutex_setprio(struct task_struct *p, int prio)if (running) p->sched_class->set_curr_task (rq);if (on_rq) { -enqueue_task (rq, p,0 , false); +enqueue_task (rq, p,0 , oldprio < prio);check_class_changed (rq, p, prev_class, oldprio, running); }
Quoted 5 lines · Thomas Gleixner
The current PI implementation violates POSIX scheduling semantics when a thread is deboosted. The following patch series adresses this.
Thanks and Kudos go to Mathias Weber and Carsten Emde for analysis, test cases and initial workaround patches.
These look fine to me,
Quoted 6 lines · Peter Zijlstra
Quoted 5 lines · Thomas Gleixner
The current PI implementation violates POSIX scheduling semantics when a thread is deboosted. The following patch series adresses this.
Thanks and Kudos go to Mathias Weber and Carsten Emde for analysis, test cases and initial workaround patches.
Oh, that sounds good - would you like to share the test cases for our rt-test suite?
Quoted 11 lines
These look fine to me,
Acked-by Peter Zijlstra <[email protected]>--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Quoted 2 lines · Thomas Gleixner
The current PI implementation violates POSIX scheduling semantics when a thread is deboosted. The following patch series addresses this.
I can confirm that this patch series fixes the incorrect scheduling behavior as observed in our test case.
Thanks, Thomas!
Quoted 2 lines · Thomas Gleixner
The current PI implementation violates POSIX scheduling semantics when a thread is deboosted. The following patch series adresses this.
I did rerun the test case with this patches applied and I can confirm that this fixes the incorrect scheduling behavior in our test case.
Thanks, Thomas and Carsten for your help.