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

!MAILaRCHIVE_VOTE_RePLACE
Previous message: [thread] [date] [author]
Next message: [thread] [date] [author]
To: Al Boldi <a1426z@...>
Cc: ck list <ck@...>, <linux-kernel@...>
Date: Sunday, March 11, 2007 - 6:12 pm

On Monday 12 March 2007 08:52, Con Kolivas wrote:

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!

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

Index: linux-2.6.21-rc3-mm2/kernel/sched.c
===================================================================
--- linux-2.6.21-rc3-mm2.orig/kernel/sched.c	2007-03-12 08:47:43.000000000 +1100
+++ linux-2.6.21-rc3-mm2/kernel/sched.c	2007-03-12 09:10:33.000000000 +1100
@@ -96,10 +96,9 @@ unsigned long long __attribute__((weak))
  * provided it is not a realtime comparison.
  */
 #define TASK_PREEMPTS_CURR(p, curr) \
-	(((p)->prio < (curr)->prio) || (((p)->prio == (curr)->prio) && \
+	(((p)->prio < (curr)->prio) || (!rt_task(p) && \
 		((p)->static_prio < (curr)->static_prio && \
-			((curr)->static_prio > (curr)->prio)) && \
-				!rt_task(p)))
+			((curr)->static_prio > (curr)->prio))))
 
 /*
  * This is the time all tasks within the same priority round robin.
@@ -3323,7 +3322,7 @@ static inline void major_prio_rotation(s
  */
 static inline void rotate_runqueue_priority(struct rq *rq)
 {
-	int new_prio_level, remaining_quota;
+	int new_prio_level;
 	struct prio_array *array;
 
 	/*
@@ -3334,7 +3333,6 @@ static inline void rotate_runqueue_prior
 	if (unlikely(sched_find_first_bit(rq->dyn_bitmap) < rq->prio_level))
 		return;
 
-	remaining_quota = rq_quota(rq, rq->prio_level);
 	array = rq->active;
 	if (rq->prio_level > MAX_PRIO - 2) {
 		/* Major rotation required */
@@ -3368,10 +3366,11 @@ static inline void rotate_runqueue_prior
 	}
 	rq->prio_level = new_prio_level;
 	/*
-	 * While we usually rotate with the rq quota being 0, it is possible
-	 * to be negative so we subtract any deficit from the new level.
+	 * As we are merging to a prio_level that may not have anything in
+	 * its quota we add 1 to ensure the tasks get to run in schedule() to
+	 * add their quota to it.
 	 */
-	rq_quota(rq, new_prio_level) += remaining_quota;
+	rq_quota(rq, new_prio_level) += 1;
 }
 
 static void task_running_tick(struct rq *rq, struct task_struct *p)
