Re: [rfc][patch] improved interactive starvation patch against 2.6.16

[Mike Galbraith <efault@gmx.de>]

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@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/