[PATCH] A nicer nice scheduling

[PATCH] A nicer nice scheduling

[Roberto Ragusa]

Hi,

please consider including this patch in the main kernel.
It was proposed on 11/04/2001 by Rik van Riel
([test-PATCH] Re: [QUESTION] 2.4.x nice level)

This patch has been working great for me, I applied it to
every new kernel out.

Without this patch, a nice=19 busy-looping process is given
15% of CPU cycles when there is a busy-looping nice=0 process.

Well, if one runs background CPU-consuming programs
(dnetc), this patch makes a nice speed boost.

Please CC to me any replies.

diff -urN linux-2.4.8-lmshsbrnc1/include/linux/sched.h linux-2.4.8-lmshsbrnc1_/include/linux/sched.h
--- linux-2.4.8-lmshsbrnc1/include/linux/sched.h    Sun Aug 12 10:18:03 2001
+++ linux-2.4.8-lmshsbrnc1_/include/linux/sched.h    Sun Aug 12 12:19:16 2001
@@ -305,7 +305,8 @@
  * the goodness() loop in schedule().
  */
     long counter;
-    long nice;
+    short nice_calc;
+    short nice;
     unsigned long policy;
     struct mm_struct *mm;
     int has_cpu, processor;
diff -urN linux-2.4.8-lmshsbrnc1/kernel/sched.c linux-2.4.8-lmshsbrnc1_/kernel/sched.c
--- linux-2.4.8-lmshsbrnc1/kernel/sched.c    Sun Aug 12 10:18:03 2001
+++ linux-2.4.8-lmshsbrnc1_/kernel/sched.c    Sun Aug 12 12:19:16 2001
@@ -680,8 +680,26 @@
         struct task_struct *p;
         spin_unlock_irq(&runqueue_lock);
         read_lock(&tasklist_lock);
-        for_each_task(p)
+        for_each_task(p) {
+            if (p->nice <= 0) {
+            /* The normal case... */
             p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
+            } else {
+            /*
+             * Niced tasks get less CPU less often, leading to
+             * the following distribution of CPU time:
+             *
+             * Nice    0    5   10   15   19
+             * %CPU  100   56   25    6    1    
+             */
+            short prio = 20 - p->nice;
+            p->nice_calc += prio;
+            if (p->nice_calc >= 20) {
+                p->nice_calc -= 20;
+                p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
+            }
+            }
+        }
         read_unlock(&tasklist_lock);
         spin_lock_irq(&runqueue_lock);
     }


-- 
            Roberto Ragusa   robertoragusa at technologist.com

Re: [PATCH] A nicer nice scheduling

[Giuliano Pochini]

Roberto Ragusa wrote:
> 
> Hi,
> 
> please consider including this patch in the main kernel.
> It was proposed on 11/04/2001 by Rik van Riel
> ([test-PATCH] Re: [QUESTION] 2.4.x nice level)
> 
> This patch has been working great for me, I applied it to
> every new kernel out.
> 
> Without this patch, a nice=19 busy-looping process is given
> 15% of CPU cycles when there is a busy-looping nice=0 process. 
> [...]

I think it's simpler to change NICE_TO_TICKS() macro in sched.c


Bye.

Re: [PATCH] A nicer nice scheduling

[Roberto Ragusa]

Giuliano Pochini wrote:

> Roberto Ragusa wrote: 
> > please consider including this patch in the main kernel. 
> > It was proposed on 11/04/2001 by Rik van Riel 
> > ([test-PATCH] Re: [QUESTION] 2.4.x nice level) 
> 
> I think it's simpler to change NICE_TO_TICKS() macro in sched.c 

I'm afraid it isn't.
We don't have enough resolution, if I understand sched.c correctly.

On 2.4.12 and with HZ=100 (common case) NICE_TO_TICKS gives:

nice | ticks
------------
 -20 |  11
 -19 |  10
 -18 |  10
 -17 |  10
 -16 |  10
 -15 |   9
 -14 |   9
 -13 |   9
 -12 |   9
 -11 |   8
 -10 |   8
 -9  |   8
 -8  |   8
 -7  |   7
 -6  |   7
 -5  |   7
 -4  |   7
 -3  |   6
 -2  |   6
 -1  |   6
  0  |   6
  1  |   5
  2  |   5
  3  |   5
  4  |   5
  5  |   4
  6  |   4
  7  |   4
  8  |   4
  9  |   3
 10  |   3
 11  |   3
 12  |   3
 13  |   2
 14  |   2
 15  |   2
 16  |   2
 17  |   1
 18  |   1
 19  |   1

So nice=19 vs. nice=0 has a 1:6 CPU ratio ( 14% - 86% ).

As we can't decrease 1 (n=19), we could increase 6 (n=0), with a more
aggressive linear dependence. But this way the time-slice would also
increase.

To balance this effect, we could also increase HZ (ref. TICK_SCALE).
But this way an n=19 process would run frequently and for a very little
time (with greater process switching overhead).

The right solution is IMHO to give an n=19 process less time and less
often than an n=0 process.
The patch from Rik gives:

