Real-Time Systems Vocabulary

Flashcards covering core concepts of real-time systems, task parameters, scheduling classification, cyclic executives, slack stealing, and dynamic scheduling algorithms.

Real-Time System

A system whose specification includes both a logical correctness requirement and a temporal correctness requirement.

Logical Correctness

A correctness requirement specifying that the system must produce the functionally correct output.

Temporal Correctness

A correctness requirement specifying that the system must produce its output at the right time relative to specified deadlines.

Soft Real-Time System

A real-time system that can tolerate some delay in delivering results and in which some deadlines may occasionally be missed.

Hard Real-Time System

A real-time system in which all deadlines are strict and missing any deadline means the system is incorrect.

Predictable Computing

The core requirement of real-time computing where predictable, deterministic timing behavior is valued over raw performance or high average-case execution speed.

Abundant Resources

A resource classification where system resources are plentiful enough that virtually any design methodology can satisfy the timing requirements of the application.

Insufficient Resources

A resource classification where application requirements exceed technology capabilities, making it impossible for any design methodology to meet timing requirements.

Sufficient but Scarce Resources

A resource classification where timing requirements can be met only through careful allocation and scheduling of limited resources.

Sampling Period ($T$)

The recurring time interval between timer interrupts in a digital control system that dictates how frequently sensor data is sampled and control outputs are computed.

Multi-Rate Control System

A control system containing multiple sensors and actuators that supports multiple control loops operating at different sampling rates.

Task

A sequential piece of code within a real-time system program.

Job

An individual instance of execution of a task.

Processor (Real-Time Resource)

A general term for any hardware or system resource required for a job to execute, such as a CPU, network link, disk, or critical section.

Release Time ($r_i$)

The exact time instant at which a job $J_i$ becomes ready to execute.

Deadline ($d_i$)

The absolute time instant by which a job $J_i$ must complete its execution.

Relative Deadline ($D_i$)

The maximum allowable execution time window of a job, calculated as $D_i = d_i - r_i$.

Response Time

The total elapsed time from when a job is released until it completes execution, calculated as $\text{Completion time} - r_i$.

Hard Deadline

A strict timing constraint that must be met; missing a hard deadline makes the system execution incorrect.

Soft Deadline

A timing constraint that can occasionally be missed without causing critical system failure.

Firm Deadline

A soft deadline with the property that a job's utility drops to $0$ immediately upon missing the deadline.

Release-Time Jitter

The variation in actual job release times expressed as a range $[r_i^-, r_i^+]$.

Periodic Task

A task $T_i$ characterized by a period $p_i$, which repeatedly releases jobs at regular intervals equal to $p_i$.

Sporadic Task

A task whose jobs are released at arbitrary times and carry hard deadlines.

Aperiodic Task

A task whose jobs are released at arbitrary times and carry soft deadlines or no deadlines.

Phase ($r_{i,1}$)

The release time of the first job $J_{i,1}$ of a task $T_i$.

Synchronous System

A periodic task system in which every task has an initial phase equal to $0$.

Asynchronous System

A periodic task system in which tasks have arbitrary initial phases.

Hyperperiod ($H$)

The least common multiple of the periods $\{p_i\}$ of all periodic tasks in a system.

Task Utilization ($u_i$)

The fraction of processor time consumed by task $T_i$, defined as $u_i = \frac{e_i}{p_i}$.

System Utilization ($U$)

The total processor utilization of all periodic tasks in a task set, defined as $U = \sum_{i=1}^n u_i$.

Independent Tasks

Tasks that operate without execution dependencies such as resource contention, critical sections, or precedence constraints.

Precedence Constraints

Execution ordering dependencies requiring a job $J_i$ to complete before another job $J_k$ can be released.

Scheduler

A runtime algorithm responsible for generating an execution schedule for ready jobs on available processors.

Feasibility Analysis Algorithm

An algorithm that checks whether a set of tasks will satisfy all specified timing constraints.

Feasible Schedule

A schedule in which every job finishes execution on or before its specified deadline.

Schedulable Task Set

A task set $T$ for which a given scheduling algorithm $A$ is guaranteed to produce a feasible schedule.

Optimal Scheduling Algorithm

A scheduling algorithm that always produces a feasible schedule if any feasible schedule exists for the task set.

Static Scheduling

An offline, clock-driven scheduling approach where scheduling decisions are precomputed and stored in a lookup table prior to execution.

Dynamic Scheduling

An online priority-driven scheduling approach where scheduling decisions and job priority assignments are made dynamically at runtime.

Cyclic Schedule

A static schedule generated by a timer-driven scheduler iterating through stored decision points over the hyperperiod $H$.

Frame

A fixed time interval of length $f$ dividing the timeline in cyclic executive systems, where scheduling decisions and checks occur only at frame boundaries.

Major Cycle

The primary repeating time interval in a cyclic executive system, equal in length to the hyperperiod $H$.

Minor Cycle

An individual frame interval of length $f$ within a major cycle.

Job Slices

Subtasks created by partitioning a long task's execution time into smaller units to allow execution across multiple frames when $f < e_i$.

Slack

The unallocated time available at the beginning of frame $k$, defined as $f - x_k$, where $x_k$ is the execution time allocated to periodic slices in frame $k$.

Slack Stealing

A scheduling optimization technique in cyclic executives where aperiodic jobs execute ahead of periodic jobs using available frame slack without causing periodic jobs to miss deadlines.

Acceptance Test

A runtime feasibility check conducted upon the arrival of a sporadic job to determine whether it can be accepted without causing any accepted sporadic job to miss its deadline.

Earliest-Deadline-First (EDF) Scheduling

A dynamic-priority scheduling algorithm that assigns the highest priority to the ready job with the earliest absolute deadline $d_i$.

Least-Laxity-First (LLF) Scheduling

A dynamic-priority scheduling algorithm that assigns the highest priority to the ready job with the smallest laxity (slack) at any given time.