Producer-consumer pattern in FreeRTOS - Time & Space Complexity

Time Complexity: Producer-consumer pattern

O(n)

Understanding Time Complexity

We want to understand how the time cost changes when using the producer-consumer pattern in FreeRTOS.

Specifically, how the number of operations grows as more items are produced and consumed.

Scenario Under Consideration

Analyze the time complexity of the following FreeRTOS producer-consumer code snippet.

void producerTask(void *params) {
    for (;;) {
        int item = produceItem();
        xQueueSend(queue, &item, portMAX_DELAY);
    }
}

void consumerTask(void *params) {
    int item;
    for (;;) {
        xQueueReceive(queue, &item, portMAX_DELAY);
        consumeItem(item);
    }
}
    

This code shows two tasks: one produces items and sends them to a queue, the other receives and consumes them.

Identify Repeating Operations

Look at what repeats in the code.

• Primary operation: The producer repeatedly sends items to the queue, and the consumer repeatedly receives items from the queue.
• How many times: Each loop runs indefinitely, processing one item per iteration.

How Execution Grows With Input

As the number of items to produce and consume grows, the tasks run more iterations.

Input Size (n items)	Approx. Operations
10	About 10 sends and 10 receives
100	About 100 sends and 100 receives
1000	About 1000 sends and 1000 receives

Pattern observation: The total operations grow directly with the number of items; doubling items doubles operations.

Final Time Complexity

Time Complexity: O(n)

This means the time to process items grows in a straight line with the number of items produced and consumed.

Common Mistake

[X] Wrong: "The producer or consumer runs in constant time no matter how many items there are."

[OK] Correct: Each item requires a send or receive operation, so more items mean more work and more time.

Interview Connect

Understanding how tasks interact and how their work scales is a key skill in real-time systems programming.

Self-Check

"What if the queue size is limited and sometimes full? How would that affect the time complexity of the producer task?"

Practice

1.

In FreeRTOS, what is the main role of the queue in the producer-consumer pattern?

easy

A. To create new tasks dynamically

B. To handle interrupts directly

C. To manage memory allocation for tasks

D. To safely transfer data between producer and consumer tasks

Solution

1. Step 1: Understand the producer-consumer pattern

   The pattern involves one task producing data and another consuming it, requiring safe data sharing.

2. Step 2: Identify the role of the queue in FreeRTOS

   The queue acts as a safe buffer that holds data items, ensuring tasks do not access the same data simultaneously.

3. Final Answer:

   To safely transfer data between producer and consumer tasks -> Option D

4. Quick Check:

   Queue = Safe data transfer [OK]

Hint: Queues safely pass data between tasks without conflicts [OK]

Common Mistakes:

• Thinking queues create tasks
• Confusing queues with memory management
• Assuming queues handle interrupts

2.

Which of the following is the correct FreeRTOS API call for a producer task to send data to a queue?

void producerTask(void *params) {
    int data = 10;
    // Send data to queue here
}

easy

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

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

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

D. vTaskDelay(queueHandle);

Solution

1. Step 1: Identify the correct API for sending data to a queue

   FreeRTOS uses xQueueSend() to send data from a producer to a queue.

2. Step 2: Check other options for correctness

   xQueueReceive() is for receiving data, xTaskCreate() creates tasks, and vTaskDelay() delays tasks, so they are incorrect here.

3. Final Answer:

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

4. Quick Check:

   Send data = xQueueSend [OK]

Hint: Use xQueueSend to put data into the queue [OK]

Common Mistakes:

• Using xQueueReceive to send data
• Confusing task creation with queue operations
• Using delay functions instead of queue functions

3.

Consider this FreeRTOS code snippet where a producer sends integers 1 to 3 to a queue and a consumer receives them:

int data;
for (int i = 1; i <= 3; i++) {
    xQueueSend(queueHandle, &i, 0);
}
for (int j = 0; j < 3; j++) {
    xQueueReceive(queueHandle, &data, 0);
    printf("%d ", data);
}

What will be the output?

medium

A. 1 2 3

B. 3 2 1

C. 0 0 0

D. Compilation error

Solution

1. Step 1: Analyze the producer loop

   The producer sends values 1, 2, and 3 in order to the queue without delay.

2. Step 2: Analyze the consumer loop

   The consumer receives three values from the queue and prints them in the order received.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Queue preserves order = 1 2 3 [OK]

Hint: Queue keeps order; output matches sent sequence [OK]

Common Mistakes:

• Assuming queue reverses order
• Expecting zeros due to uninitialized data
• Thinking code won't compile

4.

Identify the bug in this FreeRTOS consumer task code that causes it to never receive data:

void consumerTask(void *params) {
    int receivedData;
    while(1) {
        if(xQueueReceive(queueHandle, &receivedData, 0) == pdFALSE) {
            // No data received
            continue;
        }
        processData(receivedData);
    }
}

medium

A. The loop should use vTaskDelay instead of continue

B. The receive timeout is zero, causing missed data

C. The processData function is missing

D. The queue handle is not initialized

Solution

1. Step 1: Understand xQueueReceive timeout parameter

   A zero timeout means the call returns immediately if no data is available, possibly missing data if producer is slower.

2. Step 2: Identify why data is never received

   Because the consumer never waits, it may loop too fast and miss data arriving slightly later.

3. Final Answer:

   The receive timeout is zero, causing missed data -> Option B

4. Quick Check:

   Timeout 0 means no wait = missed data [OK]

Hint: Use non-zero timeout to wait for data [OK]

Common Mistakes:

• Ignoring timeout effect on receive
• Assuming missing queue handle causes this
• Thinking processData absence causes no receive

5.

You want to implement a producer-consumer system where the producer sends sensor readings every 100ms, and the consumer processes them. Which FreeRTOS queue configuration and task design is best to avoid data loss and ensure timely processing?

hard

A. Use a queue with length 5 and consumer uses zero timeout on receive

B. Use a queue with length 1 and zero receive timeout in consumer

C. Use a queue with length 10 and consumer waits with portMAX_DELAY on receive

D. Use no queue and share a global variable with no synchronization

Solution

1. Step 1: Consider queue length for buffering

   A queue length of 10 allows buffering multiple sensor readings if consumer is busy, preventing data loss.

2. Step 2: Consider consumer receive timeout

   Using portMAX_DELAY makes consumer wait indefinitely for data, ensuring it processes every reading.

3. Final Answer:

   Use a queue with length 10 and consumer waits with portMAX_DELAY on receive -> Option C

4. Quick Check:

   Buffer + wait = no data loss [OK]

Hint: Use bigger queue and wait on receive to avoid loss [OK]

Common Mistakes:

• Using too small queue causing data overwrite
• Using zero timeout causing missed data
• Sharing data without synchronization