xTaskNotifyGive() as lightweight semaphore in FreeRTOS - Time & Space Complexity

Time Complexity: xTaskNotifyGive() as lightweight semaphore

O(n)

Understanding Time Complexity

We want to understand how the time cost changes when using xTaskNotifyGive() as a lightweight semaphore in FreeRTOS.

Specifically, how does the number of operations grow when tasks notify each other?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void Task1(void *pvParameters) {
    for (;;) {
        // Do some work
        xTaskNotifyGive(Task2Handle);  // Notify Task2
        vTaskDelay(pdMS_TO_TICKS(100));
    }
}

void Task2(void *pvParameters) {
    for (;;) {
        ulTaskNotifyTake(pdTRUE, portMAX_DELAY);  // Wait for notification
        // Process after notification
    }
}
    

This code shows one task notifying another using xTaskNotifyGive() as a lightweight semaphore to signal events.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The notification send and receive calls inside infinite loops.
• How many times: Each task loops forever, sending or waiting for notifications repeatedly.

How Execution Grows With Input

Each notification operation happens once per loop cycle, independent of any input size.

Input Size (n)	Approx. Operations
10	10 notifications sent and received
100	100 notifications sent and received
1000	1000 notifications sent and received

Pattern observation: The number of operations grows linearly with the number of notification events, but each event is a simple, constant-time operation.

Final Time Complexity

Time Complexity: O(n)

This means the total time grows linearly with the number of notifications, but each notification send or receive takes a constant amount of time.

Common Mistake

[X] Wrong: "Using xTaskNotifyGive() causes time to grow with the number of notifications queued."

[OK] Correct: Notifications do not queue up like messages; each call is a simple flag set or clear, so the time per call stays constant.

Interview Connect

Understanding how lightweight synchronization like xTaskNotifyGive() works helps you write efficient multitasking code and shows you know how to reason about task communication costs.

Self-Check

"What if we replaced xTaskNotifyGive() with a queue send operation? How would the time complexity change?"

Practice

1. What is the primary purpose of xTaskNotifyGive() in FreeRTOS?

easy

A. To send a simple signal from one task to another as a lightweight semaphore

B. To create a new task in the system

C. To delete a task permanently

D. To allocate memory dynamically

Solution

1. Step 1: Understand the function role

   xTaskNotifyGive() is designed to send a notification signal from one task to another.

2. Step 2: Compare with other options

   Creating or deleting tasks and memory allocation are unrelated to xTaskNotifyGive().

3. Final Answer:

   To send a simple signal from one task to another as a lightweight semaphore -> Option A

4. Quick Check:

   Signal sending = To send a simple signal from one task to another as a lightweight semaphore [OK]

Hint: Remember: xTaskNotifyGive() signals tasks like a lightweight semaphore [OK]

Common Mistakes:

• Confusing it with task creation or deletion functions
• Thinking it manages memory
• Assuming it blocks tasks directly

2. Which of the following is the correct syntax to send a notification using xTaskNotifyGive() to a task handle named xTaskHandle?

easy

A. xTaskNotifyGive(xTaskHandle, 1);

B. xTaskNotifyGive(&xTaskHandle);

C. xTaskNotifyGive(xTaskHandle);

D. xTaskNotifyGive();

Solution

1. Step 1: Recall function signature

   xTaskNotifyGive() takes a task handle as a parameter, not a pointer or extra arguments.

2. Step 2: Check each option

   xTaskNotifyGive(xTaskHandle); correctly passes the task handle. xTaskNotifyGive(&xTaskHandle); passes address (wrong), C adds an extra argument (wrong), D has no argument (wrong).

3. Final Answer:

   xTaskNotifyGive(xTaskHandle); -> Option C

4. Quick Check:

   Correct syntax = xTaskNotifyGive(xTaskHandle); [OK]

Hint: Pass the task handle directly without extra arguments [OK]

Common Mistakes:

• Passing pointer to task handle instead of handle itself
• Adding extra parameters
• Calling without any argument

3. Consider the following code snippet:

