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

[Mike Galbraith <efault@gmx.de>]

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