cvs commit: src/sys/kern sched_ule.c

[Bruce Evans]

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.

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

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

Bruce