@@ -3397,12 +3396,11 @@ static void task_running_tick(struct rq 
 	if (!--p->time_slice)
 		task_expired_entitlement(rq, p);
 	/*
-	 * The rq quota can become negative due to a task being queued in
-	 * scheduler without any quota left at that priority level. It is
-	 * cheaper to allow it to run till this scheduler tick and then
-	 * subtract it from the quota of the merged queues.
+	 * We only employ the deadline mechanism if we run over the quota.
+	 * It allows aliasing problems around the scheduler_tick to be
+	 * less harmful.
 	 */
-	if (!rt_task(p) && --rq_quota(rq, rq->prio_level) <= 0) {
+	if (!rt_task(p) && --rq_quota(rq, rq->prio_level) < 0) {
 		if (unlikely(p->first_time_slice))
 			p->first_time_slice = 0;
 		rotate_runqueue_priority(rq);


-- 
-ck
-
Previous message: [thread] [date] [author]
Next message: [thread] [date] [author]

Messages in current thread:
Re: [ANNOUNCE] RSDL completely fair starvation free interact..., Con Kolivas, (Sun Mar 11, 6:12 pm)
RSDL development plans, Con Kolivas, (Tue Mar 13, 7:08 pm)
Re: RSDL development plans, Con Kolivas, (Fri Mar 16, 8:25 am)
RSDL v0.31, Con Kolivas, (Fri Mar 16, 9:40 am)
Re: RSDL v0.31, Al Boldi, (Fri Mar 16, 5:55 pm)
Re: RSDL v0.31, Con Kolivas, (Fri Mar 16, 10:51 pm)
Re: RSDL v0.31, Al Boldi, (Sat Mar 17, 12:40 am)
Re: RSDL v0.31, Con Kolivas, (Sat Mar 17, 12:57 am)
Re: RSDL v0.31, Al Boldi, (Sat Mar 17, 12:12 pm)
Re: RSDL v0.31, Ed Tomlinson, (Sat Mar 17, 9:50 am)
Re: RSDL v0.31, Gene Heskett, (Sat Mar 17, 1:15 am)
Re: RSDL v0.31, AshMilsted, (Fri Mar 16, 1:12 pm)
Re: RSDL v0.31, Gabriel C, (Fri Mar 16, 1:41 pm)
Re: RSDL v0.31, Mike Galbraith, (Fri Mar 16, 11:34 am)
Re: RSDL v0.31, Con Kolivas, (Fri Mar 16, 5:13 pm)
Re: RSDL v0.31, Mike Galbraith, (Fri Mar 16, 6:30 pm)
Re: RSDL v0.31, Rik van Riel, (Sat Mar 17, 10:32 am)
Re: RSDL v0.31, Ingo Molnar, (Sat Mar 17, 11:39 am)
Re: RSDL v0.31, Mike Galbraith, (Sat Mar 17, 10:43 am)
Re: [ck] Re: RSDL v0.31, Dirk Schoebel, (Fri Mar 16, 7:05 pm)
Re: RSDL v0.31, Nicholas Miell, (Sat Mar 17, 12:24 am)
Re: RSDL v0.31, Mike Galbraith, (Sat Mar 17, 1:56 am)
Re: RSDL v0.31, Nicholas Miell, (Sat Mar 17, 2:26 am)
Re: RSDL v0.31, Ingo Molnar, (Sat Mar 17, 3:56 am)
Re: [ck] Re: RSDL v0.31, jos poortvliet, (Sat Mar 17, 7:07 am)
Re: RSDL v0.31, Ingo Molnar, (Sat Mar 17, 8:44 am)
Re: RSDL v0.31, jos poortvliet, (Sat Mar 17, 9:44 am)
Re: [ck] Re: RSDL v0.31, Ed Tomlinson, (Sat Mar 17, 10:04 am)
Re: RSDL v0.31, Ingo Molnar, (Sat Mar 17, 3:45 am)
Re: RSDL v0.31, David Lang, (Sat Mar 17, 3:44 am)
Re: RSDL v0.31, Mike Galbraith, (Sat Mar 17, 4:46 am)
Re: [ck] Re: RSDL v0.31, Mark Glines, (Sat Mar 17, 10:09 am)
Re: [ck] Re: RSDL v0.31, Mike Galbraith, (Sat Mar 17, 10:33 am)
Re: [ck] Re: RSDL v0.31, Mark Glines, (Sat Mar 17, 10:54 am)
Re: [ck] Re: RSDL v0.31, Mike Galbraith, (Sat Mar 17, 10:58 am)
Re: RSDL v0.31, Serge Belyshev, (Sat Mar 17, 4:41 am)
Re: RSDL v0.31, Con Kolivas, (Sat Mar 17, 5:48 am)
Re: RSDL v0.31, Mark Hahn, (Sat Mar 17, 11:13 am)
Re: RSDL v0.31, Chris Friesen, (Mon Mar 19, 11:06 am)
Re: RSDL v0.31, Stephen Clark, (Sat Mar 17, 1:22 pm)
Re: is RSDL an "unfair" scheduler too?, Ingo Molnar, (Sat Mar 17, 7:49 am)
Re: is RSDL an "unfair" scheduler too?, Avi Kivity, (Sat Mar 17, 4:41 pm)
Re: is RSDL an "unfair" scheduler too?, William Lee Irwin III, (Sat Mar 17, 9:25 pm)
Re: is RSDL an "unfair" scheduler too?, Avi Kivity, (Sun Mar 18, 1:00 am)
Re: is RSDL an "unfair" scheduler too?, Linus Torvalds, (Sat Mar 17, 9:32 pm)
Re: is RSDL an "unfair" scheduler too?, Willy Tarreau, (Sun Mar 18, 1:24 am)
Re: is RSDL an "unfair" scheduler too?, Mike Galbraith, (Sun Mar 18, 2:26 am)
Re: [ck] Re: is RSDL an "unfair" scheduler too?, Radoslaw Szkodzinski, (Sun Mar 18, 2:54 am)
Re: [ck] Re: is RSDL an "unfair" scheduler too?, Willy Tarreau, (Sun Mar 18, 3:58 am)
Re: [ck] Re: is RSDL an "unfair" scheduler too?, Avi Kivity, (Sun Mar 18, 4:45 am)
Re: is RSDL an "unfair" scheduler too?, Bill Huey, (Sun Mar 18, 2:09 am)
Re: is RSDL an "unfair" scheduler too?, Bill Davidsen, (Mon Mar 19, 5:14 pm)
Re: is RSDL an "unfair" scheduler too?, Mike Galbraith, (Sun Mar 18, 2:37 am)
Re: is RSDL an "unfair" scheduler too?, Bill Huey, (Sun Mar 18, 3:35 am)
Re: is RSDL an "unfair" scheduler too?, Avi Kivity, (Sun Mar 18, 1:55 am)
RE: is RSDL an "unfair" scheduler too?, David Schwartz, (Sun Mar 18, 10:27 pm)
Re: is RSDL an "unfair" scheduler too?, Avi Kivity, (Mon Mar 19, 11:25 am)
Re: is RSDL an "unfair" scheduler too?, Helge Hafting, (Mon Mar 19, 12:06 pm)
Re: is RSDL an "unfair" scheduler too?, Avi Kivity, (Mon Mar 19, 12:37 pm)
Re: is RSDL an "unfair" scheduler too?, Radoslaw Szkodzinski, (Mon Mar 19, 9:27 am)
Re: is RSDL an "unfair" scheduler too?, David Lang, (Mon Mar 19, 2:30 pm)
Re: is RSDL an "unfair" scheduler too?, Con Kolivas, (Sat Mar 17, 8:02 am)
Re: [ck] Re: is RSDL an "unfair" scheduler too?, jos poortvliet, (Sat Mar 17, 8:23 am)
RE: [ck] Re: is RSDL an "unfair" scheduler too?, David Schwartz, (Sat Mar 17, 1:31 pm)
Re: is RSDL an "unfair" scheduler too?, Ingo Molnar, (Sat Mar 17, 8:28 am)
Re: is RSDL an "unfair" scheduler too?, Con Kolivas, (Sat Mar 17, 8:43 am)
Re: is RSDL an "unfair" scheduler too?, Bill Davidsen, (Sat Mar 17, 10:13 pm)
Re: is RSDL an "unfair" scheduler too?, Mike Galbraith, (Sun Mar 18, 1:37 am)
Re: [ck] Re: is RSDL an "unfair" scheduler too?, jos poortvliet, (Sun Mar 18, 6:58 am)
Re: is RSDL an "unfair" scheduler too?, Kasper Sandberg, (Sat Mar 17, 11:20 pm)
Re: is RSDL an "unfair" scheduler too?, Ingo Molnar, (Sat Mar 17, 12:34 pm)
Re: is RSDL an "unfair" scheduler too?, Bill Davidsen, (Sat Mar 17, 11:23 pm)
Re: [ck] Re: is RSDL an "unfair" scheduler too?, jos poortvliet, (Sat Mar 17, 8:15 am)
Re: RSDL v0.31, Mike Galbraith, (Sat Mar 17, 5:58 am)
Re: RSDL v0.31, Mark Lord, (Mon Mar 19, 12:03 pm)
Re: RSDL v0.31, Al Boldi, (Sat Mar 17, 4:55 pm)
Re: RSDL v0.31, Mark Lord, (Mon Mar 19, 12:07 pm)
Re: RSDL v0.31, Al Boldi, (Mon Mar 19, 4:53 pm)
Re: RSDL v0.31, Artur Skawina, (Tue Mar 20, 3:50 pm)
Re: RSDL v0.31, Al Boldi, (Wed Mar 21, 12:15 am)
Re: RSDL v0.31, Artur Skawina, (Wed Mar 21, 1:24 pm)
Re: RSDL v0.31, Xavier Bestel, (Mon Mar 19, 12:26 pm)
Re: RSDL v0.31, Mark Lord, (Mon Mar 19, 12:36 pm)
Re: RSDL v0.31, Xavier Bestel, (Mon Mar 19, 12:43 pm)
Re: RSDL v0.31, Linus Torvalds, (Mon Mar 19, 11:11 pm)
Re: RSDL v0.31, Mark Lord, (Tue Mar 20, 9:22 am)
Re: RSDL v0.31, Ray Lee, (Tue Mar 20, 11:16 am)
Re: RSDL v0.31, Kasper Sandberg, (Wed Mar 21, 4:55 am)
Re: RSDL v0.31, Mark Lord, (Tue Mar 20, 11:20 am)
Re: [ck] Re: RSDL v0.31, jos poortvliet, (Tue Mar 20, 6:26 am)
Re: RSDL v0.31, Willy Tarreau, (Tue Mar 20, 2:11 am)
Re: RSDL v0.31, Linus Torvalds, (Tue Mar 20, 11:31 am)
Re: RSDL v0.31, Bill Davidsen, (Wed Mar 28, 7:43 pm)
Re: RSDL v0.31, Keith Duthie, (Wed Mar 21, 4:22 am)
Re: RSDL v0.31, Al Boldi, (Tue Mar 20, 2:08 pm)
Re: RSDL v0.31, Xavier Bestel, (Tue Mar 20, 5:03 am)
Re: RSDL v0.31, Ingo Molnar, (Wed Mar 21, 3:50 am)
RE: RSDL v0.31, David Schwartz, (Wed Mar 21, 6:43 am)
Re: RSDL v0.31, Bill Davidsen, (Wed Mar 28, 7:37 pm)
RE: RSDL v0.31, David Schwartz, (Thu Mar 29, 3:10 am)
Re: RSDL v0.31, Nick Piggin, (Thu Mar 29, 3:34 am)
Re: RSDL v0.31, Artur Skawina, (Tue Mar 20, 8:31 am)
Re: RSDL v0.31, Artur Skawina, (Tue Mar 20, 3:16 pm)
Re: RSDL v0.31, Mike Galbraith, (Tue Mar 20, 4:03 am)
Re: RSDL v0.31, Mike Galbraith, (Wed Mar 21, 10:57 am)
Re: RSDL v0.31, Peter Zijlstra, (Wed Mar 21, 12:02 pm)
Re: RSDL v0.31, Mike Galbraith, (Thu Mar 22, 3:07 am)
Re: RSDL v0.31, Con Kolivas, (Thu Mar 22, 6:50 pm)
Re: RSDL v0.31, Mike Galbraith, (Fri Mar 23, 12:39 am)
Re: RSDL v0.31, Con Kolivas, (Fri Mar 23, 1:59 am)
Re: RSDL v0.31, Mike Galbraith, (Fri Mar 23, 8:17 am)
Re: RSDL v0.31, Mike Galbraith, (Fri Mar 23, 2:11 am)
Re: RSDL v0.31, Ingo Molnar, (Thu Mar 22, 5:18 am)
Re: RSDL v0.31, Con Kolivas, (Thu Mar 22, 6:03 pm)
Re: RSDL v0.31, Mike Galbraith, (Thu Mar 22, 5:34 am)
Re: RSDL v0.31, Mike Galbraith, (Thu Mar 22, 5:41 am)
Re: RSDL v0.31, Mike Galbraith, (Wed Mar 21, 1:06 pm)
Re: RSDL v0.31, Mike Galbraith, (Sun Mar 18, 2:17 am)
Re: RSDL v0.31, Kasper Sandberg, (Sun Mar 18, 2:47 am)
Re: RSDL v0.31, Mike Galbraith, (Sun Mar 18, 3:08 am)
Re: [ck] Re: RSDL v0.31, Radoslaw Szkodzinski, (Sun Mar 18, 3:22 am)
Re: [ck] Re: RSDL v0.31, Mike Galbraith, (Sun Mar 18, 3:38 am)
Re: [ck] Re: RSDL v0.31, Radoslaw Szkodzinski, (Sun Mar 18, 11:44 am)
Re: [ck] Re: RSDL v0.31, jos poortvliet, (Sun Mar 18, 12:09 pm)
Re: [ck] Re: RSDL v0.31, Kasper Sandberg, (Sun Mar 18, 5:57 am)
Re: [ck] Re: RSDL v0.31, Bill Davidsen, (Mon Mar 19, 4:47 pm)
Re: [ck] Re: RSDL v0.31, Kasper Sandberg, (Wed Mar 21, 4:58 am)
Re: [ck] Re: RSDL v0.31, jos poortvliet, (Tue Mar 20, 6:19 am)
Re: [ck] Re: RSDL v0.31, Avuton Olrich, (Sun Mar 18, 9:57 am)
Re: [ck] Re: RSDL v0.31, jimmy bahuleyan, (Sun Mar 18, 4:20 am)
Re: [ck] Re: RSDL v0.31, Mike Galbraith, (Sun Mar 18, 4:34 am)
Re: [ck] Re: RSDL v0.31, Mike Galbraith, (Sun Mar 18, 4:04 am)
Re: [ck] Re: RSDL v0.31, michael chang, (Sat Mar 17, 9:58 am)
Re: RSDL v0.31, Mike Galbraith, (Sat Mar 17, 6:49 am)
Re: RSDL v0.31, Gene Heskett, (Sat Mar 17, 8:05 am)
Re: RSDL v0.31, Mike Galbraith, (Sat Mar 17, 9:36 am)
Re: RSDL v0.31, Gene Heskett, (Sat Mar 17, 1:03 pm)
Re: RSDL v0.31, Mike Galbraith, (Sat Mar 17, 1:37 pm)
Re: [ck] Re: RSDL v0.31, Kacper Wysocki, (Sat Mar 17, 2:23 pm)
Re: [ck] Re: RSDL v0.31, Mike Galbraith, (Sat Mar 17, 2:45 pm)
Re: RSDL v0.31, Nicholas Miell, (Sat Mar 17, 4:23 am)
Re: RSDL v0.31, Mike Galbraith, (Sat Mar 17, 3:11 am)
Re: RSDL v0.31, Gene Heskett, (Sat Mar 17, 7:48 am)
Re: RSDL v0.31, William Lee Irwin III, (Sat Mar 17, 3:25 am)
Re: RSDL v0.31, Nicholas Miell, (Sat Mar 17, 3:29 am)
Re: RSDL v0.31, Mike Galbraith, (Sat Mar 17, 2:08 am)
RE: RSDL v0.31, David Schwartz, (Sun Mar 18, 10:27 pm)
RE: RSDL v0.31, Mike Galbraith, (Mon Mar 19, 2:21 am)
Re: RSDL v0.31, Willy Tarreau, (Mon Mar 19, 2:59 am)
Re: RSDL v0.31, Lee Revell, (Sun Mar 18, 3:37 pm)
Re: RSDL v0.31, Szonyi Calin, (Sun Mar 18, 6:45 pm)
Re: RSDL v0.31, Mike Galbraith, (Sun Mar 18, 3:55 pm)
Re: RSDL v0.31, Ed Tomlinson, (Sat Mar 17, 9:56 am)
Re: RSDL development plans, Mike Galbraith, (Fri Mar 16, 9:42 am)
Re: RSDL development plans, Con Kolivas, (Fri Mar 16, 9:59 am)
Re: RSDL development plans, Mike Galbraith, (Fri Mar 16, 10:07 am)