Re: Comments on the KSE option

David Xu wrote:
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.


I agree that it is not 'correct'. But I think it is better to fix it than remove it.

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.

not necessarily.. but I agree that there can certainly be a better way to provide process scope.


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).


if you do system scope threads properly then the overhead in the scheduler is small. As I indicated before. I think that by adjusting hte flags used it is possible to make system scope threads as efficient as
they are in the "NOKSE" case (or very close to it.)

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.

I did say that what I have at the moment is not the best but w=rather the fastest for me to do. I would loke to see it replaced.

My only comment is that getting rid of the KSEGRP is not required to
change the fairness algorythm. I still think it is useful to have
separate fairness "universes" for different groups of threads in the ssme process, no matter how it is achieved.


David Xu
_______________________________________________
freebsd-current@xxxxxxxxxxx mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-current
To unsubscribe, send any mail to "freebsd-current-unsubscribe@xxxxxxxxxxx"

Relevant Pages

  • Re: Comments on the KSE option
    ... The aim of the fair scheduling code is to ensure that if you, as a user, ... A naive scheduler would give you 1000 cpu slots and me 1. ... I removed creating multiple threads in same ksegrp because the ksegrp ... The ksegrp provided fairness is very naive since I saw weired behavior ...
    (freebsd-current)
  • Re: Comments on the KSE option
    ... A naive scheduler would give you 1000 cpu slots and me 1. ... The fairness algorythm that you have made 'optional' is a very crude one and I had thought that by now someone would have written a better one, ... If it is made a project goal that threads should be unfair, ... work only to discover at the end that it is the only thread on the ksegrp, and therefore always eligible to run). ...
    (freebsd-current)
  • Re: maybe_preempt_in_ksegrp
    ... Looking through the scheduler code and two functions ... it expects sched_choose to pick a thread from the ksegrp. ... expected it to say "I am preempting curthread because I am in the same ...
    (freebsd-hackers)
  • Re: More ULE bugs fixed.
    ... cleaning up the scheduler interface a bit.. ... In KSE there are a variable ... KSE-1:1 runs with a KSEGRP with a concurrancy of 1 per thread. ...
    (freebsd-current)
  • Re: 2.6.0-test6 scheduler goodness
    ... David B Harris wrote: ... 2.4.x's stock scheduler has always ... >them reduced throughput and responsiveness noticeably. ...
    (Linux-Kernel)