[patch] sched_yield in 2.2.x

[patch] sched_yield in 2.2.x

[Ivan Schreter]

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

Hello,

I'm not subscribed, so eventual replies please CC: to me (is@zapwerk.com).

Here is a 2-line patch that fixes sched_yield() call to actually really yield
the processor in 2.2.x kernels. I am using 2.2.16 and so have tested it in
2.2.16 only, but I suppose it should work with other kernels as well (there
seem not to be so many changes).

Bug description: When a process called sched_yield() it was properly marked for
reschedule and bit SCHED_YIELD for reschedule was properly set in p->policy.
However, prev_goodness() cleared this bit returning goodness 0 (I changed it to
-1 just to be sure this process isn't accidentally picked when there is other
process to run - maybe I'm wrong here, but 2.4.5 gives it also goodness -1, so
it should be OK). This was not that bad, but successive calls to goodness()
while searching for next process to run included last process, which had
meanwhile YIELD bit cleared and thus it's goodness value was calculated as
better. And we come to second line of the fix - do not consider prev process in
searching for next process to run, as it is anyway already selected as next by
default when no better process is found.

I hope that it will work in SMP environment as well (it should, since
schedule() seems to be mostly independent of UP/SMP).

And why do I want to use sched_yield()? Well, to implement user-space
longer-duration locks which don't consume the whole timeslice when waiting, but
rather relinquish processor to other task so it finishes it's work in critical
region sooner.

It's funny nobody has fixed this by now, but as I've seen there were couple
of discussion about sched_yield() already... I come probably too late...

Ivan Schreter
is@zapwerk.com

