Re: [PATCH] [RSDL-0.30] sched: rsdl improve latencies with differential nice -1

Re: [PATCH] [RSDL-0.30] sched: rsdl improve latencies with differential nice -1

[Al Boldi]

Con Kolivas wrote:
> On Wednesday 14 March 2007 03:03, Con Kolivas wrote:
> > On Wednesday 14 March 2007 02:31, Con Kolivas wrote:
> > > On Monday 12 March 2007 22:26, Al Boldi wrote:
> > > > I think, it should be possible to spread this max expiration latency
> > > > across the rotation, should it not?
> > >
> > > Can you try the attached patch please Al and Mike? It "dithers" the
> > > priority bitmap which tends to fluctuate the latency a lot more but in
> > > a cyclical fashion. This tends to make the max latency bound to a
> > > smaller value and should make it possible to run -nice tasks without
> > > killing the latency of the non niced tasks. Eg you could possibly run
> > > X nice -10 at a guess like we used to in 2.4 days. It's not essential
> > > of course, but is a workaround for Mike's testcase.
> >
> > Oops, one tiny fix. This is a respin of the patch, sorry.
>
> A few other minor things would need to be updated before this patch is in
> a good enough shape to join the rsdl patches. This one will be good for
> testing though.

Applied against v0.30 mainline.  It only works on prio +16 to +19.


Thanks!

--
Al

Re: [ck] Re: [PATCH] [RSDL-0.30] sched: rsdl improve latencies with differential nice -1

[Con Kolivas]

On Wednesday 14 March 2007 06:54, Al Boldi wrote:
> Con Kolivas wrote:
> > On Wednesday 14 March 2007 03:03, Con Kolivas wrote:
> > > On Wednesday 14 March 2007 02:31, Con Kolivas wrote:
> > > > On Monday 12 March 2007 22:26, Al Boldi wrote:
> > > > > I think, it should be possible to spread this max expiration
> > > > > latency across the rotation, should it not?
> > > >
> > > > Can you try the attached patch please Al and Mike? It "dithers" the
> > > > priority bitmap which tends to fluctuate the latency a lot more but
> > > > in a cyclical fashion. This tends to make the max latency bound to a
> > > > smaller value and should make it possible to run -nice tasks without
> > > > killing the latency of the non niced tasks. Eg you could possibly run
> > > > X nice -10 at a guess like we used to in 2.4 days. It's not essential
> > > > of course, but is a workaround for Mike's testcase.
> > >
> > > Oops, one tiny fix. This is a respin of the patch, sorry.
> >
> > A few other minor things would need to be updated before this patch is in
> > a good enough shape to join the rsdl patches. This one will be good for
> > testing though.
>
> Applied against v0.30 mainline.  It only works on prio +16 to +19.

I guess the "other minor things" will matter then :) I'll keep working. At 
least you know what I'm working on now.

-- 
-ck

Re: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler

[Al Boldi]

Con Kolivas wrote:
> > >> >> >This message is to announce the first general public release of
> > >> >> > the "Rotating Staircase DeadLine" cpu scheduler.

Thanks a lot!

> Just to make it clear. The purpose of this scheduler is at all costs to
> maintain absolute fairness no matter what type of load it is put under.

Great!

> This means that if you heavily load up your machine without the use of
> 'nice' then your interactive tasks _will_ slow down proportionately to the
> amount of cpu you use. So doing make -j4 for example will make any other
> task started in taht presence run precisely 1/5th speed, but they will
> still be responsive, have low latency (and audio shouldn't skip for
> example).

That's just what it did, but when you "nice make -j4", things (gears) start 
to stutter.  Is that due to the staircase?


Thanks!

--
Al

Re: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler

[Al Boldi]

