Skip to contentSkip to conversation

fix interactive task starvation

PATCH In review Mike Galbraith 4 participants 13 messages Mar 18, 2006

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 fix interactive task starvation

Greetings,

The patch below fixes a starvation problem that occurs when a stream of highly interactive tasks delay an array switch for extended periods despite EXPIRED_STARVING(rq) being true. AFAIKT, the only choice is to enqueue awakening tasks on the expired array in this case.

Without this patch, it can be nearly impossible to remotely login to a busy server, and interactive shell commands can starve for minutes.

This has not been verified by anyone. Comments?

-Mike

kernel/sched.c renamed from kernel/sched.c.org +20 -17
@@ -662,11 +662,30 @@
 }
 
 /*
+ * We place interactive tasks back into the active array, if possible.
+ *
+ * To guarantee that this does not starve expired tasks we ignore the
+ * interactivity of a task if the first expired task had to wait more
+ * than a 'reasonable' amount of time. This deadline timeout is
+ * load-dependent, as the frequency of array switched decreases with
+ * increasing number of running tasks. We also ignore the interactivity
+ * if a better static_prio task has expired:
+ */
+#define EXPIRED_STARVING(rq) \
+	((STARVATION_LIMIT && ((rq)->expired_timestamp && \
+		(jiffies - (rq)->expired_timestamp >= \
+			STARVATION_LIMIT * ((rq)->nr_running) + 1))) || \
+			((rq)->curr->static_prio > (rq)->best_expired_prio))
+
+/*
  * __activate_task - move a task to the runqueue.
  */
 static inline void __activate_task(task_t *p, runqueue_t *rq)
 {
-	enqueue_task(p, rq->active);
+	prio_array_t *array = rq->active;
+	if (unlikely(EXPIRED_STARVING(rq)))
+		array = rq->expired;
+	enqueue_task(p, array);
 	rq->nr_running++;
 }
 
@@ -2461,22 +2480,6 @@
 }
 
 /*
- * We place interactive tasks back into the active array, if possible.
- *
- * To guarantee that this does not starve expired tasks we ignore the
- * interactivity of a task if the first expired task had to wait more
- * than a 'reasonable' amount of time. This deadline timeout is
- * load-dependent, as the frequency of array switched decreases with
- * increasing number of running tasks. We also ignore the interactivity
- * if a better static_prio task has expired:
- */
-#define EXPIRED_STARVING(rq) \
-	((STARVATION_LIMIT && ((rq)->expired_timestamp && \
-		(jiffies - (rq)->expired_timestamp >= \
-			STARVATION_LIMIT * ((rq)->nr_running) + 1))) || \
-			((rq)->curr->static_prio > (rq)->best_expired_prio))
-
-/*
  * Account user cpu time to a process.
  * @p: the process that the cpu time gets accounted to
  * @hardirq_offset: the offset to subtract from hardirq_count()
#1 lore raw
Quoted 6 lines · Mike Galbraith

+#define EXPIRED_STARVING(rq) \
+ ((STARVATION_LIMIT && ((rq)->expired_timestamp && \
+ (jiffies - (rq)->expired_timestamp >= \
+ STARVATION_LIMIT * ((rq)->nr_running) + 1))) || \
+ ((rq)->curr->static_prio > (rq)->best_expired_prio))

Does this have to be a macro?

#2 lore raw
Quoted 10 lines · Andrew Morton
Quoted 6 lines · Mike Galbraith

+#define EXPIRED_STARVING(rq) \
+ ((STARVATION_LIMIT && ((rq)->expired_timestamp && \
+ (jiffies - (rq)->expired_timestamp >= \
+ STARVATION_LIMIT * ((rq)->nr_running) + 1))) || \
+ ((rq)->curr->static_prio > (rq)->best_expired_prio))

Does this have to be a macro?

I suppose not, now inlined.

-Mike

kernel/sched.c renamed from kernel/sched.c.org +27 -18
@@ -662,11 +662,36 @@
 }
 
 /*
+ * We place interactive tasks back into the active array, if possible.
+ *
+ * To guarantee that this does not starve expired tasks we ignore the
+ * interactivity of a task if the first expired task had to wait more
+ * than a 'reasonable' amount of time. This deadline timeout is
+ * load-dependent, as the frequency of array switched decreases with
+ * increasing number of running tasks. We also ignore the interactivity
+ * if a better static_prio task has expired:
+ */
+static inline int expired_starving(runqueue_t *rq)
+{
+	int limit = STARVATION_LIMIT * rq->nr_running, starving;
+
+	if (!limit || !rq->expired_timestamp)
+		return 0;
+	starving = jiffies - rq->expired_timestamp >= limit;
+	starving += rq->curr->static_prio > rq->best_expired_prio;
+
+	return starving;
+}
+
+/*
  * __activate_task - move a task to the runqueue.
  */
 static inline void __activate_task(task_t *p, runqueue_t *rq)
 {
-	enqueue_task(p, rq->active);
+	prio_array_t *array = rq->active;
+	if (unlikely(expired_starving(rq)))
+		array = rq->expired;
+	enqueue_task(p, array);
 	rq->nr_running++;
 }
 
