Re: [rfc][patch] improved interactive starvation patch against2.6.16

From: Mike Galbraith
Date: Thu Mar 30 2006 - 09:19:19 EST


On Thu, 2006-03-30 at 13:55 +0200, Willy Tarreau wrote:
> On Thu, Mar 30, 2006 at 12:19:57PM +0200, Mike Galbraith wrote:

> > For the one or two folks on the planet testing my anti-starvation
> > patches, I've attached an incremental to my 2.6.16 test release.
>
> Hmmm does not apply here :
>
> willy@wtap:linux-2.6.16-sched25$ cat /data/src/tmp/sched_*|patch -Nsp1
> willy@wtap:linux-2.6.16-sched25$ patch -p1 < /data/src/tmp/patch-2.6.16-sched-2.txt
> patching file kernel/sched.c
> Hunk #1 succeeded at 71 with fuzz 2 (offset -6 lines).
> Hunk #2 succeeded at 391 (offset 157 lines).
> Hunk #3 FAILED at 833.
> Hunk #4 FAILED at 2681.
> Hunk #5 succeeded at 2770 (offset 149 lines).
> Hunk #6 FAILED at 2806.
> Hunk #7 succeeded at 2866 (offset 162 lines).
> 3 out of 7 hunks FAILED -- saving rejects to file kernel/sched.c.rej
>
> However, it applies to plain 2.6.16 with sched_[1-6] applied (but with fuzz).
> Parts of the patches are already applied by your previous patches (eg: chunk1).
> I suspect that you accidentely rediffed sched.c against an intermediate
> working tree instead.
>
> For instance, this part is already provided by patch 4 :
> @@ -77,6 +77,21 @@
> #define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ))
> #define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ))
>
> +#if (BITS_PER_LONG < 64)
> +#define JIFFIES_TO_NS64(TIME) \
> .../...
>
> And this part overlaps with a previous chunk in patch 7 :
>
> - rq->expired_timestamp = jiffies;
> - if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
> + rq->expired_timestamp = now;
> + if (!TASK_INTERACTIVE(p) || expired_starving(rq)) {

You applied the wrong patch. The inlined one was against virgin 2.6.16,
for folks to comment on, and the attached was the incremental against
the 2.6.16 anti-starvation tree.

Ah, your mailer probably showed both as attached. Anyway, here's the
incremental again inlined.

(note to self: never include patches for two trees in same message)

-Mike

--- linux-2.6.16/kernel/sched.c-7.interactive_starvation 2006-03-27 06:11:01.000000000 +0200
+++ linux-2.6.16/kernel/sched.c 2006-03-30 10:50:46.000000000 +0200
@@ -371,7 +371,7 @@
*/
unsigned long nr_uninterruptible;

- unsigned long expired_timestamp;
+ unsigned long long expired_timestamp;
unsigned long long timestamp_last_tick;
task_t *curr, *idle;
struct mm_struct *prev_mm;
@@ -839,7 +839,7 @@
/*
* It's time to switch arrays.
*/
- if (jiffies - rq->expired_timestamp >= limit)
+ if (jiffies - NS64_TO_JIFFIES(rq->expired_timestamp) >= limit)
return 1;

/*
@@ -860,8 +860,12 @@
static inline void __activate_task(task_t *p, runqueue_t *rq)
{
prio_array_t *array = rq->active;
- if (unlikely(expired_starving(rq)))
+ if (unlikely(expired_starving(rq) && !rt_task(p) &&
+ p->last_ran > rq->expired_timestamp)) {
array = rq->expired;
+ if (p->prio < rq->best_expired_prio)
+ rq->best_expired_prio = p->prio;
+ }
enqueue_task(p, array);
rq->nr_running++;
}
@@ -2880,12 +2884,12 @@
return;
}

+ spin_lock(&rq->lock);
/* Task might have expired already, but not scheduled off yet */
if (p->array != rq->active) {
set_tsk_need_resched(p);
- goto out;
+ goto out_unlock;
}
- spin_lock(&rq->lock);
/*
* The task was running during this tick - update the
* time slice counter. Note: we do not update a thread's
@@ -2921,15 +2925,38 @@
p->prio = effective_prio(p);

if (!rq->expired_timestamp)
- rq->expired_timestamp = jiffies;
+ rq->expired_timestamp = now;
if (!TASK_INTERACTIVE(p) || expired_starving(rq)) {
enqueue_task(p, rq->expired);
- if (p->static_prio < rq->best_expired_prio)
- rq->best_expired_prio = p->static_prio;
+ if (p->prio < rq->best_expired_prio)
+ rq->best_expired_prio = p->prio;
} else
enqueue_task(p, rq->active);
} else {
/*
+ * If tasks in the expired array are starving, increase the
+ * speed of the array switch. If we do not, tasks which are
+ * awakened on the expired array may suffer severe latency
+ * due to cpu hogs using their full slice. We don't want to
+ * switch too fast however, because it may well be these very
+ * tasks which were causing starvation to begin with.
+ */
+ if (expired_starving(rq)) {
+ int limit = MIN_TIMESLICE + CURRENT_BONUS(p);
+ int runtime = now - p->timestamp;
+
+ runtime = NS_TO_JIFFIES(runtime);
+ if (runtime >= limit && p->time_slice >= limit) {
+
+ dequeue_task(p, rq->active);
+ enqueue_task(p, rq->expired);
+ set_tsk_need_resched(p);
+ if (p->prio < rq->best_expired_prio)
+ rq->best_expired_prio = p->prio;
+ }
+ }
+
+ /*
* Prevent a too long timeslice allowing a task to monopolize
* the CPU. We do this by splitting up the timeslice into
* smaller pieces.
@@ -2945,10 +2972,9 @@
* This only applies to tasks in the interactive
* delta range with at least TIMESLICE_GRANULARITY to requeue.
*/
- if (TASK_INTERACTIVE(p) && !((task_timeslice(p) -
+ else if (TASK_INTERACTIVE(p) && !((task_timeslice(p) -
p->time_slice) % TIMESLICE_GRANULARITY(p)) &&
- (p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
- (p->array == rq->active)) {
+ (p->time_slice >= TIMESLICE_GRANULARITY(p))) {

requeue_task(p, rq->active);
set_tsk_need_resched(p);


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/