Optimal Preemptively Scheduling for Real-Time Reconfigurable Uniprocessor Embedded Systems

Optimal Preemptively Scheduling for Real-Time Reconfigurable Uniprocessor Embedded Systems

Hamza Gharsellaoui (INSAT Institute, Tunisia & Al Jouf Technical College, Saudi Arabia)
Copyright: © 2015 |Pages: 13
DOI: 10.4018/978-1-4666-5888-2.ch712
OnDemand PDF Download:
List Price: $37.50

Chapter Preview



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.

Key Terms in this Chapter

Real-Time Scheduling: In computer science, scheduling is the method by which threads, processes or data flows are given access to system resources (e.g. processor time, communications bandwidth). In real-time environments, such as embedded systems for automatic control in industry, the scheduler also must ensure that processes can meet deadlines; this is crucial for keeping the system stable.

Independent Tasks: A task that must be performed without the aid of references due to mission or job requirements.

Laxity: The time quantum between the deadline of the executed task and its response time.

Reconfigurable Computing: A computer architecture combining some of the flexibility of software with the high performance of hardware by processing with very flexible high speed computing fabrics like field-programmable gate arrays (FPGAs). The principal difference when compared to using ordinary microprocessors is the ability to make substantial changes to the data path itself in addition to the control flow.

Sporadic Tasks: A sporadic task is characterized by three positive integers; an execution time e, a deadline d (relative to the release time), and a minimum separation p, with e <= d and e <= p. Sporadic tasks may make a request at any time, but two successive requests must be separated in time by at least p “time units.”

Embedded Systems: A computer system designed to perform one or a few dedicated functions often with real-time computing constraints

Response Time: Amount of time it takes from when a request was submitted until the first response is produced.

Complete Chapter List

Search this Book: