Real-Time Systems: Introduction and Applications

Introduction to Real-Time Systems Lecture 1 By: Mohammad hajibegloo hajibegloo@gmail.com

10 4 6 3 2 7 20 : 3

What is a Real-Time System? Real-time systems have been defined as: "those systems in which the correctness of the system depends not only on the logical result of the computation, but also on the time at which the results are produced"; J. Stankovic, "Misconceptions About Real-Time Computing," IEEE Computer, 21(10), October 1988. 3

A typical real-time system 4

Sample Applications 5

Real-time Systems -- Introduction Real-time systems are defined as those systems in which the correctness of the system depends not only on the logical result of computation, but also on the time at which the results are produced. Hard real-time systems (e.g., Avionics, Command & Control Systems). Firm real-time systems (e.g., Banking, Online transaction processing). Soft real-time systems (e.g., Video streaming). 6

Real-Time Systems -- Introduction Hard deadline: penalty due to missing deadline is a higher order of magnitude than the reward in meeting the deadline Firm deadline: penalty and reward are in the same order of magnitude Soft deadline: penalty often lesser magnitude than reward 7

Some Definitions Release Time(Ready time): Instant of time job becomes available for execution. If all jobs are released when the system begins execution, then there is said to be no release time Deadline: Instant of time a job's execution is required to be completed. If deadline is infinity, then job has no deadline. Absolute deadline is equal to release time plus relative deadline Response time: Length of time from release time to instant job completes 8

Some Definitions ri: ready time Deadline: Di- relative deadline di- absolute deadline Deadline: short deadline synchrone deadline Long deadline (ri, di] - feasible interval deadline relative to release time di= Di + ri

Some Definitions Task ( i) : Set of related jobs jointly provide function. Job (Jij) : Unit of work, scheduled and executed by system. characterized by the following parameters: Temporal parameters: timing constraints and behavior Functional parameters: intrinsic properties of the job. Resource parameters: resource requirements. Interconnection parameters: how it depends on other jobs and how other jobs depend on it 10

Real-Time Tasks Periodic tasks - Time-driven. Characteristics are known a priori - Task iis characterized by (ci ,Ti) E.g.: Task monitoring temperature of a patient in an ICU. Aperiodic tasks - Event-driven. Characteristics are not known a priori - Task iis characterized by (ai, ri, ci, di) E.g.: Task activated upon detecting change in patient s condition. Sporadic Tasks Aperiodic tasks with known minimum inter-arrival time. Ti: task period ai: arrival time ri: ready time di: deadline ci: worst case execution time. 11

Periodic Task Model Jobs repeated at regular or semi-regular intervals modeled as periodic. Task iis a serious of periodic Jobs Jij. Ti- period, minimum inter release interval between jobs in Task i. Must be bounded from below. ci- maximum execution time for jobs in task i. rij- release time of the jthJob in Task i (Jijin i). H - Hyperperiod = Least Common Multiple of Tifor all i. H = lcm(Ti), for all i. ui- utilization of Task i. ui= ci / Ti U - Total utilization = Sum over all ui.

Functional Parameters Preemptivity Preemption: suspend job then dispatch different job to processor. Cost includes context switch overhead. Non-preemptable task - must be run from start to completion. Criticalness - positive integer indicating the relative importance of a job. Useful during overload. Optional Executions - jobs or portions of jobs may be declared optional. Useful during overload. Laxity - Laxity type => hard or soft timing constraints. Supplemented by a usefulness function. Useful during overload. Lateness: difference between completion time and deadline, can be negative if early. Tardiness: Zero if completion time <= deadline, otherwise > 0 (complete - deadline).

Schedules and Scheduling Scheduler: Module implementing scheduling algorithms Schedule: assignment of all jobs to available processors, produced by scheduler. Valid schedule: every processor assigned to at most one job at a time every job assigned to at most one processor at a time no job scheduled before its release time Total amount of processor time assigned to every job is equal to its maximum or actual execution time

Definitions Feasible schedule: Every job starts at or after release time and completes by deadline Schedulable: set of jobs schedulable according to an algorithm if scheduler always produces a feasible schedule. Optimal: Scheduling algorithm optimal if it always produces a feasible schedule if such a schedule exists

Performance Measures Miss rate: percentage of jobs executed but completed late Loss rate: percentage of jobs discarded Invalid rate: sum of miss and loss rate. makespan : If all jobs have same release time and deadline, then makespan = response time of the last job to execute.

Notion of Predictability The most common denominator that is expected from a real-time system is predictability. The behavior of the real-time system must be predictable which means that with certain assumptions about workload and failures, it should be possible to show at design time that all the timing constraints of the application will be met. For static systems, 100% guarantees can be given at design time. For dynamic systems, 100% guarantee cannot be given since the characteristics of tasks are not known a priori. In dynamic systems, predictability means that once a task is admitted into the system, its guarantee should never be violated as long as the assumptions under which the task was admitted hold. 17

Common Misconceptions Real-time computing is equivalent to fast computing. Real-time programming is assembly coding, priority interrupt programming, and writing device drivers. Real-time systems operate in a static environment. 18