Skip to contentSkip to conversation

sched: use EDF to throttle RT task groups v2

PATCH In review Fabio Checconi 4 participants 26 messages Feb 23, 2010 – Mar 23, 2010 Scheduler

lore
Share & tools
lore
#0 lore raw

cover sched: use EDF to throttle RT task groups v2

This patchset introduces a group level EDF scheduler extending the throttling mechanism, in order to make it support generic period assignments. With this patch, the runtime and period parameters can be used to specify arbitrary CPU reservations for RT tasks.

Quoted 1 line

From the previous post [1] I've integrated Peter's suggestions, using

a multi-level hierarchy to do admission control, but a one-level only equivalent hierarchy for scheduling, and I've not removed the bandwidth migration mechanism, trying to adapt it to EDF scheduling. In this version tasks are still inserted into priority arrays and only groups are kept in a per-rq edf tree.

The main design issues involved:

- Since it is not easy to mix tasks and groups on the same scheduler queue (tasks have no deadlines), the bandwidth reserved to the tasks in a group is controlled with two additional cgroup attributes:
rt_task_runtime_us and rt_task_period_us. These attributes control, within a cgroup, how much bandwidth is reserved to the tasks it contains. The old attributes, rt_runtime_us and rt_period_us, are still there, and control the bandwidth assigned to the cgroup. They are used only for admission control.

- Shared resources are still handled using boosting. When a group contains a task inside a critical section it is scheduled according the highest priority among the ones of the tasks it contains. In this way, the same group has two modes: when it is not boosted it is scheduled according to its deadline; when it is boosted, it is scheduled according its priority. Boosted groups are always favored over non-boosted ones.

- Given that the various rt_rq's belonging to the same task group are activated independently, there is the need of a timer per each rt_rq.

- While balancing the bandwidth assigned to a cgroup on various cpus we have to make sure that utilization for the rt_rq's on each cpu does not exceed the global utilization limit for RT tasks.

Please note that these patches target a completely different usage scenario from Dario's work on SCHED_DEADLINE. SCHED_DEADLINE is about deadline scheduling for tasks, introducing a new user-visible scheduling policy; this patchset is about using throttling to provide real-time guarantees to SCHED_RR and SCHED_FIFO tasks on a per-group basis. The two patchsets do not overlap in functionality, both aim at improving the predictability of the system; we'll want to work on sharing parts of the code, but now, after discussing with Dario, we think it's too early to do that.

The patchset is against tip, it should compile (and hopefully work) on all the combinations of CONFIG_{SMP/RT_GROUP_SCHED}, but the work was focused on the SMP & RT_GROUP_SCHED case, I've only compile- or boot- tested the other configs.

As usual, feedback welcome.

[1] http://lkml.org/lkml/2009/6/15/510

Fabio Checconi (3):
sched: use EDF to schedule groups
sched: enforce per-cpu utilization limits on runtime balancing
sched: make runtime balancing code more EDF-friendly

 include/linux/sched.h |    8 +-
 kernel/sched.c        |  467 +++++++++++---------
 kernel/sched_rt.c     | 1159 +++++++++++++++++++++++++++++++++++++-----------
 3 files changed, 1161 insertions(+), 473 deletions(-)
#1 lore raw

PATCH 1/3 sched: use EDF to schedule groups

Modify sched_rt in order to implement throttling using EDF among groups; this allows the user to specify groups with different periods.

This patch:
- adds a deadline to rt_rq's (and removes the scheduling entity from it, as the new two-level compression of the full cgroup hierarchy do not use it for intermediates nodes anymore);
- moves the rt_period_timer from struct rt_bandwidth to struct rt_rq, since periods and replenishments are no more synchronized among rt_rq's belonging to the same task_group;
- adds a new struct rt_bandwidth to each task_group; the old one is used only for admission control, on a full cgroup hierarchy, while the new one is used to contain the parameters used to reserve bandwidth to tasks;
- introduces a per-rq rt_edf_tree structure, to keep all the rt_rq's belonging to the same cpu ordered by their dynamic priority (i.e., their deadline, if they are not boosted, or the static priority of their highest priority task if they are);
- updates the admission control code, to take into account the bandwidth assigned to tasks via the new cgroup attributes rt_task_period_us and rt_task_runtime_us (this bandwidth is not available for lower-level cgroups);
- removes highest_prio tracking for non-root rt_rq's and flattens the arbitrary task_group hierarchy to a two-level one, transparently to the users, who still see the full cgroup hierarchy. The push/pull logic is altered a bit after this change, as the toplevel rt_nr_running is no more meaningful, we use rt_nr_total instead (the reasoning behind this is that tasks should be pushed/pulled without taking into account the fact that they are throttled or not). The toplevel runqueue, containing both the rt_edf_tree and the highest_prio data is no more a rt_rq, but it has its own type, rt_root_rq.

---
 include/linux/sched.h |    8 +-
 kernel/sched.c        |  404 ++++++++++++++------------
 kernel/sched_rt.c     |  775 ++++++++++++++++++++++++++++++++++---------------
 3 files changed, 764 insertions(+), 423 deletions(-)
include/linux/sched.h +4 -4
index 0eef87b..b82343b 100644
@@ -2517,12 +2517,12 @@ extern int sched_group_set_shares(struct task_group *tg, unsigned long shares);
 extern unsigned long sched_group_shares(struct task_group *tg);
 #endif
 #ifdef CONFIG_RT_GROUP_SCHED
-extern int sched_group_set_rt_runtime(struct task_group *tg,
+extern int sched_group_set_rt_runtime(struct task_group *tg, int task_data,
 				      long rt_runtime_us);
-extern long sched_group_rt_runtime(struct task_group *tg);
-extern int sched_group_set_rt_period(struct task_group *tg,
+extern long sched_group_rt_runtime(struct task_group *tg, int task_data);
+extern int sched_group_set_rt_period(struct task_group *tg, int task_data,
 				      long rt_period_us);
-extern long sched_group_rt_period(struct task_group *tg);
+extern long sched_group_rt_period(struct task_group *tg, int task_data);
 extern int sched_rt_can_attach(struct task_group *tg, struct task_struct *tsk);
 #endif
 #endif
kernel/sched.c +218 -186

700 lines not on this page · raw message

kernel/sched_rt.c +542 -233

1,115 lines not on this page · raw message

Signature · 1 line
1.6.5.7
maintainer
#2 lore raw

Re: [PATCH 1/3] sched: use EDF to schedule groups

kernel/sched_rt.c static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se) · line 34

Quoted 8 lines · Fabio Checconi
kernel/sched_rt.c +2 -1
@@ -36,7 +29,8 @@ static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
 
 static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
 {
-       return container_of(rt_rq, struct rq, rt);
+       struct rt_root_rq *rt = container_of(rt_rq, struct rt_root_rq, rt_rq);
+       return container_of(rt, struct rq, rt);
 } 

I think you can write that double container_of() as a single:

return container_of(rt_rq, struct rq, rt.rt_rq);

#3 lore raw

Re: [PATCH 1/3] sched: use EDF to schedule groups

Quoted 15 lines

From: Peter Zijlstra <[email protected]>
Date: Thu, Feb 25, 2010 09:28:20PM +0100

kernel/sched_rt.c static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se) · line 34

Quoted 8 lines · Fabio Checconi
kernel/sched_rt.c +2 -1
@@ -36,7 +29,8 @@ static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
 
 static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
 {
-       return container_of(rt_rq, struct rq, rt);
+       struct rt_root_rq *rt = container_of(rt_rq, struct rt_root_rq, rt_rq);
+       return container_of(rt, struct rq, rt);
 } 

I think you can write that double container_of() as a single:

Quoted 2 lines

return container_of(rt_rq, struct rq, rt.rt_rq);

I'll fix it, thanks.

#4 lore raw

PATCH 2/3 sched: enforce per-cpu utilization limits on runtime balancing

In reply to Fabio Checconi

Enforce utilization constraints on the bandwidth assignments produced by the runtime balancing code. The underlying EDF scheduler requires, in order to work reliably, that the utilization on each cpu does not exceed 100%; this patch adds per-cpu utilization tracking and does not allow the balancer to exceed the global RT bandwidth assignment on any cpu.