nice | ticks | less often factor | equivalent ticks
---------------------------------------------------
 -20 |  11   |        1          |     11
 -19 |  10   |        1          |     10
 -18 |  10   |        1          |     10
 -17 |  10   |        1          |     10
 -16 |  10   |        1          |     10
 -15 |   9   |        1          |      9
 -14 |   9   |        1          |      9
 -13 |   9   |        1          |      9
 -12 |   9   |        1          |      9
 -11 |   8   |        1          |      8
 -10 |   8   |        1          |      8
 -9  |   8   |        1          |      8
 -8  |   8   |        1          |      8
 -7  |   7   |        1          |      7
 -6  |   7   |        1          |      7
 -5  |   7   |        1          |      7
 -4  |   7   |        1          |      7
 -3  |   6   |        1          |      6
 -2  |   6   |        1          |      6
 -1  |   6   |        1          |      6
  0  |   6   |        1          |      6
  1  |   5   |      19/20        |      4.75
  2  |   5   |      18/20        |      4.5 
  3  |   5   |      17/20        |      4.25
  4  |   5   |      16/20        |      4
  5  |   4   |      15/20        |      3
  6  |   4   |      14/20        |      2.8
  7  |   4   |      13/20        |      2.6
  8  |   4   |      12/20        |      2.4
  9  |   3   |      11/20        |      1.65
 10  |   3   |      10/20        |      1.5
 11  |   3   |       9/20        |      1.35
 12  |   3   |       8/20        |      1.2
 13  |   2   |       7/20        |      0.7
 14  |   2   |       6/20        |      0.6
 15  |   2   |       5/20        |      0.5
 16  |   2   |       4/20        |      0.4
 17  |   1   |       3/20        |      0.15
 18  |   1   |       2/20        |      0.1
 19  |   1   |       1/20        |      0.05

And we have a nice=19 vs. nice=0 ratio of 0.05:6 CPU
ratio ( 0.8% - 99.2% ).


So, this patch really solves the problem.
And yes, it is a problem: who wants dnetc/setiathome to slow
down (by 15%) apps like mozilla or gcc?

We don't want a "don't install dnetc on Linux 2.4.x, because it
does not multitask well" rumour around; that is true for MacOS 9
but should not for Linux. :-)

So, I think we should consider applying this patch (if noone
has some better solution).

Please CC to me any replies.


diff -urN linux-2.4.8-lmshsbrnc1/include/linux/sched.h linux-2.4.8-lmshsbrnc1_/include/linux/sched.h
--- linux-2.4.8-lmshsbrnc1/include/linux/sched.h    Sun Aug 12 10:18:03 2001
+++ linux-2.4.8-lmshsbrnc1_/include/linux/sched.h    Sun Aug 12 12:19:16 2001
@@ -305,7 +305,8 @@
  * the goodness() loop in schedule().
  */
     long counter;
-    long nice;
+    short nice_calc;
+    short nice;
     unsigned long policy;
     struct mm_struct *mm;
     int has_cpu, processor;
diff -urN linux-2.4.8-lmshsbrnc1/kernel/sched.c linux-2.4.8-lmshsbrnc1_/kernel/sched.c
--- linux-2.4.8-lmshsbrnc1/kernel/sched.c    Sun Aug 12 10:18:03 2001
+++ linux-2.4.8-lmshsbrnc1_/kernel/sched.c    Sun Aug 12 12:19:16 2001
@@ -680,8 +680,26 @@
         struct task_struct *p;
         spin_unlock_irq(&runqueue_lock);
         read_lock(&tasklist_lock);
-        for_each_task(p)
+        for_each_task(p) {
+            if (p->nice <= 0) {
+                /* The normal case... */
                 p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
+            } else {
+                /*
+                 * Niced tasks get less CPU less often, leading to
+                 * the following distribution of CPU time:
+                 *
+                 * Nice    0    5   10   15   19
+                 * %CPU  100   56   25    6    1
+                 */
+                short prio = 20 - p->nice;
+                p->nice_calc += prio;
+                if (p->nice_calc >= 20) {
+                    p->nice_calc -= 20;
+                    p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
+                }
+            }
+        }
         read_unlock(&tasklist_lock);
         spin_lock_irq(&runqueue_lock);
     }


-- 

            Roberto Ragusa   robertoragusa at technologist.com

Re: [PATCH] A nicer nice scheduling

[bill davidsen]

In article <yam8695.480.153891320@mail.inwind.it> robertoragusa@technologist.com wrote:

| So nice=19 vs. nice=0 has a 1:6 CPU ratio ( 14% - 86% ).
| 
| As we can't decrease 1 (n=19), we could increase 6 (n=0), with a more
| aggressive linear dependence. But this way the time-slice would also
| increase.
| 
| To balance this effect, we could also increase HZ (ref. TICK_SCALE).
| But this way an n=19 process would run frequently and for a very little
| time (with greater process switching overhead).
| 
| The right solution is IMHO to give an n=19 process less time and less
| often than an n=0 process.

