CPU_PISCH: Implement Simple Priority Based Round Robin (SPBRR) scheduler Signed-off-by: Peter Williams diff --git a/include/linux/sched.h b/include/linux/sched.h --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1214,6 +1214,9 @@ struct rcu_node; #ifdef CONFIG_CPU_PISCH struct cpu_pisch_task_data { +#ifdef CONFIG_CPU_PISCH_SPBRR + s64 rq_key; +#endif }; #endif diff --git a/kernel/Kconfig.cpu_pisch b/kernel/Kconfig.cpu_pisch --- a/kernel/Kconfig.cpu_pisch +++ b/kernel/Kconfig.cpu_pisch @@ -35,6 +35,17 @@ config CPU_PISCH_CFS_FAIR To boot this CPU scheduler, if it is not the default, use the boot parameter "cpu_pisch=cfs_fair". +config CPU_PISCH_SPBRR + bool "'Simple Priority Based Round Robin' CPU scheduler" if CPU_PISCH_CHOOSE_BUILTINS + depends on CPU_PISCH + default CPU_PISCH + ---help--- + This is a simple priority based CPU scheduler where "nice" + determines priority and tasks with the same priority round + robin with each other with fixed time slices. + To boot this CPU scheduler, if it is not the default, use the + boot parameter "cpu_pisch=spbrr". + choice prompt "Default CPU scheduler" depends on CPU_PISCH @@ -50,6 +61,14 @@ config CPU_PISCH_DEFAULT_CFS_FAIR This is the default CPU scheduler which is an O(1) model of an "ideal, precise multi-tasking CPU".. +config CPU_PISCH_DEFAULT_SPBRR + bool "Simple Priority Based Round Robin CPU scheduler" + select CPU_PISCH_SPBRR + ---help--- + This is a simple priority based CPU scheduler where "nice" + determines priority and tasks with the same priority round + robin with each other with fixed time slices. + endchoice endmenu diff --git a/kernel/cpu_pisch_drv.c b/kernel/cpu_pisch_drv.c --- a/kernel/cpu_pisch_drv.c +++ b/kernel/cpu_pisch_drv.c @@ -7,6 +7,8 @@ const struct cpu_pisch_drv *cpu_pisch_drvp = #if defined(CONFIG_CPU_PISCH_DEFAULT_CFS_FAIR) &cfs_fair_cpu_pisch_drv; +#elif defined(CONFIG_CPU_PISCH_DEFAULT_SPBRR) + &spbrr_cpu_pisch_drv; #else NULL; #error "You must have at least 1 CPU scheduler selected" @@ -16,6 +18,9 @@ const struct cpu_pisch_drv *cpu_pisch_dr #if defined(CONFIG_CPU_PISCH_CFS_FAIR) &cfs_fair_cpu_pisch_drv, #endif +#if defined(CONFIG_CPU_PISCH_SPBRR) + &spbrr_cpu_pisch_drv, +#endif NULL, }; diff --git a/kernel/cpu_pisch_spbrr.c b/kernel/cpu_pisch_spbrr.c new file mode 100644 --- /dev/null +++ b/kernel/cpu_pisch_spbrr.c @@ -0,0 +1,167 @@ +/* + * Simple Priority Based Round Robin (SPBRR) Scheduling Class + * (SCHED_NORMAL/SCHED_BATCH) + * + * Copyright (C) 2009 Peter Williams + */ + +/* + * Time slice for round robinning of SCHED_NORMAL/SCHED_BATCH tasks + * default: 20ms (units: nanoseconds) + */ +unsigned int spbrr_time_slice = 20000000ULL; + +/* + * Extra amount to add to nr_running when mustiplying spbrr_time_slice + * to determine the interval between anti starvation boosts + * default : 2 + */ +unsigned int spbrr_as_factor = 2; + +static const struct sched_class spbrr_sched_class; + +static inline +void spbrr_set_task_rq_key(struct task_struct *p, struct rq *rq) +{ + p->cpu_pisch.rq_key = p->prio * 2 + rq->cpu_pisch.key_offset + + (p->policy != SCHED_NORMAL); +} + +static inline +void spbrr_set_se_rq_key(struct cfs_rq *cfs_rq, struct sched_entity *se) +{ + spbrr_set_task_rq_key(task_of(se), rq_of(cfs_rq)); +} + +static inline +void spbrr_place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial) +{ + if (entity_is_task(se)) + spbrr_set_se_rq_key(cfs_rq, se); + else + cfs_fair_place_entity(cfs_rq, se, initial); +} + +static inline +void spbrr_place_entity_after(struct sched_entity *sea, struct sched_entity *seb) +{ + if (entity_is_task(sea)) + task_of(sea)->cpu_pisch.rq_key = task_of(seb)->cpu_pisch.rq_key + 1; + else + cfs_fair_place_entity_after(sea, seb); +} + +static inline +int spbrr_entity_before(struct sched_entity *a, struct sched_entity *b) +{ + /* only ever used on tasks so no need for complications */ + return task_of(a)->cpu_pisch.rq_key < task_of(b)->cpu_pisch.rq_key; +} + +static inline +s64 spbrr_entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se) +{ + if (entity_is_task(se)) + return task_of(se)->cpu_pisch.rq_key; + else + return cfs_fair_entity_key(cfs_rq, se); +} + +static inline +void spbrr_rq_tick(struct rq* rq) +{ + if (rq->nr_running < 2) { + rq->cpu_pisch.key_offset_last_update = rq->clock; + rq->cpu_pisch.key_offset = 0; + } + else { + u64 difftime = rq->clock - rq->cpu_pisch.key_offset_last_update; + + if (difftime > spbrr_time_slice * (rq->nr_running + spbrr_as_factor) / 2) { + rq->cpu_pisch.key_offset_last_update = rq->clock; + rq->cpu_pisch.key_offset++; + } + } +} + +static inline +u64 spbrr_sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) +{ + if (entity_is_task(se)) + return spbrr_time_slice; + else + return cfs_fair_sched_slice(cfs_rq, se); +} + +static inline void +spbrr_update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr, + unsigned long delta_exec) +{ + if (!entity_is_task(curr)) + cfs_fair_update_curr(cfs_rq, curr, delta_exec); + + spbrr_set_se_rq_key(cfs_rq, curr); +} + +static inline +void spbrr_swap_places(struct sched_entity *sea, struct sched_entity *seb) +{ + if (entity_is_task(sea)) + swap(task_of(sea)->cpu_pisch.rq_key, task_of(seb)->cpu_pisch.rq_key); + else + cfs_fair_swap_places(sea, seb); +} + +static inline +void spbrr_inherit_place(struct sched_entity *sea, struct sched_entity *seb) +{ + if (entity_is_task(sea)) + task_of(sea)->cpu_pisch.rq_key = task_of(seb)->cpu_pisch.rq_key; + else + cfs_fair_inherit_place(sea, seb); +} + +static inline int +spbrr_wakeup_preempt_entity(struct sched_entity *sea, struct sched_entity *seb) +{ + if (!entity_is_task(sea)) + return cfs_fair_wakeup_preempt_entity(sea, seb); + + if (task_of(sea)->cpu_pisch.rq_key <= task_of(seb)->cpu_pisch.rq_key) + return -1; + + return 1; +} + +static inline void +spbrr_change_task_cpu(struct task_struct *p, unsigned int old_cpu, unsigned int new_cpu) +{ + spbrr_set_task_rq_key(p, cpu_rq(new_cpu)); +} + +#define asis(x) ((unsigned long long)x) + +CPU_PISCH_SYSFS_DEFINE_UNSIGNED_RW(time_slice_ns, spbrr_time_slice, asis, asis); +CPU_PISCH_SYSFS_DEFINE_UNSIGNED_RW(as_factor, spbrr_as_factor, asis, asis); + +static struct attribute *cpu_pisch_spbrr_attrs[] = { + CPU_PISCH_SYSFS_ATTR(time_slice_ns), + CPU_PISCH_SYSFS_ATTR(as_factor), + NULL, +}; + +static const struct cpu_pisch_drv spbrr_cpu_pisch_drv = { + .name = "spbrr", + .attrs = cpu_pisch_spbrr_attrs, + .place_entity_after = spbrr_place_entity_after, + .entity_before = spbrr_entity_before, + .entity_key = spbrr_entity_key, + .place_entity = spbrr_place_entity, + .sched_slice = spbrr_sched_slice, + .update_curr = spbrr_update_curr, + .rq_tick = spbrr_rq_tick, + .swap_places = spbrr_swap_places, + .inherit_place = spbrr_inherit_place, + .wakeup_preempt_entity = spbrr_wakeup_preempt_entity, + .change_task_cpu = spbrr_change_task_cpu, +}; diff --git a/kernel/sched.c b/kernel/sched.c --- a/kernel/sched.c +++ b/kernel/sched.c @@ -517,6 +517,10 @@ static struct root_domain def_root_domai #ifdef CONFIG_CPU_PISCH struct cpu_pisch_rq_data { +#ifdef CONFIG_CPU_PISCH_SPBRR + s64 key_offset; + u64 key_offset_last_update; +#endif }; #endif @@ -1830,6 +1834,9 @@ static void calc_load_account_active(str #include "sched_fair.c" #include "sched_rt.c" #ifdef CONFIG_CPU_PISCH +#ifdef CONFIG_CPU_PISCH_SPBRR +#include "cpu_pisch_spbrr.c" +#endif #include "cpu_pisch_drv.c" #endif #ifdef CONFIG_SCHED_DEBUG