Messages in this thread |  | | | Date | Tue, 03 Aug 2004 13:39:02 +1000 | | From | Peter Williams <> | | Subject | Re: [PATCH] V-3.0 Single Priority Array O(1) CPU Scheduler Evaluation |
| |
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@bigpond.net.au
"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@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
|  |