Re: [PATCH] V-3.0 Single Priority Array O(1) CPU Scheduler Evaluation
From: Peter Williams
Date: Mon Aug 02 2004 - 22:41:57 EST
William Lee Irwin III wrote:
William Lee Irwin III wrote:
Hmm. Given do_promotions() I'd expect fenceposts, not iteration over
the priority levels of the runqueue.
On Tue, Aug 03, 2004 at 10:33:36AM +1000, Peter Williams wrote:
I don't understand what you mean. Do you mean something like the more
complex promotion mechanism in the (earlier) EBS scheduler where tasks
only get promoted if they've been on a queue without being serviced
within a given time?
An array of size N can be rotated in O(1) time
And with a smaller constant than my do_promotions(). :-)
if an integer is kept
along with it to represent an offset that has to be added to externally-
visible indices mod N to recover the true index.
OK. Now I understand.
The main reason that I didn't do something like that is that
(considering that real time tasks don't get promoted) it would complicate:
1. the selection (in schedule()) of the next task to be run as it would
no longer be a case of just finding the first bit in the bitmap,
2. determining the appropriate list to put the task on in
enqueue_task(), etc., and
3. determining the right bit to turn off in the bit map when dequeuing
the last task in a slot.
As these are frequent operations compared to promotion I thought it
would be better to leave the complexity in do_promotion(). Now that
you've caused me to think about it again I realize that the changes in
the above areas may not be as complicated as I thought would be
necessary. So I'll give it some more thought.
Thanks for the suggestion
Peter
--
Peter Williams pwil3058@xxxxxxxxxxxxxx
"Learning, n. The kind of ignorance distinguishing the studious."
-- Ambrose Bierce
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/