Tech Insider					     Technology and Trends


			      USENET Archives

From: Phillip Ezolt <ez...@perf.zko.dec.com>
Subject: Overscheduling DOES happen with high web server load.
Date: 1999/05/05
Message-ID: <fa.lrbmocv.13gphs@ifi.uio.no>
X-Deja-AN: 474518895
Original-Date: Wed, 5 May 1999 14:54:40 -0400 (EDT)
Sender: owner-linux-ker...@vger.rutgers.edu
Original-Message-ID: <Pine.OSF.3.96.990505144826.13001A-100000@perf.zko.dec.com>
To: linux-ker...@vger.rutgers.edu
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Orcpt: rfc822;linux-kernel-outgoing-dig
Organization: Internet mailing list
MIME-Version: 1.0
Newsgroups: fa.linux.kernel
X-Loop: majord...@vger.rutgers.edu

Hi all,

In doing some performance work with SPECWeb96 on ALpha/Linux with apache,
it looks like "schedule" is the main bottleneck. 

(Kernel v2.2.5, Apache 1.3.4, egcs-1.1.1, iprobe-4.1)

When running a SPECWeb96 strobe run on Alpha/linux, I found that when the
CPU is pegged, 18% of the time is spent in the scheduler.

Using Iprobe, I got the following function breakdown: (only functions >1%
are shown)

Begin            End                                    Sample Image Total
Address          Address          Name                   Count   Pct   Pct
-------          -------          ----                   -----   ---   ---
0000000000000000-00000000000029FC /usr/bin/httpd        127463        18.5 
00000001200419A0-000000012004339F   ap_vformatter        15061  11.8   2.2 
FFFFFC0000300000-00000000FFFFFFFF vmlinux               482385        70.1 
FFFFFC00003103E0-FFFFFC000031045F   entInt                7848   1.6   1.1
FFFFFC0000315E40-FFFFFC0000315F7F   do_entInt            48487  10.1   7.0
FFFFFC0000327A40-FFFFFC0000327D7F   schedule            124815  25.9  18.1
FFFFFC000033FAA0-FFFFFC000033FCDF   kfree                 7876   1.6   1.1
FFFFFC00003A9960-FFFFFC00003A9EBF   ip_queue_xmit         8616   1.8   1.3
FFFFFC00003B9440-FFFFFC00003B983F   tcp_v4_rcv           11131   2.3   1.6
FFFFFC0000441CA0-FFFFFC000044207F   do_csum_partial      43112   8.9   6.3 
                                    _copy_from_user 

I can't pin it down to the exact source line, but the cycles are spent in
close proximity of one another. 

FFFFFC0000327A40 schedule vmlinux
FFFFFC0000327C1C   01DC      2160 (  1.7) *
FFFFFC0000327C34   01F4     28515 ( 22.8) **********************
FFFFFC0000327C60   0220      1547 (  1.2) *
FFFFFC0000327C64   0224     26432 ( 21.2) *********************
FFFFFC0000327C74   0234     36470 ( 29.2) *****************************
FFFFFC0000327C9C   025C     24858 ( 19.9) *******************       

(For those interested, I have the disassembled code. )

Apache has a fairly even cycle distribution, but in the kernel, 'schedule' 
really sticks out as the CPU burner. 

I think that the linear search for next runnable process is where time is
being spent. 

As an independent test, I ran vmstat while SPECWeb was running.

The leftmost column is the number of processes waiting to run.  These number
are above the 3 or 4 that are normally quoted. 


 procs                  memory    swap        io    system         cpu
 r b w  swpd  free  buff cache  si  so   bi   bo   in   cs  us  sy  id
 0 21 0   208  5968  5240 165712   0   0 4001  303 10263 6519  31  66   4
26 27 1   208  6056  5240 165848   0   0 2984   96 5623 3440  29  60  11
 0 15 0   208  5096  5288 166384   0   0 4543  260 10850 7346  32  66   3
 0 17 0   208  6928  5248 164936   0   0 5741  309 13129 8052  32  65   3
37 19 1   208  5664  5248 166144   0   0 2502  142 6837 3896  33  63   5
 0 14 0   208  5984  5240 165656   0   0 3894  376 12432 7276  32  65   3
 0 19 1   208  4872  5272 166248   0   0 2247  124 7641 4514  32  64   4
 0 17 0   208  5248  5264 166336   0   0 4229  288 8786 5144  31  67   2
56 16 1   208  6512  5248 165592   0   0 2159  205 8098 4641  32  62   6
94 18 1   208  5920  5248 165896   0   0 1745  191 5288 2952  32  60   7
71 14 1   208  5920  5256 165872   0   0 2063  160 6493 3729  30  62   8
 0 25 1   208  5032  5256 166544   0   0 3008  112 5668 3612  31  60   9
62 22 1   208  5496  5256 165560   0   0 2512  109 5661 3392  28  62  11
43 22 1   208  4536  5272 166112   0   0 3003  202 7198 4813  30  63   7
 0 26 1   208  4800  5288 166256   0   0 2407   93 5666 3563  29  60  11