void Task1(void *pvParameters) {
    // Wait for notification
    ulTaskNotifyTake(pdTRUE, portMAX_DELAY);
    // Continue after notification
    printf("Task1 resumed\n");
}

void Task2(void *pvParameters) {
    // Notify Task1
    xTaskNotifyGive(Task1Handle);
}

What will be printed when Task2 calls xTaskNotifyGive()?

medium

A. Task2 resumes instead of Task1

B. Task1 resumed

C. Syntax error at compile time

D. No output, Task1 blocks forever

Solution

1. Step 1: Understand notification flow

   Task1 waits for a notification with ulTaskNotifyTake(). When Task2 calls xTaskNotifyGive(), it sends the notification.

2. Step 2: Effect of notification

   The notification unblocks Task1, so it prints "Task1 resumed".

3. Final Answer:

   Task1 resumed -> Option B

4. Quick Check:

   Notification received = Task1 prints [OK]

Hint: xTaskNotifyGive() wakes waiting task to continue [OK]

Common Mistakes:

• Assuming Task1 never resumes
• Confusing which task prints output
• Thinking code causes compile error

4. Identify the error in this code snippet using xTaskNotifyGive():

void TaskA(void *pvParameters) {
    ulTaskNotifyTake(pdFALSE, portMAX_DELAY);
    printf("TaskA running\n");
}

void TaskB(void *pvParameters) {
    xTaskNotifyGive(&TaskAHandle);
}

medium

A. Passing address of task handle instead of task handle to xTaskNotifyGive()

B. Using pdFALSE in ulTaskNotifyTake() causes immediate return

C. Missing delay in TaskB before notify

D. printf statement is incorrect syntax

Solution

1. Step 1: Check parameter passed to xTaskNotifyGive()

   The function expects a task handle, but &TaskAHandle passes its address, which is incorrect.

2. Step 2: Validate other parts

   Using pdFALSE is valid to clear notification count, no syntax error in printf, and delay is optional.

3. Final Answer:

   Passing address of task handle instead of task handle to xTaskNotifyGive() -> Option A

4. Quick Check:

   Correct parameter type needed = Passing address of task handle instead of task handle to xTaskNotifyGive() [OK]

Hint: Pass task handle directly, not its address [OK]

Common Mistakes:

• Passing pointer to handle instead of handle
• Misunderstanding pdFALSE effect
• Assuming printf syntax error

5. You want to use xTaskNotifyGive() as a lightweight semaphore to synchronize two tasks: Producer and Consumer. The Consumer waits for the notification before processing data. Which sequence correctly implements this synchronization?

hard

A. Producer calls ulTaskNotifyTake(pdTRUE, portMAX_DELAY);, Consumer calls xTaskNotifyGive(ProducerHandle);

B. Consumer calls xTaskNotifyGive() and Producer calls ulTaskNotifyTake()

C. Both tasks call xTaskNotifyGive() simultaneously without waiting

D. Consumer calls ulTaskNotifyTake(pdTRUE, portMAX_DELAY); to wait, Producer calls xTaskNotifyGive(ConsumerHandle); to signal

Solution

1. Step 1: Identify roles of tasks

   The Consumer should wait for a signal before processing, so it uses ulTaskNotifyTake() to block until notified.

2. Step 2: Producer signals Consumer

   The Producer sends the notification using xTaskNotifyGive() with the Consumer's task handle.

3. Final Answer:

   Consumer calls ulTaskNotifyTake(pdTRUE, portMAX_DELAY); to wait, Producer calls xTaskNotifyGive(ConsumerHandle); to signal -> Option D

4. Quick Check:

   Wait then signal = Consumer calls ulTaskNotifyTake(pdTRUE, portMAX_DELAY); to wait, Producer calls xTaskNotifyGive(ConsumerHandle); to signal [OK]

Hint: Consumer waits, Producer signals with xTaskNotifyGive() [OK]

Common Mistakes:

• Reversing roles of Producer and Consumer
• Both tasks signaling without waiting
• Using wrong task handles in calls