lkml.org 
[lkml]   [1999]   [May]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[patch] new scheduler
Hi,

attached is a patch that changes the Linux scheduler
to do the following things better/right:
- niced tasks use far less CPU than before
- interactive tasks always have a higher priority
than running tasks (more so than it's the case now)
- global priority recalculation has been changed to a
new mechanism involving p->defer, indicating when a
program is to get it's next time slice
- hopefully give a better interactive feel under
rediculous loads

This patch is against 2.2.8-5, which I haven't been able
to test because it hangs on either the IO Apic initialization
or the PCI probing -- just after the IO Apic IRQ routing table
is printed... I damn my weird Intel Mercury SMP chipset!
[Ingo, do you read my APIC call for help?]

The scheduler changes are trivial enough to be tested by
willing victims^Wtesters, so don't feel burdened by the
idea that I haven't tested the code. Besides, it's more
fun this way, isn't it?

cheers,

Rik -- Open Source: you deserve to be in control of your data.
+-------------------------------------------------------------------+
| Le Reseau netwerksystemen BV: http://www.reseau.nl/ |
| Linux Memory Management site: http://humbolt.geo.uu.nl/Linux-MM/ |
| Nederlandse Linux documentatie: http://www.nl.linux.org/ |
+-------------------------------------------------------------------+

--- linux/kernel/sched.c.orig Sun May 9 20:59:26 1999
+++ linux/kernel/sched.c Sun May 9 21:58:56 1999
@@ -88,6 +88,7 @@
extern void mem_use(void);

unsigned long volatile jiffies=0;
+unsigned long schedload = 1;

/*
* Init task must be ok at boot for the ix86 as we will check its signals
@@ -151,20 +152,15 @@
* into account).
*/
if (p->policy != SCHED_OTHER) {
- weight = 1000 + p->rt_priority;
+ weight = (1000 * HZ) + p->rt_priority;
goto out;
}

/*
* Give the process a first-approximation goodness value
- * according to the number of clock-ticks it has left.
- *
- * Don't do any other calculations if the time slice is
- * over..
+ * according to the time till the next-run deadline.
*/
- weight = p->counter;
- if (!weight)
- goto out;
+ weight = (100 * HZ) - ((long)p->defer - (long)jiffies);

#ifdef __SMP__
/* Give a largish advantage to the same processor... */
@@ -176,7 +172,6 @@
/* .. and a slight advantage to the current MM */
if (p->mm == prev->mm)
weight += 1;
- weight += p->priority;

out:
return weight;
@@ -453,6 +448,10 @@
if (p->next_run)
goto out;
add_to_runqueue(p);
+ if (time_after(jiffies, p->defer)) {
+ p->defer = jiffies;
+ p->counter = p->priority;
+ }
spin_unlock_irqrestore(&runqueue_lock, flags);

reschedule_idle(p);
@@ -718,6 +717,11 @@
goto move_rr_last;
move_rr_back:

+ /* recalculate process priority.. */
+ if (!prev->counter && prev->policy == SCHED_OTHER)
+ goto defer_process;
+defer_process_back:
+
switch (prev->state) {
case TASK_INTERRUPTIBLE:
if (signal_pending(prev)) {
@@ -768,9 +772,6 @@
p = p->next_run;
}

- /* Do we need to re-calculate counters? */
- if (!c)
- goto recalculate;
/*
* from this point on nothing can prevent us from
* switching to the next task, save this fact in
@@ -827,18 +828,6 @@
reacquire_kernel_lock(current);
return;

-recalculate:
- {
- struct task_struct *p;
- spin_unlock_irq(&runqueue_lock);
- read_lock(&tasklist_lock);
- for_each_task(p)
- p->counter = (p->counter >> 1) + p->priority;
- read_unlock(&tasklist_lock);
- spin_lock_irq(&runqueue_lock);
- goto repeat_schedule;
- }
-
still_running:
c = prev_goodness(prev, prev, this_cpu);
next = prev;
@@ -859,6 +848,17 @@
}
goto move_rr_back;

+defer_process:
+#define DEFER_NORMAL ((2 * DEF_PRIORITY - p->priority) * schedload)
+#define DEFER_NICE ((DEF_PRIORITY - p->priority) * DEF_PRIORITY * schedload)
+ p->counter = p->priority;
+ if (p->priority >= DEF_PRIORITY) {
+ p->defer = DEFER_NORMAL + jiffies;
+ } else {
+ p->defer = DEFER_NICE + jiffies;
+ }
+ goto defer_process_back;
+
scheduling_in_interrupt:
printk("Scheduling in interrupt\n");
*(int *)0 = 0;
@@ -1219,6 +1219,11 @@
CALC_LOAD(avenrun[1], EXP_5, active_tasks);
CALC_LOAD(avenrun[2], EXP_15, active_tasks);
}
+ schedload = (avenrun[0] >> FSHIFT);
+#ifdef SMP
+ schedload /= smp_num_cpus;
+#endif
+ schedload++;
}

/*
--- linux/kernel/fork.c.orig Sun May 9 20:59:31 1999
+++ linux/kernel/fork.c Sun May 9 21:01:21 1999
@@ -648,6 +648,7 @@
*/
current->counter >>= 1;
p->counter = current->counter;
+ p->defer = jiffies;

/*
* Ok, add it to the run-queues and make it
--- linux/include/linux/sched.h.orig Sun May 9 20:56:53 1999
+++ linux/include/linux/sched.h Sun May 9 22:02:21 1999
@@ -230,6 +230,7 @@
/* various fields */
long counter;
long priority;
+ unsigned long defer;
cycles_t avg_slice;
/* SMP and runqueue state */
int has_cpu;
@@ -347,7 +348,7 @@
*/
#define INIT_TASK \
/* state etc */ { 0,0,0,KERNEL_DS,&default_exec_domain,0, \
-/* counter */ DEF_PRIORITY,DEF_PRIORITY,0, \
+/* counter */ DEF_PRIORITY,DEF_PRIORITY,0,0, \
/* SMP */ 0,0,0,-1, \
/* schedlink */ &init_task,&init_task, &init_task, &init_task, \
/* binfmt */ NULL, \

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

\
 
 \ /
  Last update: 2005-03-22 13:51    [W:0.087 / U:0.436 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site