Date: Fri, 13 Feb 2004 06:31:39 +0900 From: Taku YAMAMOTO <taku@cent.saitama-u.ac.jp> To: current@FreeBSD.org Subject: SCHED_ULE sometimes puts P_SA processes into ksq_next unnecessarily Message-ID: <20040213063139.71298ea9.taku@cent.saitama-u.ac.jp>
next in thread | raw e-mail | index | archive | help
This is a multi-part message in MIME format.
--Multipart=_Fri__13_Feb_2004_06_31_39_+0900_pWUuvlQLWQvsE=m1
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
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@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@cent.saitama-u.ac.jp>
| __ <
Post Scriptum: Sorry for no concrete statistics :)
--Multipart=_Fri__13_Feb_2004_06_31_39_+0900_pWUuvlQLWQvsE=m1
Content-Type: text/plain;
name="ule_runq_preserve.patch"
Content-Disposition: attachment;
filename="ule_runq_preserve.patch"
Content-Transfer-Encoding: 7bit
--- 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:
/*
--Multipart=_Fri__13_Feb_2004_06_31_39_+0900_pWUuvlQLWQvsE=m1
Content-Type: text/plain;
name="ule_runq_reset.patch"
Content-Disposition: attachment;
filename="ule_runq_reset.patch"
Content-Transfer-Encoding: 7bit
--- 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);
--Multipart=_Fri__13_Feb_2004_06_31_39_+0900_pWUuvlQLWQvsE=m1
Content-Type: text/plain;
name="ule_sameas_sa.patch"
Content-Disposition: attachment;
filename="ule_sameas_sa.patch"
Content-Transfer-Encoding: 7bit
--- 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);
--Multipart=_Fri__13_Feb_2004_06_31_39_+0900_pWUuvlQLWQvsE=m1--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040213063139.71298ea9.taku>