Waiting for event bits (AND/OR) in FreeRTOS - Time & Space Complexity

Time Complexity: Waiting for event bits (AND/OR)

O(n)

Understanding Time Complexity

When a FreeRTOS task waits for event bits, it pauses until certain conditions are met.

We want to understand how the waiting time grows as the number of event bits or tasks increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Wait for event bits with AND or OR condition
EventBits_t bits = xEventGroupWaitBits(
    xEventGroup,          // Event group handle
    BIT_0 | BIT_1,        // Bits to wait for
    pdTRUE,               // Clear bits on exit
    pdFALSE,              // Wait for any bit (OR)
    portMAX_DELAY         // Wait forever
);
    

This code waits for either BIT_0 or BIT_1 to be set in the event group before continuing.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking event bits in the event group.
• How many times: The check happens each time an event bit changes or a task is unblocked.

How Execution Grows With Input

As the number of event bits or tasks waiting increases, the system checks more bits or wakes more tasks.

Input Size (n)	Approx. Operations
10 event bits/tasks	10 checks or wake-ups
100 event bits/tasks	100 checks or wake-ups
1000 event bits/tasks	1000 checks or wake-ups

Pattern observation: The work grows roughly in direct proportion to the number of bits or tasks involved.

Final Time Complexity

Time Complexity: O(n)

This means the time to check or wake tasks grows linearly as more event bits or tasks are involved.

Common Mistake

[X] Wrong: "Waiting for event bits is instant and does not depend on the number of bits or tasks."

[OK] Correct: The system must check each relevant bit and possibly wake tasks, so more bits or tasks mean more work.

Interview Connect

Understanding how waiting on event bits scales helps you design responsive and efficient real-time systems.

Self-Check

"What if we changed the wait condition from OR to AND? How would the time complexity change?"

Practice

1. What does waiting for event bits in FreeRTOS allow a task to do?

easy

A. Pause execution until specific event bits are set

B. Run continuously without interruption

C. Automatically clear all event bits on start

D. Create new event bits dynamically

Solution

1. Step 1: Understand event bits purpose

   Event bits are signals that tasks can wait for to synchronize actions.

2. Step 2: Identify what waiting means

   Waiting means the task pauses until the required bits are set.

3. Final Answer:

   Pause execution until specific event bits are set -> Option A

4. Quick Check:

   Waiting for event bits = pause task until bits set [OK]

Hint: Waiting means pausing until bits signal event [OK]

Common Mistakes:

• Thinking waiting means running continuously
• Confusing event bits with task creation
• Assuming bits clear automatically on start

2. Which of the following is the correct syntax to wait for event bits using AND mode in FreeRTOS?

easy

A. xEventGroupClearBits(eventGroup, bitsToWaitFor);

B. xEventGroupWaitBits(eventGroup, bitsToWaitFor, clearOnExit, pdFALSE, timeout);

C. xEventGroupWaitBits(eventGroup, bitsToWaitFor, clearOnExit, pdTRUE, timeout);

D. xEventGroupSetBits(eventGroup, bitsToWaitFor);

Solution

1. Step 1: Identify the AND mode parameter

   The fourth parameter is pdTRUE to wait for all bits (AND mode).

2. Step 2: Confirm function usage

   xEventGroupWaitBits waits for bits with parameters: event group, bits, clear flag, wait mode, timeout.

3. Final Answer:

   xEventGroupWaitBits(eventGroup, bitsToWaitFor, clearOnExit, pdTRUE, timeout); -> Option C

4. Quick Check:

   pdTRUE means AND mode in wait bits [OK]

Hint: pdTRUE means wait for all bits (AND) [OK]

Common Mistakes:

• Using pdFALSE for AND mode
• Confusing SetBits with WaitBits
• Mixing up clearOnExit parameter

3. Given the code snippet:

EventBits_t bits = xEventGroupWaitBits(eventGroup, BIT_1 | BIT_2, pdTRUE, pdFALSE, 1000);

