Activation-adjusted scheduling algorithms for real-time systems

Scheduling in real-time is an important problem due to its role in practical applications. Among the scheduling algorithms proposed in the literature, static priority scheduling algorithms have less run-time scheduling overhead due to their logical simplicity. Rate monotonic scheduling is the first static priority algorithm proposed for real-time a scheduiling[1]. It has been extensively analyzed and heavily used in practice for its simplicity. One of the limitations of rate monotonic scheduling, as shown recently in [261, is that it incurs significant run-time overhead due to high preemptions. The main objective of this paper is to propose static priority scheduling algorithms with reduced preemptions. We present two frameworks, called off-line activation-adjusted scheduling (OAA) and adaptive activation-adjusted scheduling (AAA), from which many static priority scheduling algorithms can be derived by appropriately implementing the abstract components. The proposed algorithms reduce the number of unnecessary preemptions and hence: (i) increase processor utilization in real-time systems; (ii) reduce energy consumption when used in embedded systems; and (iii) increase tasks schedulability. We conducted a simulation study for selected algorithms derived from the frameworks and the results indicate that the algorithms reduce preemptions significantly. The appeal of our algorithms is that they generally achieve significant reduction in preemptions while retaining the simplicity of static priority algorithms intact.