[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: scheduler going backwards solution?
Sean Murphy <[email protected]> writes:
> > 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
>
> 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?
That's the general idea. Except that in certain circumstances the
calendar and the heap need to resize themselves which makes those
estimates a little fuzzy.
-Yuri
>
> Rgds,
> Sean.
>
> -----
> Sean Murphy, Email: [email protected]
> Teltec Ireland, Phone: +353-1-7045080
> DCU, Dublin 9, Fax: +353-1-7045092
> Ireland.