lkml.org 
[lkml]   [2007]   [Apr]   [15]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[PATCH] scheduler: fix the return of the first time_slice
At Sat, 14 Apr 2007 01:31:12 +1000,
Con Kolivas wrote:
>
> On Monday 09 April 2007 16:09, Andrew Morton wrote:
> > On Sat, 07 Apr 2007 16:31:39 +0900 Satoru Takeuchi
> <takeuchi_satoru@jp.fujitsu.com> wrote:
> > > When I was examining the following program ...
> > >
> > > 1. There are a large amount of small jobs takes several msecs,
> > > and the number of job increases constantly.
> > > 2. The process creates a thread or a process per job (I examined both
> > > the thread model and the process model).
> > > 3. Each child process/thread does the assigned job and exit
> > > immediately.
> > >
> > > ... I found that the thread model's latency is longer than proess
> > > model's one against my expectation. It's because of the current
> > > sched_fork()/sched_exit() implementation as follows:
> > >
> > > a) On sched_fork, the creator share its timeslice with new process.
> > > b) On sched_exit, if the exiting process didn't exhaust its first
> > > timeslice yet, it gives its timeslice to the parent.
> > >
> > > It has no problem on the process model since the creator is the parent.
> > > However, on the thread model, the creator is not the parent, it is same
> > > as the creator's parent. Hence, on this kind of program, the creator
> > > can't retrieve shared timeslice and exausts its timeslice at a rate of
> > > knots. In addition, somehow, the parent (typically shell?) gets extra
> > > timeslice.
> > >
> > > I believe it's a bug and the exiting process should give its timeslice
> > > to the creator. Now I have some patch plan to fix this problem as follow:
> > >
> > > a) Add the field for the creator to task_struct. It needs extra memory.
> > > b) Doesn't add extra field and have thread's parent the creater, which
> > > is same as process creation. However it has many side effects, for
> > > example, we also need to change sys_getppid() implementation.
> > >
> > > What do you think? Any comments are welcome.
> >
> > This comes at an awkward time, because we might well merge the
> > staircase/deadline work into 2.6.22, and I think it rewrites the part of
> > the scheduler which is causing the problems you're observing.
> >
> > Has anyone verified that SD fixes this problem and the one at
> > http://lkml.org/lkml/2007/4/7/21 ?
>
> No, SD does nothing different in this regard. There is no notion of who made
> the thread and who the remaining timeslice should go to. As you say, some
> decision on sched_exit should probably be used to decide where to send it. In
> the absence of yet more fields in task_struct, the easiest thing to do would
> be to check if the the thread id is equal to the pid and if not, send it to
> the pid (or any parent of that if it no longer exists). Whether it's worth
> adding yet another field to task_struct to track this or not I do not have
> enough information to make an informed choice in this regard. Either way I'm
> low on patch-creation cycles so please feel free to provide your solution.

I wrote the patch fixing this problem. It's for 2.6.21-rc6 and works well.
I also examined the following load tests:

- Compile kernel with -j4 option continuously for 8 hours on i386 UP box.
- Compile kernel with -j48 option continuously for 2 hours on ia64 12 CPU
box.

Now I'm testing its 2.6.21-rc6-mm1(with SD) version and would submit it soon.

Thanks,

Satoru

---
Fix the return of the first time_slice
Currently exiting process takes back its first_time_slice to its
parent. If the task is created with CLONE_PARENT or CLONE_THREAD
flag, the parent is not the creator. Hence the creator can't
collect the time_slice and time_slice leak occurs.

To fix this problem, remove first_time_slice field of task_struct
and introduce time_slice_reaper field instead. The new field means
the task which exiting task should return its first_time_slice to,
and is NULL after exhausting its first time_slice.

Signed-off-by: Satoru Takeuchi <takeuchi_satoru@jp.fujitsu.com>

Index: linux-2.6.21-rc6.tsfix/kernel/exit.c
===================================================================
--- linux-2.6.21-rc6.tsfix.orig/kernel/exit.c 2007-04-13 20:53:11.000000000 +0900
+++ linux-2.6.21-rc6.tsfix/kernel/exit.c 2007-04-14 13:58:29.000000000 +0900
@@ -679,6 +679,8 @@
reaper = child_reaper(father);
break;
}
+ if (reaper->time_slice_reaper == father)
+ p->time_slice_reaper = NULL;
} while (reaper->exit_state);

