From owner-p4-projects Mon Jun 3 11:39:33 2002 Delivered-To: p4-projects@freebsd.org Received: by hub.freebsd.org (Postfix, from userid 32767) id CFCA837B400; Mon, 3 Jun 2002 11:39:24 -0700 (PDT) Delivered-To: perforce@freebsd.org Received: from freefall.freebsd.org (freefall.FreeBSD.org [216.136.204.21]) by hub.freebsd.org (Postfix) with ESMTP id E7FC237B404 for ; Mon, 3 Jun 2002 11:39:23 -0700 (PDT) Received: (from perforce@localhost) by freefall.freebsd.org (8.11.6/8.11.6) id g53IdN721188 for perforce@freebsd.org; Mon, 3 Jun 2002 11:39:23 -0700 (PDT) (envelope-from julian@freebsd.org) Date: Mon, 3 Jun 2002 11:39:23 -0700 (PDT) Message-Id: <200206031839.g53IdN721188@freefall.freebsd.org> X-Authentication-Warning: freefall.freebsd.org: perforce set sender to julian@freebsd.org using -f From: Julian Elischer Subject: PERFORCE change 12326 for review To: Perforce Change Reviews Sender: owner-p4-projects@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG 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 #include #include To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe p4-projects" in the body of the message