sched_yield in 2.2.x

Hello,

I'm not subscribed, so eventual replies please CC: to me ([email protected]).

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
[email protected]

@@ -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;

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/

Hello,

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

[...]

[...]

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...

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
[email protected]

Hello,

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

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
[email protected]

@@ -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;