rSDl cpu scheduler version 0.34-test patch
Subsystems (2)
This is just for testing at the moment! The reason is the size of this patch.
In the interest of evolution, I've taken the RSDL cpu scheduler and increased the resolution of the task timekeeping to nanosecond resolution. This removes the need for the runqueue rotation component entirely out of RSDL. The design basically is mostly unchanged, minus over 150 lines of code for the rotation, yet should be slightly better performing. It should be indistinguishable in usage from v0.33.
Other changes from v0.33:
-rr interval was not being properly scaled with HZ -fix possible race in checking task_queued in task_running_tick -scale down rr interval for niced tasks if HZ can tolerate it -cull list_splice_tail
What does this mean for the next version of RSDL?
Assuming all works as expected on these test patches, it will be cleanest to submit a new series of patches for -mm with the renamed Staircase-Deadline scheduler and new documentation (when it's done).
So for testing here are full rollups for 2.6.20.4 and 2.6.21-rc4:
http://ck.kolivas.org/patches/staircase-deadline/2.6.20.4-sd-0.34-test.patch
http://ck.kolivas.org/patches/staircase-deadline/2.6.21-rc4-sd-0.34-test.patch
The patches available also include a rollup of sched: accurate user accounting as this code touches the same area and it is most convenient to include them together.
(incrementals in each subdir of staircase-deadline/ for those interested).
Thanks Mike for continuing to attempt to use the cluebat on me on this one.
Quoted 1 line
From the start I wasn't sure if this was necessary or not but ends up being
less code than RSDL.
While I'm still far from being well, luckily I am in much better shape to be able to spend the time at the pc to have done this. Thanks to all those who expressed their concern.
Signature · 1 line
-ck
Quoted 1 line · Con Kolivas
This is just for testing at the moment! The reason is the size of this patch.
(no testing done yet, but I have a couple comments)
Quoted 2 lines
In the interest of evolution, I've taken the RSDL cpu scheduler and increased the resolution of the task timekeeping to nanosecond resolution.
+ /* All the userspace visible cpu accounting is done here */
+ time_diff = now - p->last_ran;
...
+ /* cpu scheduler quota accounting is performed here */
+ if (p->policy != SCHED_FIFO)
+ p->time_slice -= time_diff;
If we still have any jiffies resolution clocks out there, this could be a bit problematic.
+static inline void enqueue_pulled_task(struct rq *src_rq, struct rq *rq,
+ struct task_struct *p)
+{
+ int queue_prio;
+
+ p->array = rq->active; <== set
+ if (!rt_task(p)) {
+ if (p->rotation == src_rq->prio_rotation) {
+ if (p->array == src_rq->expired) { <== evaluate
+ queue_expired(p, rq);
+ goto out_queue;
+ }
+ if (p->time_slice < 0)
+ task_new_array(p, rq);
+ } else
+ task_new_array(p, rq);
+ }
+ queue_prio = next_entitled_slot(p, rq);
(bug aside, this special function really shouldn't exist imho, because there's nothing special going on. we didn't need it before to do the same thing, so we shouldn't need it now.)
+static void recalc_task_prio(struct task_struct *p, struct rq *rq) +{
+ struct prio_array *array = rq->active;
+ int queue_prio;
+
+ if (p->rotation == rq->prio_rotation) {
+ if (p->array == array) {
+ if (p->time_slice > 0)
+ return;
+ p->time_slice = p->quota;
+ } else if (p->array == rq->expired) {
+ queue_expired(p, rq);
+ return;
+ } else
+ task_new_array(p, rq);
+ } else
Dequeueing a task still leaves a stale p->array laying around to be possibly evaluated later. try_to_wake_up() doesn't currently evaluate and set p->rotation (but should per design doc), so when you get here, a cross-cpu waking task won't continue it's rotation. If it did evaluate and set, recalc_task_prio() would evaluate the guaranteed to fail these tests array pointer, so the task will still not continue it's rotation. Stale pointers are evil.
-Mike
Quoted 3 lines · Con Kolivas
The patches available also include a rollup of sched: accurate user accounting as this code touches the same area and it is most convenient to include them together.
as i mentioned it before, please keep this one separate, as we want to apply it first.
Ingo
Quoted 6 lines · Ingo Molnar
Quoted 3 lines
The patches available also include a rollup of sched: accurate user accounting as this code touches the same area and it is most convenient to include them together.
as i mentioned it before, please keep this one separate, as we want to apply it first.
i.e. have the patch below the first patch of the series. Thanks,
Ingo
----------------------->
Subject: [patch] sched: accurate user accounting
From: Con Kolivas <[email protected]>
Currently we only do cpu accounting to userspace based on what is actually happening precisely on each tick. The accuracy of that accounting gets progressively worse the lower HZ is. As we already keep accounting of nanosecond resolution we can accurately track user cpu, nice cpu and idle cpu if we move the accounting to update_cpu_clock with a nanosecond cpu_usage_stat entry. This increases overhead slightly but avoids the problem of tick aliasing errors making accounting unreliable.
Remove the now defunct Documentation/cpu-load.txt file.
--- Documentation/cpu-load.txt | 113 -------------------------------------------- include/linux/kernel_stat.h | 3 + include/linux/sched.h | 2 kernel/sched.c | 58 +++++++++++++++++++++- kernel/timer.c | 5 - 5 files changed, 60 insertions(+), 121 deletions(-)
Documentation/cpu-load.txt deleted +0 -113
@@ -1,113 +0,0 @@ -CPU load --------- - -Linux exports various bits of information via `/proc/stat' and -`/proc/uptime' that userland tools, such as top(1), use to calculate -the average time system spent in a particular state, for example: - - $ iostat - Linux 2.6.18.3-exp (linmac) 02/20/2007 - - avg-cpu: %user %nice %system %iowait %steal %idle - 10.01 0.00 2.92 5.44 0.00 81.63 - - ... - -Here the system thinks that over the default sampling period the -system spent 10.01% of the time doing work in user space, 2.92% in the -kernel, and was overall 81.63% of the time idle. - -In most cases the `/proc/stat' information reflects the reality quite -closely, however due to the nature of how/when the kernel collects -this data sometimes it can not be trusted at all. - -So how is this information collected? Whenever timer interrupt is -signalled the kernel looks what kind of task was running at this -moment and increments the counter that corresponds to this tasks -kind/state. The problem with this is that the system could have -switched between various states multiple times between two timer -interrupts yet the counter is incremented only for the last state. - - -Example -------- - -If we imagine the system with one task that periodically burns cycles -in the following manner: - - time line between two timer interrupts -|--------------------------------------| - ^ ^ - |_ something begins working | - |_ something goes to sleep - (only to be awaken quite soon) - -In the above situation the system will be 0% loaded according to the -`/proc/stat' (since the timer interrupt will always happen when the -system is executing the idle handler), but in reality the load is -closer to 99%. - -One can imagine many more situations where this behavior of the kernel -will lead to quite erratic information inside `/proc/stat'. - - -/* gcc -o hog smallhog.c */ -#include <time.h> -#include <limits.h> -#include <signal.h> -#include <sys/time.h> -#define HIST 10 - -static volatile sig_atomic_t stop; - -static void sighandler (int signr) -{ - (void) signr; - stop = 1; -} -static unsigned long hog (unsigned long niters) -{ - stop = 0; - while (!stop && --niters); - return niters; -} -int main (void) -{ - int i; - struct itimerval it = { .it_interval = { .tv_sec = 0, .tv_usec = 1 }, - .it_value = { .tv_sec = 0, .tv_usec = 1 } }; - sigset_t set; - unsigned long v[HIST]; - double tmp = 0.0; - unsigned long n; - signal (SIGALRM, &sighandler); - setitimer (ITIMER_REAL, &it, NULL); - - hog (ULONG_MAX); - for (i = 0; i < HIST; ++i) v[i] = ULONG_MAX - hog (ULONG_MAX); - for (i = 0; i < HIST; ++i) tmp += v[i]; - tmp /= HIST; - n = tmp - (tmp / 3.0); - - sigemptyset (&set); - sigaddset (&set, SIGALRM); - - for (;;) { - hog (n); - sigwait (&set, &i); - } - return 0; -} - - -References ----------- - -http://lkml.org/lkml/2007/2/12/6 -Documentation/filesystems/proc.txt (1.8) - - -Thanks ------- - -Con Kolivas, Pavel Machek
include/linux/kernel_stat.h +3 -0
@@ -16,11 +16,14 @@struct cpu_usage_stat {cputime64_t user; +cputime64_t user_ns;cputime64_t nice; +cputime64_t nice_ns;cputime64_t system;cputime64_t softirq;cputime64_t irq;cputime64_t idle; +cputime64_t idle_ns;cputime64_t iowait;cputime64_t steal; };
include/linux/sched.h +1 -1
@@ -882,7 +882,7 @@ struct task_struct {int __user *clear_child_tid;/* CLONE_CHILD_CLEARTID */ unsigned long rt_priority; -cputime_t utime, stime; +cputime_t utime, utime_ns, stime;unsigned long nvcsw, nivcsw;/* context switch counts */ struct timespec start_time;/* mm fault and swap info: this can arguably be seen as either mm-specific or thread-specific */
kernel/sched.c +54 -4
76 lines not on this page · raw message
kernel/timer.c +2 -3
@@ -1196,10 +1196,9 @@ void update_process_times(int user_tick)int cpu =smp_processor_id ();/* Note: this timer irq context must be accounted for as well. */ -if (user_tick) -account_user_time (p,jiffies_to_cputime (1 )); -else +if (!user_tick)account_system_time (p,HARDIRQ_OFFSET ,jiffies_to_cputime (1 )); +/* User time is accounted for in update_cpu_clock in sched.c */ run_local_timers ();if (rcu_pending (cpu))rcu_check_callbacks (cpu, user_tick);
Quoted 17 lines · Mike Galbraith
Quoted 2 lines · Con Kolivas
This is just for testing at the moment! The reason is the size of this patch.
(no testing done yet, but I have a couple comments)
Quoted 3 lines
In the interest of evolution, I've taken the RSDL cpu scheduler and increased the resolution of the task timekeeping to nanosecond resolution.
(quoted diff) +5
-0+ /* All the userspace visible cpu accounting is done here */ + time_diff = now - p->last_ran; + /* cpu scheduler quota accounting is performed here */ + if (p->policy != SCHED_FIFO) + p->time_slice -= time_diff;
Quoted 2 lines
If we still have any jiffies resolution clocks out there, this could be a bit problematic.
Works fine with jiffy only resolution. sched_clock just returns the change when it happens. This leaves us with the accuracy of the previous code on hardware that doesn't give higher resolution time from sched_clock.
Review
Quoted 9 lines
(quoted diff) +9
-0+static inline void enqueue_pulled_task(struct rq *src_rq, struct rq *rq, + struct task_struct *p) +{ + int queue_prio; + + p->array = rq->active; <== set + if (!rt_task(p)) { + if (p->rotation == src_rq->prio_rotation) { + if (p->array == src_rq->expired) { <== evaluate
I don't see a problem.
Quoted 10 lines
(quoted diff) +9
-0+ queue_expired(p, rq); + goto out_queue; + } + if (p->time_slice < 0) + task_new_array(p, rq); + } else + task_new_array(p, rq); + } + queue_prio = next_entitled_slot(p, rq);
Quoted 3 lines
(bug aside, this special function really shouldn't exist imho, because there's nothing special going on. we didn't need it before to do the same thing, so we shouldn't need it now.)
As the comment says, the likelihood that both runqueues happen to be at the same priority_level is very low so the exact position cannot be transposed in my opinion. I'll see if I can simplify it though.
Quoted 17 lines
(quoted diff) +16
-0+static void recalc_task_prio(struct task_struct *p, struct rq *rq) +{ + struct prio_array *array = rq->active; + int queue_prio; + + if (p->rotation == rq->prio_rotation) { + if (p->array == array) { + if (p->time_slice > 0) + return; + p->time_slice = p->quota; + } else if (p->array == rq->expired) { + queue_expired(p, rq); + return; + } else + task_new_array(p, rq); + } else
Quoted 2 lines
Dequeueing a task still leaves a stale
p->arraylaying around to be possibly evaluated later.
I don't see quite why that's a problem. If there's memory of the last dequeue and it enqueues at a different rotation it gets ignored. If it enqueues during the same rotation then that memory proves useful for ensuring it doesn't get a new full quota. Either way the array is always updated on enqueue so it wont be trying to add it to the wrong runlist.
Quoted 2 lines
try_to_wake_up()doesn't currently evaluate
and setp->rotation(but should per design doc),
try_to_wake_up->activate_task->enqueue_task->recalc_task_prio which updates p->rotation
Quoted 6 lines
so when you get here, a
cross-cpu waking task won't continue it's rotation. If it did evaluate and set,recalc_task_prio()would evaluate the guaranteed to fail these tests array pointer, so the task will still not continue it's rotation.Stale pointers are evil.
I prefer to use the array value as a memory in case it wakes up on the same rotation and runqueue.
Quoted 2 lines
-Mike
Thanks.
Signature · 1 line
-ck
Quoted 18 lines · Con Kolivas
Quoted 17 lines · Mike Galbraith
Quoted 2 lines · Con Kolivas
This is just for testing at the moment! The reason is the size of this patch.
(no testing done yet, but I have a couple comments)
Quoted 3 lines
In the interest of evolution, I've taken the RSDL cpu scheduler and increased the resolution of the task timekeeping to nanosecond resolution.
(quoted diff) +5
-0+ /* All the userspace visible cpu accounting is done here */ + time_diff = now - p->last_ran; + /* cpu scheduler quota accounting is performed here */ + if (p->policy != SCHED_FIFO) + p->time_slice -= time_diff;
Quoted 6 lines
Quoted 2 lines
If we still have any jiffies resolution clocks out there, this could be a bit problematic.
Works fine with jiffy only resolution.
sched_clockjust returns the change when it happens. This leaves us with the accuracy of the previous code on hardware that doesn't give higher resolution time fromsched_clock.
I was thinking about how often you could zip through there with zero change to time_slice. Yeah, I suppose the net effect may be about the same as dodged ticks.
Quoted 11 lines
Review
Quoted 9 lines
(quoted diff) +9
-0+static inline void enqueue_pulled_task(struct rq *src_rq, struct rq *rq, + struct task_struct *p) +{ + int queue_prio; + + p->array = rq->active; <== set + if (!rt_task(p)) { + if (p->rotation == src_rq->prio_rotation) { + if (p->array == src_rq->expired) { <== evaluateI don't see a problem.
p->array can be set to rq->active and evaluate to src_rq->expired?
Quoted 26 lines
Quoted 17 lines
(quoted diff) +16
-0+static void recalc_task_prio(struct task_struct *p, struct rq *rq) +{ + struct prio_array *array = rq->active; + int queue_prio; + + if (p->rotation == rq->prio_rotation) { + if (p->array == array) { + if (p->time_slice > 0) + return; + p->time_slice = p->quota; + } else if (p->array == rq->expired) { + queue_expired(p, rq); + return; + } else + task_new_array(p, rq); + } elseQuoted 2 lines
Dequeueing a task still leaves a stale
p->arraylaying around to be possibly evaluated later.I don't see quite why that's a problem. If there's memory of the last dequeue and it enqueues at a different rotation it gets ignored. If it enqueues during the same rotation then that memory proves useful for ensuring it doesn't get a new full quota. Either way the array is always updated on enqueue so it wont be trying to add it to the wrong runlist.
Quoted 5 lines
Quoted 2 lines
try_to_wake_up()doesn't currently evaluate
and setp->rotation(but should per design doc),
try_to_wake_up->activate_task->enqueue_task->recalc_task_priowhich updatesp->rotation
As I read it, it's task_new_array() which sets p->rotation, _after_ recalc_task_prio() has evaluated it to see if the task should continue it's rotation or not. The mechanism which ensures that sleeping tasks can only get their fair share, as I understand it, is that they continue their rotation on wakeup with their bitmap intact. That appears to indeed be the way same cpu wakeups are handled. In the cross-cpu wakeup case, it can't do anything but call task_new_array(), because the chances that p->rotation being the same as the rotation number of the new queue is practically nil, wherein the tasks bitmap is zeroed, ie it starts over every time it changes cpu. No?
-Mike
P.S. (I've not studied the hotplug code) When a cpu is hot-unplugged, are it's runqueues and whatnot deallocated? (i should just go look, but by the time i get around to it, some nice person may have already put an answer in my mailbox;)
-Mike
P.S.#2: not only bitmap are zeroed, task is issued a fresh time_slice.
-Mike