1. Introduction

Real-time systems are specialized computing systems in which correctness depends not only on producing the correct output but also on producing that output within a specified time limit. In these systems, timing requirements are as important as computational correctness.

A result produced after its deadline may be considered useless or even dangerous, regardless of whether the result itself is correct.

Formally:

A real-time system is a system in which the correctness of computation depends on both the logical correctness of the result and the time at which the result is produced.

Unlike general-purpose operating systems that focus on maximizing throughput, minimizing waiting time, or improving CPU utilization, real-time systems prioritize:

• Meeting deadlines

• Predictability

• Reliability

• Deterministic behavior

Examples include:

• Aircraft flight control systems

• Medical monitoring devices

• Industrial automation systems

• Autonomous vehicles

• Multimedia systems

In such environments, CPU scheduling becomes significantly more critical because failure to execute tasks within their deadlines can lead to severe consequences.

2. Types of Real-Time Systems

Real-time systems are broadly classified into two categories based on the strictness of their timing requirements.

2.1 Hard Real-Time Systems

Definition

A Hard Real-Time System is one in which missing a deadline is considered a system failure.

The timing constraints are absolute and must always be satisfied.

Formally:

Every task must complete execution before its deadline.

If even a single deadline is missed:

Deadline Missed
      ↓
System Failure

the system is considered incorrect.

Characteristics

Strict Timing Constraints

Deadlines are mandatory.

Deterministic Behavior

Execution timing must be predictable.

Zero Tolerance for Delays

Even small delays may be unacceptable.

High Reliability Requirements

System behavior must be guaranteed under all operating conditions.

Examples

Aircraft Flight Control Systems

Control decisions must be made within precise time limits.

Pacemakers

Failure to generate pulses at the correct time may endanger lives.

Industrial Automation

Manufacturing equipment often requires precise timing guarantees.

Nuclear Reactor Control Systems

Delayed responses may lead to catastrophic consequences.

Key Observation

Correct Result
      +
Correct Timing
      =
Success

Both are mandatory.

2.2 Soft Real-Time Systems

Definition

A Soft Real-Time System is one in which deadlines are important but not absolutely mandatory.

Missing a deadline degrades system performance but does not cause total system failure.

Formally:

Occasional deadline misses are tolerated, although performance may suffer.

Characteristics

Flexible Timing Constraints

Deadlines are desirable rather than mandatory.

Some Delay Tolerance

Late results may still retain value.

Performance-Oriented

Focuses on quality rather than strict guarantees.

Best-Effort Scheduling

Attempts to meet deadlines whenever possible.

Examples

Video Streaming

Late video frames may cause reduced quality.

Online Gaming

Occasional delays may cause lag but not system failure.

Multimedia Applications

Dropped frames degrade user experience but remain acceptable.

Video Conferencing

Small delays are inconvenient but tolerable.

Key Observation

Deadline Missed
      ↓
Performance Degradation
      ↓
System Continues

Unlike hard real-time systems, operation continues.

3. Key Concepts in Real-Time Scheduling

Real-time scheduling introduces several concepts not commonly emphasized in traditional CPU scheduling.

3.1 Task

In real-time systems, processes are often referred to as:

Tasks

A task is a unit of work that must be completed within a specified timing constraint.

Each task is typically characterized by:

• Execution time

• Deadline

• Period

Example

Read Sensor
Process Data
Update Controller

Each may be represented as an independent task.

3.2 Deadline

A deadline is the latest time by which a task must complete execution.

Example

Task Arrival = 0 ms

Deadline = 20 ms

The task must finish before:

20 ms

Failure to do so constitutes a deadline miss.

Importance

Real-time schedulers make decisions primarily based on deadlines rather than waiting times or turnaround times.

3.3 Periodic vs Aperiodic Tasks

Tasks may be classified according to arrival patterns.

Periodic Tasks

Periodic tasks repeat at fixed intervals.

Example:

Sensor Reading

Every 10 ms

Timeline:

0
10
20
30
40
...

Periodic tasks are common in control systems.

Aperiodic Tasks

Aperiodic tasks occur irregularly.

Example:

Emergency Alarm

User Input

Network Event

Arrival times are unpredictable.

Comparison

4. Scheduling Objectives

Traditional scheduling focuses on metrics such as:

• Waiting time

• Turnaround time

• Throughput

Real-time scheduling focuses on different objectives.

Meeting Deadlines

Primary goal:

Task Completion
Before Deadline

