Re: Comments on the KSE option

From: David Xu <davidxu_at_freebsd.org>
Date: Sat, 28 Oct 2006 11:32:21 +0800
On Saturday 28 October 2006 03:27, Julian Elischer wrote:
> John, I appreciate that you have made KSE an option, but the way you
> have done it shows a complete misundertanding of what is there.
>
> What you are calling "KSE" is in fact several different facilities that
> are orthogonal.  The one that you have the most trouble with is in fact
> not SA based threading (refered to by most people as "KSE" but, rather
> the fair scheduling code).
>
> The aim of the fair scheduling code is to ensure that if you, as a user,
> make a process that starts 1000 threads, and I as a user, make an
> unthreaded process, then I can still get to the CPU at somewhat similar
> rates to you.  A naive scheduler would give you 1000 cpu slots and me 1.
>
> the current fair scheduler tries to make sure that each process gets
> a fair crack at the CPU by holding back some of the runnable threads
> from the threadded process, until the ones it has in therun queu have
> been completed.. A bit like telling a young child, "yes you can have
> more ice-cream, when you've finished the ice-cream you already have".
>
> I note that David recently (in the last year) disabled the fair
> scheduling capacity of the libthr  code, but he didn't do it quite right
> so that it still does all the work for it, and then disregarded the
> result. This means that not only does a 1000 thread process (libthr)
> completely push a nonthreaded process out of the system, but it pays
> all the costs in the scheduler for working out how to NOT do that.
>

1) I removed creating multiple threads in same ksegrp because the ksegrp
implementation is broken, as I said earlier days, you have put a kg_user_pri
in it and force each thread in the group to must have same user priority,
this is completly broken, if I want to set different priority for each thread,
how do I ? does POSIX say that every thread must have same priority?
it does not and should not, when I implemented POSIX priority mutex in
umtx code, I found I must throw away the ksegrp.
2)  The ksegrp provided fairness is very naive since I saw weired behavior
when testing David ButenHof pthread susp example. I saw the example even
can not finish its test on a SMP machine. since I must throw away ksegrp
because of 1), so kernel ksegrp can not help fairness for libthr.
3) Third, it adds overhead to scheduler (I have already post a number) 
and might make locking more diffcult for per-cpu queue like scheduler,
since now you always have to contend the ksegrp runqueue lock between
many CPUs, also because you have build the fairness in the scheduler and
every scheduler must obey the ksegrp algorithm, it may make more diffcult
to implement another alogrithm and replace it, see 4).
4) There is better fairness scheduling alogrithm published many years ago,
http://www.cs.cornell.edu/Courses/cs614/2003SP/papers/KL89.pdf
I believe it was implemented in Solaris.

David Xu
Received on Sat Oct 28 2006 - 01:32:31 UTC

This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:39:01 UTC