Date: Tue, 13 Nov 2001 16:44:26 -0800 (PST) From: Julian Elischer <julian@elischer.org> To: Glenn Gombert <ggombert@imatowns.com> Cc: arch@freebsd.org Subject: RE: Thread scheduling in the kernel Message-ID: <Pine.BSF.4.21.0111131614160.298-100000@InterJet.elischer.org> In-Reply-To: <3.0.6.32.20011113163004.009803c0@imatowns.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Tue, 13 Nov 2001, Glenn Gombert wrote: > > Well, that's cause I think that there are some basic things that need t= o be > > decided before we can make the decisisons at the bottom of your e-mail.= I > > think the first thing is that priorities need to be decided. The real > question > > there is do we want per-thread priorities or per-ksegroup priorities? = If > you > > go totally with per-thread priorities which you seem to be favoring now= and > > just use ksegroup for nice and fixed priorities, then that makes kse gr= oups > > simpler at the expense of complicating KSE scheduling. :) >=20 > Is not a KSE 'bound' to a particular CPU, with each thread in the KSE > given a specific amount of time by the kernel scheduler ??. how does > the UTS play in this (other than to sleep and wakeup threads) =85 Threads become runnable when whatever they were blocking on allows them to run. A KSE (this still open to discussion) becomes runnable when there is at least one runnable thread that it could provide cycles to. The KSE may not be bound to a single processor (though it MIGHT be) but just able to hop in to take any cycles on any CPU available. (actually since threads can migrate between KSEs in the same group, they are actually equivalent, so you might select the KSE that was last on this processor if you wanted, but it may not gain you much.) you could put the KSEGRP on the run queue but hte difficulty comes with=20 the accounting. If you take it off to run a KSE on it's behalf, then what happens if another processor becomes available...? It's not on the=20 run queue.. so even though it may be able to use the extra horsepower it isn't going to be asked.. If it stays on the run queue head until it has run out of threads, then it may never leave the head, as new threads may continually be coming available. By puting KSEs on the run queues and removing them when they are run, you can ensure that when their quantum is completed, they are placed back onto the queue at the tail end.. there are aother answers to theses problems.. that's what we need to discuss..=20 "who has priority?" - it seems clear there is a component from both the=20 =09thread and the KSEGRP.. selected by the KSE.. "how do we do the queueing to maintain fairness and resposiveness" =09- I think by queueing KSEs but hopefully someone else =09has a REALLY SNEAKY and CUTE solution :-) >=20 > > If we let each thread have a priority and maintain its own scheduling > > parameters then I would be tempted to put threads on the runqueue's > rather than > > kse's primarily because you then have the problem of having to go updat= e the > > priorities of KSE's all the time when thread priorites change. And sin= ce > you > > want a thread to run as soon as its priority allows, this means changig= n the > > prioritiy of all KSE's in its group so it gets to run on the first one = that >=20 > what is the mechanism for this (kernel scheduling ) or does the UTS > become involve as well ? What is the impact on performance (if > re-scheduling is done on a per-thread basis)=85 >=20 >=20 > > becomes available. This would point to a single priority in the KSE > group that > > all KSE's share that is the highest priority of all runnable threads. = If > the > > list of runnable threads in the KSE group is priority sorted (as it > should be) > > this isn't but so difficult as you look at the priority of the thread a= t the > > head of the list. However, every time that priority changes, you have = to go > > shuffle KSE's around on the queue's potentially, rather than just movin= g > that > > one thread around on the queue's (or putting it on the queue as the cas= e may > > be). >=20 > Is not time allocated between Threads in a KSE based upon the total > amount of time available to the KSE.. if it is not this way , does not > Threads associated with a particular application gain an 'unfair' > advantage when it come to running =85 Fairness is a very important criteria. Time is allocatged between therads in a KSE in a priority order, with no real pre-emption between them. We are in the kernel. We control the code.. We can be sure that within the kernel, codepaths are short before a "completion" of some sort occurs. (Even if that event is actually the thread re-blocking). When all kernel activity has completed, teh UTS can be called.. I cannot imagine that it would be wise to call teh UTS when there are still runnable threads stuck in a semi-completed state within the kernel. >=20 > > One comment about preemption: probably what we will go with is only > preempting > > for real time threads (including interrupt threads) and not preempt tim= e > > sharing threads until their quantum is up or they block. The entire > concept of > > KSE's as I understand it, is to serve as a holder for the quantum so th= at we > > can give a multithreaded process it's full quantum each go-around even = if > > threads block in which case we split it across multiple threads. In th= at > case, > > I think this might be a resonable model: >=20 >=20 > > I think this will achieve the desired goal of a KSE (preserve quanta fo= r > > multithreading time-sharing processes across threads) while still allow= ing > > things like priority propagation and preemption to work smoothly. It's= also > > fairly simple. >=20 >=20 >=20 > > If you use a priority bias for affinity, then that means you basically > have a > > constant, say 4 (that is random, prolly not the real value) then you wi= ll > > basically artificially bump the priority of threads with lastcpu =3D=3D= cpuid > by 4 > > during your comparison. This means you can stop walking the ksegroup > list of > > threads when you hit a thread whose priority is more than 4 levels less= than > > that of the highest priority thread. Also, the first thread you hit th= at > meets > > the affinity requirement is the one you run, this should keep a (hopefu= lly) > > decent bound on the amount of list walking done. >=20 > If KSE's are bound to a particular CPU, how does this affect KSE's & > Threads on different CPU' Threads are like water. They flow between any available KSEs for their KSEGRP. (with a slight preference for one on their last processor) KSEs from the same KSEGRP have the same priority and can therefore never pre-empt each other on the same processor, this it makes no sense to have more of them than there are processors. Binding them to procesors is also dubious.. if KSE A runs on processor A, then KSE B must run on Processor B unless it is already busy. If KSE A finishes, abd processor B is still busy, then KSE B can run on procesor A, but this si functionally identical to the case where the 3rd KSE (that was keeping B busy) finished and KSE ran on processor B, since both KSE A and KSE B are drawing from the same pool opf runnable threads.. It MAY make some small sense to say "Hey that KSEGRP has another quantum and since Processor B is busy, we'll run the KSE for Processor A again, in KSE B's place" but there is no real gain in doing so. One case to consider is as follows: KSE A is running at raised priority '3' (1 is more priority) because it is running a thread (T) that holds a mutex needed by a high priority process. Thread (S) becomes runnable at a higher priority(2). If there is a KSE (B) for that KSEGRP available, it is made runnable and its priority is set to (2). Is it possible that it might pre-empt the KSE from the same process group (A) on the same processor if there is a thread of priority (1) running on th eother procesor?. How is this differnt from pre-empting= =20 the thread (T) within (A), and running (S) wihtin (A) instead. This all needs thrashing out. and is what I'm trying to achieve here on -arch.. >=20 >=20 >=20 > To Unsubscribe: send mail to majordomo@FreeBSD.org > with "unsubscribe freebsd-arch" in the body of the message >=20 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.0111131614160.298-100000>