What does bits contain if only BIT_1 is set in the event group before the call?

medium

A. Only BIT_1 set in bits

B. Both BIT_1 and BIT_2 set in bits

C. Zero (no bits set)

D. Function blocks indefinitely

Solution

1. Step 1: Understand wait mode pdFALSE

   pdFALSE means OR mode: wait for any bit set.

2. Step 2: Check which bits are set before call

   Only BIT_1 is set, but the third parameter is pdTRUE (clearOnExit), and the fourth parameter is pdFALSE (waitForAll = false), so the function waits for any bit set.

3. Step 3: Analyze the code

   However, the third parameter is pdTRUE (clearOnExit), so bits are cleared on exit. But since waitForAll is pdFALSE, the function returns when any bit is set.

4. Step 4: But the question is what bits contains if only BIT_1 is set before call

   Since waitForAll is false, the function returns immediately with bits containing BIT_1 set.

5. Final Answer:

   Only BIT_1 set in bits -> Option A

6. Quick Check:

   OR mode returns bits set among requested [OK]

Hint: pdFALSE means OR mode, returns any set bits [OK]

Common Mistakes:

• Assuming both bits must be set for return
• Thinking function blocks if not all bits set
• Confusing pdTRUE and pdFALSE meanings

4. Identify the error in this code snippet:

EventBits_t bits = xEventGroupWaitBits(eventGroup, BIT_1 | BIT_2, pdTRUE, pdTRUE, 500);

What is wrong?

medium

A. pdTRUE for waitForAll means wait for all bits, but clearOnExit should be false to avoid clearing

B. pdTRUE for clearOnExit clears bits on exit, which is valid; no error

C. Using pdTRUE for both clearOnExit and waitForAll bits is correct

D. pdTRUE for waitForAll is invalid; must be pdFALSE

Solution

1. Step 1: Understand clearOnExit parameter

   pdTRUE means bits are cleared when function returns.

2. Step 2: Understand waitForAll parameter

   pdTRUE means wait for all bits (AND mode), which is valid.

3. Final Answer:

   pdTRUE for clearOnExit clears bits on exit, which is valid; no error -> Option B

4. Quick Check:

   clearOnExit pdTRUE is allowed and common [OK]

Hint: clearOnExit pdTRUE clears bits on return, allowed [OK]

Common Mistakes:

• Thinking clearOnExit pdTRUE is always wrong
• Confusing waitForAll with clearOnExit
• Assuming pdTRUE for waitForAll is invalid

5. You want a task to wait until both BIT_1 and BIT_2 are set, then clear those bits automatically on exit. Which call achieves this correctly?

hard

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

B. xEventGroupWaitBits(eventGroup, BIT_1 | BIT_2, pdFALSE, pdFALSE, portMAX_DELAY);

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

D. xEventGroupWaitBits(eventGroup, BIT_1 | BIT_2, pdTRUE, pdTRUE, portMAX_DELAY);

Solution

1. Step 1: Identify wait for all bits

   Fourth parameter pdTRUE means wait for all bits (AND mode).

2. Step 2: Identify clear bits on exit

   Third parameter pdTRUE means clear bits on exit.

3. Step 3: Match parameters to options

   xEventGroupWaitBits(eventGroup, BIT_1 | BIT_2, pdTRUE, pdTRUE, portMAX_DELAY); uses clearOnExit = pdTRUE and waitForAll = pdTRUE, correct for requirement.

4. Final Answer:

   xEventGroupWaitBits(eventGroup, BIT_1 | BIT_2, pdTRUE, pdTRUE, portMAX_DELAY); -> Option D

5. Quick Check:

   Clear bits and wait all bits = clearOnExit pdTRUE, waitForAll pdTRUE [OK]

Hint: clearOnExit and waitForAll both pdTRUE for AND + clear [OK]

Common Mistakes:

• Mixing up clearOnExit and waitForAll parameters
• Using pdFALSE for waitForAll when AND needed
• Not setting timeout to wait indefinitely