lkml.org 
[lkml]   [2003]   [Sep]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
SubjectRe: [PATCH] yet another scheduler patch
Date
Now my patch works also on x86 platform, and it works well (for me).
Please give it a try, any feedback is welcome!

The attached diff is for 2.6.0-test5 and is only for ppc32 and i386 archs

Ciao,
-- Francesco
diff -urN linux-2.6.0-test5-orig/fs/proc/array.c linux-2.6.0-test5/fs/proc/array.c
--- linux-2.6.0-test5-orig/fs/proc/array.c 2003-09-08 21:50:07.000000000 +0200
+++ linux-2.6.0-test5/fs/proc/array.c 2003-09-09 12:04:03.000000000 +0200
@@ -154,13 +154,22 @@
read_lock(&tasklist_lock);
buffer += sprintf(buffer,
"State:\t%s\n"
+ "sleeptime:\t%d\n"
+ "runtime:\t%d\n"
+ "prio:\t%d\n"
+ "static_prio:\t%d\n"
"Tgid:\t%d\n"
"Pid:\t%d\n"
"PPid:\t%d\n"
"TracerPid:\t%d\n"
"Uid:\t%d\t%d\t%d\t%d\n"
"Gid:\t%d\t%d\t%d\t%d\n",
- get_task_state(p), p->tgid,
+ get_task_state(p),
+ p->sleeptime,
+ p->runtime,
+ p->prio,
+ p->static_prio,
+ p->tgid,
p->pid, p->pid ? p->real_parent->pid : 0,
p->pid && p->ptrace ? p->parent->pid : 0,
p->uid, p->euid, p->suid, p->fsuid,
diff -urN linux-2.6.0-test5-orig/include/asm-i386/bitops.h linux-2.6.0-test5/include/asm-i386/bitops.h
--- linux-2.6.0-test5-orig/include/asm-i386/bitops.h 2003-09-08 21:50:08.000000000 +0200
+++ linux-2.6.0-test5/include/asm-i386/bitops.h 2003-09-09 12:16:01.000000000 +0200
@@ -426,8 +426,8 @@

/*
* Every architecture must define this function. It's the fastest
- * way of searching a 140-bit bitmap where the first 100 bits are
- * unlikely to be set. It's guaranteed that at least one of the 140
+ * way of searching a 220-bit bitmap where the first 100 bits are
+ * unlikely to be set. It's guaranteed that at least one of the 220
* bits is cleared.
*/
static inline int sched_find_first_bit(const unsigned long *b)
@@ -439,8 +439,12 @@
if (unlikely(b[2]))
return __ffs(b[2]) + 64;
if (b[3])
- return __ffs(b[3]) + 96;
- return __ffs(b[4]) + 128;
+ return __ffs(b[3]) + 96;
+ if (b[4])
+ return __ffs(b[4]) + 128;
+ if (b[5])
+ return __ffs(b[5]) + 160;
+ return __ffs(b[6]) + 192;
}

/**
diff -urN linux-2.6.0-test5-orig/include/asm-ppc/bitops.h linux-2.6.0-test5/include/asm-ppc/bitops.h
--- linux-2.6.0-test5-orig/include/asm-ppc/bitops.h 2003-09-08 21:50:06.000000000 +0200
+++ linux-2.6.0-test5/include/asm-ppc/bitops.h 2003-09-09 12:16:03.000000000 +0200
@@ -273,7 +273,7 @@
#define hweight8(x) generic_hweight8(x)

/*
- * Find the first bit set in a 140-bit bitmap.
+ * Find the first bit set in a 200-bit bitmap.
* The first 100 bits are unlikely to be set.
*/
static inline int sched_find_first_bit(unsigned long *b)
@@ -286,7 +286,11 @@
return __ffs(b[2]) + 64;
if (b[3])
return __ffs(b[3]) + 96;
- return __ffs(b[4]) + 128;
+ if (b[4])
+ return __ffs(b[4]) + 128;
+ if (b[5])
+ return __ffs(b[5]) + 160;
+ return __ffs(b[6]) + 192;
}