32 17 1   208  5984  5296 165632   0   0 2046  329 7296 4305  31  62   6
23 7 1   208  6744  5248 164904   0   0 1739  284 9496 5923  33  65   2
14 18 1   208  5128  5272 166416   0   0 3755  322 9663 6203  32  65   3
 0 22 1   208  4256  5304 167288   0   0 2593  156 5678 3219  31  60   9
44 20 1   208  3688  5264 167184   0   0 3010  149 7277 4398  31  62   7
29 24 1   208  5232  5264 166248   0   0 1954  104 5687 3496  31  61   9
26 23 1   208  5688  5256 165568   0   0 3029  169 7124 4473  30  60  10
 0 18 1   208  5576  5256 165656   0   0 3395  270 8464 5702  30  63   7      

It looks like the run queue is much longer than expected. 

I imagine this problem is compounded by the number of times "schedule" is
called. 

On a webserver that does not have all of the web pages in memory, an httpd
processes life is the following:

1. Wake up for a request from the network.
2. Figure out what web page to load.
3. Ask the disk for it.
4. Sleep (Schedule()) until the page is ready.

This means that schedule will be called alot. In addition a process will wake 
and sleep in a time much shorter than its allotted time slice. 

Each time we schedule, we have to walk through the entire run queue. This will
cause less requests to be serviced.  This will cause more processes to be stuck
on the run queue,  this will make the walk down the runqueue even longer...

Bottom line, under a heavy web load, the linux kernel seems to spend and
unnecessary amount of time scheduling processes.

Is it necessary to calculate the goodness of every process at every schedule?
Can't we make the goodnesses static?  Monkeying with the scheduler is big 
business, and I realize that this will not be a v2.2 issue, but what about 
v2.3? 

--Phil

Digital/Compaq:                     HPSD/Benchmark Performance Engineering
Phillip.Ez...@compaq.com                            ez...@perf.zko.dec.com

ps. <shameless plug> For those interested in more detail there will be a
WIP paper describing this work presented at Linux Expo. </shameless plug>


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

From: Richard Gooch <rgo...@atnf.csiro.au>
Subject: Re: Overscheduling DOES happen with high web server load.
Date: 1999/05/06
Message-ID: <fa.i397bcv.k5i7ak@ifi.uio.no>#1/1
X-Deja-AN: 474602020
Original-Date: Thu, 6 May 1999 10:42:18 +1000
Sender: owner-linux-ker...@vger.rutgers.edu
Original-Message-Id: <199905060042.KAA19778@vindaloo.atnf.CSIRO.AU>
References: <fa.lrbmocv.13gphs@ifi.uio.no>
To: Phillip Ezolt <ez...@perf.zko.dec.com>
Original-References: <Pine.OSF.3.96.990505144826.13001A-100...@perf.zko.dec.com>
Notfrom: spam...@atnf.csiro.au
X-Orcpt: rfc822;linux-kernel-outgoing-dig
Organization: Internet mailing list
Newsgroups: fa.linux.kernel
X-Loop: majord...@vger.rutgers.edu

Phillip Ezolt writes:
> Hi all,
> 
> In doing some performance work with SPECWeb96 on ALpha/Linux with apache,
> it looks like "schedule" is the main bottleneck. 
> 
> (Kernel v2.2.5, Apache 1.3.4, egcs-1.1.1, iprobe-4.1)
> 
> When running a SPECWeb96 strobe run on Alpha/linux, I found that when the
> CPU is pegged, 18% of the time is spent in the scheduler.

This is some very interesting data!

> Using Iprobe, I got the following function breakdown: (only functions >1%
> are shown)
> 
> Begin            End                                    Sample Image Total
> Address          Address          Name                   Count   Pct   Pct
> -------          -------          ----                   -----   ---   ---
> 0000000000000000-00000000000029FC /usr/bin/httpd        127463        18.5 
> 00000001200419A0-000000012004339F   ap_vformatter        15061  11.8   2.2 
> FFFFFC0000300000-00000000FFFFFFFF vmlinux               482385        70.1 
> FFFFFC00003103E0-FFFFFC000031045F   entInt                7848   1.6   1.1
> FFFFFC0000315E40-FFFFFC0000315F7F   do_entInt            48487  10.1   7.0
> FFFFFC0000327A40-FFFFFC0000327D7F   schedule            124815  25.9  18.1
> FFFFFC000033FAA0-FFFFFC000033FCDF   kfree                 7876   1.6   1.1
> FFFFFC00003A9960-FFFFFC00003A9EBF   ip_queue_xmit         8616   1.8   1.3
> FFFFFC00003B9440-FFFFFC00003B983F   tcp_v4_rcv           11131   2.3   1.6
> FFFFFC0000441CA0-FFFFFC000044207F   do_csum_partial      43112   8.9   6.3 
>                                     _copy_from_user 

Why don't we see the time taken by the goodness() function?

> Apache has a fairly even cycle distribution, but in the kernel, 'schedule' 
> really sticks out as the CPU burner. 
> 
> I think that the linear search for next runnable process is where time is
> being spent. 

