scheduler: compute time-average nr_running per run-queue

Compute the time-average number of running tasks per run-queue for a
trailing window of a fixed time period. The detla add/sub to the
average value is weighted by the amount of time per nr_running value
relative to the total measurement period.

Change-Id: I4b1fa8fee82a549889560ceded4b94bdb811671d
Signed-off-by: Diwakar Tundlam <dtundlam@nvidia.com>
Reviewed-on: http://git-master/r/108070
Reviewed-by: Automatic_Commit_Validation_User
Reviewed-by: Ryan Wong <ryanw@nvidia.com>
Tested-by: Ryan Wong <ryanw@nvidia.com>

3 files changed, 44 insertions, 0 deletions

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 5bb4dd2e4c59..c9e03a9aa956 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -139,6 +139,7 @@ extern int nr_processes(void);
 extern unsigned long nr_running(void);
 extern unsigned long nr_uninterruptible(void);
 extern unsigned long nr_iowait(void);
+extern unsigned long avg_nr_running(void);
 extern unsigned long nr_iowait_cpu(int cpu);
 extern unsigned long this_cpu_load(void);
 
diff --git a/kernel/sched.c b/kernel/sched.c
index f6cf5cbc64ba..d6d87b918399 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -472,6 +472,10 @@ struct rq {
 #endif
 	int skip_clock_update;
 
+	/* time-based average load */
+	u64 nr_last_stamp;
+	unsigned int ave_nr_running;
+
 	/* capture load from *all* tasks on this cpu: */
 	struct load_weight load;
 	unsigned long nr_load_updates;
@@ -1756,13 +1760,39 @@ static const struct sched_class rt_sched_class;
 
 #include "sched_stats.h"
 
+/* 27 ~= 134217728ns = 134.2ms
+ * 26 ~=  67108864ns =  67.1ms
+ * 25 ~=  33554432ns =  33.5ms
+ * 24 ~=  16777216ns =  16.8ms */
+#define NR_AVE_PERIOD_EXP	27
+#define NR_AVE_SCALE(x)		((x) << FSHIFT)
+#define NR_AVE_PERIOD		(1 << NR_AVE_PERIOD_EXP)
+#define NR_AVE_DIV_PERIOD(x)	((x) >> NR_AVE_PERIOD_EXP)
+
+static inline void do_avg_nr_running(struct rq *rq)
+{
+	s64 nr, deltax;
+
+	deltax = rq->clock_task - rq->nr_last_stamp;
+	rq->nr_last_stamp = rq->clock_task;
+	nr = NR_AVE_SCALE(rq->nr_running);
+
+	if (deltax > NR_AVE_PERIOD)
+		rq->ave_nr_running = nr;
+	else
+		rq->ave_nr_running +=
+			NR_AVE_DIV_PERIOD(deltax * (nr - rq->ave_nr_running));
+}
+
 static void inc_nr_running(struct rq *rq)
 {
+	do_avg_nr_running(rq);
 	rq->nr_running++;
 }
 
 static void dec_nr_running(struct rq *rq)
 {
+	do_avg_nr_running(rq);
 	rq->nr_running--;
 }
 
@@ -3255,6 +3285,16 @@ unsigned long nr_iowait(void)
 	return sum;
 }
 
+unsigned long avg_nr_running(void)
+{
+	unsigned long i, sum = 0;
+
+	for_each_online_cpu(i)
+		sum += cpu_rq(i)->ave_nr_running;
+
+	return sum;
+}
+
 unsigned long nr_iowait_cpu(int cpu)
 {
 	struct rq *this = cpu_rq(cpu);
diff --git a/kernel/sched_debug.c b/kernel/sched_debug.c
index a6710a112b4f..6371af0e4612 100644
--- a/kernel/sched_debug.c
+++ b/kernel/sched_debug.c
@@ -264,6 +264,9 @@ static void print_cpu(struct seq_file *m, int cpu)
 	SEQ_printf(m, "  .%-30s: %Ld.%06ld\n", #x, SPLIT_NS(rq->x))
 
 	P(nr_running);
+	SEQ_printf(m, "  .%-30s: %d.%03d   \n", "ave_nr_running",
+		   rq->ave_nr_running / FIXED_1,
+		   ((rq->ave_nr_running % FIXED_1) * 1000) / FIXED_1);
 	SEQ_printf(m, "  .%-30s: %lu\n", "load",
 		   rq->load.weight);
 	P(nr_switches);