Optimal Preemptively Scheduling for Real-Time Reconfigurable Uniprocessor Embedded Systems

Introduction

Nowadays, due to the growing class of portable systems, such as personal computing and communication devices, embedded and real-time systems are addressing new criteria such as flexibility and agility (Gharsellaoui et al., 2012). For these reasons, there is a need to develop tools, methodologies in embedded software engineering and reconfigurable embedded control systems as an independent discipline. By response for this requirement of developing reconfigurable systems, many interesting academic and industrial studies have been made in recent years. Feasibility Conditions (FC) for the dimensioning of a real-time system enables a designer to grant that timeliness constraints associated to an application run by the system are always met for all possible configurations. A reconfiguration can be decided either off-line or on-line. In the first case, the goal is to check if several hardware platforms or several hardware configurations can be used to run a specific application while preserving the timeliness constraints of the tasks. In the second case, a reconfiguration might result from a system mode change to adapt the system to the context of its execution or to handle hardware or software faults. We study in this work many dimension sensitivity analysis (more than one task parameter can evolve). A reconfiguration scenario means the addition, removal or update of tasks in order to save the whole system on the occurrence of hardware/software faults, or also to improve its performance when random disturbances happen at run time.

We consider in this article the problem of preemptively scheduling that mixed a workload on uniprocessor to optimize the response time and while ensuring that all off-line requests meet their deadlines and to accept as many sporadic requests which must be guaranteed to meet their deadlines after a reconfiguration scenario by using the earliest deadline first (EDF) scheduling algorithm. Indeed, many real-time systems rely on the EDF scheduling algorithm. This algorithm has been shown to be optimal under many different conditions. For example, for independent, preemptable tasks, on a uniprocessor EDF is optimal in the sense that if any algorithm can find a schedule where all tasks meet their deadlines, then EDF can meet the deadlines (Dertouzos, 1974). Also, Jackson’s rule (Jackson, 1955) says that ordering a set of tasks by deadline will minimize the maximum lateness. Further, it has also been shown that EDF is optimal under certain stochastic conditions (Towsley & Panwar, 1991). In spite of these advantageous properties, EDF has one major negative aspect. That is, when using EDF in a dynamic system, if overload occurs, tasks may miss deadlines in an unpredictable manner, and in the worst case, the performance of the system can approach zero effective throughputs (Locke, 1986). The main contribution of this article is the development and the performance evaluation of an optimal version of the EDF algorithm. We propose an intelligent agent-based architecture in which a software agent is deployed to dynamically adapt the system to its environment by applying reconfiguration scenarios.

Before any reconfiguration scenario, the initial real-time embedded control system is assumed to be feasible with a rapid response time. If the system is reconfigured by adding some OS tasks, the processor utilization factor U will be increased and/or some tasks of the new execution model will violate corresponding deadlines. The agent dynamically provides technical solutions for users where the system becomes unfeasible (e.g deadlines are violated), by sending sporadic tasks to idle times, by modifying the deadlines of tasks, the worst case execution times (WCETs), the activation time, by tolerating some non critical tasks m among n according to the (m,n) firm and a reasonable cost (for more details on (m,n) firm see (Hamdaoui & Ramanathan, 1995), or in the worst case by removing some non hard (soft) tasks according to predefined heuristic. A tool RT-Reconfiguration is developed at INSAT institute in university of Carthage, Tunisia to support all the services offered by the agent. The minimization of the response time is evaluated after each reconfiguration scenario to be offered by the agent.