Re: O(1) scheduler starvation

From: Felipe Alfaro Solana (
Date: Wed Jun 18 2003 - 09:22:53 EST

On Wed, 2003-06-18 at 14:04, Mike Galbraith wrote:
> At 09:53 AM 6/18/2003 +0200, Felipe Alfaro Solana wrote:
> >Hi!
> >
> >I've been poking around and found the following link on O(1) scheduler
> >starvation problems:
> >
> >
> >
> >The web page contains a small test program which supposedly is able to
> >make two processes starvate. However, I've been unable to reproduce what
> >is described in the above link. In fact, the CPU usage ratio ranges
> >between 60-40% or 70-30% in the worst cases.
> (you're talking about with my monotinic_clock() diff in your kernel right?)

Don't know exactly its name. wli posted to LKLM a few days ago. In a few
words, the patch creates

+inline void __scheduler_tick(runqueue_t *rq, task_t *p)


+#define SCHED_SECOND (1000000000 * SCHED_NANOSECOND)

Don't know if this is the patch you're talking about. It's not thud,

> If you examine the priorities vs cpu usage, therein lies a big fat bug.
> I think the fundamental problem is that you can only execute in series, but
> can sleep in parallel, which makes for more sleep time existing than all
> execution time combined. If you're running test-starve with my
> monotonic_clock() diff, you should notice that one task is at maximum
> priority and eating ~75% cpu, while the other is at minumum and getting the
> rest minus what top gets. In a sane universe, that should be
> impossible. In my current tree, this _is_ now impossible, but I haven't
> worked out some nasty kinks.

Exactly. This is more or less what was happening, roughly a 70-30
balance of CPU usage.

> >I'm running 2.5.72-mm1 with Mike Galbraith's scheduler patches and a
> >small patch I made myself to improve interactivity (mainly, to stop XMMS
> >from skipping by adjusting some scheduler parameters).
> Please show me your xmms hack, and show me how you make xmms skip without
> doing something that puts tons of stress on the cache. I built xmms here,
> and the only time the audio thread gets starved is when starting a new
> song. That's because of CHILD_PENALTY when starting a new copy of xmms
> while something of prio < 20 is hogging cpu (process_load <grrrr>). Once
> playing, it's rock solid here.

No, I wasn't talking about an XMMS hack. I was talking about changing
scheduler defaults, as shown in the following patch:

--- old/kernel/sched.c 2003-06-17 21:04:21.240902000 +0200
+++ new/kernel/sched.c 2003-06-17 20:58:54.840902000 +0200
@@ -66,14 +66,14 @@
  * they expire.
 #define MIN_TIMESLICE ( 10 * HZ / 1000)
-#define MAX_TIMESLICE (200 * HZ / 1000)
+#define MAX_TIMESLICE ( 20 * HZ / 1000)
 #define CHILD_PENALTY 50
 #define PARENT_PENALTY 100
 #define EXIT_WEIGHT 3
-#define PRIO_BONUS_RATIO 25
+#define PRIO_BONUS_RATIO 20
-#define MAX_SLEEP_AVG (10*HZ)
+#define MAX_SLEEP_AVG (2*HZ)
 #define NODE_THRESHOLD 125
 #define SCHED_SECOND (1000000000 * SCHED_NANOSECOND)

To make XMMS skip, just force the X server to do a lot of repainting,
for example, by dragging a big window slowly enough over another one
which requires a lot of painting (Evolution, for example, is a good
candidate as it requires a lot of CPU to repaint uncovered areas). It's
easy to reproduce just after launching XMMS. However, after a while, it
gets difficult to make XMMS to skip sound (it seems the scheduler
adjusts priorities well enough). This is on a PIII 700Mhz laptop with no
niced processes at all.

With your patch and my scheduler changes, I've been unable to make XMMS
skip audio, even when the X server is reniced to -20, or another CPU hog
is running.

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Mon Jun 23 2003 - 22:00:24 EST