Deferred interrupt processing pattern in FreeRTOS - Time & Space Complexity

Time Complexity: Deferred interrupt processing pattern

O(n)

Understanding Time Complexity

When using deferred interrupt processing in FreeRTOS, we want to understand how the time to handle tasks grows as more interrupts occur.

We ask: How does the processing time change when more events need deferred handling?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void ISR_Handler(void) {
    BaseType_t xHigherPriorityTaskWoken = pdFALSE;
    xQueueSendFromISR(xQueue, &data, &xHigherPriorityTaskWoken);
    portYIELD_FROM_ISR(xHigherPriorityTaskWoken);
}

void DeferredTask(void *pvParameters) {
    DataType data;
    while(1) {
        if(xQueueReceive(xQueue, &data, portMAX_DELAY) == pdPASS) {
            ProcessData(data);
        }
    }
}

This code defers work from an interrupt to a task by sending data to a queue inside the ISR and processing it later in a task.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The task repeatedly waits and receives data from the queue in a loop.
• How many times: Once for each item sent by the ISR, which depends on interrupt frequency.

How Execution Grows With Input

As more interrupts occur, more items are sent to the queue, so the task processes more data items one by one.

Input Size (n)	Approx. Operations
10	10 queue receives and process calls
100	100 queue receives and process calls
1000	1000 queue receives and process calls

Pattern observation: The total work grows directly with the number of deferred items to process.

Final Time Complexity

Time Complexity: O(n)

This means the time to process deferred interrupts grows linearly with the number of interrupts that need handling.

Common Mistake

[X] Wrong: "The ISR processing time dominates and the deferred task time is constant regardless of input."

[OK] Correct: The ISR only queues data quickly, but the deferred task does the real work for each item, so its time grows with the number of items.

Interview Connect

Understanding deferred interrupt processing time helps you design responsive systems and shows you can reason about how tasks scale with workload.

Self-Check

"What if the deferred task processed multiple items in a batch instead of one by one? How would the time complexity change?"

Practice

1. What is the main purpose of the deferred interrupt processing pattern in FreeRTOS?

easy

A. To move heavy processing from the ISR to a task for better system responsiveness

B. To execute all interrupt code inside the ISR for faster response

C. To disable all interrupts during task execution

D. To avoid using semaphores or queues in interrupt handling

Solution

1. Step 1: Understand ISR limitations

   Interrupt Service Routines (ISRs) should be short to keep system responsive.

2. Step 2: Role of deferred processing

   Heavy or time-consuming work is moved to a task, triggered by ISR using semaphores or queues.

3. Final Answer:

   To move heavy processing from the ISR to a task for better system responsiveness -> Option A

4. Quick Check:

   Deferred processing = move work out of ISR [OK]

Hint: Heavy work belongs in tasks, not ISRs [OK]

Common Mistakes:

• Thinking all work should be done inside ISR
• Believing interrupts should be disabled during tasks
• Ignoring use of semaphores or queues

2. Which of the following is the correct way to notify a task from an ISR in FreeRTOS?

easy

A. vTaskDelay()

B. xSemaphoreGive()

C. xSemaphoreGiveFromISR()

D. xQueueSend()

Solution

1. Step 1: Identify ISR-safe functions

   Functions called from ISRs must be ISR-safe variants, like xSemaphoreGiveFromISR().

2. Step 2: Compare options

   xSemaphoreGive() is for tasks, not ISRs; vTaskDelay() is a task delay; xQueueSend() is not ISR-safe.

3. Final Answer:

   xSemaphoreGiveFromISR() -> Option C

4. Quick Check:

   Use FromISR functions inside ISRs [OK]

Hint: Use FromISR suffix functions inside ISRs [OK]

Common Mistakes:

• Using task-only functions inside ISR
• Calling blocking functions in ISR
• Not using FromISR variants

3. Consider this snippet inside an ISR in FreeRTOS:

BaseType_t xHigherPriorityTaskWoken = pdFALSE;
xSemaphoreGiveFromISR(xSemaphore, &xHigherPriorityTaskWoken);
portYIELD_FROM_ISR(xHigherPriorityTaskWoken);

What is the purpose of portYIELD_FROM_ISR() here?

medium

A. To reset the semaphore count

B. To request a context switch if a higher priority task was woken

C. To delay the ISR until the task runs

D. To disable interrupts after giving the semaphore

Solution

1. Step 1: Understand xHigherPriorityTaskWoken

   This flag indicates if giving the semaphore woke a higher priority task.

2. Step 2: Role of portYIELD_FROM_ISR()

   If the flag is true, portYIELD_FROM_ISR() requests a context switch to run the higher priority task immediately.

3. Final Answer:

   To request a context switch if a higher priority task was woken -> Option B

4. Quick Check:

   portYIELD_FROM_ISR triggers context switch [OK]

Hint: portYIELD_FROM_ISR triggers immediate task switch [OK]

Common Mistakes:

• Thinking it disables interrupts
• Assuming it delays ISR execution
• Confusing it with semaphore reset

4. You wrote this ISR code to notify a task:

void ISR_Handler(void) {
    xSemaphoreGive(xSemaphore);
}

Why might this cause problems in FreeRTOS?

medium

A. xSemaphoreGive() is not safe to call from an ISR

B. The semaphore is given twice accidentally

C. The ISR does not clear the interrupt flag

D. The task will never unblock

Solution

1. Step 1: Check function usage in ISR

   xSemaphoreGive() is a task-level function and is not safe to call inside an ISR.

2. Step 2: Correct function to use

   Inside ISR, xSemaphoreGiveFromISR() must be used to safely notify the task.

3. Final Answer:

   xSemaphoreGive() is not safe to call from an ISR -> Option A

4. Quick Check:

   Use FromISR functions in ISRs [OK]

Hint: Never call task functions inside ISR, use FromISR versions [OK]

Common Mistakes:

• Calling task functions inside ISR
• Forgetting to clear interrupt flags
• Assuming semaphore gives always unblock tasks

5. You want to implement deferred interrupt processing where an ISR signals a task to process sensor data. Which sequence correctly follows FreeRTOS best practices?

hard

A. Task polls sensor data continuously, ISR disables interrupts

B. ISR processes sensor data directly, then calls vTaskDelay()

C. ISR sends data via xQueueSend(), task never blocks

D. ISR calls xSemaphoreGiveFromISR(), then task waits on semaphore and processes data

Solution

1. Step 1: ISR role in deferred processing

   ISR should be short and only notify the task using xSemaphoreGiveFromISR().

2. Step 2: Task role in processing

   The task waits on the semaphore and processes sensor data when notified.

3. Final Answer:

   ISR calls xSemaphoreGiveFromISR(), then task waits on semaphore and processes data -> Option D

4. Quick Check:

   ISR signals, task processes data [OK]

Hint: ISR signals; task does heavy work [OK]

Common Mistakes:

• Doing heavy work inside ISR
• Using blocking calls inside ISR
• Not synchronizing task and ISR properly