Date: Thu, 22 Nov 2001 01:30:41 -0800 (PST) From: Julian Elischer <julian@elischer.org> To: John Baldwin <jhb@FreeBSD.org> Cc: arch@freebsd.org Subject: RE: Kernel Thread scheduler Message-ID: <Pine.BSF.4.21.0111220124220.41963-100000@InterJet.elischer.org> In-Reply-To: <XFMail.011121194816.jhb@FreeBSD.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Wed, 21 Nov 2001, John Baldwin wrote: > > On 22-Nov-01 Julian Elischer wrote: > > > > > > Peter, John (Baldwin) and I got to gether yesterday and thrashed > > out the mechanisms behind the KSE/thread scheduler. > > This allows us to go ahead and start coding again, now that we know what > > we are aiming at. > > > > Here is the basic mechanism. > > > > > > recap: > > "thread".. structure that is associated with a running context, running in > > the kernel.. has a stack, and storage for registers when blocked.. > > WHen a system call starts, the 'current' thread is used. WHen it blocks, a > > new one is created to return to the userland and collect more work. When > > the syscall finishes, the thread may be freed back rto a system wide pool > > of threads, unless it is the last one in the KSE, in which case it remains > > 'current' and in reserve for the next syscall. > > > > "KSE" (Kernel schedulable Entity). An entity that has cycles. It can spend > > them running one of the contexts in associated threads. It is to some > > extent a virtual CPU. > > > > "KSEGROUP" (KSEGRP). AN entity that represents a group of KSEs that, > > together share the same scheduling characteristics. There can only be at > > Maximum N KSEs in a KSEGRP, where N is the number of processors. KSEGRPs > > homd scheduling parameters and statistics. > > > > "Process" (proc). All resources and permissions are properties of the > > process. > > > > There can be 1 or more KSEGRPS per process. > > There can be 1 to N KSEs per KSEGRP. > > There can be 0 or more threads per KSEGRP at any time. > > > > > > Structures for scheduling: > > Threads aer owned by a KSEGRP. > > The KSEGRP has a list of all its runnable threads, sorted in priority > > order, > > The KSEGRP has a list of all its blocked threads. > > The KSEGRP has a list of KSEs. > > The first N runnable threads have a pointer to an assigned KSE. > > The assigned KSE is either on the run queue, or actuallly running that > > thread at that time. > > The KSE is on the run queue according to the priority of the thread > > which is currently assigned to it. (it has a back link to it too.) > > A ksegroup also has a pointer to the highest priority runnable thread w/o a > reserved KSE, which is important for when a running thread blocks and the KSE > needs to pick anotehr thread to run so that we know what thread to give to the > KSE that we steal the thread from. > I made a slight change to this in the pictures. (did you look at them yet? what do you think?) Instead of being a pointer to the next 'unassigned' thread, I made it a pointer to the "last assigned thread". It happens to fall out better in some cases. (e.g. you can find the last assigned thread when it is also the "last thread" as well.. If you used "first-unassigned" it would have to be NULL as all are assigned..) > > I have drawn up a set of pictures inllustrating the basic > > behaviour during thread scheduling.. > > > > they are at: > > http://www.freebsd.org/~julian/threads/ > > and are under the heading: > > "Pictures drawn in tgif of a KSE scheduling. -- Nov 21 2001-- " Have you looked at them? I think I covered all the points we discussed. > > > > Basically: As threads become runnable they are hung on the runnable > > queue for their KSEGRP, and if there are no runnable or running KSEs > > one is put on the system run queue. > > If the new thread is among the N highest priority threads, then > > teh lowest priority thread with an assigned (but not yet running) KSE > > is unassigned, and it's KSE is repositionned in the system run queue > > in a place suitable for the new thread. It is then assigned to that > > thread. > > Yep, that pointer above (which we did discuss, it was just missing > from your list. :) Yep, just slipped by.. (but it's in the pics which are much more descriptive.. (A picture is worth a thousand words so my 7 picures amount to about 21 pages of description :-) > > > Pre-emption of a running thread (normal timesharing-wise) by another > > thread in the same KSEGRP, when the running thread on a KSE either > > completes or blocks. However the KSE itself can be pre-empted by a higher > > priority KSE from a different process. > > > > In other words a thread of higher priority than the running thread, > > from the same group, will not pre-empt that running thread, but will > > move to the head of the queue to be 'next'. The priority > > of the running thread that would have been pre-emted might be bumped..? > > Nah. This is fine enough for time sharing threads. For real-time > threads preemption will be immediate. > > > There needs to be a way to stop the KSE assigned to the higher priority > > thread from pre-empting it's sibling, but rather, try run on another > > processor. (Is this needed? might something bad happen > > if it does pre-empt it?) (can you pre-empt a syscall in the kernel?) > > If the current KSE is always running the highest priority thread > available you don't have this. When you preempt due to a real time > thread becoming runnable, you just always preempt on the current CPU. > Trying to do IPI's to be perfect isn't worth the extra effort. > > -- > > 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 > 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.0111220124220.41963-100000>