Deferred interrupt processing architecture in FreeRTOS - Time & Space Complexity

Time Complexity: Deferred interrupt processing architecture

O(n)

Understanding Time Complexity

When using deferred interrupt processing, we want to know how the time to handle interrupts changes as more interrupts happen.

We ask: How does the system's work grow when more interrupts are deferred for later processing?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Interrupt Service Routine (ISR)
void ISR_Handler() {
    BaseType_t xHigherPriorityTaskWoken = pdFALSE;
    xQueueSendFromISR(deferredQueue, &data, &xHigherPriorityTaskWoken);
    portYIELD_FROM_ISR(xHigherPriorityTaskWoken);
}

// Deferred processing task
void DeferredTask(void *params) {
    DataType data;
    while(1) {
        if(xQueueReceive(deferredQueue, &data, portMAX_DELAY) == pdPASS) {
            ProcessData(data);
        }
    }
}
    

This code defers work from the interrupt to a task by sending data to a queue, then the task processes each item.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The deferred task loops forever, receiving and processing each queued item one by one.
• How many times: Once per deferred interrupt event, so as many times as interrupts occur.

How Execution Grows With Input

Each interrupt adds one item to the queue, and the task processes each item individually.

Input Size (n)	Approx. Operations
10	10 processing calls
100	100 processing calls
1000	1000 processing calls

Pattern observation: The work grows directly with the number of interrupts deferred.

Final Time Complexity

Time Complexity: O(n)

This means the total processing time grows linearly with the number of deferred interrupts.

Common Mistake

[X] Wrong: "Deferring work means the interrupt handling time is always constant no matter how many interrupts happen."

[OK] Correct: While the interrupt itself is quick, the deferred task must still process each item, so total work grows with the number of interrupts.

Interview Connect

Understanding how deferred interrupt processing scales helps you design responsive systems and shows you can think about how code behaves as load increases.

Self-Check

"What if the deferred task processed multiple items at once instead of one by one? How would the time complexity change?"

Practice

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

easy

A. To disable all interrupts during task execution

B. To execute all interrupt code inside the ISR for speed

C. To split interrupt handling between a fast ISR and a slower task

D. To avoid using queues or notifications in interrupt handling

Solution

1. Step 1: Understand ISR limitations

   ISRs should be short to keep system responsive and avoid blocking other interrupts.

2. Step 2: Role of deferred processing

   Deferred processing moves longer work to a task, improving system reliability and responsiveness.

3. Final Answer:

   To split interrupt handling between a fast ISR and a slower task -> Option C

4. Quick Check:

   Deferred interrupt processing = splitting work [OK]

Hint: Remember: ISR is fast, task does the heavy work [OK]

Common Mistakes:

• Thinking all work should be done inside ISR
• Believing interrupts are disabled during task execution
• Ignoring the use of task notifications or queues

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

easy

A. xTaskNotifyGiveFromISR(taskHandle, &higherPriorityTaskWoken);

B. xTaskNotifyGive(taskHandle);

C. vTaskDelay(10);

D. xQueueSend(queueHandle, &data, portMAX_DELAY);

Solution

1. Step 1: Identify ISR-safe notification function

   Only functions ending with 'FromISR' are safe to call inside ISRs.

2. Step 2: Check options

   xTaskNotifyGiveFromISR is designed for ISR context; others are not ISR-safe or unrelated.

3. Final Answer:

   xTaskNotifyGiveFromISR(taskHandle, &higherPriorityTaskWoken); -> Option A

4. Quick Check:

   ISR notification uses FromISR functions [OK]

Hint: Use 'FromISR' functions inside ISRs only [OK]

Common Mistakes:

• Using normal task notification functions inside ISR
• Calling blocking functions like vTaskDelay in ISR
• Using queue send with infinite block time inside ISR

3. Given the following code snippet, what will be the output?

void ISR_Handler() {
    BaseType_t xHigherPriorityTaskWoken = pdFALSE;
    xTaskNotifyGiveFromISR(taskHandle, &xHigherPriorityTaskWoken);
    portYIELD_FROM_ISR(xHigherPriorityTaskWoken);
}

void TaskFunction(void *pvParameters) {
    for(;;) {
        ulTaskNotifyTake(pdTRUE, portMAX_DELAY);
        printf("Task notified\n");
    }
}

medium

A. Task notified printed only once

B. No output because task is never notified

C. Compilation error due to missing parameters

D. Task notified printed each time ISR runs

Solution

1. Step 1: Analyze ISR notification

   ISR calls xTaskNotifyGiveFromISR which increments the task's notification count and may cause context switch.

2. Step 2: Analyze task behavior

   Task blocks on ulTaskNotifyTake until notified, then prints "Task notified" and loops back to wait again.

3. Final Answer:

   Task notified printed each time ISR runs -> Option D

4. Quick Check:

   ISR notifies task -> task prints [OK]

Hint: ISR notification wakes task repeatedly [OK]

Common Mistakes:

• Assuming task never wakes up
• Confusing notification count with binary flag
• Thinking task prints only once

4. Identify the error in this deferred interrupt processing code snippet:

void ISR_Handler() {
    xQueueSend(queueHandle, &data, portMAX_DELAY);
}

void TaskFunction(void *pvParameters) {
    for(;;) {
        if(xQueueReceive(queueHandle, &receivedData, portMAX_DELAY) == pdPASS) {
            process(receivedData);
        }
    }
}

medium

A. xQueueReceive should be called from ISR

B. Using portMAX_DELAY in ISR causes a blocking call

C. ISR should not send data to queue

D. Task should not block on queue receive

Solution

1. Step 1: Check ISR queue send parameters

   portMAX_DELAY causes blocking; ISRs must never block or wait.

2. Step 2: Correct usage in ISR

   Use xQueueSendFromISR with zero block time to avoid blocking in ISR.

3. Final Answer:

   Using portMAX_DELAY in ISR causes a blocking call -> Option B

4. Quick Check:

   ISRs must not block = no portMAX_DELAY in ISR [OK]

Hint: Never block inside ISR; use FromISR functions with zero wait [OK]

Common Mistakes:

• Using blocking calls inside ISR
• Calling task functions from ISR
• Confusing ISR and task context functions

5. You want to design a deferred interrupt processing system where multiple ISRs notify a single task to process different events. Which approach best ensures the task processes all events without missing any notifications?

hard

A. Use a queue to send event data from each ISR to the task

B. Use xTaskNotifyGiveFromISR from each ISR without data

C. Use global flags set by ISRs and polled by the task

D. Disable interrupts while the task processes events

Solution

1. Step 1: Understand notification limitations

   xTaskNotifyGiveFromISR increments a count but cannot carry event data, risking lost info if multiple events occur quickly.

2. Step 2: Use queue for event data

   Queues can hold multiple event messages safely, ensuring the task processes all events without loss.

3. Final Answer:

   Use a queue to send event data from each ISR to the task -> Option A

4. Quick Check:

   Queues hold multiple events safely [OK]

Hint: Use queues to handle multiple event data safely [OK]

Common Mistakes:

• Relying on notifications without event data
• Using global flags causing race conditions
• Disabling interrupts too long hurting responsiveness