From: Mike Galbraith <efault@gmx.de>
To: Davide Libenzi <davidel@xmailserver.org>
Cc: Valdis.Kletnieks@vt.edu,
linux kernel mailing list <linux-kernel@vger.kernel.org>
Subject: [NOTAPATCH] Re: [PATCH] O6int for interactivity
Date: Mon, 21 Jul 2003 14:39:21 +0200 [thread overview]
Message-ID: <5.2.1.1.2.20030721143309.01bb95f8@pop.gmx.net> (raw)
In-Reply-To: <Pine.LNX.4.55.0307201715130.3548@bigblue.dev.mcafeelabs.co m>
[-- Attachment #1: Type: text/plain, Size: 1314 bytes --]
At 05:21 PM 7/20/2003 -0700, Davide Libenzi wrote:
>On Sat, 19 Jul 2003, Mike Galbraith wrote:
>
> > >Everything that will make the scheduler to say "ok, I gave enough time to
> > >interactive tasks, now I'm really going to spin one from the masses" will
> > >work. Having a clean solution would not be an option here.
> >
> > ... just as soon as I get my decidedly unclean work-around functioning at
> > least as well as it did for plain old irman. irman2 is _much_ more evil
> > than irman ever was (wow, good job!). I thought it'd be a half an hour
> > tops. This little bugger shows active starvation, expired starvation,
> > priority inflation, _and_ interactive starvation (i have to keep inventing
> > new terms to describe things i see.. jeez this is a good testcase).
>
>Yes, the problem is not only the expired tasks starvation. Anything in
>the active array that reside underneath the lower priority value of the
>range irman2 tasks oscillate inbetween, will experience a "CPU time eclipse".
>And you do not even need a smoked glass to look at it :)
I think I whipped the obnoxious little bugger. Comments on the attached
[kiss] approach?
I don't like what gpm tells me while irman2 is running with this diff, but
hiccup hiccup is a heck of lot better than terminal starvation.
-Mike
[-- Attachment #2: xx.diff --]
[-- Type: application/octet-stream, Size: 3586 bytes --]
--- linux-2.6.0-test1.virgin/kernel/sched.c.org Sat Jul 19 09:42:12 2003
+++ linux-2.6.0-test1.virgin/kernel/sched.c Mon Jul 21 14:29:26 2003
@@ -76,6 +76,12 @@
#define MAX_SLEEP_AVG (10*HZ)
#define STARVATION_LIMIT (10*HZ)
#define NODE_THRESHOLD 125
+#define END_IA_PRIO (NICE_TO_PRIO(1 - INTERACTIVE_DELTA))
+#define INTERVAL (HZ)
+#define DURATION_PERCENT 10
+#define DURATION (INTERVAL * DURATION_PERCENT / 100)
+#define INTERVAL_EXPIRED(rq) (time_after(jiffies, \
+ (rq)->interval_ts + ((rq)->idx ? DURATION : INTERVAL)))
/*
* If a task is 'interactive' then we reinsert it in the active
@@ -158,7 +164,7 @@
struct runqueue {
spinlock_t lock;
unsigned long nr_running, nr_switches, expired_timestamp,
- nr_uninterruptible;
+ nr_uninterruptible, interval_ts;
task_t *curr, *idle;
struct mm_struct *prev_mm;
prio_array_t *active, *expired, arrays[2];
@@ -171,6 +177,7 @@
struct list_head migration_queue;
atomic_t nr_iowait;
+ int idx;
};
static DEFINE_PER_CPU(struct runqueue, runqueues);
@@ -1166,6 +1173,23 @@
STARVATION_LIMIT * ((rq)->nr_running) + 1)))
/*
+ * Must be called with the runqueue lock held.
+ */
+static void __requeue_one_expired(runqueue_t *rq)
+{
+ int idx = sched_find_first_bit(rq->expired->bitmap);
+ struct list_head *queue;
+ task_t *p;
+
+ if (idx >= MAX_PRIO)
+ return;
+ queue = rq->expired->queue + idx;
+ p = list_entry(queue->next, task_t, run_list);
+ dequeue_task(p, p->array);
+ enqueue_task(p, rq->active);
+}
+
+/*
* This function gets called by the timer code, with HZ frequency.
* We call it with interrupts disabled.
*
@@ -1242,10 +1266,35 @@
if (!rq->expired_timestamp)
rq->expired_timestamp = jiffies;
enqueue_task(p, rq->expired);
- } else
+ } else {
enqueue_task(p, rq->active);
+ if (rq->idx)
+ __requeue_one_expired(rq);
+ }
+ } else if (INTERVAL_EXPIRED(rq)) {
+ /*
+ * If we haven't run a non-interactive task within our
+ * interval, we take this as a hint that we may have
+ * starvation in progress. Trigger a queue walk-down,
+ * and walk until either non-interactive tasks have
+ * received DURATION ticks, or we hit the bottom.
+ */
+ if (TASK_INTERACTIVE(p)) {
+ prio_array_t *array = p->array;
+
+ /* Requeue the hight priority expired task... */
+ __requeue_one_expired(rq);
+ /* and tell the scheduler where to start walking. */
+ rq->idx = find_next_bit(array->bitmap, MAX_PRIO, 1 + p->prio);
+ if (rq->idx >= MAX_PRIO)
+ rq->idx = 0;
+ } else
+ rq->idx = 0;
+ rq->interval_ts = jiffies;
}
out_unlock:
+ if (rq->idx && TASK_INTERACTIVE(p))
+ rq->interval_ts++;
spin_unlock(&rq->lock);
out:
rebalance_tick(rq, 0);
@@ -1312,6 +1361,8 @@
#endif
next = rq->idle;
rq->expired_timestamp = 0;
+ rq->interval_ts = jiffies;
+ rq->idx = 0;
goto switch_tasks;
}
@@ -1329,6 +1380,17 @@
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, task_t, run_list);
+ if (unlikely(rq->idx)) {
+ if(!rt_task(next)) {
+ int index = find_next_bit(array->bitmap, MAX_PRIO, rq->idx);
+ if (index < MAX_PRIO) {
+ queue = array->queue + index;
+ next = list_entry(queue->next, task_t, run_list);
+ if (index < END_IA_PRIO)
+ rq->idx = index + 1;
+ }
+ }
+ }
switch_tasks:
prefetch(next);
@@ -2497,6 +2559,7 @@
rq = cpu_rq(i);
rq->active = rq->arrays;
rq->expired = rq->arrays + 1;
+ rq->interval_ts = INITIAL_JIFFIES;
spin_lock_init(&rq->lock);
INIT_LIST_HEAD(&rq->migration_queue);
atomic_set(&rq->nr_iowait, 0);
next prev parent reply other threads:[~2003-07-21 12:21 UTC|newest]
Thread overview: 43+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-07-16 14:30 [PATCH] O6int for interactivity Con Kolivas
2003-07-16 15:22 ` Felipe Alfaro Solana
2003-07-16 19:55 ` Marc-Christian Petersen
2003-07-16 17:08 ` Valdis.Kletnieks
2003-07-16 21:59 ` Wiktor Wodecki
2003-07-16 22:30 ` Con Kolivas
2003-07-16 22:12 ` Davide Libenzi
2003-07-17 0:33 ` Con Kolivas
2003-07-17 0:35 ` Davide Libenzi
2003-07-17 1:12 ` Con Kolivas
2003-07-17 0:48 ` Wade
2003-07-17 1:15 ` Con Kolivas
2003-07-17 1:27 ` Eugene Teo
2003-07-17 3:05 ` Wes Janzen
2003-07-17 9:05 ` Alex Riesen
2003-07-17 9:14 ` Con Kolivas
2003-07-18 7:38 ` Alex Riesen
[not found] ` <Pine.LNX.4.44.0307251628500.26172-300000@localhost.localdomain>
2003-07-25 19:40 ` Alex Riesen
[not found] ` <Pine.LNX.4.55.0307161241280.4787@bigblue.dev.mcafeelabs.co m>
2003-07-18 5:38 ` Mike Galbraith
2003-07-18 6:34 ` Nick Piggin
2003-07-18 10:18 ` Mike Galbraith
2003-07-18 10:31 ` Wiktor Wodecki
2003-07-18 10:43 ` Con Kolivas
2003-07-18 11:34 ` Wiktor Wodecki
2003-07-18 11:38 ` Nick Piggin
2003-07-19 10:59 ` Wiktor Wodecki
2003-07-18 15:46 ` Mike Galbraith
2003-07-18 16:52 ` Davide Libenzi
2003-07-18 17:05 ` Davide Libenzi
2003-07-18 17:39 ` Valdis.Kletnieks
2003-07-18 19:31 ` Davide Libenzi
[not found] ` <Pine.LNX.4.55.0307181038450.5608@bigblue.dev.mcafeelabs.co m>
2003-07-18 20:31 ` Mike Galbraith
2003-07-18 20:38 ` Davide Libenzi
[not found] ` <Pine.LNX.4.55.0307181333520.5608@bigblue.dev.mcafeelabs.co m>
2003-07-19 17:04 ` Mike Galbraith
2003-07-21 0:21 ` Davide Libenzi
[not found] ` <Pine.LNX.4.55.0307201715130.3548@bigblue.dev.mcafeelabs.co m>
2003-07-21 5:36 ` Mike Galbraith
2003-07-21 12:39 ` Mike Galbraith [this message]
2003-07-21 17:13 ` [NOTAPATCH] " Mike Galbraith
2003-07-18 14:24 ` Con Kolivas
2003-07-18 15:50 ` Mike Galbraith
2003-07-18 13:46 ` Davide Libenzi
[not found] ` <Pine.LNX.4.55.0307180630450.5077@bigblue.dev.mcafeelabs.co m>
2003-07-18 15:41 ` Mike Galbraith
[not found] ` <Pine.LNX.4.55.0307180951050.5608@bigblue.dev.mcafeelabs.co m>
2003-07-18 18:49 ` Mike Galbraith
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=5.2.1.1.2.20030721143309.01bb95f8@pop.gmx.net \
--to=efault@gmx.de \
--cc=Valdis.Kletnieks@vt.edu \
--cc=davidel@xmailserver.org \
--cc=linux-kernel@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).