lkml.org 
[lkml]   [2007]   [Apr]   [13]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
Subject[PATCH] sched: implement staircase deadline scheduler rework priomatrix
Date
Rework the priority matrix used by the staircase-deadline cpu scheduler.

Ensuring every nice level uses priority slot 139 means that niced tasks will
not cause expiration prematurely for less niced tasks that have been sleeping.

This also increases the frequency less niced tasks preempt niced tasks, and
simplifies greatly the code that generates the priority matrix.

Update the documentation accordingly and explain why the priority matrix
exists in the first place.

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

---
Documentation/sched-design.txt | 13 +++++++------
kernel/sched.c | 37 ++++++++++++++++---------------------
2 files changed, 23 insertions(+), 27 deletions(-)

Index: linux-2.6.21-rc6-mm1/kernel/sched.c
===================================================================
--- linux-2.6.21-rc6-mm1.orig/kernel/sched.c 2007-04-14 00:25:36.000000000 +1000
+++ linux-2.6.21-rc6-mm1/kernel/sched.c 2007-04-14 00:25:46.000000000 +1000
@@ -113,15 +113,19 @@ int rr_interval __read_mostly;
* 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.
+ * The purpose of a pre-generated matrix is for rapid lookup of next slot in
+ * O(1) time without having to recalculate every time priority gets demoted.
+ * All nice levels use priority slot 39 as this allows less niced tasks to
+ * get all priority slots better than that before expiration is forced.
* ie, where 0 means a slot for that priority, priority running from left to
- * right:
+ * right is from prio 0 to prio 39:
* nice -20 0000000000000000000000000000000000000000
- * nice -10 1001000100100010001001000100010010001000
- * nice 0 0101010101010101010101010101010101010101
- * nice 5 1101011010110101101011010110101101011011
- * nice 10 0110111011011101110110111011101101110111
- * nice 15 0111110111111011111101111101111110111111
- * nice 19 1111111111111111111011111111111111111111
+ * nice -10 1000100010001000100010001000100010010000
+ * nice 0 1010101010101010101010101010101010101010
+ * nice 5 1011010110110101101101011011010110110110
+ * nice 10 1110111011101110111011101110111011101110
+ * nice 15 1111111011111110111111101111111011111110
+ * nice 19 1111111111111111111111111111111111111110
*/
static unsigned long prio_matrix[PRIO_RANGE][BITS_TO_LONGS(PRIO_RANGE)]
__read_mostly;
@@ -6983,20 +6987,11 @@ void __init sched_init(void)

/* Generate the priority matrix */
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]);
+ bitmap_fill(prio_matrix[i], PRIO_RANGE);
+ j = PRIO_RANGE * PRIO_RANGE / (PRIO_RANGE - i);
+ for (k = 0; k <= PRIO_RANGE * (PRIO_RANGE - 1); k += j) {
+ __clear_bit(PRIO_RANGE - 1 - (k / PRIO_RANGE),
+ prio_matrix[i]);
}
}

Index: linux-2.6.21-rc6-mm1/Documentation/sched-design.txt
===================================================================
--- linux-2.6.21-rc6-mm1.orig/Documentation/sched-design.txt 2007-04-13 17:01:43.000000000 +1000
+++ linux-2.6.21-rc6-mm1/Documentation/sched-design.txt 2007-04-14 00:25:46.000000000 +1000
@@ -268,13 +268,14 @@ there are 40 priority slots where a task
and the allocation of slots is dependant on nice level. In the
following table, a zero represents a slot where the task may run.

+PRIORITY:0..................20.................39
nice -20 0000000000000000000000000000000000000000
-nice -10 1001000100100010001001000100010010001000
-nice 0 0101010101010101010101010101010101010101
-nice 5 1101011010110101101011010110101101011011
-nice 10 0110111011011101110110111011101101110111
-nice 15 0111110111111011111101111101111110111111
-nice 19 1111111111111111111011111111111111111111
+nice -10 1000100010001000100010001000100010010000
+nice 0 1010101010101010101010101010101010101010
+nice 5 1011010110110101101101011011010110110110
+nice 10 1110111011101110111011101110111011101110
+nice 15 1111111011111110111111101111111011111110
+nice 19 1111111111111111111111111111111111111110

As can be seen, a nice -20 task runs in every priority slot whereas a nice 19
task only runs one slot per major rotation. This dithered table allows for the
--
-ck
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2007-04-13 16:47    [W:0.022 / U:0.200 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site