SCHED_ULE sometimes puts P_SA processes into ksq_next unnecessarily

[Taku YAMAMOTO]

I observed that SCHED_ULE doesn't give fair amount of CPU time to processes
which are using scheduler-activation-based threads when other
(semi-)CPU-intensive, non-P_SA processes are running.

# for example, browsing a complicated web page while compiling some
# amount of code with nice 0.

After spending several hours, I finally tracked it down to the following
code in sched_ule.c:
<code>
**** snip ****
void
sched_switch(struct thread *td)
{
**** snip ****
		if (TD_IS_RUNNING(td)) {
			if (td->td_proc->p_flag & P_SA) {
				kseq_load_rem(KSEQ_CPU(ke->ke_cpu), ke);
				setrunqueue(td);
			} else
				kseq_runq_add(KSEQ_SELF(), ke);
**** snip ****
void
sched_add(struct thread *td)
{
**** snip ****
	case PRI_TIMESHARE:
		if (SCHED_CURR(kg, ke))
			ke->ke_runq = kseq->ksq_curr;
		else
			ke->ke_runq = kseq->ksq_next;
		break;
**** snip ****
</code>

The problem is that setrunqueue() calls sched_add(), which resets ke_runq,
thus non-interactive threads are likely to be put into ksq_next regardless
of however much slices remaining.

On the contrary, threads of !P_SA processes stay in ksq_curr unless slices
have been expired, since !P_SA case bypass setrunqueue() => sched_add()
path.

In order to reduce the difference, I tested three different strategies.

 1. preserve ke_runq in P_SA case (ule_runq_preserve.patch)

    This became a bit hackish, but I felt the characteristics of ULE were
    well preserved.

 2. set ke_runq to ksq_next if the given thread is considered
    non-interactive in !P_SA case (ule_runq_reset.patch)

    I felt that the scheduler behaves a bit like the SCHED_4BSD does, which
    I think is not good.

 3. use setrunqueue() (= sched_add()) in !P_SA case, too, like SCHED_4BSD
    does (ule_sameas_sa.patch)

    I felt that the scheduler behaves much more like the SCHED_4BSD (read: 
    good characteristics of ULE seemed to fade out), but it might be
    scientifically correct.

In either way, P_SA processes were given reasonable amount of CPU time
relative to the !P_SA processes, while with unmodified scheduler, most of
CPU time was eaten up by cc1plus(PRI=136..139) and nearly zero CPU to
epiphany-bin(PRI=92 or so).
# checked with top, epiphany+libpthread and compiling 4k-lines C++ program
# with CXXFLAGS='-pipe -O3 etc...', took several minutes on Pen2 at 300MHz

Since I am totally unfamilier with the scheduler things, all of the three
can be completely wrong or irrelevant to the problem. But I hope one of
them brings some lights to scheduler gulus.

Thank you for reading,
taku
-- 
-|-__   YAMAMOTO, Taku  <taku at cent.saitama-u.ac.jp>
 | __ <

Post Scriptum: Sorry for no concrete statistics :)

-------------- next part --------------
--- sched_ule.c.orig	Fri Feb 13 05:24:48 2004
+++ sched_ule.c	Fri Feb 13 05:26:56 2004
@@ -186,7 +186,7 @@
 #define	SCHED_INTERACTIVE(kg)						\
     (sched_interact_score(kg) < SCHED_INTERACT_THRESH)
 #define	SCHED_CURR(kg, ke)						\
-    (ke->ke_thread->td_priority != kg->kg_user_pri ||			\
+    (ke->ke_thread->td_priority < kg->kg_user_pri ||			\
     SCHED_INTERACTIVE(kg))
 
 /*
@@ -1167,9 +1167,13 @@
 	if ((ke->ke_flags & KEF_ASSIGNED) == 0) {
 		if (TD_IS_RUNNING(td)) {
 			if (td->td_proc->p_flag & P_SA) {
+				struct runq *rq;
+
+				rq = ke->ke_runq;
 				kseq_load_rem(KSEQ_CPU(ke->ke_cpu), ke);
+				ke->ke_runq = rq;
 				setrunqueue(td);
-			} else 
+			} else
 				kseq_runq_add(KSEQ_SELF(), ke);
 		} else {
 			if (ke->ke_runq) {
@@ -1579,10 +1583,12 @@
 		ke->ke_cpu = PCPU_GET(cpuid);
 		break;
 	case PRI_TIMESHARE:
-		if (SCHED_CURR(kg, ke))
-			ke->ke_runq = kseq->ksq_curr;
-		else
-			ke->ke_runq = kseq->ksq_next;
+		if (ke->ke_runq == NULL) {
+			if (SCHED_CURR(kg, ke))
+				ke->ke_runq = kseq->ksq_curr;
+			else
+				ke->ke_runq = kseq->ksq_next;
+		}
 		break;
 	case PRI_IDLE:
 		/*

-------------- next part --------------
--- sched_ule.c.orig	Fri Feb 13 05:24:48 2004
+++ sched_ule.c	Fri Feb 13 05:38:17 2004
@@ -186,7 +186,7 @@
 #define	SCHED_INTERACTIVE(kg)						\
     (sched_interact_score(kg) < SCHED_INTERACT_THRESH)
 #define	SCHED_CURR(kg, ke)						\
-    (ke->ke_thread->td_priority != kg->kg_user_pri ||			\
+    (ke->ke_thread->td_priority < kg->kg_user_pri ||			\
     SCHED_INTERACTIVE(kg))
 
 /*
@@ -1169,8 +1169,17 @@
 			if (td->td_proc->p_flag & P_SA) {
 				kseq_load_rem(KSEQ_CPU(ke->ke_cpu), ke);
 				setrunqueue(td);
-			} else 
+			} else {
+				struct ksegrp *kg;
+
+				kg = ke->ke_ksegrp;
+				if (kg->kg_pri_base == PRI_TIMESHARE &&
+				    !SCHED_CURR(kg, ke))
+					/* XXX - is the choice of kseq right? */
+					ke->ke_runq =
+					    KSEQ_CPU(ke->ke_cpu)->ksq_next;
 				kseq_runq_add(KSEQ_SELF(), ke);
+			}
 		} else {
 			if (ke->ke_runq) {
 				kseq_load_rem(KSEQ_CPU(ke->ke_cpu), ke);

-------------- next part --------------
--- sched_ule.c.orig	Fri Feb 13 05:24:48 2004
+++ sched_ule.c	Fri Feb 13 05:37:53 2004
@@ -186,7 +186,7 @@
 #define	SCHED_INTERACTIVE(kg)						\
     (sched_interact_score(kg) < SCHED_INTERACT_THRESH)
 #define	SCHED_CURR(kg, ke)						\
-    (ke->ke_thread->td_priority != kg->kg_user_pri ||			\
+    (ke->ke_thread->td_priority < kg->kg_user_pri ||			\
     SCHED_INTERACTIVE(kg))
 
 /*
@@ -1166,11 +1166,8 @@
 	 */
 	if ((ke->ke_flags & KEF_ASSIGNED) == 0) {
 		if (TD_IS_RUNNING(td)) {
-			if (td->td_proc->p_flag & P_SA) {
-				kseq_load_rem(KSEQ_CPU(ke->ke_cpu), ke);
-				setrunqueue(td);
-			} else 
-				kseq_runq_add(KSEQ_SELF(), ke);
+			kseq_load_rem(KSEQ_CPU(ke->ke_cpu), ke);
+			setrunqueue(td);
 		} else {
 			if (ke->ke_runq) {
 				kseq_load_rem(KSEQ_CPU(ke->ke_cpu), ke);