Date: Wed, 21 Nov 2001 16:39:18 -0800 (PST) From: Julian Elischer <julian@elischer.org> To: arch@freebsd.org Subject: Kernel Thread scheduler Message-ID: <Pine.BSF.4.21.0111211208410.35591-100000@InterJet.elischer.org>
next in thread | raw e-mail | index | archive | help
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.) 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. 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..? 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?) julian 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.0111211208410.35591-100000>