sched: Add SCHED_BGND (background) scheduling policy
Subsystems (3)
PATCH 1/1 sched: Add SCHED_BGND (background) scheduling policy
Problem:
There is a genuine need for the ability to put tasks in the background (a la the SCHED_IDLEPRIO policy in Con Kolivas's -sc kernels) as is evidenced by comments in LKML re a desire for SCHED_BATCH tasks to run completely in the background.
Solution:
Of course, one option would have been to just modify SCHED_BATCH so that tasks with that policy run completely in the background but there is a genuine need for a non background batch policy so the solution adopted is to implementa a new policy SCHED_BGND.
SCHED_BATCH means that it's a normal process and should get a fair share of the CPU in accordance with its "nice" setting but it is NOT an interactive task and should NOT receive any of the special treatment that a task that is adjudged to be interactive receives. In particular, it should always be moved to the expired array at the end of its time slice as to do otherwise might result in CPU starvation for other tasks.
SCHED_BGND means it's totally unimportant and should only be given the CPU if no one else wants it OR if not giving it the CPU could lead to priority inversion or starvation of other tasks due to this tasks holding system resources.
--- include/linux/init_task.h | 6 - include/linux/sched.h | 11 ++ kernel/fork.c | 1 kernel/mutex.c | 28 ++++++- kernel/sched.c | 183 ++++++++++++++++++++++++++++++++++++++-------- 5 files changed, 192 insertions(+), 37 deletions(-)
include/linux/init_task.h +3 -3
@@ -99,9 +99,9 @@ extern struct group_info init_groups; .usage = ATOMIC_INIT(2), \ .flags = 0, \ .lock_depth = -1, \ - .prio = MAX_PRIO-20, \ - .static_prio = MAX_PRIO-20, \ - .normal_prio = MAX_PRIO-20, \ + .prio = MAX_RT_PRIO+20, \ + .static_prio = MAX_RT_PRIO+20, \ + .normal_prio = MAX_RT_PRIO+20, \ .policy = SCHED_NORMAL, \ .cpus_allowed = CPU_MASK_ALL, \ .mm = NULL, \
include/linux/sched.h +9 -2
@@ -34,6 +34,8 @@#define SCHED_FIFO 1#define SCHED_RR 2#define SCHED_BATCH 3 +/* Scheduler class for background tasks */ +#define SCHED_BGND 4#ifdef __KERNEL__
@@ -503,13 +505,16 @@ struct signal_struct {#define MAX_USER_RT_PRIO 100#define MAX_RT_PRIO MAX_USER_RT_PRIO -#define MAX_PRIO (MAX_RT_PRIO + 40) +#define BGND_PRIO (MAX_RT_PRIO + 40) +/* add another slot for SCHED_BGND tasks */ +#define MAX_PRIO (BGND_PRIO + 1)#define rt_prio (prio) unlikely((prio) < MAX_RT_PRIO)#define rt_task (p) rt_prio((p)->prio)#define batch_task (p) (unlikely((p)->policy == SCHED_BATCH))#define has_rt_policy (p) \ - unlikely((p)->policy != SCHED_NORMAL && (p)->policy != SCHED_BATCH) + unlikely((p)->policy != SCHED_NORMAL && (p)->policy < SCHED_BATCH) +#define bgnd_task (p) (unlikely((p)->policy == SCHED_BGND))/* * Some day this will be a full-fledged user tracking system..
@@ -810,6 +815,7 @@ struct task_struct {unsigned long sleep_avg;unsigned long long timestamp, last_ran;unsigned long long sched_time;/* sched_clock time spent running */ +unsigned int mutexes_held;/* for knowing when it's safe to repress SCHED_BGND tasks */ enum sleep_type sleep_type;unsigned long policy;
@@ -1090,6 +1096,7 @@ static inline void put_task_struct(struc#define PF_SWAPWRITE 0x00800000/* Allowed to write to swap */ #define PF_SPREAD_PAGE 0x01000000/* Spread page cache over cpuset */ #define PF_SPREAD_SLAB 0x02000000/* Spread some slab caches over cpuset */ +#define PF_UIWAKE 0x08000000/* Just woken from uninterrptible sleep */ #define PF_MEMPOLICY 0x10000000/* Non-default NUMA mempolicy */ #define PF_MUTEX_TESTER 0x20000000/* Thread belongs to the rt mutex tester */
kernel/sched.c +153 -30
306 lines not on this page · raw message
kernel/mutex.c +26 -2
@@ -51,6 +51,16 @@ __mutex_init(struct mutex *lock, const cEXPORT_SYMBOL (__mutex_init); +static inline void inc_mutex_count (void ) +{ + current->mutexes_held++; +} + +static inline void dec_mutex_count (void ) +{ + current->mutexes_held--; +} +/* * We split the mutex lock/unlock logic into separate fastpath and * slowpath functions, to reduce the register pressure on the fastpath.
@@ -89,6 +99,7 @@ void inline fastcall __sched mutex_lock(* 'unlocked' into 'locked' state. */ __mutex_fastpath_lock (&lock->count, __mutex_lock_slowpath); +inc_mutex_count (); }EXPORT_SYMBOL (mutex_lock);
@@ -114,6 +125,7 @@ void fastcall __sched mutex_unlock(struc* into 'unlocked' state: */ __mutex_fastpath_unlock (&lock->count, __mutex_unlock_slowpath); +dec_mutex_count (); }EXPORT_SYMBOL (mutex_unlock);
@@ -274,9 +286,16 @@ __mutex_lock_interruptible_slowpath(atom*/ int fastcall __sched mutex_lock_interruptible(struct mutex *lock) { +int ret; +might_sleep (); -return __mutex_fastpath_lock_retval + ret =__mutex_fastpath_lock_retval (&lock->count, __mutex_lock_interruptible_slowpath); + +if (likely (!ret)) +inc_mutex_count (); + +return ret; }EXPORT_SYMBOL (mutex_lock_interruptible);
@@ -331,8 +350,13 @@ static inline int __mutex_trylock_slowpa*/ int fastcall __sched mutex_trylock(struct mutex *lock) { -return __mutex_fastpath_trylock (&lock->count, +int ret =__mutex_fastpath_trylock (&lock->count, __mutex_trylock_slowpath); + +if (likely (ret)) +inc_mutex_count (); + +return ret; }EXPORT_SYMBOL (mutex_trylock);
kernel/fork.c +1 -0
@@ -1029,6 +1029,7 @@ static struct task_struct *copy_process( p->wchar =0 ;/* I/O counter: bytes written */ p->syscr =0 ;/* I/O counter: read syscalls */ p->syscw =0 ;/* I/O counter: write syscalls */ + p->mutexes_held =0 ;acct_clear_integrals (p); p->it_virt_expires = cputime_zero;
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Quoted 21 lines · Peter Williams
Problem:
There is a genuine need for the ability to put tasks in the background (a la the
SCHED_IDLEPRIOpolicy in Con Kolivas's -sc kernels) as is evidenced by comments in LKML re a desire forSCHED_BATCHtasks to run completely in the background.Solution:
Of course, one option would have been to just modify
SCHED_BATCHso that tasks with that policy run completely in the background but there is a genuine need for a non background batch policy so the solution adopted is to implementa a new policySCHED_BGND.
SCHED_BATCHmeans that it's a normal process and should get a fair share of the CPU in accordance with its "nice" setting but it is NOT an interactive task and should NOT receive any of the special treatment that a task that is adjudged to be interactive receives. In particular, it should always be moved to the expired array at the end of its time slice as to do otherwise might result in CPU starvation for other tasks.
Quoted 4 lines
SCHED_BGNDmeans it's totally unimportant and should only be given the CPU if no one else wants it OR if not giving it the CPU could lead to priority inversion or starvation of other tasks due to this tasks holding system resources.
Could we just call it SCHED_IDLEPRIO since it's the same thing and there are tools out there that already use this name?
Signature · 1 line
-ck
Quoted 22 lines · Con Kolivas
Quoted 21 lines · Peter Williams
Problem:
There is a genuine need for the ability to put tasks in the background (a la the
SCHED_IDLEPRIOpolicy in Con Kolivas's -sc kernels) as is evidenced by comments in LKML re a desire forSCHED_BATCHtasks to run completely in the background.Solution:
Of course, one option would have been to just modify
SCHED_BATCHso that tasks with that policy run completely in the background but there is a genuine need for a non background batch policy so the solution adopted is to implementa a new policySCHED_BGND.
SCHED_BATCHmeans that it's a normal process and should get a fair share of the CPU in accordance with its "nice" setting but it is NOT an interactive task and should NOT receive any of the special treatment that a task that is adjudged to be interactive receives. In particular, it should always be moved to the expired array at the end of its time slice as to do otherwise might result in CPU starvation for other tasks.
Quoted 7 lines
Quoted 4 lines
SCHED_BGNDmeans it's totally unimportant and should only be given the CPU if no one else wants it OR if not giving it the CPU could lead to priority inversion or starvation of other tasks due to this tasks holding system resources.Could we just call it
SCHED_IDLEPRIOsince it's the same thing and there are tools out there that already use this name?
I'm easy. Which user space visible headers contain the definition? That's the only place that it matters. When I was writing a program to use this feature, I couldn't find a header that defined any of the scheduler policies that was visible in user space (of course, that doesn't mean there isn't one - just that I couldn't find it).
Peter
PS Any programs that use SCHED_IDLEPRIO should work as long as its value is defined as 4.
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Quoted 9 lines · Peter Williams
Quoted 2 lines · Con Kolivas
Could we just call it
SCHED_IDLEPRIOsince it's the same thing and there are tools out there that already use this name?I'm easy. Which user space visible headers contain the definition? That's the only place that it matters. When I was writing a program to use this feature, I couldn't find a header that defined any of the scheduler policies that was visible in user space (of course, that doesn't mean there isn't one - just that I couldn't find it).
Obviously nothing since this is out of tree stuff; it's hard coded into the apps themselves currently.
Quoted 3 lines
Peter
PS Any programs that useSCHED_IDLEPRIOshould work as long as its value is defined as 4.
Aye I just figured not confusing terminology would be nice.
Signature · 1 line
-ck
Quoted 4 lines · Peter Williams
Quoted 3 lines · Con Kolivas
On Wednesday 05 July 2006 09:35, Peter Williams wrote:
Could we just call itSCHED_IDLEPRIOsince it's the same thing and there are tools out there that already use this name?
That makes quite some sense, seconded.
Plus, I like SCHED_IDLEPRIO more than SCHED_BGND, since it's more descriptive when stuff happens and when not (but of course the SCHED_BGND name is shorter).
Quoted 9 lines
I'm easy. Which user space visible headers contain the definition? That's the only place that it matters. When I was writing a program to use this feature, I couldn't find a header that defined any of the scheduler policies that was visible in user space (of course, that doesn't mean there isn't one - just that I couldn't find it).
Peter
PS Any programs that useSCHED_IDLEPRIOshould work as long as its value is defined as 4.
OK, nice, but:
2.6.17-ck1:
/*
* Scheduling policies
*/
#define SCHED_NORMAL 0 #define SCHED_FIFO 1 #define SCHED_RR 2 #define SCHED_BATCH 3 #define SCHED_ISO 4 #define SCHED_IDLEPRIO 5
#define SCHED_MIN 0
#define SCHED_MAX 5
Arggl.
So what does that tell us?
Does it tell us that the new policy should indeed be called SCHED_BGND so that user-space programs that make use of a policy (e.g. schedtool or any user-space app that wants to adjust its policy on its own) can figure out which policy number to use (the 4 vs. 5 difference) by #ifdef SCHED_IDLEPRIO elseif SCHED_BGND checks?
A less favourable solution would be to rename SCHED_BGND to SCHED_IDLEPRIO but keep the current last policy number (4) for it, since that would introduce a gross conflict (or do programs always go after the policy name defines instead of the raw policy numbers?).
Given this issue, maybe best would be to add SCHED_IDLEPRIO *and* SCHED_ISO to mainline at the same time, in order to keep the current policy numbering extension as done in -ck.
Or maybe we should even introduce a more flexible way of dealing scheduling policy registration and listing? A numbered solution that changes on a whim whenever someone adds his own policy may be.... numbered ;) (in terms of days, that is).
Semi-hard-coding scheduling numbers that get used by user-space sounds somewhat hackish to me, maybe we should instead (or additionally?) have a query API that returns a list of policy numbers for a given query input (near-hard realtime features, non-root access, interactivity, cache usage friendliness, batched operation, background processing).
What do other systems (*BSD, Solaris, ...) do in this case?
Andreas Mohr
Quoted 18 lines
Quoted 3 lines
Peter
PS Any programs that useSCHED_IDLEPRIOshould work as long as its value is defined as 4.OK, nice, but:
2.6.17-ck1:
/*
* Scheduling policies
*/#define SCHED_NORMAL 0 #define SCHED_FIFO 1 #define SCHED_RR 2 #define SCHED_BATCH 3 #define SCHED_ISO 4 #define SCHED_IDLEPRIO 5
Quoted 8 lines
#define
SCHED_MIN0
#defineSCHED_MAX5Arggl.
So what does that tell us?
We need a common header now.
Jan Engelhardt
some quick comments within code below.
Quoted 45 lines · Peter Williams
--- include/linux/init_task.h | 6 - include/linux/sched.h | 11 ++ kernel/fork.c | 1 kernel/mutex.c | 28 ++++++- kernel/sched.c | 183++++++++++++++++++++++++++++++++++++++-------- 5 files changed, 192 insertions(+), 37 deletions(-)
Index:
MM-2.6.17-mm6/include/linux/init_task.h
===================================================================
---MM-2.6.17-mm6.orig/include/linux/init_task.h2006-07-04
14:37:42.000000000 +1000 +++MM-2.6.17-mm6/include/linux/init_task.h2006-07-04 14:38:12.000000000 +1000include/linux/init_task.h +3
-3@@ -99,9 +99,9 @@ extern struct group_info init_groups; .usage = ATOMIC_INIT(2), \ .flags = 0, \ .lock_depth = -1, \ - .prio = MAX_PRIO-20, \ - .static_prio = MAX_PRIO-20, \ - .normal_prio = MAX_PRIO-20, \ + .prio = MAX_RT_PRIO+20, \ + .static_prio = MAX_RT_PRIO+20, \ + .normal_prio = MAX_RT_PRIO+20, \ .policy = SCHED_NORMAL, \ .cpus_allowed = CPU_MASK_ALL, \ .mm = NULL, \Index:
MM-2.6.17-mm6/include/linux/sched.h
===================================================================
---MM-2.6.17-mm6.orig/include/linux/sched.h2006-07-04 14:37:43.000000000
+1000 +++MM-2.6.17-mm6/include/linux/sched.h2006-07-04 14:38:12.000000000
+1000 @@ -34,6 +34,8 @@
#defineSCHED_FIFO1
#defineSCHED_RR2
#defineSCHED_BATCH3include/linux/sched.h +2
-1+/* Scheduler class for background tasks */ +#define SCHED_BGND 4#ifdef __KERNEL__@@ -503,13 +505,16 @@ struct signal_struct {#define MAX_USER_RT_PRIO 100#define MAX_RT_PRIO MAX_USER_RT_PRIO -#define MAX_PRIO (MAX_RT_PRIO + 40)
include/linux/sched.h struct signal_struct { · line 516
Quoted 10 lines
include/linux/sched.h +4
-1+#define BGND_PRIO (MAX_RT_PRIO + 40) +/* add another slot for SCHED_BGND tasks */ +#define MAX_PRIO (BGND_PRIO + 1)#define rt_prio (prio) unlikely((prio) < MAX_RT_PRIO)#define rt_task (p) rt_prio((p)->prio)#define batch_task (p) (unlikely((p)->policy == SCHED_BATCH))#define has_rt_policy (p) \ - unlikely((p)->policy != SCHED_NORMAL && (p)->policy != SCHED_BATCH) + unlikely((p)->policy != SCHED_NORMAL && (p)->policy < SCHED_BATCH)
idleprio tasks should be able to get rt_policy as well
Quoted 89 lines
include/linux/sched.h +2
-0+#define bgnd_task (p) (unlikely((p)->policy == SCHED_BGND))/* * Some day this will be a full-fledged user tracking system.. @@ -810,6 +815,7 @@ struct task_struct {unsigned long sleep_avg;unsigned long long timestamp, last_ran;unsigned long long sched_time;/* sched_clock time spent running */ +unsigned int mutexes_held;/* for knowing when it's safe to repress SCHED_BGND tasks */ enum sleep_type sleep_type;unsigned long policy;@@ -1090,6 +1096,7 @@ static inline void put_task_struct(struc#define PF_SWAPWRITE 0x00800000/* Allowed to write to swap */ #define PF_SPREAD_PAGE 0x01000000/* Spread page cache over cpuset */ #define PF_SPREAD_SLAB 0x02000000 /* Spread some slab caches over cpuset */ +#define PF_UIWAKE 0x08000000 /* Just woken from uninterrptible sleep */#define PF_MEMPOLICY 0x10000000/* Non-default NUMA mempolicy */ #define PF_MUTEX_TESTER 0x20000000/* Thread belongs to the rt mutex tester */
Index:
MM-2.6.17-mm6/kernel/sched.c
===================================================================kernel/sched.c +14
-6@@ -59,7 +59,7 @@/* * Convert user-nice values [ -20 ... 0 ... 19 ] -* to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ], +* to static priority [ MAX_RT_PRIO..BGND_PRIO-1 ], * and back. */ #define NICE_TO_PRIO (nice) (MAX_RT_PRIO + (nice) + 20)@@ -73,7 +73,7 @@*/ #define USER_PRIO (p) ((p)-MAX_RT_PRIO)#define TASK_USER_PRIO (p) USER_PRIO((p)->static_prio) -#define MAX_USER_PRIO (USER_PRIO(MAX_PRIO)) +#define MAX_USER_PRIO (USER_PRIO(BGND_PRIO))/* * Some helpers for converting nanosecond timing to jiffy resolution @@ -171,7 +171,7 @@*/ #define SCALE_PRIO (x, prio) \ - max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO / 2), MIN_TIMESLICE) + max(x * (BGND_PRIO - prio) / (MAX_USER_PRIO / 2), MIN_TIMESLICE)static unsigned int static_prio_timeslice (int static_prio) {@@ -186,6 +186,11 @@ static inline unsigned int task_timeslicreturn static_prio_timeslice (p->static_prio); } +#define task_in_background (p) unlikely((p)->prio == BGND_PRIO) +#define safe_to_background (p) \ + (!((p)->mutexes_held || \ + (p)->flags & (PF_FREEZE | PF_UIWAKE | PF_EXITING))) +/* * These are the runqueue data structures: */ @@ -715,13 +720,17 @@ static inline int __normal_prio(struct t {int bonus, prio; +/* Ensure that background tasks stay at BGND_PRIO */ +if (bgnd_task (p) &&safe_to_background (p)) +return BGND_PRIO ; + bonus =CURRENT_BONUS (p) -MAX_BONUS /2 ; prio = p->static_prio - bonus;if (prio <MAX_RT_PRIO ) prio =MAX_RT_PRIO ; -if (prio >MAX_PRIO -1 ) - prio =MAX_PRIO -1 ; +if (prio >BGND_PRIO -1 ) + prio =BGND_PRIO -1 ;return prio; }@@ -761,8 +770,18 @@ static void set_load_weight(struct task_ else#endif p->load_weight =RTPRIO_TO_LOAD_WEIGHT (p->rt_priority); - }else
kernel/sched.c static void set_load_weight(struct task_ · line 781
Quoted 10 lines
kernel/sched.c +9
-1- p->load_weight =PRIO_TO_LOAD_WEIGHT (p->static_prio); + }else { +/* +* Reduce the probability of a task escaping the background +* due to load balancing leaving it on a lighly used CPU +* Can't use zero as that would kill load balancing when only +* background tasks are running. +*/ +if (bgnd_task (p)) + p->load_weight =LOAD_WEIGHT (MIN_TIMESLICE /2 ? :1 );
Why not just set it to 1 for all idleprio tasks? The granularity will be lost at anything lower anyway and it avoids a more complex calculation.
kernel/sched.c static void __activate_task(struct task_ · line 856
Quoted 12 lines
kernel/sched.c +4
-1+else + p->load_weight =PRIO_TO_LOAD_WEIGHT (p->static_prio); + } } static inline void@@ -834,7 +853,10 @@ static void __activate_task(struct task_ {struct prio_array *target = rq->active; -if (batch_task (p)) +/* Don't punish batch tasks just tasks actually in the background
An extra line here for multiline comments such as:
+ /*
+ * Don't punish batch tasks just tasks actually in the background
Quoted 30 lines
kernel/sched.c +9
-0+* as anything else is counter productive from a system wide aspect +*/ +if (task_in_background (p)) target = rq->expired;enqueue_task (p, target);inc_nr_running (p, rq);@@ -942,6 +964,8 @@ static void activate_task(struct task_stif (!rt_task (p)) p->prio =recalc_task_prio (p, now); + p->flags &= ~PF_UIWAKE ; +/* * This checks to make sure it's not an uninterruptible task * that is now waking up. @@ -1484,6 +1508,7 @@ out_activate:* sleep_avg beyond just interactive state. */ p->sleep_type =SLEEP_NONINTERACTIVE ; + p->flags |=PF_UIWAKE ; }else /* @@ -3024,6 +3049,48 @@ void scheduler_tick(void) } goto out_unlock; } + +if (bgnd_task (p)) { +/*
kernel/sched.c void scheduler_tick(void) · line 3064
Quoted 10 lines
kernel/sched.c +10
-0+* Do this even if there's only one task on the queue as +* we want to set the priority low so that any waking tasks +* can preempt. +*/ +if (task_in_background (p)) { +/* +* Tasks currently in the background will be +* at BGND_PRIO priority and preemption +* should be enough to keep them in check provided we +* don't let them adversely effect tasks on the expired
ok I'm going to risk a lart and say "affect" ?
Quoted 91 lines
kernel/sched.c +61
-0+* array. +*/ +if (!safe_to_background (p)) { +dequeue_task (p, rq->active); + p->prio =effective_prio (p); +enqueue_task (p, rq->active); + }else if (rq->expired->nr_active && + rq->best_expired_prio < p->prio) { +dequeue_task (p, rq->active); +enqueue_task (p, rq->expired); +set_tsk_need_resched (p); + goto out_unlock; + } + } +else if (safe_to_background (p)) { +dequeue_task (p, rq->active); + p->normal_prio =BGND_PRIO ; +/* this should be safe for PI purposes */ + p->prio = p->normal_prio; +enqueue_task (p, rq->expired); +/* +* think about making this conditional to reduce +* context switch rate +*/ +set_tsk_need_resched (p); + goto out_unlock; + } + } +if (!--p->time_slice) {dequeue_task (p, rq->active);set_tsk_need_resched (p);@@ -3033,6 +3100,11 @@ void scheduler_tick(void)if (!rq->expired_timestamp) rq->expired_timestamp = jiffies; +/* +* No need to do anything special for background tasks here +* as TASK_INTERACTIVE() should fail when they're in the +* background. +*/ if (!TASK_INTERACTIVE (p) ||expired_starving (rq)) {enqueue_task (p, rq->expired);if (p->static_prio < rq->best_expired_prio)@@ -3122,6 +3194,33 @@ smt_slice(struct task_struct *p, struct }/* +* task time slice for SMT dependent idle purposes +*/ +static unsigned int smt_timeslice (struct task_struct *p) +{ +if (task_in_background (p)) +return 0 ; + +return task_timeslice (p); +} + +/* +* Is the thisp a higher priority task than thatp for SMT dependent idle +* purposes? +*/ +static int task_priority_gt (const struct task_struct *thisp, +const struct task_struct *thatp) +{ +if (task_in_background (thisp)) +return !task_in_background (thatp); + +if (task_in_background (thatp)) +return 1 ; + +return thisp->static_prio < thatp->static_prio; +} + +/* * To minimise lock contention and not have to drop this_rq's runlock we only * trylock the sibling runqueues and bypass those runqueues if we fail to * acquire their lock. As we only trylock the normal locking order does not @@ -3180,9 +3279,9 @@ dependent_sleeper(int
this_cpu, struct rkernel/sched.c +2
-2(sd->per_cpu_gain * DEF_TIMESLICE / 100)) ret =1 ; }else { -if (smt_curr->static_prio < p->static_prio && +if (task_priority_gt (smt_curr, p) && !TASK_PREEMPTS_CURR (p, smt_rq) && -smt_slice (smt_curr, sd) >task_timeslice (p)) +smt_slice (smt_curr, sd) >smt_timeslice (p)) ret =1 ; } unlock:
kernel/sched.c static inline int interactive_sleep(enum · line 3350
Quoted 7 lines
kernel/sched.c +3
-0@@ -3245,6 +3344,22 @@ static inline int interactive_sleep(enum }/* +* Switch the active and expired arrays. +*/ +static struct prio_array *switch_arrays (struct rq *rq,int best_active_prio) +{
In the fast path this should be inlined even if it is large.
Quoted 54 lines
kernel/sched.c +26
-12+struct prio_array *array = rq->active; + +schedstat_inc (rq, sched_switch); + rq->active = rq->expired; + rq->expired = array; + rq->expired_timestamp =0 ; + rq->best_expired_prio = best_active_prio; + +return rq->active; +} + +/* * schedule() is the main scheduler function. */ asmlinkage void __sched schedule(void)@@ -3332,23 +3447,25 @@ need_resched_nonpreemptible: } array = rq->active; -if (unlikely (!array->nr_active)) { -/* -* Switch the active and expired arrays. -*/ -schedstat_inc (rq, sched_switch); - rq->active = rq->expired; - rq->expired = array; - array = rq->active; - rq->expired_timestamp =0 ; - rq->best_expired_prio =MAX_PRIO ; - } +if (unlikely (!array->nr_active)) + array =switch_arrays (rq,MAX_PRIO ); idx =sched_find_first_bit (array->bitmap); +get_next: queue = array->queue + idx; next = list_entry(queue->next, struct task_struct, run_list); +/* very strict backgrounding */ +if (unlikely (task_in_background (next) && rq->expired->nr_active)) { +int tmp =sched_find_first_bit (rq->expired->bitmap); + +if (likely (tmp < idx)) { + array =switch_arrays (rq, idx); + idx = tmp; + goto get_next; + } + } -if (!rt_task (next) &&interactive_sleep (next->sleep_type)) { +if (!rt_task (next) &&interactive_sleep (next->sleep_type) && !bgnd_task (next)) {unsigned long long delta = now - next->timestamp;if (unlikely ((long long )(now - next->timestamp) <0 )) delta =0 ;
kernel/sched.c recheck: · line 4173
Quoted 6 lines
kernel/sched.c +2
-1@@ -4052,7 +4169,8 @@ recheck:if (policy <0 ) policy = oldpolicy = p->policy;else if (policy !=SCHED_FIFO && policy !=SCHED_RR && - policy !=SCHED_NORMAL && policy !=SCHED_BATCH ) + policy !=SCHED_NORMAL && policy !=SCHED_BATCH && + policy !=SCHED_BGND )
how about a wrapper for all these policies? (see my sched_range patch)
kernel/sched.c recheck: · line 4186
Quoted 12 lines
kernel/sched.c +2
-2return -EINVAL ;/* * Valid priorities for SCHED_FIFO and SCHED_RR are @@ -4063,8 +4181,8 @@ recheck: (p->mm && param->sched_priority >MAX_USER_RT_PRIO -1 ) || (!p->mm && param->sched_priority > MAX_RT_PRIO-1)) return -EINVAL; -if ((policy ==SCHED_NORMAL || policy ==SCHED_BATCH ) - != (param->sched_priority ==0 )) +if ((policy ==SCHED_NORMAL || policy ==SCHED_BATCH || + policy ==SCHED_BGND ) != (param->sched_priority ==0 ))return -EINVAL ;
same
Quoted 8 lines
kernel/sched.c +1
-2/* @@ -4072,15 +4190,20 @@ recheck:*/ if (!capable (CAP_SYS_NICE )) {/* -* can't change policy, except between SCHED_NORMAL -* and SCHED_BATCH: +* can't change policy, except between SCHED_NORMAL,
kernel/sched.c recheck: · line 4201
Quoted 10 lines
kernel/sched.c +7
-2+* SCHED_BATCH or SCHED_BGND: */ - if (((policy != SCHED_NORMAL && p->policy != SCHED_BATCH) && - (policy != SCHED_BATCH && p->policy != SCHED_NORMAL)) && + if (((policy != SCHED_NORMAL && p->policy != SCHED_BATCH && + p->policy != SCHED_BGND) && + (policy != SCHED_BATCH && p->policy != SCHED_NORMAL && + p->policy != SCHED_BGND) && + (policy != SCHED_BGND && p->policy != SCHED_NORMAL && + p->policy != SCHED_BATCH)) &&
same
Quoted 91 lines
kernel/sched.c +2
-1!p->signal->rlim[RLIMIT_RTPRIO].rlim_cur)return -EPERM ;/* can't increase priority */ -if ((policy !=SCHED_NORMAL && policy !=SCHED_BATCH ) && +if ((policy !=SCHED_NORMAL && policy !=SCHED_BATCH && + policy !=SCHED_BGND ) && param->sched_priority > p->rt_priority && param->sched_priority > p->signal->rlim[RLIMIT_RTPRIO ].rlim_cur)Index:
MM-2.6.17-mm6/kernel/mutex.c
===================================================================kernel/mutex.c +26
-2@@ -51,6 +51,16 @@ __mutex_init(struct mutex *lock, const cEXPORT_SYMBOL (__mutex_init); +static inline void inc_mutex_count (void ) +{ + current->mutexes_held++; +} + +static inline void dec_mutex_count (void ) +{ + current->mutexes_held--; +} +/* * We split the mutex lock/unlock logic into separate fastpath and * slowpath functions, to reduce the register pressure on the fastpath. @@ -89,6 +99,7 @@ void inline fastcall __sched mutex_lock(* 'unlocked' into 'locked' state. */ __mutex_fastpath_lock (&lock->count, __mutex_lock_slowpath); +inc_mutex_count (); }EXPORT_SYMBOL (mutex_lock);@@ -114,6 +125,7 @@ void fastcall __sched mutex_unlock(struc* into 'unlocked' state: */ __mutex_fastpath_unlock (&lock->count, __mutex_unlock_slowpath); +dec_mutex_count (); }EXPORT_SYMBOL (mutex_unlock);@@ -274,9 +286,16 @@ __mutex_lock_interruptible_slowpath(atom*/ int fastcall __sched mutex_lock_interruptible(struct mutex *lock) { +int ret; +might_sleep (); -return __mutex_fastpath_lock_retval + ret =__mutex_fastpath_lock_retval (&lock->count, __mutex_lock_interruptible_slowpath); + +if (likely (!ret)) +inc_mutex_count (); + +return ret; }EXPORT_SYMBOL (mutex_lock_interruptible);@@ -331,8 +350,13 @@ static inline int __mutex_trylock_slowpa*/ int fastcall __sched mutex_trylock(struct mutex *lock) { -return __mutex_fastpath_trylock (&lock->count, +int ret =__mutex_fastpath_trylock (&lock->count, __mutex_trylock_slowpath); + +if (likely (ret)) +inc_mutex_count (); + +return ret; }EXPORT_SYMBOL (mutex_trylock);Index:
MM-2.6.17-mm6/kernel/fork.c
===================================================================kernel/fork.c +1
-0@@ -1029,6 +1029,7 @@ static struct task_struct *copy_process( p->wchar =0 ;/* I/O counter: bytes written */ p->syscr =0 ;/* I/O counter: read syscalls */ p->syscw =0 ;/* I/O counter: write syscalls */ + p->mutexes_held =0 ;acct_clear_integrals (p); p->it_virt_expires = cputime_zero;
Signature · 1 line
-ck
Quoted 52 lines · Con Kolivas
some quick comments within code below.
Quoted 49 lines · Peter Williams
--- include/linux/init_task.h | 6 - include/linux/sched.h | 11 ++ kernel/fork.c | 1 kernel/mutex.c | 28 ++++++- kernel/sched.c | 183++++++++++++++++++++++++++++++++++++++-------- 5 files changed, 192 insertions(+), 37 deletions(-)
Index:
MM-2.6.17-mm6/include/linux/init_task.h
===================================================================
---MM-2.6.17-mm6.orig/include/linux/init_task.h2006-07-04
14:37:42.000000000 +1000 +++MM-2.6.17-mm6/include/linux/init_task.h2006-07-04 14:38:12.000000000 +1000include/linux/init_task.h +3
-3@@ -99,9 +99,9 @@ extern struct group_info init_groups; .usage = ATOMIC_INIT(2), \ .flags = 0, \ .lock_depth = -1, \ - .prio = MAX_PRIO-20, \ - .static_prio = MAX_PRIO-20, \ - .normal_prio = MAX_PRIO-20, \ + .prio = MAX_RT_PRIO+20, \ + .static_prio = MAX_RT_PRIO+20, \ + .normal_prio = MAX_RT_PRIO+20, \ .policy = SCHED_NORMAL, \ .cpus_allowed = CPU_MASK_ALL, \ .mm = NULL, \Index:
MM-2.6.17-mm6/include/linux/sched.h
===================================================================
---MM-2.6.17-mm6.orig/include/linux/sched.h2006-07-04 14:37:43.000000000
+1000 +++MM-2.6.17-mm6/include/linux/sched.h2006-07-04 14:38:12.000000000
+1000 @@ -34,6 +34,8 @@
#defineSCHED_FIFO1
#defineSCHED_RR2
#defineSCHED_BATCH3include/linux/sched.h +5
-1+/* Scheduler class for background tasks */ +#define SCHED_BGND 4#ifdef __KERNEL__@@ -503,13 +505,16 @@ struct signal_struct {#define MAX_USER_RT_PRIO 100#define MAX_RT_PRIO MAX_USER_RT_PRIO -#define MAX_PRIO (MAX_RT_PRIO + 40) +#define BGND_PRIO (MAX_RT_PRIO + 40) +/* add another slot for SCHED_BGND tasks */ +#define MAX_PRIO (BGND_PRIO + 1)
Quoted 8 lines
include/linux/sched.h struct signal_struct { · line 516
Quoted 6 lines
include/linux/sched.h +1
-1#define rt_prio (prio) unlikely((prio) < MAX_RT_PRIO)#define rt_task (p) rt_prio((p)->prio)#define batch_task (p) (unlikely((p)->policy == SCHED_BATCH))#define has_rt_policy (p) \ - unlikely((p)->policy != SCHED_NORMAL && (p)->policy != SCHED_BATCH) + unlikely((p)->policy != SCHED_NORMAL && (p)->policy < SCHED_BATCH)idleprio tasks should be able to get
rt_policyas well
I don't understand what you mean here. A task can only have one scheduling policy. The simple (direct) definition of has_rt_policy() is (p->policy == SCHED_FIFO || p->policy == SCHED_RR) and the one defined is just a rearrangement of that with a view to minimizing overhead in the majority of invocations.
Quoted 155 lines
Quoted 90 lines
include/linux/sched.h +2
-0+#define bgnd_task (p) (unlikely((p)->policy == SCHED_BGND))/* * Some day this will be a full-fledged user tracking system.. @@ -810,6 +815,7 @@ struct task_struct {unsigned long sleep_avg;unsigned long long timestamp, last_ran;unsigned long long sched_time;/* sched_clock time spent running */ +unsigned int mutexes_held;/* for knowing when it's safe to repress SCHED_BGND tasks */ enum sleep_type sleep_type;unsigned long policy;@@ -1090,6 +1096,7 @@ static inline void put_task_struct(struc#define PF_SWAPWRITE 0x00800000/* Allowed to write to swap */ #define PF_SPREAD_PAGE 0x01000000/* Spread page cache over cpuset */ #define PF_SPREAD_SLAB 0x02000000 /* Spread some slab caches over cpuset */ +#define PF_UIWAKE 0x08000000 /* Just woken from uninterrptible sleep */#define PF_MEMPOLICY 0x10000000/* Non-default NUMA mempolicy */ #define PF_MUTEX_TESTER 0x20000000/* Thread belongs to the rt mutex tester */
Index:
MM-2.6.17-mm6/kernel/sched.c
===================================================================kernel/sched.c +14
-6@@ -59,7 +59,7 @@/* * Convert user-nice values [ -20 ... 0 ... 19 ] -* to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ], +* to static priority [ MAX_RT_PRIO..BGND_PRIO-1 ], * and back. */ #define NICE_TO_PRIO (nice) (MAX_RT_PRIO + (nice) + 20)@@ -73,7 +73,7 @@*/ #define USER_PRIO (p) ((p)-MAX_RT_PRIO)#define TASK_USER_PRIO (p) USER_PRIO((p)->static_prio) -#define MAX_USER_PRIO (USER_PRIO(MAX_PRIO)) +#define MAX_USER_PRIO (USER_PRIO(BGND_PRIO))/* * Some helpers for converting nanosecond timing to jiffy resolution @@ -171,7 +171,7 @@*/ #define SCALE_PRIO (x, prio) \ - max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO / 2), MIN_TIMESLICE) + max(x * (BGND_PRIO - prio) / (MAX_USER_PRIO / 2), MIN_TIMESLICE)static unsigned int static_prio_timeslice (int static_prio) {@@ -186,6 +186,11 @@ static inline unsigned int task_timeslicreturn static_prio_timeslice (p->static_prio); } +#define task_in_background (p) unlikely((p)->prio == BGND_PRIO) +#define safe_to_background (p) \ + (!((p)->mutexes_held || \ + (p)->flags & (PF_FREEZE | PF_UIWAKE | PF_EXITING))) +/* * These are the runqueue data structures: */ @@ -715,13 +720,17 @@ static inline int __normal_prio(struct t {int bonus, prio; +/* Ensure that background tasks stay at BGND_PRIO */ +if (bgnd_task (p) &&safe_to_background (p)) +return BGND_PRIO ; + bonus =CURRENT_BONUS (p) -MAX_BONUS /2 ; prio = p->static_prio - bonus;if (prio <MAX_RT_PRIO ) prio =MAX_RT_PRIO ; -if (prio >MAX_PRIO -1 ) - prio =MAX_PRIO -1 ; +if (prio >BGND_PRIO -1 ) + prio =BGND_PRIO -1 ;return prio; }@@ -761,8 +770,18 @@ static void set_load_weight(struct task_ else#endif p->load_weight =RTPRIO_TO_LOAD_WEIGHT (p->rt_priority); - }else kernel/sched.c static void set_load_weight(struct task_ · line 781
Quoted 10 lines
kernel/sched.c +9
-1- p->load_weight =PRIO_TO_LOAD_WEIGHT (p->static_prio); + }else { +/* +* Reduce the probability of a task escaping the background +* due to load balancing leaving it on a lighly used CPU +* Can't use zero as that would kill load balancing when only +* background tasks are running. +*/ +if (bgnd_task (p)) + p->load_weight =LOAD_WEIGHT (MIN_TIMESLICE /2 ? :1 );Why not just set it to 1 for all idleprio tasks? The granularity will be lost at anything lower anyway and it avoids a more complex calculation.
kernel/sched.c static void __activate_task(struct task_ · line 856
Quoted 12 lines
kernel/sched.c +4
-1+else + p->load_weight =PRIO_TO_LOAD_WEIGHT (p->static_prio); + } } static inline void@@ -834,7 +853,10 @@ static void __activate_task(struct task_ {struct prio_array *target = rq->active; -if (batch_task (p)) +/* Don't punish batch tasks just tasks actually in the background An extra line here for multiline comments such as:
(quoted diff) +2
-0+ /* + * Don't punish batch tasks just tasks actually in the backgroundQuoted 36 lines
kernel/sched.c +13
-0+* as anything else is counter productive from a system wide aspect +*/ +if (task_in_background (p)) target = rq->expired;enqueue_task (p, target);inc_nr_running (p, rq);@@ -942,6 +964,8 @@ static void activate_task(struct task_stif (!rt_task (p)) p->prio =recalc_task_prio (p, now); + p->flags &= ~PF_UIWAKE ; +/* * This checks to make sure it's not an uninterruptible task * that is now waking up. @@ -1484,6 +1508,7 @@ out_activate:* sleep_avg beyond just interactive state. */ p->sleep_type =SLEEP_NONINTERACTIVE ; + p->flags |=PF_UIWAKE ; }else /* @@ -3024,6 +3049,48 @@ void scheduler_tick(void) } goto out_unlock; } + +if (bgnd_task (p)) { +/* +* Do this even if there's only one task on the queue as +* we want to set the priority low so that any waking tasks +* can preempt. +*/
Quoted 8 lines
kernel/sched.c void scheduler_tick(void) · line 3064
Quoted 6 lines
kernel/sched.c +6
-0+if (task_in_background (p)) { +/* +* Tasks currently in the background will be +* at BGND_PRIO priority and preemption +* should be enough to keep them in check provided we +* don't let them adversely effect tasks on the expired ok I'm going to risk a lart and say "affect" ?
I have to refer you to the Oxford English Dictionary. According to it (when used as a verb):
affect: 1. like, love 2. like to use, practice or wear 3. aim at, seek 4. use or display ostentatiously 5. assume a false appearance 6. attack as a disease 7. move or touch.
effect: 1. bring about (an event or result) 2. produce (a state or condition) 3. make, construct or build
Quoted 94 lines
Quoted 94 lines
kernel/sched.c +61
-0+* array. +*/ +if (!safe_to_background (p)) { +dequeue_task (p, rq->active); + p->prio =effective_prio (p); +enqueue_task (p, rq->active); + }else if (rq->expired->nr_active && + rq->best_expired_prio < p->prio) { +dequeue_task (p, rq->active); +enqueue_task (p, rq->expired); +set_tsk_need_resched (p); + goto out_unlock; + } + } +else if (safe_to_background (p)) { +dequeue_task (p, rq->active); + p->normal_prio =BGND_PRIO ; +/* this should be safe for PI purposes */ + p->prio = p->normal_prio; +enqueue_task (p, rq->expired); +/* +* think about making this conditional to reduce +* context switch rate +*/ +set_tsk_need_resched (p); + goto out_unlock; + } + } +if (!--p->time_slice) {dequeue_task (p, rq->active);set_tsk_need_resched (p);@@ -3033,6 +3100,11 @@ void scheduler_tick(void)if (!rq->expired_timestamp) rq->expired_timestamp = jiffies; +/* +* No need to do anything special for background tasks here +* as TASK_INTERACTIVE() should fail when they're in the +* background. +*/ if (!TASK_INTERACTIVE (p) ||expired_starving (rq)) {enqueue_task (p, rq->expired);if (p->static_prio < rq->best_expired_prio)@@ -3122,6 +3194,33 @@ smt_slice(struct task_struct *p, struct }/* +* task time slice for SMT dependent idle purposes +*/ +static unsigned int smt_timeslice (struct task_struct *p) +{ +if (task_in_background (p)) +return 0 ; + +return task_timeslice (p); +} + +/* +* Is the thisp a higher priority task than thatp for SMT dependent idle +* purposes? +*/ +static int task_priority_gt (const struct task_struct *thisp, +const struct task_struct *thatp) +{ +if (task_in_background (thisp)) +return !task_in_background (thatp); + +if (task_in_background (thatp)) +return 1 ; + +return thisp->static_prio < thatp->static_prio; +} + +/* * To minimise lock contention and not have to drop this_rq's runlock we only * trylock the sibling runqueues and bypass those runqueues if we fail to * acquire their lock. As we only trylock the normal locking order does not @@ -3180,9 +3279,9 @@ dependent_sleeper(int
this_cpu, struct rkernel/sched.c +2
-2(sd->per_cpu_gain * DEF_TIMESLICE / 100)) ret =1 ; }else { -if (smt_curr->static_prio < p->static_prio && +if (task_priority_gt (smt_curr, p) && !TASK_PREEMPTS_CURR (p, smt_rq) && -smt_slice (smt_curr, sd) >task_timeslice (p)) +smt_slice (smt_curr, sd) >smt_timeslice (p)) ret =1 ; } unlock:@@ -3245,6 +3344,22 @@ static inline int interactive_sleep(enum }
Quoted 7 lines
kernel/sched.c static inline int interactive_sleep(enum
Quoted 5 lines
kernel/sched.c +3
-0/* +* Switch the active and expired arrays. +*/ +static struct prio_array *switch_arrays (struct rq *rq,int best_active_prio) +{In the fast path this should be inlined even if it is large.
OK.
Quoted 49 lines
Quoted 49 lines
kernel/sched.c +25
-11+struct prio_array *array = rq->active; + +schedstat_inc (rq, sched_switch); + rq->active = rq->expired; + rq->expired = array; + rq->expired_timestamp =0 ; + rq->best_expired_prio = best_active_prio; + +return rq->active; +} + +/* * schedule() is the main scheduler function. */ asmlinkage void __sched schedule(void)@@ -3332,23 +3447,25 @@ need_resched_nonpreemptible: } array = rq->active; -if (unlikely (!array->nr_active)) { -/* -* Switch the active and expired arrays. -*/ -schedstat_inc (rq, sched_switch); - rq->active = rq->expired; - rq->expired = array; - array = rq->active; - rq->expired_timestamp =0 ; - rq->best_expired_prio =MAX_PRIO ; - } +if (unlikely (!array->nr_active)) + array =switch_arrays (rq,MAX_PRIO ); idx =sched_find_first_bit (array->bitmap); +get_next: queue = array->queue + idx; next = list_entry(queue->next, struct task_struct, run_list); +/* very strict backgrounding */ +if (unlikely (task_in_background (next) && rq->expired->nr_active)) { +int tmp =sched_find_first_bit (rq->expired->bitmap); + +if (likely (tmp < idx)) { + array =switch_arrays (rq, idx); + idx = tmp; + goto get_next; + } + }
Quoted 14 lines
kernel/sched.c recheck: · line 4173
Quoted 12 lines
kernel/sched.c +3
-2-if (!rt_task (next) &&interactive_sleep (next->sleep_type)) { +if (!rt_task (next) &&interactive_sleep (next->sleep_type) && !bgnd_task (next)) {unsigned long long delta = now - next->timestamp;if (unlikely ((long long )(now - next->timestamp) <0 )) delta =0 ;@@ -4052,7 +4169,8 @@ recheck:if (policy <0 ) policy = oldpolicy = p->policy;else if (policy !=SCHED_FIFO && policy !=SCHED_RR && - policy !=SCHED_NORMAL && policy !=SCHED_BATCH ) + policy !=SCHED_NORMAL && policy !=SCHED_BATCH && + policy !=SCHED_BGND )how about a wrapper for all these policies? (see my
sched_rangepatch)
I must admit that when I was doing this I wished it was less messy. But I figured that it was best to do it in a way that was easy to show as being correct and then do simplification later. Especially, as simplification would also effect the other policies.
Quoted 129 lines
kernel/sched.c recheck: · line 4186
Quoted 13 lines
kernel/sched.c +2
-2return -EINVAL ;/* * Valid priorities for SCHED_FIFO and SCHED_RR are @@ -4063,8 +4181,8 @@ recheck: (p->mm && param->sched_priority >MAX_USER_RT_PRIO -1 ) || (!p->mm && param->sched_priority > MAX_RT_PRIO-1)) return -EINVAL; -if ((policy ==SCHED_NORMAL || policy ==SCHED_BATCH ) - != (param->sched_priority ==0 )) +if ((policy ==SCHED_NORMAL || policy ==SCHED_BATCH || + policy ==SCHED_BGND ) != (param->sched_priority ==0 ))return -EINVAL ;same
Quoted 8 lines
kernel/sched.c +1
-2/* @@ -4072,15 +4190,20 @@ recheck:*/ if (!capable (CAP_SYS_NICE )) {/* -* can't change policy, except between SCHED_NORMAL -* and SCHED_BATCH: +* can't change policy, except between SCHED_NORMAL, kernel/sched.c recheck: · line 4201
Quoted 10 lines
kernel/sched.c +7
-2+* SCHED_BATCH or SCHED_BGND: */ - if (((policy != SCHED_NORMAL && p->policy != SCHED_BATCH) && - (policy != SCHED_BATCH && p->policy != SCHED_NORMAL)) && + if (((policy != SCHED_NORMAL && p->policy != SCHED_BATCH && + p->policy != SCHED_BGND) && + (policy != SCHED_BATCH && p->policy != SCHED_NORMAL && + p->policy != SCHED_BGND) && + (policy != SCHED_BGND && p->policy != SCHED_NORMAL && + p->policy != SCHED_BATCH)) &&same
Quoted 91 lines
kernel/sched.c +2
-1!p->signal->rlim[RLIMIT_RTPRIO].rlim_cur)return -EPERM ;/* can't increase priority */ -if ((policy !=SCHED_NORMAL && policy !=SCHED_BATCH ) && +if ((policy !=SCHED_NORMAL && policy !=SCHED_BATCH && + policy !=SCHED_BGND ) && param->sched_priority > p->rt_priority && param->sched_priority > p->signal->rlim[RLIMIT_RTPRIO ].rlim_cur)Index:
MM-2.6.17-mm6/kernel/mutex.c
===================================================================kernel/mutex.c +26
-2@@ -51,6 +51,16 @@ __mutex_init(struct mutex *lock, const cEXPORT_SYMBOL (__mutex_init); +static inline void inc_mutex_count (void ) +{ + current->mutexes_held++; +} + +static inline void dec_mutex_count (void ) +{ + current->mutexes_held--; +} +/* * We split the mutex lock/unlock logic into separate fastpath and * slowpath functions, to reduce the register pressure on the fastpath. @@ -89,6 +99,7 @@ void inline fastcall __sched mutex_lock(* 'unlocked' into 'locked' state. */ __mutex_fastpath_lock (&lock->count, __mutex_lock_slowpath); +inc_mutex_count (); }EXPORT_SYMBOL (mutex_lock);@@ -114,6 +125,7 @@ void fastcall __sched mutex_unlock(struc* into 'unlocked' state: */ __mutex_fastpath_unlock (&lock->count, __mutex_unlock_slowpath); +dec_mutex_count (); }EXPORT_SYMBOL (mutex_unlock);@@ -274,9 +286,16 @@ __mutex_lock_interruptible_slowpath(atom*/ int fastcall __sched mutex_lock_interruptible(struct mutex *lock) { +int ret; +might_sleep (); -return __mutex_fastpath_lock_retval + ret =__mutex_fastpath_lock_retval (&lock->count, __mutex_lock_interruptible_slowpath); + +if (likely (!ret)) +inc_mutex_count (); + +return ret; }EXPORT_SYMBOL (mutex_lock_interruptible);@@ -331,8 +350,13 @@ static inline int __mutex_trylock_slowpa*/ int fastcall __sched mutex_trylock(struct mutex *lock) { -return __mutex_fastpath_trylock (&lock->count, +int ret =__mutex_fastpath_trylock (&lock->count, __mutex_trylock_slowpath); + +if (likely (ret)) +inc_mutex_count (); + +return ret; }EXPORT_SYMBOL (mutex_trylock);Index:
MM-2.6.17-mm6/kernel/fork.c
===================================================================kernel/fork.c +1
-0@@ -1029,6 +1029,7 @@ static struct task_struct *copy_process( p->wchar =0 ;/* I/O counter: bytes written */ p->syscr =0 ;/* I/O counter: read syscalls */ p->syscw =0 ;/* I/O counter: write syscalls */ + p->mutexes_held =0 ;acct_clear_integrals (p); p->it_virt_expires = cputime_zero;
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Quoted 9 lines · Peter Williams
Quoted 7 lines · Con Kolivas
some quick comments within code below.
include/linux/sched.h struct signal_struct { · line 516
Quoted 2 lines · Peter Williams
include/linux/sched.h +1
-1-unlikely ((p)->policy !=SCHED_NORMAL && (p)->policy !=SCHED_BATCH ) +unlikely ((p)->policy !=SCHED_NORMAL && (p)->policy <SCHED_BATCH )idleprio tasks should be able to get
rt_policyas well
Quoted 5 lines
I don't understand what you mean here. A task can only have one scheduling policy. The simple (direct) definition of
has_rt_policy()is (p->policy==SCHED_FIFO||p->policy==SCHED_RR) and the one defined is just a rearrangement of that with a view to minimizing overhead in the majority of invocations.
I meant they could get rt priority. This does look correct, sorry.
Quoted 8 lines
Quoted 6 lines
kernel/sched.c void scheduler_tick(void) · line 3064
Quoted 4 lines
kernel/sched.c +4
-0+* Tasks currently in the background will be +* at BGND_PRIO priority and preemption +* should be enough to keep them in check provided we +* don't let them adversely effect tasks on the expired ok I'm going to risk a lart and say "affect" ?
I have to refer you to the Oxford English Dictionary.
I was hoping you would.
Quoted 9 lines
According to it
(when used as a verb):affect: 1. like, love 2. like to use, practice or wear 3. aim at, seek
4. use or display ostentatiously 5. assume a false appearance 6. attack as a disease 7. move or touch.effect: 1. bring about (an event or result) 2. produce (a state or condition) 3. make, construct or build
Let's take this discussion offlist for my benefit, as I'd like to nut this out. I still see it as affect with those definitions.
Signature · 1 line
-ck
Quoted 6 lines · Con Kolivas
Quoted 5 lines · Peter Williams
Quoted 3 lines · Con Kolivas
kernel/sched.c void scheduler_tick(void) · line 3064
Quoted 1 line
kernel/sched.c +1
-0+* don't let them adversely effect tasks on the expired ok I'm going to risk a lart and say "affect" ?
No, that would be correct English.
Quoted 1 line
Quoted 1 line
I have to refer you to the Oxford English Dictionary.
Actually, something like Strunk&White's "Elements of Style" is better suited to this sort of thing than the OED. The OED just lists *words*, not how to put them together.
Quoted 1 line
I was hoping you would.
They would *affect* tasks. The *effect* of this would be...
Note that 'effect' can be a verb too, but in that sense it refers to a "facilitator" - "The mayor effected change in policy" meaning that he made it happen. So in the kernel, "A effects B" is only correct if A is code that is intended to make B happen. If A, through blind all-elbows coding, happens to cause B to change, then "A affects B" is proper.
Clear as mud? :) If not, read the Strunk&White explanation of this one. :)
Quoted 12 lines · Con Kolivas
some quick comments within code below.
Quoted 9 lines · Peter Williams
kernel/sched.c +3
-2@@ -761,8 +770,18 @@ static void set_load_weight(struct task_ else#endif p->load_weight =RTPRIO_TO_LOAD_WEIGHT (p->rt_priority); - }else - p->load_weight =PRIO_TO_LOAD_WEIGHT (p->static_prio); + }else { +/* +* Reduce the probability of a task escaping the background
Quoted 8 lines
kernel/sched.c static void set_load_weight(struct task_ · line 781
Quoted 6 lines
kernel/sched.c +6
-0+* due to load balancing leaving it on a lighly used CPU +* Can't use zero as that would kill load balancing when only +* background tasks are running. +*/ +if (bgnd_task (p)) + p->load_weight =LOAD_WEIGHT (MIN_TIMESLICE /2 ? :1 );Why not just set it to 1 for all idleprio tasks? The granularity will be lost at anything lower anyway and it avoids a more complex calculation.
I missed this one in my previous reply. I agree, what you say makes sense. I was in my "think too hard" mode and probably thinking (unnecessarily) about how it might effect the smoothed load calculations.
Peter
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Quoted 7 lines · Peter Williams
===================================================================
kernel/mutex.c +0
-0@@ -51,6 +51,16 @@ __mutex_init(struct mutex *lock, const cEXPORT_SYMBOL (__mutex_init);
kernel/mutex.c __mutex_init(struct mutex *lock, const c · line 63
Quoted 10 lines
kernel/mutex.c +10
-0+static inline void inc_mutex_count (void ) +{ + current->mutexes_held++; +} + +static inline void dec_mutex_count (void ) +{ + current->mutexes_held--; +} +
NACK! This whole patch is way too intrusive for such a relatively small gain.
also, if something doesnt hold a mutex, it might still be unsafe to background it! For example if it holds a semaphore. Or an rwsem. Or any other kernel resource that has exclusion semantics.
so unless this patch gets _much_ less complex and much less intrusive, we'll have to stay with SCHED_BATCH and nice +19.
Ingo
Quoted 22 lines · Ingo Molnar
Quoted 7 lines · Peter Williams
===================================================================
kernel/mutex.c +0
-0@@ -51,6 +51,16 @@ __mutex_init(struct mutex *lock, const cEXPORT_SYMBOL (__mutex_init);kernel/mutex.c __mutex_init(struct mutex *lock, const c · line 63
Quoted 10 lines
kernel/mutex.c +10
-0+static inline void inc_mutex_count (void ) +{ + current->mutexes_held++; +} + +static inline void dec_mutex_count (void ) +{ + current->mutexes_held--; +} +NACK! This whole patch is way too intrusive for such a relatively small gain.
Quoted 3 lines
also, if something doesnt hold a mutex, it might still be unsafe to background it! For example if it holds a semaphore. Or an rwsem. Or any other kernel resource that has exclusion semantics.
so unless this patch gets _much_ less complex and much less intrusive, we'll have to stay with
SCHED_BATCHand nice +19.
This means being less strict but (as you imply) that may be not much better than nice +19. I'll have a look at it.
Of course, a comprehensive (as opposed to RT only) priority inheritance mechanism would make the "safe/unsafe to background" problem go away and make this patch very simple. Any plans in that direction?
Peter
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Quoted 5 lines
Of course, a comprehensive (as opposed to RT only) priority inheritance mechanism would make the "safe/unsafe to background" problem go away and make this patch very simple. Any plans in that direction?
there is a very simple prio inheritance mechanism available already:
just treat "running in kernel mode" as a "go to nice +19" thing, and I suspect things will suddenly be safe ;)
Quoted 18 lines · Peter Williams
Quoted 18 lines
kernel/mutex.c __mutex_init(struct mutex *lock, const c · line 63
Quoted 10 lines
kernel/mutex.c +10
-0+static inline void inc_mutex_count (void ) +{ + current->mutexes_held++; +} + +static inline void dec_mutex_count (void ) +{ + current->mutexes_held--; +} +NACK! This whole patch is way too intrusive for such a relatively small gain.
also, if something doesnt hold a mutex, it might still be unsafe to background it! For example if it holds a semaphore. Or an rwsem. Or any other kernel resource that has exclusion semantics.
Quoted 5 lines
Quoted 2 lines
so unless this patch gets _much_ less complex and much less intrusive, we'll have to stay with
SCHED_BATCHand nice +19.This means being less strict but (as you imply) that may be not much better than nice +19. I'll have a look at it.
it's way too much pain for little gain.
Quoted 4 lines
Of course, a comprehensive (as opposed to RT only) priority inheritance mechanism would make the "safe/unsafe to background" problem go away and make this patch very simple. Any plans in that direction?
that seems quite unlikely to happen. I think you are missing the biggest
issue: for RT, if the priority inheritance mechanism does not extend to a given scheduling pattern it causes longer latencies, but no harm is done otherwise. But for SCHED_BGND we'd have to make sure _every_ place is priority-inversions safe - otherwise we risk a potential local DoS if a task with a critical resource is backgrounded! That's plain impossible to achieve.
Ingo
Quoted 6 lines · Ingo Molnar
Quoted 1 line · Peter Williams
Of course, a comprehensive (as opposed to RT only) priority inheritance mechanism would make the "safe/unsafe to background" problem go away and make this patch very simple. Any plans in that direction?
that seems quite unlikely to happen. I think you are missing the biggest issue: for RT, if the priority inheritance mechanism does not extend to a given scheduling pattern it causes longer latencies, but no harm is done otherwise. But for
SCHED_BGNDwe'd have to make sure _every_ place is priority-inversions safe - otherwise we risk a potential local DoS if a task with a critical resource is backgrounded! That's plain impossible to achieve.
Right. And it isn't just straightforward things like locks, but any limited resource.
mempools and block device requests are two that come to mind.
Signature · 3 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Quoted 20 lines · Peter Williams
kernel/sched.c +3
-11@@ -3332,23 +3447,25 @@ need_resched_nonpreemptible: } array = rq->active; -if (unlikely (!array->nr_active)) { -/* -* Switch the active and expired arrays. -*/ -schedstat_inc (rq, sched_switch); - rq->active = rq->expired; - rq->expired = array; - array = rq->active; - rq->expired_timestamp =0 ; - rq->best_expired_prio =MAX_PRIO ; - } +if (unlikely (!array->nr_active)) + array =switch_arrays (rq,MAX_PRIO ); idx =sched_find_first_bit (array->bitmap); +get_next:
kernel/sched.c need_resched_nonpreemptible: · line 3464
Quoted 10 lines
kernel/sched.c +8
-0queue = array->queue + idx; next = list_entry(queue->next, struct task_struct, run_list); +/* very strict backgrounding */ +if (unlikely (task_in_background (next) && rq->expired->nr_active)) { +int tmp =sched_find_first_bit (rq->expired->bitmap); + +if (likely (tmp < idx)) { + array =switch_arrays (rq, idx); + idx = tmp; + goto get_next;
Won't this potentially expire the mutex holder which you specifically protect in scheduler_tick() if it was preempted before being ticked? The task in the expired array could also be a !safe_to_background() task who already had a chance to run, and who's slice expired.
If it's worth protecting higher priority tasks from mutex holders ending up in the expired array, then there's a case that should be examined. There's little difference between a background task acquiring a mutex, and a normal task with one tick left on it's slice. Best for sleepers is of course to just say no to expiring mutex holders period.
-Mike
Quoted 20 lines · Mike Galbraith
Quoted 18 lines · Peter Williams
kernel/sched.c +2
-11@@ -3332,23 +3447,25 @@ need_resched_nonpreemptible: } array = rq->active; -if (unlikely (!array->nr_active)) { -/* -* Switch the active and expired arrays. -*/ -schedstat_inc (rq, sched_switch); - rq->active = rq->expired; - rq->expired = array; - array = rq->active; - rq->expired_timestamp =0 ; - rq->best_expired_prio =MAX_PRIO ; - } +if (unlikely (!array->nr_active)) + array =switch_arrays (rq,MAX_PRIO );
Quoted 15 lines
kernel/sched.c need_resched_nonpreemptible: · line 3464
Quoted 12 lines
kernel/sched.c +9
-0idx =sched_find_first_bit (array->bitmap); +get_next: queue = array->queue + idx; next = list_entry(queue->next, struct task_struct, run_list); +/* very strict backgrounding */ +if (unlikely (task_in_background (next) && rq->expired->nr_active)) { +int tmp =sched_find_first_bit (rq->expired->bitmap); + +if (likely (tmp < idx)) { + array =switch_arrays (rq, idx); + idx = tmp; + goto get_next;Won't this potentially expire the mutex holder which you specifically protect in
scheduler_tick()if it was preempted before being ticked?
I don't think so as its prio value should cause task_in_background() to fail.
Quoted 2 lines
The task in the expired array could also be a !safe_to_background() task who already had a chance to run, and who's slice expired.
If it's !safe_to_background() it's in our interest to let it run in order to free up the resource that it's holding.
Quoted 3 lines
If it's worth protecting higher priority tasks from mutex holders ending up in the expired array, then there's a case that should be examined.
It's more than just stopping them end up in the expired array. It's stopping them being permanently in the expired array.
Quoted 2 lines
There's little difference between a background task acquiring a mutex, and a normal task with one tick left on it's slice.
The difference is that the background task could stay there forever.
Quoted 2 lines
Best for sleepers
is of course to just say no to expiring mutex holders period.
In spite of my comments above, I agree that not expiring mutex holders might (emphasis on the "might") be good for overall system performance by reducing the time for which locks are held. Giving them a whole new time slice on the active array might be too generous though. It could become quite complex.
Peter
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Quoted 37 lines · Peter Williams
Quoted 20 lines · Mike Galbraith
Quoted 18 lines · Peter Williams
kernel/sched.c +2
-11@@ -3332,23 +3447,25 @@ need_resched_nonpreemptible: } array = rq->active; -if (unlikely (!array->nr_active)) { -/* -* Switch the active and expired arrays. -*/ -schedstat_inc (rq, sched_switch); - rq->active = rq->expired; - rq->expired = array; - array = rq->active; - rq->expired_timestamp =0 ; - rq->best_expired_prio =MAX_PRIO ; - } +if (unlikely (!array->nr_active)) + array =switch_arrays (rq,MAX_PRIO );Quoted 15 lines
kernel/sched.c need_resched_nonpreemptible: · line 3464
Quoted 12 lines
kernel/sched.c +9
-0idx =sched_find_first_bit (array->bitmap); +get_next: queue = array->queue + idx; next = list_entry(queue->next, struct task_struct, run_list); +/* very strict backgrounding */ +if (unlikely (task_in_background (next) && rq->expired->nr_active)) { +int tmp =sched_find_first_bit (rq->expired->bitmap); + +if (likely (tmp < idx)) { + array =switch_arrays (rq, idx); + idx = tmp; + goto get_next;Won't this potentially expire the mutex holder which you specifically protect in
scheduler_tick()if it was preempted before being ticked?
Quoted 1 line
I don't think so as its prio value should cause
task_in_background()to fail.
Actually, you're right, a pre-emption at the wrong time could cause the prio value not to have been changed. There needs to be a safe_to_background(next) in there somewhere.
Peter
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Quoted 6 lines · Peter Williams
Quoted 2 lines · Mike Galbraith
The task in the expired array could also be a !safe_to_background() task who already had a chance to run, and who's slice expired.
If it's !safe_to_background() it's in our interest to let it run in order to free up the resource that it's holding.
Only if there are waiters (or you know there will be some before the holder gets a chance to run again). Even then, they might be background tasks, so it could still be ~wrong.
(yeah, comprehensive PI would be mucho tidier than tick time)
-Mike
Quoted 11 lines · Mike Galbraith
Quoted 4 lines · Peter Williams
Quoted 2 lines · Mike Galbraith
The task in the expired array could also be a !safe_to_background() task who already had a chance to run, and who's slice expired.
If it's !safe_to_background() it's in our interest to let it run in order to free up the resource that it's holding.
Only if there are waiters (or you know there will be some before the holder gets a chance to run again). Even then, they might be background tasks, so it could still be ~wrong.
(yeah, comprehensive PI would be mucho tidier than tick time)
Yes. Unfortunately, in Ingo's opinion, even if we have comprehensive PI it's unlikely to be reliable enough to guarantee putting tasks into the background is safe. Of course, this wouldn't detract from its general usefulness -- just makes it no good for SCHED_BGND/SCHED_IDLEPRIO purposes.
Peter
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce