|
|
|
|
|
|
| Author |
Message |
Terry Lambert
*nix forums Guru
Joined: 19 Mar 2002
Posts: 434
|
 Posted: Wed Jul 17, 2002 5:24 am Post subject:
Re: proposed changes to kern_switch.c and kern_synch.c
|
|
|
Luigi Rizzo wrote:
| Quote: | Hi,
we have implemented a weight-based process scheduler
for FreeBSD-stable, and are trying to port it to -current (in the
description below replace "process" with "thread/kse" as appropriate
for the -current case).
|
Are you going to make this new scheduler generally available?
What is the weighting?
Is it weighted fair share?
-- Terry
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message |
|
| Back to top |
|
 |
Luigi Rizzo
*nix forums addict
Joined: 07 Apr 2002
Posts: 72
|
| Posted: Wed Jul 17, 2002 5:42 am Post subject:
Re: proposed changes to kern_switch.c and kern_synch.c
|
|
|
On Wed, Jul 17, 2002 at 12:24:09AM -0700, Terry Lambert wrote:
| Quote: | Luigi Rizzo wrote:
Hi,
we have implemented a weight-based process scheduler
for FreeBSD-stable, and are trying to port it to -current (in the
description below replace "process" with "thread/kse" as appropriate
for the -current case).
Are you going to make this new scheduler generally available?
|
yes of course! At least the version for -stable is basically working,
for -current i still have to understand the relation between
KSEG's and threads etc.
| Quote: | What is the weighting?
|
it is basically the WF2Q+ algorithm used in dummynet (i am the king
of recycling  . The OS community calls this "Proportional Share"
or something like that.
Same as for dummynet queues, active processes get each a share of
the CPU which is proportional to their weight. The absolute share
of course depends on the number of active processes and the total
sum of weights.
The complexity of the algorithm is O(log N) where N is the number
of active processes.
The code has been developed by a PhD student of mine, Paolo Valente,
who is also the guy behind the WF2Q+ implementation in dummynet.
cheers
luigi
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message |
|
| Back to top |
|
|
Peter Wemm
*nix forums Guru Wannabe
Joined: 11 Apr 2002
Posts: 113
|
| Posted: Wed Jul 17, 2002 5:43 am Post subject:
Re: proposed changes to kern_switch.c and kern_synch.c
|
|
|
Luigi Rizzo wrote:
| Quote: | In order to make this work, it is convenient to have all
scheduler-specific functions and data structures in a
single file (kern_switch*.c), and generic support in
another one (kern_synch.c). I believe this was also the original
BSD design in partitioning the code between the two files.
|
You would be mistaken there. kern_switch.c is new and has only existed
very recently. kern_switch.c came about as a C implementation of code that
used to be embedded inside i386/swtch.s. It has taken on a life of its own
now though. :-/
Cheers,
-Peter
--
Peter Wemm - peter@wemm.org; peter@FreeBSD.org; peter@yahoo-inc.com
"All of this is for nothing if we don't go to the stars" - JMS/B5
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message |
|
| Back to top |
|
|
Luigi Rizzo
*nix forums addict
Joined: 07 Apr 2002
Posts: 72
|
| Posted: Wed Jul 17, 2002 5:47 am Post subject:
Re: proposed changes to kern_switch.c and kern_synch.c
|
|
|
On Wed, Jul 17, 2002 at 12:43:35AM -0700, Peter Wemm wrote:
| Quote: | Luigi Rizzo wrote:
In order to make this work, it is convenient to have all
scheduler-specific functions and data structures in a
single file (kern_switch*.c), and generic support in
another one (kern_synch.c). I believe this was also the original
BSD design in partitioning the code between the two files.
You would be mistaken there. kern_switch.c is new and has only existed
very recently. kern_switch.c came about as a C implementation of code that
used to be embedded inside i386/swtch.s. It has taken on a life of its own
now though. :-/
|
good to know!
Anyways, does the partitioning of functionalities sound reasonable ?
cheers
luigi
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message |
|
| Back to top |
|
|
Luigi Rizzo
*nix forums addict
Joined: 07 Apr 2002
Posts: 72
|
| Posted: Wed Jul 17, 2002 6:57 am Post subject:
Re: proposed changes to kern_switch.c and kern_synch.c
|
|
|
On Wed, Jul 17, 2002 at 05:09:16PM -0700, Lars Eggert wrote:
| Quote: | Luigi Rizzo wrote:
it is basically the WF2Q+ algorithm used in dummynet (i am the king
of recycling . The OS community calls this "Proportional Share"
or something like that.
Since it sounds similar, what are the key differences to the lottery
scheduler
(http://www.csua.berkeley.edu/computing/software/lottery-sched.html)?
|
i don't know much on the lottery scheduler, but it looks like it
is probabilistic as opposed to deterministic. The paper on lottery
scheduling claims to have the same O(log N) complexity as WF2Q+
(though i haven't looked at the implementation issues).
In any case, one of the good things of our work is that it provides
a framework for replacing the standard scheduler with another one
with minimal interaction with the rest of the system, being all
code and data structures confined in a private file/data structures.
cheers
luigi
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message |
|
| Back to top |
|
|
Peter Wemm
*nix forums Guru Wannabe
Joined: 11 Apr 2002
Posts: 113
|
| Posted: Wed Jul 17, 2002 7:22 am Post subject:
Re: proposed changes to kern_switch.c and kern_synch.c
|
|
|
Luigi Rizzo wrote:
| Quote: | On Wed, Jul 17, 2002 at 12:43:35AM -0700, Peter Wemm wrote:
Luigi Rizzo wrote:
In order to make this work, it is convenient to have all
scheduler-specific functions and data structures in a
single file (kern_switch*.c), and generic support in
another one (kern_synch.c). I believe this was also the original
BSD design in partitioning the code between the two files.
You would be mistaken there. kern_switch.c is new and has only existed
very recently. kern_switch.c came about as a C implementation of code that
used to be embedded inside i386/swtch.s. It has taken on a life of its own
now though. :-/
good to know!
Anyways, does the partitioning of functionalities sound reasonable ?
|
Please be a little careful. There has been a lot of talk about splitting
the current scheduler into an event driven system rather than a 'run once a
second' thing. This was something along the lines of splitting the current
schedcpu stuff and the various other glue into 3 parts. I think the gist
of it was to have each process do a slight incremental priority adjustment
each time it used up its entire quantum, a slight adjustment at wakeup time,
and the periodic system load factoring code would still run periodically.
You haven't given much details about how you're intending to implement your
alternate scheduler, or even which part you're intending to provide an
alternative for (I'm guessing a different kern_switch, ie: alterantive
run queues, chooseproc^H^H^H^Hkse, setrunqueue(), etc)
Some other comments.. You seem to have seperate the comments about the
digital decay magic in schedcpu() from the code that does the magic. In
fact, things like cexp[] etc are shared between kern_switch (schedcpu1) and
kern_synch (loadav) etc. Are you sure the partitioning is correct?
Maybe *everything* other than the msleep/wakeup/etc related stuff should move?
ie: setrunnable() (which uses updatepri()) etc move as well?
Cheers,
-Peter
--
Peter Wemm - peter@wemm.org; peter@FreeBSD.org; peter@yahoo-inc.com
"All of this is for nothing if we don't go to the stars" - JMS/B5
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message |
|
| Back to top |
|
|
Luigi Rizzo
*nix forums addict
Joined: 07 Apr 2002
Posts: 72
|
| Posted: Wed Jul 17, 2002 7:36 am Post subject:
Re: proposed changes to kern_switch.c and kern_synch.c
|
|
|
there is a lot of overload in the use of priority fields to store
both process state and priority info. Decoupling them is non-trivial,
and so we decided to leave the old scheduler unmodified, and our
alternate scheduler right now tries to keep the relevant information
updated in a consistent way (please be patient, the code will come
out in a couple of days, but i thought the overall design is more
important than the details, which besides might have bugs).
Rather than proposing a massive change all at once, my idea was to
play safe and just start with moving some code from one file to
another, and then revise things one step at a time.
You are right about the schedcpu1() thing, in -stable
the block of code moved there is slightly smalle i think.
Yes, the alternate scheduler is in kern_switch_*.c,
providing replacement for the various chooseproc() and friends,
which are accessed through function pointers initialized according
to the scheduler being chosen.
cheers
luigi
On Wed, Jul 17, 2002 at 02:22:10AM -0700, Peter Wemm wrote:
....
| Quote: | Anyways, does the partitioning of functionalities sound reasonable ?
Please be a little careful. There has been a lot of talk about splitting
the current scheduler into an event driven system rather than a 'run once a
second' thing. This was something along the lines of splitting the current
schedcpu stuff and the various other glue into 3 parts. I think the gist
of it was to have each process do a slight incremental priority adjustment
each time it used up its entire quantum, a slight adjustment at wakeup time,
and the periodic system load factoring code would still run periodically.
You haven't given much details about how you're intending to implement your
alternate scheduler, or even which part you're intending to provide an
alternative for (I'm guessing a different kern_switch, ie: alterantive
run queues, chooseproc^H^H^H^Hkse, setrunqueue(), etc)
Some other comments.. You seem to have seperate the comments about the
digital decay magic in schedcpu() from the code that does the magic. In
fact, things like cexp[] etc are shared between kern_switch (schedcpu1) and
kern_synch (loadav) etc. Are you sure the partitioning is correct?
Maybe *everything* other than the msleep/wakeup/etc related stuff should move?
ie: setrunnable() (which uses updatepri()) etc move as well?
Cheers,
-Peter
--
Peter Wemm - peter@wemm.org; peter@FreeBSD.org; peter@yahoo-inc.com
"All of this is for nothing if we don't go to the stars" - JMS/B5
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message
|
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message |
|
| Back to top |
|
|
Matthew D. Fuller
*nix forums beginner
Joined: 17 Jul 2002
Posts: 23
|
| Posted: Wed Jul 17, 2002 8:54 am Post subject:
Re: proposed changes to kern_switch.c and kern_synch.c
|
|
|
On Tue, Jul 16, 2002 at 11:52:16PM -0700 I heard the voice of
Luigi Rizzo, and lo! it spake thus:
| Quote: |
--- Re. the multi-scheduler architecture ---
The general idea is to make the process/thread/kse scheduler
a replaceable piece of the kernel, requiring no modifications
to the "struct proc", and with the ability of switching from
one scheduler to another one at runtime (this both for testing
purposes and for whatever need may arise).
|
Random related thoughts:
1) From the work you've done on this already, how difficult would you
expect it to be to do this in such a way that you could have multiple
(>2) schedulers around, loading and unloading at will (when disabled, of
course) through KLD's?
2) How much unavoidable overhead is there in switching between the
schedulers? Could it get low enough that it might be meaningful to,
instead of writing One True Scheduler, instead write 3 or 4 different
optimized ones, and have some intelligence to switch between them
automagically as load demands?
--
Matthew Fuller (MF4839) | fullermd@over-yonder.net
Systems/Network Administrator | http://www.over-yonder.net/~fullermd/
"The only reason I'm burning my candle at both ends, is because I
haven't figured out how to light the middle yet"
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message |
|
| Back to top |
|
|
Luigi Rizzo
*nix forums addict
Joined: 07 Apr 2002
Posts: 72
|
| Posted: Wed Jul 17, 2002 9:45 am Post subject:
Re: proposed changes to kern_switch.c and kern_synch.c
|
|
|
On Wed, Jul 17, 2002 at 05:54:34AM -0500, Matthew D. Fuller wrote:
....
| Quote: | Luigi Rizzo, and lo! it spake thus:
--- Re. the multi-scheduler architecture ---
The general idea is to make the process/thread/kse scheduler
a replaceable piece of the kernel, requiring no modifications
to the "struct proc", and with the ability of switching from
one scheduler to another one at runtime (this both for testing
purposes and for whatever need may arise).
Random related thoughts:
1) From the work you've done on this already, how difficult would you
expect it to be to do this in such a way that you could have multiple
(>2) schedulers around, loading and unloading at will (when disabled, of
course) through KLD's?
|
it is basically already done -- schedulers are loaded and initialized
via SYSINIT, and when you switch to another one all references to
the old one are removed and data structures freed.
It is just a matter of providing the module glue.
| Quote: | 2) How much unavoidable overhead is there in switching between the
schedulers? Could it get low enough that it might be meaningful to,
instead of writing One True Scheduler, instead write 3 or 4 different
optimized ones, and have some intelligence to switch between them
automagically as load demands?
|
you need to move all processes from one scheduler to another,
so it is O(n) overhead.
Frankly i do not believe it is very interesting to switch between
different schedulers at runtime other than for testing purposes.
What _might_ be more interesting is to use multiple schedulers
in a hierarchical fashion, e.g. WFQ within each priority class,
or priority among threads or processes belonging to the same
scheduling entity (KSEG or process group).
Not that I am an advocate of that either, i generally prefer
flat structures.
cheers
luigi
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message |
|
| Back to top |
|
|
Bruce Evans
*nix forums Guru Wannabe
Joined: 22 Mar 2002
Posts: 190
|
| Posted: Wed Jul 17, 2002 1:26 pm Post subject:
Re: proposed changes to kern_switch.c and kern_synch.c
|
|
|
On Tue, 16 Jul 2002, Luigi Rizzo wrote:
| Quote: | we have implemented a weight-based process scheduler
for FreeBSD-stable, and are trying to port it to -current (in the
description below replace "process" with "thread/kse" as appropriate
for the -current case).
In order to make this work, it is convenient to have all
scheduler-specific functions and data structures in a
single file (kern_switch*.c), and generic support in
another one (kern_synch.c). I believe this was also the original
BSD design in partitioning the code between the two files.
However, in our current code, there are some functions which
are scheduler-specific (see below) which are misplaced.
|
This move would be sort of backwards IMO. As has been pointed
out, the original BSD design is nothing like that. Almost everything
related to scheduling was in kern_synch.c. I think of kern_synch.c
is being mainly for scheduling (and sleeping), and wouldn't like
to see the scheduling stuff moved out of it, especially to
kern_switch.c. Moving mi_switch() to kern_switch.c would be OK.
My viewpoint may be colored by having 902 lines of diffs (-c2) for
kern_synch.c including about 100 lines of bug fixes and 300 lines
of scheduler changes. (Latest breakage: running processes are
classified as sleeping and not scheduled. Scheduling is not very
important, so even huge bugs like this go unnoticed.)
| Quote: | So I would like to make the following, purely cosmetic, change
identified as step #1 below, both for consistency with what i
believe to be the original design, and to simplify further work
in this area. These would go to both -current and -stable; I
repeat, they are only cosmetic changes.
...
Step #1 is basically a cosmetic change, requiring mostly a move of
some functions from kern_synch.c to kern_switch.c. These are
roundrobin();
curpriority_cmp();
|
curpriority_cmp() doesn't exist in -current and shouldn't be reintroduced.
It is part of maybe_resched() in -current. I think that this function
and most of the things now in kern_switch.c should not be scheduler-dependent.
Each scheduler can manage priorities and let common code choose the
process with highest priority. If you want a different priority scheme
then you would need to change much more, especially in -current where
there is priority-propagation stuff that depends on linear priorities
to work.
| Quote: |
resetpriority();
parts of schedcpu() and schedclock();
|
Why not all of these functions? schedcpu() is almost empty after the
move. Each scheduler can easily duplicate this part (or maybe not have
it).
Bruce
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message |
|
| Back to top |
|
|
Robert Watson
*nix forums Guru Wannabe
Joined: 22 Mar 2002
Posts: 218
|
| Posted: Wed Jul 17, 2002 2:12 pm Post subject:
Re: proposed changes to kern_switch.c and kern_synch.c
|
|
|
I'm very excited about the idea of a more flexible scheduler interface, as
having that tends to encourage scheduler research. The main cautions I
have are:
(1) In introducing flexibility, be careful to avoid unnecessary costs. In
particular, the notion of changing the scheduler at run-time is cool,
but not if it involves introducing scary new locks. Being able to
support introducing flexible new scheduling algorithms at boot time is
very appealing, though.
(2) Currently the MD code speaks a few specific MI-defined data structures
in the scheduling code. In a move towards a more flexible mechanism
for specifying scheduling behavior, hammering down the details of what
exactly can and cannot be modified at the C level, and what the
assembly code is and is not permitted to assume, is probably a useful
piece of this work.
Robert N M Watson FreeBSD Core Team, TrustedBSD Projects
robert@fledge.watson.org Network Associates Laboratories
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message |
|
| Back to top |
|
|
Terry Lambert
*nix forums Guru
Joined: 19 Mar 2002
Posts: 434
|
| Posted: Wed Jul 17, 2002 4:25 pm Post subject:
Re: proposed changes to kern_switch.c and kern_synch.c
|
|
|
Lars Eggert wrote:
| Quote: | i don't know much on the lottery scheduler, but it looks like it
is probabilistic as opposed to deterministic. The paper on lottery
scheduling claims to have the same O(log N) complexity as WF2Q+
(though i haven't looked at the implementation issues).
Ah, so it's more like Waldspurger's later stride scheduler than his
lottery scheduler.
|
Just a "head's up":
The thing you are comparing to the stride scheduler is Luigi's first
impression of the lottery scheduler, not his weighted scheduler.
Luigi's comment was directed to the lottery scheduler you referenced,
not to the weighted scheduler. His comparative perspective is based
on his own work, not on the work you are referencing. Next time you
ask someone to "compare A and B", you may want to be careful to make
sure that they are telling you how A differs from B, rather than how
B differs from A.
;^).
-- Terry
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message |
|
| Back to top |
|
|
John Baldwin
*nix forums Guru Wannabe
Joined: 27 Mar 2002
Posts: 278
|
| Posted: Wed Jul 17, 2002 5:36 pm Post subject:
RE: proposed changes to kern_switch.c and kern_synch.c
|
|
|
On 17-Jul-2002 Luigi Rizzo wrote:
| Quote: | Hi,
we have implemented a weight-based process scheduler
for FreeBSD-stable, and are trying to port it to -current (in the
description below replace "process" with "thread/kse" as appropriate
for the -current case).
|
Unfortunately, the differences between -current and -stable in this area
aren't that simple. I think while developing on this on -stable is fine,
trying to retrofit those changes into -current will be fairly hard. Mostly
because you basically need to rewrite a lot of it. The current scheduler
is still very much a work in progress and I think we need to not try to do
too many things at once. Some remaining issues that I think need to be
done first before we look into this:
- Finish up KSE changes
- Really make the scheduler fully preemptive
- Get rid of schedcpu() in favor of event-driven priority updates somewhat
similar to SVR4 as described in Unix Internals
- A few other simplifications would be to have things like turnstiles and
generic sleep queues shared between at least cv's and sleep/wakeup,
possibly with turnstiles as well.
Some other notes: I think kern_switch.c should just contain the code to
support processor runqueues and possibly mi_switch().
| Quote: | 3. implement a function which, under control of a sysctl call,
activate a new scheduler (by initialising all the function
pointers to appropriate values) and moves all processes from
the old to the new one.
|
In SVR4 different processes could be in different scheduling classes that
could cooperate with each other. I think that is a better long-term
design goal then requiring switch-overs.
--
John Baldwin <jhb@FreeBSD.org> <>< http://www.FreeBSD.org/~jhb/
"Power Users Use the Power to Serve!" - http://www.FreeBSD.org/
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message |
|
| Back to top |
|
|
Lars Eggert
*nix forums beginner
Joined: 18 May 2002
Posts: 6
|
| Posted: Wed Jul 17, 2002 10:09 pm Post subject:
Re: proposed changes to kern_switch.c and kern_synch.c
|
|
|
Luigi Rizzo wrote:
| Quote: | it is basically the WF2Q+ algorithm used in dummynet (i am the king
of recycling . The OS community calls this "Proportional Share"
or something like that.
|
Since it sounds similar, what are the key differences to the lottery
scheduler
(http://www.csua.berkeley.edu/computing/software/lottery-sched.html)?
Lars
--
Lars Eggert <larse@isi.edu> USC Information Sciences Institute |
|
| Back to top |
|
|
Lars Eggert
*nix forums beginner
Joined: 18 May 2002
Posts: 6
|
| Posted: Thu Jul 18, 2002 1:08 am Post subject:
Re: proposed changes to kern_switch.c and kern_synch.c
|
|
|
Luigi Rizzo wrote:
| Quote: | Since it sounds similar, what are the key differences to the lottery
scheduler
(http://www.csua.berkeley.edu/computing/software/lottery-sched.html)?
i don't know much on the lottery scheduler, but it looks like it
is probabilistic as opposed to deterministic. The paper on lottery
scheduling claims to have the same O(log N) complexity as WF2Q+
(though i haven't looked at the implementation issues).
|
Ah, so it's more like Waldspurger's later stride scheduler than his
lottery scheduler.
| Quote: | In any case, one of the good things of our work is that it provides
a framework for replacing the standard scheduler with another one
with minimal interaction with the rest of the system, being all
code and data structures confined in a private file/data structures.
|
I agree; that sounds useful.
Thanks for the info,
Lars
--
Lars Eggert <larse@isi.edu> USC Information Sciences Institute |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Thu Jan 08, 2009 5:42 am | All times are GMT
|
|
Credit Counseling | Bankruptcy | Personal Finance | Remortgages | Credit Counseling
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
|
|
Other DeniX Solutions sites:
Unix/Linux blog |
electronics forum |
medicine forum |
science forum |
|
|
Privacy Policy
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
*nix
»
BSD
»
FreeBSD
»
mail-lists
»
Architecture
