cvs commit: src/sys/kern sched_ule.c
jroberson at chesapeake.net
Fri Apr 11 12:08:59 PDT 2003
On Fri, 11 Apr 2003, Bruce Evans wrote:
> On Thu, 10 Apr 2003, Jeff Roberson wrote:
> > In this benchmark I have many processes that each run for 10ms and then
> > sleep for 10ms. Each of them has a different nice value. I record many
> > statistics, but below is the amount of cpu time given to each.
> > -20 -15 -10 -5 -1 0
> > ULE 5.753623 5.282634 4.856530 3.450129 3.126798 2.423626
> > 4BSD 5.737184 4.694133 4.185013 3.363824 2.711405 2.260881
> > 1 5 10 15 20
> > ULE 2.105255 0.657852 0.429098 0.411582 0.501759
> > 4BSD 2.452399 1.506065 0.859527 0.681111 0.427333
> > You can see that ule is quite regular until it gets to the positive nice
> > values where it is not as smooth as 4bsd. I'll fix this.
> The poor dynamic range of niceness for the 4bsd scheduler in current should
> not be aimed for. In the above it is about 5.74:0.43 = 13:1. It should be
> more like 100:1 or 1000:1.
I don't think this is so bad considering that they were only attempting to
use 50% of the cpu. That leaves a lot of idle time for other threads.
Although in ULE it is currently very easy to tune by adjusting your min
and max slice. Since each tick is 10ms on x86 ule currently does 10:1 for
processes of nice 0 and 19. If hz was 1000 it could easily be made 100:1.
I'm not sure if this is really desirable though.
> > This commit does fix the bug where nice +20 processes were still getting
> > CPU when 0 and negative nice processes were runnable. This should fix
> > most of the interactivity complaints with niced processes.
> Isn't this a non-bug? Something is needed to prevent priority inversion.
> I think priority inversion can be a problem at the level of user processes
> where the kernel can't do anything about it. A nice -20 process may aquire
> a lock on something important (perhaps just a file lock) and then never
> run again because there is a nice -0 process that is always runnable.
> meanwhile, even nice --20 processes may have to wait forever for the lock.
> Giving nice -20 processes a tiny but nonzero amount of CPU fixes the
> problem eventually.
While I do believe priority inversion is an issue, I'm not sure what I
think should be done here. Previously a nice 20 would compete equally
with a nice 0 if there was only one process running. This was a bug.
Basically the niced process didn't consider the currently running process
when its slice was picked. It only looked at the run queue.
What I could do is implement cpu distribution vs nice as a curve that
tapers of considerably once you get past 19 nice values. This would allow
really nice programs to slowly creep along. The problem is that my
scheduler can only adjust the amount of cpu time a process gets by
adjusting its slice size. The minimum is actually quite high. I may
introduce some divisor for the slice that essentially causes this thread
to get skipped over x times before it gets to run for the minimum amount.
This would give more more granularity than 10ms for every pass through the
> I think interactivity is mostly a different problem. When we give
> some CPU to niced processes, it is important that we only give them a
> tiny amount. Another problem with the small dynamic range is that it
> always gives a non-tiny amount. Scheduling granularity may be a
> problem, especially in the 4BSD scheduler - we can't give processes
> less than the quantum (if they want it), and with a quantum of 1/10
> second just 10 niced processes getting the minimal amount would give
> a delay of 1 second for interactive processes. These problems are
> limited by old bugfeatures in BSD for at least the 4BSD scheduler
> (interactive processes wake up at a kernel priority and normally
> essentially keep that priority when they return to userland, since we
> neglect to reschedule them).
ULE solves this differently. Interactivity is determined by the ratio of
voluntary sleep time to actual runtime. If it figures out that a process
is interactive it always puts it on the current queue which means it
doesn't have to wait for the current queue to complete and the next queue
to be switched to. High negative nice values can still delay interactive
processes that are very nice. I think this is what the user is indicating
with negative nice values though isn't he? Or do you think that nice
should not impact interactive processes?
It's difficult for me to grasp what behavior is most desirable. I have a
framework in place with ULE that would allow me to achieve most anything.
I guess my primary questions are these:
1) What distribution of cpu time vs nice is desirable?
2) Should nice processes starve interactive jobs?
More information about the cvs-all