Task Scheduling

Scheduling is the mechanism by which the RTOS kernel decides which task runs at any given instant. The choice of scheduling algorithm directly determines whether deadlines are met and how fairly CPU time is distributed. Two fundamental approaches exist: preemptive scheduling and cooperative scheduling. GATE questions on RTOS frequently test the ability to trace through scheduling timelines and compute completion times.

Core Concept Explanation

In preemptive scheduling, the kernel has full authority to suspend a currently running task and replace it with a higher-priority task at any moment, including in the middle of a function. This is triggered by an interrupt, a timer tick, or an API call that unblocks a higher-priority task. Preemptive scheduling is used in almost all modern RTOS implementations because it guarantees that critical tasks always get the CPU when needed, regardless of what lower-priority tasks are doing.

In cooperative scheduling, the kernel only switches tasks when the current task voluntarily yields the CPU by calling a yield or blocking function. The kernel never interrupts a running task forcefully. This is simpler to implement and avoids race conditions on shared resources, but it requires every task to be well-behaved. A single buggy task that never yields can starve all other tasks permanently.

The Round Robin scheduling algorithm is a special case of preemptive scheduling where all tasks at the same priority level receive equal time slices (also called a time quantum). After each time slice expires, the scheduler moves to the next task at the same priority. This prevents any single same-priority task from monopolizing the CPU. Round Robin is combined with priority-based preemption in most RTOS to handle both fairness and urgency.

Mathematical Expression

For a Rate Monotonic Scheduler (RMS), task priorities are assigned inversely proportional to their periods. The task with the shortest period gets the highest priority. This is provably optimal for fixed-priority preemptive scheduling of periodic tasks. The schedulability condition is: sum of Ci/Ti for i=1 to n must be less than or equal to n(2^(1/n) - 1).

For Earliest Deadline First (EDF) scheduling, the task whose absolute deadline is closest gets highest priority at every scheduling instant. EDF is dynamically optimal and can schedule any task set with total utilization up to 100 percent (U <= 1.0). However, EDF requires dynamic priority computation at runtime, which adds overhead compared to fixed-priority RMS.

Practical Understanding

In FreeRTOS, preemptive scheduling with Round Robin for equal-priority tasks is the default configuration. The scheduler runs at every tick interrupt. The tick period is configurable (configTICK_RATE_HZ). A typical value is 1000 Hz (1ms tick). Higher tick rates give finer time resolution but increase context switch overhead.

The choice between preemptive and cooperative scheduling depends on the application. Safety-critical systems use preemptive scheduling to ensure critical tasks always execute on time. Simple single-function embedded firmware sometimes uses cooperative scheduling for code simplicity. Many industrial RTOS support both modes and allow configuration at build time.

Given:
3 tasks using Round Robin at same priority:
Task A: needs 3 time slices to complete
Task B: needs 2 time slices to complete
Task C: needs 4 time slices to complete
Time quantum = 1 unit

Why this formula applies:
Round Robin gives each task one quantum in turn.
Completion time = when task gets its last required quantum.

Schedule (sequential rounds):
Round 1: A(1), B(1), C(1)
Round 2: A(2), B(2), C(2)  -> B completes at end of slot 6
Round 3: A(3), C(3)        -> A completes at slot 8, C gets slot 9
Round 4: C(4)              -> C completes at slot 9

Completion Times:
Task B = 6 units
Task A = 8 units
Task C = 9 units

Formula for Turnaround Time = Completion Time - Arrival Time
All arrive at t=0:
Turnaround A = 8, B = 6, C = 9
Average Turnaround = (8 + 6 + 9) / 3 = 7.67 units

Final Answer:
Average turnaround time = 7.67 time units

Exam Tip: In GATE, EDF can achieve up to 100% CPU utilization while RMS is limited to ~69.3% for large task sets. However, EDF suffers from domino effect under overload: if utilization exceeds 1.0, all tasks may miss deadlines simultaneously. RMS degrades more gracefully under overload.

Mechanism - Scheduling Decision Steps

• At every tick interrupt, the scheduler scans the ready queue for the highest-priority task and compares it with the currently running task.
• If a higher-priority task is ready, a context switch is immediately triggered (preemptive mode only).
• For tasks at the same priority, Round Robin assigns each task a fixed time quantum. After the quantum expires, the next same-priority task is selected.
• In EDF scheduling, the priority of every ready task is recomputed at each scheduling event based on its absolute deadline, which is (release time + relative deadline).
• Cooperative mode: scheduling only occurs at yield points (taskYIELD() in FreeRTOS) or when a task calls a blocking function, so tick interrupt does not trigger preemption.

Quick Revision

• Preemptive: kernel can interrupt running task at any time. Cooperative: task must yield voluntarily.
• Round Robin: equal priority tasks share CPU in fixed time quantum slots, preventing starvation at same priority level.
• RMS: fixed priority, period inversely proportional to priority. Bound: U <= n(2^(1/n)-1), converges to 0.693.
• EDF: dynamic priority based on closest deadline. Bound: U <= 1.0. Optimal but complex to implement.
• Exam trap: If U <= 0.693, RMS always schedulable. If 0.693 < U <= 1.0, RMS test is inconclusive (may or may not work). EDF always works up to U = 1.0.
• Domino effect: EDF under overload (U > 1.0) causes all tasks to miss deadlines. RMS under overload causes only lowest-priority tasks to miss.