scheduler going backwards solution?
Lloyd Wood <L.Wood@ee.surrey.ac.uk>
Wed, 8 Sep 1999 15:18:16 +0100 (BST)
On Wed, 8 Sep 1999, Sean Murphy wrote:
> > What is "added desk calendar wrapping feature"?
> > Heap as well as Calendar had a problem with re-ordering of
> > simultaneous events, but that has been fixed. Keeping the order the
> > same is useful for validations and lets different schedulers verify
> > each other.
> > Calendar is still the default because no one ventured to change it to
> > Heap. There is a hope that recent fixes are enough to keep that
> > 'backwards' error from reappearing. In theory, Calendar's hold time
> > (1 enqueue + 1 dequeue) is O(1), which is better than Heap's O(lg(N)).
> > In practice, there may be not that much difference, though.
> I never understood the differences between these different schedulers, but
> I think I'm beginning to see it now. Am I right in saying that
> 1. The Calendar scheduler uses hashing to insert an event into the
> scheduler queue, and hence it takes O(1) to insert and remove an event
Apparently so. IMO it would be good to have the year adjustment in
CalendarScheduler::deque() optionally settable as an otcl parameter
with period (wrap years?/wrap days?/wrap hours?), rather than as the
> 2. The Heap scheduler is based on some form of binary tree and it takes
> O(lg(N)) to insert and remove events into/out of the scheduler queue?
> 3. The List scheduler is based on a simple linked list, and it takes O(N)
> to insert an event and O(1) to remove the next event - just pop it from
> the top of the queue?
> Sean Murphy, Email: firstname.lastname@example.org
> Teltec Ireland, Phone: +353-1-7045080
> DCU, Dublin 9, Fax: +353-1-7045092