Queue full and empty handling in FreeRTOS - Time & Space Complexity

Time Complexity: Queue full and empty handling

O(1)

Understanding Time Complexity

When working with queues in FreeRTOS, it's important to understand how the time to add or remove items changes as the queue size changes.

We want to know how the operations behave when the queue is full or empty.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Send an item to the queue
if(xQueueSend(queue, &item, 0) == pdPASS) {
    // Item added successfully
} else {
    // Queue full, item not added
}

// Receive an item from the queue
if(xQueueReceive(queue, &receivedItem, 0) == pdPASS) {
    // Item received successfully
} else {
    // Queue empty, no item to receive
}
    

This code tries to add or remove an item from a FreeRTOS queue, handling the cases when the queue is full or empty.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding or removing a single item from the queue buffer.
• How many times: Each call handles one item at a time, no loops inside the call for multiple items.

How Execution Grows With Input

Each send or receive operation works on one item regardless of queue size.

Input Size (queue length)	Approx. Operations per call
10	Constant steps to add or remove one item
100	Same constant steps, no increase
1000	Still constant steps, no increase

Pattern observation: The time to add or remove one item does not grow with queue size; it stays constant.

Final Time Complexity

Time Complexity: O(1)

This means adding or removing one item from the queue takes the same amount of time no matter how big the queue is.

Common Mistake

[X] Wrong: "Adding an item takes longer when the queue is bigger because it has more space to check."

[OK] Correct: The queue uses a circular buffer and pointers, so it directly places the item without scanning the whole queue.

Interview Connect

Understanding that queue operations are constant time helps you explain efficient task communication in embedded systems.

Self-Check

"What if we changed the queue to allow sending multiple items at once? How would the time complexity change?"

Practice

1. In FreeRTOS, what happens if you try to send an item to a queue that is already full without waiting?

easy

A. The send operation fails immediately and returns an error.

B. The queue automatically expands to fit the new item.

C. The oldest item in the queue is overwritten.

D. The task sending the item is suspended indefinitely.

Solution

1. Step 1: Understand queue full behavior

   When a queue is full, FreeRTOS does not allow new items to be added without waiting or handling the error.

2. Step 2: Check send operation without wait

   If the send function is called with zero wait time and the queue is full, it returns immediately with an error indicating failure.

3. Final Answer:

   The send operation fails immediately and returns an error. -> Option A

4. Quick Check:

   Queue full + no wait = send fails [OK]

Hint: Send with zero wait fails if queue is full [OK]

Common Mistakes:

• Assuming queue grows automatically
• Thinking oldest data is overwritten
• Believing task suspends indefinitely

2. Which of the following is the correct way to receive an item from a FreeRTOS queue with a block time of 10 ticks?

easy

A. xQueueReceive(queue, &item, 10);

B. xQueueReceive(queue, item, 10);

C. xQueueReceive(queue, &item, 0);

D. xQueueReceive(queue, &item, -1);

Solution

1. Step 1: Understand xQueueReceive parameters

   The function takes the queue handle, a pointer to the variable to store the item, and the block time in ticks.

2. Step 2: Identify correct syntax

   Passing &item as the second argument is correct to provide the address. Block time 10 means wait up to 10 ticks.

3. Final Answer:

   xQueueReceive(queue, &item, 10); -> Option A

4. Quick Check:

   Pointer + block time 10 = correct receive call [OK]

Hint: Use &item and positive ticks for blocking receive [OK]

Common Mistakes:

• Passing item instead of &item
• Using zero or negative block time incorrectly
• Confusing send and receive parameters

3. Consider the following code snippet:

QueueHandle_t queue = xQueueCreate(2, sizeof(int));
int val = 10;
xQueueSend(queue, &val, 0);
val = 20;
xQueueSend(queue, &val, 0);
val = 30;
BaseType_t result = xQueueSend(queue, &val, 0);

What is the value of result after the last send call?

medium

A. pdPASS (send succeeded)

B. errQUEUE_FULL (send failed due to full queue)

C. pdFAIL (generic failure)

D. Block indefinitely until space is available

Solution

1. Step 1: Analyze queue creation and sends

   The queue can hold 2 integers. Two sends with zero wait fill it completely.

2. Step 2: Evaluate last send with zero wait

   The third send tries to add an item when the queue is full and does not wait, so it fails returning errQUEUE_FULL.

3. Final Answer:

   errQUEUE_FULL (send failed due to full queue) -> Option B

4. Quick Check:

   Queue full + zero wait = send fails with errQUEUE_FULL [OK]

Hint: Queue size 2 + 3 sends with zero wait = last send fails [OK]

Common Mistakes:

• Assuming last send blocks
• Thinking last send overwrites data
• Confusing pdPASS and pdFAIL

4. Given this code snippet, why does xQueueReceive never return pdPASS?

QueueHandle_t queue = xQueueCreate(1, sizeof(int));
int data;

// Task A
xQueueReceive(queue, &data, 0);

// Task B
int val = 5;
xQueueSend(queue, &val, 0);

medium

A. xQueueSend is called with zero wait time, so it fails.

B. Queue size is too small to hold any data.

C. xQueueReceive is called with incorrect pointer.

D. Task A tries to receive before Task B sends, queue is empty, no wait time.

Solution

1. Step 1: Understand queue state at receive

   Task A calls receive immediately with zero wait, but queue is empty because Task B hasn't sent yet.

2. Step 2: Effect of zero wait on empty queue

   With zero wait, receive returns immediately with failure since no data is available yet.

3. Final Answer:

   Task A tries to receive before Task B sends, queue is empty, no wait time. -> Option D

4. Quick Check:

   Receive zero wait + empty queue = no pdPASS [OK]

Hint: Receive zero wait on empty queue always fails [OK]

Common Mistakes:

• Thinking queue size 1 means no data can be stored
• Assuming send fails with zero wait
• Confusing pointer usage in receive

5. You want to design a FreeRTOS task that sends sensor data to a queue but must never block if the queue is full. Which approach correctly handles the queue full condition?

hard

A. Increase the queue size dynamically when full.

B. Use xQueueSend with portMAX_DELAY to wait indefinitely until space is available.

C. Use xQueueSend with zero block time and check the return value to discard data if full.

D. Use xQueueOverwrite to replace the oldest data in the queue automatically.

Solution

1. Step 1: Understand non-blocking send requirement

   The task must never block, so waiting indefinitely or for a long time is not allowed.

2. Step 2: Choose correct send method and handling

   Using xQueueSend with zero block time returns immediately. Checking the return value lets the task discard data if the queue is full.

3. Step 3: Evaluate other options

   Use xQueueSend with portMAX_DELAY to wait indefinitely until space is available. blocks indefinitely, violating requirement. Use xQueueOverwrite to replace the oldest data in the queue automatically. overwrites data but may lose important info. Increase the queue size dynamically when full. is not supported by FreeRTOS.

4. Final Answer:

   Use xQueueSend with zero block time and check the return value to discard data if full. -> Option C

5. Quick Check:

   Non-blocking send + check return = safe discard [OK]

Hint: Send zero wait + check return to avoid blocking [OK]

Common Mistakes:

• Using blocking send when non-blocking needed
• Assuming queue size can grow dynamically
• Ignoring return value of send