Skip to contentSkip to conversation

web page on O(1) scheduler

Linux-ia64 Mike Galbraith 1 participant 1 message May 27, 2003 Scheduler

lore
Share & tools
lore
#0 lore raw
Quoted 19 lines · Mike Galbraith
Quoted 18 lines · Mike Galbraith
Quoted 16 lines · David Mosberger
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Wed, 21 May 2003 11:26:31 +0200, Mike Galbraith

<[email protected]> said:

Mike> The page mentions persistent starvation. My own explorations Mike> of this issue indicate that the primary source is always Mike> selecting the highest priority queue.

My working assumption is that the problem is a bug with the dynamic prioritization. The task receiving the signals calls sleep() after handling a signal and hence it's dynamic priority should end up higher than the priority of the task sending signals (since the sender never relinquishes the CPU voluntarily).

However, I haven't actually had time to look at the relevant code, so I may be missing something. If you understand the issue better, please explain to me why this isn't a dynamic priority issue.

Quoted 8 lines
Quoted 1 line

You're right, it looks like a corner case.

Out of curiosity, is someone hitting that with a real program?

-Mike

aside:
if so, I suppose nano-ticks may be needed....

Since I spent a bunch of time fumbling around with this problem, I may as well post one last time and put it to bed. I bet Ingo has a _lot_ better way to cure that problem, but...

Yes indeed, pedantic tracking of cpu usage does fix the problem. It also makes for some interesting changes in contest numbers (well, _I_ find them interesting;) If anyone wants to see the numbers, they're attached. If anyone wants to try the attached diff, it's attached too, have fun... the standard "you get to keep the pieces" lkml warrantee applies :) FWIW, it works just fine here, and the only time someone now manages to steal ticks (one) is (apparently) once in a long while when someone (whose initials appear to be IDE:) keeps interrupts disabled for too long. Nobody has yet managed to steal more than one tick.

The End,

-Mike

P.S. ok, so they're micro-ticks... what's a few orders of magnitude :)

include/linux/sched.h renamed from include/linux/sched.h.org +3 -1
@@ -328,7 +328,9 @@
 	prio_array_t *array;
 
 	unsigned long sleep_avg;
-	unsigned long last_run;
+	unsigned long long last_run;
+	unsigned int run_nsecs;
+	unsigned int sleep_nsecs;
 
 	unsigned long policy;
 	unsigned long cpus_allowed;
kernel/sched.c renamed from kernel/sched.c.org +79 -48

207 lines not on this page · raw message

arch/i386/kernel/timers/timer_tsc.c renamed from arch/i386/kernel/timers/timer_tsc.c.org +3 -2
@@ -102,12 +102,13 @@
 static unsigned long long monotonic_clock_tsc(void)
 {
 	unsigned long long last_offset, this_offset, base;
+	unsigned long flags;
 	
 	/* atomically read monotonic base & last_offset */
-	read_lock_irq(&monotonic_lock);
+	read_lock_irqsave(&monotonic_lock, flags);
 	last_offset = ((unsigned long long)last_tsc_high<<32)|last_tsc_low;
 	base = monotonic_base;
-	read_unlock_irq(&monotonic_lock);
+	read_unlock_irqrestore(&monotonic_lock, flags);
 
 	/* Read the Time Stamp Counter */
 	rdtscll(this_offset);
kernel/printk.c renamed from kernel/printk.c.org +2 -0
@@ -510,8 +510,10 @@
 	console_may_schedule = 0;
 	up(&console_sem);
 	spin_unlock_irqrestore(&logbuf_lock, flags);
+#if 0
 	if (wake_klogd && !oops_in_progress && waitqueue_active(&log_wait))
 		wake_up_interruptible(&log_wait);
+#endif
 }
 
 /** console_conditional_schedule - yield the CPU if required

no_load:
Kernel [runs] Time CPU% Loads LCPU% Ratio
2.5.69 1 153 94.8 0.0 0.0 1.00
2.5.69X 1 154 94.2 0.0 0.0 1.00
cacherun:
Kernel [runs] Time CPU% Loads LCPU% Ratio
2.5.69 1 146 98.6 0.0 0.0 0.95
2.5.69X 1 147 98.6 0.0 0.0 0.95
process_load:
Kernel [runs] Time CPU% Loads LCPU% Ratio
2.5.69 1 331 43.8 90.0 55.3 2.16
2.5.69X 1 344 41.9 94.0 57.0 2.23
ctar_load:
Kernel [runs] Time CPU% Loads LCPU% Ratio
2.5.69 1 190 77.9 0.0 0.0 1.24
2.5.69X 1 187 79.1 0.0 0.0 1.21
xtar_load:
Kernel [runs] Time CPU% Loads LCPU% Ratio
2.5.69 1 196 75.0 0.0 3.1 1.28
2.5.69X 1 198 74.7 0.0 3.5 1.29
io_load:
Kernel [runs] Time CPU% Loads LCPU% Ratio
2.5.69 1 437 34.6 69.1 15.1 2.86
2.5.69X 1 349 43.3 53.3 14.9 2.27
io_other:
Kernel [runs] Time CPU% Loads LCPU% Ratio
2.5.69 1 387 38.8 69.3 17.3 2.53
2.5.69X 1 436 34.9 63.4 14.0 2.83
read_load:
Kernel [runs] Time CPU% Loads LCPU% Ratio
2.5.69 1 221 67.0 9.4 3.6 1.44
2.5.69X 1 208 71.2 9.0 3.4 1.35
list_load:
Kernel [runs] Time CPU% Loads LCPU% Ratio
2.5.69 1 203 71.4 99.0 20.2 1.33
2.5.69X 1 204 71.1 100.0 20.1 1.32
mem_load:
Kernel [runs] Time CPU% Loads LCPU% Ratio
2.5.69 1 256 57.8 34.0 1.2 1.67
2.5.69X 1 244 60.2 36.0 1.2 1.58
dbench_load:
Kernel [runs] Time CPU% Loads LCPU% Ratio
2.5.69 1 517 28.8 5.0 35.6 3.38
2.5.69X 1 444 33.3 3.0 28.8 2.88
ab_load:
Kernel [runs] Time CPU% Loads LCPU% Ratio
2.5.69 1 300 48.3 46.0 21.7 1.96
2.5.69X 1 293 49.5 44.0 21.5 1.90