Re: CFS review

[Willy Tarreau <w@1wt.eu>]

On Thu, Aug 02, 2007 at 12:43:29PM +0200, Andi Kleen wrote:
> > However, I undertand why Ingo chose to use 64 bits. It has the advantage
> > that the numbers never wrap within 584 years. I'm well aware that it's
> > very difficult to keep tasks ordered according to a key which can wrap.
> 
> If you define an appropiate window and use some macros for the comparisons
> it shouldn't be a big problem.

It should not, but the hardest thing is often to keep values sorted within a
window. When you store your values in a tree according to a key, it's not
always easy to do find the first one relative to a sliding offset.

> > But if we consider that we don't need to be more precise than the return
> > value from gettimeofday() that all applications use,
> 
> gettimeofday() has too strict requirements, that make it unnecessarily slow
> for this task.

maybe we would use (TSC >> (x bits)) when TSC is available, or jiffies in other
cases. I believe that people not interested in high time accuracies are not
much interested in perfect fairness either. However, we should do the best to
avoid any form of starvation, otherwise we jump back to the problem with the
current scheduler.

> > every hour. We may accept to recompute all keys every hour.
> 
> You don't need to recompute keys; just use careful comparisons using
> subtractions and a window. TCPs have done that for decades. 
> 
> > Have all keys use 32-bit resolution, and monitor the 32nd bit. All tasks
> 
> If you're worried about wrapping in one hour why is wrapping in two
> hours not a problem? 

I've not said I was worried about that (or maybe I explained myself poorly).
Even if it was once a minute, it would not bother me. I wanted to explain
that if the solution requires to do it that often, it should be acceptable.

> I have one request though. If anybody adds anything complicated
> for this please make it optional so that 64bit platforms are not 
> burdened by it.

Fair enough. But the solution is not there yet. Maybe once it's there, it
will be better than current design for all platforms and the only difference
will be the accuracy due to optional use of the TSC.

> -Andi

Willy

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/