* [patch 0/3] sched: Make Priority Inheritance POSIX compliant
@ 2010-01-20 20:58 Thomas Gleixner
2010-01-20 20:58 ` [patch 1/3] sched: Extend enqueue_task to allow head queueing Thomas Gleixner
` (5 more replies)
0 siblings, 6 replies; 11+ messages in thread
From: Thomas Gleixner @ 2010-01-20 20:58 UTC (permalink / raw
To: LKML; +Cc: Peter Zijlstra, Ingo Molnar, Carsten Emde, Mathias Weber
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* [patch 1/3] sched: Extend enqueue_task to allow head queueing
2010-01-20 20:58 [patch 0/3] sched: Make Priority Inheritance POSIX compliant Thomas Gleixner
@ 2010-01-20 20:58 ` Thomas Gleixner
2010-01-22 17:12 ` [tip:sched/core] " tip-bot for Thomas Gleixner
2010-01-20 20:59 ` [patch 2/3] sched: Implement head queueing for sched_rt Thomas Gleixner
` (4 subsequent siblings)
5 siblings, 1 reply; 11+ messages in thread
From: Thomas Gleixner @ 2010-01-20 20:58 UTC (permalink / raw
To: LKML; +Cc: Peter Zijlstra, Ingo Molnar, Carsten Emde, Mathias Weber
[-- Attachment #1: sched-extend-enqueue-task-to-allow-head-queueing.patch --]
[-- Type: text/plain, Size: 3812 bytes --]
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.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
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(-)
Index: linux-2.6-tip/include/linux/sched.h
===================================================================
--- linux-2.6-tip.orig/include/linux/sched.h
+++ linux-2.6-tip/include/linux/sched.h
@@ -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);
Index: linux-2.6-tip/kernel/sched.c
===================================================================
--- linux-2.6-tip.orig/kernel/sched.c
+++ linux-2.6-tip/kernel/sched.c
@@ -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_struct
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);
}
@@ -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_struct
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);
}
Index: linux-2.6-tip/kernel/sched_fair.c
===================================================================
--- linux-2.6-tip.orig/kernel/sched_fair.c
+++ linux-2.6-tip/kernel/sched_fair.c
@@ -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;
Index: linux-2.6-tip/kernel/sched_rt.c
===================================================================
--- linux-2.6-tip.orig/kernel/sched_rt.c
+++ linux-2.6-tip/kernel/sched_rt.c
@@ -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;
^ permalink raw reply [flat|nested] 11+ messages in thread
* [patch 2/3] sched: Implement head queueing for sched_rt
2010-01-20 20:58 [patch 0/3] sched: Make Priority Inheritance POSIX compliant Thomas Gleixner
2010-01-20 20:58 ` [patch 1/3] sched: Extend enqueue_task to allow head queueing Thomas Gleixner
@ 2010-01-20 20:59 ` Thomas Gleixner
2010-01-22 17:12 ` [tip:sched/core] " tip-bot for Thomas Gleixner
2010-01-20 20:59 ` [patch 3/3] sched: Queue a deboosted task to the head of the RT priority queue Thomas Gleixner
` (3 subsequent siblings)
5 siblings, 1 reply; 11+ messages in thread
From: Thomas Gleixner @ 2010-01-20 20:59 UTC (permalink / raw
To: LKML; +Cc: Peter Zijlstra, Ingo Molnar, Carsten Emde, Mathias Weber
[-- Attachment #1: sched-implement-head-queueing-for-rt.patch --]
[-- Type: text/plain, Size: 2719 bytes --]
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.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
kernel/sched_rt.c | 19 +++++++++++--------
1 file changed, 11 insertions(+), 8 deletions(-)
Index: linux-2.6-tip/kernel/sched_rt.c
===================================================================
--- linux-2.6-tip.orig/kernel/sched_rt.c
+++ linux-2.6-tip/kernel/sched_rt.c
@@ -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 r
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
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 s
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 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 sch
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 ta
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);
^ permalink raw reply [flat|nested] 11+ messages in thread
* [patch 3/3] sched: Queue a deboosted task to the head of the RT priority queue
2010-01-20 20:58 [patch 0/3] sched: Make Priority Inheritance POSIX compliant Thomas Gleixner
2010-01-20 20:58 ` [patch 1/3] sched: Extend enqueue_task to allow head queueing Thomas Gleixner
2010-01-20 20:59 ` [patch 2/3] sched: Implement head queueing for sched_rt Thomas Gleixner
@ 2010-01-20 20:59 ` Thomas Gleixner
2010-01-22 17:13 ` [tip:sched/core] sched: Queue a deboosted task to the head of the RT prio queue tip-bot for Thomas Gleixner
2010-01-20 21:06 ` [patch 0/3] sched: Make Priority Inheritance POSIX compliant Peter Zijlstra
` (2 subsequent siblings)
5 siblings, 1 reply; 11+ messages in thread
From: Thomas Gleixner @ 2010-01-20 20:59 UTC (permalink / raw
To: LKML; +Cc: Peter Zijlstra, Ingo Molnar, Carsten Emde, Mathias Weber
[-- Attachment #1: rtmutex-set-prio-fix-deboost-enqueueing.patch --]
[-- Type: text/plain, Size: 1436 bytes --]
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 X
task 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.
Reported-by: Mathias Weber <mathias.weber.mw1@roche.com>
Reported-by: Carsten Emde <cbe@osadl.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
kernel/sched.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
Index: linux-2.6-tip/kernel/sched.c
===================================================================
--- linux-2.6-tip.orig/kernel/sched.c
+++ linux-2.6-tip/kernel/sched.c
@@ -6066,7 +6066,7 @@ void rt_mutex_setprio(struct task_struct
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);
}
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [patch 0/3] sched: Make Priority Inheritance POSIX compliant
2010-01-20 20:58 [patch 0/3] sched: Make Priority Inheritance POSIX compliant Thomas Gleixner
` (2 preceding siblings ...)
2010-01-20 20:59 ` [patch 3/3] sched: Queue a deboosted task to the head of the RT priority queue Thomas Gleixner
@ 2010-01-20 21:06 ` Peter Zijlstra
2010-01-20 21:59 ` John Kacur
2010-01-21 0:52 ` Carsten Emde
2010-01-21 16:16 ` Weber, Mathias
5 siblings, 1 reply; 11+ messages in thread
From: Peter Zijlstra @ 2010-01-20 21:06 UTC (permalink / raw
To: Thomas Gleixner; +Cc: LKML, Ingo Molnar, Carsten Emde, Mathias Weber
On Wed, 2010-01-20 at 20:58 +0000, Thomas Gleixner wrote:
> 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,
Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [patch 0/3] sched: Make Priority Inheritance POSIX compliant
2010-01-20 21:06 ` [patch 0/3] sched: Make Priority Inheritance POSIX compliant Peter Zijlstra
@ 2010-01-20 21:59 ` John Kacur
0 siblings, 0 replies; 11+ messages in thread
From: John Kacur @ 2010-01-20 21:59 UTC (permalink / raw
To: Peter Zijlstra
Cc: Thomas Gleixner, LKML, Ingo Molnar, Carsten Emde, Mathias Weber,
Clark Williams
On Wed, Jan 20, 2010 at 10:06 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Wed, 2010-01-20 at 20:58 +0000, Thomas Gleixner wrote:
>> 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?
>
> These look fine to me,
>
> Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
>
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [patch 0/3] sched: Make Priority Inheritance POSIX compliant
2010-01-20 20:58 [patch 0/3] sched: Make Priority Inheritance POSIX compliant Thomas Gleixner
` (3 preceding siblings ...)
2010-01-20 21:06 ` [patch 0/3] sched: Make Priority Inheritance POSIX compliant Peter Zijlstra
@ 2010-01-21 0:52 ` Carsten Emde
2010-01-21 16:16 ` Weber, Mathias
5 siblings, 0 replies; 11+ messages in thread
From: Carsten Emde @ 2010-01-21 0:52 UTC (permalink / raw
To: Thomas Gleixner; +Cc: LKML, Peter Zijlstra, Ingo Molnar, Mathias Weber
On 01/20/2010 09:58 PM, Thomas Gleixner wrote:
> 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!
Tested-by: Carsten Emde <cbe@osadl.org>
^ permalink raw reply [flat|nested] 11+ messages in thread
* RE: [patch 0/3] sched: Make Priority Inheritance POSIX compliant
2010-01-20 20:58 [patch 0/3] sched: Make Priority Inheritance POSIX compliant Thomas Gleixner
` (4 preceding siblings ...)
2010-01-21 0:52 ` Carsten Emde
@ 2010-01-21 16:16 ` Weber, Mathias
5 siblings, 0 replies; 11+ messages in thread
From: Weber, Mathias @ 2010-01-21 16:16 UTC (permalink / raw
To: Thomas Gleixner; +Cc: LKML, Peter Zijlstra, Ingo Molnar, Carsten Emde
On 01/20/2010 09:58 PM, Thomas Gleixner wrote:
>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.
Tested-by: Mathias Weber <mathias.weber.mw1@oche.com>
^ permalink raw reply [flat|nested] 11+ messages in thread
* [tip:sched/core] sched: Extend enqueue_task to allow head queueing
2010-01-20 20:58 ` [patch 1/3] sched: Extend enqueue_task to allow head queueing Thomas Gleixner
@ 2010-01-22 17:12 ` tip-bot for Thomas Gleixner
0 siblings, 0 replies; 11+ messages in thread
From: tip-bot for Thomas Gleixner @ 2010-01-22 17:12 UTC (permalink / raw
To: linux-tip-commits
Cc: linux-kernel, hpa, mingo, peterz, mathias.weber.mw1, cbe, tglx
Commit-ID: ea87bb7853168434f4a82426dd1ea8421f9e604d
Gitweb: http://git.kernel.org/tip/ea87bb7853168434f4a82426dd1ea8421f9e604d
Author: Thomas Gleixner <tglx@linutronix.de>
AuthorDate: Wed, 20 Jan 2010 20:58:57 +0000
Committer: Thomas Gleixner <tglx@linutronix.de>
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.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Acked-by: Peter Zijlstra <peterz@infradead.org>
Tested-by: Carsten Emde <cbe@osadl.org>
Tested-by: Mathias Weber <mathias.weber.mw1@roche.com>
LKML-Reference: <20100120171629.734886007@linutronix.de>
---
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(-)
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 8b07973..b35c0c7 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -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);
diff --git a/kernel/sched.c b/kernel/sched.c
index 41e76d3..f47560f 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -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);
}
diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index 22231cc..0e7a7af 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -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;
diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
index 502bb61..38076da 100644
--- a/kernel/sched_rt.c
+++ b/kernel/sched_rt.c
@@ -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;
^ permalink raw reply related [flat|nested] 11+ messages in thread
* [tip:sched/core] sched: Implement head queueing for sched_rt
2010-01-20 20:59 ` [patch 2/3] sched: Implement head queueing for sched_rt Thomas Gleixner
@ 2010-01-22 17:12 ` tip-bot for Thomas Gleixner
0 siblings, 0 replies; 11+ messages in thread
From: tip-bot for Thomas Gleixner @ 2010-01-22 17:12 UTC (permalink / raw
To: linux-tip-commits
Cc: linux-kernel, hpa, mingo, peterz, mathias.weber.mw1, cbe, tglx
Commit-ID: 37dad3fce97f01e5149d69de0833d8452c0e862e
Gitweb: http://git.kernel.org/tip/37dad3fce97f01e5149d69de0833d8452c0e862e
Author: Thomas Gleixner <tglx@linutronix.de>
AuthorDate: Wed, 20 Jan 2010 20:59:01 +0000
Committer: Thomas Gleixner <tglx@linutronix.de>
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.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Acked-by: Peter Zijlstra <peterz@infradead.org>
Tested-by: Carsten Emde <cbe@osadl.org>
Tested-by: Mathias Weber <mathias.weber.mw1@roche.com>
LKML-Reference: <20100120171629.772169931@linutronix.de>
---
kernel/sched_rt.c | 19 +++++++++++--------
1 files changed, 11 insertions(+), 8 deletions(-)
diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
index 38076da..ca49ceb 100644
--- a/kernel/sched_rt.c
+++ b/kernel/sched_rt.c
@@ -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);
^ permalink raw reply related [flat|nested] 11+ messages in thread
* [tip:sched/core] sched: Queue a deboosted task to the head of the RT prio queue
2010-01-20 20:59 ` [patch 3/3] sched: Queue a deboosted task to the head of the RT priority queue Thomas Gleixner
@ 2010-01-22 17:13 ` tip-bot for Thomas Gleixner
0 siblings, 0 replies; 11+ messages in thread
From: tip-bot for Thomas Gleixner @ 2010-01-22 17:13 UTC (permalink / raw
To: linux-tip-commits
Cc: linux-kernel, hpa, mingo, peterz, cbe, mathias.weber.mw1, tglx
Commit-ID: 60db48cacb9b253d5607a5ff206112a59cd09e34
Gitweb: http://git.kernel.org/tip/60db48cacb9b253d5607a5ff206112a59cd09e34
Author: Thomas Gleixner <tglx@linutronix.de>
AuthorDate: Wed, 20 Jan 2010 20:59:06 +0000
Committer: Thomas Gleixner <tglx@linutronix.de>
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 X
task 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.
Reported-by: Mathias Weber <mathias.weber.mw1@roche.com>
Reported-by: Carsten Emde <cbe@osadl.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Acked-by: Peter Zijlstra <peterz@infradead.org>
Tested-by: Carsten Emde <cbe@osadl.org>
Tested-by: Mathias Weber <mathias.weber.mw1@roche.com>
LKML-Reference: <20100120171629.809074113@linutronix.de>
---
kernel/sched.c | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/kernel/sched.c b/kernel/sched.c
index f47560f..a56ead4 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -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);
}
^ permalink raw reply related [flat|nested] 11+ messages in thread
end of thread, other threads:[~2010-01-22 17:13 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2010-01-20 20:58 [patch 0/3] sched: Make Priority Inheritance POSIX compliant Thomas Gleixner
2010-01-20 20:58 ` [patch 1/3] sched: Extend enqueue_task to allow head queueing Thomas Gleixner
2010-01-22 17:12 ` [tip:sched/core] " tip-bot for Thomas Gleixner
2010-01-20 20:59 ` [patch 2/3] sched: Implement head queueing for sched_rt Thomas Gleixner
2010-01-22 17:12 ` [tip:sched/core] " tip-bot for Thomas Gleixner
2010-01-20 20:59 ` [patch 3/3] sched: Queue a deboosted task to the head of the RT priority queue Thomas Gleixner
2010-01-22 17:13 ` [tip:sched/core] sched: Queue a deboosted task to the head of the RT prio queue tip-bot for Thomas Gleixner
2010-01-20 21:06 ` [patch 0/3] sched: Make Priority Inheritance POSIX compliant Peter Zijlstra
2010-01-20 21:59 ` John Kacur
2010-01-21 0:52 ` Carsten Emde
2010-01-21 16:16 ` Weber, Mathias
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).