Abstract

Task period selection is often used to adjust the workload to the available computational resources. We propose a model where each selected period is not restricted to be a natural number, but can be any rational number within a range.

Under this generalisation, we contribute a period selection algorithm that yields a much smaller hyper-period than that of previous works: with respect to the largest period, the hyper-period with integer constraints is exponentially bounded; with rational periods the worst case is only quadratic. By means of an integer approximation at each task activation, we show how our rational period approach can work under system clock granularity; it is thus compatible with scheduling analysis practice and implementation.

Our finding has practical applications in several fields of real-time scheduling: lowering complexity in table driven schedulers, reducing search space in model checking analysis, generating synthetic workload for statistical analysis of real-time scheduling algorithms, etc.

The elastic periodic model

Co-design process.

Minimal hyper-period facts

Time complexity:

In the worst case, quadratic with respect to the largest of the task periods. That is: O(max(P_i))

Spatial complexity:

The memory required by the algorithm is just 2n integers, where "n" is the numbers of tasks.

Reduction improvement over the classic LCM value

Generally, it finds an exponentially smaller hyper-period.

Links