[Linux-ia64] Re: web page on O(1) scheduler

Mike Galbraith
2003-05-22T09:52:24Z

[-- Attachment #1: Type: text/plain, Size: 951 bytes --]

At 10:56 AM 5/21/2003 -0700, David Mosberger wrote:
> >>>>> On Wed, 21 May 2003 11:26:31 +0200, Mike Galbraith <efault@gmx.de>
> said:
>
> Mike> The page mentions persistent starvation. My own explorations
> Mike> of this issue indicate that the primary source is always
> Mike> selecting the highest priority queue.
>
>My working assumption is that the problem is a bug with the dynamic
>prioritization. The task receiving the signals calls sleep() after
>handling a signal and hence it's dynamic priority should end up higher
>than the priority of the task sending signals (since the sender never
>relinquishes the CPU voluntarily).
>
>However, I haven't actually had time to look at the relevant code, so
>I may be missing something. If you understand the issue better,
>please explain to me why this isn't a dynamic priority issue.

You're right, it looks like a corner case. It works fine here with the
attached diff.

-Mike

[-- Attachment #2: xx.diff --]
[-- Type: application/octet-stream, Size: 1553 bytes --]

--- linux-2.5.69.virgin/kernel/sched.c.org Wed May 21 07:45:00 2003
+++ linux-2.5.69.virgin/kernel/sched.c Thu May 22 11:06:12 2003
@@ -1264,7 +1264,7 @@
task_t *prev, *next;
runqueue_t *rq;
prio_array_t *array;
- struct list_head *queue;
+ struct list_head *head, *curr;
int idx;

/*
@@ -1286,7 +1286,6 @@
rq = this_rq();

release_kernel_lock(prev);
- prev->last_run = jiffies;
spin_lock_irq(&rq->lock);

/*
@@ -1303,6 +1302,9 @@
break;
}
default:
+ /* One sleep credit for releasing the cpu immediately. */
+ if (prev->last_run == jiffies && prev->sleep_avg < MAX_SLEEP_AVG)
+ prev->sleep_avg++;
deactivate_task(prev, rq);
case TASK_RUNNING:
;
@@ -1331,8 +1333,22 @@
}

idx = sched_find_first_bit(array->bitmap);
- queue = array->queue + idx;
- next = list_entry(queue->next, task_t, run_list);
+next_queue:
+ head = array->queue + idx;
+ curr = head->next;
+ next = list_entry(curr, task_t, run_list);
+ curr = curr->next;
+ /*
+ * If we are about to wrap back to the head of the queue,
+ * give a lower priority queue a chance to sneak one in.
+ */
+ if (idx == prev->prio && curr == head && array->nr_active > 1) {
+ int tmp = find_next_bit(array->bitmap, MAX_PRIO, ++idx);
+ if (tmp < MAX_PRIO) {
+ idx = tmp;
+ goto next_queue;
+ }
+ }

switch_tasks:
prefetch(next);
@@ -1342,6 +1358,7 @@
if (likely(prev != next)) {
rq->nr_switches++;
rq->curr = next;
+ prev->last_run = next->last_run = jiffies;

prepare_arch_switch(rq, next);
prev = context_switch(rq, prev, next);