Messages in this thread Patch in this message | | | From | Francesco Sportolari <> | Subject | Re: [PATCH] yet another scheduler patch | Date | Tue, 9 Sep 2003 13:23:53 +0200 |
| |
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, ¤t->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); | |