Date: Mon, 27 Nov 2000 15:48:00 -0800 From: Jason Evans <jasone@canonware.com> To: Julian Elischer <julian@elischer.org> Cc: arch@FreeBSD.ORG Subject: Re: Threads (KSE etc) comments Message-ID: <20001127154800.M4140@canonware.com> In-Reply-To: <3A211C82.2464D07E@elischer.org>; from julian@elischer.org on Sun, Nov 26, 2000 at 06:21:54AM -0800 References: <Pine.SUN.3.91.1001121160717.7102A-100000@pcnet1.pcnet.com> <3A1B0B64.6D694248@elischer.org> <3A211C82.2464D07E@elischer.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Sun, Nov 26, 2000 at 06:21:54AM -0800, Julian Elischer wrote: > There has been some discussion as to what the function of the KSEG > is.... > > [...] why we needed KSEGs. > The basic answer is, > > "We need some method by which we group the scheduled entities > so as to be able to ensure that the scheduler has full > information and control over what is going on." Yes. > Whether we actually need a KSEG and what it does depends upon what > semantics we want our threading support to have. If we want to provide a > virtual machine for the process, that looks as if it has an unlimited > number of virtual processors, then we allow the KSEG to spawn an > unlimited number of KSEs. In this case, do we allow the "scheduling > clout" to build up linearly with the number of KSEs or do we limit it in > some way? Theoretically you would want a KSEG with two KSEs to have the > same clout as a process running unthreaded, so that cpu time would be > divided 50-50. However this would mean assigning the threaded process > 'partial quantum' for each processor. There shouldn't be a need for assigning partial quanta. In the case of a single-threaded process, A, and a multi-threaded process B, on a 2 processor machine, B may initially get ~75% of the CPU resources. However, re-prioritization will notice this and lower the priority of B after a short period of time (4 ticks or so). > Maybe this 'exact fairness' is too hard to achieve.. IMO, the existing priority adjustment mechanisms are probably adequate. > When a KSE is pre-empted, the kernel saves state for that thread in the > thread-control-block and the next KSE to upcall to the UTS will include > that thread-control-block in its list of reportable entities. I'm not > clear on whether it's the next upcall on ANY KSE, or just the next > upcall on that KSE.. I think it should be the next upcall on any KSE. > If the latter then having multiple KSEs on the same processor, allows > the KSEG round-robin scheduler to make the UTS believe that it has N > virtual processors, (N-KSEs). However, it also means that the KSEG > round-robin scheduler is usurping the decision from the UTS as to which > thread is to be run next, as the UTS doesn't know that the thread on the > other KSE was pre-empted in favour of this one. (It's on a different > virtual CPU). I don't understand how we're usurping the UTS's scheduling decisions. If a KSE is preempted, then an upcall (resulting in yet another preemption, if necessary) must be done right away in order to give the UTS enough information to correctly schedule threads on the KSEs that are still running. This is one of the basic tenets of scheduler activations, which we really have to follow. > If the Former (All KSEs report all events) then there is no real > advantage to having more than N KSEs (N processors), because that means > that the UTS will probably keep swapping the threads it thinks are most > important to the KSEs which means that the thread that was pre-empted on > KSE-A will probably be re-scheduled on KSE-B when it preempts KSE-A. So > why have KSE-B at all? All it does is massively confuse things, and > creates a whole new class of scheduling problems. The main advantage I see of allowing more KSEs than processors (total across all KSEGs) is that it simplifies the implementation considerably. Very little has to be changed about how things currently work, which also means that single-threaded applications work the same as they do now, without a lot of extra work. I agree that there's no good reason to have more KSEs in a KSEG than there are processors, but it doesn't actually break anything to allow this, and simply using process resource limits to control the number of KSEs is simpler than enforcing limits on the number of KSEs per KSEG. One example of why enforcing KSE/KSEG limits could become hard in the future is if the number of processors is dynamic (i.e. processors can be added and removed). In discussions I've had with Mike Smith, this is a very real possibility, and is something we should keep in mind. > So, in summary: > Assuming we allow only SLIGHT unfairness, if you allow the process to > have more than N KSEs in a KSEG, you have one of the following: > 1/ A lot of unfairness if you allow each KSE to be in the queues by > itself. Why is there unfairness? Scheduler re-prioritization should prevent long-term unfairness just fine. > 2/ The KSEG scheduler usurping the role of the UTS if it really does > hide the true number of processors. We shouldn't be hiding the true number of processors. > 3/ An increased level of UTS complexity, and un-needed work, as the UTS > struggles to switch the important threads onto the ever-changing set of > running KSEs (it must be ever changing because there are more of them > than CPUs). The UTS doesn't need to be any more complex. It would simply get more upcalls if there were more preemptions as a result of excessive KSEs, which I don't think would happen anyway. > The reason for having KSEGs is simply as an entity that competes for CPU > to assure fairness. > It may not even exist as a separate structure in the case where there > are separate per-CPU scheduling queues, (though I think it would for > efficiency's sake). It would PROBABLY have a analogous partner in the > UTS that represents the virtual machine that runs all the threads that > are competing at the same scope. I agree with everything you say here. > On a single scheduling queue system, I > think I would have the KSEG in the queue rather than the independent > KSEs. When it get's to the head, you schedule > KSEs on all the CPUs. This allows the threads to communicate quickly > using shared memory should they want. The UTS has the entire quantum > across as many CPUs as it has. As I mentioned in another email, I don't think we should plan on having a production release that is implemented with only a single scheduling queue. Jason 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?20001127154800.M4140>