[PATCH] add requeue task

[PATCH] add requeue task

[Con Kolivas]

[-- Attachment #1.1: Type: text/plain, Size: 19 bytes --]

add requeue task



[-- Attachment #1.2: sched-add_requeue_task.diff --]
[-- Type: text/x-patch, Size: 2198 bytes --]

We can requeue tasks for cheaper then doing a complete dequeue followed by
an enqueue. Add the requeue_task function and perform it where possible.

Change the granularity code to requeue tasks at their best priority
instead of changing priority while they're running. This keeps tasks at
their top interactive level during their whole timeslice.

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

Index: linux-2.6.10-rc1-mm2/kernel/sched.c
===================================================================
--- linux-2.6.10-rc1-mm2.orig/kernel/sched.c	2004-11-02 14:48:54.686316718 +1100
+++ linux-2.6.10-rc1-mm2/kernel/sched.c	2004-11-02 14:52:51.805763544 +1100
@@ -579,6 +579,16 @@ static void enqueue_task(struct task_str
 }
 
 /*
+ * Put task to the end of the run list without the overhead of dequeue
+ * followed by enqueue.
+ */
+static void requeue_task(struct task_struct *p, prio_array_t *array)
+{
+	list_del(&p->run_list);
+	list_add_tail(&p->run_list, array->queue + p->prio);
+}
+
+/*
  * Used by the migration code - we pull tasks from the head of the
  * remote queue so we want these tasks to show up at the head of the
  * local queue:
@@ -2425,8 +2435,7 @@ void scheduler_tick(void)
 			set_tsk_need_resched(p);
 
 			/* put it at the end of the queue: */
-			dequeue_task(p, rq->active);
-			enqueue_task(p, rq->active);
+			requeue_task(p, rq->active);
 		}
 		goto out_unlock;
 	}
@@ -2467,10 +2476,8 @@ void scheduler_tick(void)
 			(p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
 			(p->array == rq->active)) {
 
-			dequeue_task(p, rq->active);
+			requeue_task(p, rq->active);
 			set_tsk_need_resched(p);
-			p->prio = effective_prio(p);
-			enqueue_task(p, rq->active);
 		}
 	}
 out_unlock:
@@ -3569,8 +3576,14 @@ asmlinkage long sys_sched_yield(void)
 	} else if (!rq->expired->nr_active)
 		schedstat_inc(rq, yld_exp_empty);
 
-	dequeue_task(current, array);
-	enqueue_task(current, target);
+	if (array != target) {
+		dequeue_task(current, array);
+		enqueue_task(current, target);
+	} else
+		/*
+		 * requeue_task is cheaper so perform that if possible.
+		 */
+		requeue_task(current, array);
 
 	/*
 	 * Since we are going to call schedule() anyway, there's


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]

Re: [PATCH] add requeue task

[Nick Piggin]

Con Kolivas wrote:
> add requeue task
> 
> 
> 
> ------------------------------------------------------------------------
> 
> We can requeue tasks for cheaper then doing a complete dequeue followed by
> an enqueue. Add the requeue_task function and perform it where possible.
> 
> Change the granularity code to requeue tasks at their best priority
> instead of changing priority while they're running. This keeps tasks at
> their top interactive level during their whole timeslice.
> 

I wonder... these things are all in sufficiently rarely used places,
that the icache miss might be more costly than the operations saved.

But....

> Signed-off-by: Con Kolivas <kernel@kolivas.org>
> 
> Index: linux-2.6.10-rc1-mm2/kernel/sched.c
> ===================================================================
> --- linux-2.6.10-rc1-mm2.orig/kernel/sched.c	2004-11-02 14:48:54.686316718 +1100
> +++ linux-2.6.10-rc1-mm2/kernel/sched.c	2004-11-02 14:52:51.805763544 +1100
> @@ -579,6 +579,16 @@ static void enqueue_task(struct task_str
>  }
>  
>  /*
> + * Put task to the end of the run list without the overhead of dequeue
> + * followed by enqueue.
> + */
> +static void requeue_task(struct task_struct *p, prio_array_t *array)
> +{
> +	list_del(&p->run_list);
> +	list_add_tail(&p->run_list, array->queue + p->prio);
> +}
> +
> +/*
>   * Used by the migration code - we pull tasks from the head of the
>   * remote queue so we want these tasks to show up at the head of the
>   * local queue:
> @@ -2425,8 +2435,7 @@ void scheduler_tick(void)
>  			set_tsk_need_resched(p);
>  
>  			/* put it at the end of the queue: */
> -			dequeue_task(p, rq->active);
> -			enqueue_task(p, rq->active);
> +			requeue_task(p, rq->active);
>  		}
>  		goto out_unlock;
>  	}
> @@ -2467,10 +2476,8 @@ void scheduler_tick(void)
>  			(p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
>  			(p->array == rq->active)) {
>  
> -			dequeue_task(p, rq->active);
> +			requeue_task(p, rq->active);
>  			set_tsk_need_resched(p);
> -			p->prio = effective_prio(p);
> -			enqueue_task(p, rq->active);
>  		}
>  	}
>  out_unlock:

