Date: Tue, 13 Nov 2001 10:59:04 -0800 (PST) From: John Baldwin <jhb@FreeBSD.org> To: Julian Elischer <julian@elischer.org> Cc: arch@freebsd.org Subject: RE: Thread scheduling in the kernel Message-ID: <XFMail.011113105904.jhb@FreeBSD.org> In-Reply-To: <Pine.BSF.4.21.0111130929230.98845-100000@InterJet.elischer.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On 13-Nov-01 Julian Elischer wrote:
> (I notice you only comented on the first half, but that's a lot better
> than the complete lack of interest from everyone else.....)
Well, that's cause I think that there are some basic things that need to be
decided before we can make the decisisons at the bottom of your e-mail. I
think the first thing is that priorities need to be decided. The real question
there is do we want per-thread priorities or per-ksegroup priorities? If you
go totally with per-thread priorities which you seem to be favoring now and
just use ksegroup for nice and fixed priorities, then that makes kse groups
simpler at the expense of complicating KSE scheduling. :)
If we let each thread have a priority and maintain its own scheduling
parameters then I would be tempted to put threads on the runqueue's rather than
kse's primarily because you then have the problem of having to go update the
priorities of KSE's all the time when thread priorites change. And since you
want a thread to run as soon as its priority allows, this means changign the
prioritiy of all KSE's in its group so it gets to run on the first one that
becomes available. This would point to a single priority in the KSE group that
all KSE's share that is the highest priority of all runnable threads. If the
list of runnable threads in the KSE group is priority sorted (as it should be)
this isn't but so difficult as you look at the priority of the thread at the
head of the list. However, every time that priority changes, you have to go
shuffle KSE's around on the queue's potentially, rather than just moving that
one thread around on the queue's (or putting it on the queue as the case may
be).
One comment about preemption: probably what we will go with is only preempting
for real time threads (including interrupt threads) and not preempt time
sharing threads until their quantum is up or they block. The entire concept of
KSE's as I understand it, is to serve as a holder for the quantum so that we
can give a multithreaded process it's full quantum each go-around even if
threads block in which case we split it across multiple threads. In that case,
I think this might be a resonable model:
- Put threads on the runqueues.
- During choosethread, we use the following algorithm:
- If the highest priority thread is a time sharing or idle thread, our
current process is a KSE process, and we still have quantum left (I am
foreseeing a KEF_FORCESWITCH for forcing a KSE switch when quantum
expires) then we will look for another thread in this kse group in
priority order with a bias for threads that last run on the current
cpu for affinity purposes. This may mean that we don't run the strictly
highest priority thread in the system for the purposes of preserving
quanta for time-shared processes.
- Otherwise, we simply run the highest priority thread.
I think this will achieve the desired goal of a KSE (preserve quanta for
multithreading time-sharing processes across threads) while still allowing
things like priority propagation and preemption to work smoothly. It's also
fairly simple.
If you use a priority bias for affinity, then that means you basically have a
constant, say 4 (that is random, prolly not the real value) then you will
basically artificially bump the priority of threads with lastcpu == cpuid by 4
during your comparison. This means you can stop walking the ksegroup list of
threads when you hit a thread whose priority is more than 4 levels less than
that of the highest priority thread. Also, the first thread you hit that meets
the affinity requirement is the one you run, this should keep a (hopefully)
decent bound on the amount of list walking done.
--
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?XFMail.011113105904.jhb>