| And we have a nice=19 vs. nice=0 ratio of 0.05:6 CPU
| ratio ( 0.8% - 99.2% ).
| 
| 
| So, this patch really solves the problem.
| And yes, it is a problem: who wants dnetc/setiathome to slow
| down (by 15%) apps like mozilla or gcc?
| 
| We don't want a "don't install dnetc on Linux 2.4.x, because it
| does not multitask well" rumour around; that is true for MacOS 9
| but should not for Linux. :-)
| 
| So, I think we should consider applying this patch (if noone
| has some better solution).
| 
| Please CC to me any replies.

  I will probably try this patch, assuming it applies nicely to newer
kernels. But such an aggressive nice does have a downside as given, it
can result in a process in memory which doesn't get scheduled. Or one
which gets run only long enough to get the next page fault, and which
takes resources while never getting anything done.

  So this is useful, but I hope people won't consider this as a complete
colution. I still think we need a real idle process to do the low
priority task feature in the most useful way. I think this would not
provide good results in a system with significant memory pressure.

-- 
bill davidsen <davidsen@tmr.com>
  His first management concern is not solving the problem, but covering
his ass. If he lived in the middle ages he'd wear his codpiece backward.

Re: [PATCH] A nicer nice scheduling

[Bill Davidsen]

On Mon, 22 Oct 2001, Mark Hahn wrote:

> > kernels. But such an aggressive nice does have a downside as given, it
> > can result in a process in memory which doesn't get scheduled. 
> 
> why would it be "in memory"?  idle pages get reclaimed/swapped.

In the long run that's true, but there's nothing to preferentially swap
that page set, so they don't go away any faster than any other pages. If
the idle process were another thing instead of just a low priority
process, it could be treated in some special ways WRT memory management.

We have two people actively working on VM, please let them comment on what
could be done. I would think about swapping the idle process
preferentially if it didn't get run for some realtime, and perhaps doing
{something_else} fancy otherwise. At the rate the VM code is getting
complex I expect to see standard deviation and FFTs in 2.5. Only half
kidding, both VMs are working better with every refinement, complexity is
not bad if it produces better results. I always thought per-process page
fault rates would be useful, if some weighted attention to that would
reduce the total system i/o rate.

Anyway, that was my thinking, if the load is high a true idle process
could be treated as a special case, including running a small number of
them instead of having a lot of low priority processes doing not much if
too many were started. I can remember batch processing, and for real idle
jobs that's not a bad thing.

-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: [PATCH] A nicer nice scheduling

[Bill Davidsen]

On Mon, 22 Oct 2001, Mark Hahn wrote:

> > the idle process were another thing instead of just a low priority
> > process, it could be treated in some special ways WRT memory management.
> 
> why?  it's clearly optimal to discard pages from ultra-high-prio
> processes as well.  the best choice of pages to discard seems to 
> mainly depend on frequency or recency of use.
> 
> there's no reason that nice (or better yet, mmnice)
> couldn't be used in VM choices.

If the current load is high the idle process will get no time, and its
pages are best swapped. Choosing to do this (or not) is one of the things
I meant by special treatment. More information can mean better choices.
 
> > not bad if it produces better results. I always thought per-process page
> > fault rates would be useful, if some weighted attention to that would
> > reduce the total system i/o rate.
> 
> they existed around 2.3.40, I think.  it's not clear that this kind
> of information is really that useful, since "process that's causing
> lots of faults" is sometimes the one you want to give *more* memory to,
> and sometimes one you want to starve.

Exactly my point, I didn't recall that it had been tried. But clearly if
you have several processes which are long running and one has a much
higher fault rate than the others, there is certainly a possibility that
the systyem will run better by giving that process more RSS.
 
> > Anyway, that was my thinking, if the load is high a true idle process
> > could be treated as a special case, including running a small number of
> > them instead of having a lot of low priority processes doing not much if
> > too many were started. I can remember batch processing, and for real idle
> > jobs that's not a bad thing.
> 
> I think there are vanishingly few procs that could tolerate batch
> behavior these days, at least in the desktop/server domain.
> and the textbook answer is that this sort of thing should be 
> handled by a separte scheduler (usually they're called short-term
> and long-term) - that is, if you have a special workload that naturally
> like batches, then you should have a higher-level queue-manager
> (perl would be plenty) that submits a single job to the short-term
> manager and lets it run to completion.

But that's not an idle process, it competes with the rest of the system.
There are quite a few systems on which I'd love to run things like
setiathome, ray tracing, etc, if they wouldn't impact the CPU to
production. Obviously this only applies if the system has enough memory,
but in general that's true.
 
> in fact, the only case I can think of where batching still takes 
> place is number-crunching.  and I would dearly love to have better
> control over the mini-supercomputer I run (112 alphas!).

Even if batching meant running only one "idle process" at a time for,
perhaps, ten seconds at a go, then running the next. At least they
wouldn't compete with other jobs, and would be likely to get some actual
work done while running.

I think the idle task has merit, but I admit it's mainly because I have
lots of things I'd like to run on big servers as long as they didn't hurt.
Kernel compiles, for instance, if they didn't hurt response.

-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.