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