Dynamic voltage scaling (DVS) has been adopted as an effective technique for reducing energy consumption in embedded systems. Although several scheduling approaches have been developed to address voltage scaling together with stringent timing constraints, inter-task relations have been neglected. This work presents a pre-runtime method for hard real-time systems scheduling considering dynamic voltage scaling, overheads and inter-task relations. The proposed work considers time Petri nets as a formal model in order to provide a basis for precise schedule generation as well as to allow property analysis and verification. Experimental results depict the proposed approach feasibility, in the sense that energy consumption is minimized as well as system constraints are met.
Whenever designing embedded systems, several constraints, such as size, reliability, energy consumption and timing constraints, may have to be considered to satisfy system requirements. Lately, considerable special attention has been devoted to energy consumption, mainly due to the great expansion of the mobile device market.
During the last decade, DVS (dynamic voltage scaling) has been adopted as one of the most effective techniques for reducing energy consumption in embedded systems. Adjusting CPU supply voltage has great impact on energy consumption, since the consumption is proportional to the square of supply voltage in CMOS microprocessors [11]. However, lowering the supply voltage linearly affects the maximum operating frequency. Therefore, DVS may be seen as a technique for trading-off energy consumption and performance.
When considering hard real-time systems, DVS needs to be adopted with caution, since stringent timing constraints may be affected. In this case, equipment damage or even loss of human lives may occur due to timing constraint violations. Thus, several scheduling approaches, mainly based on runtime techniques, have been devised to cope with DVS in time-critical systems. However, system specifications often either oversimplify tasks’ relations such as precedence and exclusion relation or do not consider them at all. Furthermore, overheads, such as preemptions and voltage/frequency switching, are issues that must be considered during schedule generation. Indeed, if overheads are neglected, tasks’ constraints may be affected and even the gains obtained with DVS may be significantly reduced [15].
This paper presents a pre-runtime scheduling method for hard real-time systems that considers DVS, inter-task relations and overheads. More specifically, the contributions are: (i) the proposition of a formal model based on time Petri nets (TPN) that provides the basis for precise schedule generation as well as for the verification/analysis of behavioral and structural properties; (ii) the explicit modeling of inter-task relations and overheads (e.g. voltage/frequency switching), so as to allow considering them for the schedule generation; and (iii) a pre-runtime scheduling algorithm that finds out feasible schedules that satisfy timing and energy constraints. Besides, a technique for dealing with dynamic slack times is presented in order to take advantage of new opportunities to further reduce energy consumption during system execution.
One challenge designers have to face when dealing with embedded hard real-time systems is the modeling power of tools. In order to be of practical usability, they might provide means for representing concurrent communicating tasks, synchronization mechanisms and communication primitives as well as they should describe timing constraints and requirements. Furthermore, the availability of precise methods for analysis and verification of systems’ representation is a requirement of remarkable importance. Petri nets [16] are a very well suited model for representing real-time embedded systems, since concurrency, synchronization and communication mechanisms are naturally represented. It should also be emphasized the sound mathematical basis related to Petri net analysis methods.
The rest of the paper is organized as follows: Section 2 summarizes related works. Section 3 presents some preliminaries with the purpose of providing a better comprehension of the proposed approach. Section 4 describes the computational model and Section 5 introduces the formal modeling. Section 6 describes the proposed pre-runtime schedule synthesis as well as discussing the respective algorithm complexity. Section 7 presents a technique for dealing with slack times that may appear during system execution. Section 8 describes experimental results, and Section 9 concludes this paper and introduces future works.
This paper presented a method based on time Petri nets for power-aware hard real-time systems schedule generation, considering dynamic voltage scaling, overheads, precedence and exclusion relations. Although many works deal with DVS in time-critical systems, inter-task relations as well as overheads have been neglected. In addition, most works rely on runtime methods, which, although flexible, may fail in finding a feasible schedule, even if such a schedule exists. Predictability is an important concern when considering time-critical systems. For assuring that every critical task meets its deadlines, a pre-runtime scheduling method was proposed. Several experiments have been conducted to demonstrate the feasibility of the proposed method, in such a way that viable schedules were found in situations where runtime methods may fail, and, also, energy consumption was reduced by adopting DVS. Besides, using the proposed formal model, several properties can be verified as well as analyzed.
Currently, we are developing an automatic code generation method, which will provide customized code satisfying timing and energy constraints. As future work, we are planning to extend the proposed scheduling method in order to consider multiple processors.
