PendSV and SysTick exceptions in ARM Architecture - Time & Space Complexity

Time Complexity: PendSV and SysTick exceptions

O(1)

Understanding Time Complexity

We want to understand how the time taken by PendSV and SysTick exceptions changes as the system workload grows.

Specifically, how does handling these exceptions scale with the number of tasks or timer ticks?

Scenario Under Consideration

Analyze the time complexity of the following simplified ARM exception handlers.

PendSV_Handler:
    // Save context (fixed registers to current task stack)
    // Switch to next task (scheduler selects next TCB)
    // Restore context (fixed registers from next task stack)
    BX LR

SysTick_Handler:
    INC tick_count
    IF tick_count % TIME_SLICE == 0
        SET PendSV pending
    BX LR
    

This code switches tasks when the SysTick timer reaches a time slice, using PendSV to perform the context switch.

Identify Repeating Operations

Look at what repeats as the system runs.

• Primary operation: PendSV context switch involves saving current task's fixed-size state to its stack and restoring next task's from its stack.
• How many times: SysTick fires regularly (e.g., every millisecond), PendSV runs only on task switches (e.g., every time slice).

How Execution Grows With Input

As the number of tasks increases, context switch frequency may rise, but work per PendSV invocation stays fixed: always save/restore same registers for current/next task.

Number of Tasks (n)	Approx. Operations per Switch
2	Fixed (~16-20 instr: push/pop registers, update SP)
10	Fixed (same ~16-20 instr)
100	Fixed (same ~16-20 instr)

Pattern observation: Time per PendSV/SysTick handler is constant, independent of n.

Final Time Complexity

Time Complexity: O(1)

Per-exception handling time for PendSV and SysTick is constant-time (fixed instructions), regardless of task count. (Scheduler may add minor overhead, often O(1) or O(log n).)

Common Mistake

[X] Wrong: "PendSV time grows with n because more tasks' states must be saved/restored."

[OK] Correct: Each task has its own stack; PendSV only handles current/next task's fixed register set (~17 registers in Cortex-M). Other tasks' states untouched.

Interview Connect

Grasping O(1) context switch cost shows RTOS insight; contrasts with O(n) naive schedulers, key for embedded performance discussions.

Self-Check

What if the system used a fixed-size context save area regardless of the number of tasks? How would the time complexity change?

(This is standard; stays O(1). Saving all tasks each switch would be O(n), but inefficient/not done.)