/*
@@ -700,6 +702,8 @@

if (father == p->real_parent) {
/* reparent with a reaper, real father it's us */
+ if (p->time_slice_reaper == father)
+ p->time_slice_reaper = NULL;
choose_new_parent(p, reaper);
reparent_thread(p, father, 0);
} else {
@@ -721,6 +725,8 @@
}
list_for_each_safe(_p, _n, &father->ptrace_children) {
p = list_entry(_p, struct task_struct, ptrace_list);
+ if (p->time_slice_reaper == father)
+ p->time_slice_reaper = NULL;
choose_new_parent(p, reaper);
reparent_thread(p, father, 1);
}
Index: linux-2.6.21-rc6.tsfix/kernel/sched.c
===================================================================
--- linux-2.6.21-rc6.tsfix.orig/kernel/sched.c 2007-04-13 20:53:11.000000000 +0900
+++ linux-2.6.21-rc6.tsfix/kernel/sched.c 2007-04-14 01:27:20.000000000 +0900
@@ -1628,7 +1628,7 @@
* The remainder of the first timeslice might be recovered by
* the parent if the child exits early enough.
*/
- p->first_time_slice = 1;
+ p->time_slice_reaper = current;
current->time_slice >>= 1;
p->timestamp = sched_clock();
if (unlikely(!current->time_slice)) {
@@ -1739,19 +1739,23 @@
{
unsigned long flags;
struct rq *rq;
+ struct task_struct *reaper = p->time_slice_reaper;

/*
* If the child was a (relative-) CPU hog then decrease
* the sleep_avg of the parent as well.
*/
- rq = task_rq_lock(p->parent, &flags);
- if (p->first_time_slice && task_cpu(p) == task_cpu(p->parent)) {
- p->parent->time_slice += p->time_slice;
- if (unlikely(p->parent->time_slice > task_timeslice(p)))
- p->parent->time_slice = task_timeslice(p);
+ if (!reaper)
+ return;
+
+ rq = task_rq_lock(reaper, &flags);
+ if (task_cpu(p) == task_cpu(reaper)) {
+ reaper->time_slice += p->time_slice;
+ if (unlikely(reaper->time_slice > task_timeslice(reaper)))
+ reaper->time_slice = task_timeslice(reaper);
}
- if (p->sleep_avg < p->parent->sleep_avg)
- p->parent->sleep_avg = p->parent->sleep_avg /
+ if (p->sleep_avg < reaper->sleep_avg)
+ reaper->sleep_avg = reaper->sleep_avg /
(EXIT_WEIGHT + 1) * EXIT_WEIGHT + p->sleep_avg /
(EXIT_WEIGHT + 1);
task_rq_unlock(rq, &flags);
@@ -3153,7 +3157,7 @@
*/
if ((p->policy == SCHED_RR) && !--p->time_slice) {
p->time_slice = task_timeslice(p);
- p->first_time_slice = 0;
+ p->time_slice_reaper = NULL;
set_tsk_need_resched(p);

/* put it at the end of the queue: */
@@ -3166,7 +3170,7 @@
set_tsk_need_resched(p);
p->prio = effective_prio(p);
p->time_slice = task_timeslice(p);
- p->first_time_slice = 0;
+ p->time_slice_reaper = NULL;

if (!rq->expired_timestamp)
rq->expired_timestamp = jiffies;
Index: linux-2.6.21-rc6.tsfix/include/linux/sched.h
===================================================================
--- linux-2.6.21-rc6.tsfix.orig/include/linux/sched.h 2007-04-13 20:58:27.000000000 +0900
+++ linux-2.6.21-rc6.tsfix/include/linux/sched.h 2007-04-13 20:59:03.000000000 +0900
@@ -827,7 +827,8 @@

unsigned long policy;
cpumask_t cpus_allowed;
- unsigned int time_slice, first_time_slice;
+ unsigned int time_slice;
+ struct task_struct *time_slice_reaper;

#if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
struct sched_info sched_info;
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
\
 
 \ /
  Last update: 2007-04-16 04:21    [from the cache]
©2003-2011 Jasper Spaans