Date: Sun, 26 Nov 2000 16:37:49 -0500 (EST) From: Daniel Eischen <eischen@vigrid.com> To: Julian Elischer <julian@elischer.org> Cc: arch@FreeBSD.ORG, jasone@FreeBSD.ORG Subject: Re: Threads (KSE etc) comments Message-ID: <Pine.SUN.3.91.1001126162942.20005A-100000@pcnet1.pcnet.com> In-Reply-To: <3A211C82.2464D07E@elischer.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Sun, 26 Nov 2000, Julian Elischer wrote:
> Where's jasone? He's been perculiarly silent during this....
>
> There has been some discussion as to what the function of the KSEG
> is....
>
> I was shaving today (doesn't the best thinkin happen at such times?)
> and thinking about why we needed KSEGs.
>
> The basic answer is,
>
> "We need some method by which we group the scheduled entities
> so as to be able to ensure that the scheduler has full
> information and control over what is going on."
Which scheduler - the UTS or the kernel sheduler? The UTS need
not know about KSEGs, except if that is the only way to get a
quantum.
> Whether we actually need a KSEG and what it does depends upon what
> semantics we want our threading support to have. If we want to provide a
> virtual machine for the process, that looks as if it has an unlimited
> number of virtual processors, then we allow the KSEG to spawn an
> unlimited number of KSEs. In this case, do we allow the "scheduling
> clout" to build up linearly with the number of KSEs or do we limit it in
> some way? Theoretically you would want a KSEG with two KSEs to have the
> same clout as a process running unthreaded, so that cpu time would be
> divided 50-50. However this would mean assigning the threaded process
> 'partial quantum' for each processor.
>
> By this I mean that after 5 ticks the KSE on each processor for the KSE
> would be interrupted and the other process allowed to run. This is
> unworkable. Another way of sharing the processors between the two
> processors would be to schedule bith KSEs on one process and allow the
> other process to run uninterrupted on the other. This is also quite
> unworkable - what if there are three competing processes and only 2
> processors?
>
> Maybe this 'exact fairness' is too hard to achieve..
>
> In my world, we allow the KSEG to become SLIGHTLTY unfair, by allowing
> it to compete independently on each processor. If we allow the KSEG to
> have an unlimited number of KSEs then we need some other item that
> competes on behalf of the KSEG on each processor. That is, we invent
> some other structure (KSEG-agent) that sits in the scheduling queue(s)
I like Terry's usage of "scheduler reservation" which includes quantum
and priority.
> on behalf of the KSEG. When the 'agent' gets a quantum, it allows the
> KSEG to decide which of it's KSEGs will be run next. (The KSEG could
^^^^^ KSEs
> round robin them for example).
If you are going to afford N quantum (for N CPUs) to a KSE, then it
doesn't make sense to have more than N KSEs within that KSEG. From the
UTS point of view, I will not attempt to create/ask for more than N
KSEs. Let's ignore this case.
>
> When a KSE is pre-empted, the kernel saves state for that thread in the
> thread-control-block and the next KSE to upcall to the UTS will include
> that thread-control-block in its list of reportable entities. I'm not
> clear on whether it's the next upcall on ANY KSE, or just the next
> upcall on that KSE.
It has to be on the next KSE, otherwise there will be too much
latency (possibly priority inversion) for RT threads if they are
being blocked by a preempted thread. For instance if a thread is
within a critical region and the KSE on which it is running is
preempted, and the next KSE to execute is running in RT (it's a
scope system thread). The RT KSE must get notification of the
preemption so it can resume the thread that was preempted long
enough for it to leave the critical region. It should also be
noted that without notification that the RT KSE cannot determine
which thread is blocking it. At the minimum, the RT KSE must be
able to search all the other KSE mailboxes to find the thread
that is blocking it. You also have read-write hazards that have
to be avoided (what happens when the preempted KSE is resumed
on another processor while the RT KSE is resuming the preempted
thread?). One idea I had was that the RT KSE (in this case) would
issue a system call to halt resumption of preempted KSE. It would
then resume the preempted thread until it leaves the critical
region, updates the preempted KSEs mailbox, and issues another
system call to release the preempted KSE. Critical regions are
very brief so this would not be an often occurrence.
Anyway, these problems really have to be worked out. I really want
this to work well with a mix of RT and non-RT threads. You could
have the same problem with threads of the same scheduling class
and it would be possible that no KSE makes any progress until the
preempted KSE gets its turn to run again.
> If the latter then having multiple KSEs on the same processor, allows
> the KSEG round-robin scheduler to make the UTS believe that it has N
> virtual processors, (N-KSEs). However, it also means that the KSEG
> round-robin scheduler is usurping the decision from the UTS as to which
> thread is to be run next, as the UTS doesn't know that the thread on the
> other KSE was pre-empted in favour of this one. (It's on a different
> virtual CPU).
It has to know. See above.
>
> If the Former (All KSEs report all events) then there is no real
> advantage to having more than N KSEs (N processors), because that means
> that the UTS will probably keep swapping the threads it thinks are most
> important to the KSEs which means that the thread that was pre-empted on
> KSE-A will probably be re-scheduled on KSE-B when it preempts KSE-A. So
> why have KSE-B at all? All it does is massively confuse things, and
> creates a whole new class of scheduling problems.
I am going to assume that you are talking about KSEs that have their
own scheduling quantum (I agree that it doesn't make sense to have
more than N KSEs if they don't have their own quantum). What has
gone unasked is "what is the application interface to allow creation
of KSEs, quantum, thread/kse/processor binding?". Let's look at
it from the UTS and application interface point of view. Let's also
ignore scope system threads; they are uninteresting since we know
how they are scheduled. So the question now is how are scope process
threads scheduled and what API is presented to the application?
I am in the middle of writing up my notes on this topic, and will post
them when I'm done. But a brief synopsis is that we want to allow
the application to bind scope process threads to a specific KSE, bind
KSEs to a specific processor, and to allow creation of additional
quantum (KSEs or KSEGs, subject to limitations of course). This
allows the application to decide how threads are scheduled. If a
thread is bound to a specific KSE, then it is not rescheduled on
another KSE when it is preempted (unless it is in a critical region).
If a thread is not bound to a specific KSE and it is preempted, then
the UTS could decide to only reschedule it on the next KSE to execute
if there were no other threads of greator or equal priority. The
UTS could also decide not to reschedule it regardless; this gets
into what scheduling allocation domain we are using. For scheduling
allocation domains > 1, it is valid (perhaps against POLA) to have
multiple scheduling queues. I submit that it is difficult for the
UTS to decide how to (soft or hard) bind threads to KSEs -- perhaps
we want to try to do this in the future, but let's keep it simple
for now. Let the application decide how threads are bound to KSEs
and how much quantum (KSEs or KSEGs) it wants. This makes it much
easier for the UTS and doesn't "massively confuse things".
> So, in summary:
> Assuming we allow only SLIGHT unfairness, if you allow the process to
> have more than N KSEs in a KSEG, you have one of the following:
> 1/ A lot of unfairness if you allow each KSE to be in the queues by
> itself.
No more than LinuxThreads or fork()'d processes. Again, this can
be limited just as there is a user process limit. I don't see this
as a problem.
> 2/ The KSEG scheduler usurping the role of the UTS if it really does
> hide the true number of processors.
> 3/ An increased level of UTS complexity, and un-needed work, as the UTS
> struggles to switch the important threads onto the ever-changing set of
> running KSEs (it must be ever changing because there are more of them
> than CPUs).
Not really true. I've addressed this above.
> If you only allow N KSEs to the KSEG, then all these problems go away.
> The UTS can be aware that it has a limit. But it can also be aware that
> a KSE will not be re-empted by another of it's own KSEs. (this
> simplifies things). It gets the same amount of
> CPU-time, but has less work to do. It has full control of which threads
> are running,
> and competes fairly with other processes and KSEGs.
Whether there are N or N+d KSEs, it makes no difference to the UTS.
The same problem of scheduling scope process threads over more than
1 KSE exists; it is no more difficult or simple with a limit of N
KSEs.
> The reason for having KSEGs is simply as an entity that competes for CPU
> to assure fairness.
My argument is that if you assign the quantum (and priority) to the
KSE, then the _KSE_ is the entity that competes for CPU fairness. There
is no visible advantage to me of having a KSEG, especially forcing
knowledge of this to the UTS when it doesn't really care.
> It may not even exist as a separate structure in the case where there
> are separate per-CPU scheduling queues, (though I think it would for
> efficiency's sake). It would PROBABLY have a analogous partner in the
> UTS that represents the virtual machine that runs all the threads that
> are competing at the same scope. On a single scheduling queue system, I
> think I would have the KSEG in the queue rather than the independent
> KSEs. When it get's to the head, you schedule
> KSEs on all the CPUs. This allows the threads to communicate quickly
> using shared memory should they want. The UTS has the entire quantum
> across as many CPUs as it has.
I'm confused. Now you seem to be advocating having multiple KSEs
with one quantum.
> I hope that his answers some of the questions as to why I think there
> are reasons for having the KSEG entity.
I am not convinced :-) I think we need to look more closely at what
the UTS needs and what API (both POSIX and non-POSIX) is needed/desired.
My point is that the UTS doesn't need to know about the KSEG. If that's
the only way to get a quantum, then I guess it'll be forced to know
about it. But also keep in mind that the UTS could also create a
KSEG just as easily as a KSE in order to provide additional quantum.
It already has to do this for system scope threads.
--
"Some folks are into open source, but me, I'm into open bar."
-- Spencer F. Katt
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.SUN.3.91.1001126162942.20005A-100000>