[-- Attachment #2: sched_patch.diff --]
[-- Type: text/plain, Size: 522 bytes --]

--- kernel/sched.c.orig	Wed May 30 01:17:24 2001
+++ kernel/sched.c	Wed May 30 01:41:34 2001
@@ -196,7 +196,7 @@
 {
 	if (p->policy & SCHED_YIELD) {
 		p->policy &= ~SCHED_YIELD;
-		return 0;
+		return -1;
 	}
 	return goodness(prev, p, this_cpu);
 }
@@ -729,7 +729,7 @@
  * list, so our list starting at "p" is essentially fixed.
  */
 	while (p != &init_task) {
-		if (can_schedule(p)) {
+		if (p != prev && can_schedule(p)) {
 			int weight = goodness(prev, p, this_cpu);
 			if (weight > c)
 				c = weight, next = p;

Re: [patch] sched_yield in 2.2.x

[george anzinger]

Ivan Schreter wrote:
> 
> Hello,
> 
> I'm not subscribed, so eventual replies please CC: to me (is@zapwerk.com).
> 
> Here is a 2-line patch that fixes sched_yield() call to actually really yield
> the processor in 2.2.x kernels. I am using 2.2.16 and so have tested it in
> 2.2.16 only, but I suppose it should work with other kernels as well (there
> seem not to be so many changes).
> 
> Bug description: When a process called sched_yield() it was properly marked for
> reschedule and bit SCHED_YIELD for reschedule was properly set in p->policy.
> However, prev_goodness() cleared this bit returning goodness 0 (I changed it to
> -1 just to be sure this process isn't accidentally picked when there is other
> process to run - maybe I'm wrong here, but 2.4.5 gives it also goodness -1, so
> it should be OK). This was not that bad, but successive calls to goodness()

The -1 is better than 0 since 0 will trigger a recalc if no other tasks
have any time left.  (Or do you want this to happen?  As you have it,
the yielding task will get control if all other tasks in the run list
have zero counters.  Seems like the recalculation should happen to find
a better candidate.)

The real problem with this patch is that if a real time task yields, the
patch will cause the scheduler to pick a lower priority task or a
SCHED_OTHER task.  This one is not so easy to solve.  You want to scan
the run_list in the proper order so that the real time task will be the
last pick at its priority.  Problem is, the pre load with the prev task
is out of order.  You might try: http://rtsched.sourceforge.net/

> while searching for next process to run included last process, which had
> meanwhile YIELD bit cleared and thus it's goodness value was calculated as
> better. And we come to second line of the fix - do not consider prev process in
> searching for next process to run, as it is anyway already selected as next by
> default when no better process is found.
> 
> I hope that it will work in SMP environment as well (it should, since
> schedule() seems to be mostly independent of UP/SMP).
> 
> And why do I want to use sched_yield()? Well, to implement user-space
> longer-duration locks which don't consume the whole timeslice when waiting, but
> rather relinquish processor to other task so it finishes it's work in critical
> region sooner.
> 
> It's funny nobody has fixed this by now, but as I've seen there were couple
> of discussion about sched_yield() already... I come probably too late...
> 
> Ivan Schreter
> is@zapwerk.com
> 
>   ------------------------------------------------------------------------
>                        Name: sched_patch.diff
>    sched_patch.diff    Type: Plain Text (text/plain)
>                    Encoding: base64

Re: [patch] sched_yield in 2.2.x

[Ivan Schreter]

Hello,

I'm not subscribed, so replies please CC: to me.

[...]

> > (I changed it to -1 just to be sure this process isn't accidentally
> > picked when there is other process to run - maybe I'm wrong here, but
> > 2.4.5 gives it also goodness -1, so it should be OK).
[...]
> The -1 is better than 0 since 0 will trigger a recalc if no other tasks
> have any time left.  (Or do you want this to happen?  As you have it,
> the yielding task will get control if all other tasks in the run list
> have zero counters.  Seems like the recalculation should happen to find
> a better candidate.)

Yes, I think that is OK according to specs. If we get a recalc, then we get
control anyway, since we have some time left when calling sched_yield(). Or am
I wrong here? Anyway, it performs quite well in tests...

> The real problem with this patch is that if a real time task yields, the
> patch will cause the scheduler to pick a lower priority task or a
> SCHED_OTHER task.  This one is not so easy to solve.  You want to scan
> the run_list in the proper order so that the real time task will be the
> last pick at its priority.  Problem is, the pre load with the prev task
> is out of order.  You might try: http://rtsched.sourceforge.net/

Well, let's look at it this way: real-time tasks may want to yield when they
are waiting for something to happen that is not system-controlled (like a
user-mode spinlock). Otherwise they would be waiting in (un)interruptible sleep
controlled by the kernel. So when a RR task yields, then it yields because some
condition isn't met. So it has to wait anyway. Scheduling a lower
priority task in the meantime will do only good to the system IMHO.

I know this is not quite standard, but to make it work standards-compliant
(task will continue to run if there are no other tasks blabla) it is enough to
check # of runnable tasks in the run queue in sys_sched_yield() and return
immediately if we are the only task running. I can implement that. Anybody
thinks it's worth it?

Ivan Schreter
is@zapwerk.com

Re: [patch] sched_yield in 2.2.x - version 2

[Ivan Schreter]

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

Hello,

please CC: replies to me as I am not subscribed to the list.

> The real problem with this patch is that if a real time task yields, the
> patch will cause the scheduler to pick a lower priority task or a
> SCHED_OTHER task.  This one is not so easy to solve.  You want to scan
> the run_list in the proper order so that the real time task will be the
> last pick at its priority.  Problem is, the pre load with the prev task
> is out of order.  You might try: http://rtsched.sourceforge.net/

No it's not a problem at all, since RR tasks will just be moved to the end of
the queue and no SCHED_YIELD flag is set for them => no lower-priority task may
be scheduled.

However, I found a bug in my own patch :-)
The problem is that when a process yields and no process has a timeslice left,
recalc is called. But then we lose YIELD flag once again. So the simple
solution (and hopefully this time right :-) was to NOT clear YIELD flag at all
before exit from schedule() and move test for this flag from goodness_prev() to
goodness() function (getting rid of goodness_prev() altogether).

However, one of my tests still show strange behavior, so maybe you will get 3rd
version of the patch :-) Anyway, I got good 30% performance boost for
high-contention case in user-space spinlocks when sched_yield() is working
right.

Another function that would be very interesting is possibility to give up our
timeslice to specific other process. This way I could transfer control to other
process/thread that owns the lock directly so that process/thread may finish
working with the lock. This can again speed up everything. When I have now 4
processes contending for a lock, I get performance 1x. However, when there are
20 processes contending, performance is only 0.7x. I suppose this is due to
excessive context switches. I will try to implement something like
"sched_switchto" to switch to specific pid (from user space) and see if that
helps. Or is there such a function already?

Ivan Schreter
is@zapwerk.com

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: sched_patch.diff --]
[-- Type: text/x-c; name="sched_patch.diff", Size: 1636 bytes --]

--- kernel/sched.c.orig	Wed May 30 01:17:24 2001
+++ kernel/sched.c	Wed May 30 12:30:03 2001
@@ -145,6 +145,11 @@
 {
 	int weight;
 
+	if (p->policy & SCHED_YIELD) {
+		/* do not schedule yielded process now */
+		return -1;
+	}
+
 	/*
 	 * Realtime process, select the first one on the
 	 * runqueue (taking priorities within processes
@@ -183,25 +188,6 @@
 }
 
 /*
- * subtle. We want to discard a yielded process only if it's being
- * considered for a reschedule. Wakeup-time 'queries' of the scheduling
- * state do not count. Another optimization we do: sched_yield()-ed
- * processes are runnable (and thus will be considered for scheduling)
- * right when they are calling schedule(). So the only place we need
- * to care about SCHED_YIELD is when we calculate the previous process'
- * goodness ...
- */
-static inline int prev_goodness (struct task_struct * prev,
-					struct task_struct * p, int this_cpu)
-{
-	if (p->policy & SCHED_YIELD) {
-		p->policy &= ~SCHED_YIELD;
-		return 0;
-	}
-	return goodness(prev, p, this_cpu);
-}
-
-/*
  * the 'goodness value' of replacing a process on a given CPU.
  * positive value means 'replace', zero or negative means 'dont'.
  */
@@ -740,6 +726,10 @@
 	/* Do we need to re-calculate counters? */
 	if (!c)
 		goto recalculate;
+
+	/* clean up potential SCHED_YIELD bit */
+	prev->policy &= ~SCHED_YIELD;
+
 	/*
 	 * from this point on nothing can prevent us from
 	 * switching to the next task, save this fact in
@@ -809,7 +799,7 @@
 	}
 
 still_running:
-	c = prev_goodness(prev, prev, this_cpu);
+	c = goodness(prev, prev, this_cpu);
 	next = prev;
 	goto still_running_back;