This isn't a 1:1 transformation. Looks like the effective_prio there
might be superfluous, but if so that should be a different patch.

> @@ -3569,8 +3576,14 @@ asmlinkage long sys_sched_yield(void)
>  	} else if (!rq->expired->nr_active)
>  		schedstat_inc(rq, yld_exp_empty);
>  
> -	dequeue_task(current, array);
> -	enqueue_task(current, target);
> +	if (array != target) {
> +		dequeue_task(current, array);
> +		enqueue_task(current, target);
> +	} else
> +		/*
> +		 * requeue_task is cheaper so perform that if possible.
> +		 */
> +		requeue_task(current, array);
>  
>  	/*
>  	 * Since we are going to call schedule() anyway, there's
> 

Hmm if you have to go to this trouble I'd say its not worth it.
Ingo may want to weigh in though.

Re: [PATCH] add requeue task

[Nikita Danilov]

Nick Piggin writes:
 > Con Kolivas wrote:
 > > add requeue task
 > > 
 > > 
 > > 
 > > ------------------------------------------------------------------------
 > > 
 > > We can requeue tasks for cheaper then doing a complete dequeue followed by
 > > an enqueue. Add the requeue_task function and perform it where possible.
 > > 
 > > Change the granularity code to requeue tasks at their best priority
 > > instead of changing priority while they're running. This keeps tasks at
 > > their top interactive level during their whole timeslice.
 > > 
 > 
 > I wonder... these things are all in sufficiently rarely used places,
 > that the icache miss might be more costly than the operations saved.
 > 
 > But....
 > 
 > > Signed-off-by: Con Kolivas <kernel@kolivas.org>
 > > 
 > > Index: linux-2.6.10-rc1-mm2/kernel/sched.c
 > > ===================================================================
 > > --- linux-2.6.10-rc1-mm2.orig/kernel/sched.c	2004-11-02 14:48:54.686316718 +1100
 > > +++ linux-2.6.10-rc1-mm2/kernel/sched.c	2004-11-02 14:52:51.805763544 +1100
 > > @@ -579,6 +579,16 @@ static void enqueue_task(struct task_str
 > >  }
 > >  
 > >  /*
 > > + * Put task to the end of the run list without the overhead of dequeue
 > > + * followed by enqueue.
 > > + */
 > > +static void requeue_task(struct task_struct *p, prio_array_t *array)
 > > +{
 > > +	list_del(&p->run_list);
 > > +	list_add_tail(&p->run_list, array->queue + p->prio);
 > > +}

Shouldn't this be

list_move_tail(&p->run_list, array->queue + p->prio);

?

Nikita.

Re: [PATCH] add requeue task

[Nick Piggin]

Nikita Danilov wrote:
> Nick Piggin writes:
>  > Con Kolivas wrote:
>  > > add requeue task

>  > >  /*
>  > > + * Put task to the end of the run list without the overhead of dequeue
>  > > + * followed by enqueue.
>  > > + */
>  > > +static void requeue_task(struct task_struct *p, prio_array_t *array)
>  > > +{
>  > > +	list_del(&p->run_list);
>  > > +	list_add_tail(&p->run_list, array->queue + p->prio);
>  > > +}
> 
> Shouldn't this be
> 
> list_move_tail(&p->run_list, array->queue + p->prio);
> 
> ?
> 

I think it should indeed.

Re: [PATCH] add requeue task

[Con Kolivas]

[-- Attachment #1: Type: text/plain, Size: 410 bytes --]

Nikita Danilov wrote:
>  > Con Kolivas wrote:
>  > > +	list_del(&p->run_list);
>  > > +	list_add_tail(&p->run_list, array->queue + p->prio);
>  > > +}
> 
> Shouldn't this be
> 
> list_move_tail(&p->run_list, array->queue + p->prio);

Yes indeed thanks! Fortunately they're one and the same thing. I've 
already resent this patch once, let akpm's tree settle for a bit before 
I throw more at him.

Cheers,
Con

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]

Re: [PATCH] add requeue task

[Ingo Molnar]

* Con Kolivas <kernel@kolivas.org> wrote:

> add requeue task

ack for this bit, but please split this one out:

| Change the granularity code to requeue tasks at their best priority
| instead of changing priority while they're running. This keeps tasks 
| at their top interactive level during their whole timeslice.

this is a behavioral change and should go into the 'possible negative
effect on interactivity' bucket. (of course it could very likely have a
positive effect as well - the bucket is just to separate the risks.)

	Ingo

Re: [PATCH] add requeue task

[Con Kolivas]

