massive_intr on CFS, BFS, and EDF
Subsystems (8)
Hi,
I tried massive_intr, a process scheduler's fairness and throughtput testing program for massive interactive processes, on vanilla 2.6.31, 2.6.31-bfs211 (with BFS) and 2.6.31-edf(latest linus tree + EDF patch).
CFS and BFS look good. CFS has better fairness, and BFS has better throughput. EDF looks unfair and is unstable. I tested 3 times and the tendency was the same.
NOTE:
- BFS patch is applied to 2.6.31, but EDF patch is applied to latest linus tree, so they can't compare strictly. This report is just FYI.
- EDF kernel shows some strange behavior as follows:
* aptitude(debian package management tool) stacks on the way
* oocalc doesn't start
- I dont't subscribe lkml now. So if you reply, pleas CC me.
Thanks,
Satoru
===============================================================================
[ test envinronment ]
A laptop machine with x86_64 dual core CPU
[ test program ]
# CFS and BFS:
$ massive_intr 30 30
# EDF
$ schedtool -E -d 100000 -b 25000 -e ./massive_intr 30 30
It means running 30 interactive processes simultaneously for 30 secs. Full description of this program is on the comments of source code.
URL:
http://people.redhat.com/mingo/cfs-scheduler/tools/massive_intr.c
[ test result ]
+---------------+-----------+---------+---------+---------+-----------+ | kernel | scheduler | avg(*1) | min(*2) | max(*3) | stdev(*4) | +---------------+-----------+---------+---------+---------+-----------+ | 2.6.31 | CFS | 246 | 240 | 247 | 1.3 | | 2.6.31-bfs211 | BFS | 254 | 241 | 268 | 7.1 | +---------------+-----------+---------+---------+---------+-----------+ | 2.6.31-edf(*5)| EDF | 440 | 154 | 1405 | 444.8 | +---------------+-----------+---------+---------+---------+-----------+
*1) average number of loops among all processes
*2) minimum number of loops among all processes
*3) maximum number of loops among all processes
*4) standard deviation
*5) EDF kernel hanged up on the way. The data is only among 7 threads.
High average means good throughput, and low stdev means good fairness.
[raw data]
# vanilla 2.6.31 (CFS) sat@debian:~/practice/bfs$ uname -r 2.6.31 sat@debian:~/practice/bfs$ ./massive_intr 30 30 003873 00000246 003893 00000246 003898 00000240 003876 00000245 003888 00000245 003870 00000245 003882 00000247 003890 00000245 003872 00000245 003880 00000246 003895 00000246 003892 00000246 003878 00000246 003874 00000246 003896 00000246 003897 00000246 003884 00000246 003891 00000246 003894 00000246 003871 00000246 003886 00000247 003877 00000246 003879 00000246 003889 00000246 003881 00000246 003899 00000244 003887 00000247 003875 00000247 003885 00000247 003883 00000247
# 2.6.31-bfs211
sat@debian:~/practice/bfs$ uname -r 2.6.31-bfs211 sat@debian:~/practice/bfs$ ./massive_intr 30 30 004143 00000248 004127 00000241 004154 00000252 004145 00000255 004137 00000251 004148 00000263 004135 00000261 004153 00000247 004132 00000250 004146 00000248 004140 00000251 004130 00000245 004138 00000267 004136 00000249 004139 00000262 004141 00000255 004147 00000251 004131 00000253 004150 00000254 004152 00000254 004129 00000253 004142 00000242 004151 00000268 004128 00000263 004134 00000260 004144 00000252 004133 00000254 004149 00000265 004126 00000252 004125 00000246
# 2.6.31-edf (latest linus tree + edf patch)
sat@debian:~/practice/bfs$ uname -r 2.6.31-edf sat@debian:~/practice/bfs$ schedtool-edf/schedtool -E -d 100000 -b 25000 -e ./massive_intr 30 30 Dumping mode: 0xa Dumping affinity: 0xffffffff We have 3 args to do Dump arg 0: ./massive_intr Dump arg 1: 30 Dump arg 2: 30 003915 00000541 003914 00001405 003916 00000310 003924 00000177 003923 00000154 003917 00000280 003918 00000211 # <kernel hunged up here>
Hi Raistlin,
sat さんは書きました:
Quoted 1 line
NOTE:
....
Quoted 4 lines
- EDF kernel shows some strange behavior as follows:
* aptitude(debian package management tool) stacks on the way
* oocalc doesn't start
In addition, aptitude and oocalc are not SCHED_EDF, but SCHED_OTHER (SCHED_FAIR). So you probably broke some codes other than sched_edf part.
Thanks,
Satoru
Quoted 2 lines · sat
Hi,
Hi,
Quoted 4 lines
I tried
massive_intr, a process scheduler's fairness and throughtput testing program for massive interactive processes, on vanilla 2.6.31, 2.6.31-bfs211 (with BFS) and 2.6.31-edf(latest linus tree + EDF patch).
Hey, thanks a lot, that's interesting!
Quoted 9 lines
CFS and BFS look good. CFS has better fairness, and BFS has better throughput. EDF looks unfair and is unstable. I tested 3 times and the tendency was the same.
NOTE:
- BFS patch is applied to 2.6.31, but EDF patch is applied to latest linus tree, so they can't compare strictly. This report is just FYI.
Quoted 7 lines
- EDF kernel shows some strange behavior as follows:
* aptitude(debian package management tool) stacks on the way
* oocalc doesn't start- I dont't subscribe lkml now. So if you reply, pleas CC me.
Ok... I have to run now, but I'll look carefully at the results when I'll be back.
In the meanwhile, if you want and have time, here's a new version of the patch, which solves some BUGs, in case you want to you give it another try...
arch/arm/include/asm/unistd.h +3 -0
@@ -391,6 +391,9 @@#define __NR_pwritev (__NR_SYSCALL_BASE+362)#define __NR_rt_tgsigqueueinfo (__NR_SYSCALL_BASE+363)#define __NR_perf_event_open (__NR_SYSCALL_BASE+364) +#define __NR_sched_setscheduler_ex (__NR_SYSCALL_BASE+365) +#define __NR_sched_setparam_ex (__NR_SYSCALL_BASE+366) +#define __NR_sched_getparam_ex (__NR_SYSCALL_BASE+367)/* * The following SWIs are ARM private.
arch/arm/kernel/calls.S +3 -0
@@ -374,6 +374,9 @@ CALL(sys_pwritev) CALL(sys_rt_tgsigqueueinfo) CALL(sys_perf_event_open) +/* 365 */ CALL(sys_sched_setscheduler_ex) + CALL(sys_sched_setparam_ex) + CALL(sys_sched_getparam_ex) #ifndef syscalls_counted .equ syscalls_padding, ((NR_syscalls + 3) & ~3) - NR_syscalls #define syscalls_counted
arch/x86/ia32/ia32entry.S +3 -0
@@ -832,4 +832,7 @@ ia32_sys_call_table: .quad compat_sys_pwritev .quad compat_sys_rt_tgsigqueueinfo /* 335 */ .quad sys_perf_event_open + .quad sys_sched_setscheduler_ex + .quad sys_sched_setparam_ex + .quad sys_sched_getparam_ex ia32_syscall_end:
arch/x86/include/asm/unistd_32.h +3 -0
@@ -342,6 +342,9 @@#define __NR_pwritev 334#define __NR_rt_tgsigqueueinfo 335#define __NR_perf_event_open 336 +#define __NR_sched_setscheduler_ex 337 +#define __NR_sched_setparam_ex 338 +#define __NR_sched_getparam_ex 339#ifdef __KERNEL__
arch/x86/include/asm/unistd_64.h +6 -0
@@ -661,6 +661,12 @@ __SYSCALL(__NR_pwritev, sys_pwritev) __SYSCALL(__NR_rt_tgsigqueueinfo, sys_rt_tgsigqueueinfo)#define __NR_perf_event_open 298 __SYSCALL(__NR_perf_event_open, sys_perf_event_open) +#define __NR_sched_setscheduler_ex 299 +__SYSCALL(__NR_sched_setscheduler_ex, sys_sched_setscheduler_ex) +#define __NR_sched_setparam_ex 230 +__SYSCALL(__NR_sched_setparam_ex, sys_sched_setparam_ex) +#define __NR_sched_getparam_ex 231 +__SYSCALL(__NR_sched_getparam_ex, sys_sched_getparam_ex)#ifndef __NO_STUBS#define __ARCH_WANT_OLD_READDIR
arch/x86/kernel/syscall_table_32.S +3 -0
@@ -336,3 +336,6 @@ ENTRY(sys_call_table) .long sys_pwritev .long sys_rt_tgsigqueueinfo /* 335 */ .long sys_perf_event_open + .long sys_sched_setscheduler_ex + .long sys_sched_setparam_ex + .long sys_sched_getparam_ex
include/linux/sched.h +57 -0
105 lines not on this page · raw message
include/linux/syscalls.h +7 -0
@@ -33,6 +33,7 @@ struct pollfd;struct rlimit ;struct rusage ;struct sched_param ; +struct sched_param_ex ;struct semaphore ;struct sembuf ;struct shmid_ds ;
@@ -390,11 +391,17 @@ asmlinkage long sys_clock_nanosleep(clockid_t which_clock, int flags,asmlinkage long sys_nice (int increment);asmlinkage long sys_sched_setscheduler (pid_t pid,int policy,struct sched_param __user *param); +asmlinkage long sys_sched_setscheduler_ex (pid_t pid,int policy, +struct sched_param_ex __user *param);asmlinkage long sys_sched_setparam (pid_t pid,struct sched_param __user *param); +asmlinkage long sys_sched_setparam_ex (pid_t pid, +struct sched_param_ex __user *param);asmlinkage long sys_sched_getscheduler (pid_t pid);asmlinkage long sys_sched_getparam (pid_t pid,struct sched_param __user *param); +asmlinkage long sys_sched_getparam_ex (pid_t pid, +struct sched_param_ex __user *param);asmlinkage long sys_sched_setaffinity (pid_t pid,unsigned int len,unsigned long __user *user_mask_ptr); asmlinkage long sys_sched_getaffinity(pid_t pid, unsigned int len,
init/Kconfig +14 -0
@@ -454,6 +454,20 @@ config RT_GROUP_SCHED realtime bandwidth for them. See Documentation/scheduler/sched-rt-group.txt for more information. +config EDF_GROUP_SCHED + bool "Group scheduling for SCHED_EDF" + depends on EXPERIMENTAL + depends on GROUP_SCHED + depends on CGROUPS + depends on !USER_SCHED + select CPUSETS + default n + help + This feature lets you explicitly specify, in terms of runtime + and period, the bandwidth of a task control group. This means + tasks and other control groups can be added, until such bandwidth + limit is reached, after that they will fail. + choice depends on GROUP_SCHED prompt "Basis for grouping tasks"
kernel/fork.c +12 -0
@@ -1226,6 +1226,18 @@ static struct task_struct *copy_process(unsigned long clone_flags, p->parent_exec_id = current->self_exec_id; } +/* +* In case an EDF task is forking, both parent and child get half +* the bandwidth of the parent (via dividing runtime by 2). +* This make it a lot easier to deal with control group bandwidth, and +* also prevent an heavily spawning task to exhaust the system (or +* a control group, if enabled) bandwidht. +*/ +if (edf_task (p->real_parent)) { + p->real_parent->edf.runtime_max /=2 ; + p->edf.runtime_max = p->real_parent->edf.runtime_max; + } +spin_lock (¤t->sighand->siglock);/*
kernel/sched.c +556 -19
853 lines not on this page · raw message
kernel/sched_debug.c +35 -1
@@ -146,7 +146,8 @@ static void print_rq(struct seq_file *m, struct rq *rq, int rq_cpu) }#if defined(CONFIG_CGROUP_SCHED ) && \ - (defined(CONFIG_FAIR_GROUP_SCHED ) || defined(CONFIG_RT_GROUP_SCHED )) + (defined(CONFIG_FAIR_GROUP_SCHED ) || defined(CONFIG_RT_GROUP_SCHED ) || \ + defined(CONFIG_EDF_GROUP_SCHED ))static void task_group_path (struct task_group *tg,char *buf,int buflen) {/* may be NULL if the underlying cgroup isn't fully-created yet */
@@ -218,6 +219,38 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)#endif } +void print_edf_rq (struct seq_file *m,int cpu,struct edf_rq *edf_rq) +{ +s64 min_deadline =-1 , max_deadline =-1 ; +struct rq *rq = &per_cpu (runqueues, cpu); +struct sched_edf_entity *last; +unsigned long flags; + +SEQ_printf (m,"\nedf_rq[%d]:\n" , cpu); + +spin_lock_irqsave (&rq->lock, flags); +if (edf_rq->rb_leftmost) + min_deadline = (rb_entry (edf_rq->rb_leftmost, + struct sched_edf_entity, + rb_node))->deadline; + last =__pick_edf_last_entity (edf_rq); +if (last) + max_deadline = last->deadline; +spin_unlock_irqrestore (&rq->lock, flags); + +#define P (x) \ + SEQ_printf(m, " .%-30s: %Ld\n", #x, (long long)(x)) +#define PN (x) \ + SEQ_printf(m, " .%-30s: %Ld.%06ld\n", #x, SPLIT_NS(x)) + +P (edf_rq->edf_nr_running); +PN (min_deadline); +PN (max_deadline); + +#undef PN +#undef P +} +void print_rt_rq (struct seq_file *m,int cpu,struct rt_rq *rt_rq) {#if defined(CONFIG_CGROUP_SCHED ) && defined(CONFIG_RT_GROUP_SCHED )
@@ -300,6 +333,7 @@ static void print_cpu(struct seq_file *m, int cpu)#undef P#endif print_cfs_stats (m, cpu); +print_edf_stats (m, cpu);print_rt_stats (m, cpu);print_rq (m, rq, cpu);
kernel/sched_edf.c new file +548 -0
548 lines not on this page · raw message
kernel/sched_fair.c +1 -3
@@ -1571,10 +1571,8 @@ static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_update_curr (cfs_rq); -if (unlikely (rt_prio (p->prio))) { +if (rt_prio (p->prio) ||task_has_edf_policy (p))resched_task (curr); -return ; - }if (unlikely (p->sched_class != &fair_sched_class))return ;
kernel/sched_rt.c +1 -1
@@ -1746,7 +1746,7 @@ unsigned int get_rr_interval_rt(struct task_struct *task) }static const struct sched_class rt_sched_class = { - .next = &fair_sched_class, + .next = &edf_sched_class, .enqueue_task = enqueue_task_rt, .dequeue_task = dequeue_task_rt, .yield_task = yield_task_rt,
kernel/trace/trace_sched_wakeup.c +31 -0
@@ -24,6 +24,7 @@ static int __read_mostly tracer_enabled;static struct task_struct *wakeup_task;static int wakeup_cpu; +static int wakeup_edf;static int wakeup_current_cpu;static unsigned wakeup_prio =-1 ;static int wakeup_rt;
@@ -214,6 +215,9 @@ probe_wakeup(struct rq *rq, struct task_struct *p, int success)tracing_record_cmdline (p);tracing_record_cmdline (current); +if (wakeup_edf && !edf_task (p)) +return ; +if ((wakeup_rt && !rt_task (p)) || p->prio >= wakeup_prio || p->prio >= current->prio)
@@ -340,12 +344,21 @@ static int __wakeup_tracer_init(struct trace_array *tr)static int wakeup_tracer_init (struct trace_array *tr) { + wakeup_edf =0 ; + wakeup_rt =0 ; +return __wakeup_tracer_init (tr); +} + +static int wakeup_edf_tracer_init (struct trace_array *tr) +{ + wakeup_edf =1 ; wakeup_rt =0 ;return __wakeup_tracer_init (tr); }static int wakeup_rt_tracer_init (struct trace_array *tr) { + wakeup_edf =0 ; wakeup_rt =1 ;return __wakeup_tracer_init (tr); }
@@ -384,6 +397,20 @@ static struct tracer wakeup_tracer __read_mostly =#endif }; +static struct tracer wakeup_edf_tracer__read_mostly = +{ + .name ="wakeup_edf" , + .init = wakeup_edf_tracer_init, + .reset = wakeup_tracer_reset, + .start = wakeup_tracer_start, + .stop = wakeup_tracer_stop, + .wait_pipe = poll_wait_pipe, + .print_max =1 , +#ifdef CONFIG_FTRACE_SELFTEST + .selftest = trace_selftest_startup_wakeup, +#endif +}; +static struct tracer wakeup_rt_tracer__read_mostly = { .name ="wakeup_rt" ,
@@ -406,6 +433,10 @@ __init static int init_wakeup_tracer(void)if (ret)return ret; + ret =register_tracer (&wakeup_edf_tracer); +if (ret) +return ret; + ret =register_tracer (&wakeup_rt_tracer);if (ret)return ret;
Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere) ---------------------------------------------------------------------- Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa (Italy) http://blog.linux.it/raistlin / [email protected] / [email protected]
Quoted 4 lines · Satoru Takeuchi
In addition, aptitude and oocalc are not
SCHED_EDF, butSCHED_OTHER(SCHED_FAIR). So you probably broke some codes other thansched_edfpart.
Strange... It does not happen here, I'll investigate.
Thanks again,
Dario
Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere) ---------------------------------------------------------------------- Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa (Italy) http://blog.linux.it/raistlin / [email protected] / [email protected]
Hi,
Quoted 9 lines · sat
Hi,
I tried
massive_intr, a process scheduler's fairness and throughtput testing program for massive interactive processes, on vanilla 2.6.31, 2.6.31-bfs211 (with BFS) and 2.6.31-edf(latest linus tree + EDF patch).CFS and BFS look good. CFS has better fairness, and BFS has better throughput. EDF looks unfair and is unstable. I tested 3 times and the tendency was the same.
Thank you for your testing, the instability problems you hit are due to some bugs in our implementation, we'll try to reproduce and fix them. Your test shows that we have some problems with how we handle fork(); the code attempts at distributing the bandwidth between the parent and the child, and the fact that the children hang means that there is something wrong in how we handle recharges. It is important to note that the expected behavior of an edf scheduler is *not* a fair one. It has to do its best to guarantee the deadlines of the admitted tasks.
Regards Michael
Quoted 3 lines · Michael Trimarchi
It is important to note that
the expected behavior of an edf scheduler is *not* a fair one. It has to do its best to guarantee the deadlines of the admitted tasks.
Do you allow oversubscription with EDF? It would seem so based on these results. Would it maybe make sense to disallow oversubscription, or make it an option?
If you have massive oversubscription with EDF, what is the design intent? Do you try to meet the goals on as many tasks as possible, while the oversubscribed tasks get nothing?
Chris
Peter Zijlstra
maintainerQuoted 8 lines · Chris Friesen
Quoted 3 lines · Michael Trimarchi
It is important to note that
the expected behavior of an edf scheduler is *not* a fair one. It has to do its best to guarantee the deadlines of the admitted tasks.Do you allow oversubscription with EDF? It would seem so based on these results. Would it maybe make sense to disallow oversubscription, or make it an option?
afaiu he doesn't, he simply splits the task's wcet between parent and child and (intends?) to feed back on child exit.
Quoted 3 lines
If you have massive oversubscription with EDF, what is the design intent? Do you try to meet the goals on as many tasks as possible, while the oversubscribed tasks get nothing?
oversubscribing edf isn't in general recommended, iirc u>1 gives unbounded latencies with edf.
Quoted 8 lines · Peter Zijlstra
Quoted 3 lines · Chris Friesen
Do you allow oversubscription with EDF? It would seem so based on these results. Would it maybe make sense to disallow oversubscription, or make it an option?
afaiu he doesn't, he simply splits the task's wcet between parent and child and (intends?) to feed back on child exit.
How does this work if we have one parent task that forks off a bunch of kids like massive_intr? Does each child get half the bandwidth of the previous child?
Quoted 2 lines
oversubscribing edf isn't in general recommended, iirc u>1 gives unbounded latencies with edf.
Right...so would it perhaps be more interesting to try a modified test where each child's bandwidth is equal and small enough that there is no oversubscription?
Chris
Quoted 4 lines · Chris Friesen
Do you allow oversubscription with EDF? It would seem so based on these results. Would it maybe make sense to disallow oversubscription, or make it an option?
What I want is the user to be able to achieve whatever result he likes.
Thus, with EDF_GROUP_SCHED enabled, you first have to assign a bandwidth value, at least to the root group. If 100% (e.g., on UP) is used as such value, oversubscription will never happen.
If EDF_GROUP_SCHED is off, nothing is in place right now, but I already planned to add it, and I'm just introducing something like sysctl_sched_rt_runtime, sysctl_sched_rt_period, in the new version I'm working on right now.
Quoted 4 lines
If you have massive oversubscription with EDF, what is the design intent? Do you try to meet the goals on as many tasks as possible, while the oversubscribed tasks get nothing?
No, nothing like that... So using this scheduler without avoiding system overload will be nonsene, unless some kind of logic (as you was describing) is not implemented in userspace, and that's why I think oversubscription avoidance should be an available, but also, configurrable feature... Comments on that?
Regards,
Dario
Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere) ---------------------------------------------------------------------- Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa (Italy) http://blog.linux.it/raistlin / [email protected] / [email protected]
Quoted 6 lines · Peter Zijlstra
Quoted 3 lines · Chris Friesen
Do you allow oversubscription with EDF? It would seem so based on these results. Would it maybe make sense to disallow oversubscription, or make it an option?
afaiu he doesn't,
yeaah, as explained in the previous mail, this is in place only if group scheduling is on since now, but I'll add these bits to non-group solution, aalready planned that. :-)
Quoted 3 lines
he simply splits the task's wcet between parent and child and (intends?) to feed back on child exit.
yes again, that's what the submitted patch does, which is an arbitrary choice among all the non-optimal solutions I'm able to think of, as explained in the first e-mail! :-(
Now, I'm going to give your suggestion of assigning children 0 bandwidth a shot, and ask the parent (they can't they have no bandwidth!) to give them some runtime/deadline to make them run.
This also has some issues, I think, but looks more natural... At least does not affect parent's bandwidth, possibly reducing it to (almost) 0!! :-(
Regards,
Dario
Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere) ---------------------------------------------------------------------- Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa (Italy) http://blog.linux.it/raistlin / [email protected] / [email protected]
Quoted 8 lines · Chris Friesen
Quoted 2 lines · Peter Zijlstra
afaiu he doesn't, he simply splits the task's wcet between parent and child and (intends?) to feed back on child exit.
How does this work if we have one parent task that forks off a bunch of kids like
massive_intr? Does each child get half the bandwidth of the previous child?
Yes, that's exactly how I think it goes... Moreover, also the parent's bandwidth is halved at each fork, which make things very odd in workloads like massive_intr! :-(
Quoted 4 lines
Right...so would it perhaps be more interesting to try a modified test where each child's bandwidth is equal and small enough that there is no oversubscription?
So right! I think that should be the way to go, and I'll try to do something like this as soon as I can... I promise... :-D
Regards,
Dario
Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere) ---------------------------------------------------------------------- Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa (Italy) http://blog.linux.it/raistlin / [email protected] / [email protected]