Event group for task synchronization in FreeRTOS - Time & Space Complexity

Time Complexity: Event group for task synchronization

O(n)

Understanding Time Complexity

When tasks wait for events using event groups, the time to check and set events matters.

We want to know how the time to synchronize tasks grows as the number of events changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

EventBits_t uxBits;

// Wait for bits 0x01 or 0x02 to be set
uxBits = xEventGroupWaitBits(
    xEventGroup,          // The event group handle
    0x03,                 // Bits to wait for
    pdTRUE,               // Clear bits on exit
    pdFALSE,              // Wait for any bit
    portMAX_DELAY);       // Wait forever

if((uxBits & 0x01) != 0) {
    // Bit 0x01 was set
}
if((uxBits & 0x02) != 0) {
    // Bit 0x02 was set
}
    

This code waits for one or more event bits to be set, then checks which bits triggered the wait.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking event bits in the event group variable.
• How many times: The check happens once per event bit mask, typically a fixed small number.

How Execution Grows With Input

The time to check event bits grows with the number of bits you wait for.

Input Size (number of bits)	Approx. Operations
2	2 bit checks
8	8 bit checks
32	32 bit checks

Pattern observation: The number of operations grows linearly with the number of bits checked.

Final Time Complexity

Time Complexity: O(n)

This means the time to check event bits grows in direct proportion to how many bits you wait for.

Common Mistake

[X] Wrong: "Waiting for more event bits does not affect the time because it's just one variable."

[OK] Correct: Each bit must be checked individually, so more bits mean more checks and more time.

Interview Connect

Understanding how event groups scale helps you design responsive multitasking systems and shows you can reason about synchronization costs.

Self-Check

"What if the event group used a more complex data structure to track bits? How would that change the time complexity?"

Practice

1. What is the primary purpose of an event group in FreeRTOS for task synchronization?

easy

A. To allocate memory dynamically for tasks

B. To allow tasks to wait for multiple events using bits

C. To create queues for message passing

D. To manage task priorities automatically

Solution

1. Step 1: Understand event groups in FreeRTOS

   Event groups use bits to represent events that tasks can wait for or signal.

2. Step 2: Identify the main use of event groups

   They help tasks synchronize by waiting on or setting bits representing events.

3. Final Answer:

   To allow tasks to wait for multiple events using bits -> Option B

4. Quick Check:

   Event groups = wait for multiple events [OK]

Hint: Event groups use bits to sync tasks, not memory or priorities [OK]

Common Mistakes:

• Confusing event groups with queues
• Thinking event groups manage memory
• Assuming event groups change task priorities

2. Which of the following is the correct function to wait for bits in an event group in FreeRTOS?

easy

A. xEventGroupClearBits()

B. xEventGroupSetBits()

C. xEventGroupWaitBits()

D. xEventGroupCreate()

Solution

1. Step 1: Recall FreeRTOS event group functions

   xEventGroupWaitBits() is used to wait for specific bits to be set.

2. Step 2: Differentiate from other functions

   xEventGroupSetBits() sets bits, ClearBits clears bits, Create creates the group.

3. Final Answer:

   xEventGroupWaitBits() -> Option C

4. Quick Check:

   Wait for bits = xEventGroupWaitBits() [OK]

Hint: Wait uses xEventGroupWaitBits(), set uses xEventGroupSetBits() [OK]

Common Mistakes:

• Using xEventGroupSetBits() to wait
• Confusing create with wait functions
• Mixing clear bits with wait bits

3. Given the following code snippet, what will be the value of bits after xEventGroupWaitBits() returns?

EventBits_t bits;
bits = xEventGroupWaitBits(eventGroup, BIT_0 | BIT_1, pdTRUE, pdFALSE, portMAX_DELAY);

Assume BIT_0 and BIT_1 are both set in eventGroup before the call.

medium

A. Only BIT_0 set

B. Only BIT_1 set

C. No bits set

D. Both BIT_0 and BIT_1 set

Solution

1. Step 1: Understand xEventGroupWaitBits parameters

   The function waits for BIT_0 or BIT_1 to be set, clears bits on exit (pdTRUE), and does not wait for all bits (pdFALSE).

2. Step 2: Analyze the bits set before call

   Both BIT_0 and BIT_1 are set, so the function returns with both bits set in the return value.

3. Final Answer:

   Both BIT_0 and BIT_1 set -> Option D

4. Quick Check:

   WaitBits returns bits set before clearing [OK]

Hint: WaitBits returns bits set before clearing them [OK]

Common Mistakes:

• Assuming only one bit is returned
• Ignoring bits cleared on exit
• Confusing wait for all bits with wait for any

4. Identify the error in the following FreeRTOS event group usage:

EventGroupHandle_t eventGroup = xEventGroupCreate();

void Task1(void *pvParameters) {
    xEventGroupWaitBits(eventGroup, BIT_0, pdFALSE, pdTRUE, portMAX_DELAY);
    // Task code
}

void Task2(void *pvParameters) {
    xEventGroupSetBits(eventGroup, BIT_0);
}

medium

A. Not checking if eventGroup creation succeeded

B. Using portMAX_DELAY as wait time

C. Using pdFALSE for clearOnExit in xEventGroupWaitBits

D. Setting bits before event group creation

Solution

1. Step 1: Check event group creation

   xEventGroupCreate() can return NULL if creation fails; code does not check this.

2. Step 2: Verify other parameters

   Using pdFALSE for clearOnExit is valid; portMAX_DELAY is valid; bits are set after creation.

3. Final Answer:

   Not checking if eventGroup creation succeeded -> Option A

4. Quick Check:

   Always check event group creation success [OK]

Hint: Always verify event group creation returned non-NULL [OK]

Common Mistakes:

• Ignoring NULL return from xEventGroupCreate
• Misusing clearOnExit parameter
• Setting bits before creating event group

5. You want two tasks to synchronize so that Task A waits until Task B signals both BIT_0 and BIT_1. Which xEventGroupWaitBits() call correctly waits for both bits before continuing?

hard

A. xEventGroupWaitBits(eventGroup, BIT_0 | BIT_1, pdTRUE, pdTRUE, portMAX_DELAY);

B. xEventGroupWaitBits(eventGroup, BIT_0 & BIT_1, pdTRUE, pdTRUE, portMAX_DELAY);

C. xEventGroupWaitBits(eventGroup, BIT_0 | BIT_1, pdTRUE, pdFALSE, portMAX_DELAY);

D. xEventGroupWaitBits(eventGroup, BIT_0 & BIT_1, pdFALSE, pdFALSE, portMAX_DELAY);

Solution

1. Step 1: Understand wait for all bits parameter

   The fourth parameter (xWaitForAllBits) must be pdTRUE to wait for both bits together.

2. Step 2: Check bit mask and parameters

   Use BIT_0 | BIT_1 to specify both bits; pdTRUE for clearOnExit clears bits after wait.

3. Final Answer:

   xEventGroupWaitBits(eventGroup, BIT_0 | BIT_1, pdTRUE, pdTRUE, portMAX_DELAY); -> Option A

4. Quick Check:

   Wait for all bits = xEventGroupWaitBits with xWaitForAllBits = pdTRUE [OK]

Hint: Set xWaitForAllBits to pdTRUE to wait for all bits [OK]

Common Mistakes:

• Using bitwise AND (&) instead of OR (|) for bit mask
• Setting xWaitForAllBits to pdFALSE when waiting for all bits
• Confusing clearOnExit with wait for all bits