Could well be, especially if the context switches are happening
between threads rather than separate processes. Thread switches are
*really* fast under Linux.

> As an independent test, I ran vmstat while SPECWeb was running.
> 
> The leftmost column is the number of processes waiting to run.  These number
> are above the 3 or 4 that are normally quoted. 
> 
>  procs                  memory    swap        io    system         cpu
>  r b w  swpd  free  buff cache  si  so   bi   bo   in   cs  us  sy  id
[...]
> 94 18 1   208  5920  5248 165896   0   0 1745  191 5288 2952  32  60   7
> 
> It looks like the run queue is much longer than expected. 

Indeed. As a separate question, we may wonder why so many
processes/threads are being used, and whether that number could/should
be reduced. Perhaps the server is doing something silly. But that's an
aside. Instead, I'd like to explore ways of reducing the (already low)
scheduler overhead.

In September last year I wrote a patch which put RT processes on a
separate run queue. While you don't have RT processes (I expect), one
of the benefits of this patch is that it cleans up some of the
scheduler code. Specifically, the goodness() function has some
special-casing for RT processes removed. For a short run queue, the
improvement is pretty marginal. However, for a long run queue, the
improvement may be significant. So I'd ask you to redo your tests
again with this patch applied. I've ported the patch to 2.2.7. It's
untested in 2.2.7, but it worked fine in 2.1.x.

See: http://www.atnf.csiro.au/~rgooch/linux/kernel-patches.html

				Regards,

					Richard....

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

From: Rik van Riel <r...@nl.linux.org>
Subject: Re: Overscheduling DOES happen with high web server load.
Date: 1999/05/06
Message-ID: <fa.n4qmvjv.b400bh@ifi.uio.no>#1/1
X-Deja-AN: 474660725
Original-Date: Thu, 6 May 1999 09:32:39 +0200 (CEST)
Sender: owner-linux-ker...@vger.rutgers.edu
Original-Message-ID: <Pine.LNX.4.03.9905060929130.219-100000@mirkwood.dummy.home>
References: <fa.i397bcv.k5i7ak@ifi.uio.no>
To: Richard Gooch <rgo...@atnf.csiro.au>
X-Sender: r...@mirkwood.dummy.home
X-Authentication-Warning: mirkwood.nl.linux.org: riel owned process doing -bs
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Search-Engine-Bait: http://humbolt.nl.linux.org/
X-Orcpt: rfc822;linux-kernel-outgoing-dig
X-My-Own-Server: http://www.nl.linux.org/
Organization: Internet mailing list
MIME-Version: 1.0
Newsgroups: fa.linux.kernel
X-Loop: majord...@vger.rutgers.edu

On Thu, 6 May 1999, Richard Gooch wrote:
> Phillip Ezolt writes:

> > (Kernel v2.2.5, Apache 1.3.4, egcs-1.1.1, iprobe-4.1)
> > 
> > When running a SPECWeb96 strobe run on Alpha/linux, I found that when the
> > CPU is pegged, 18% of the time is spent in the scheduler.
> 
> This is some very interesting data!

Indeed.

> > It looks like the run queue is much longer than expected. 
> 
> Instead, I'd like to explore ways of reducing the (already low)
> scheduler overhead.
> 
> In September last year I wrote a patch which put RT processes on a
> separate run queue.

I'll start working on my scheduler bigpatch again. There
must be more things that can be incorporated in order to
improve the efficiency and performance of the Linux
scheduler...

regards,

Rik -- Open Source: you deserve to be in control of your data.
+-------------------------------------------------------------------+
| Le Reseau netwerksystemen BV:               http://www.reseau.nl/ |
| Linux Memory Management site:  http://humbolt.geo.uu.nl/Linux-MM/ |
| Nederlandse Linux documentatie:          http://www.nl.linux.org/ |
+-------------------------------------------------------------------+


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

From: j...@pa.dec.com (Jim Gettys)
Subject: Re: Overscheduling DOES happen with high web server load.
Date: 1999/05/06
Message-ID: <fa.gsrd1gv.lkcv2h@ifi.uio.no>#1/1
X-Deja-AN: 474791689
Original-Date: Thu, 6 May 1999 06:30:31 -0700
Sender: owner-linux-ker...@vger.rutgers.edu
Original-Message-Id: <9905061330.AA24536@pachyderm.pa.dec.com>
References: <fa.lrcap4v.34p9h@ifi.uio.no>
To: Phillip Ezolt <ez...@perf.zko.dec.com>
Content-Type: text/plain
X-Orcpt: rfc822;linux-kernel-outgoing-dig
Organization: Internet mailing list
Mime-Version: 1.0
Newsgroups: fa.linux.kernel
X-Loop: majord...@vger.rutgers.edu

Whle this discussion continues, I'd like to remind people of the
the work of the linux scalability project, at 
http://www.citi.umich.edu/projects/citi-netscape/

Some of these patches have already been applied to current kernels; but 
some have not, and there are some issues described there for which there 
are yet no solutions, including the poll() work there....
			- Jim


