Activity Heap scheduler

The Activity Heap is based on a heap, though allows for reschedules.

To allow reschedules to happen, a model is accompagnied by a flag to indicate whether or not it is still valid. As soon as a model is rescheduled, the flag of the previously scheduled time is set and another entry is added. This causes the heap to become dirty, requiring a check for the flag as soon as the first element is requested.

Due to the possibility for a dirty heap, the heap will be cleaned up as soon as the number of invalid elements becomes too high. This cleanup method has O(n) complexity and is therefore only ran when the heap becomes way too dirty.

Another problem is that it might consume more memory than other schedulers, due to invalid elements being kept in memory. However, the actual model and states are not duplicated as they are references. The additional memory requirement should not be a problem in most situations.

The ‘activity’ part from the name stems from the fact that only models where the time_next attribute is smaller than infinity will be scheduled. Since these elements are not added to the heap, they aren’t taken into account in the complexity. This allows for severe optimisations in situations where a lot of models can be scheduled for infinity.

Of all provided schedulers, this one is the most mature due to it being the oldest and also the default scheduler. It is also applicable in every situation and it offers sufficient performance in most cases.

This scheduler is ideal in situations where (nearly) no reschedules happen and where most models transition at a different time.

It results in slow behaviour in situations requiring lots of rescheduling, and thus lots of dirty elements.

This method is also applied in the VLE simulator and is the common approach to heap schedulers that require invalidation. It varies from the scheduler in ADEVS due to the heap from the heapq library being used, which doesn’t offer functions to restructure the heap. Reimplementing these methods in pure Python would be unnecessarily slow.

class pypdevs.schedulers.schedulerAH.SchedulerAH(models, epsilon, total_models)[source]

Scheduler class itself

__init__(models, epsilon, total_models)[source]

Constructor

Parameters

models – all models in the simulation

cleanFirst()[source]

Clean up the invalid elements in front of the list

getImminent(time)[source]

Returns a list of all models that transition at the provided time, with a 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