/**
Binary files linux-2.6.0-test5-orig/include/linux/.vermagic.h.swp and linux-2.6.0-test5/include/linux/.vermagic.h.swp differ
diff -urN linux-2.6.0-test5-orig/include/linux/init_task.h linux-2.6.0-test5/include/linux/init_task.h
--- linux-2.6.0-test5-orig/include/linux/init_task.h 2003-09-08 21:49:53.000000000 +0200
+++ linux-2.6.0-test5/include/linux/init_task.h 2003-09-09 12:04:03.000000000 +0200
@@ -68,7 +68,7 @@
.flags = 0, \
.lock_depth = -1, \
.prio = MAX_PRIO-20, \
- .static_prio = MAX_PRIO-20, \
+ .static_prio = MAX_PRIO-100, \
.policy = SCHED_NORMAL, \
.cpus_allowed = CPU_MASK_ALL, \
.mm = NULL, \
diff -urN linux-2.6.0-test5-orig/include/linux/sched.h linux-2.6.0-test5/include/linux/sched.h
--- linux-2.6.0-test5-orig/include/linux/sched.h 2003-09-08 21:49:53.000000000 +0200
+++ linux-2.6.0-test5/include/linux/sched.h 2003-09-09 12:04:03.000000000 +0200
@@ -280,7 +280,7 @@
#define MAX_USER_RT_PRIO 100
#define MAX_RT_PRIO MAX_USER_RT_PRIO

-#define MAX_PRIO (MAX_RT_PRIO + 40)
+#define MAX_PRIO (MAX_RT_PRIO + 120)

/*
* Some day this will be a full-fledged user tracking system..
@@ -339,8 +339,11 @@
struct list_head run_list;
prio_array_t *array;

- unsigned long sleep_avg;
unsigned long last_run;
+ unsigned long go_to_sleep;
+ unsigned runtime;
+ unsigned sleeptime;
+ int interactive_score;

unsigned long policy;
cpumask_t cpus_allowed;
diff -urN linux-2.6.0-test5-orig/kernel/sched.c linux-2.6.0-test5/kernel/sched.c
--- linux-2.6.0-test5-orig/kernel/sched.c 2003-09-08 21:50:21.000000000 +0200
+++ linux-2.6.0-test5/kernel/sched.c 2003-09-09 12:04:03.000000000 +0200
@@ -41,9 +41,10 @@
#define cpu_to_node_mask(cpu) (cpu_online_map)
#endif

+#define MAX(x,y) ((x > y) ? x : y)
/*
* Convert user-nice values [ -20 ... 0 ... 19 ]
- * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
+ * to static priority [ MAX_RT_PRIO..139 ],
* and back.
*/
#define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20)
@@ -53,7 +54,7 @@
/*
* 'User priority' is the nice value converted to something we
* can work with better when scaling various scheduler parameters,
- * it's a [ 0 ... 39 ] range.
+ * it's a [ 0 ... 120 ] range.
*/
#define USER_PRIO(p) ((p)-MAX_RT_PRIO)
#define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio)
@@ -62,18 +63,17 @@
/*
* These are the 'tuning knobs' of the scheduler:
*
- * Minimum timeslice is 10 msecs, default timeslice is 100 msecs,
- * maximum timeslice is 200 msecs. Timeslices get refilled after
- * they expire.
+ * Minimum timeslice is 10 msecs, maximum timeslice is 140 msecs.
+ * Timeslices get refilled after they expire.
*/
#define MIN_TIMESLICE ( 10 * HZ / 1000)
-#define MAX_TIMESLICE (200 * HZ / 1000)
-#define CHILD_PENALTY 50
-#define PARENT_PENALTY 100
+#define MAX_TIMESLICE (140 * HZ / 1000)
+#define SLEEP_RUN_MAX (10*HZ)
+#define SLEEP_RUN_THROTTLE 80
+#define INTERACTIVE_SCORE_MAX 80
+#define INTERACTIVE_SCORE_HALF (INTERACTIVE_SCORE_MAX / 2)
+#define INTERACTIVE_THRESHOLD 16
#define EXIT_WEIGHT 3
-#define PRIO_BONUS_RATIO 25
-#define INTERACTIVE_DELTA 2
-#define MAX_SLEEP_AVG (10*HZ)
#define STARVATION_LIMIT (10*HZ)
#define NODE_THRESHOLD 125

@@ -83,54 +83,30 @@
* continue to run immediately, it will still roundrobin with
* other interactive tasks.)
*
- * This part scales the interactivity limit depending on niceness.
- *
- * We scale it linearly, offset by the INTERACTIVE_DELTA delta.
- * Here are a few examples of different nice levels:
- *
- * TASK_INTERACTIVE(-20): [1,1,1,1,1,1,1,1,1,0,0]
- * TASK_INTERACTIVE(-10): [1,1,1,1,1,1,1,0,0,0,0]
- * TASK_INTERACTIVE( 0): [1,1,1,1,0,0,0,0,0,0,0]
- * TASK_INTERACTIVE( 10): [1,1,0,0,0,0,0,0,0,0,0]
- * TASK_INTERACTIVE( 19): [0,0,0,0,0,0,0,0,0,0,0]
- *
- * (the X axis represents the possible -5 ... 0 ... +5 dynamic
- * priority range a task can explore, a value of '1' means the
- * task is rated interactive.)
- *
- * Ie. nice +19 tasks can never get 'interactive' enough to be
- * reinserted into the active array. And only heavily CPU-hog nice -20
- * tasks will be expired. Default nice 0 tasks are somewhere between,
- * it takes some effort for them to get interactive, but it's not
- * too hard.
- */
-
-#define SCALE(v1,v1_max,v2_max) \
- (v1) * (v2_max) / (v1_max)
-
-#define DELTA(p) \
- (SCALE(TASK_NICE(p), 40, MAX_USER_PRIO*PRIO_BONUS_RATIO/100) + \
- INTERACTIVE_DELTA)
+ * If the interactive_score of the process is less than
+ * INTERACTIVE_THRESHOLD, we have an interactive thread.
+ *
+ */

#define TASK_INTERACTIVE(p) \
- ((p)->prio <= (p)->static_prio - DELTA(p))
+ (p->interactive_score <= INTERACTIVE_THRESHOLD)

/*
- * BASE_TIMESLICE scales user-nice values [ -20 ... 19 ]
+ * BASE_TIMESLICE scales effective priority values
* to time slice values.
*
- * The higher a thread's priority, the bigger timeslices
- * it gets during one round of execution. But even the lowest
- * priority thread gets MIN_TIMESLICE worth of execution time.
- *
- * task_timeslice() is the interface that is used by the scheduler.
+ * The higher a thread's priority, the smaller timeslices
+ * it gets during one round of execution. Interactive threads
+ * always get a MIN_TIMESLICE slice.
*/

-#define BASE_TIMESLICE(p) (MIN_TIMESLICE + \
- ((MAX_TIMESLICE - MIN_TIMESLICE) * (MAX_PRIO-1-(p)->static_prio)/(MAX_USER_PRIO - 1)))
+#define BASE_TIMESLICE(p) ((((MAX_TIMESLICE - MIN_TIMESLICE) * (p)->prio)/(MAX_USER_PRIO - 1)) + MIN_TIMESLICE)

static inline unsigned int task_timeslice(task_t *p)
{
+ if (TASK_INTERACTIVE(p))
+ return MIN_TIMESLICE;
+
return BASE_TIMESLICE(p);
}

@@ -298,35 +274,56 @@
p->array = array;
}

+static void sleeptime_runtime_update(task_t *p)
+{
+ while ((p->runtime + p->sleeptime) > SLEEP_RUN_MAX) {
+ p->runtime = (p->runtime / 5) * 4;
+ p->sleeptime = (p->sleeptime / 5) * 4;
+ }
+}
+
+static int interactive_score(task_t *p)
+{
+ int div, score;
+
+ if (p->runtime > p->sleeptime) {
+ div = MAX(1, p->runtime / INTERACTIVE_SCORE_HALF);
+ score = (INTERACTIVE_SCORE_HALF +
+ (INTERACTIVE_SCORE_HALF - (p->sleeptime / div)));
+ }
+ else if (p->sleeptime > p->runtime) {
+ div = MAX(1, p->sleeptime / INTERACTIVE_SCORE_HALF);
+ score = (p->runtime / div);
+ }
+ else
+ score = 0;
+
+ return score;
+}
+
/*
- * effective_prio - return the priority that is based on the static
- * priority but is modified by bonuses/penalties.
- *
- * We scale the actual sleep average [0 .... MAX_SLEEP_AVG]
- * into the -5 ... 0 ... +5 bonus/penalty range.
+ * effective_prio - return the priority that is the static priority
+ * plus the interactive score of the process.
*
- * We use 25% of the full 0...39 priority range so that:
+ * The interactive score is in the 0 ... +80 range.
*
- * 1) nice +19 interactive tasks do not preempt nice 0 CPU hogs.
- * 2) nice -20 CPU hogs do not get preempted by nice 0 tasks.
- *
- * Both properties are important to certain workloads.
*/
-static int effective_prio(task_t *p)
+
+static inline int effective_prio(task_t *p)
{
- int bonus, prio;
+ int prio;

if (rt_task(p))
return p->prio;

- bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*p->sleep_avg/MAX_SLEEP_AVG/100 -
- MAX_USER_PRIO*PRIO_BONUS_RATIO/100/2;
-
- prio = p->static_prio - bonus;
+ p->interactive_score = interactive_score(p);
+ prio = p->static_prio + p->interactive_score;
+
if (prio < MAX_RT_PRIO)
prio = MAX_RT_PRIO;
if (prio > MAX_PRIO-1)
prio = MAX_PRIO-1;
+
return prio;
}

@@ -342,38 +339,17 @@
/*
* activate_task - move a task to the runqueue and do priority recalculation
*
- * Update all the scheduling statistics stuff. (sleep average
- * calculation, priority modifiers, etc.)
+ * Update the sleeptime amount of the process and scale (if necessary) the
+ * sleeptime/runtime values
*/
static inline void activate_task(task_t *p, runqueue_t *rq)
{
- long sleep_time = jiffies - p->last_run - 1;
+ long sleep_time = jiffies - p->go_to_sleep;

if (sleep_time > 0) {
- int sleep_avg;
-
- /*
- * This code gives a bonus to interactive tasks.
- *
- * The boost works by updating the 'average sleep time'
- * value here, based on ->last_run. The more time a task
- * spends sleeping, the higher the average gets - and the
- * higher the priority boost gets as well.
- */
- sleep_avg = p->sleep_avg + sleep_time;
-
- /*
- * 'Overflow' bonus ticks go to the waker as well, so the
- * ticks are not lost. This has the effect of further
- * boosting tasks that are related to maximum-interactive
- * tasks.
- */
- if (sleep_avg > MAX_SLEEP_AVG)
- sleep_avg = MAX_SLEEP_AVG;
- if (p->sleep_avg != sleep_avg) {
- p->sleep_avg = sleep_avg;
- p->prio = effective_prio(p);
- }
+ p->sleeptime += sleep_time;
+ sleeptime_runtime_update(p);
+ p->prio = effective_prio(p);
}
__activate_task(p, rq);
}
@@ -384,6 +360,7 @@
static inline void deactivate_task(struct task_struct *p, runqueue_t *rq)
{
nr_running_dec(rq);
+ p->go_to_sleep = jiffies;
if (p->state == TASK_UNINTERRUPTIBLE)
rq->nr_uninterruptible++;
dequeue_task(p, p->array);
@@ -539,7 +516,7 @@
* This function will do some initial scheduler statistics housekeeping
* that must be done for every newly created process.
*/
-void wake_up_forked_process(task_t * p)
+void wake_up_forked_process(task_t *p)
{
unsigned long flags;
runqueue_t *rq = task_rq_lock(current, &flags);
@@ -550,15 +527,21 @@
* and children as well, to keep max-interactive tasks
* from forking tasks that are max-interactive.
*/
- current->sleep_avg = current->sleep_avg * PARENT_PENALTY / 100;
- p->sleep_avg = p->sleep_avg * CHILD_PENALTY / 100;
- p->prio = effective_prio(p);
+
+ p->prio = current->prio;
+ p->static_prio = current->static_prio;
+ p->sleeptime = current->sleeptime / SLEEP_RUN_THROTTLE;
+ p->runtime = current->runtime / SLEEP_RUN_THROTTLE;
+ p->runtime++;
+ p->time_slice = MIN_TIMESLICE;
+ sleeptime_runtime_update(p);
+
set_task_cpu(p, smp_processor_id());

- if (unlikely(!current->array))
+ if (unlikely(!current->array)) {
+ p->prio = effective_prio(p);
__activate_task(p, rq);
- else {
- p->prio = current->prio;
+ } else {
list_add_tail(&p->run_list, &current->run_list);
p->array = current->array;
p->array->nr_active++;
@@ -591,9 +574,14 @@
* If the child was a (relative-) CPU hog then decrease
* the sleep_avg of the parent as well.
*/
- if (p->sleep_avg < p->parent->sleep_avg)
- p->parent->sleep_avg = (p->parent->sleep_avg * EXIT_WEIGHT +
- p->sleep_avg) / (EXIT_WEIGHT + 1);
+ if (p->runtime > p->parent->runtime)
+ p->parent->runtime = (p->parent->runtime * EXIT_WEIGHT +
+ p->runtime) / (EXIT_WEIGHT + 1);
+ if (p->sleeptime > p->parent->sleeptime)
+ p->parent->sleeptime = (p->parent->sleeptime * EXIT_WEIGHT +
+ p->sleeptime) / (EXIT_WEIGHT + 1);
+
+ sleeptime_runtime_update(p->parent);
}

/**
@@ -1238,8 +1226,9 @@
* it possible for interactive tasks to use up their
* timeslices at their highest priority levels.
*/
- if (p->sleep_avg)
- p->sleep_avg--;
+ p->runtime++;
+ sleeptime_runtime_update(p);
+
if (unlikely(rt_task(p))) {
/*
* RR tasks need a special form of timeslice management.
@@ -1259,6 +1248,7 @@
if (!--p->time_slice) {
dequeue_task(p, rq->active);
set_tsk_need_resched(p);
+ sleeptime_runtime_update(p);
p->prio = effective_prio(p);
p->time_slice = task_timeslice(p);
p->first_time_slice = 0;
@@ -2155,6 +2145,7 @@
if (retval)
goto out_unlock;

+ sleeptime_runtime_update(p);
jiffies_to_timespec(p->policy & SCHED_FIFO ?
0 : task_timeslice(p), &t);
read_unlock(&tasklist_lock);
\
 
 \ /
  Last update: 2005-03-22 13:48    [W:0.062 / U:0.072 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site