Date: Mon, 12 Nov 2001 16:24:29 -0800 (PST) From: John Baldwin <jhb@FreeBSD.org> To: Julian Elischer <julian@elischer.org> Cc: arch@freebsd.org Subject: RE: Thread scheduling in the kernel Message-ID: <XFMail.011112162429.jhb@FreeBSD.org> In-Reply-To: <Pine.BSF.4.21.0111121507240.94926-100000@InterJet.elischer.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On 12-Nov-01 Julian Elischer wrote: > > In an attempt to get the next part of the KSE work designed (design before > code you know.. a strange new concept) I've been trying to work out > the "correct" scheduling methods for such a system. > > There are a few 'tricks' that need to be taken into account.. > > a few notes.. > > > 1/ Since threads running a syscall hit 'sleep' events > the entities on teh sleep queues must be the threads. > > 2/ the entity that is scheduled onto the run queues is the KSE. > (as the name suggests). > > 3/ If we have only one run queue, then KSEs for several processors > from the same process, may be on the same queue. > > 4/ If threads 'wake up' they are hung of a list of runnable threads > somewhere. This list could be hanging off the process, or the KSE. > (actually more likely the KSEgroup than the process but...) It should hang off the group. > 5/ If a KSE reaches teh front of the queue, but the process > that is running is not that for which that KSE has some affinity, > does it get out of the way to allow another KSE in the queue > to get run? or does it just run and 'switch' everything over to the new > available processor? Maybe the scheduler looks for the KSE from the same > group, that was assigned to that processor, and runs that, leaving > the original KSE at the head of the queue? > Maybe that happens until all the KSEs in the queue > that were from that group have been run? In this case it becomes possible > to always have a KSE from that group ready... Actually, I would remove the concept of affinities from the KSE itself. Rather I would let each thread have lastcpu like it does now, and when a KSE goes to choose a thread, it chooses one that has the lastcpu == current cpuid. > Maybe the KSE-GROUP is what is put unto the run queue, and KSEs from that > group are put on all processors that look for work, until all of them > have been run? (this would ensure that threads from the same process > would all be run at the same time which is sometimes good, and sometimes > bad, depending on the application. I wouldn't do this. I would just put KSE's on the queue's. However, I think that KSE's actually can be even smaller than they are now. AFAICT they are basically placeholders to sit on the runqueue's and not good for much else. :) > 6/ When a Thread is made runnable it gets (in the present system) a > priority. What priority does a KSE in the run queues have when it has > threads of several differnt priorities? Do we sort them in priority order > and drop the priority of the KSE(group) as we go through them > until we have less priority than some other kse? Actually, in theory the prioities are supposed to be per-KSE group right? In that case, changign the priority of an individual thread for the purposes of priority propagation/inheritance or other shenanigans results in creating a new group for that thread. > 7/ when a KSE runs out of work, how does it decide whether there is work > that should be stolen from a fellow KSE? How does processor affinity > effect this? If the list is per-ksegroup, then you just make a first pass preferring threads that last ran on the current CPU. If you don't find anything, you just grab the first thing on the list. > 8/ If we had per-processor scheduling queues, How would that effect it? > Which element get's put on the queues? Does a KSE > stay on the run queue if it has un=run threads, even when it's running? > How do we handle the arrival of new runnable threads with a KSE > when it's running but a fellow KSE is not runnable. Do we > bump the priority of the other KSE and hand it the new threads? I'm not sure how this fits in that model unless you bind KSE's to CPU's or something similar. Only threads really have affinity, KSE's don't really care if they migrate as they have no execution context that gets affected. If the priorities are per-KSEgroup, then you get to assume that all threads in a group are equal in priority, which is true unless a particular thread temporiarly gets a bump from priority propagation or the process assigns a thread to a realtime priority or some such. -- John Baldwin <jhb@FreeBSD.org> -- http://www.FreeBSD.org/~jhb/ PGP Key: http://www.baldwin.cx/~john/pgpkey.asc "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.011112162429.jhb>