[patch] O(1) scheduler, 2.5.2-pre9-C1

[patch] O(1) scheduler, 2.5.2-pre9-C1

[Ingo Molnar]

i've uploaded an updated O(1) scheduler patch, against 2.5.2-pre9:

 	http://redhat.com/~mingo/O(1)-scheduler/sched-O1-2.5.2-C1.patch
 	http://redhat.com/~mingo/O(1)-scheduler/sched-O1-2.4.17-C1.patch

only minimal fixes were added to the code, the goal is to reach a stable
base.

Changelog:

 - fixed the mozilla crash, forgot to revert the ->prio value in
   setscheduler() which caused a wrong index ... (many thanks go to Pawel
   Kot for testing this out.)

 - fixed a load balancer bug that would get the runqueue count incorrectly
   if there is a RT running. With this fixed a 2-CPU system is completely
   usable even if a RT task is taking up 100% CPU time on one of the CPUs.

 - fix the sys_sched_yield export in ksyms.c (Davide Libenzi)

 - adds an RT event counter to optimize RT scheduling. (Davide, me)

	Ingo

Re: O(1) scheduler, 2.5.2-pre9-C1: some results

[Luc Van Oostenryck]

[-- Attachment #1: Type: text/plain, Size: 633 bytes --]

Ingo Molnar wrote:
> 
> i've uploaded an updated O(1) scheduler patch, against 2.5.2-pre9:
> 
>         http://redhat.com/~mingo/O(1)-scheduler/sched-O1-2.5.2-C1.patch
>         http://redhat.com/~mingo/O(1)-scheduler/sched-O1-2.4.17-C1.patch
> 
> only minimal fixes were added to the code, the goal is to reach a stable
> base.
> 

Here is some comparaison I have made between vanilla -pre9 and Ingo's C1
patch
using parts of lmbench and variing background process CPU bounded.

Result in short: seems rock solid and really O(1)!

For imformation: running on PentiumII/400MHz 196Mb RAM uniprocessor
(alas!).


-- 
Luc Van Oostenryck

[-- Attachment #2: result-ctxt-2.5.2-pre9 --]
[-- Type: application/octet-stream, Size: 1510 bytes --]

2.5.2-pre9
# latency process
Process fork+exit: 367.5333 microseconds
Process fork+exit: 367.2000 microseconds
Process fork+exit: 367.0000 microseconds
Process fork+exit: 367.8667 microseconds
Process fork+exit: 367.0000 microseconds
Process fork+execve: 1976.6667 microseconds
Process fork+execve: 1990.6667 microseconds
Process fork+execve: 1984.6667 microseconds
Process fork+execve: 1992.3333 microseconds
Process fork+execve: 1986.6667 microseconds
Process fork+/bin/sh -c: 7669.0000 microseconds
Process fork+/bin/sh -c: 7704.0000 microseconds
Process fork+/bin/sh -c: 7695.0000 microseconds
Process fork+/bin/sh -c: 7662.0000 microseconds
Process fork+/bin/sh -c: 7659.0000 microseconds

# latency select
Select on 10 fd's: 4.6042 microseconds
Select on 100 fd's: 20.1222 microseconds
Select on 250 fd's: 46.0167 microseconds
Select on 500 fd's: 89.3871 microseconds
Select on 1000 fd's: 176.3226 microseconds

Select on 10 tcp fd's: 5.9902 microseconds
Select on 100 tcp fd's: 33.7963 microseconds
Select on 250 tcp fd's: 86.6719 microseconds
Select on 500 tcp fd's: 155.5588 microseconds
Select on 1000 tcp fd's: 308.0556 microseconds

# latency context switching with 000 process
1.65
1.86
1.75

# latency context switching with 010 process
2.69
3.02
3.02

# latency context switching with 020 process
3.45
3.97
3.87

# latency context switching with 030 process
4.43
4.45
3.98

# latency context switching with 040 process
6.98
5.84
6.10

# latency context switching with 050 process
9.67
9.06
8.71

[-- Attachment #3: result-ctxt-2.5.2-pre9-O1_C1 --]
[-- Type: application/octet-stream, Size: 1516 bytes --]

2.5.2-pre9-O1_C1
# latency process
Process fork+exit: 368.1333 microseconds
Process fork+exit: 371.0667 microseconds
Process fork+exit: 368.2667 microseconds
Process fork+exit: 369.4000 microseconds
Process fork+exit: 368.2667 microseconds
Process fork+execve: 2002.3333 microseconds
Process fork+execve: 2016.3333 microseconds
Process fork+execve: 2024.0000 microseconds
Process fork+execve: 2043.6667 microseconds
Process fork+execve: 2014.0000 microseconds
Process fork+/bin/sh -c: 7810.0000 microseconds
Process fork+/bin/sh -c: 7857.0000 microseconds
Process fork+/bin/sh -c: 7734.0000 microseconds
Process fork+/bin/sh -c: 7725.0000 microseconds
Process fork+/bin/sh -c: 7714.0000 microseconds

# latency select
Select on 10 fd's: 4.6092 microseconds
Select on 100 fd's: 20.1741 microseconds
Select on 250 fd's: 46.2185 microseconds
Select on 500 fd's: 89.3871 microseconds
Select on 1000 fd's: 176.4194 microseconds

Select on 10 tcp fd's: 5.9978 microseconds
Select on 100 tcp fd's: 33.4939 microseconds
Select on 250 tcp fd's: 79.1143 microseconds
Select on 500 tcp fd's: 155.3529 microseconds
Select on 1000 tcp fd's: 307.9444 microseconds

# latency context switching with 000 process
1.84
1.83
1.84

# latency context switching with 010 process
1.61
1.59
1.60

# latency context switching with 020 process
1.64
1.60
1.55

# latency context switching with 030 process
1.58
1.58
1.60

# latency context switching with 040 process
1.55
1.58
1.56

# latency context switching with 050 process
1.69
1.62
1.63

[-- Attachment #4: bench --]
[-- Type: application/octet-stream, Size: 870 bytes --]

#!/bin/sh

DIR=/tmp/LMbench/bin/i686-pc-linux-gnu

function launch () {
  for i in $(seq 1 $1)
  do
	# spill is just a stupid process that eat CPU time
	./spill &
  done
}


function do_bench_ctx () {

  n=0
  max=50

  while [ $n -le $max ]
  do
	echo
	echo "# latency context switching with $(printf %03d $n) process"
  	for i in $(seq 0 2)
  	do
  		$DIR/lat_ctx -s 0 2 2>&1 | grep '^2' | cut -f 2 -d' '
  	done

	if [ $n -lt $max ]; then
  		launch 10
	fi
	n=$((n+10))
  done
  killall spill
}

function do_bench() {
uname -r

echo "# latency process"
for j in fork exec shell
do
	for i in $(seq 0 4)
	do
		$DIR/lat_proc $j
	done
done
echo

echo "# latency select"
for i in 10 100 250 500 1000; do $DIR/lat_select file $i; done
echo
for i in 10 100 250 500 1000; do $DIR/lat_select tcp $i; done

do_bench_ctx
}

do_bench 2>&1 | tee result-ctxt-$(uname -r)
echo Done