Con Kolivas wrote:
> On Monday 12 March 2007 15:42, Al Boldi wrote:
> > Con Kolivas wrote:
> > > On Monday 12 March 2007 08:52, Con Kolivas wrote:
> > > > And thank you! I think I know what's going on now. I think each
> > > > rotation is followed by another rotation before the higher priority
> > > > task is getting a look in in schedule() to even get quota and add it
> > > > to the runqueue quota. I'll try a simple change to see if that
> > > > helps. Patch coming up shortly.
> > >
> > > Can you try the following patch and see if it helps. There's also one
> > > minor preemption logic fix in there that I'm planning on including.
> > > Thanks!
> >
> > Applied on top of v0.28 mainline, and there is no difference.
> >
> > What's it look like on your machine?
>
> The higher priority one always get 6-7ms whereas the lower priority one
> runs 6-7ms and then one larger perfectly bound expiration amount.
> Basically exactly as I'd expect. The higher priority task gets precisely
> RR_INTERVAL maximum latency whereas the lower priority task gets
> RR_INTERVAL min and full expiration (according to the virtual deadline) as
> a maximum. That's exactly how I intend it to work. Yes I realise that the
> max latency ends up being longer intermittently on the niced task but
> that's -in my opinion- perfectly fine as a compromise to ensure the nice 0
> one always gets low latency.

I think, it should be possible to spread this max expiration latency across 
the rotation, should it not?


Thanks!

--
Al

[PATCH] [RSDL-0.30] sched: rsdl improve latencies with differential nice

[Con Kolivas]

On Monday 12 March 2007 22:26, Al Boldi wrote:
> I think, it should be possible to spread this max expiration latency across
> the rotation, should it not?

Can you try the attached patch please Al and Mike? It "dithers" the priority
bitmap which tends to fluctuate the latency a lot more but in a cyclical
fashion. This tends to make the max latency bound to a smaller value and
should make it possible to run -nice tasks without killing the latency of the
non niced tasks. Eg you could possibly run X nice -10 at a guess like we used
to in 2.4 days. It's not essential of course, but is a workaround for Mike's
testcase.

Thanks.

---
Modify the priority bitmaps of different nice levels to be dithered
minimising the latency likely when different nice levels are used. This
allows low cpu using relatively niced tasks to still get low latency in the
presence of less niced tasks.

Fix the accounting on -nice levels to not be scaled by HZ.

Signed-off-by: Con Kolivas <kernel@kolivas.org>

---
 kernel/sched.c |   69 +++++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 45 insertions(+), 24 deletions(-)

Index: linux-2.6.21-rc3-mm2/kernel/sched.c
===================================================================
--- linux-2.6.21-rc3-mm2.orig/kernel/sched.c	2007-03-13 23:17:29.000000000 +1100
+++ linux-2.6.21-rc3-mm2/kernel/sched.c	2007-03-14 02:20:37.000000000 +1100
@@ -89,24 +89,34 @@ unsigned long long __attribute__((weak))
 #define SCHED_PRIO(p)		((p)+MAX_RT_PRIO)
 #define MAX_DYN_PRIO		(MAX_PRIO + PRIO_RANGE)
 
-/*
- * Preemption needs to take into account that a low priority task can be
- * at a higher prio due to list merging. Its priority is artificially
- * elevated and it should be preempted if anything higher priority wakes up
- * provided it is not a realtime comparison.
- */
-#define TASK_PREEMPTS_CURR(p, curr) \
-	(((p)->prio < (curr)->prio) || (!rt_task(p) && \
-		((p)->static_prio < (curr)->static_prio && \
-			((curr)->static_prio > (curr)->prio))))
+#define TASK_PREEMPTS_CURR(p, curr)	((p)->prio < (curr)->prio)
 
 /*
  * This is the time all tasks within the same priority round robin.
  * Set to a minimum of 6ms.
  */
-#define RR_INTERVAL		((6 * HZ / 1001) + 1)
+#define __RR_INTERVAL		6
+#define RR_INTERVAL		((__RR_INTERVAL * HZ / 1001) + 1)
 #define DEF_TIMESLICE		(RR_INTERVAL * 20)
 
+/*
+ * This contains a bitmap for each dynamic priority level with empty slots
+ * for the valid priorities each different nice level can have. It allows
+ * us to stagger the slots where differing priorities run in a way that
+ * keeps latency differences between different nice levels at a minimum.
+ * ie, where 0 means a slot for that priority, priority running from left to
+ * right:
+ * nice -20 0000000000000000000000000000000000000000
+ * nice -10 1001000100100010001001000100010010001000
+ * nice   0 1010101010101010101010101010101010101010
+ * nice   5 1101011010110101101011010110101101011011
+ * nice  10 1101110110111011101101110111011011101110
+ * nice  15 1111101111110111111011111011111101111110
+ * nice  19 1111111111111111111011111111111111111111
+  */
+static unsigned long prio_matrix[PRIO_RANGE][BITS_TO_LONGS(PRIO_RANGE)]
+				__read_mostly;
+
 #ifdef CONFIG_SMP
 /*
  * Divide a load by a sched group cpu_power : (load / sg->__cpu_power)
@@ -649,15 +659,6 @@ static inline int task_queued(struct tas
 static inline void set_task_entitlement(struct task_struct *p)
 {
 	__set_bit(USER_PRIO(p->prio), p->bitmap);
-
-	/*
-	 * In the case this task has been part of a merged list that has
-	 * made it to higher priority than it should be, we remove the
-	 * quota from its own priority since it will get a quota at this
-	 * priority.
-	 */
-	if (p->normal_prio < p->static_prio)
-		__set_bit(USER_PRIO(p->static_prio), p->bitmap);
 	p->time_slice = p->quota;
 }
 
