Task Scheduling under Uncertain Timing Constraints in Real-Time Embedded Systems

1. Introduction

Real-time systems are those systems for which a timely response to the external stimuli within a specified time frame is a must (Krishna & Shin, 1997). In other words, computing systems where catastrophe may occur or results may become useless if task completion takes more than some specified time are known as real-time systems (Ramamritham & Stankovic, 1994). Communication Systems, Defense Systems, Aircraft Flight Control Systems, Air Traffic Control, Space Stations, Nuclear Power Plants etc. depend solely on real-time computing and are examples of Real-Time Systems. Real-Time Systems draw attention to various issues especially in scheduling, resource allocation, and communication between components and subsystems etc. Three main measures that count the merits of real-time systems are: predictably very rapid response to urgent events, high degree of schedulability (i.e. surety of feasible schedule) and stability during transient overload (Sha, 1994).

Computing applications of real-time systems, i.e. time critical systems, require satisfying explicit timing constraints of the tasks and hence these timing constraints play the most important role for the purposeful and safe operation of real-time systems. These timing constraints may be hard or soft. Therefore, real-time systems can be classified into hard real-time systems and soft real-time systems. Computing systems with hard timing constraints are known as hard real-time systems, whereas those with soft timing constraints are known as soft real-time systems. The timing constraints of a particular set of tasks in a real-time system comprises of task arrival or release times, relative task deadlines, absolute task deadlines, processing times, intervals between subsequent invocations of tasks i.e. period etc as defined below:

• •

  The release time of task is the time before which it cannot start execution.

• •

  The time within which a task must be completed after it is released is known as the relative deadline of that particular task.

• •

  Release time plus the relative deadline gives the absolute deadline of a task.

• •

  The time required by the processor to execute a particular task is known as the processing time or execution time.

• •

  Tasks may be periodic, aperiodic, or sporadic.

• •

  When tasks are released periodically they are periodic tasks.

• •

  An invocation of sporadic tasks happens in irregular intervals rather than periodically. An upper bound on the invocation rate characterizes the sporadic tasks.

• •

  Aperiodic tasks are not periodic nor carry any bound on invocation rate.