[-- Attachment #1: Type: text/plain, Size: 796 bytes --]

Ingo Molnar wrote:
> * Con Kolivas <kernel@kolivas.org> wrote:
> 
> 
>>add requeue task
> 
> 
> ack for this bit, but please split this one out:
> 
> | Change the granularity code to requeue tasks at their best priority
> | instead of changing priority while they're running. This keeps tasks 
> | at their top interactive level during their whole timeslice.
> 
> this is a behavioral change and should go into the 'possible negative
> effect on interactivity' bucket. (of course it could very likely have a
> positive effect as well - the bucket is just to separate the risks.)

Actually I'd like to say I did it for positive effect to counter the 
change that occurred with dropping interactive credit. That was what I 
found in my testing, and I'd like them both to go together into -mm.

Con

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]

Re: [PATCH] add requeue task

[Ingo Molnar]

* Con Kolivas <kernel@kolivas.org> wrote:

> >| Change the granularity code to requeue tasks at their best priority
> >| instead of changing priority while they're running. This keeps tasks 
> >| at their top interactive level during their whole timeslice.
> >
> >this is a behavioral change and should go into the 'possible negative
> >effect on interactivity' bucket. (of course it could very likely have a
> >positive effect as well - the bucket is just to separate the risks.)
> 
> Actually I'd like to say I did it for positive effect to counter the
> change that occurred with dropping interactive credit. That was what I
> found in my testing, and I'd like them both to go together into -mm.

just in case my splitout comment wasnt clear: ack for that fix too,
conditional on good -mm exposure. Unlike the interactive_credit change i
think this one would be borderline doable for 2.6.10 if in -mm for a
couple of weeks at least, because the regression fixed by this is fresh
in 2.6.9.

	Ingo

[PATCH] requeue at granularity intervals

[Con Kolivas]

[-- Attachment #1.1: Type: text/plain, Size: 34 bytes --]

requeue at granularity intervals


[-- Attachment #1.2: sched-requeue_granularity.diff --]
[-- Type: text/x-patch, Size: 834 bytes --]

Change the granularity code to requeue tasks at their best priority
instead of changing priority while they're running. This keeps tasks at
their top interactive level during their whole timeslice.

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

Index: linux-2.6.10-rc1-mm2/kernel/sched.c
===================================================================
--- linux-2.6.10-rc1-mm2.orig/kernel/sched.c	2004-11-03 00:55:48.638171430 +1100
+++ linux-2.6.10-rc1-mm2/kernel/sched.c	2004-11-03 00:57:50.863711719 +1100
@@ -2476,10 +2476,8 @@ void scheduler_tick(void)
 			(p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
 			(p->array == rq->active)) {
 
-			dequeue_task(p, rq->active);
+			requeue_task(p, rq->active);
 			set_tsk_need_resched(p);
-			p->prio = effective_prio(p);
-			enqueue_task(p, rq->active);
 		}
 	}
 out_unlock:


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]

[PATCH] add requeue task redo

[Con Kolivas]

[-- Attachment #1.1: Type: text/plain, Size: 24 bytes --]

add requeue task redo



[-- Attachment #1.2: sched-add_requeue_task-1.diff --]
[-- Type: text/x-patch, Size: 1682 bytes --]

We can requeue tasks for cheaper then doing a complete dequeue followed by
an enqueue. Add the requeue_task function and perform it where possible.

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

Index: linux-2.6.10-rc1-mm2/kernel/sched.c
===================================================================
--- linux-2.6.10-rc1-mm2.orig/kernel/sched.c	2004-11-03 00:54:33.157137840 +1100
+++ linux-2.6.10-rc1-mm2/kernel/sched.c	2004-11-03 00:55:48.638171430 +1100
@@ -579,6 +579,16 @@ static void enqueue_task(struct task_str
 }
 
 /*
+ * Put task to the end of the run list without the overhead of dequeue
+ * followed by enqueue.
+ */
+static void requeue_task(struct task_struct *p, prio_array_t *array)
+{
+	list_del(&p->run_list);
+	list_add_tail(&p->run_list, array->queue + p->prio);
+}
+
+/*
  * Used by the migration code - we pull tasks from the head of the
  * remote queue so we want these tasks to show up at the head of the
  * local queue:
@@ -2425,8 +2435,7 @@ void scheduler_tick(void)
 			set_tsk_need_resched(p);
 
 			/* put it at the end of the queue: */
-			dequeue_task(p, rq->active);
-			enqueue_task(p, rq->active);
+			requeue_task(p, rq->active);
 		}
 		goto out_unlock;
 	}
@@ -3569,8 +3578,14 @@ asmlinkage long sys_sched_yield(void)
 	} else if (!rq->expired->nr_active)
 		schedstat_inc(rq, yld_exp_empty);
 
-	dequeue_task(current, array);
-	enqueue_task(current, target);
+	if (array != target) {
+		dequeue_task(current, array);
+		enqueue_task(current, target);
+	} else
+		/*
+		 * requeue_task is cheaper so perform that if possible.
+		 */
+		requeue_task(current, array);
 
 	/*
 	 * Since we are going to call schedule() anyway, there's


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]