In the Linux scheduler they use a circular queue implementation with round
robin. What is the advantage of this over just using a normal queue with a
back and front. Also does anyone know what a test plan for such a design
would even begin to look like. This is a project for a proposal going around
in my neighborhood and I am wondering why in the world someone would want to
modify the Linux scheduler to this extent.
--------- Received message begins Here ---------
>
> In the Linux scheduler they use a circular queue implementation with round
> robin. What is the advantage of this over just using a normal queue with a
> back and front. Also does anyone know what a test plan for such a design
> would even begin to look like. This is a project for a proposal going around
> in my neighborhood and I am wondering why in the world someone would want to
> modify the Linux scheduler to this extent.
This is not an authoritive answer but:
It's simple, and fast. Locks only needed when adding/removing
entries.
It is also nearly optimum when the queue only has 5 (or so) number of
entries. It will not be optimum if there are 32/64 CPUs with 120 or more
runnable entries. There are other schedulers available that may do a
better job for that situation.
-------------------------------------------------------------------------
Jesse I Pollard, II
Email: [email protected]
Any opinions expressed are solely my own.
----- Original Message -----
From: Jesse Pollard <[email protected]>
To: <[email protected]>; <[email protected]>
Sent: Wednesday, November 01, 2000 2:27 PM
Subject: Re: 1.2.45 Linux Scheduler
> --------- Received message begins Here ---------
>
> >
> > In the Linux scheduler they use a circular queue implementation with
round
> > robin. What is the advantage of this over just using a normal queue with
a
> > back and front. Also does anyone know what a test plan for such a design
> > would even begin to look like. This is a project for a proposal going
around
> > in my neighborhood and I am wondering why in the world someone would
want to
> > modify the Linux scheduler to this extent.
>
> This is not an authoritive answer but:
>
> It's simple, and fast. Locks only needed when adding/removing
> entries.
>
> It is also nearly optimum when the queue only has 5 (or so) number of
> entries. It will not be optimum if there are 32/64 CPUs with 120 or more
> runnable entries. There are other schedulers available that may do a
> better job for that situation.
I don't know who runs Linux w/ 32/64 CPUs and w/ 120 active procs but
if someone on earth exist ... :
http://www.mycio.com/davidel/lk/adapt-sched-v3.0-2.2.14.gz
- Davide
Anonymous wrote:
>
> In the Linux scheduler they use a circular queue implementation with round
> robin. What is the advantage of this over just using a normal queue with a
> back and front. Also does anyone know what a test plan for such a design
> would even begin to look like. This is a project for a proposal going around
> in my neighborhood and I am wondering why in the world someone would want to
> modify the Linux scheduler to this extent.
>
The advantages to the circular bi-directional list are:
1.) You can insert AND remove entries at any point in the list with
simple code that does not have to a:) test to see if it is dealing with
an end point or b:) know ANY thing about the rest of the list.
2.) You have access to each end of the queue without searching (great
for RR stuff).
3.) It is easy to get the compiler to do as good a job at insert and
delete as you can do in assembly (see 2.4.0-testX code).
In fact Linux uses this list structure for almost all of its lists, not
just the run list.
The problems with the scheduler list management are not so much circular
bi-directional issues as the fact that the actual dispatch priorities
are so dynamic that you (the scheduler) can not predict at list
insertion time the best task dispatch order. A real-time scheduler with
fixed priorities has a much easier go of it in this regard. See, for
example, the real-time scheduler at <http://www.mvista.com>.
George