Priority-Based Reconfiguration And Priority-Free Conditionally-Preemptive Scheduling Of Real-Time Systems

Real-time scheduling has been extensively studied in the last four decades. The key results in real-time scheduling theory and the historical events lead to the establishment of the cur-rent real-time computing infrastructure. Generally, all the well-known real-time scheduling algorithms can be divided into two categories:dynamic priorities or static priorities. Earliest deadline first (EDF) scheduling algorithm is the most well-known and widely-used dynamic priority real-time scheduling algorithm. On the other hand, fixed-priority (FP) is the well-accepted static-priority-based real-time scheduling algorithm. Furthermore, during the real-time scheduling process, the execution of each task may or may not be preempted by other tasks. Based on these principles, users can reconfigure the real-time systems dynamically to generate safe execution sequences.Recently, many research groups are devoted to the dynamic low-power reconfiguration of real-time systems. The first contribution of this thesis is to dynamically reconfigure a real-time system for the purpose of obtaining low-power consumption. This part deals with the dynamic low-power reconfiguration of a real-time system. It processes periodic and probabilistic tasks that have hard/soft deadlines corresponding to internal/external events. A run-time event-based reconfiguration scenario is a dynamic operation allowing the addi-tion/removal of the assumed periodic/probabilistic tasks. Thereafter, some tasks may miss their hard deadlines and the power consumption may increase. In order to reconfigure the system to be schedulable and efficient, i.e., satisfying its real-time constraints with low-power consumption, this research presents a software-agent-based architecture. An intelli-gent agent is developed, which provides four run-time solutions to reconfigure the system at run-time. To reconfigure the probabilistic tasks to be feasible, the agent modifies their tem-poral parameters dynamically; moreover, in order to feasibly serve the probabilistic tasks and reduce the system’s power consumption, the agent provides three virtual processors by dynamically extending the periods of the periodic tasks. A simulation study verifies the effectiveness of the agent.In the last three decades, supervisory control of discrete-event systems (SCDES) is well developed. Based on discrete-event systems (DES), the system behaviors are described by regular language, based on which the specifications can be well defined. It is often possible to meet this specification in an "optimal", that is,minimally restrictive, fashion.The control problems will be considered fully solved when a controller that forces the specification to be met has been shown to exist and to be constructible. The supervisory control of timed DES (TDES) can find the system behaviors by considering the timed feature. As known that, the traditional real-time scheduling method cannot provide all the safe execution sequences. Research in [32] is the first study to find all the safe execution sequences of the real-time systems by using the nonblocking supervisory control of TDES. Building on this, the sec-ond contribution of this thesis is to present a dynamic reconfiguration technique for real-time scheduling of real-time systems running on uni-processors. A new formalism is developed to assign periodic tasks with multiple-periods. By implementing supervisory control theory (SCT), a real-time system is dynamically reconfigured when its initial safe execution se-quence set is empty. During the reconfiguration process, based on the multiple-periods, the supervisor proposes different safe execution sequences. Two real-world examples illustrate that the presented approach provides an increased number of safe execution sequences as compared to the earliest-deadline-first (EDF) scheduling algorithm.Since the time event in TDES is represented by a unique event tick, it has some restric-tions on describing the real-time system’s behavior. Consequently, the TDES models can only model, schedule and reconfigure the real-time systems with fixed priorities. Thus, in order to present a general real-time system model, the third contribution of this thesis is to present a general DES-based hard periodic real-time task model. Based on SCT, an optimal priority-free real-time scheduling technique is proposed to process all the tasks running in uni-processor or multi-processor real-time systems. The preemption relation in this thesis generalizes priority-based preemption. First, regular languages are utilized to describe the processor behavior related to each task’s execution. Thereafter, the languages are repre-sented by DES generators. Finally, the global processor behavior is generated as the syn-chronous product of these DES generators. A novel preemption policy, namely conditional-preemption, is developed. Two sets of conditional-preemption specifications are developed, on the processor level and task level, respectively. Moreover, in order to control the system to be nonblocking and also limit the worst-case response time (WCRT) of the tasks, two corresponding sets of specifications are presented. After generating the global specification as the synchronous product, by implementing SCT the calculated supervisor can provide all the safe real-time execution sequences. The supervisor calculation can be sped up by a three step algorithm. Finally, the real-time scheduling is implemented for real-world examples. In the future work, building on the third contribution of this thesis, we will dynamically re-configure real-time systems.Moreover, we will also provide a quantitatively optimal sched-ule from the perhaps large number of safe execution sequences.