Exception priority levels in ARM Architecture - Time & Space Complexity

Time Complexity: Exception priority levels

O(n)

Understanding Time Complexity

When dealing with exception priority levels in ARM architecture, it is important to understand how the processor decides which exception to handle first when multiple occur.

We want to analyze how the time to decide and handle exceptions grows as the number of exceptions increases.

Scenario Under Consideration

Analyze the time complexity of the following simplified ARM exception priority check.

    LDR R0, =EXCEPTIONS       ; Load base address of exceptions
    MOV R1, #NUM_EXCEPTIONS   ; Number of exceptions
    MOV R2, #0                ; Index
    MOV R4, #0                ; Initialize current highest priority
  LOOP:
    LDR R3, [R0, R2, LSL #2] ; Load priority of exception at index
    CMP R3, R4                ; Compare with current highest priority
    BLS SKIP                  ; If lower or same, skip
    MOV R4, R3                ; Update highest priority
    MOV R5, R2                ; Save index of highest priority
  SKIP:
    ADD R2, R2, #1            ; Increment index
    CMP R2, R1                ; Check if all exceptions checked
    BLT LOOP                  ; Loop if not done
    

This code loops through all exceptions to find the one with the highest priority.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each exception to compare priorities.
• How many times: Exactly once for each exception, so the number of exceptions times.

How Execution Grows With Input

As the number of exceptions increases, the processor must check each one to find the highest priority.

Input Size (n)	Approx. Operations
10	10 priority checks
100	100 priority checks
1000	1000 priority checks

Pattern observation: The number of operations grows directly with the number of exceptions.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the highest priority exception grows linearly as the number of exceptions increases.

Common Mistake

[X] Wrong: "The processor can instantly know the highest priority exception without checking all."

[OK] Correct: The processor must compare each exception's priority to be sure which one is highest, so it takes time proportional to the number of exceptions.

Interview Connect

Understanding how exception priority checking scales helps you reason about processor responsiveness and system design, a useful skill in embedded systems and hardware-related roles.

Self-Check

"What if the exceptions were stored in a sorted list by priority? How would the time complexity change?"

Practice

1. In ARM architecture, what does a lower exception priority number indicate?

easy

A. No priority assigned

B. Lower priority for handling the exception

C. Higher priority for handling the exception

D. Equal priority to all exceptions

Solution

1. Step 1: Understand priority numbering in ARM

   In ARM processors, exception priority levels use numbers where lower numbers mean higher priority.

2. Step 2: Interpret the meaning of lower numbers

   A lower number means the exception is handled before others with higher numbers.

3. Final Answer:

   Higher priority for handling the exception -> Option C

4. Quick Check:

   Lower number = Higher priority [OK]

Hint: Lower number means higher priority in ARM exceptions [OK]

Common Mistakes:

• Thinking higher numbers mean higher priority
• Assuming all exceptions have equal priority
• Confusing priority with exception type

2. Which of the following correctly represents the priority order in ARM exception levels from highest to lowest?

easy

A. 3, 2, 1, 0

B. 0, 1, 2, 3

C. 1, 0, 3, 2

D. 2, 3, 0, 1

Solution

1. Step 1: Recall ARM priority numbering

   Lower numbers indicate higher priority, so priority order starts from 0 upwards.

2. Step 2: Arrange numbers from lowest to highest

   The correct order from highest to lowest priority is 0, 1, 2, 3.

3. Final Answer:

   0, 1, 2, 3 -> Option B

4. Quick Check:

   Priority order = 0 to 3 [OK]

Hint: Priority order counts up from 0 as highest [OK]

Common Mistakes:

• Reversing the order thinking higher numbers are higher priority
• Mixing up the sequence of numbers
• Assuming priority starts at 1 instead of 0

3. Given these exception priorities in ARM: IRQ = 2, FIQ = 0, SVC = 1, which exception will be handled first?

medium

A. FIQ

B. IRQ

C. SVC

D. All handled simultaneously

Solution

1. Step 1: Identify priority numbers for each exception

   FIQ has priority 0, SVC has 1, IRQ has 2.

2. Step 2: Determine which priority is highest

   Lower number means higher priority, so FIQ with 0 is handled first.

3. Final Answer:

   FIQ -> Option A

4. Quick Check:

   Lowest number (0) = FIQ first [OK]

Hint: Exception with priority 0 handled first [OK]

Common Mistakes:

• Choosing IRQ because it sounds more common
• Assuming SVC is highest priority by name
• Thinking all exceptions run at the same time

4. If an ARM system incorrectly assigns a higher number to a critical exception, what is the likely problem?

medium

A. The critical exception may be delayed or ignored

B. The system will crash immediately

C. All exceptions will have equal priority

D. The critical exception will run first anyway

Solution

1. Step 1: Understand priority impact on handling

   Higher numbers mean lower priority, so a critical exception with a high number is handled later.

2. Step 2: Predict system behavior

   This delay can cause the critical exception to be delayed or missed, affecting system reliability.

3. Final Answer:

   The critical exception may be delayed or ignored -> Option A

4. Quick Check:

   Wrong priority number delays critical exception [OK]

Hint: Critical exceptions need lowest priority number [OK]

Common Mistakes:

• Assuming system crashes immediately
• Thinking priority numbers do not affect handling
• Believing all exceptions run equally regardless of priority

5. You have three exceptions with priorities: Timer = 1, UART = 3, Reset = 0. If Timer, UART, and Reset exceptions occur simultaneously, which will ARM handle first and why?

hard

A. UART, because it has the highest number

B. Timer, because it occurs first

C. Timer, because it has a medium priority

D. Reset, because it has the lowest number

Solution

1. Step 1: Identify priorities and exceptions involved

   Reset has priority 0, Timer 1, UART 3. Timer, UART, and Reset occur simultaneously.

2. Step 2: Determine which exception ARM handles first

   ARM handles the exception with the lowest priority number first, which is Reset with 0.

3. Step 3: Understand simultaneous exceptions handling

   Since Reset has the highest priority, it preempts others.

4. Final Answer:

   Reset, because it has the lowest number -> Option D

5. Quick Check:

   Lowest number = highest priority = Reset first [OK]

Hint: Lowest priority number exception handled first always [OK]

Common Mistakes:

• Overlooking Reset's highest priority
• Picking Timer due to medium priority
• Choosing UART because it occurs simultaneously