xQueueSend() and xQueueReceive() in FreeRTOS - Time & Space Complexity

Time Complexity: xQueueSend() and xQueueReceive()

O(1)

Understanding Time Complexity

When working with FreeRTOS queues, it's important to know how the time to send or receive items grows as the queue size changes.

We want to understand how the cost of adding or removing items from a queue changes when the queue gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Create a queue to hold 10 integers
QueueHandle_t queue = xQueueCreate(10, sizeof(int));

int value = 42;

// Send an item to the queue
xQueueSend(queue, &value, portMAX_DELAY);

int receivedValue;

// Receive an item from the queue
xQueueReceive(queue, &receivedValue, portMAX_DELAY);
    

This code creates a queue, sends one integer to it, and then receives one integer from it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding or removing an item from the queue buffer.
• How many times: Each call to xQueueSend() or xQueueReceive() handles one item at a time.

How Execution Grows With Input

Each send or receive operation moves one item in or out of the queue without scanning the whole queue.

Queue Size (n)	Approx. Operations per Send/Receive
10	Constant steps to place or take one item
100	Same constant steps, no extra work
1000	Still constant steps, independent of size

Pattern observation: The time to send or receive does not grow with queue size; it stays about the same.

Final Time Complexity

Time Complexity: O(1)

This means sending or receiving one item takes the same amount of time no matter how big the queue is.

Common Mistake

[X] Wrong: "Sending or receiving items takes longer as the queue gets bigger because it has to check all items."

[OK] Correct: The queue uses a circular buffer and pointers, so it directly places or takes one item without scanning others.

Interview Connect

Understanding how queue operations scale helps you explain efficient communication between tasks in embedded systems, a key skill in real-time programming.

Self-Check

"What if the queue was implemented as a linked list instead of a circular buffer? How would the time complexity of sending and receiving change?"

Practice

1. What is the primary purpose of the xQueueSend() function in FreeRTOS?

easy

A. To remove an item from a queue

B. To add an item to a queue for other tasks to receive

C. To create a new queue

D. To delete an existing queue

Solution

1. Step 1: Understand the role of xQueueSend()

   xQueueSend() is used to place data into a queue so that other tasks can retrieve it later.

2. Step 2: Differentiate from other queue functions

   Functions like xQueueReceive() remove data, while xQueueCreate() and xQueueDelete() manage queue lifecycle, not data transfer.

3. Final Answer:

   To add an item to a queue for other tasks to receive -> Option B

4. Quick Check:

   xQueueSend() adds data [OK]

Hint: Remember: Send puts data in, Receive takes data out [OK]

Common Mistakes:

• Confusing sending with receiving
• Thinking it creates or deletes queues
• Ignoring the function's data transfer role

2. Which of the following is the correct syntax to send data to a queue using xQueueSend()?

easy

A. xQueueSend(queueHandle, data, 0);

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

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

D. xQueueSend(queueHandle, &data);

Solution

1. Step 1: Check parameter types for xQueueSend()

   The function expects the queue handle, a pointer to the data, and a timeout value.

2. Step 2: Match the correct syntax

   xQueueSend(queueHandle, &data, portMAX_DELAY); correctly passes the queue handle, address of data, and a timeout constant portMAX_DELAY.

3. Final Answer:

   xQueueSend(queueHandle, &data, portMAX_DELAY); -> Option C

4. Quick Check:

   Queue handle + &data + timeout = correct syntax [OK]

Hint: Always pass data by address and include timeout [OK]

Common Mistakes:

• Passing data by value instead of pointer
• Omitting the timeout parameter
• Passing queue handle by address

3. Consider the following code snippet:

int value = 10;
if (xQueueSend(queue, &value, 0) == pdPASS) {
    int receivedValue = 0;
    if (xQueueReceive(queue, &receivedValue, 0) == pdPASS) {
        printf("%d", receivedValue);
    }
}

What will be printed when this code runs?

medium

A. 10

B. 0

C. No output (queue empty)

D. Compilation error

Solution

1. Step 1: Analyze xQueueSend() call

   The value 10 is sent to the queue with zero wait time. If the queue is not full, it returns pdPASS.

2. Step 2: Analyze xQueueReceive() call

   The code tries to receive from the queue immediately. Since the value was just sent, it will receive 10 and print it.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Send 10, receive 10, print 10 [OK]

Hint: Send then receive immediately prints sent value [OK]

Common Mistakes:

• Assuming queue is empty at receive
• Confusing return values with data
• Ignoring zero timeout behavior

4. What is wrong with this code snippet?

int data = 5;
if (xQueueSend(queue, data, 10) != pdPASS) {
    // handle error
}

medium

A. Data should be passed by pointer, not by value

B. Timeout value 10 is invalid

C. Return value should not be compared to pdPASS

D. Queue handle is missing

Solution

1. Step 1: Check parameter types in xQueueSend()

   The second parameter must be a pointer to the data, but here data is passed by value.

2. Step 2: Identify the error cause

   Passing data by value causes a type mismatch and likely a compilation error or incorrect behavior.

3. Final Answer:

   Data should be passed by pointer, not by value -> Option A

4. Quick Check:

   Pass &data, not data [OK]

Hint: Always pass address of data to queue functions [OK]

Common Mistakes:

• Passing data directly instead of pointer
• Misunderstanding timeout parameter
• Ignoring return value check

5. You want to send multiple integers to a queue and then receive them in order. Which approach correctly uses xQueueSend() and xQueueReceive() to achieve this without losing data?

hard

A. Use xQueueReceive() to send data and xQueueSend() to receive data

B. Send all integers at once by passing an array pointer to xQueueSend(), then receive with one xQueueReceive()

C. Send integers without checking return values, then receive once expecting all data

D. Send each integer with xQueueSend() using a timeout, then receive each with xQueueReceive() using a timeout, checking return values each time

Solution

1. Step 1: Understand queue data handling

   Queues handle one item at a time, so each integer must be sent individually with xQueueSend().

2. Step 2: Properly receive data

   Each item must be received individually with xQueueReceive(), checking return values to avoid errors or data loss.

3. Step 3: Eliminate incorrect options

   Send all integers at once by passing an array pointer to xQueueSend(), then receive with one xQueueReceive() is wrong because queues do not send arrays as single items. Send integers without checking return values, then receive once expecting all data risks data loss by ignoring return values. Use xQueueReceive() to send data and xQueueSend() to receive data reverses function roles.

4. Final Answer:

   Send each integer with xQueueSend() using a timeout, then receive each with xQueueReceive() using a timeout, checking return values each time -> Option D

5. Quick Check:

   Send and receive items one by one, check returns [OK]

Hint: Send and receive items individually, always check returns [OK]

Common Mistakes:

• Trying to send multiple items at once
• Ignoring return values causing lost data
• Mixing up send and receive functions