Date: Wed, 21 Nov 2001 19:48:16 -0800 (PST) From: John Baldwin <jhb@FreeBSD.org> To: Julian Elischer <julian@elischer.org> Cc: arch@freebsd.org Subject: RE: Kernel Thread scheduler Message-ID: <XFMail.011121194816.jhb@FreeBSD.org> In-Reply-To: <Pine.BSF.4.21.0111211208410.35591-100000@InterJet.elischer.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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 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-- " > > 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. :) > 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?XFMail.011121194816.jhb>