Adaptive workload management through elastic scheduling

In real-time computing systems, timing constraints imposed on application tasks are typically guaranteed off line using schedulability tests based on fixed parameters and worst-case execution times. However, a precise estimation of tasks' computation times is very hard to achieve, due to the non-deterministic behavior of several low-level processor mechanisms, such as caching, prefetching, and DMA data transfer. The disadvantage of relying the guarantee test on a priori estimates is that an underestimation of computation times may jeopardize the correct behavior of the system, whereas an overestimation will certainly waste system resources and causes a performance degradation. In this paper, we propose a new methodology for automatically adapting the rates of a periodic task set without forcing the programmer to provide a priori estimates of tasks' computation times. Actual executions are monitored by a runtime mechanism and used as feedback signals for predicting the actual load and achieving rate adaptation. Load balancing is performed using an elastic task model, according to which tasks utilizations are treated as springs with given elastic coefficients.