sched throttle tree extract
Subsystems (2)
cover sched throttle tree extract
Greetings,
The following 9 patches is an extraction of my scheduler throttling tree against 2.6.16-mm2. The patch below has already been applied, and is only included such that anyone applying these patches to virgin source will see no offsets.
-Mike
kernel/sched.c renamed from kernel/sched.c.org +1 -1
@@ -820,7 +820,7 @@ static void __activate_task(task_t *p, r {prio_array_t *target = rq->active; -if (unlikely (batch_task (p) ||expired_starving (rq))) +if (unlikely (batch_task (p) || (expired_starving (rq) && !rt_task (p)))) target = rq->expired;enqueue_task (p, target);inc_nr_running (p, rq);
Re: [patch 2.6.16-mm2 1/9] sched throttle tree extract - ignore invalid timestamps
On an SMP system, a task can awaken on a different cpu from where it went to sleep. Timestamp inaccuracies can result from the attempt to compensate for clock drift. Ignore resulting timewarps.
kernel/sched.c renamed from kernel/sched.c-0.fix_rt +9 -0
@@ -845,6 +845,15 @@ static int recalc_task_prio(task_t *p, uunsigned long long __sleep_time = now - p->timestamp;unsigned long sleep_time; +/* +* On SMP systems, a task can go to sleep on one CPU +* and wake up on another. When this happens, now can +* end up being less than p->timestamp for short sleeps. +* Ignore these, they're insignificant. +*/ +if (unlikely (now < p->timestamp)) + __sleep_time =0 ; +if (batch_task (p)) sleep_time =0 ;else {
Re: [patch 2.6.16-mm2 2/9] sched throttle tree extract - fix potential task uninterruptible bug
This patch fixes a bug waiting for a place to happen should anyone ever combine TASK_NONINTERACTIVE with TASK_UNINTERRUPTIBLE.
kernel/sched.c renamed from kernel/sched.c-1.timewarp +2 -2
@@ -1457,7 +1457,7 @@ out_set_cpu: out_activate:#endif /* CONFIG_SMP */ -if (old_state ==TASK_UNINTERRUPTIBLE ) { +if (old_state &TASK_UNINTERRUPTIBLE ) { rq->nr_uninterruptible--;/* * Tasks on involuntary sleep don't earn
@@ -3167,7 +3167,7 @@ need_resched_nonpreemptible: unlikely(signal_pending(prev)))) prev->state = TASK_RUNNING; else { -if (prev->state ==TASK_UNINTERRUPTIBLE ) +if (prev->state &TASK_UNINTERRUPTIBLE ) rq->nr_uninterruptible++;deactivate_task (prev, rq); }
Re: [patch 2.6.16-mm2 3/9] sched throttle tree extract - remove IO priority barrier
This patch removes the barrier preventing IO bound tasks from competing against highly interactive tasks for cpu time. This barrier has been demonstrated to cause starvation of IO bound tasks, and in testing, I've found it to now be unnecessary in any case.
kernel/sched.c renamed from kernel/sched.c-2.fix_uninterruptible +0 -15
@@ -880,21 +880,6 @@ static int recalc_task_prio(task_t *p, u p->sleep_avg = ceiling; }else {/* -* Tasks waking from uninterruptible sleep are -* limited in their sleep_avg rise as they -* are likely to be waiting on I/O -*/ -if (p->sleep_type ==SLEEP_NONINTERACTIVE && p->mm) { -if (p->sleep_avg >=INTERACTIVE_SLEEP (p)) - sleep_time =0 ; -else if (p->sleep_avg + sleep_time >= -INTERACTIVE_SLEEP (p)) { - p->sleep_avg =INTERACTIVE_SLEEP (p); - sleep_time =0 ; - } - } - -/* * This code gives a bonus to interactive tasks. * * The boost works by updating the 'average sleep time'
Re: [patch 2.6.16-mm2 4/9] sched throttle tree extract - remove kthread barrier
This patch removes the last barrier between a normal task using dynamic priorities and kthreads using the same. In testing, this separation has proven to be unnecessary.
kernel/sched.c renamed from kernel/sched.c-3.remove_IO_barrier +3 -3
@@ -865,13 +865,13 @@ static int recalc_task_prio(task_t *p, uif (likely (sleep_time >0 )) {/* -* User tasks that sleep a long time are categorised as -* idle. They will only have their sleep_avg increased to a +* Tasks that sleep a long time are categorised as idle. +* They will only have their sleep_avg increased to a * level that makes them just interactive priority to stay * active yet prevent them suddenly becoming cpu hogs and * starving other processes. */ -if (p->mm && sleep_time >INTERACTIVE_SLEEP (p)) { +if (sleep_time >INTERACTIVE_SLEEP (p)) {unsigned long ceiling; ceiling = JIFFIES_TO_NS(MAX_SLEEP_AVG -
Re: [patch 2.6.16-mm2 5/9] sched throttle tree extract - correct idle sleep logic
This patch corrects the idle sleep logic to place a long sleeping task into the runqueue at a barely interactive priority such that it can not destroy interactivity should it immediately begin consuming massive cpu.
It further ensures that no task will cross the boundary from normal task to interactive task without first stopping at the border before moving on. Note, that this in no way hinders a long sleeping task from waking at max priority. They stop on the way up, but are not truncated. This only prevents long sleeping tasks from slamming straight to max interactive with one sleep, and causing trouble.
kernel/sched.c renamed from kernel/sched.c-4.remove_kthread_barrier +38 -9
@@ -99,6 +99,9 @@#define MAX_SLEEP_AVG (DEF_TIMESLICE * MAX_BONUS)#define STARVATION_LIMIT (MAX_SLEEP_AVG)#define NS_MAX_SLEEP_AVG (JIFFIES_TO_NS(MAX_SLEEP_AVG)) +#define NS_MAX_SLEEP_AVG_PCNT (NS_MAX_SLEEP_AVG / 100) +#define PCNT_PER_DYNPRIO (100 / MAX_BONUS) +#define NS_PER_DYNPRIO (PCNT_PER_DYNPRIO * NS_MAX_SLEEP_AVG_PCNT)/* * If a task is 'interactive' then we reinsert it in the active
@@ -153,9 +156,23 @@#define TASK_INTERACTIVE (p) \ ((p)->prio <= (p)->static_prio - DELTA(p)) -#define INTERACTIVE_SLEEP (p) \ - (JIFFIES_TO_NS(MAX_SLEEP_AVG * \ - (MAX_BONUS / 2 + DELTA((p)) + 1) / MAX_BONUS - 1)) +#define INTERACTIVE_SLEEP_AVG (p) \ + (min(JIFFIES_TO_NS(MAX_SLEEP_AVG * (MAX_BONUS / 2 + DELTA(p)) / \ + MAX_BONUS), NS_MAX_SLEEP_AVG)) + +/* +* Returns whether a task has been asleep long enough to be considered idle. +* The metric is whether this quantity of sleep would promote the task more +* than one priority beyond marginally interactive. +*/ +static int task_interactive_idle (task_t *p,unsigned long sleep_time) +{ +unsigned long ceiling = (CURRENT_BONUS (p) +2 ) *NS_PER_DYNPRIO ; + +if (p->sleep_avg + sleep_time < ceiling) +return 0 ; +return p->sleep_avg + sleep_time >=INTERACTIVE_SLEEP_AVG (p); +}#define TASK_PREEMPTS_CURR (p, rq) \ ((p)->prio < (rq)->curr->prio)
@@ -871,13 +888,25 @@ static int recalc_task_prio(task_t *p, u* active yet prevent them suddenly becoming cpu hogs and * starving other processes. */ -if (sleep_time >INTERACTIVE_SLEEP (p)) { -unsigned long ceiling; +if (task_interactive_idle (p, sleep_time)) { +unsigned long ceiling =INTERACTIVE_SLEEP_AVG (p); + +/* +* Promote previously interactive task. +*/ +if (p->sleep_avg > ceiling) { + ceiling = p->sleep_avg /NS_PER_DYNPRIO ; +if (ceiling <MAX_BONUS ) + ceiling++; + ceiling *=NS_PER_DYNPRIO ; + }else { + ceiling += p->slice_time_ns >>2 ; +if (ceiling >NS_MAX_SLEEP_AVG ) + ceiling =NS_MAX_SLEEP_AVG ; + } - ceiling =JIFFIES_TO_NS (MAX_SLEEP_AVG - -DEF_TIMESLICE ); -if (p->sleep_avg < ceiling) - p->sleep_avg = ceiling; +if (p->sleep_avg < ceiling) + p->sleep_avg = ceiling; }else {/* * This code gives a bonus to interactive tasks.
Re: [patch 2.6.16-mm2 6/9] sched throttle tree extract - move division to slow path
This patch moves division of runtime from the fast path into the slow path. In doing so, it converts the task's time slice into nanoseconds, which also disallows high frequency scheduling tasks from stealing time from their neighbors by ducking the timer interrupt. (two birds, one stone)
slice_time_ns is identical in function to time_slice, but conversion of everything that referred to time_slice to nanoseconds just made a mess. Ergo, I close the lesser of two evils, and duplicated what was necessary to allow use of nanoseconds only where needed.
include/linux/sched.h renamed from include/linux/sched.h.org +1 -0
@@ -744,6 +744,7 @@ struct task_struct {unsigned long policy;cpumask_t cpus_allowed;unsigned int time_slice, first_time_slice; +long slice_time_ns;#ifdef CONFIG_SCHEDSTATS struct sched_info sched_info;
kernel/sched.c renamed from kernel/sched.c-5.interactive_idle +43 -30
164 lines not on this page · raw message
Re: [patch 2.6.16-mm2 7/9] sched throttle tree extract - implement throttling
This patch implements task throttling. In order to determine whether a task needs throttling, compute slice_avg, which is the upper limit a task's sleep_avg can be and be sane. A task which consumes no more than what is expected accrues CPU credit, which may be used later, on a slice by slice basis. This allows interactive tasks to perform in high cpu usage bursts, yet we retain control over their long term cpu usage. A task which exhausts it's earned credit will have it's sleep_avg trimmed, and consequently it's priority trimmed to match it's actual cpu usage.
include/linux/sched.h renamed from include/linux/sched.h.org +2 -2
@@ -736,14 +736,14 @@ struct task_struct {unsigned short ioprio;unsigned int btrace_seq; -unsigned long sleep_avg; +unsigned long sleep_avg, last_slice, throttle;unsigned long long timestamp, last_ran;unsigned long long sched_time;/* sched_clock time spent running */ enum sleep_type sleep_type;unsigned long policy;cpumask_t cpus_allowed; -unsigned int time_slice, first_time_slice; +unsigned int time_slice, slice_info;long slice_time_ns;#ifdef CONFIG_SCHEDSTATS
kernel/sched.c renamed from kernel/sched.c-6.move_division +243 -22
340 lines not on this page · raw message
Re: [patch 2.6.16-mm2 8/9] sched throttle tree extract - maximize timeslice accounting
This patch maximizes time slice accounting. A task which receives too much CPU time due to missing the timer interrupt will have the excess deducted from it's next slice.
kernel/sched.c renamed from kernel/sched.c-7.implement_throttle +18 -3
@@ -2966,13 +2966,28 @@ static void refresh_timeslice(task_t *p)unsigned int slice =last_slice (p);unsigned int slice_avg, cpu, idle;long run_time =-1 * p->slice_time_ns; +long slice_time_ns =task_timeslice_ns (p);int w =MAX_BONUS , delta, bonus;/* -* Update time_slice. +* Update time_slice. Account for unused fragment, +* or excess time received due to missed tick. */ - p->slice_time_ns =task_timeslice_ns (p); - p->time_slice =task_timeslice (p); + p->slice_time_ns += slice_time_ns; +/* +* Not common, but this does happen on SMP systems. +* Timeslice theft of this magnitude has never been +* observed in the wild, so assume that this is BS, +* and give the poor task it's full slice. Theory: +* mostly idle task migrates between CPUs numerous +* times during it's slice, timestamp rounding leads +* to wildly inaccurate calculation. Rounding has +* maximum effect on those who stretch their slice, +* but is also fairly meaningless, so ignore it. +*/ +if (unlikely (p->slice_time_ns <NS_TICK )) + p->slice_time_ns = slice_time_ns; + p->time_slice =NS_TO_JIFFIES (p->slice_time_ns);set_last_slice (p, p->time_slice);/*
Re: [patch 2.6.16-mm2 9/9] sched throttle tree extract - export tunables
This patch is a convenience for people testing this patch series. It exports throttling tunables to userland, and is utterly disposable.
include/linux/sysctl.h renamed from include/linux/sysctl.h.org +2 -0
@@ -148,6 +148,8 @@ enumKERN_SPIN_RETRY =70 ,/* int: number of spinlock retries */ KERN_ACPI_VIDEO_FLAGS =71 ,/* int: flags for setting up video after ACPI sleep */ KERN_IA64_UNALIGNED =72 ,/* int: ia64 unaligned userland trap enable */ +KERN_SCHED_THROTTLE1 =73 ,/* int: throttling credit period 1 in secs */ + KERN_SCHED_THROTTLE2=74, /* int: throttling credit period 2 in secs */ };
kernel/sysctl.c renamed from kernel/sysctl.c.org +30 -6
@@ -73,6 +73,9 @@ extern int printk_ratelimit_burst;extern int pid_max_min, pid_max_max;extern int sysctl_drop_caches;extern int percpu_pagelist_fraction; +extern int credit_c1; +extern int credit_c2; +extern int credit_max;#if defined(CONFIG_X86_LOCAL_APIC ) && defined(CONFIG_X86 )int unknown_nmi_panic;
@@ -230,6 +233,11 @@ static ctl_table root_table[] = { { .ctl_name = 0 } }; +/* Constants for minimum and maximum testing in vm_table and +* kern_table. We use these as one-element integer vectors. */ +static int zero; +static int one_hundred =100 ; +static ctl_table kern_table[] = { { .ctl_name =KERN_OSTYPE ,
@@ -684,15 +692,31 @@ static ctl_table kern_table[] = { .proc_handler = &proc_dointvec, },#endif + { + .ctl_name = KERN_SCHED_THROTTLE1, + .procname = "credit_c1", + .data = &credit_c1, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec_minmax, + .strategy = &sysctl_intvec, + .extra1 = &zero, + .extra2 = &credit_max, + }, + { + .ctl_name = KERN_SCHED_THROTTLE2, + .procname = "credit_c2", + .data = &credit_c2, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec_minmax, + .strategy = &sysctl_intvec, + .extra1 = &zero, + .extra2 = &credit_max, + }, { .ctl_name = 0 } }; -/* Constants for minimum and maximum testing in vm_table. -We use these as one-element integer vectors. */ -static int zero; -static int one_hundred =100 ; - -static ctl_table vm_table[] = { { .ctl_name =VM_OVERCOMMIT_MEMORY ,
kernel/sched.c renamed from kernel/sched.c-8.slice_accounting +5 -4
@@ -220,11 +220,12 @@ static int task_interactive_idle(task_t* credit that fits in 32 bits jiffies is 42949 seconds. */ -#define CREDIT_C1 10 -#define CREDIT_C2 14400 +int credit_c1 =10 ; +int credit_c2 =14400 ; +int credit_max =42949 ; -#define C1 (CREDIT_C1 * MAX_BONUS * HZ) -#define C2 (CREDIT_C2 * MAX_BONUS * HZ + C1) +#define C1 (credit_c1 * MAX_BONUS * HZ) +#define C2 (credit_c2 * MAX_BONUS * HZ + C1)#define C3 (MAX_BONUS * C2)#define credit_exhausted (p, credit) \
Re: [patch 2.6.16-mm2 5/9] sched throttle tree extract - correct idle sleep logic
In reply to Mike GalbraithQuoted 4 lines · Mike Galbraith
This patch corrects the idle sleep logic to place a long sleeping task into the runqueue at a barely interactive priority such that it can not destroy interactivity should it immediately begin consuming massive cpu.
Did you test this extensively with bloated apps like Evolution and Firefox that need to be scheduled as interactive tasks even though they often peg the CPU?
Lee
Re: [patch 2.6.16-mm2 5/9] sched throttle tree extract - correct idle sleep logic
Quoted 9 lines · Lee Revell
Quoted 4 lines · Mike Galbraith
This patch corrects the idle sleep logic to place a long sleeping task into the runqueue at a barely interactive priority such that it can not destroy interactivity should it immediately begin consuming massive cpu.
Did you test this extensively with bloated apps like Evolution and Firefox that need to be scheduled as interactive tasks even though they often peg the CPU?
I use both Evolution and Firefox with no problems. Well, no problems isn't quite true, Evolution slogs along terribly when IO is going on, but that isn't a scheduler issue. My desktop experience has zero problems with these patches, but YMMV.
These patches are much more about anti-starvation than interactive task selection. Tasks which were scheduled as interactive before should remain so, but that's not to say that they won't ever be throttled. There is no way to differentiate between nice cpu hog and evil cpu hog, and these patches do no even attempt to do so. These patches simply enforce a set of rules. There is no doubt in my mind that these rules will not be favorable to every interactive task situation.
I can give you one right off the top of my head. A visualization for your mp3 player is a pure cpu hog right from the start, and will be throttled. If you test this, you'll see that despite that, it does a pretty darn good job with the problem.
-Mike
Re: [patch 2.6.16-mm2 10/9] sched throttle tree extract - kill interactive task feedback loop
In reply to Mike GalbraithGreetings,
The patch below stops interactive tasks from feeding off each other during round-robin.
With this 10th patch in place, a busy server with _default_ throttle settings (ie tunables may now be mostly unneeded) looks like this:
[root]:# w
18:38:00 up 23 min, 2 users, load average: 10.07, 9.94, 7.50
USER TTY LOGIN@ IDLE JCPU PCPU WHAT root tty1 18:15 22:12 30.89s 30.84s top d1 root pts/0 18:20 0.00s 0.07s 0.00s w
[root]:# time netstat|grep :81|wc -l
1758
real 0m0.304s user 0m0.144s sys 0m0.135s
[root]:# time netstat|grep :81|wc -l
1776
real 0m0.306s user 0m0.118s sys 0m0.163s
[root]:# time netstat|grep :81|wc -l
1799
real 0m0.493s user 0m0.146s sys 0m0.141s
[root]:#
My desktop still feels just peachy.
kernel/sched.c renamed from kernel/sched.c-9.export_tunables +1 -1
@@ -3480,7 +3480,7 @@ go_idle: queue = array->queue + idx; next =list_entry (queue->next, task_t, run_list); -if (!rt_task (next) &&interactive_sleep (next->sleep_type)) { +if (!TASK_INTERACTIVE (next) &&interactive_sleep (next->sleep_type)) {unsigned long long delta = now - next->timestamp;if (unlikely ((long long )(now - next->timestamp) <0 )) delta =0 ;
Re: [patch 2.6.16-mm2 10/9] sched throttle tree extract - kill interactive task feedback loop
Quoted 11 lines · Mike Galbraith
Greetings,
The patch below stops interactive tasks from feeding off each other during round-robin.
With this 10th patch in place, a busy server with _default_ throttle settings (ie tunables may now be mostly unneeded) looks like this:
--- linux-2.6.16-mm2/kernel/sched.c-9.export_tunables 2006-03-31
13:37:09.000000000 +0200 +++linux-2.6.16-mm2/kernel/sched.c2006-04-05
19:22:01.000000000 +0200 @@ -3480,7 +3480,7 @@go_idle:
kernel/sched.c go_idle: · line 3483
Quoted 5 lines
kernel/sched.c renamed from kernel/sched.c-9.export_tunables +1
-1queue = array->queue + idx; next =list_entry (queue->next, task_t, run_list); -if (!rt_task (next) &&interactive_sleep (next->sleep_type)) { +if (!TASK_INTERACTIVE (next) &&interactive_sleep (next->sleep_type)) {
You can't remove that rt_task check from there can you? We shouldn't ever requeue a rt task.
Cheers,
Con
Re: [patch 2.6.16-mm2 10/9] sched throttle tree extract - kill interactive task feedback loop
Quoted 15 lines · Con Kolivas
Quoted 14 lines · Mike Galbraith
Greetings,
The patch below stops interactive tasks from feeding off each other during round-robin.
With this 10th patch in place, a busy server with _default_ throttle settings (ie tunables may now be mostly unneeded) looks like this:
--- linux-2.6.16-mm2/kernel/sched.c-9.export_tunables 2006-03-31
13:37:09.000000000 +0200 +++linux-2.6.16-mm2/kernel/sched.c2006-04-05
19:22:01.000000000 +0200 @@ -3480,7 +3480,7 @@go_idle:kernel/sched.c renamed from kernel/sched.c-9.export_tunables +0
-0queue = array->queue + idx; next =list_entry (queue->next, task_t, run_list);
Quoted 5 lines
kernel/sched.c go_idle: · line 3483
Quoted 2 lines
kernel/sched.c renamed from kernel/sched.c-9.export_tunables +1
-1-if (!rt_task (next) &&interactive_sleep (next->sleep_type)) { +if (!TASK_INTERACTIVE (next) &&interactive_sleep (next->sleep_type)) {You can't remove that
rt_taskcheck from there can you? We shouldn't ever requeue a rt task.
RT tasks are always interactive aren't they? (I'll check)
Anyway, this is definitely a large part of the problem with the ssh to busy server, but a complete block of interactive tasks isn't quite the right solution. With an SMP kernel, my desktop appeared to be fine, but a quick spin with UP kernel isn't looking quite so good. This needs more investigation.
-Mike
Re: [patch 2.6.16-mm2 10/9] sched throttle tree extract - kill interactive task feedback loop
Quoted 9 lines · Mike Galbraith
Quoted 6 lines · Con Kolivas
kernel/sched.c go_idle: · line 3483
Quoted 2 lines · Mike Galbraith
kernel/sched.c renamed from kernel/sched.c-9.export_tunables +1
-1-if (!rt_task (next) &&interactive_sleep (next->sleep_type)) { +if (!TASK_INTERACTIVE (next) &&interactive_sleep (next->sleep_type)) {You can't remove that
rt_taskcheck from there can you? We shouldn't ever requeue a rt task.RT tasks are always interactive aren't they? (I'll check)
No, they're always equal to their static_prio. This rt_task check was added originally because it was found to inappropriately be requeueing SCHED_FIFO tasks.
Cheers,
Con