Real-Time Scheduling

Real-Time Task Deadline Definition

• The latest time a task must be completed.

• Requires predictable behavior.

• Guarantees tasks meet deadlines.

CPU Utilization Formula

• Utilization (U) formula: $U = \frac{ctotal - cidle}{ctotal} \leq 1$.

• ctotal: total CPU time.

• cidle: idle time.

Real-Time Analysis Assumptions

• Tasks are periodic.
• Deadline equals next invocation.
• No time cost for context switches.

Periodic Task Set Utilization

• For tasks T₁…Tₙ: total utilization $U = \sum \left( \frac{cᵢ}{pᵢ} \right) \leq 1$.
• cᵢ: CPU time.
• pᵢ: period.

Schedulability Requirement

• A real-time system is schedulable if all tasks meet their deadlines.
• Requires $U = \sum \left( \frac{cᵢ}{pᵢ} \right) \leq 1$.

Static Cyclic Scheduling

• Tasks finish within the most frequent task's period.
• Uses a table for fixed time slots.
• Simple but inflexible.

Fixed Priority Scheduling

• Priorities assigned at compile time.
• Simple and predictable behavior.
• Optimal scheme: Rate Monotonic Scheduling.

Dynamic Priority Scheduling

• Priorities change during runtime based on criteria.
• More flexible but complex.
• Optimal scheme: Earliest Deadline First.

Rate Monotonic Scheduling (RMS)

• Optimal fixed-priority scheme.
• Highest priority for most frequent task.
• Priority based on frequency.

RMS Requirements

• Tasks are independent.
• Fixed CPU requirements.
• Free context switching.
• Deadline equals task period.

RMS Utilization Bound

• Guaranteed schedulable if $U = \sum \left( \frac{cᵢ}{pᵢ} \right) \leq n(2^{\frac{1}{n}} - 1)$.
• Approaches 69% as n increases.

RMS Priority Assignment Example

• Task C (50Hz): highest priority.
• Task A (2Hz): medium priority.
• Task B (0.1Hz): lowest priority.

RMS Optimality

• Optimal among fixed-priority schemes.
• No better manual priority assignment for meeting deadlines.

RMS Beyond Utilization Bound

• Tasks exceeding 69% may still be schedulable.
• Requires specific set analysis.

Utilizing Spare CPU Capacity

• Remaining CPU time can run low-priority background jobs.
• Up to 30% of CPU capacity.

Harmonic Task Sets

• Each task period is a multiple of higher priority periods.
• Example: 15ms, 30ms, 120ms vs 17ms, 31ms, 130ms.

Harmonic RMS Benefits

• Can achieve 100% utilization.
• Easier analysis.
• Regular execution patterns.

Earliest Deadline First (EDF)

• Dynamic priority scheduling.
• Task with earliest deadline runs first.
• Can achieve 100% utilization.

EDF Characteristics

• More complex scheduler.
• Handles changing task importance.
• Not stable under overload.

EDF vs RMS Comparison

• EDF: higher utilization possible, dynamic, more overhead.
• RMS: simpler, 69% bound, stable under overload.