Re: [PATCH] A nicer nice scheduling

Roberto Ragusa (robertoragusa@technologist.com)
Mon, 22 Oct 2001 20:16:09 +0200


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

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