--
Jim Gettys
Industry Standards and Consortia
Compaq Computer Corporation
Visting Scientist, World Wide Web Consortium, M.I.T.
http://www.w3.org/People/Gettys/
j...@w3.org, j...@pa.dec.com


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

From: Andrea Arcangeli <and...@e-mind.com>
Subject: Re: Overscheduling DOES happen with high web server load.
Date: 1999/05/06
Message-ID: <fa.j5b0g0v.175qmbb@ifi.uio.no>#1/1
X-Deja-AN: 474816447
Original-Date: Thu, 6 May 1999 17:39:35 +0200 (CEST)
Sender: owner-linux-ker...@vger.rutgers.edu
Original-Message-ID: <Pine.LNX.4.05.9905061734270.2228-100000@laser.random>
References: <fa.lrbmocv.13gphs@ifi.uio.no>
To: Phillip Ezolt <ez...@perf.zko.dec.com>
X-Sender: and...@laser.random
X-Authentication-Warning: laser.random: andrea owned process doing -bs
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Orcpt: rfc822;linux-kernel-outgoing-dig
Organization: Internet mailing list
X-Public-Key-URL: http://e-mind.com/~andrea/aa.asc
MIME-Version: 1.0
Newsgroups: fa.linux.kernel
X-Loop: majord...@vger.rutgers.edu

On Wed, 5 May 1999, Phillip Ezolt wrote:

>Hi all,
>
>In doing some performance work with SPECWeb96 on ALpha/Linux with apache,
>it looks like "schedule" is the main bottleneck. 

Alt. Alpha uses HZ at 1024 so you get a scheduling rate by default 10
times higher than in all other archs.

>Is it necessary to calculate the goodness of every process at every schedule?

I think what we should do is to reschedule _only_ if a different process
will be scheduled. What I consider oversheduling is to schedule() and then
not switch to another task. Could you apply the patch below and run vmstat
1 again and see the rate of the overscheduling?

Index: kernel//sched.c
===================================================================
RCS file: /var/cvs/linux/kernel/sched.c,v
retrieving revision 1.1.2.33
diff -u -r1.1.2.33 sched.c
--- sched.c	1999/05/05 11:26:37	1.1.2.33
+++ sched.c	1999/05/06 15:37:16
@@ -764,12 +764,12 @@
 #ifdef __SMP__
 		sched_data->prev = prev;
 #endif
-	 	kstat.context_swtch++;
 		get_mmu_context(next);
 		switch_to(prev,next);
 
 		__schedule_tail();
 	}
+	 	kstat.context_swtch++;
   
 	reacquire_kernel_lock(current);
 	return;


If the rate is low there is no overscheduling and you should simply
decrease HZ to spend less time in the scheduler.

Andrea Arcangeli


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/


From: Kurt Garloff <garl...@suse.de>
Subject: Re: Overscheduling DOES happen with high web server load.
Date: 1999/05/07
Message-ID: <fa.ed3pouv.ohimj6@ifi.uio.no>#1/1
X-Deja-AN: 475019424
X-Operating-System: Linux 2.2.5-ac3_devfs i686
Original-Date: Thu, 6 May 1999 21:02:04 +0200
Sender: owner-linux-ker...@vger.rutgers.edu
References: <fa.j5b0g0v.175qmbb@ifi.uio.no>
Mime-Version: 1.0
X-PGP-Version: 2.6.3i
Original-Message-ID: <19990506210204.B5468@kurt.kdt.de>
X-PGP-Fingerprint: 92 00 AC 56 59 50 13 83  3C 18 6F 1B 25 A0 3A 5F
X-PGP-Key: 1024/CEFC9215
To: Andrea Arcangeli <and...@e-mind.com>
Original-References: <Pine.OSF.3.96.990505144826.13001A-100...@perf.zko.dec.com> 
<Pine.LNX.4.05.9905061734270.2228-100...@laser.random>
X-PGP-Info: on http://www.garloff.de/kurt/pgp.public.key.kurt.home.asc
Content-Type: multipart/signed; boundary="2B/JsCI69OhZNC5r"; 
micalg=pgp-md5; protocol="application/pgp-signature"
X-Orcpt: rfc822;linux-kernel-outgoing-dig
Organization: Internet mailing list
Mail-Followup-To: Andrea Arcangeli <and...@e-mind.com>, Phillip Ezolt 
<ez...@perf.zko.dec.com>, linux-ker...@vger.rutgers.edu, j...@pa.dec.com, 
greg.ta...@digital.com
Newsgroups: fa.linux.kernel
X-Loop: majord...@vger.rutgers.edu


--2B/JsCI69OhZNC5r
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: quoted-printable

On Thu, May 06, 1999 at 05:39:35PM +0200, Andrea Arcangeli wrote:
> On Wed, 5 May 1999, Phillip Ezolt wrote:
> >
> >In doing some performance work with SPECWeb96 on ALpha/Linux with apache,
> >it looks like "schedule" is the main bottleneck.=20
>=20
> Alt. Alpha uses HZ at 1024 so you get a scheduling rate by default 10
> times higher than in all other archs.