Predictability

Execution timing should be known in advance.

Low Latency

Tasks should begin execution quickly.

Reliability

System behavior must remain dependable under all conditions.

Deterministic Performance

Timing behavior should remain consistent.

Key Observation

Deadline Satisfaction
      >
Average Performance

in real-time environments.

5. Real-Time Scheduling Algorithms

Several specialized scheduling algorithms have been developed for real-time systems.

The two most important are:

• Rate Monotonic Scheduling (RMS)

• Earliest Deadline First (EDF)

5.1 Rate Monotonic Scheduling (RMS)

Concept

Rate Monotonic Scheduling assigns priorities based on task frequency.

Rule:

Shorter period → Higher priority

Tasks that execute more frequently receive higher priority.

Example

Priority assignment:

T1 > T2 > T3

because:

10 < 20 < 50

Characteristics

Static Priority Scheduling

Priorities are assigned once.

Preemptive

Higher-priority tasks can interrupt lower-priority tasks.

Suitable for Periodic Tasks

Most effective when task periods are known.

Advantages

• Predictable behavior

• Easy analysis

• Widely used in embedded systems

Limitation

Not always optimal.

Certain feasible task sets may still miss deadlines.

5.2 Earliest Deadline First (EDF)

Concept

Earliest Deadline First dynamically assigns priorities based on deadlines.

Rule:

Task with earliest deadline receives highest priority.

Example

Execution order:

T1 → T2 → T3

because T1 has the nearest deadline.

Characteristics

Dynamic Priority Scheduling

Priorities change continuously.

Preemptive

New tasks may immediately preempt running tasks.

Deadline-Oriented

Scheduling decisions are based entirely on deadlines.

Advantages

• Highly flexible

• Better CPU utilization

• Can schedule larger workloads

Important Property

Under ideal conditions:

EDF is an optimal uniprocessor scheduling algorithm.

If any algorithm can meet all deadlines, EDF can as well.

6. Visualization of Real-Time Scheduling

Consider three tasks:

T1 Deadline = 10

T2 Deadline = 20

T3 Deadline = 30

EDF execution:

T1 → T2 → T3

because deadlines determine priority.

In RMS:

Shortest Period
      ↓
Highest Priority

regardless of immediate deadlines.

7. Key Differences Between RMS and EDF

Key Insight

RMS

Frequent Tasks
      ↓
Higher Priority

EDF

Earlier Deadline
      ↓
Higher Priority

8. Challenges in Real-Time Scheduling

Designing real-time schedulers presents several challenges.

8.1 Deadline Misses

The most critical challenge.

In hard real-time systems:

Missed Deadline
      ↓
Failure

Preventing deadline misses is the scheduler's primary responsibility.

8.2 Resource Contention

Multiple tasks may compete for:

• CPU

• Memory

• I/O devices

Scheduling becomes difficult when resources are limited.

8.3 Priority Inversion

One of the most important interview topics.

A lower-priority task indirectly blocks a higher-priority task.

This can cause unexpected delays.

9. Priority Inversion (Important)

Concept

Priority inversion occurs when:

High Priority Task
      ↓
Waiting
      ↓
Low Priority Task

because the low-priority task holds a required resource.

Example

Step 1

Low-priority task acquires a lock.

Low Priority
      ↓
Resource Acquired

Step 2

High-priority task needs the same lock.

High Priority
      ↓
Blocked

Step 3

Medium-priority tasks execute repeatedly.

Medium Priority Tasks
        ↓
Keep Running

The low-priority task never gets CPU time to release the lock.

The high-priority task remains blocked.

This creates:

Priority Inversion

Solution: Priority Inheritance Protocol

The blocked high-priority task temporarily transfers its priority.

Low Priority Task
        ↓
Inherits High Priority
        ↓
Completes Work
        ↓
Releases Resource

Normal priority is then restored.

This prevents prolonged blocking.

10. Key Observations

Several observations distinguish real-time scheduling from conventional scheduling.

Predictability is More Important Than Speed

The scheduler must guarantee timing behavior.

Preemption is Essential

High-priority tasks often require immediate CPU access.

Deadlines Drive Decisions

Scheduling is deadline-oriented rather than throughput-oriented.

Determinism Matters

Consistent behavior is preferred over average-case performance.

11. Comparison with General Scheduling

Key Difference

General scheduling asks:

How Efficient Is The System?

Real-time scheduling asks:

Can Every Deadline Be Met?