Queue set for monitoring multiple queues in FreeRTOS - Time & Space Complexity

Time Complexity: Queue set for monitoring multiple queues

O(1)

Understanding Time Complexity

When using a queue set in FreeRTOS, we want to know how checking multiple queues affects the time it takes to find data.

We ask: How does the time to check queues grow as we add more queues to the set?

Scenario Under Consideration

Analyze the time complexity of the following FreeRTOS code snippet.

QueueSetHandle_t xQueueSet = xQueueCreateSet( 3 * queue_LENGTH );
xQueueAddToSet( xQueue1, xQueueSet );
xQueueAddToSet( xQueue2, xQueueSet );
xQueueAddToSet( xQueue3, xQueueSet );

QueueSetMemberHandle_t xActivatedMember = xQueueSelectFromSet( xQueueSet, portMAX_DELAY );

if( xActivatedMember == xQueue1 ) {
    // Process xQueue1
} else if( xActivatedMember == xQueue2 ) {
    // Process xQueue2
} else if( xActivatedMember == xQueue3 ) {
    // Process xQueue3
}
    

This code creates a queue set from three queues and waits to see which queue has data ready to process.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Receive from the queue set's internal event queue (no loop over queues).
• How many times: Constant time (O(1)) per call to xQueueSelectFromSet.

How Execution Grows With Input

As the number of queues in the set grows, the time to check which queue is ready remains constant (O(1)).

Input Size (n)	Approx. Operations
3	1 operation
10	1 operation
100	1 operation

Pattern observation: The number of operations stays constant regardless of the number of queues.

Final Time Complexity

Time Complexity: O(1)

This means the time to find which queue has data is constant, independent of the number of queues in the set.

Common Mistake

[X] Wrong: "Checking multiple queues in a queue set requires scanning all queues linearly."

[OK] Correct: FreeRTOS queue sets use an internal event queue that stores handles of ready queues, enabling O(1) selection without scanning.

Interview Connect

Understanding how queue sets scale helps you design responsive systems that handle multiple data sources efficiently.

Self-Check

"What if the queue set used a priority system to check queues? How would that affect the time complexity?"

Practice

1. What is the main purpose of a Queue Set in FreeRTOS?

easy

A. To monitor multiple queues with a single wait call

B. To increase the size of a single queue

C. To create a queue that stores different data types

D. To prioritize tasks based on queue length

Solution

1. Step 1: Recall the purpose of a Queue Set

   A Queue Set allows monitoring multiple queues or semaphores with one blocking call.

2. Step 2: Match options to the Queue Set purpose

   Only "To monitor multiple queues with a single wait call" correctly describes this purpose; others describe unrelated features.

3. Final Answer:

   To monitor multiple queues with a single wait call -> Option A

4. Quick Check:

   Queue Set = single wait for many queues [OK]

Hint: Queue Set = watch many queues with one wait [OK]

Common Mistakes:

• Thinking Queue Set increases queue size
• Confusing Queue Set with task priority
• Believing Queue Set stores mixed data types

2. Which of the following is the correct way to create a queue set for monitoring two queues in FreeRTOS?

easy

A. xQueueSetCreate( queue1Length + queue2Length, itemSize )

B. xQueueSetCreate( queue1Length * queue2Length, itemSize )

C. xQueueSetCreate( queue1Length + queue2Length, sizeof(void*) )

D. xQueueSetCreate( queue1Length + queue2Length, 0 )

Solution

1. Step 1: Review parameters of xQueueSetCreate

   The first parameter is the total number of items the set can hold, usually sum of queue lengths. The second is the size of a pointer (sizeof(void*)) because queue sets hold references to queues.

2. Step 2: Evaluate each option

   xQueueSetCreate( queue1Length + queue2Length, sizeof(void*) ) correctly uses sum of lengths and pointer size. Others are incorrect: itemSize, multiplication, or zero size.

3. Final Answer:

   xQueueSetCreate( queue1Length + queue2Length, sizeof(void*) ) -> Option C

4. Quick Check:

   Queue set size = sum lengths, item size = pointer size [OK]

Hint: Queue set size = sum of queues, item size = pointer size [OK]

Common Mistakes:

• Using item size instead of pointer size
• Multiplying queue lengths instead of adding
• Setting item size to zero

3. Given the code snippet:

QueueHandle_t queue1 = xQueueCreate(5, sizeof(int));
QueueHandle_t queue2 = xQueueCreate(3, sizeof(int));
QueueSetHandle_t queueSet = xQueueSetCreate(8, sizeof(void*));
xQueueAddToSet(queue1, queueSet);
xQueueAddToSet(queue2, queueSet);
QueueSetMemberHandle_t activatedQueue = xQueueSelectFromSet(queueSet, portMAX_DELAY);

What does activatedQueue represent after xQueueSelectFromSet returns?

medium

A. A pointer to the data item received

B. A handle to the queue that has data available

C. The total number of items in all queues

D. NULL if no queues have data

Solution

1. Step 1: Analyze xQueueSelectFromSet behavior

   This function blocks until any queue in the set has data, then returns a handle to that queue.

2. Step 2: Determine what activatedQueue holds

   It holds the queue handle that has data ready to be read, not the data itself or count.

3. Final Answer:

   A handle to the queue that has data available -> Option B

4. Quick Check:

   xQueueSelectFromSet returns queue handle with data [OK]

Hint: xQueueSelectFromSet returns queue handle with data ready [OK]

Common Mistakes:

• Thinking it returns data pointer
• Confusing with total item count
• Expecting NULL when data is available

4. What is wrong with this code snippet for using a queue set?

QueueSetHandle_t set = xQueueSetCreate(5, sizeof(void*));
QueueHandle_t q1 = xQueueCreate(3, sizeof(int));
xQueueAddToSet(q1, set);
QueueSetMemberHandle_t member = xQueueSelectFromSet(set, portMAX_DELAY);
int value;
xQueueReceive(set, &value, 0);

medium

A. xQueueCreate uses wrong item size

B. Queue set size is too small for the queue length

C. xQueueAddToSet is missing for q1

D. xQueueReceive is called with a queue set handle instead of a queue handle

Solution

1. Step 1: Examine the xQueueReceive call

   The code calls xQueueReceive(set, &value, 0), passing the queue set handle 'set'.

2. Step 2: Recall the return value of xQueueSelectFromSet

   It returns 'member', a handle to the queue with data available.

3. Step 3: Identify the mistake

   xQueueReceive must use the queue handle 'member', not the queue set handle 'set'.

4. Final Answer:

   xQueueReceive is called with a queue set handle instead of a queue handle -> Option D

5. Quick Check:

   xQueueReceive uses queue handle from set, not set itself [OK]

Hint: xQueueSelectFromSet returns queue handle for xQueueReceive [OK]

Common Mistakes:

• Confusing queue set handle with queue handle
• Assuming queue set size must match queue length
• Missing xQueueAddToSet call

5. You want to monitor three queues with lengths 4, 5, and 6 using a queue set. Which of the following is the best practice to create and use the queue set correctly?

hard

A. Create queue set with size 15, add all queues, then call xQueueSelectFromSet to wait

B. Create queue set with size 6, add all queues, then call xQueueSelectFromSet to wait

C. Create queue set with size 4, add only the largest queue, then call xQueueSelectFromSet

D. Create queue set with size 15, add queues after calling xQueueSelectFromSet

Solution

1. Step 1: Calculate total queue set size

   The queue set size must be at least the sum of all queue lengths: 4 + 5 + 6 = 15.

2. Step 2: Add all queues before waiting

   All queues must be added to the set before calling xQueueSelectFromSet to monitor them properly.

3. Step 3: Evaluate options

   Create queue set with size 15, add all queues, then call xQueueSelectFromSet to wait follows best practice: correct size, all queues added, then wait. Others fail on size, timing, or completeness.

4. Final Answer:

   Create queue set with size 15, add all queues, then call xQueueSelectFromSet to wait -> Option A

5. Quick Check:

   Queue set size = sum lengths, add all queues first [OK]

Hint: Queue set size = sum of queues; add all before waiting [OK]

Common Mistakes:

• Using queue set size smaller than total queue lengths
• Adding queues after waiting
• Adding only some queues to the set