Re: [PATCH] sched: implement staircase deadline scheduler further improvements-1
On Thursday 19 April 2007 09:48, Con Kolivas wrote: > While the Staircase Deadline scheduler has not been completely killed off > and is still in -mm I would like to fix some outstanding issues that I've > found since it still serves for comparison with all the upcoming > schedulers. > > While still in -mm can we queue this on top please? > > A set of staircase-deadline v 0.41 patches will make their way into the > usual place for those willing to test it. > > http://ck.kolivas.org/patches/staircase-deadline/ Oops! Minor thinko! Here is a respin. Please apply this one instead. I better make a 0.42 heh. --- The prio_level was being inappropriately decreased if a higher priority task was still using previous timeslice. Fix that. Task expiration of higher priority tasks was not being taken into account with allocating priority slots. Check the expired best_static_prio level to facilitate that. Explicitly check all better static priority prio_levels when deciding on allocating slots for niced tasks. These changes improve behaviour in many ways. Signed-off-by: Con Kolivas <[EMAIL PROTECTED]> --- kernel/sched.c | 64 ++--- 1 file changed, 43 insertions(+), 21 deletions(-) Index: linux-2.6.21-rc7-sd/kernel/sched.c === --- linux-2.6.21-rc7-sd.orig/kernel/sched.c 2007-04-19 08:51:54.0 +1000 +++ linux-2.6.21-rc7-sd/kernel/sched.c 2007-04-19 12:03:29.0 +1000 @@ -145,6 +145,12 @@ struct prio_array { */ DECLARE_BITMAP(prio_bitmap, MAX_PRIO + 1); + /* +* The best static priority (of the dynamic priority tasks) queued +* this array. +*/ + int best_static_prio; + #ifdef CONFIG_SMP /* For convenience looks back at rq */ struct rq *rq; @@ -191,9 +197,9 @@ struct rq { /* * The current dynamic priority level this runqueue is at per static -* priority level, and the best static priority queued this rotation. +* priority level. */ - int prio_level[PRIO_RANGE], best_static_prio; + int prio_level[PRIO_RANGE]; /* How many times we have rotated the priority queue */ unsigned long prio_rotation; @@ -669,7 +675,7 @@ static void task_new_array(struct task_s } /* Find the first slot from the relevant prio_matrix entry */ -static inline int first_prio_slot(struct task_struct *p) +static int first_prio_slot(struct task_struct *p) { if (unlikely(p->policy == SCHED_BATCH)) return p->static_prio; @@ -682,11 +688,18 @@ static inline int first_prio_slot(struct * level. SCHED_BATCH tasks do not use the priority matrix. They only take * priority slots from their static_prio and above. */ -static inline int next_entitled_slot(struct task_struct *p, struct rq *rq) +static int next_entitled_slot(struct task_struct *p, struct rq *rq) { + int search_prio = MAX_RT_PRIO, uprio = USER_PRIO(p->static_prio); + struct prio_array *array = rq->active; DECLARE_BITMAP(tmp, PRIO_RANGE); - int search_prio, uprio = USER_PRIO(p->static_prio); + /* +* Go straight to expiration if there are higher priority tasks +* already expired. +*/ + if (p->static_prio > rq->expired->best_static_prio) + return MAX_PRIO; if (!rq->prio_level[uprio]) rq->prio_level[uprio] = MAX_RT_PRIO; /* @@ -694,15 +707,22 @@ static inline int next_entitled_slot(str * static_prio are acceptable, and only if it's not better than * a queued better static_prio's prio_level. */ - if (p->static_prio < rq->best_static_prio) { - search_prio = MAX_RT_PRIO; + if (p->static_prio < array->best_static_prio) { if (likely(p->policy != SCHED_BATCH)) - rq->best_static_prio = p->static_prio; - } else if (p->static_prio == rq->best_static_prio) + array->best_static_prio = p->static_prio; + } else if (p->static_prio == array->best_static_prio) { search_prio = rq->prio_level[uprio]; - else { - search_prio = max(rq->prio_level[uprio], - rq->prio_level[USER_PRIO(rq->best_static_prio)]); + } else { + int i; + + search_prio = rq->prio_level[uprio]; + /* A bound O(n) function, worst case n is 40 */ + for (i = array->best_static_prio; i <= p->static_prio ; i++) { + if (!rq->prio_level[USER_PRIO(i)]) + rq->prio_level[USER_PRIO(i)] = MAX_RT_PRIO; + search_prio = max(search_prio, + rq->prio_level[USER_PRIO(i)]); + } } if (unlikely(p->policy == SCHED_BATCH)) { search_prio = max(search_prio, p->stat
[PATCH] sched: implement staircase deadline scheduler further improvements
While the Staircase Deadline scheduler has not been completely killed off and is still in -mm I would like to fix some outstanding issues that I've found since it still serves for comparison with all the upcoming schedulers. While still in -mm can we queue this on top please? A set of staircase-deadline v 0.41 patches will make their way into the usual place for those willing to test it. http://ck.kolivas.org/patches/staircase-deadline/ --- The prio_level was being inappropriately decreased if a higher priority task was still using previous timeslice. Fix that. Task expiration of higher priority tasks was not being taken into account with allocating priority slots. Check the expired best_static_prio level to facilitate that. Explicitly check all better static priority prio_levels when deciding on allocating slots for niced tasks. These changes improve behaviour in many ways. Signed-off-by: Con Kolivas <[EMAIL PROTECTED]> --- kernel/sched.c | 61 ++--- 1 file changed, 41 insertions(+), 20 deletions(-) Index: linux-2.6.21-rc7-sd/kernel/sched.c === --- linux-2.6.21-rc7-sd.orig/kernel/sched.c 2007-04-19 08:51:54.0 +1000 +++ linux-2.6.21-rc7-sd/kernel/sched.c 2007-04-19 09:30:39.0 +1000 @@ -145,6 +145,12 @@ struct prio_array { */ DECLARE_BITMAP(prio_bitmap, MAX_PRIO + 1); + /* +* The best static priority (of the dynamic priority tasks) queued +* this array. +*/ + int best_static_prio; + #ifdef CONFIG_SMP /* For convenience looks back at rq */ struct rq *rq; @@ -191,9 +197,9 @@ struct rq { /* * The current dynamic priority level this runqueue is at per static -* priority level, and the best static priority queued this rotation. +* priority level. */ - int prio_level[PRIO_RANGE], best_static_prio; + int prio_level[PRIO_RANGE]; /* How many times we have rotated the priority queue */ unsigned long prio_rotation; @@ -669,7 +675,7 @@ static void task_new_array(struct task_s } /* Find the first slot from the relevant prio_matrix entry */ -static inline int first_prio_slot(struct task_struct *p) +static int first_prio_slot(struct task_struct *p) { if (unlikely(p->policy == SCHED_BATCH)) return p->static_prio; @@ -682,11 +688,18 @@ static inline int first_prio_slot(struct * level. SCHED_BATCH tasks do not use the priority matrix. They only take * priority slots from their static_prio and above. */ -static inline int next_entitled_slot(struct task_struct *p, struct rq *rq) +static int next_entitled_slot(struct task_struct *p, struct rq *rq) { + int search_prio = MAX_RT_PRIO, uprio = USER_PRIO(p->static_prio); + struct prio_array *array = rq->active; DECLARE_BITMAP(tmp, PRIO_RANGE); - int search_prio, uprio = USER_PRIO(p->static_prio); + /* +* Go straight to expiration if there are higher priority tasks +* already expired. +*/ + if (p->static_prio > rq->expired->best_static_prio) + return MAX_PRIO; if (!rq->prio_level[uprio]) rq->prio_level[uprio] = MAX_RT_PRIO; /* @@ -694,15 +707,21 @@ static inline int next_entitled_slot(str * static_prio are acceptable, and only if it's not better than * a queued better static_prio's prio_level. */ - if (p->static_prio < rq->best_static_prio) { - search_prio = MAX_RT_PRIO; + if (p->static_prio < array->best_static_prio) { if (likely(p->policy != SCHED_BATCH)) - rq->best_static_prio = p->static_prio; - } else if (p->static_prio == rq->best_static_prio) + array->best_static_prio = p->static_prio; + } else if (p->static_prio == array->best_static_prio) { search_prio = rq->prio_level[uprio]; - else { + } else { + int i; + + /* A bound O(n) function, worst case n is 40 */ + for (i = array->best_static_prio; i <= p->static_prio ; i++) { + if (!rq->prio_level[USER_PRIO(i)]) + rq->prio_level[USER_PRIO(i)] = MAX_RT_PRIO; search_prio = max(rq->prio_level[uprio], - rq->prio_level[USER_PRIO(rq->best_static_prio)]); + rq->prio_level[USER_PRIO(i)]); + } } if (unlikely(p->policy == SCHED_BATCH)) { search_prio = max(search_prio, p->static_prio); @@ -718,6 +737,8 @@ static void queue_expired(struct task_st { task_new_array(p, rq, rq->expired); p->prio = p->normal_prio = first_prio_slot(p); + if (p->static_prio < rq->expired->best_static_prio) + rq->expired->best_static_prio = p->static