=46rom what I understand, the scheduling is not caused by the timer but by
blocking and woken processes.

--=20
Kurt Garloff  <garl...@suse.de>           SuSE GmbH, N=FCrnberg, FRG
Linux kernel development;    SCSI driver: DC390 (tmscsim/AM53C974)

--2B/JsCI69OhZNC5r
Content-Type: application/pgp-signature

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3in

iQCVAwUBNzHnLBaQN/7O/JIVAQE7kwP/fKhXWZhSES0WhOUUzYQpXNUAzlqF+yws
MGoqncJT/fwexzLI06ghRPk22tISM4B26nW/ihQD4RnpXiM9IPyyRubf3HjJ5BD8
UWCqe4597aYeWXbvtOC43pKvityWKFfaKXqXF5tuIfZ6pZ5upbllIr4Lux01xcWY
T9CAazJ52a8=
=yird
-----END PGP SIGNATURE-----

--2B/JsCI69OhZNC5r--

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

From: Rik van Riel <r...@nl.linux.org>
Subject: Re: Overscheduling DOES happen with high web server load.
Date: 1999/05/07
Message-ID: <fa.n7aov3v.9km0rq@ifi.uio.no>#1/1
X-Deja-AN: 475202853
Original-Date: Fri, 7 May 1999 17:15:25 +0200 (CEST)
Sender: owner-linux-ker...@vger.rutgers.edu
Original-Message-ID: <Pine.LNX.4.03.9905071703560.219-100000@mirkwood.dummy.home>
References: <fa.ed3pouv.ohimj6@ifi.uio.no>
To: Kurt Garloff <garl...@suse.de>
X-Sender: r...@mirkwood.dummy.home
X-Authentication-Warning: mirkwood.nl.linux.org: riel owned process doing -bs
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Search-Engine-Bait: http://humbolt.nl.linux.org/
X-Orcpt: rfc822;linux-kernel-outgoing-dig
X-My-Own-Server: http://www.nl.linux.org/
Organization: Internet mailing list
MIME-Version: 1.0
Newsgroups: fa.linux.kernel
X-Loop: majord...@vger.rutgers.edu

On Thu, 6 May 1999, Kurt Garloff wrote:

> From what I understand, the scheduling is not caused by the timer
> but by blocking and woken processes.

Not only that, the fact that we're using a traditional O(n)
run queue is somewhat of a performance bottleneck.

I'm currently looking into the scheduler used by Alliance
(www.allos.org) and it looks very promising. If I have any
time left, I'll port it to Linux.

It's based on the idea of a priority heap. Processes have
a quantum and a defer value. The quantum value is the length
of the process' time slice and the defer value is the time
at which it will be run next (sort of a deadline).

The process at the top of the heap is the process with the
lowest (run next) defer value. After a process finishes it's
time slice, the defer value is incremented (say, by p->priority)
and the process is sorted down the B-tree. This means that the
algorithm for selecting the best process is O(1) on UP machines
and O(log(nr_cpus)) on SMP machines.

Schedule_timeout() can be replaced by a simple resorting of
the heap. Basically we only need to remove processes from
the heap if they do blocking I/O or wait for a signal
(otherwise they would clutter up the heap).

cheers,

Rik -- Open Source: you deserve to be in control of your data.
+-------------------------------------------------------------------+
| Le Reseau netwerksystemen BV:               http://www.reseau.nl/ |
| Linux Memory Management site:  http://humbolt.geo.uu.nl/Linux-MM/ |
| Nederlandse Linux documentatie:          http://www.nl.linux.org/ |
+-------------------------------------------------------------------+


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

From: Ingo Molnar <mi...@chiara.csoma.elte.hu>
Subject: Re: Overscheduling DOES happen with high web server load.
Date: 1999/05/07
Message-ID: <fa.lhohhov.f563o4@ifi.uio.no>#1/1
X-Deja-AN: 475225521
Original-Date: Fri, 7 May 1999 18:17:33 +0200 (CEST)
Sender: owner-linux-ker...@vger.rutgers.edu
Original-Message-ID: <Pine.LNX.3.96.990507181436.8938B-100000@chiara.csoma.elte.hu>
References: <fa.n7aov3v.9km0rq@ifi.uio.no>
To: Rik van Riel <r...@nl.linux.org>
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Orcpt: rfc822;linux-kernel-outgoing-dig
Organization: Internet mailing list
MIME-Version: 1.0
Newsgroups: fa.linux.kernel
X-Loop: majord...@vger.rutgers.edu


On Fri, 7 May 1999, Rik van Riel wrote:

> Schedule_timeout() can be replaced by a simple resorting of
> the heap. Basically we only need to remove processes from
> the heap if they do blocking I/O or wait for a signal
> (otherwise they would clutter up the heap).

schedule_timeout() is not really expected to have high performance. Its
functionality was moved out of the main scheduler partly for this reason. 
Btw., the timer code (which is used by schedule_timeout() intrnally) has a
sort of heap structure already.

-- mingo


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