@@ -705,7 +706,8 @@ static void dequeue_task(struct task_str
  */
 static inline void task_new_array(struct task_struct *p, struct rq *rq)
 {
-	bitmap_zero(p->bitmap, PRIO_RANGE);
+	bitmap_copy(p->bitmap, prio_matrix[USER_PRIO(p->static_prio)],
+		    PRIO_RANGE);
 	p->rotation = rq->prio_rotation;
 }
 
@@ -833,11 +835,12 @@ static void requeue_task(struct task_str
  */
 static inline unsigned int task_timeslice(struct task_struct *p)
 {
-	unsigned int slice, rr;
+	unsigned int slice;
 
-	slice = rr = p->quota;
+	slice = p->quota;
 	if (likely(!rt_task(p)))
-		slice += (PRIO_RANGE - 1 - TASK_USER_PRIO(p)) * rr;
+		slice += (PRIO_RANGE - 1 - TASK_USER_PRIO(p)) *
+			__RR_INTERVAL / HZ;
 	return slice;
 }
 
@@ -7066,6 +7069,24 @@ void __init sched_init(void)
 	int i, j, k;
 	int highest_cpu = 0;
 
+	for (i = 0; i < PRIO_RANGE; i++) {
+		if (i < 20) {
+			bitmap_zero(prio_matrix[i] , PRIO_RANGE);
+			j = PRIO_RANGE * PRIO_RANGE / (i + 1);
+			for (k = j; k < PRIO_RANGE * PRIO_RANGE; k += j)
+				__set_bit(k / PRIO_RANGE, prio_matrix[i]);
+		} else if (i == 20) {
+			bitmap_fill(prio_matrix[i], PRIO_RANGE);
+			for (k = 1; k < PRIO_RANGE; k += 2)
+				__clear_bit(k, prio_matrix[i]);
+		} else {
+			bitmap_fill(prio_matrix[i], PRIO_RANGE);
+			j = PRIO_RANGE * PRIO_RANGE / (PRIO_RANGE - i + 1);
+			for (k = j; k < PRIO_RANGE * PRIO_RANGE; k += j)
+				__clear_bit(k / PRIO_RANGE, prio_matrix[i]);
+		}
+	}
+
 	for_each_possible_cpu(i) {
 		struct prio_array *array;
 		struct rq *rq;

-- 
-ck

[PATCH] [RSDL-0.30] sched: rsdl improve latencies with differential nice -1

[Con Kolivas]

On Wednesday 14 March 2007 02:31, Con Kolivas wrote:
> On Monday 12 March 2007 22:26, Al Boldi wrote:
> > I think, it should be possible to spread this max expiration latency
> > across the rotation, should it not?
>
> Can you try the attached patch please Al and Mike? It "dithers" the
> priority bitmap which tends to fluctuate the latency a lot more but in a
> cyclical fashion. This tends to make the max latency bound to a smaller
> value and should make it possible to run -nice tasks without killing the
> latency of the non niced tasks. Eg you could possibly run X nice -10 at a
> guess like we used to in 2.4 days. It's not essential of course, but is a
> workaround for Mike's testcase.

Oops, one tiny fix. This is a respin of the patch, sorry.
---
Modify the priority bitmaps of different nice levels to be dithered
minimising the latency likely when different nice levels are used. This
allows low cpu using relatively niced tasks to still get low latency in the
presence of less niced tasks.

Fix the accounting on -nice levels to not be scaled by HZ.

Signed-off-by: Con Kolivas <kernel@kolivas.org>

---
 kernel/sched.c |   73 ++++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 47 insertions(+), 26 deletions(-)

Index: linux-2.6.21-rc3-mm2/kernel/sched.c
===================================================================
--- linux-2.6.21-rc3-mm2.orig/kernel/sched.c	2007-03-13 23:17:29.000000000 +1100
+++ linux-2.6.21-rc3-mm2/kernel/sched.c	2007-03-14 03:01:58.000000000 +1100
@@ -89,24 +89,34 @@ unsigned long long __attribute__((weak))
 #define SCHED_PRIO(p)		((p)+MAX_RT_PRIO)
 #define MAX_DYN_PRIO		(MAX_PRIO + PRIO_RANGE)
 
-/*
- * Preemption needs to take into account that a low priority task can be
- * at a higher prio due to list merging. Its priority is artificially
- * elevated and it should be preempted if anything higher priority wakes up
- * provided it is not a realtime comparison.
- */
-#define TASK_PREEMPTS_CURR(p, curr) \
-	(((p)->prio < (curr)->prio) || (!rt_task(p) && \
-		((p)->static_prio < (curr)->static_prio && \
-			((curr)->static_prio > (curr)->prio))))
+#define TASK_PREEMPTS_CURR(p, curr)	((p)->prio < (curr)->prio)
 
 /*
  * This is the time all tasks within the same priority round robin.
  * Set to a minimum of 6ms.
  */
-#define RR_INTERVAL		((6 * HZ / 1001) + 1)
+#define __RR_INTERVAL		6
+#define RR_INTERVAL		((__RR_INTERVAL * HZ / 1001) + 1)
 #define DEF_TIMESLICE		(RR_INTERVAL * 20)
 
+/*
+ * This contains a bitmap for each dynamic priority level with empty slots
+ * for the valid priorities each different nice level can have. It allows
+ * us to stagger the slots where differing priorities run in a way that
+ * keeps latency differences between different nice levels at a minimum.
+ * ie, where 0 means a slot for that priority, priority running from left to
+ * right:
+ * nice -20 0000000000000000000000000000000000000000
+ * nice -10 1001000100100010001001000100010010001000
+ * nice   0 1010101010101010101010101010101010101010
+ * nice   5 1101011010110101101011010110101101011011
+ * nice  10 1101110110111011101101110111011011101110
+ * nice  15 1111101111110111111011111011111101111110
+ * nice  19 1111111111111111111011111111111111111111
+  */
+static unsigned long prio_matrix[PRIO_RANGE][BITS_TO_LONGS(PRIO_RANGE)]
+				__read_mostly;
+
 #ifdef CONFIG_SMP
 /*
  * Divide a load by a sched group cpu_power : (load / sg->__cpu_power)
@@ -649,15 +659,6 @@ static inline int task_queued(struct tas
 static inline void set_task_entitlement(struct task_struct *p)
 {
 	__set_bit(USER_PRIO(p->prio), p->bitmap);
-
-	/*
-	 * In the case this task has been part of a merged list that has
-	 * made it to higher priority than it should be, we remove the
-	 * quota from its own priority since it will get a quota at this
-	 * priority.
-	 */
-	if (p->normal_prio < p->static_prio)
-		__set_bit(USER_PRIO(p->static_prio), p->bitmap);
 	p->time_slice = p->quota;
 }
 
@@ -705,7 +706,8 @@ static void dequeue_task(struct task_str
  */
 static inline void task_new_array(struct task_struct *p, struct rq *rq)
 {
-	bitmap_zero(p->bitmap, PRIO_RANGE);
+	bitmap_copy(p->bitmap, prio_matrix[USER_PRIO(p->static_prio)],
+		    PRIO_RANGE);
 	p->rotation = rq->prio_rotation;
 }
 
@@ -746,7 +748,7 @@ static void recalc_task_prio(struct task
 			task_new_array(p, rq);
 	} else
 		task_new_array(p, rq);
-	search_prio = p->static_prio;
+	search_prio = MAX_RT_PRIO;
 
 	/*
 	 * SCHED_BATCH tasks never start at better priority than any other
@@ -755,7 +757,7 @@ static void recalc_task_prio(struct task
 	 * non SCHED_BATCH tasks of the same nice level.
 	 */
 	if (unlikely(p->policy == SCHED_BATCH))
-		search_prio = max(p->static_prio, rq->prio_level);
+		search_prio = rq->prio_level;
 	queue_prio = SCHED_PRIO(find_next_zero_bit(p->bitmap, PRIO_RANGE,
 		     USER_PRIO(search_prio)));
 	if (queue_prio == MAX_PRIO) {
@@ -833,11 +835,12 @@ static void requeue_task(struct task_str
  */
 static inline unsigned int task_timeslice(struct task_struct *p)
 {
-	unsigned int slice, rr;
+	unsigned int slice;
 
-	slice = rr = p->quota;
+	slice = p->quota;
 	if (likely(!rt_task(p)))
-		slice += (PRIO_RANGE - 1 - TASK_USER_PRIO(p)) * rr;
+		slice += (PRIO_RANGE - 1 - TASK_USER_PRIO(p)) *
+			__RR_INTERVAL / HZ;
 	return slice;
 }
 
@@ -7066,6 +7069,24 @@ void __init sched_init(void)
 	int i, j, k;
 	int highest_cpu = 0;
 
+	for (i = 0; i < PRIO_RANGE; i++) {
+		if (i < 20) {
+			bitmap_zero(prio_matrix[i] , PRIO_RANGE);
+			j = PRIO_RANGE * PRIO_RANGE / (i + 1);
+			for (k = j; k < PRIO_RANGE * PRIO_RANGE; k += j)
+				__set_bit(k / PRIO_RANGE, prio_matrix[i]);
+		} else if (i == 20) {
+			bitmap_fill(prio_matrix[i], PRIO_RANGE);
+			for (k = 1; k < PRIO_RANGE; k += 2)
+				__clear_bit(k, prio_matrix[i]);
+		} else {
+			bitmap_fill(prio_matrix[i], PRIO_RANGE);
+			j = PRIO_RANGE * PRIO_RANGE / (PRIO_RANGE - i + 1);
+			for (k = j; k < PRIO_RANGE * PRIO_RANGE; k += j)
+				__clear_bit(k / PRIO_RANGE, prio_matrix[i]);
+		}
+	}
+
 	for_each_possible_cpu(i) {
 		struct prio_array *array;
 		struct rq *rq;

-- 
-ck

Re: [PATCH] [RSDL-0.30] sched: rsdl improve latencies with differential nice -1

[Con Kolivas]

On Wednesday 14 March 2007 03:03, Con Kolivas wrote:
> On Wednesday 14 March 2007 02:31, Con Kolivas wrote:
> > On Monday 12 March 2007 22:26, Al Boldi wrote:
> > > I think, it should be possible to spread this max expiration latency
> > > across the rotation, should it not?
> >
> > Can you try the attached patch please Al and Mike? It "dithers" the
> > priority bitmap which tends to fluctuate the latency a lot more but in a
> > cyclical fashion. This tends to make the max latency bound to a smaller
> > value and should make it possible to run -nice tasks without killing the
> > latency of the non niced tasks. Eg you could possibly run X nice -10 at a
> > guess like we used to in 2.4 days. It's not essential of course, but is a
> > workaround for Mike's testcase.
>
> Oops, one tiny fix. This is a respin of the patch, sorry.

A few other minor things would need to be updated before this patch is in a 
good enough shape to join the rsdl patches. This one will be good for testing 
though.

-- 
-ck

Re: [PATCH] [RSDL-0.30] sched: rsdl improve latencies with differential nice -1

[Con Kolivas]

On Wednesday 14 March 2007 03:03, Con Kolivas wrote:
> On Wednesday 14 March 2007 02:31, Con Kolivas wrote:
> > On Monday 12 March 2007 22:26, Al Boldi wrote:
> > > I think, it should be possible to spread this max expiration latency
> > > across the rotation, should it not?
> >
> > Can you try the attached patch please Al and Mike? It "dithers" the
> > priority bitmap which tends to fluctuate the latency a lot more but in a
> > cyclical fashion. This tends to make the max latency bound to a smaller
> > value and should make it possible to run -nice tasks without killing the
> > latency of the non niced tasks. Eg you could possibly run X nice -10 at a
> > guess like we used to in 2.4 days. It's not essential of course, but is a
> > workaround for Mike's testcase.
>
> Oops, one tiny fix. This is a respin of the patch, sorry.
> ---

Bah with a bit more sleep under my belt it became clear that I forgot to 
update the expired array in any proper way so this change almost breaks stuff 
at the moment in the shape it's in. Please disregard this change for now 
apart from interest in how I'm tackling the nice issue.

-- 
-ck