Heapset scheduler

The Heapset scheduler is based on a small heap, combined with two dictionaries.

The heap will contain only the timestamps of events that should happen. One of the dictionaries will contain the actual models that transition at the specified time. The second dictionary than contains a reverse relation: it maps the models to their time_next. This reverse relation is necessary to know the old time_next value of the model. Because as soon as the model has its time_next changed, its previously scheduled time will be unknown. This ‘previous time’ is not equal to the timeLast, as it might be possible that the models wait time was interrupted.

For a schedule, the model is added to the dictionary at the specified time_next. In case it is the first element at this location in the dictionary, we also add the timestamp to the heap. This way, the heap only contains unique timestamps and thus the actual complexity is reduced to the number of different timestamps. Furthermore, the reverse relation is also updated.

Unscheduling is done similarly by simply removing the element from the dictionary.

Rescheduling is a slight optimisation of unscheduling, followed by scheduling.

This scheduler does still schedule models that are inactive (their time_next is infinity), though this does not influence the complexity. The complexity is not affected due to infinity being a single element in the heap that is always present. Since a heap has O(log(n)) complexity, this one additional element does not have a serious impact.

The main advantage over the Activity Heap is that it never gets dirty and thus doesn’t require periodical cleanup. The only part that gets dirty is the actual heap, which only contains small tuples. Duplicates of these will also be reduced to a single element, thus memory consumption should not be a problem in most cases.

This scheduler is ideal in situations where most transitions happen at exactly the same time, as we can then profit from the internal structure and simply return the mapped elements. It results in sufficient efficiency in most other cases, mainly due to the code base being a lot smaller then the Activity Heap.

class pypdevs.schedulers.schedulerHS.SchedulerHS(models, epsilon, total_models)[source]

Scheduler class itself

__init__(models, epsilon, total_models)[source]

Constructor

Parameters

models – all models in the simulation

getImminent(time)[source]

Returns a list of all models that transition at the provided time, with the specified epsilon deviation allowed.

Parameters

time – timestamp to check for models

Warning

For efficiency, this method only checks the first elements, so trying to invoke this function with a timestamp higher than the value provided with the readFirst method, will always return an empty set.

massReschedule(reschedule_set)[source]

Reschedule all models provided. Equivalent to calling unschedule(model); schedule(model) on every element in the iterable.

Parameters

reschedule_set – iterable containing all models to reschedule

readFirst()[source]

Returns the time of the first model that has to transition

Returns

timestamp of the first model

schedule(model)[source]

Schedule a model

Parameters

model – the model to schedule

unschedule(model)[source]

Unschedule a model

Parameters

model – model to unschedule