Whenever the bandwidth assigments change (i.e., the user writes an RT-scheduler cgroup attribute, or a task_group disappears, the bandwidth assignment is reset to a symmetric assignment, and the balancing restarts from a safe startpoint. This requires iterating on all the rt_rq's in the system (N_cpu * N_groups), and it is surely suboptimal, but it is conceptually simple and safe.

Synchronization needs a couple of words: a per-rq flag disables runtime balancing to/from single rq's; the flag relies on spinlock acquire barriers to ensure that all the balancing operations starting after the flag has been set see the its correct value. To protect the per-rq free bandwidth counter we use per-rq locks, that can nest like rq->lock; reusing existing locks proved not to be easy, as the various rt_runtime_locks act on a per-group or per-rt_rq basis.

---
 kernel/sched.c    |   77 ++++++++++-----
 kernel/sched_rt.c |  280 +++++++++++++++++++++++++++++++++++++++++++++++++----
 2 files changed, 312 insertions(+), 45 deletions(-)
kernel/sched.c +53 -24
index fe013c6..4dddbc2 100644
@@ -374,6 +374,11 @@ struct rt_rq {
 struct rt_edf_tree {
 	struct rb_root rb_root;
 	struct rb_node *rb_leftmost;
+
+#ifdef CONFIG_SMP
+	unsigned long rt_free_bw;
+	raw_spinlock_t rt_bw_lock;
+#endif
 };
 
 /* Root runqueue for rt tasks: */
@@ -458,6 +463,7 @@ struct rq {
 
 	struct cfs_rq cfs;
 	struct rt_root_rq rt;
+	int rt_balancing_disabled;
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	/* list of leaf cfs_rq on this cpu: */
@@ -1754,6 +1760,25 @@ static void cfs_rq_set_shares(struct cfs_rq *cfs_rq, unsigned long shares)
 }
 #endif
 
+#ifdef CONFIG_RT_GROUP_SCHED
+static unsigned long to_ratio(u64 period, u64 runtime)
+{
+	if (runtime == RUNTIME_INF)
+		return 1UL << 20;
+
+	return div64_u64(runtime << 20, period);
+}
+#endif
+
+#ifdef CONFIG_SMP
+static inline unsigned long rt_init_free_bw(void)
+{
+	unsigned long used = to_ratio(global_rt_period(), global_rt_runtime());
+
+	return to_ratio(RUNTIME_INF, RUNTIME_INF) - used;
+}
+#endif
+
 static void calc_load_account_active(struct rq *this_rq);
 static void update_sysctl(void);
 static int get_update_sysctl_factor(void);
@@ -7563,6 +7588,9 @@ static void init_rt_root_rq(struct rt_root_rq *rt, struct rq *rq)
 	rt->rt_nr_migratory = 0;
 	rt->overloaded = 0;
 	plist_head_init_raw(&rt->pushable_tasks, &rq->lock);
+
+	rt->rt_edf_tree.rt_free_bw = rt_init_free_bw();
+	raw_spin_lock_init(&rt->rt_edf_tree.rt_bw_lock);
 #endif
 	rt->rt_edf_tree.rb_root = RB_ROOT;
 	init_rt_rq(&rt->rt_rq, rq, &def_rt_bandwidth);
@@ -8114,7 +8142,11 @@ static void free_sched_group(struct task_group *tg)
 	kfree(tg);
 }
 
-/* allocate runqueue etc for a new task group */
+/*
+ * Allocate runqueue etc for a new task group.  Note that new groups
+ * are created with zero runtime, so there is no need to update the
+ * free bandwidth counters.
+ */
 struct task_group *sched_create_group(struct task_group *parent)
 {
 	struct task_group *tg;
@@ -8159,6 +8191,8 @@ static void free_sched_group_rcu(struct rcu_head *rhp)
 	free_sched_group(container_of(rhp, struct task_group, rcu));
 }
 
+static DEFINE_MUTEX(rt_constraints_mutex);
+
 /* Destroy runqueue etc associated with a task group */
 void sched_destroy_group(struct task_group *tg)
 {
@@ -8174,6 +8208,10 @@ void sched_destroy_group(struct task_group *tg)
 	list_del_rcu(&tg->siblings);
 	spin_unlock_irqrestore(&task_group_lock, flags);
 
+	mutex_lock(&rt_constraints_mutex);
+	rt_reset_runtime();
+	mutex_unlock(&rt_constraints_mutex);
+
 	/* wait for possible concurrent references to cfs_rqs complete */
 	call_rcu(&tg->rcu, free_sched_group_rcu);
 }
@@ -8313,15 +8351,6 @@ unsigned long sched_group_shares(struct task_group *tg)
 /*
  * Ensure that the real time constraints are schedulable.
  */
-static DEFINE_MUTEX(rt_constraints_mutex);
-
-static unsigned long to_ratio(u64 period, u64 runtime)
-{
-	if (runtime == RUNTIME_INF)
-		return 1ULL << 20;
-
-	return div64_u64(runtime << 20, period);
-}
 
 /* Must be called with tasklist_lock held */
 static inline int tg_has_rt_tasks(struct task_group *tg)
@@ -8442,7 +8471,7 @@ static int __rt_schedulable(struct task_group *tg, u64 period,
 static int tg_set_bandwidth(struct task_group *tg, int task_data,
 		u64 rt_period, u64 rt_runtime)
 {
-	int i, err = 0;
+	int err = 0;
 
 	mutex_lock(&rt_constraints_mutex);
 	read_lock(&tasklist_lock);
@@ -8454,15 +8483,6 @@ static int tg_set_bandwidth(struct task_group *tg, int task_data,
 		raw_spin_lock_irq(&tg->rt_task_bandwidth.rt_runtime_lock);
 		tg->rt_task_bandwidth.rt_period = ns_to_ktime(rt_period);
 		tg->rt_task_bandwidth.rt_runtime = rt_runtime;
-
-		for_each_possible_cpu(i) {
-			struct rt_rq *rt_rq = tg->rt_rq[i];
-
-			raw_spin_lock(&rt_rq->rt_runtime_lock);
-			rt_rq->rt_runtime = rt_runtime;
-			rt_rq->rt_period = ns_to_ktime(rt_period);
-			raw_spin_unlock(&rt_rq->rt_runtime_lock);
-		}
 		raw_spin_unlock_irq(&tg->rt_task_bandwidth.rt_runtime_lock);
 	} else {
 		raw_spin_lock_irq(&tg->rt_bandwidth.rt_runtime_lock);
@@ -8473,6 +8493,8 @@ static int tg_set_bandwidth(struct task_group *tg, int task_data,
 
 unlock:
 	read_unlock(&tasklist_lock);
+	if (task_data)
+		rt_reset_runtime();
 	mutex_unlock(&rt_constraints_mutex);
 
 	return err;
@@ -8568,12 +8590,12 @@ int sched_rt_can_attach(struct task_group *tg, struct task_struct *tsk)
 	return 1;
 }
 
+static inline void sched_rt_update_bandwidth(void) {}
+
 #else /* !CONFIG_RT_GROUP_SCHED */
+
 static int sched_rt_global_constraints(void)
 {
-	unsigned long flags;
-	int i;
-
 	if (sysctl_sched_rt_period <= 0)
 		return -EINVAL;
 
@@ -8586,7 +8608,7 @@ static int sched_rt_global_constraints(void)
 
 	raw_spin_lock_irqsave(&def_rt_bandwidth.rt_runtime_lock, flags);
 	for_each_possible_cpu(i) {
-		struct rt_rq *rt_rq = &cpu_rq(i)->rt;
+		struct rt_rq *rt_rq = &cpu_rq(i)->rt.rt_rq;
 
 		raw_spin_lock(&rt_rq->rt_runtime_lock);
 		rt_rq->rt_runtime = global_rt_runtime();
@@ -8596,6 +8618,12 @@ static int sched_rt_global_constraints(void)
 
 	return 0;
 }
+
+static inline void sched_rt_update_bandwidth(void)
+{
+	rt_reset_runtime();
+}
+
 #endif /* CONFIG_RT_GROUP_SCHED */
 
 int sched_rt_handler(struct ctl_table *table, int write,
@@ -8621,6 +8649,7 @@ int sched_rt_handler(struct ctl_table *table, int write,
 			def_rt_bandwidth.rt_runtime = global_rt_runtime();
 			def_rt_bandwidth.rt_period =
 				ns_to_ktime(global_rt_period());
+			sched_rt_update_bandwidth();
 		}
 	}
 	mutex_unlock(&mutex);
kernel/sched_rt.c +259 -21

334 lines not on this page · raw message

Signature · 1 line
1.6.5.7
maintainer
#5 lore raw

Re: [PATCH 2/3] sched: enforce per-cpu utilization limits on runtime balancing

Quoted 29 lines · Fabio Checconi
kernel/sched_rt.c +29 -0
+static u64 from_ratio(unsigned long ratio, u64 period)
+{
+       return (ratio * period) >> 20;
+}
+
+/*
+ * Try to move *diff units of runtime from src to dst, checking
+ * that the utilization does not exceed the global limits on the
+ * destination cpu.  Returns true if the migration succeeded, leaving
+ * in *diff the actual amount of runtime moved, false on failure, which
+ * means that no more bandwidth can be migrated to rt_rq.
+ */
+static int rt_move_bw(struct rt_rq *src, struct rt_rq *dst,
+                      s64 *diff, u64 rt_period)
+{
+       struct rq *rq = rq_of_rt_rq(dst), *src_rq = rq_of_rt_rq(src);
+       struct rt_edf_tree *dtree = &rq->rt.rt_edf_tree;
+       struct rt_edf_tree *stree = &src_rq->rt.rt_edf_tree;
+       unsigned long bw_to_move;
+       int ret = 0;
+
+       double_spin_lock(&dtree->rt_bw_lock, &stree->rt_bw_lock);
+
+       if (dtree->rt_free_bw) {
+               bw_to_move = to_ratio(rt_period, *diff);
+               if (bw_to_move > dtree->rt_free_bw) {
+                       bw_to_move = dtree->rt_free_bw;
+                       *diff = from_ratio(bw_to_move, rt_period);
+               }

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 534

Quoted 10 lines
kernel/sched_rt.c +10 -0
+
+               stree->rt_free_bw -= bw_to_move;
+               dtree->rt_free_bw += bw_to_move;
+               ret = 1;
+       }
+
+       double_spin_unlock(&dtree->rt_bw_lock, &stree->rt_bw_lock);
+
+       return ret;
+} 

The from_ratio() stuff smells like numerical instability for ->rt_free_bw, I can't see anything that would, given sufficient balance cycles keep the sum of rt_free_bw over the cpus equal to what it started out with.

#6 lore raw

Re: [PATCH 2/3] sched: enforce per-cpu utilization limits on runtime balancing

Quoted 40 lines

From: Peter Zijlstra <[email protected]>
Date: Thu, Feb 25, 2010 09:28:25PM +0100

Quoted 36 lines · Fabio Checconi
kernel/sched_rt.c +36 -0
+static u64 from_ratio(unsigned long ratio, u64 period)
+{
+       return (ratio * period) >> 20;
+}
+
+/*
+ * Try to move *diff units of runtime from src to dst, checking
+ * that the utilization does not exceed the global limits on the
+ * destination cpu.  Returns true if the migration succeeded, leaving
+ * in *diff the actual amount of runtime moved, false on failure, which
+ * means that no more bandwidth can be migrated to rt_rq.
+ */
+static int rt_move_bw(struct rt_rq *src, struct rt_rq *dst,
+                      s64 *diff, u64 rt_period)
+{
+       struct rq *rq = rq_of_rt_rq(dst), *src_rq = rq_of_rt_rq(src);
+       struct rt_edf_tree *dtree = &rq->rt.rt_edf_tree;
+       struct rt_edf_tree *stree = &src_rq->rt.rt_edf_tree;
+       unsigned long bw_to_move;
+       int ret = 0;
+
+       double_spin_lock(&dtree->rt_bw_lock, &stree->rt_bw_lock);
+
+       if (dtree->rt_free_bw) {
+               bw_to_move = to_ratio(rt_period, *diff);
+               if (bw_to_move > dtree->rt_free_bw) {
+                       bw_to_move = dtree->rt_free_bw;
+                       *diff = from_ratio(bw_to_move, rt_period);
+               }
+
+               stree->rt_free_bw -= bw_to_move;
+               dtree->rt_free_bw += bw_to_move;
+               ret = 1;
+       }
+
+       double_spin_unlock(&dtree->rt_bw_lock, &stree->rt_bw_lock);
Quoted 8 lines

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 534

Quoted 3 lines
kernel/sched_rt.c +3 -0
+
+       return ret;
+} 

The from_ratio() stuff smells like numerical instability for ->rt_free_bw, I can't see anything that would, given sufficient balance cycles keep the sum of rt_free_bw over the cpus equal to what it started out with.

You're right... What would you think about the following solution? It just keep tracks of the bw accounted for every rt_rq when it is updated, and that should be enough to avoid accumulating the errors.

static inline void rt_update_bw(struct rt_rq *rt_rq, struct rt_edf_tree *tree,

                                s64 diff, u64 rt_period)
{       
	unsigned long bw;

	rt_rq->rt_runtime += diff;
	bw = to_ratio(rt_period, rt_rq->rt_runtime);
	tree->rt_free_bw += bw - rt_rq->rt_bw;
	rt_rq->rt_bw = bw;
}

static bool rt_move_bw(struct rt_rq *src, struct rt_rq *dst,

		       s64 *diff, u64 rt_period)
{
	struct rq *rq = rq_of_rt_rq(dst), *src_rq = rq_of_rt_rq(src);
	struct rt_edf_tree *dtree = &rq->rt.rt_edf_tree;
	struct rt_edf_tree *stree = &src_rq->rt.rt_edf_tree;
	unsigned long bw_to_move;
	bool ret = false;

	double_spin_lock(&dtree->rt_bw_lock, &stree->rt_bw_lock);

	if (dtree->rt_free_bw) {
		bw_to_move = to_ratio(rt_period, *diff);
		if (bw_to_move > dtree->rt_free_bw)
			*diff = from_ratio(dtree->rt_free_bw, rt_period);

		if (*diff) {
			rt_update_bw(src, stree, -(*diff), rt_period);
			rt_update_bw(dst, dtree, *diff, rt_period);

			ret = true;
		}
	}

	double_spin_unlock(&dtree->rt_bw_lock, &stree->rt_bw_lock);

	return ret;
}
maintainer
#7 lore raw

Re: [PATCH 2/3] sched: enforce per-cpu utilization limits on runtime balancing

Quoted 84 lines · Fabio Checconi
Quoted 40 lines

From: Peter Zijlstra <[email protected]>
Date: Thu, Feb 25, 2010 09:28:25PM +0100

Quoted 36 lines · Fabio Checconi
kernel/sched_rt.c +36 -0
+static u64 from_ratio(unsigned long ratio, u64 period)
+{
+       return (ratio * period) >> 20;
+}
+
+/*
+ * Try to move *diff units of runtime from src to dst, checking
+ * that the utilization does not exceed the global limits on the
+ * destination cpu.  Returns true if the migration succeeded, leaving
+ * in *diff the actual amount of runtime moved, false on failure, which
+ * means that no more bandwidth can be migrated to rt_rq.
+ */
+static int rt_move_bw(struct rt_rq *src, struct rt_rq *dst,
+                      s64 *diff, u64 rt_period)
+{
+       struct rq *rq = rq_of_rt_rq(dst), *src_rq = rq_of_rt_rq(src);
+       struct rt_edf_tree *dtree = &rq->rt.rt_edf_tree;
+       struct rt_edf_tree *stree = &src_rq->rt.rt_edf_tree;
+       unsigned long bw_to_move;
+       int ret = 0;
+
+       double_spin_lock(&dtree->rt_bw_lock, &stree->rt_bw_lock);
+
+       if (dtree->rt_free_bw) {
+               bw_to_move = to_ratio(rt_period, *diff);
+               if (bw_to_move > dtree->rt_free_bw) {
+                       bw_to_move = dtree->rt_free_bw;
+                       *diff = from_ratio(bw_to_move, rt_period);
+               }
+
+               stree->rt_free_bw -= bw_to_move;
+               dtree->rt_free_bw += bw_to_move;
+               ret = 1;
+       }
+
+       double_spin_unlock(&dtree->rt_bw_lock, &stree->rt_bw_lock);
Quoted 8 lines

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 534

Quoted 3 lines
kernel/sched_rt.c +3 -0
+
+       return ret;
+} 

The from_ratio() stuff smells like numerical instability for ->rt_free_bw, I can't see anything that would, given sufficient balance cycles keep the sum of rt_free_bw over the cpus equal to what it started out with.

You're right... What would you think about the following solution? It just keep tracks of the bw accounted for every rt_rq when it is updated, and that should be enough to avoid accumulating the errors.

static inline void rt_update_bw(struct rt_rq *rt_rq, struct rt_edf_tree *tree,

                                s64 diff, u64 rt_period)
{       
	unsigned long bw;

	rt_rq->rt_runtime += diff;
	bw = to_ratio(rt_period, rt_rq->rt_runtime);
	tree->rt_free_bw += bw - rt_rq->rt_bw;
	rt_rq->rt_bw = bw;
}

static bool rt_move_bw(struct rt_rq *src, struct rt_rq *dst,

		       s64 *diff, u64 rt_period)
{
	struct rq *rq = rq_of_rt_rq(dst), *src_rq = rq_of_rt_rq(src);
	struct rt_edf_tree *dtree = &rq->rt.rt_edf_tree;
	struct rt_edf_tree *stree = &src_rq->rt.rt_edf_tree;
	unsigned long bw_to_move;
	bool ret = false;

	double_spin_lock(&dtree->rt_bw_lock, &stree->rt_bw_lock);

	if (dtree->rt_free_bw) {
		bw_to_move = to_ratio(rt_period, *diff);
		if (bw_to_move > dtree->rt_free_bw)
			*diff = from_ratio(dtree->rt_free_bw, rt_period);

		if (*diff) {
			rt_update_bw(src, stree, -(*diff), rt_period);
			rt_update_bw(dst, dtree, *diff, rt_period);
Quoted 8 lines
			ret = true;
		}
	}

	double_spin_unlock(&dtree->rt_bw_lock, &stree->rt_bw_lock);

	return ret;
}

OK, I think that should work, add a little comment on why we're doing it this way and all should be well ;-)

maintainer
#8 lore raw

Re: [PATCH 2/3] sched: enforce per-cpu utilization limits on runtime balancing

In reply to Fabio Checconi

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 459

Quoted 5 lines · Fabio Checconi
kernel/sched_rt.c +5 -0
+               /*
+                * Make sure that before restarting balancing everyone
+                * sees the new free bandwidth.
+                */
+               smp_wmb(); 

You cannot order something on its own, barriers come in pairs, where is his?

#9 lore raw

Re: [PATCH 2/3] sched: enforce per-cpu utilization limits on runtime balancing

Quoted 4 lines

From: Peter Zijlstra <[email protected]>
Date: Thu, Feb 25, 2010 09:28:22PM +0100

On Tue, 2010-02-23 at 19:56 +0100, Fabio Checconi wrote:

Quoted 8 lines

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 459

Quoted 5 lines
kernel/sched_rt.c +5 -0
+               /*
+                * Make sure that before restarting balancing everyone
+                * sees the new free bandwidth.
+                */
+               smp_wmb(); 

You cannot order something on its own, barriers come in pairs, where is his?

It was coupled with the acquire barrier implied by the spin_lock(rt_b) in the balance path, as the other wmb() before starting the reset (more details on the reply about this last barrier, as per your comment they can be removed).

maintainer
#10 lore raw

Re: [PATCH 2/3] sched: enforce per-cpu utilization limits on runtime balancing

In reply to Fabio Checconi
Quoted 58 lines · Fabio Checconi

/*
+ * Reset the balancing machinery, restarting from a safe runtime assignment
+ * on all the cpus/rt_rqs in the system. There is room for improvements here,
+ * as this iterates through all the rt_rqs in the system; the main problem
+ * is that after the balancing has been running for some time we are not
+ * sure that the fragmentation of the free bandwidth it produced allows new
+ * groups to run where they need to run. The caller has to make sure that
+ * only one instance of this function is running at any time.
*/

kernel/sched_rt.c +46 -0
+static void __rt_reset_runtime(void)
 {
+       struct rq *rq;
+       struct rt_rq *rt_rq;
+       struct rt_bandwidth *rt_b;
+       unsigned long flags;
+       int i;
+
+       for_each_possible_cpu(i) {
+               rq = cpu_rq(i);
+
+               rq->rt_balancing_disabled = 1;
+               /*
+                * Make sure that all the new calls to do_balance_runtime()
+                * see the disable flag and do not migrate anything.  We will
+                * implicitly wait for the old ones to terminate entering all
+                * the rt_b->rt_runtime_lock, one by one.  Note that maybe
+                * iterating over the task_groups first would be a good idea...
+                */
+               smp_wmb();
+
+               for_each_leaf_rt_rq(rt_rq, rq) {
+                       rt_b = sched_rt_bandwidth(rt_rq);
+
+                       raw_spin_lock_irqsave(&rt_b->rt_runtime_lock, flags);
+                       raw_spin_lock(&rt_rq->rt_runtime_lock);
+                       rt_rq->rt_runtime = rt_b->rt_runtime;
+                       rt_rq->rt_period = rt_b->rt_period;
+                       rt_rq->rt_time = 0;
+                       raw_spin_unlock(&rt_rq->rt_runtime_lock);
+                       raw_spin_unlock_irqrestore(&rt_b->rt_runtime_lock, flags);
+               }
+       }
+}
 
 
+/*
+ * Handle runtime rebalancing: try to push our bandwidth to
+ * runqueues that need it.
+ */
+static void do_balance_runtime(struct rt_rq *rt_rq)
+{
+       struct rq *rq = cpu_rq(smp_processor_id());
+       struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
+       struct root_domain *rd = rq->rd;
+       int i, weight, ret;
+       u64 rt_period, prev_runtime;
+       s64 diff;
+

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 558

Quoted 10 lines
kernel/sched_rt.c +7 -0
        weight = cpumask_weight(rd->span);
 
        raw_spin_lock(&rt_b->rt_runtime_lock);
+       /*
+        * The raw_spin_lock() acts as an acquire barrier, ensuring
+        * that rt_balancing_disabled is accessed after taking the lock;
+        * since rt_reset_runtime() takes rt_runtime_lock after
+        * setting the disable flag we are sure that no bandwidth
+        * is migrated while the reset is in progress.
+        */

Note that LOCK != {RMB,MB}, what you can do is order the WMB with the UNLOCK+LOCK (== MB).

I'm thinking the WMB above is superfluous, either we are already in do_balance() and __rt_reset_runtime() will wait for us, or __rt_reset_runtime() will have done a LOCK+UNLOCK between setting ->rt_balancing_disabled here and we'll have done a LOCK before the read.

So we always have at least store+UNLOCK+LOCK+load, which can never be reordered.

IOW, look at it as if the store leaks into the rt_b->rt_runtime_lock section, in that case that lock properly serializes the store and these loads.

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 560

Quoted 2 lines
kernel/sched_rt.c +2 -0
+       if (rq->rt_balancing_disabled)
+               goto out;

( maybe call that label unlock )

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 570

Quoted 10 lines
kernel/sched_rt.c +4 -0
+
+       prev_runtime = rt_rq->rt_runtime;
        rt_period = ktime_to_ns(rt_b->rt_period);
+
        for_each_cpu(i, rd->span) {
                struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
+               struct rq *iter_rq = rq_of_rt_rq(iter);
 
                if (iter == rt_rq)
                        continue;

Idem to the above ordering.

Quoted 6 lines
kernel/sched_rt.c +3 -0
+               if (iter_rq->rt_balancing_disabled)
+                       continue;
+
                raw_spin_lock(&iter->rt_runtime_lock);
                /*
                 * Either all rqs have inf runtime and there's nothing to steal 
#11 lore raw

Re: [PATCH 2/3] sched: enforce per-cpu utilization limits on runtime balancing

Quoted 82 lines

From: Peter Zijlstra <[email protected]>
Date: Thu, Feb 25, 2010 09:28:28PM +0100

Quoted 58 lines · Fabio Checconi

/*
+ * Reset the balancing machinery, restarting from a safe runtime assignment
+ * on all the cpus/rt_rqs in the system. There is room for improvements here,
+ * as this iterates through all the rt_rqs in the system; the main problem
+ * is that after the balancing has been running for some time we are not
+ * sure that the fragmentation of the free bandwidth it produced allows new
+ * groups to run where they need to run. The caller has to make sure that
+ * only one instance of this function is running at any time.
*/

kernel/sched_rt.c +46 -0
+static void __rt_reset_runtime(void)
 {
+       struct rq *rq;
+       struct rt_rq *rt_rq;
+       struct rt_bandwidth *rt_b;
+       unsigned long flags;
+       int i;
+
+       for_each_possible_cpu(i) {
+               rq = cpu_rq(i);
+
+               rq->rt_balancing_disabled = 1;
+               /*
+                * Make sure that all the new calls to do_balance_runtime()
+                * see the disable flag and do not migrate anything.  We will
+                * implicitly wait for the old ones to terminate entering all
+                * the rt_b->rt_runtime_lock, one by one.  Note that maybe
+                * iterating over the task_groups first would be a good idea...
+                */
+               smp_wmb();
+
+               for_each_leaf_rt_rq(rt_rq, rq) {
+                       rt_b = sched_rt_bandwidth(rt_rq);
+
+                       raw_spin_lock_irqsave(&rt_b->rt_runtime_lock, flags);
+                       raw_spin_lock(&rt_rq->rt_runtime_lock);
+                       rt_rq->rt_runtime = rt_b->rt_runtime;
+                       rt_rq->rt_period = rt_b->rt_period;
+                       rt_rq->rt_time = 0;
+                       raw_spin_unlock(&rt_rq->rt_runtime_lock);
+                       raw_spin_unlock_irqrestore(&rt_b->rt_runtime_lock, flags);
+               }
+       }
+}
 
 
+/*
+ * Handle runtime rebalancing: try to push our bandwidth to
+ * runqueues that need it.
+ */
+static void do_balance_runtime(struct rt_rq *rt_rq)
+{
+       struct rq *rq = cpu_rq(smp_processor_id());
+       struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
+       struct root_domain *rd = rq->rd;
+       int i, weight, ret;
+       u64 rt_period, prev_runtime;
+       s64 diff;
+

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 558

Quoted 10 lines
kernel/sched_rt.c +7 -0
        weight = cpumask_weight(rd->span);
 
        raw_spin_lock(&rt_b->rt_runtime_lock);
+       /*
+        * The raw_spin_lock() acts as an acquire barrier, ensuring
+        * that rt_balancing_disabled is accessed after taking the lock;
+        * since rt_reset_runtime() takes rt_runtime_lock after
+        * setting the disable flag we are sure that no bandwidth
+        * is migrated while the reset is in progress.
+        */

Note that LOCK != {RMB,MB}, what you can do is order the WMB with the UNLOCK+LOCK (== MB).

I'm thinking the WMB above is superfluous, either we are already in do_balance() and __rt_reset_runtime() will wait for us, or __rt_reset_runtime() will have done a LOCK+UNLOCK between setting ->rt_balancing_disabled here and we'll have done a LOCK before the read.

Quoted 7 lines

So we always have at least store+UNLOCK+LOCK+load, which can never be reordered.

IOW, look at it as if the store leaks into the rt_b->rt_runtime_lock section, in that case that lock properly serializes the store and these loads.

The barrier can be removed. Unfortunately the comments were not clear at all; what I wanted to do was ensuring that *all* the bw balance operations be stopped before the first loop in the reset path. So I did not need a full memory barrier in do_balance_runtime(), but the acquire barrier implied by the spin_lock() (paired with the wmb() in the reset path), was enough to prevent any new balancing op from moving bandwidth.

As you noticed, after the first reset loop a full mb() will be implied by the lock+unlock sequence, so removing the wmb() would relax the synchronisation constraints, theoretically allowing some balancing operations to be started while the first reset loop is being executed. Since no balancing operation will affect rt_b's already traversed by the reset loop everything should be safe, so I'll remove the wmb().

The wmb() in __rt_restart_balancing() was needed for the same reason, when reenabling balancing, so it too can be removed.

Quoted 5 lines

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 560

Quoted 2 lines
kernel/sched_rt.c +2 -0
+       if (rq->rt_balancing_disabled)
+               goto out;

( maybe call that label unlock )

Will do,

Thank you!

Quoted 21 lines

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 570

Quoted 10 lines
kernel/sched_rt.c +4 -0
+
+       prev_runtime = rt_rq->rt_runtime;
        rt_period = ktime_to_ns(rt_b->rt_period);
+
        for_each_cpu(i, rd->span) {
                struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
+               struct rq *iter_rq = rq_of_rt_rq(iter);
 
                if (iter == rt_rq)
                        continue;

Idem to the above ordering.

Quoted 6 lines
kernel/sched_rt.c +3 -0
+               if (iter_rq->rt_balancing_disabled)
+                       continue;
+
                raw_spin_lock(&iter->rt_runtime_lock);
                /*
                 * Either all rqs have inf runtime and there's nothing to steal 
maintainer
#12 lore raw

Re: [PATCH 2/3] sched: enforce per-cpu utilization limits on runtime balancing

In reply to Fabio Checconi
Quoted 13 lines · Fabio Checconi
kernel/sched_rt.c +13 -0
+static inline void double_spin_lock(raw_spinlock_t *lock1,
+                                   raw_spinlock_t *lock2)
+       __acquires(lock1)
+       __acquires(lock2)
+{
+       if (lock1 < lock2) {
+               raw_spin_lock(lock1);
+               raw_spin_lock_nested(lock2, SINGLE_DEPTH_NESTING);
+       } else {
+               raw_spin_lock(lock2);
+               raw_spin_lock_nested(lock1, SINGLE_DEPTH_NESTING);
+       }
+}

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 494

Quoted 10 lines
kernel/sched_rt.c +10 -0
+
+static inline void double_spin_unlock(raw_spinlock_t *lock1,
+                                     raw_spinlock_t *lock2)
+       __releases(lock1)
+       __releases(lock2)
+{
+       raw_spin_unlock(lock1);
+       lock_set_subclass(&lock2->dep_map, 0, _RET_IP_);
+       raw_spin_unlock(lock2);
+} 

If you release both there is no need to re-set the subclass.

#13 lore raw

Re: [PATCH 2/3] sched: enforce per-cpu utilization limits on runtime balancing

Quoted 21 lines

From: Peter Zijlstra <[email protected]>
Date: Thu, Feb 25, 2010 09:28:24PM +0100

Quoted 17 lines · Fabio Checconi
kernel/sched_rt.c +17 -0
+static inline void double_spin_lock(raw_spinlock_t *lock1,
+                                   raw_spinlock_t *lock2)
+       __acquires(lock1)
+       __acquires(lock2)
+{
+       if (lock1 < lock2) {
+               raw_spin_lock(lock1);
+               raw_spin_lock_nested(lock2, SINGLE_DEPTH_NESTING);
+       } else {
+               raw_spin_lock(lock2);
+               raw_spin_lock_nested(lock1, SINGLE_DEPTH_NESTING);
+       }
+}
+
+static inline void double_spin_unlock(raw_spinlock_t *lock1,
+                                     raw_spinlock_t *lock2)
+       __releases(lock1)
Quoted 8 lines

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 494

Quoted 6 lines
kernel/sched_rt.c +6 -0
+       __releases(lock2)
+{
+       raw_spin_unlock(lock1);
+       lock_set_subclass(&lock2->dep_map, 0, _RET_IP_);
+       raw_spin_unlock(lock2);
+} 

If you release both there is no need to re-set the subclass.

Will fix, thanks.

maintainer
#14 lore raw

Re: [PATCH 2/3] sched: enforce per-cpu utilization limits on runtime balancing

In reply to Fabio Checconi
Quoted 9 lines · Fabio Checconi
kernel/sched_rt.c +8 -0
+#ifdef CONFIG_SMP
+static inline unsigned long rt_init_free_bw(void)
+{
+       unsigned long used = to_ratio(global_rt_period(), global_rt_runtime());
+
+       return to_ratio(RUNTIME_INF, RUNTIME_INF) - used;
+}
+#endif
 

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 444

Quoted 10 lines
kernel/sched_rt.c +10 -0
+static void __rt_restart_balancing(void)
+{
+       unsigned long used, global, free;
+       struct rq *rq;
+       int i;
+
+       used = rt_used_bandwidth();
+       global = to_ratio(RUNTIME_INF, RUNTIME_INF);
+
+       free = global - used;

We take the max as RUNTIME_INF instead of global_rt_* so that we can move runtime around and fully saturate a single cpu (given there is enough free to compensate on other cpus) ?

#15 lore raw

Re: [PATCH 2/3] sched: enforce per-cpu utilization limits on runtime balancing

Quoted 13 lines

From: Peter Zijlstra <[email protected]>
Date: Thu, Feb 25, 2010 09:28:23PM +0100

Quoted 8 lines · Fabio Checconi
kernel/sched.c +8 -0
+#ifdef CONFIG_SMP
+static inline unsigned long rt_init_free_bw(void)
+{
+       unsigned long used = to_ratio(global_rt_period(), global_rt_runtime());
+
+       return to_ratio(RUNTIME_INF, RUNTIME_INF) - used;
+}
+#endif
Quoted 15 lines

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 444

Quoted 10 lines
kernel/sched_rt.c +10 -0
+static void __rt_restart_balancing(void)
+{
+       unsigned long used, global, free;
+       struct rq *rq;
+       int i;
+
+       used = rt_used_bandwidth();
+       global = to_ratio(RUNTIME_INF, RUNTIME_INF);
+
+       free = global - used;

We take the max as RUNTIME_INF instead of global_rt_* so that we can move runtime around and fully saturate a single cpu (given there is enough free to compensate on other cpus) ?

The only reason I've used RUNTIME_INF instead of global_rt_* is for the !GROUP_SCHED case, where using the global_rt_* values would make balancing have no effect at all (the initial value for def_rt_bandwidth already uses the maximum bw on each cpu) . The current throttling implementation in this case still tries to concentrate bw on a single cpu, and I wanted to replicate the same behaviour.

Should I go for the global_rt_* values and add some #ifdef unreadability to avoid the balancing overhead in the !GROUP_SCHED case?

maintainer
#16 lore raw

Re: [PATCH 2/3] sched: enforce per-cpu utilization limits on runtime balancing

Quoted 36 lines · Fabio Checconi
Quoted 13 lines

From: Peter Zijlstra <[email protected]>
Date: Thu, Feb 25, 2010 09:28:23PM +0100

Quoted 8 lines · Fabio Checconi
kernel/sched.c +8 -0
+#ifdef CONFIG_SMP
+static inline unsigned long rt_init_free_bw(void)
+{
+       unsigned long used = to_ratio(global_rt_period(), global_rt_runtime());
+
+       return to_ratio(RUNTIME_INF, RUNTIME_INF) - used;
+}
+#endif
Quoted 15 lines

kernel/sched_rt.c static inline int rt_time_before(u64 a, u64 b) · line 444

Quoted 10 lines
kernel/sched_rt.c +10 -0
+static void __rt_restart_balancing(void)
+{
+       unsigned long used, global, free;
+       struct rq *rq;
+       int i;
+
+       used = rt_used_bandwidth();
+       global = to_ratio(RUNTIME_INF, RUNTIME_INF);
+
+       free = global - used;

We take the max as RUNTIME_INF instead of global_rt_* so that we can move runtime around and fully saturate a single cpu (given there is enough free to compensate on other cpus) ?

The only reason I've used RUNTIME_INF instead of global_rt_* is for the !GROUP_SCHED case, where using the global_rt_* values would make balancing have no effect at all (the initial value for def_rt_bandwidth already uses the maximum bw on each cpu) . The current throttling implementation in this case still tries to concentrate bw on a single cpu, and I wanted to replicate the same behaviour.

Quoted 2 lines

Should I go for the global_rt_* values and add some #ifdef unreadability to avoid the balancing overhead in the !GROUP_SCHED case?

Nah, but adding a comment to clarify this might help.. I only asked because it was not immediately obvious.

#17 lore raw

PATCH 3/3 sched: make runtime balancing code more EDF-friendly

In reply to Fabio Checconi

The old runtime balancing code logic does not work too well when using EDF to schedule runqueues. One of the problems is that the old throttling code had only one timer to handle budget replenishments; EDF needs per-cpu timers, not in sync among themselves.

This patch changes balance_runtime() to work in push or pull mode: 1) when an rt_rq needs extra runtime, it tries to borrow it from its siblings, and
2) when an rt_rq has some borroewed runtime, it tries to distribute it among the rt_rq's needing it. This change improves things a little bit, making easier to redistribute bandwidth when the load on the various rt_rq's changes; anyway this is far from being an optimal solution. I think we need (intependently from this patchset) to make the balancing logic cooperate with (or at least aware of) task push/pulls and define more formally the objectives of the runtime migration policy.

---
 kernel/sched_rt.c |  152 ++++++++++++++++++++++++++++++++++++++++-------------
 1 files changed, 116 insertions(+), 36 deletions(-)
kernel/sched_rt.c +116 -36
index 27768bd..fa0ad58 100644
@@ -498,6 +498,20 @@ static u64 from_ratio(unsigned long ratio, u64 period)
 	return (ratio * period) >> 20;
 }
 
+static inline bool runtime_push_needed(struct rt_rq *src, struct rt_rq *dst)
+{
+	if (!rt_rq_throttled(dst))
+		return false;
+
+	if (!dst->rt_nr_running)
+		return false;
+
+	if (src->rt_runtime <= dst->rt_runtime)
+		return false;
+
+	return true;
+}
+
 /*
  * Try to move *diff units of runtime from src to dst, checking
  * that the utilization does not exceed the global limits on the
@@ -505,14 +519,14 @@ static u64 from_ratio(unsigned long ratio, u64 period)
  * in *diff the actual amount of runtime moved, false on failure, which
  * means that no more bandwidth can be migrated to rt_rq.
  */
-static int rt_move_bw(struct rt_rq *src, struct rt_rq *dst,
+static bool rt_move_bw(struct rt_rq *src, struct rt_rq *dst,
 		       s64 *diff, u64 rt_period)
 {
 	struct rq *rq = rq_of_rt_rq(dst), *src_rq = rq_of_rt_rq(src);
 	struct rt_edf_tree *dtree = &rq->rt.rt_edf_tree;
 	struct rt_edf_tree *stree = &src_rq->rt.rt_edf_tree;
 	unsigned long bw_to_move;
-	int ret = 0;
+	bool ret = false;
 
 	double_spin_lock(&dtree->rt_bw_lock, &stree->rt_bw_lock);
 
@@ -525,7 +539,7 @@ static int rt_move_bw(struct rt_rq *src, struct rt_rq *dst,
 
 		stree->rt_free_bw -= bw_to_move;
 		dtree->rt_free_bw += bw_to_move;
-		ret = 1;
+		ret = true;
 	}
 
 	double_spin_unlock(&dtree->rt_bw_lock, &stree->rt_bw_lock);
@@ -533,18 +547,85 @@ static int rt_move_bw(struct rt_rq *src, struct rt_rq *dst,
 	return ret;
 }
 
+static inline bool stop_runtime_balancing(bool pull, bool moved, s64 diff)
+{
+	if (pull && !moved) {
+		/* No more available bw on our cpu while pulling. */
+		return true;
+	}
+
+	if (!pull && diff < 0) {
+		/* No more bandwidth to give back while pushing. */
+		return true;
+	}
+
+	return false;
+}
+
 /*
- * Handle runtime rebalancing: try to push our bandwidth to
- * runqueues that need it.
+ * Try to move runtime between rt_rq and iter, in the direction specified
+ * by pull.  Return true if balancing should stop.
  */
-static void do_balance_runtime(struct rt_rq *rt_rq)
+static inline bool move_runtime(struct rt_rq *rt_rq, struct rt_rq *iter,
+			       int weight, u64 rt_period, bool pull)
+{
+	struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
+	struct rt_rq *src, *dst;
+	u64 leave;
+	s64 diff = 0;
+	bool moved = true;
+
+	if (pull) {
+		/*
+		 * From runqueues with spare time, take 1/n part of their
+		 * spare time, but no more than our period.  In case we are
+		 * stealing from an active rt_rq, make sure we steal only
+		 * from the runtime it borrowed, to avoid instability.
+		 */
+		if (iter->rt_nr_running)
+			leave = max(rt_b->rt_runtime, iter->rt_time);
+		else
+			leave = iter->rt_time;
+		diff = iter->rt_runtime - leave;
+		src = iter;
+		dst = rt_rq;
+	} else if (runtime_push_needed(rt_rq, iter)) {
+		/*
+		 * Try to give 1/n part of our borrowed runtime to the
+		 * runqueues needing it.
+		 */
+		diff = rt_rq->rt_runtime - rt_rq->rt_time - rt_b->rt_runtime;
+		src = rt_rq;
+		dst = iter;
+	}
+
+	if (diff > 0) {
+		diff = div_u64((u64)diff, weight);
+		if (dst->rt_runtime + diff > rt_period)
+			diff = rt_period - dst->rt_runtime;
+
+		moved = rt_move_bw(src, dst, &diff, rt_period);
+		if (moved) {
+			src->rt_runtime -= diff;
+			dst->rt_runtime += diff;
+		}
+	}
+
+	return stop_runtime_balancing(pull, moved, diff);
+}
+
+/*
+ * Handle runtime rebalancing: either try to push our bandwidth to
+ * runqueues that need it, or pull from those that can lend some.
+ */
+static void do_balance_runtime(struct rt_rq *rt_rq, bool pull)
 {
 	struct rq *rq = cpu_rq(smp_processor_id());
 	struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
 	struct root_domain *rd = rq->rd;
-	int i, weight, ret;
+	int i, weight;
 	u64 rt_period, prev_runtime;
-	s64 diff;
+	bool stop;
 
 	weight = cpumask_weight(rd->span);
 
@@ -581,26 +662,10 @@ static void do_balance_runtime(struct rt_rq *rt_rq)
 		if (iter->rt_runtime == RUNTIME_INF)
 			goto next;
 
-		/*
-		 * From runqueues with spare time, take 1/n part of their
-		 * spare time, but no more than our period.
-		 */
-		diff = iter->rt_runtime - iter->rt_time;
-		if (diff > 0) {
-			diff = div_u64((u64)diff, weight);
-			if (rt_rq->rt_runtime + diff > rt_period)
-				diff = rt_period - rt_rq->rt_runtime;
-
-			ret = rt_move_bw(iter, rt_rq, &diff, rt_period);
-			if (ret) {
-				iter->rt_runtime -= diff;
-				rt_rq->rt_runtime += diff;
-			}
-
-			if (!ret || rt_rq->rt_runtime == rt_period) {
-				raw_spin_unlock(&iter->rt_runtime_lock);
-				break;
-			}
+		stop = move_runtime(rt_rq, iter, weight, rt_period, pull);
+		if (stop) {
+			raw_spin_unlock(&iter->rt_runtime_lock);
+			break;
 		}
 next:
 		raw_spin_unlock(&iter->rt_runtime_lock);
@@ -756,16 +821,27 @@ static void enable_runtime(struct rq *rq)
 	raw_spin_unlock_irqrestore(&rq->lock, flags);
 }
 
-static inline void balance_runtime(struct rt_rq *rt_rq)
+static inline void balance_runtime(struct rt_rq *rt_rq, int pull)
 {
-	if (rt_rq->rt_time > rt_rq->rt_runtime) {
-		raw_spin_unlock(&rt_rq->rt_runtime_lock);
-		do_balance_runtime(rt_rq);
-		raw_spin_lock(&rt_rq->rt_runtime_lock);
-	}
+	raw_spin_unlock(&rt_rq->rt_runtime_lock);
+	do_balance_runtime(rt_rq, pull);
+	raw_spin_lock(&rt_rq->rt_runtime_lock);
 }
 
+static void pull_runtime(struct rt_rq *rt_rq)
+{
+	if (rt_rq->rt_time > rt_rq->rt_runtime)
+		balance_runtime(rt_rq, true);
+}
+
+static void push_runtime(struct rt_rq *rt_rq)
+{
+	if (rt_rq->rt_time < rt_rq->rt_runtime)
+		balance_runtime(rt_rq, false);
+}
 #else /* !CONFIG_SMP */
+static inline void pull_runtime(struct rt_rq *rt_rq) {}
+static inline void push_runtime(struct rt_rq *rt_rq) {}
 
 static void rt_reset_runtime(void)
 {
@@ -828,6 +904,9 @@ static int __do_sched_rt_period_timer(struct rt_rq *rt_rq, int overrun)
 	} else if (rt_rq->rt_nr_running)
 		idle = 0;
 
+	/* Try to give back what we borrowed from rt_rq's in need. */
+	push_runtime(rt_rq);
+
 	return idle && !rt_rq_needs_recharge(rt_rq);
 }
 
@@ -843,7 +922,7 @@ static int do_sched_rt_period_timer(struct rt_rq *rt_rq, int overrun)
 	raw_spin_lock(&rt_rq->rt_runtime_lock);
 
 	if (rt_rq->rt_throttled)
-		balance_runtime(rt_rq);
+		pull_runtime(rt_rq);
 
 	idle = __do_sched_rt_period_timer(rt_rq, overrun);
 
@@ -919,7 +998,7 @@ static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq)
 	if (sched_rt_runtime(rt_rq) >= sched_rt_period(rt_rq))
 		return 0;
 
-	balance_runtime(rt_rq);
+	pull_runtime(rt_rq);
 	runtime = sched_rt_runtime(rt_rq);
 	if (runtime == RUNTIME_INF)
 		return 0;
@@ -1261,6 +1340,7 @@ update:
 			rt_rq->rt_deadline += period;
 			rt_rq->rt_time -= runtime;
 		}
+		push_runtime(rt_rq);
 	}
 	raw_spin_unlock(&rt_rq->rt_runtime_lock);
 }
Signature · 1 line
1.6.5.7
maintainer
#18 lore raw

Re: [PATCH 3/3] sched: make runtime balancing code more EDF-friendly

kernel/sched_rt.c static void do_balance_runtime(struct rt_rq *rt_rq) · line 671

Quoted 8 lines · Fabio Checconi

+ stop = move_runtime(rt_rq, iter, weight, rt_period,
pull);

kernel/sched_rt.c +3 -0
+               if (stop) {
+                       raw_spin_unlock(&iter->rt_runtime_lock);
+                       break;
                }
 next:
                raw_spin_unlock(&iter->rt_runtime_lock); 

might as well put that:

if (stop)

    break;

right after the raw_spin_unlock() that's already there.

#19 lore raw

Re: [PATCH 3/3] sched: make runtime balancing code more EDF-friendly

Quoted 13 lines

From: Peter Zijlstra <[email protected]>
Date: Thu, Feb 25, 2010 09:28:26PM +0100

kernel/sched_rt.c static void do_balance_runtime(struct rt_rq *rt_rq) · line 671

Quoted 8 lines · Fabio Checconi

+ stop = move_runtime(rt_rq, iter, weight, rt_period,
pull);

kernel/sched_rt.c +3 -0
+               if (stop) {
+                       raw_spin_unlock(&iter->rt_runtime_lock);
+                       break;
                }
 next:
                raw_spin_unlock(&iter->rt_runtime_lock); 
Quoted 6 lines

might as well put that:

if (stop)

    break;

right after the raw_spin_unlock() that's already there.

Will do (initializing stop to false before entering the loop), thanks.

maintainer
#20 lore raw
In reply to Fabio Checconi
Quoted 35 lines · Fabio Checconi

This patchset introduces a group level EDF scheduler extending the throttling mechanism, in order to make it support generic period assignments. With this patch, the runtime and period parameters can be used to specify arbitrary CPU reservations for RT tasks.

From the previous post [1] I've integrated Peter's suggestions, using a multi-level hierarchy to do admission control, but a one-level only equivalent hierarchy for scheduling, and I've not removed the bandwidth migration mechanism, trying to adapt it to EDF scheduling. In this version tasks are still inserted into priority arrays and only groups are kept in a per-rq edf tree.

The main design issues involved:

- Since it is not easy to mix tasks and groups on the same scheduler queue (tasks have no deadlines), the bandwidth reserved to the tasks in a group is controlled with two additional cgroup attributes:
rt_task_runtime_us and rt_task_period_us. These attributes control, within a cgroup, how much bandwidth is reserved to the tasks it contains. The old attributes, rt_runtime_us and rt_period_us, are still there, and control the bandwidth assigned to the cgroup. They are used only for admission control.

- Shared resources are still handled using boosting. When a group contains a task inside a critical section it is scheduled according the highest priority among the ones of the tasks it contains. In this way, the same group has two modes: when it is not boosted it is scheduled according to its deadline; when it is boosted, it is scheduled according its priority. Boosted groups are always favored over non-boosted ones.

- Given that the various rt_rq's belonging to the same task group are activated independently, there is the need of a timer per each rt_rq.

Quoted 6 lines

- While balancing the bandwidth assigned to a cgroup on various cpus we have to make sure that utilization for the rt_rq's on each cpu does not exceed the global utilization limit for RT tasks.

As usual, feedback welcome.

Looks very nice, good work! comments in individual replies.

maintainer
#21 lore raw
In reply to Fabio Checconi
Quoted 8 lines · Fabio Checconi

- Since it is not easy to mix tasks and groups on the same scheduler queue (tasks have no deadlines), the bandwidth reserved to the tasks in a group is controlled with two additional cgroup attributes:
rt_task_runtime_us and rt_task_period_us. These attributes control, within a cgroup, how much bandwidth is reserved to the tasks it contains. The old attributes, rt_runtime_us and rt_period_us, are still there, and control the bandwidth assigned to the cgroup. They are used only for admission control.

We could do this implicitly by simply setting the task_bandwidth to the cgroup bandwidth - \Sum_children bandwidth.

Having it explicit gives the administrator slightly more control at the cost of a more complex interface.

Just wondering if you thought about this trade-off?

#22 lore raw
Quoted 13 lines

From: Peter Zijlstra <[email protected]>
Date: Sat, Feb 27, 2010 01:33:11PM +0100

Quoted 8 lines · Fabio Checconi

- Since it is not easy to mix tasks and groups on the same scheduler queue (tasks have no deadlines), the bandwidth reserved to the tasks in a group is controlled with two additional cgroup attributes:
rt_task_runtime_us and rt_task_period_us. These attributes control, within a cgroup, how much bandwidth is reserved to the tasks it contains. The old attributes, rt_runtime_us and rt_period_us, are still there, and control the bandwidth assigned to the cgroup. They are used only for admission control.

Quoted 7 lines

We could do this implicitly by simply setting the task_bandwidth to the cgroup bandwidth - \Sum_children bandwidth.

Having it explicit gives the administrator slightly more control at the cost of a more complex interface.

Just wondering if you thought about this trade-off?

I started with it, because I didn't like changing the interface and because four files to manage the bandwidth *are* a nightmare from the user perspective... The problem with using only two files and assign the residual bandwidth to the tasks in the group is that it makes really hard to find out how much bw is allocated to the tasks, esp. when the child groups have different periods. In practice we would be guaranteeing something but the user would have a hard time finding out what...

The biggest problem with the four files used in the current implementation is that bandwidth assignments should be atomic (because setting all the parameters independently can force the system to go through non-feasible assignments, and the order to use when assigning runtime and period changes depending on the direction of the change). I know this is a dangerous question, but I'll try it anyway: are we ready for multi-valued cgroup parameters?

maintainer
#23 lore raw
Quoted 21 lines · Fabio Checconi
Quoted 13 lines

From: Peter Zijlstra <[email protected]>
Date: Sat, Feb 27, 2010 01:33:11PM +0100

Quoted 8 lines · Fabio Checconi

- Since it is not easy to mix tasks and groups on the same scheduler queue (tasks have no deadlines), the bandwidth reserved to the tasks in a group is controlled with two additional cgroup attributes:
rt_task_runtime_us and rt_task_period_us. These attributes control, within a cgroup, how much bandwidth is reserved to the tasks it contains. The old attributes, rt_runtime_us and rt_period_us, are still there, and control the bandwidth assigned to the cgroup. They are used only for admission control.

Quoted 7 lines

We could do this implicitly by simply setting the task_bandwidth to the cgroup bandwidth - \Sum_children bandwidth.

Having it explicit gives the administrator slightly more control at the cost of a more complex interface.

Just wondering if you thought about this trade-off?

Quoted 8 lines

I started with it, because I didn't like changing the interface and because four files to manage the bandwidth *are* a nightmare from the user perspective... The problem with using only two files and assign the residual bandwidth to the tasks in the group is that it makes really hard to find out how much bw is allocated to the tasks, esp. when the child groups have different periods. In practice we would be guaranteeing something but the user would have a hard time finding out what...

Right, we could do both, by allowing the task files to have -1 values, effectively disabling their reservation and thus ending up with whatever remains or so.

Quoted 7 lines

The biggest problem with the four files used in the current implementation is that bandwidth assignments should be atomic (because setting all the parameters independently can force the system to go through non-feasible assignments, and the order to use when assigning runtime and period changes depending on the direction of the change). I know this is a dangerous question, but I'll try it anyway: are we ready for multi-valued cgroup parameters?

Right, I don't know about multi-valued files, that sounds like its going to confuse people too.

Another option might be some transactional interface, but not sure how that would work out either.. maybe by toggling the system wide bandwidth control off and on, not sure who's in charge of cgroupfs anyway.

#24 lore raw
Quoted 9 lines
Quoted 8 lines

The biggest problem with the four files used in the current implementation is that bandwidth assignments should be atomic (because setting all the parameters independently can force the system to go through non-feasible assignments, and the order to use when assigning runtime and period changes depending on the direction of the change). I know this is a dangerous question, but I'll try it anyway: are we ready for multi-valued cgroup parameters?

Quoted 3 lines

Right, I don't know about multi-valued files, that sounds like its going to confuse people too.

True, but after having used the current interface I feel multi-valued files will be better. For an idea, this is how I currently change bandwidth allocated to a group.

(I am ignoring cpu.rt_ prefixes and _us suffixes for the filenames)

Starting state: task_runtime: 100000, task_period: 1000000. runtime=200000, period=1000000

Suppose I want to bring down the periods to 100000, then first I need to change task_runtime to 10000, then the task period, then the runtime and finally the period.

If I want to go the opposite way, then first I need to increase the periods and then the runtimes.

But I can also see why one would not want a multi-valued interface, esp when the idea is just to change the runtimes. (though there is a complicated interaction between task_runtime and runtime which I am not sure how to avoid).

IOW, this interface sucks :-). We really need something better and easier to use. (Sorry for no constructive input)

Thanks,
Dhaval

#25 lore raw
Quoted 8 lines · Dhaval Giani

But I can also see why one would not want a multi-valued interface, esp when the idea is just to change the runtimes. (though there is a complicated interaction between task_runtime and runtime which I am not sure how to avoid).

IOW, this interface sucks :-). We really need something better and easier to use. (Sorry for no constructive input)

Hi,

is it really so bad to think of a well-engineered API for real-time scheduling services of the OS, to be made available to applications by means of a library, and to be implemented by whatever means fits best in the current kernel/user-space interaction model ? For example, variants on the sched_setscheduler() syscall (remember the sched_setscheduler_ex() for SCHED_SPORADIC ?), a completely new set of syscalls, a cgroupfs based interaction, a set of binary files within the cgroupfs, a set of ioctl()s over cgroupfs entries (somebody must have told me this is not possible), or a special device in /dev, /sys, /proc, /wherever, etc.

For example, on OS-X there seems to be this THREAD_TIME_CONSTRAINT_POLICY

http://developer.apple.com/mac/library/documentation/Darwin/Conceptual/KernelProgramming/scheduler/scheduler.html#//apple_ref/doc/uid/TP30000905-CH211-BABCHEEB

which is claimed to be used by multimedia and system interactive services, even if at the kernel level I don't know how it is implemented and what it actually provides.

Also, in the context of some research projects, a few APIs have come out in the last few years for Linux as well. Now, I don't want to say that we must have something as ugly as:

int frsh_contract_set_resource_and_label
(frsh_contract_t *contract,
const frsh_resource_type_t resource_type,
const frsh_resource_id_t resource_id,
const char *contract_label);

and as complex and multi-faceted as the entire FRESCOR API

http://www.frescor.org/

http://www.frescor.org/index.php?mact=Uploads,cntnt01,getfile,0&cntnt01showtemplate=false&cntnt01upload_id=75&cntnt01returnid=54

pretending to merge into a single framework management of real-time computing, networking, storage, or even memory allocation. However, at least that experience may help in identifying the requirements for a well-engineered approach to a real-time interface. I also know it cannot be something as naive and simple as the AQuoSA API

http://aquosa.sourceforge.net/aquosa-docs/aquosa-qosres/html/group__QRES__LIB.html

designed around a single-processor embedded (and academic) context.

I'm really scared that this cgroupfs-based kind of interfaces fit well only within requirements of "static partitioning" of the system by sysadmins, whilst general real-time, interactive and multimedia applications cannot easily benefit of the potentially available real-time guarantees (in our research we used to dynamically change the reserved resources (runtime) for the application every 40ms or so, others from the same group desire some kind of "elastic scheduling" where the reservation period is changed dynamically for control tasks at an even higher rate . . . I know that those ones may represent pathologically and polarized scenarios of no general interest as well).

Another example: we can quickly find out that we may need more than atomically set 2 parameters, just as an example one may just have:
- runtime
- period
- a set of flags governing the exact scheduling behavior, for example:
- whether or not it may take more than the assigned runtime
- if yes, by what means (SCHED_OTHER when runtime exhausted a'la
AQuoSA, or low priority a'la Sporadic Server, or deadline post-ponement a'la Constant Bandwidth Server, or what ?)
- any weight for governing a weighted fair partitioning of the excess
bandwidth ?
- on Mac OS-X, they seem to have a flag driving preemtability of the
process
- whether we want partitioned scheduling or global scheduling ?
- whether we want to allocate on an individual CPU, on all available
CPUs a'la Fabio's scheduler, or on a cpuset ?
- low priority ?
- signal to be delivered in case of budget overrun ?
- something mad about synchronization, such as blocking times ? (ok, now I'm starting to talk real-time-ish, I'll stop).

and, we may need more complex operations than simply reading/writing runtimes and periods, such as:
- attaching/detaching threads
- monitoring the available instantaneous budget
- setting-up hierarchical scheduling (ok, for such things the cgroups seems just perfect)

My 2 cents (apologies for the length),

Tommaso

Signature · 4 lines
Tommaso Cucinotta, Computer Engineering PhD, Researcher
ReTiS Lab, Scuola Superiore Sant'Anna, Pisa, Italy
Tel +39 050 882 024, Fax +39 050 882 003
http://retis.sssup.it/people/tommaso