20 Apr, 2008
6 commits
-
Now that the group hierarchy can have an arbitrary depth the O(n^2) nature
of RT task dequeues will really hurt. Optimize this by providing space to
store the tree path, so we can walk it the other way.Signed-off-by: Peter Zijlstra
Signed-off-by: Ingo Molnar -
Implement SMP nice support for the full group hierarchy.
On each load-balance action, compile a sched_domain wide view of the full
task_group tree. We compute the domain wide view when walking down the
hierarchy, and readjust the weights when walking back up.After collecting and readjusting the domain wide view, we try to balance the
tasks within the task_groups. The current approach is a naively balance each
task group until we've moved the targeted amount of load.Inspired by Srivatsa Vaddsgiri's previous code and Abhishek Chandra's H-SMP
paper.XXX: there will be some numerical issues due to the limited nature of
SCHED_LOAD_SCALE wrt to representing a task_groups influence on the
total weight. When the tree is deep enough, or the task weight small
enough, we'll run out of bits.Signed-off-by: Peter Zijlstra
CC: Abhishek Chandra
CC: Srivatsa Vaddagiri
Signed-off-by: Ingo Molnar -
This patch allows tasks and groups to exist in the same cfs_rq. With this
change the CFS group scheduling follows a 1/(M+N) model from a 1/(1+N)
fairness model where M tasks and N groups exist at the cfs_rq level.[a.p.zijlstra@chello.nl: rt bits and assorted fixes]
Signed-off-by: Dhaval Giani
Signed-off-by: Srivatsa Vaddagiri
Signed-off-by: Peter Zijlstra
Signed-off-by: Ingo Molnar -
Add a new function that accepts a pointer to the "newly allowed cpus"
cpumask argument.int set_cpus_allowed_ptr(struct task_struct *p, const cpumask_t *new_mask)
The current set_cpus_allowed() function is modified to use the above
but this does not result in an ABI change. And with some compiler
optimization help, it may not introduce any additional overhead.Additionally, to enforce the read only nature of the new_mask arg, the
"const" property is migrated to sub-functions called by set_cpus_allowed.
This silences compiler warnings.Signed-off-by: Mike Travis
Signed-off-by: Ingo Molnar -
Currently the rt group scheduling does a per cpu runtime limit, however
the rt load balancer makes no guarantees about an equal spread of real-
time tasks, just that at any one time, the highest priority tasks run.Solve this by making the runtime limit a global property by borrowing
excessive runtime from the other cpus once the local limit runs out.Signed-off-by: Peter Zijlstra
Signed-off-by: Ingo Molnar -
Various SMP balancing algorithms require that the bandwidth period
run in sync.Possible improvements are moving the rt_bandwidth thing into root_domain
and keeping a span per rt_bandwidth which marks throttled cpus.Signed-off-by: Peter Zijlstra
Signed-off-by: Ingo Molnar
07 Mar, 2008
1 commit
-
Sripathi Kodi reported a crash in the -rt kernel:
https://bugzilla.redhat.com/show_bug.cgi?id=435674
this is due to a place that can reschedule a task without holding
the tasks runqueue lock. This was caused by the RT balancing code
that pulls RT tasks to the current run queue and will reschedule the
current task.There's a slight chance that the pulling of the RT tasks will release
the current runqueue's lock and retake it (in the double_lock_balance).
During this time that the runqueue is released, the current task can
migrate to another runqueue.In the prio_changed_rt code, after the pull, if the current task is of
lesser priority than one of the RT tasks pulled, resched_task is called
on the current task. If the current task had migrated in that small
window, resched_task will be called without holding the runqueue lock
for the runqueue that the task is on.This race condition also exists in the mainline kernel and this patch
adds a check to make sure the task hasn't migrated before calling
resched_task.Signed-off-by: Steven Rostedt
Tested-by: Sripathi Kodi
Acked-by: Peter Zijlstra
Signed-off-by: Ingo Molnar
05 Mar, 2008
1 commit
-
The following commits cause a number of regressions:
commit 58e2d4ca581167c2a079f4ee02be2f0bc52e8729
Author: Srivatsa Vaddagiri
Date: Fri Jan 25 21:08:00 2008 +0100
sched: group scheduling, change how cpu load is calculatedcommit 6b2d7700266b9402e12824e11e0099ae6a4a6a79
Author: Srivatsa Vaddagiri
Date: Fri Jan 25 21:08:00 2008 +0100
sched: group scheduler, fix fairness of cpu bandwidth allocation for task groupsNamely:
- very frequent wakeups on SMP, reported by PowerTop users.
- cacheline trashing on (large) SMP
- some latencies larger than 500msWhile there is a mergeable patch to fix the latter, the former issues
are not fixable in a manner suitable for .25 (we're at -rc3 now).Hence we revert them and try again in v2.6.26.
Signed-off-by: Peter Zijlstra
CC: Srivatsa Vaddagiri
Tested-by: Alexey Zaytsev
Signed-off-by: Ingo Molnar
13 Feb, 2008
3 commits
-
Make the rt group scheduler compile time configurable.
Keep it experimental for now.Signed-off-by: Peter Zijlstra
Signed-off-by: Ingo Molnar -
Change the rt_ratio interface to rt_runtime_us, to match rt_period_us.
This avoids picking a granularity for the ratio.Extend the /sys/kernel/uids// interface to allow setting
the group's rt_runtime.Signed-off-by: Peter Zijlstra
Signed-off-by: Ingo Molnar -
Steven mentioned the fun case where a lock holding task will be throttled.
Simple fix: allow groups that have boosted tasks to run anyway.
If a runnable task in a throttled group gets boosted the dequeue/enqueue
done by rt_mutex_setprio() is enough to unthrottle the group.This is ofcourse not quite correct. Two possible ways forward are:
- second prio array for boosted tasks
- boost to a prio ceiling (this would also work for deadline scheduling)Signed-off-by: Peter Zijlstra
Signed-off-by: Ingo Molnar
26 Jan, 2008
29 commits
-
looking at it one more time:
(1) it looks to me that there is no need to call
sched_rt_ratio_exceeded() from pick_next_rt_entity()- [ for CONFIG_FAIR_GROUP_SCHED ] queues with rt_rq->rt_throttled are
not within this 'tree-like hierarchy' (or whatever we should call it
:-)- there is also no need to re-check 'rt_rq->rt_time > ratio' at this
point as 'rt_rq->rt_time' couldn't have been increased since the last
call to update_curr_rt() (which obviously calls
sched_rt_ratio_esceeded())
well, it might be that 'ratio' for this rt_rq has been re-configured
(and the period over which this rt_rq was active has not yet been
finished)... but I don't think we should really take this into
account.(2) now pick_next_rt_entity() must never return NULL, so let's change
pick_next_task_rt() accordingly.Signed-off-by: Dmitry Adamushko
Signed-off-by: Ingo Molnar -
Remove the curious logic to set it_sched_expires in the future. It useless
because rt.timeout wouldn't be incremented anyway.Explicity check for RLIM_INFINITY as a test programm that had a 1s soft limit
and a inf hard limit would SIGKILL at 1s. This is because RLIM_INFINITY+d-1
is d-2.Signed-off-by: Peter Zijlsta
CC: Michal Schmidt
Signed-off-by: Ingo Molnar -
Only reschedule if the new group has a higher prio task.
Signed-off-by: Peter Zijlstra
Signed-off-by: Ingo Molnar -
We need to teach no_hz about the rt throttling because its tick driven.
Signed-off-by: Peter Zijlstra
Signed-off-by: Ingo Molnar -
"goto out" is an odd way to spell "skip".
Signed-off-by: Mike Galbraith
Signed-off-by: Ingo Molnar -
Extend group scheduling to also cover the realtime classes. It uses the time
limiting introduced by the previous patch to allow multiple realtime groups.The hard time limit is required to keep behaviour deterministic.
The algorithms used make the realtime scheduler O(tg), linear scaling wrt the
number of task groups. This is the worst case behaviour I can't seem to get out
of, the avg. case of the algorithms can be improved, I focused on correctness
and worst case.[ akpm@linux-foundation.org: move side-effects out of BUG_ON(). ]
Signed-off-by: Peter Zijlstra
Signed-off-by: Ingo Molnar -
Very simple time limit on the realtime scheduling classes.
Allow the rq's realtime class to consume sched_rt_ratio of every
sched_rt_period slice. If the class exceeds this quota the fair class
will preempt the realtime class.Signed-off-by: Peter Zijlstra
Signed-off-by: Ingo Molnar -
Use HR-timers (when available) to deliver an accurate preemption tick.
The regular scheduler tick that runs at 1/HZ can be too coarse when nice
level are used. The fairness system will still keep the cpu utilisation 'fair'
by then delaying the task that got an excessive amount of CPU time but try to
minimize this by delivering preemption points spot-on.The average frequency of this extra interrupt is sched_latency / nr_latency.
Which need not be higher than 1/HZ, its just that the distribution within the
sched_latency period is important.Signed-off-by: Peter Zijlstra
Signed-off-by: Ingo Molnar -
Introduce a new rlimit that allows the user to set a runtime timeout on
real-time tasks their slice. Once this limit is exceeded the task will receive
SIGXCPU.So it measures runtime since the last sleep.
Input and ideas by Thomas Gleixner and Lennart Poettering.
Signed-off-by: Peter Zijlstra
CC: Lennart Poettering
CC: Michael Kerrisk
CC: Ulrich Drepper
Signed-off-by: Ingo Molnar -
Move the task_struct members specific to rt scheduling together.
A future optimization could be to put sched_entity and sched_rt_entity
into a union.Signed-off-by: Peter Zijlstra
CC: Srivatsa Vaddagiri
Signed-off-by: Ingo Molnar -
We had support for overlapping cpuset based rto logic in early
prototypes that is no longer used, so remove it.Signed-off-by: Gregory Haskins
Signed-off-by: Steven Rostedt
Signed-off-by: Ingo Molnar -
The overload set/clears were originally idempotent when this logic was first
implemented. But that is no longer true due to the addition of the atomic
counter and this logic was never updated to work properly with that change.
So only adjust the overload state if it is actually changing to avoid
getting out of sync.Signed-off-by: Gregory Haskins
Signed-off-by: Steven Rostedt
Signed-off-by: Ingo Molnar -
Dmitry Adamushko found that the current implementation of the RT
balancing code left out changes to the sched_setscheduler and
rt_mutex_setprio.This patch addresses this issue by adding methods to the schedule classes
to handle being switched out of (switched_from) and being switched into
(switched_to) a sched_class. Also a method for changing of priorities
is also added (prio_changed).This patch also removes some duplicate logic between rt_mutex_setprio and
sched_setscheduler.Signed-off-by: Steven Rostedt
Signed-off-by: Ingo Molnar -
To make the main sched.c code more agnostic to the schedule classes.
Instead of having specific hooks in the schedule code for the RT class
balancing. They are replaced with a pre_schedule, post_schedule
and task_wake_up methods. These methods may be used by any of the classes
but currently, only the sched_rt class implements them.Signed-off-by: Steven Rostedt
Signed-off-by: Ingo Molnar -
fix build bug in sched_rt.c:join/leave_domain and make them only
be included on SMP builds.Signed-off-by: Ingo Molnar
-
We move the rt-overload data as the first global to per-domain
reclassification. This limits the scope of overload related cache-line
bouncing to stay with a specified partition instead of affecting all
cpus in the system.Finally, we limit the scope of find_lowest_cpu searches to the domain
instead of the entire system. Note that we would always respect domain
boundaries even without this patch, but we first would scan potentially
all cpus before whittling the list down. Now we can avoid looking at
RQs that are out of scope, again reducing cache-line hits.Note: In some cases, task->cpus_allowed will effectively reduce our search
to within our domain. However, I believe there are cases where the
cpus_allowed mask may be all ones and therefore we err on the side of
caution. If it can be optimized later, so be it.Signed-off-by: Gregory Haskins
CC: Christoph Lameter
Signed-off-by: Ingo Molnar -
clean up schedule_balance_rt().
Signed-off-by: Ingo Molnar
-
clean up pull_rt_task().
Signed-off-by: Ingo Molnar
-
remove leftover debugging.
Signed-off-by: Ingo Molnar
-
remove rt_overload() - it's an unnecessary indirection.
Signed-off-by: Ingo Molnar
-
clean up whitespace damage and missing comments in kernel/sched_rt.c.
Signed-off-by: Ingo Molnar
-
clean up overlong line in kernel/sched_debug.c.
Signed-off-by: Ingo Molnar
-
clean up find_lock_lowest_rq().
Signed-off-by: Ingo Molnar
-
clean up pick_next_highest_task_rt().
Signed-off-by: Ingo Molnar
-
This patch removes several cpumask operations by keeping track
of the first of the CPUS that is of the lowest priority. When
the search for the lowest priority runqueue is completed, all
the bits up to the first CPU with the lowest priority runqueue
is cleared.Signed-off-by: Steven Rostedt
Signed-off-by: Ingo Molnar -
We can cheaply track the number of bits set in the cpumask for the lowest
priority CPUs. Therefore, compute the mask's weight and use it to skip
the optimal domain search logic when there is only one CPU available.Signed-off-by: Gregory Haskins
Signed-off-by: Ingo Molnar -
We don't need to bother searching if the task cannot be migrated
Signed-off-by: Gregory Haskins
Signed-off-by: Steven Rostedt
Signed-off-by: Ingo Molnar -
This patch changes the searching for a run queue by a waking RT task
to try to pick another runqueue if the currently running task
is an RT task.The reason is that RT tasks behave different than normal
tasks. Preempting a normal task to run a RT task to keep
its cache hot is fine, because the preempted non-RT task
may wait on that same runqueue to run again unless the
migration thread comes along and pulls it off.RT tasks behave differently. If one is preempted, it makes
an active effort to continue to run. So by having a high
priority task preempt a lower priority RT task, that lower
RT task will then quickly try to run on another runqueue.
This will cause that lower RT task to replace its nice
hot cache (and TLB) with a completely cold one. This is
for the hope that the new high priority RT task will keep
its cache hot.Remeber that this high priority RT task was just woken up.
So it may likely have been sleeping for several milliseconds,
and will end up with a cold cache anyway. RT tasks run till
they voluntarily stop, or are preempted by a higher priority
task. This means that it is unlikely that the woken RT task
will have a hot cache to wake up to. So pushing off a lower
RT task is just killing its cache for no good reason.Signed-off-by: Steven Rostedt
Signed-off-by: Ingo Molnar -
We have logic to detect whether the system has migratable tasks, but we are
not using it when deciding whether to push tasks away. So we add support
for considering this new information.Signed-off-by: Gregory Haskins
Signed-off-by: Steven Rostedt
Signed-off-by: Ingo Molnar