From: Ingo Molnar <mi...@chiara.csoma.elte.hu>
Subject: Re: Overscheduling DOES happen with high web server load.
Date: 1999/05/07
Message-ID: <fa.li8jhgv.cl43g4@ifi.uio.no>#1/1
X-Deja-AN: 475225522
Original-Date: Fri, 7 May 1999 18:09:43 +0200 (CEST)
Sender: owner-linux-ker...@vger.rutgers.edu
Original-Message-ID: <Pine.LNX.3.96.990507180747.8938A-100000@chiara.csoma.elte.hu>
References: <fa.n7aov3v.9km0rq@ifi.uio.no>
To: Rik van Riel <r...@nl.linux.org>
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Orcpt: rfc822;linux-kernel-outgoing-dig
Organization: Internet mailing list
MIME-Version: 1.0
Newsgroups: fa.linux.kernel
X-Loop: majord...@vger.rutgers.edu


On Fri, 7 May 1999, Rik van Riel wrote:

> It's based on the idea of a priority heap. Processes have
> a quantum and a defer value. The quantum value is the length
> of the process' time slice and the defer value is the time
> at which it will be run next (sort of a deadline).
> 
> The process at the top of the heap is the process with the
> lowest (run next) defer value. After a process finishes it's
> time slice, the defer value is incremented (say, by p->priority)
> and the process is sorted down the B-tree. This means that the
> algorithm for selecting the best process is O(1) on UP machines
> and O(log(nr_cpus)) on SMP machines.
> 
> Schedule_timeout() can be replaced by a simple resorting of
> the heap. Basically we only need to remove processes from
> the heap if they do blocking I/O or wait for a signal
> (otherwise they would clutter up the heap).

so? And how do you handle VM and CPU (and who knows what type of other
future) affinity?

-- mingo


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

From: Rik van Riel <r...@nl.linux.org>
Subject: Re: Overscheduling DOES happen with high web server load.
Date: 1999/05/07
Message-ID: <fa.n7a703v.8ks1rs@ifi.uio.no>#1/1
X-Deja-AN: 475316640
Original-Date: Fri, 7 May 1999 20:48:07 +0200 (CEST)
Sender: owner-linux-ker...@vger.rutgers.edu
Original-Message-ID: <Pine.LNX.4.03.9905072045440.219-100000@mirkwood.dummy.home>
References: <fa.li8jhgv.cl43g4@ifi.uio.no>
To: Ingo Molnar <mi...@chiara.csoma.elte.hu>
X-Sender: r...@mirkwood.dummy.home
X-Authentication-Warning: mirkwood.nl.linux.org: riel owned process doing -bs
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Search-Engine-Bait: http://humbolt.nl.linux.org/
X-Orcpt: rfc822;linux-kernel-outgoing-dig
X-My-Own-Server: http://www.nl.linux.org/
Organization: Internet mailing list
MIME-Version: 1.0
Newsgroups: fa.linux.kernel
X-Loop: majord...@vger.rutgers.edu

On Fri, 7 May 1999, Ingo Molnar wrote:
> On Fri, 7 May 1999, Rik van Riel wrote:
> 
> > It's based on the idea of a priority heap.
	[snip]

> so? And how do you handle VM and CPU (and who knows what type of
> other future) affinity?

I haven't thought about that yet, but I think we _will_
have to think up something to make the current scheduler
more responsive and more predictable under load and to
reduce the CPU time used by niced tasks.

I think that even without the priority heap we can use the
Quantum/Defer model in order to get better predictability
and responsiveness under load.

Rik -- Open Source: you deserve to be in control of your data.
+-------------------------------------------------------------------+
| Le Reseau netwerksystemen BV:               http://www.reseau.nl/ |
| Linux Memory Management site:  http://humbolt.geo.uu.nl/Linux-MM/ |
| Nederlandse Linux documentatie:          http://www.nl.linux.org/ |
+-------------------------------------------------------------------+


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

From: Ingo Molnar <mi...@chiara.csoma.elte.hu>
Subject: Re: Overscheduling DOES happen with high web server load.
Date: 1999/05/08
Message-ID: <fa.lfo5h8v.95m087@ifi.uio.no>#1/1
X-Deja-AN: 475726641
Original-Date: Sat, 8 May 1999 17:14:39 +0200 (CEST)
Sender: owner-linux-ker...@vger.rutgers.edu
Original-Message-ID: <Pine.LNX.3.96.990508170633.5517A-100000@chiara.csoma.elte.hu>
References: <fa.n7a703v.8ks1rs@ifi.uio.no>
To: Rik van Riel <r...@nl.linux.org>
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Orcpt: rfc822;linux-kernel-outgoing-dig
Organization: Internet mailing list
MIME-Version: 1.0
Newsgroups: fa.linux.kernel
X-Loop: majord...@vger.rutgers.edu


On Fri, 7 May 1999, Rik van Riel wrote:

> > > It's based on the idea of a priority heap.
> 	[snip]
> 
> > [...] And how do you handle VM and CPU (and who knows what type of
> > other future) affinity?
> 
> I haven't thought about that yet [...]

