Re: [patch] new scheduler

Greg Lindahl (lindahl@cs.virginia.edu)
Mon, 10 May 1999 12:39:58 -0400 (EDT)

> Greg Lindal suggested this alternate solution for schedule selection:
>
> while (p!= &init_task)
> {
> if (can_schedule())
> {
> int weight = goodness(p,prev,this_cpu);
> if (weight>=0)
> {c=weight, next=p; break;}
> } p = p->next_run
> }

This was just a straw man to test if the overhead could be
dramatically reduced by an O(1) algorithm. It is possible to make the
current algorithm O(1).

Which processes can be scheduled?

1) The one with the highest priority
2) The one with the highest prority on the same CPU (+PROC_CHANGE_PENALTY)
3) The current process (+1)

If you keep the runq sorted by priority, you can do a small search to
find (2) and (3); it ought to be a lot cheaper than O(N).

I haven't looked at 2.2.8, though, so all this may be moot.

-- g

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/