@@ -2461,22 +2486,6 @@
 }
 
 /*
- * We place interactive tasks back into the active array, if possible.
- *
- * To guarantee that this does not starve expired tasks we ignore the
- * interactivity of a task if the first expired task had to wait more
- * than a 'reasonable' amount of time. This deadline timeout is
- * load-dependent, as the frequency of array switched decreases with
- * increasing number of running tasks. We also ignore the interactivity
- * if a better static_prio task has expired:
- */
-#define EXPIRED_STARVING(rq) \
-	((STARVATION_LIMIT && ((rq)->expired_timestamp && \
-		(jiffies - (rq)->expired_timestamp >= \
-			STARVATION_LIMIT * ((rq)->nr_running) + 1))) || \
-			((rq)->curr->static_prio > (rq)->best_expired_prio))
-
-/*
  * Account user cpu time to a process.
  * @p: the process that the cpu time gets accounted to
  * @hardirq_offset: the offset to subtract from hardirq_count()
@@ -2611,7 +2620,7 @@
 
 		if (!rq->expired_timestamp)
 			rq->expired_timestamp = jiffies;
-		if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
+		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;
#3 lore raw
Quoted 6 lines · Mike Galbraith
Quoted 3 lines

Does this have to be a macro?

I suppose not, now inlined.

It would be nice to uninline the function and then to modify it in a followup patch. That way, we get to see what changed, which is one of the reasons to not use megamacros (sorry).

kernel/sched.c line 684

Quoted 11 lines
kernel/sched.c renamed from kernel/sched.c.org +11 -0
+static inline int expired_starving(runqueue_t *rq)
+{
+	int limit = STARVATION_LIMIT * rq->nr_running, starving;
+
+	if (!limit || !rq->expired_timestamp)
+		return 0;
+	starving = jiffies - rq->expired_timestamp >= limit;
+	starving += rq->curr->static_prio > rq->best_expired_prio;
+
+	return starving;
+}

ick. Is that really what that macros does??

The function returns a boolean, so we should short-circuit the evaluation where possible.

static inline int expired_starving(runqueue_t *rq)

{
	int limit;

	/* Comment goes here */
	if (!rq->expired_timestamp)
		return 0;

	limit = STARVATION_LIMIT * rq->nr_running;

	/* Here too */
	if (!limit)
		return 0;

	/* And here */
	if (jiffies - rq->expired_timestamp >= limit)
		return 1;

	/* And here */
	if (rq->curr->static_prio > rq->best_expired_prio)
		return 1;

	/* And here */
	return 0;
}

This way

a) We get somewhere to put comments describing each step of the logic.

b) We get to select the order of the comparisons in decreasing (probability*expensiveness) order.

See how you're performing an unneeded multiplication if !rq->expired_timestamp?

