Queue from ISR (xQueueSendFromISR) in FreeRTOS - Time & Space Complexity

Time Complexity: Queue from ISR (xQueueSendFromISR)

O(1)

Understanding Time Complexity

When using queues inside an interrupt service routine (ISR), it's important to know how the time to send data grows as the queue size changes.

We want to understand how the cost of sending to a queue from an ISR scales with input size.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

BaseType_t xHigherPriorityTaskWoken = pdFALSE;

// Attempt to send an item to the queue from ISR
BaseType_t result = xQueueSendFromISR(xQueue, &item, &xHigherPriorityTaskWoken);

// Optionally request a context switch if needed
portYIELD_FROM_ISR(xHigherPriorityTaskWoken);
    

This code sends an item to a FreeRTOS queue from an ISR and may trigger a context switch if a higher priority task was waiting.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting an item into the queue's circular buffer.
• How many times: This operation happens once per call to xQueueSendFromISR.

How Execution Grows With Input

The time to send an item does not grow with the number of items already in the queue.

Input Size (Queue Length)	Approx. Operations
10	Constant steps to insert one item
100	Same constant steps, independent of queue size
1000	Still constant steps, no extra work for larger queue

Pattern observation: The operation time stays the same no matter how many items are in the queue.

Final Time Complexity

Time Complexity: O(1)

This means sending to the queue from an ISR takes the same amount of time regardless of queue size.

Common Mistake

[X] Wrong: "Sending to a queue from an ISR takes longer if the queue has more items inside."

[OK] Correct: The queue uses a circular buffer, so adding an item is a simple pointer update and copy, which does not depend on how full the queue is.

Interview Connect

Understanding constant time operations in embedded systems shows you know how to write efficient interrupt code that keeps the system responsive.

Self-Check

"What if the queue was replaced with a linked list that requires traversal to insert? How would the time complexity change?"

Practice

1.

What is the primary purpose of xQueueSendFromISR() in FreeRTOS?

easy

A. To send data to a queue safely from an interrupt service routine (ISR)

B. To create a new queue in the system

C. To delete a queue from an ISR

D. To block a task until data is received

Solution

1. Step 1: Understand the function context

   xQueueSendFromISR() is designed to be called inside an ISR, where normal queue functions that can block are unsafe.

2. Step 2: Identify the function's role

   It safely sends data to a queue without blocking, allowing communication from ISR to tasks.

3. Final Answer:

   To send data to a queue safely from an interrupt service routine (ISR) -> Option A

4. Quick Check:

   Purpose of xQueueSendFromISR = safe queue send from ISR [OK]

Hint: Remember: xQueueSendFromISR is for sending data inside interrupts [OK]

Common Mistakes:

• Confusing it with queue creation or deletion
• Thinking it blocks the ISR
• Using normal queue send functions inside ISR

2.

Which of the following is the correct way to call xQueueSendFromISR()?

BaseType_t xQueueSendFromISR(QueueHandle_t xQueue, const void * pvItemToQueue, BaseType_t *pxHigherPriorityTaskWoken);

easy

A. xQueueSendFromISR(queue, data, NULL);

B. xQueueSendFromISR(queue, &data, NULL);

C. xQueueSendFromISR(&queue, &data, NULL);

D. xQueueSendFromISR(queue, &data);

Solution

1. Step 1: Check parameter types

   The function expects a queue handle, a pointer to the data, and a pointer to a BaseType_t variable for task wake flag.

2. Step 2: Match correct call

   xQueueSendFromISR(queue, &data, NULL); passes the queue handle, address of data, and NULL for the last parameter, which is valid if you don't care about task wake.

3. Final Answer:

   xQueueSendFromISR(queue, &data, NULL); -> Option B

4. Quick Check:

   Correct parameters and pointers used = xQueueSendFromISR(queue, &data, NULL); [OK]

Hint: Always pass data address and pxHigherPriorityTaskWoken pointer [OK]

Common Mistakes:

• Passing data instead of its address
• Passing queue address instead of handle
• Omitting the third parameter