thats one of the tough things IMO ... without those constraints we could
easily get rid of the linear behavior in the scheduler. We are trying to
avoid situations where there are lots of tasks on the runqueue _and_ there
are lots of reschedules happening, this way linearity doesnt matter. 

>                           [...], but I think we _will_
> have to think up something to make the current scheduler
> more responsive and more predictable under load [...]

do you still see responsiveness problems under pre4-2.2.8? If yes then i'd
be very interested in reproducing it.

>                                             [...] and to
> reduce the CPU time used by niced tasks.

this can be achieved by increasing (or changing) the scale of priorities. 
(this can be done seemlessly) But i doubt this matters in most cases.
(except when there are _lots_ of niced 100%-CPU using processes running)

-- mingo


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

From: Rik van Riel <r...@nl.linux.org>
Subject: Re: Overscheduling DOES happen with high web server load.
Date: 1999/05/09
Message-ID: <fa.lge9onv.6gipos@ifi.uio.no>#1/1
X-Deja-AN: 475889559
Original-Date: Sun, 9 May 1999 18:21:55 +0200 (CEST)
Sender: owner-linux-ker...@vger.rutgers.edu
Original-Message-ID: <Pine.LNX.4.03.9905091817410.256-100000@mirkwood.nl.linux.org>
References: <fa.lfo5h8v.95m087@ifi.uio.no>
To: Ingo Molnar <mi...@chiara.csoma.elte.hu>
X-Authentication-Warning: mirkwood.nl.linux.org: riel owned process doing -bs
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Search-Engine-Bait: http://humbolt.nl.linux.org/
X-Orcpt: rfc822;linux-kernel-outgoing-dig
X-My-Own-Server: http://www.nl.linux.org/
Organization: Internet mailing list
MIME-Version: 1.0
Newsgroups: fa.linux.kernel
X-Loop: majord...@vger.rutgers.edu

On Sat, 8 May 1999, Ingo Molnar wrote:
> On Fri, 7 May 1999, Rik van Riel wrote:
> 
> >                           [...], but I think we _will_
> > have to think up something to make the current scheduler
> > more responsive and more predictable under load [...]
> 
> do you still see responsiveness problems under pre4-2.2.8? If yes
> then i'd be very interested in reproducing it.

I've read the patch and think you're right about this one.
Under normal loads 2.2.8 will have no problems at all except
possibly the fact that it calls reschedule_idle() twice on
most reschedules and the fact that the kernel still recalculates
the priority of _all_ processes as soon as one process runs
out of it's time slice.

> >                                             [...] and to
> > reduce the CPU time used by niced tasks.
> 
> this can be achieved by increasing (or changing) the scale of
> priorities.  (this can be done seemlessly)

More importantly, it can be done without an increase in
the scheduling overhead and with removal of the current
process recalculation ritual.

It will increase SMP scalability of the scheduler, allow
for a wider priority scale and maybe even decrease scheduler
overhead (I'm not sure about the last one being measurable
though)...

cheers,

Rik -- Open Source: you deserve to be in control of your data.
+-------------------------------------------------------------------+
| Le Reseau netwerksystemen BV:               http://www.reseau.nl/ |
| Linux Memory Management site:  http://humbolt.geo.uu.nl/Linux-MM/ |
| Nederlandse Linux documentatie:          http://www.nl.linux.org/ |
+-------------------------------------------------------------------+


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

From: Ingo Molnar <mi...@chiara.csoma.elte.hu>
Subject: Re: Overscheduling DOES happen with high web server load.
Date: 1999/05/09
Message-ID: <fa.nkq90mv.1j4eios@ifi.uio.no>#1/1
X-Deja-AN: 475897443
Original-Date: Sun, 9 May 1999 19:33:44 +0200 (CEST)
Sender: owner-linux-ker...@vger.rutgers.edu
Original-Message-ID: <Pine.LNX.3.96.990509192416.17632G-100000@chiara.csoma.elte.hu>
References: <fa.lge9onv.6gipos@ifi.uio.no>
To: Rik van Riel <r...@nl.linux.org>
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Orcpt: rfc822;linux-kernel-outgoing-dig
Organization: Internet mailing list
MIME-Version: 1.0
Newsgroups: fa.linux.kernel
X-Loop: majord...@vger.rutgers.edu


On Sun, 9 May 1999, Rik van Riel wrote:

> I've read the patch and think you're right about this one.
> Under normal loads 2.2.8 will have no problems at all except
> possibly the fact that it calls reschedule_idle() twice on
> most reschedules [...]

what do you mean? We call reschedule_idle() only when a process 1) gets
runnable 2) gets scheduled away (but is still runnable). These are two
different situations.

>            [...] and the fact that the kernel still recalculates
> the priority of _all_ processes as soon as one process runs
> out of it's time slice.

this recalculation argument is a complete red herring. I've explained this
earlier too: the number of recalculations happens at a _constant
frequency_, with the additional mechanizm that there are less
recalculations if there are more CPU-bound processes. The goal is to have
tasks' increase their 'dynamic priority' even if they are not on the
runqueue. So any architectural change that concentrates on removing these
recalculations is seriously misguided.

