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.)

Practice

1. What is the primary purpose of the PendSV exception in ARM processors?

easy

A. To reset the processor

B. To provide a regular timer interrupt

C. To handle task switching smoothly in the background

D. To manage memory access

Solution

1. Step 1: Understand PendSV role

   PendSV is designed to handle context switching between tasks without interrupting the main program flow.

2. Step 2: Compare with other exceptions

   Unlike SysTick, which provides timing interrupts, PendSV is specifically for smooth task switching.

3. Final Answer:

   To handle task switching smoothly in the background -> Option C

4. Quick Check:

   PendSV = task switching [OK]

Hint: PendSV = background task switcher [OK]

Common Mistakes:

• Confusing PendSV with SysTick timer
• Thinking PendSV resets the processor
• Assuming PendSV manages memory

2. Which of the following is the correct way to enable the SysTick timer in ARM Cortex-M processors?

easy

A. Set the CTRL register's ENABLE bit to 1

B. Clear the CTRL register's ENABLE bit to 0

C. Write 0xFFFFFFFF to the LOAD register

D. Disable the PendSV exception

Solution

1. Step 1: Identify SysTick control

   The SysTick timer is controlled by the CTRL register, where setting the ENABLE bit starts the timer.

2. Step 2: Eliminate incorrect options

   Clearing ENABLE stops the timer, writing max to LOAD sets reload value but doesn't enable, and disabling PendSV is unrelated.

3. Final Answer:

   Set the CTRL register's ENABLE bit to 1 -> Option A

4. Quick Check:

   SysTick enable = CTRL ENABLE bit set [OK]

Hint: Enable SysTick by setting CTRL ENABLE bit [OK]

Common Mistakes:

• Confusing enabling with disabling bits
• Thinking LOAD register enables timer
• Mixing PendSV control with SysTick

3. Consider this simplified ARM Cortex-M code snippet:

SysTick->LOAD = 1000 - 1;
SysTick->VAL = 0;
SysTick->CTRL = 7;

What does the value 7 in SysTick->CTRL represent?

medium

A. Enable SysTick, enable interrupt, and use processor clock

B. Disable SysTick and interrupts

C. Enable SysTick only without interrupts

D. Reset SysTick counter

Solution

1. Step 1: Decode CTRL register bits

   Value 7 in binary is 0b111, meaning bits ENABLE(0), TICKINT(1), and CLKSOURCE(2) are set.

2. Step 2: Understand each bit meaning

   ENABLE starts the timer, TICKINT enables interrupt, CLKSOURCE selects processor clock.

3. Final Answer:

   Enable SysTick, enable interrupt, and use processor clock -> Option A

4. Quick Check:

   CTRL=7 means all three bits set [OK]

Hint: 7 in CTRL means enable + interrupt + clock source [OK]

Common Mistakes:

• Ignoring interrupt enable bit
• Assuming 7 disables timer
• Confusing bits order

4. A developer writes this code to trigger PendSV manually:

SCB->ICSR |= (1 << 28);

But the PendSV exception does not occur. What is the likely cause?

medium

A. ICSR register is read-only

B. SysTick timer is disabled

C. PendSV cannot be triggered manually

D. PendSV priority is not set low enough

Solution

1. Step 1: Understand PendSV triggering

   Writing to ICSR bit 28 sets the PendSV pending flag, but PendSV only runs if its priority is low enough.

2. Step 2: Identify common mistake

   If PendSV priority is higher or equal to other interrupts, it won't run even if pending.

3. Final Answer:

   PendSV priority is not set low enough -> Option D

4. Quick Check:

   PendSV priority must be low to run [OK]

Hint: PendSV needs low priority to run when pending [OK]

Common Mistakes:

• Assuming ICSR is read-only
• Thinking SysTick affects PendSV trigger
• Believing PendSV can't be triggered manually

5. In a real-time operating system (RTOS) on ARM Cortex-M, how do PendSV and SysTick work together to manage multitasking?

hard

A. PendSV triggers timer interrupts; SysTick switches tasks

B. SysTick triggers regular interrupts; PendSV performs context switching after SysTick

C. Both PendSV and SysTick handle memory management

D. SysTick disables PendSV during task switching

Solution

1. Step 1: Understand SysTick role in RTOS

   SysTick generates periodic interrupts to keep track of time slices and trigger scheduler checks.

2. Step 2: Understand PendSV role in RTOS

   PendSV is triggered by the scheduler to perform the actual task context switch smoothly in the background.

3. Step 3: Combine roles for multitasking

   SysTick signals when to switch; PendSV does the switch, enabling efficient multitasking.

4. Final Answer:

   SysTick triggers regular interrupts; PendSV performs context switching after SysTick -> Option B

5. Quick Check:

   SysTick = timer, PendSV = switcher [OK]

Hint: SysTick triggers; PendSV switches tasks [OK]

Common Mistakes:

• Swapping roles of PendSV and SysTick
• Thinking both handle memory
• Assuming SysTick disables PendSV