[NOTAPATCH] Re: [PATCH] O6int for interactivity

Mike Galbraith
2003-07-21T12:21:28Z

[-- 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);