Date: Tue, 13 Nov 2001 16:13:51 -0800 (PST) From: Julian Elischer <julian@elischer.org> To: Glenn Gombert <ggombert@imatowns.com> Cc: freebsd-arch@FreeBSD.org Subject: Re: freebsd-arch@FreeBSD.org Message-ID: <Pine.BSF.4.21.0111131533210.298-100000@InterJet.elischer.org> In-Reply-To: <3.0.6.32.20011113154711.009793e0@imatowns.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Tue, 13 Nov 2001, Glenn Gombert wrote:
> A couple of questions --
Ok, bu tremember this stuff is still under discussion so any answer give
here may be wrong :-)
>=20
> >1/ Since threads running a syscall hit 'sleep' events
> >the entities on teh sleep queues must be the threads.
>=20
> Will the sleep queues (which mix threads from multiple CPUs) impact
> performance as the number of threads dramatically increase ..
Not really.. For several reasons...
There are an awfull lot of sleep queues and they are manipulated using
O(1) operations. "Wakeup_one()" is also independent of the number of
entries, and we don't expect the average number of threads-per-process to
be much more than 1.
> > > 2/ the entity that is
scheduled onto the run queues is the KSE. > > (as the name suggests).
>=20
> Is there a number of threads per KSE that is optimum for
> performance? will this be impacted by the UpCalls that are made
> between the Kernel and User land..what determines the optimum number
> of threads to be created per KSE (before another one is created for a
> particular application)..
Up to a sane limit, the number of threads per KSE/KSEGROUP id unlimitted
and controlled by the UTS. The kernel will always ask the UTS it it has
another thread to run whenever the KSE discovers it has no work to do. The
UTS has the option of either runing a new thread, or retunring a 'yield()'
to the kernel.
>=20
> > 3/ If we have only one run queue, then KSEs for several processors=20
> > from the same process, may be on the same queue.
>=20
> > 4/ If threads 'wake up' they are hung of a list of runnable threads
> > somewhere. This list could be hanging off the process, or the KSE.
> > actually more likely the KSEgroup than the process but...)
>=20
> .. does not one process serve as a 'container' for one KSEG and
> multiple KSE and Threads ?? does this process share the time quanta
> between all its member(s) or is it the job of the UTS to make these
> type of decisions??
There is a one-to-many relationship on each step..
1 process to N KSE groups (a process may start several proces groups and
assign different scheduling characteristics for each)
1 KSEGRP to N KSEs (Each KSE can be used to reserve soem cycles on a
processor). It makes no sense to have more KSEs per KSEGRP than there are
processors.
1 KSEGRP to N threads.. In fact it makes no sense to have more active
KSEs than threads and there tends to be a thread assigned to each KSE
at minimum. (A yielded KSE may not have a thread assigned to it, but then
I said ACTIVE.. :-)
>=20
>=20
> > 5/ If a KSE reaches teh front of the queue, but the process
> > that is running is not that for which that KSE has some affinity,
> > does it get out of the way to allow another KSE in the queue
> > to get run? or does it just run and 'switch' everything over to the new
> > available processor? Maybe the scheduler looks for the KSE from the sam=
e
> > group, that was assigned to that processor, and runs that, leaving
> > the original KSE at the head of the queue?=20
> > Maybe that happens until all the KSEs in the queue
> > that were from that group have been run? In this case it becomes possib=
le
> > to always have a KSE from that group ready...
>=20
> Does the kernel scheduler make the decisions about scheduling (once a
> Thread has been created) ?..what is the relationship between the UTS
> and the Kernel Scheduler (from the standpoint of time allocation when
> it comes to Use's and individual threads)
The kernel shceduler decides what threads (which are currently IN THE
KERNEL) shuold be run, but as soon as control passes up to userland, the
UTS can decide which thread is run. The UTS can probably influence the=20
kernelscheduler's decision. Probably the rule "All threads in the kernel
have priority over all threads in the userland" will be the default
behaviour, though we might be able to adjust this on a per KSEGRP basis.
If we can think of an alternative..
The result of this woudl be that on teh starting of a scheduler quantum
all runnable completing syscalls would be completed before the upcall is
made to the UTS. The UTS can then select which of the returned threads
it wants to run...
>=20
> > Maybe the KSE-GROUP is what is put unto the run queue, and KSEs from th=
at
> > group are put on all processors that look for work, until all of them=
=20
> > have been run? (this would ensure that threads from the same process
> > would all be run at the same time which is sometimes good, and sometime=
s
> > bad, depending on the application.
>=20
> How is the time quanta divided up between KSE's and Threads ??=85who mak=
es
> the decision when each should be placed on the runqueue and run at a
> particular time when the responsibility is devided up between the UTS and
> kernel scheduler=85
^^^
what's with the ^E's??
A KSE get's a quantum when it's active priority is the highest among
runnable KSEs. It will run each thread it has until completion, in turn.
In this case "completion" is one of:
1/ returns to userland
2/ blocks
3/ self destructs
4/ quantum ends.
When it has no runnable threads in the kernel to do, then the next action
for the KSE is to upcal to the UTS.
>=20
> > 6/ When a Thread is made runnable it gets (in the present system) a
> > priority. What priority does a KSE in the run queues have when it has
> > threads of several differnt priorities? Do we sort them in priority ord=
er
> > and drop the priority of the KSE(group) as we go through them
> > until we have less priority than some other kse?
>=20
> > 7/ when a KSE runs out of work, how does it decide whether there is wor=
k
> > that should be stolen from a fellow KSE? How does processor affinity
> > effect this?
>=20
> Is a KSE not bound to a particular processor with the KSEG able to
> allocate resources between multiple processors?
This is open to debate. It makes no sense to have more KSEs than
processors. It may also be useful to bind a KSe to a particular processor.
Since threads can migrate between KSEs in the same KSEGRP, it may mean
that you's have to make a special KSEGRP with a single KSE to confine the
threads to a single CPU.
>=20
> > 8/ If we had per-processor scheduling queues, How would that effect it?
> > Which element get's put on the queues? Does a KSE
> > stay on the run queue if it has un=3Drun threads, even when it's runnin=
g?
> > How do we handle the arrival of new runnable threads with a KSE
> > when it's running but a fellow KSE is not runnable. Do we=20
> > bump the priority of the other KSE and hand it the new threads?
>=20
>=20
> > remember: here are the 4 structures:
>=20
> > proc - owner of all resources (FDs, memory, user creds) except cpu
>=20
> > Ksegroup - owner of all scheduler controlling characteristics
> > =09(e.g. nice, realtime, number of processors), N per process.
> > =09Owner of stats used for scheduling calculations.=09
>=20
> > kse -=09kind of a placeholder. It gets scheduled onto=20
> > =09a processor (by a yet un-named mechaninsm) and provides
> > =09cpu-cycles for the execution of 'threads' (see next).
> > =09Max. Of one per processor per KSE-group.
>=20
> > thread - The in-kernel incarnation of a user thread that is presently
> > =09in the kernel for some reason (e.g. syscall, pagefault, etc)
> > =09Holds ALL the state needed to resume after sleeping, and is the
> > =09entity that is suspended when the thread hits a 'sleep'.
> > =09"unlimmitted" per KSEgroup. probably have a short-term
> > =09"favourite" KSE/processor.
>=20
>=20
> What is the relationship between processors and processes?? Does not one
> KSEG distribute multiple KSE's between multiple CPU's?
Yes..
KSEs are the vehicle of concurancy, as they can be runnig at the same time
on different processors. Theoretically KSEs in the same KSEGRP should not
directly compete with each other as there can never be more of them than
there are procerssors. KSEs from a different KSEGRP compete in the same
way that processes now compete.
>=20
> > When a thread blocks, the KSE looks for another thread to run, and if i=
t
> > doesn't find one, it will create one, and upcall back to the=20
> > userland to see if there are more userland threads to run.
> > (if not, it returns to yield the processor)
>=20
> > The question that has been giving me headaches is the=20
> > relationship between these elements, and
> > the definitions of how these structures are linked up and moved
> > around to provide fair efficient scheduling.
>=20
> > If a KSE has a high priority thread and a low priority thread
> > runnable in the kernel, but in reverse order, should it take
> > the high priority from the higher prio. thread and process both,
> > or should it order the threads and run teh high prio one first.
> > In this case what happens whan a higher prio. thread becomes runnable
> > while one is already running, and if the highest prio thread returns to
> > userland, should teh processor move to userland to follow it, or
> > switch to the next priority thread in the kernel.?
> > Do all threads in the kernel have priority over all threads in userland=
?
> > (this might be a reasonable decision).
>=20
> Does the UTS have any input into the priority of how time is apportione=
d
> to each individual KSE / Thread in the kernel runqueue??..or is that
> entirely up to the kernel scheduler =85
The KSE is a placeholder to which quanta are assigned for the purpose of
running any available and runnable threads. If there are no runnable
threads (including the one in userland) teh KSE will not request any=20
cycles. The KSE applies for these cycles at the priority of the highest
priority thread waiting, where the priority
of the thread is a combination of inherrited priority and KSEGROUP-wide=20
general priority characteristics (e.g. nice, etc.).
Possibly, as the highest priority threads are "completed" teh priority of
the KSE may effectlively drop to that of the next highest thread.
It is conceivable that it may drop below that of a competing KSE, which
may under some circumstances produce a pre-emption.
(this is still under discussion). It's not completely obvious at which
point the UTS is called to allow processing in userland to continue, but I
suspect that it is when there are no more runnable threads in the kernel,
and there are no more KSEs of higher priority requesting CPU.
The question of whether the raised priority from IO that is present in
current UNIX systems should be carried over to the UTS when it finally
gets control, or whether it should be run at it's BASE priority.
Presently if you do IO, your process get's a bost in priority when the IO
completes to allow you to be quickly scheduled to process the results
of the IO quickly, and then request more IO (at which time you=20
probably sleep again). This is to help interactive processes vs.
batch proceses. It is not obvious what the right thing to do for=20
a UTS that has both batch and Interractive threads is....
>=20
> In general does the memory allocation/recrimination scheme seem adequate
> for all the KSE's/Threads that will be created and destroyed with the new
> implementation=85
>=20
>=20
>=20
> To Unsubscribe: send mail to majordomo@FreeBSD.org
> with "unsubscribe freebsd-arch" in the body of the message
>=20
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?Pine.BSF.4.21.0111131533210.298-100000>