> 
> > >                                             [...] and to
> > > reduce the CPU time used by niced tasks.
> > 
> > this can be achieved by increasing (or changing) the scale of
> > priorities.  (this can be done seemlessly)
> 
> More importantly, it can be done without an increase in
> the scheduling overhead and with removal of the current
> process recalculation ritual.
> 
> It will increase SMP scalability of the scheduler, allow
> for a wider priority scale and maybe even decrease scheduler
> overhead (I'm not sure about the last one being measurable
> though)...
> 
> cheers,
> 
> Rik -- Open Source: you deserve to be in control of your data.
> +-------------------------------------------------------------------+
> | Le Reseau netwerksystemen BV:               http://www.reseau.nl/ |
> | Linux Memory Management site:  http://humbolt.geo.uu.nl/Linux-MM/ |
> | Nederlandse Linux documentatie:          http://www.nl.linux.org/ |
> +-------------------------------------------------------------------+
> 


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

From: Rik van Riel <r...@nl.linux.org>
Subject: Re: Overscheduling DOES happen with high web server load.
Date: 1999/05/09
Message-ID: <fa.lfu3pfv.40cogo@ifi.uio.no>#1/1
X-Deja-AN: 475921984
Original-Date: Sun, 9 May 1999 20:49:23 +0200 (CEST)
Sender: owner-linux-ker...@vger.rutgers.edu
Original-Message-ID: <Pine.LNX.4.03.9905092043260.256-100000@mirkwood.nl.linux.org>
References: <fa.nkq90mv.1j4eios@ifi.uio.no>
To: Ingo Molnar <mi...@chiara.csoma.elte.hu>
X-Authentication-Warning: mirkwood.nl.linux.org: riel owned process doing -bs
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Search-Engine-Bait: http://humbolt.nl.linux.org/
X-Orcpt: rfc822;linux-kernel-outgoing-dig
X-My-Own-Server: http://www.nl.linux.org/
Organization: Internet mailing list
MIME-Version: 1.0
Newsgroups: fa.linux.kernel
X-Loop: majord...@vger.rutgers.edu

On Sun, 9 May 1999, Ingo Molnar wrote:
> On Sun, 9 May 1999, Rik van Riel wrote:
> 
> > I've read the patch and think you're right about this one.
> > Under normal loads 2.2.8 will have no problems at all except
> > possibly the fact that it calls reschedule_idle() twice on
> > most reschedules [...]
> 
> what do you mean? We call reschedule_idle() only when a process 1)
> gets runnable 2) gets scheduled away (but is still runnable).
> These are two different situations.

OK, you're right about that one -- a slight brain fart on my
side. Then again, we probably want to make goodness() a bit
cheaper than it is now because we're calling it more often
than before....

> >            [...] and the fact that the kernel still recalculates
> > the priority of _all_ processes as soon as one process runs
> > out of it's time slice.
> 
> this recalculation argument is a complete red herring. I've explained this
> earlier too: the number of recalculations happens at a _constant
> frequency_, with the additional mechanizm that there are less
> recalculations if there are more CPU-bound processes. The goal is to have
> tasks' increase their 'dynamic priority' even if they are not on the
> runqueue. So any architectural change that concentrates on removing these
> recalculations is seriously misguided.

I've got a new scheme in mind which uses a new variable in
the task struct in order to make goodness simpler, increase
the range of CPU usage (for niced tasks), favor interactive
performance better and get rid of the recalculation as a
nice side effect...

Btw, the rate of recalculation increases with more CPUs in
the machine so I wouldn't be surprised if it didn't scale
well to number crunching machines with a lot of nice +19
tasks.

Anyway, I think I can bring my point across much better in
C than in english, so I'll focus on some source code now...

cheers,

Rik -- Open Source: you deserve to be in control of your data.
+-------------------------------------------------------------------+
| Le Reseau netwerksystemen BV:               http://www.reseau.nl/ |
| Linux Memory Management site:  http://humbolt.geo.uu.nl/Linux-MM/ |
| Nederlandse Linux documentatie:          http://www.nl.linux.org/ |
+-------------------------------------------------------------------+


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

			        About USENET

USENET (Users’ Network) was a bulletin board shared among many computer
systems around the world. USENET was a logical network, sitting on top
of several physical networks, among them UUCP, BLICN, BERKNET, X.25, and
the ARPANET. Sites on USENET included many universities, private companies
and research organizations. See USENET Archives.

		       SCO Files Lawsuit Against IBM

March 7, 2003 - The SCO Group filed legal action against IBM in the State 
Court of Utah for trade secrets misappropriation, tortious interference, 
unfair competition and breach of contract. The complaint alleges that IBM 
made concentrated efforts to improperly destroy the economic value of 
UNIX, particularly UNIX on Intel, to benefit IBM's Linux services 
business. See SCO vs IBM.

The materials and information included in this website may only be used
for purposes such as criticism, review, private study, scholarship, or
research.

Electronic mail:			       WorldWideWeb:
   tech-insider@outlook.com			  http://tech-insider.org/