c) See how the first test of `limit' comes after that multiplication? STARVATION_LIMIT is a constant (isn't it?) If so, we need only test rq->nr_running.

d) The next guy who comes along has to update the comments ;)

#4 lore raw
Quoted 11 lines · Andrew Morton
Quoted 6 lines · Mike Galbraith
Quoted 3 lines

Does this have to be a macro?

I suppose not, now inlined.

It would be nice to uninline the function and then to modify it in a followup patch. That way, we get to see what changed, which is one of the reasons to not use megamacros (sorry).

Ok, take 3 below, with updated main comment as well.

Quoted 2 lines

The function returns a boolean, so we should short-circuit the evaluation where possible.

Done.

-Mike

kernel/sched.c renamed from kernel/sched.c.org +47 -18
@@ -662,11 +662,56 @@
 }
 
 /*
+ * We place interactive tasks back into the active array, if possible.
+ *
+ * To guarantee that this does not starve expired tasks we ignore the
+ * interactivity of a task if the first expired task had to wait more
+ * than a 'reasonable' amount of time. This deadline timeout is
+ * load-dependent, as the frequency of array switched decreases with
+ * increasing number of running tasks. We also ignore the interactivity
+ * if a better static_prio task has expired, and switch periodically
+ * regardless, to ensure that highly interactive tasks do not starve
+ * the less fortunate for unreasonably long periods.
+ */
+static int expired_starving(runqueue_t *rq)
+{
+	int limit;
+
+	/*
+	 * Arrays were recently switched, all is well.
+	 */
+	if (!rq->expired_timestamp)
+		return 0;
+
+	limit = STARVATION_LIMIT * rq->nr_running;
+
+	/*
+	 * It's time to switch arrays.
+	 */
+	if (jiffies - rq->expired_timestamp >= limit)
+		return 1;
+
+	/*
+	 * There's a better selection in the expired array.
+	 */
+	if (rq->curr->static_prio > rq->best_expired_prio)
+		return 1;
+
+	/*
+	 * All is well.
+	 */
+	return 0;
+}
+
+/*
  * __activate_task - move a task to the runqueue.
  */
 static inline void __activate_task(task_t *p, runqueue_t *rq)
 {
-	enqueue_task(p, rq->active);
+	prio_array_t *array = rq->active;
+	if (unlikely(expired_starving(rq)))
+		array = rq->expired;
+	enqueue_task(p, array);
 	rq->nr_running++;
 }
 
@@ -2461,22 +2506,6 @@
 }
 
 /*
- * We place interactive tasks back into the active array, if possible.
- *
- * To guarantee that this does not starve expired tasks we ignore the
- * interactivity of a task if the first expired task had to wait more
- * than a 'reasonable' amount of time. This deadline timeout is
- * load-dependent, as the frequency of array switched decreases with
- * increasing number of running tasks. We also ignore the interactivity
- * if a better static_prio task has expired:
- */
-#define EXPIRED_STARVING(rq) \
-	((STARVATION_LIMIT && ((rq)->expired_timestamp && \
-		(jiffies - (rq)->expired_timestamp >= \
-			STARVATION_LIMIT * ((rq)->nr_running) + 1))) || \
-			((rq)->curr->static_prio > (rq)->best_expired_prio))
-
-/*
  * Account user cpu time to a process.
  * @p: the process that the cpu time gets accounted to
  * @hardirq_offset: the offset to subtract from hardirq_count()
@@ -2611,7 +2640,7 @@
 
 		if (!rq->expired_timestamp)
 			rq->expired_timestamp = jiffies;
-		if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
+		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;
#5 lore raw
Quoted 7 lines · Mike Galbraith
Quoted 5 lines · Andrew Morton
Quoted 4 lines · Mike Galbraith
Quoted 3 lines

Does this have to be a macro?

Quoted 9 lines
Quoted 6 lines
Quoted 2 lines

I suppose not, now inlined.

It would be nice to uninline the function and then to modify it in a followup patch. That way, we get to see what changed, which is one of the reasons to not use megamacros (sorry).

Ok, take 3 below, with updated main comment as well.

Thanks for doing that. Not really your job, but someone has to do these things ;)

Quoted 2 lines

You can't trick me that easily - I kept a copy of your changlog!

Quoted 5 lines

/*
+ * We place interactive tasks back into the active array, if possible.
+ *
+ * To guarantee that this does not starve expired tasks we ignore the
+ * interactivity of a task if the first expired task had to wait more

Quoted 8 lines

+ * than a 'reasonable' amount of time. This deadline timeout is
+ * load-dependent, as the frequency of array switched decreases with
+ * increasing number of running tasks. We also ignore the interactivity
+ * if a better static_prio task has expired, and switch periodically
+ * regardless, to ensure that highly interactive tasks do not starve
+ * the less fortunate for unreasonably long periods.
+ */
+static int expired_starving(runqueue_t *rq)

I'll make that inline..

kernel/sched.c line 686

Quoted 10 lines
kernel/sched.c renamed from kernel/sched.c.org +10 -0
+{
+	int limit;
+
+	/*
+	 * Arrays were recently switched, all is well.
+	 */
+	if (!rq->expired_timestamp)
+		return 0;
+
+	limit = STARVATION_LIMIT * rq->nr_running;

In the previous iteration you had, effectively,

	if (!limit)
		return 0;

in here. But it's now gone. Deliberate?

Quoted 17 lines
kernel/sched.c renamed from kernel/sched.c.org +17 -0
+	/*
+	 * It's time to switch arrays.
+	 */
+	if (jiffies - rq->expired_timestamp >= limit)
+		return 1;
+
+	/*
+	 * There's a better selection in the expired array.
+	 */
+	if (rq->curr->static_prio > rq->best_expired_prio)
+		return 1;
+
+	/*
+	 * All is well.
+	 */
+	return 0;
+}
#6 lore raw
Quoted 4 lines · Andrew Morton
Quoted 1 line

+static int expired_starving(runqueue_t *rq)

I'll make that inline..

Oops, I understood you to want that uninlined.

Quoted 13 lines

kernel/sched.c line 686

Quoted 10 lines
kernel/sched.c renamed from kernel/sched.c.org +10 -0
+{
+	int limit;
+
+	/*
+	 * Arrays were recently switched, all is well.
+	 */
+	if (!rq->expired_timestamp)
+		return 0;
+
+	limit = STARVATION_LIMIT * rq->nr_running;

In the previous iteration you had, effectively,

Quoted 4 lines
	if (!limit)
		return 0;

in here. But it's now gone. Deliberate?

Yes. I see no way for it to be zero. I think that was just a leftover.

-Mike

#7 lore raw
Quoted 9 lines · Mike Galbraith
Quoted 4 lines · Andrew Morton
Quoted 1 line

+static int expired_starving(runqueue_t *rq)

I'll make that inline..

Oops, I understood you to want that uninlined.

It has just one callsite. Modern gcc should inline it anyway, but older versions tend to need help.

Quoted 13 lines
Quoted 13 lines

kernel/sched.c line 686

Quoted 10 lines
kernel/sched.c renamed from kernel/sched.c.org +10 -0
+{
+	int limit;
+
+	/*
+	 * Arrays were recently switched, all is well.
+	 */
+	if (!rq->expired_timestamp)
+		return 0;
+
+	limit = STARVATION_LIMIT * rq->nr_running;

In the previous iteration you had, effectively,

Quoted 7 lines
Quoted 4 lines
	if (!limit)
		return 0;

in here. But it's now gone. Deliberate?

Yes. I see no way for it to be zero. I think that was just a leftover.

ok..

#9 lore raw
In reply to Mike Galbraith
Quoted 10 lines · Mike Galbraith

The patch below fixes a starvation problem that occurs when a stream of
highly interactive tasks delay an array switch for extended periods despite EXPIRED_STARVING(rq) being true. AFAIKT, the only choice is to enqueue awakening tasks on the expired array in this case.

Without this patch, it can be nearly impossible to remotely login to a busy server, and interactive shell commands can starve for minutes.

This has not been verified by anyone. Comments?

What does that question mean, btw?

-mm is looking like linux-2.6.38 at present so of course things got tangled up - sched-activate-sched-batch-expired.patch modifies __activate_task().

I ended up with the below.

Which do we think is more likely to be true - batch_task(p) or expired_starving(rq)? batch_task() looks cheaper to evaluate so I put that first. But I guess it's less likely to be true. hmm.

kernel/sched.c renamed from kernel/sched.c~sched-fix-interactive-task-starvation +45 -19
diff -puN kernel/sched.c~sched-fix-interactive-task-starvation kernel/sched.c
@@ -733,14 +733,56 @@ static inline void dec_nr_running(task_t
 }
 
 /*
+ * We place interactive tasks back into the active array, if possible.
+ *
+ * To guarantee that this does not starve expired tasks we ignore the
+ * interactivity of a task if the first expired task had to wait more
+ * than a 'reasonable' amount of time. This deadline timeout is
+ * load-dependent, as the frequency of array switched decreases with
+ * increasing number of running tasks. We also ignore the interactivity
+ * if a better static_prio task has expired, and switch periodically
+ * regardless, to ensure that highly interactive tasks do not starve
+ * the less fortunate for unreasonably long periods.
+ */
+static inline int expired_starving(runqueue_t *rq)
+{
+	int limit;
+
+	/*
+	 * Arrays were recently switched, all is well
+	 */
+	if (!rq->expired_timestamp)
+		return 0;
+
+	limit = STARVATION_LIMIT * rq->nr_running;
+
+	/*
+	 * It's time to switch arrays
+	 */
+	if (jiffies - rq->expired_timestamp >= limit)
+		return 1;
+
+	/*
+	 * There's a better selection in the expired array
+	 */
+	if (rq->curr->static_prio > rq->best_expired_prio)
+		return 1;
+
+	/*
+	 * All is well
+	 */
+	return 0;
+}
+
+/*
  * __activate_task - move a task to the runqueue.
  */
 static void __activate_task(task_t *p, runqueue_t *rq)
 {
 	prio_array_t *target = rq->active;
 
-	if (batch_task(p))
-		target = rq->expired;
+	if (unlikely(batch_task(p) || expired_starving(rq)))
+		target = rq->expired;
 	enqueue_task(p, target);
 	inc_nr_running(p, rq);
 }
@@ -2614,22 +2656,6 @@ unsigned long long current_sched_time(co
 }
 
 /*
- * We place interactive tasks back into the active array, if possible.
- *
- * To guarantee that this does not starve expired tasks we ignore the
- * interactivity of a task if the first expired task had to wait more
- * than a 'reasonable' amount of time. This deadline timeout is
- * load-dependent, as the frequency of array switched decreases with
- * increasing number of running tasks. We also ignore the interactivity
- * if a better static_prio task has expired:
- */
-#define EXPIRED_STARVING(rq) \
-	((STARVATION_LIMIT && ((rq)->expired_timestamp && \
-		(jiffies - (rq)->expired_timestamp >= \
-			STARVATION_LIMIT * ((rq)->nr_running) + 1))) || \
-			((rq)->curr->static_prio > (rq)->best_expired_prio))
-
-/*
  * Account user cpu time to a process.
  * @p: the process that the cpu time gets accounted to
  * @hardirq_offset: the offset to subtract from hardirq_count()
@@ -2764,7 +2790,7 @@ void scheduler_tick(void)
 
 		if (!rq->expired_timestamp)
 			rq->expired_timestamp = jiffies;
-		if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
+		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;

_

Acked-by
#10 lore raw
Quoted 6 lines · Andrew Morton
Quoted 5 lines · Mike Galbraith

The patch below fixes a starvation problem that occurs when a stream of
highly interactive tasks delay an array switch for extended periods despite EXPIRED_STARVING(rq) being true. AFAIKT, the only choice is to enqueue awakening tasks on the expired array in this case.

Quoted 6 lines
Quoted 4 lines

Without this patch, it can be nearly impossible to remotely login to a busy server, and interactive shell commands can starve for minutes.

This has not been verified by anyone. Comments?

What does that question mean, btw?

He's waiting for me to say I don't like it. But I do like it.

Quoted 8 lines

-mm is looking like linux-2.6.38 at present so of course things got tangled up - sched-activate-sched-batch-expired.patch modifies __activate_task().

I ended up with the below.

Which do we think is more likely to be true - batch_task(p) or expired_starving(rq)? batch_task() looks cheaper to evaluate so I put that first. But I guess it's less likely to be true. hmm.

Depends entirely on workload so it's impossible to predict in advance. Any order will do I suspect.

kernel/sched.c static inline void dec_nr_running(task_t · line 784

Quoted 1 line
kernel/sched.c renamed from kernel/sched.c~sched-fix-interactive-task-starvation +1 -0
+	if (unlikely(batch_task(p) || expired_starving(rq)))

Looks good to me.

Cheers,
Con

#11 lore raw
Quoted 7 lines · Con Kolivas
Quoted 6 lines · Andrew Morton
Quoted 5 lines · Mike Galbraith

The patch below fixes a starvation problem that occurs when a stream of
highly interactive tasks delay an array switch for extended periods despite EXPIRED_STARVING(rq) being true. AFAIKT, the only choice is to enqueue awakening tasks on the expired array in this case.

Quoted 8 lines
Quoted 6 lines
Quoted 4 lines

Without this patch, it can be nearly impossible to remotely login to a busy server, and interactive shell commands can starve for minutes.

This has not been verified by anyone. Comments?

What does that question mean, btw?

He's waiting for me to say I don't like it. But I do like it.

<chuckle>

No. Actually, I'm waiting for Ingo to just yawn and nuke the problem with a casual flick of his pinkie.

-Mike

#12 lore raw
In reply to Andrew Morton
Quoted 5 lines · Andrew Morton

I ended up with the below.

Which do we think is more likely to be true - batch_task(p) or expired_starving(rq)? batch_task() looks cheaper to evaluate so I put that first. But I guess it's less likely to be true. hmm.

it doesnt really matter - scheduler_tick() is a slowpath. Putting batch_task() first is ok.

Ingo