MinhQuan805

Posted on Aug 25 • Edited on Aug 31

How does CPU scheduling ensure that every real-time task meets its deadline?

#os

For a deeper understanding of operating systems and related concepts, feel free to explore more resources on my website: Quan Notes

Scheduling is the strategy of selecting the most suitable process to execute in order to achieve the highest efficiency.

Real-time systems are designed to perform real-time tasks, which need to be executed immediately with a certain degree of urgency.

CPU scheduling for real-time systems poses many challenges due to the real-time requirements.

There are two types of real-time systems:

Soft real-time systems: Critical tasks are given the highest priority, but no other guarantees are provided.
Hard real-time systems: Tasks must be completed before their deadlines. If a task misses its deadline, it is considered a failure, and execution after the deadline has no value or may be canceled by the system.

In this article, we will explore some issues related to process scheduling in both soft and hard real-time systems.

I. Minimizing Latency

Real-time systems operate on an event-driven model, waiting for events from software (e.g., a timer expiring) or hardware (e.g., a remote-controlled device detecting an obstacle). When an event occurs, the system must respond and process it quickly.
Event latency is the time from when an event occurs to when it is serviced.

Events in real-time systems have varying latency requirements. For example, an anti-lock braking system requires a latency of 3–5 milliseconds to respond when a wheel slips, otherwise the car may lose control. In contrast, a radar system on an aircraft may tolerate a latency of a few seconds.
There are two decision-making modes in scheduling:

Non-preemptive: Once in the running state, a process will execute until it completes or is interrupted due to an I/O request.
Preemptive: A running process can be interrupted mid-execution and moved back to the ready state.

The performance of real-time systems is affected by two types of latency:

Interrupt Latency: The time from when an interrupt reaches the CPU to when the interrupt service routine (ISR) begins.

The operating system must complete the current instruction, identify the type of interrupt, save the current process state, and then handle the interrupt.
Minimizing and bounding interrupt latency is critical, especially in hard real-time systems, and interrupts can only be disabled for very short periods to update kernel data structures.

Dispatch Latency: The time it takes for the scheduler to stop one process and start another. The most effective technique for keeping dispatch latency low is to provide a preemptive kernel, which includes:

Conflict Phase: Pausing kernel tasks and releasing resources from lower-priority processes.
Dispatch Phase: Scheduling a higher-priority process onto the CPU.

Real-time systems need to minimize both interrupt latency and dispatch latency to ensure immediate responses for real-time tasks.

II. Priority-Based Scheduling

The core feature of a real-time operating system is the ability to respond immediately to real-time processes when they request CPU time. Therefore, the scheduler must support priority-based scheduling with preemption.

These algorithms assign priorities to processes based on their importance; more critical tasks are given higher priority.
If preemption is supported, a running process will be paused when a higher-priority process becomes ready.

Examples:

Operating systems like Windows, Linux, and Solaris assign the highest priority to real-time processes.
Windows has 32 priority levels, with levels 16–31 reserved for real-time processes. Linux and Solaris have similar mechanisms.

Limitations:

Priority-based scheduling with preemption only guarantees functionality for soft real-time systems.
Hard real-time systems further ensure that tasks are serviced by their deadlines, requiring additional scheduling features.

III. Task Models in Real-Time Systems

1. Periodic Tasks

These are real-time tasks that repeat after a fixed time interval, known as the period.

These tasks are triggered by clock interrupts. For example, collecting data from a sensor every 5 seconds.

a. Rate Monotonic Scheduling (RMS)

Priority is assigned based on the inverse of the period: shorter periods receive higher priority, and longer periods receive lower priority.
A set of processes can be scheduled if it satisfies the formula:

Where:

To understand Rate Monotonic scheduling, consider the following example table:

Calculating Utilization (U):

The RMS threshold for n = 3:

Result: U=0.75 ≤ 0.7797, so this set of processes is schedulable with RMS.

Based on periods:

• P1(T1 = 20): Lowest priority.

• P2(T2 = 5): Highest priority.

• P3(T3 = 10): Second-highest priority.

Priority order: P2 > P3 > P1.

b. Earliest Deadline First (EDF)

This is an optimal dynamic priority scheduling algorithm for real-time systems, applicable to both static and dynamic scheduling.
Priority Principle: The process with the earliest deadline is assigned the highest priority, while processes with later deadlines receive lower priority.
High Efficiency: Can achieve 100% CPU utilization while ensuring all processes meet their deadlines, as long as the schedule is feasible.
Priority Adjustment: When a new process becomes ready, it announces its deadline to the system, and the priorities of existing processes are dynamically adjusted based on the new deadline.

2. Aperiodic Tasks

These are real-time tasks that occur at random times, without a fixed period.

The time between two occurrences can be very short (even zero) or very long.
These tasks are typically soft real-time and involve random interactions, e.g., pressing a key on a keyboard for input.
Scheduling algorithms for periodic tasks, such as Total Bandwidth Server and Enhanced Virtual Release Advancing, can be explored further.