3.

Given the following code snippet inside an ISR, what will be the value of result after execution?

BaseType_t xHigherPriorityTaskWoken = pdFALSE;
int data = 10;
BaseType_t result = xQueueSendFromISR(myQueue, &data, &xHigherPriorityTaskWoken);

Assume myQueue has space available.

medium

A. pdFAIL (0)

B. pdFALSE (0)

C. pdTRUE (1)

D. pdPASS (1)

Solution

1. Step 1: Understand return values of xQueueSendFromISR

   The function returns pdPASS (1) if the item was successfully sent to the queue, pdFAIL (0) otherwise.

2. Step 2: Analyze queue state

   Since myQueue has space, the send will succeed, so result will be pdPASS (1).

3. Final Answer:

   pdPASS (1) -> Option D

4. Quick Check:

   Queue has space, send success = pdPASS (1) [OK]

Hint: If queue has space, xQueueSendFromISR returns pdPASS (1) [OK]

Common Mistakes:

• Confusing pdPASS with pdTRUE
• Assuming it returns pdFALSE on success
• Ignoring queue capacity

4.

Identify the error in this ISR code snippet using xQueueSendFromISR():

void ISR_Handler(void) {
    int value = 5;
    BaseType_t xHigherPriorityTaskWoken;
    xQueueSendFromISR(myQueue, &value, &xHigherPriorityTaskWoken);
    if(xHigherPriorityTaskWoken) {
        portYIELD_FROM_ISR();
    }
}

medium

A. value should be a pointer, not an int

B. portYIELD_FROM_ISR() is called incorrectly

C. xHigherPriorityTaskWoken is not initialized before use

D. xQueueSendFromISR() cannot be called inside ISR

Solution

1. Step 1: Check variable initialization

   xHigherPriorityTaskWoken must be initialized to pdFALSE before calling xQueueSendFromISR() to avoid unpredictable behavior.

2. Step 2: Verify other parts

   Calling portYIELD_FROM_ISR() conditionally is correct; value is passed by address; calling xQueueSendFromISR() inside ISR is valid.

3. Final Answer:

   xHigherPriorityTaskWoken is not initialized before use -> Option C

4. Quick Check:

   Initialize xHigherPriorityTaskWoken = pdFALSE before use [OK]

Hint: Always init xHigherPriorityTaskWoken to pdFALSE before sending [OK]

Common Mistakes:

• Not initializing xHigherPriorityTaskWoken
• Misusing portYIELD_FROM_ISR
• Passing data incorrectly

5.

You want to send multiple sensor readings from an ISR to a task using xQueueSendFromISR(). Which approach correctly ensures the task runs immediately if it has higher priority?

void SensorISR(void) {
    static int sensorData = 0;
    BaseType_t xHigherPriorityTaskWoken = pdFALSE;
    sensorData++;
    xQueueSendFromISR(sensorQueue, &sensorData, &xHigherPriorityTaskWoken);
    // What should be done here?
}

hard

A. Call portYIELD_FROM_ISR(xHigherPriorityTaskWoken); after sending

B. Call vTaskDelay(1); inside the ISR

C. Call taskYIELD(); inside the ISR unconditionally

D. Do nothing; the task will run eventually

Solution

1. Step 1: Understand task wake mechanism

   After sending data from ISR, if a higher priority task was woken, you must request a context switch immediately.

2. Step 2: Use correct yield function

   portYIELD_FROM_ISR(xHigherPriorityTaskWoken); triggers a context switch only if needed, which is the correct approach.

3. Final Answer:

   Call portYIELD_FROM_ISR(xHigherPriorityTaskWoken); after sending -> Option A

4. Quick Check:

   Use portYIELD_FROM_ISR with xHigherPriorityTaskWoken to yield [OK]

Hint: Use portYIELD_FROM_ISR with flag to yield only if needed [OK]

Common Mistakes:

• Calling blocking functions like vTaskDelay in ISR
• Calling taskYIELD unconditionally inside ISR
• Ignoring portYIELD_FROM_ISR call