Date: Mon, 3 Jun 2002 11:39:23 -0700 (PDT) From: Julian Elischer <julian@FreeBSD.org> To: Perforce Change Reviews <perforce@freebsd.org> Subject: PERFORCE change 12326 for review Message-ID: <200206031839.g53IdN721188@freefall.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://people.freebsd.org/~peter/p4db/chv.cgi?CH=12326 Change 12326 by julian@julian_ref on 2002/06/03 11:39:10 add a comment describing what we are trying to do. Affected files ... ... //depot/projects/kse/sys/kern/kern_switch.c#48 edit Differences ... ==== //depot/projects/kse/sys/kern/kern_switch.c#48 (text+ko) ==== @@ -26,6 +26,69 @@ * $FreeBSD: src/sys/kern/kern_switch.c,v 1.27 2002/05/25 01:12:23 jake Exp $ */ +/*** + +Here is the logic.. + +If there are N processors, then there are at most N KSEs (kernel +schedulable entities) working to process threads that belong to a +KSEGOUP (kg). If there are X of these KSEs actually running at the +moment in question, then there are at most M (N-X) of these KSEs on +the run queue, as running KSEs are not on the queue. + +Runnable threads are queued off the KSEGROUP in priority order. +If there are M or more threads runnable, the top M threads +(by priority) are 'preassigned' to the M KSEs not running. The KSEs take +their priority from those threads and are put on the run queue. + +The last thread that had a priority high enough to have a KSE associated +with it, AND IS ON THE RUN QUEUE is pointed to by +kg->kg_last_assigned. If no threads queued off the KSEGROUP have KSEs +assigned as all the available KSEs are activly running, or because there +are no threads queued, that pointer is NULL. + +When a KSE is removed from the run queue to become runnable, We know +it was associated with the highest priority thread in the queue (at the head +of the queue). If it is also the last assigned, that pointer must be +removed from it. Since it was the last assigned, we know there were no more +KSEs available, (M was 1 and is now 0) and since we are not FREEING our KSE +but using it, we know there are STILL no more KSEs available, we can prove +that the next thread in the ksegrp list will not have a KSE to assign to +it, so we can show that the pointer must be made 'invalid' because there +are now NO threads on the list that are assigned a KSE. + +The pointer exists so that when a new threasd is made runnable, it can +have it's priority compared with the last assigned thread to see if +it should 'steal' it's KSE or not.. i.e. is it 'earlier' +on the list than that thread or later.. If it's earlier, then th e KSE is +removed from the last assigned (which is now not assigned a KSE) +and reassigned to the new thread, which is placed earlier in the list. +The pointer is then backed up to the previous thread (which may or may not +be the new thread. + +When a thread sleeps or is removed, the KSE becomes available and if there +are queued threads that are not assigned KSEs, the highest priority one of +them is assigned the KSE, which is then placed back on the run queue at +the approipriate place, and the kg->kg_last_assigned pointer is adjusted down +to point to it. + +The following diagram shows 2 KSEs and 3 threads from a single process. + + RUNQ: --->KSE---KSE--... (KSEs queued at priorities from threads) + \ \____ + \ \ + KSEGROUP---thread--thread--thread (queued in priority order) + \ / + \_______________/ + (last_assigned) + +The result of this scheme is that the M available KSEs are always +queued at the priorities they have inherrited from the M highest priority +threads for that KSEGROUP. If this situation changes, the KSEs are +reassigned to keep this true. + +*/ + #include <sys/param.h> #include <sys/systm.h> #include <sys/kernel.h> To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe p4-projects" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200206031839.g53IdN721188>