Binary semaphore creation and usage in FreeRTOS - Time & Space Complexity

Time Complexity: Binary semaphore creation and usage

O(n)

Understanding Time Complexity

We want to understand how the time cost changes when using binary semaphores in FreeRTOS.

Specifically, how the operations scale when tasks take or give the semaphore.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SemaphoreHandle_t xSemaphore;

void setup() {
    xSemaphore = xSemaphoreCreateBinary();
}

void task1() {
    if (xSemaphoreTake(xSemaphore, portMAX_DELAY) == pdTRUE) {
        // critical section
        xSemaphoreGive(xSemaphore);
    }
}

This code creates a binary semaphore and a task that waits to take it, enters a critical section, then gives it back.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The task repeatedly tries to take and give the semaphore.
• How many times: This happens each time the task runs and needs the resource.

How Execution Grows With Input

Each semaphore take or give is a single operation regardless of how many tasks exist.

Input Size (number of semaphore operations)	Approx. Operations
10	10
100	100
1000	1000

Pattern observation: The time grows linearly with the number of semaphore operations.

Final Time Complexity

Time Complexity: O(n)

This means the time spent grows directly with how many times the semaphore is taken and given.

Common Mistake

[X] Wrong: "The time complexity of using semaphores is O(1) regardless of the number of operations."

[OK] Correct: Each take or give takes constant time, but for n operations the total time is O(n).

Interview Connect

Understanding how synchronization tools like semaphores scale helps you write efficient multitasking programs and shows you know how to reason about system performance.

Self-Check

"What if we changed the binary semaphore to a counting semaphore? How would the time complexity change?"

Practice

1. What is the primary purpose of a binary semaphore in FreeRTOS?

easy

A. To store multiple values for task communication

B. To signal and control access to shared resources between tasks

C. To create multiple tasks automatically

D. To allocate memory dynamically

Solution

1. Step 1: Understand the role of binary semaphores

   Binary semaphores are used to signal availability or control access to resources between tasks.

2. Step 2: Compare options with this role

   Only To signal and control access to shared resources between tasks describes signaling and controlling access, which matches the purpose of binary semaphores.

3. Final Answer:

   To signal and control access to shared resources between tasks -> Option B

4. Quick Check:

   Binary semaphore = resource signaling [OK]

Hint: Binary semaphore controls resource access between tasks [OK]

Common Mistakes:

• Confusing binary semaphore with counting semaphore
• Thinking it stores multiple values
• Assuming it creates tasks

2. Which of the following is the correct way to create a binary semaphore in FreeRTOS?

easy

A. xSemaphoreCreateBinary();

B. xSemaphoreCreateCounting(1, 0);

C. xSemaphoreCreateMutex();

D. xSemaphoreCreateBinary(1);

Solution

1. Step 1: Recall the function to create a binary semaphore

   The correct function is xSemaphoreCreateBinary() with no parameters.

2. Step 2: Check each option

   xSemaphoreCreateBinary(); matches the correct function. xSemaphoreCreateCounting(1, 0); creates a counting semaphore, C creates a mutex, and D is invalid syntax.

3. Final Answer:

   xSemaphoreCreateBinary(); -> Option A

4. Quick Check:

   Create binary semaphore = xSemaphoreCreateBinary() [OK]

Hint: Use xSemaphoreCreateBinary() with no arguments [OK]

Common Mistakes:

• Using counting semaphore creation instead
• Adding parameters to xSemaphoreCreateBinary()
• Confusing mutex creation with binary semaphore

3. Consider the following FreeRTOS code snippet:

SemaphoreHandle_t xBinarySemaphore = xSemaphoreCreateBinary();

void Task1(void *pvParameters) {
    if (xSemaphoreTake(xBinarySemaphore, portMAX_DELAY) == pdTRUE) {
        // Critical section
    }
}

void Task2(void *pvParameters) {
    xSemaphoreGive(xBinarySemaphore);
}

What will happen when Task1 runs before Task2?

medium

A. Task1 will enter the critical section immediately

B. Task1 will skip the critical section

C. Task1 will cause a runtime error

D. Task1 will block indefinitely until Task2 gives the semaphore

Solution

1. Step 1: Analyze xSemaphoreTake with portMAX_DELAY

   Task1 calls xSemaphoreTake with portMAX_DELAY, so it waits indefinitely for the semaphore.

2. Step 2: Consider initial semaphore state and Task2 action

   The semaphore is created but not given initially, so Task1 blocks until Task2 calls xSemaphoreGive.

3. Final Answer:

   Task1 will block indefinitely until Task2 gives the semaphore -> Option D

4. Quick Check:

   xSemaphoreTake with portMAX_DELAY blocks until given [OK]

Hint: xSemaphoreTake with portMAX_DELAY waits until given [OK]

Common Mistakes:

• Assuming semaphore is initially available
• Thinking Task1 runs critical section immediately
• Confusing blocking with error

4. Identify the error in this FreeRTOS binary semaphore usage:

SemaphoreHandle_t xBinarySemaphore = xSemaphoreCreateBinary();

void Task(void *pvParameters) {
    if (xSemaphoreTake(xBinarySemaphore, 0) == pdTRUE) {
        // Do work
        xSemaphoreGive(xBinarySemaphore);
    }
}

medium

A. xSemaphoreCreateBinary requires a parameter

B. xSemaphoreGive should be called before xSemaphoreTake

C. Semaphore is never given before take, so take always fails

D. xSemaphoreTake timeout cannot be zero

Solution

1. Step 1: Check initial semaphore state after creation

   xSemaphoreCreateBinary creates a semaphore that is initially empty (not given).

2. Step 2: Analyze xSemaphoreTake with zero timeout

   With zero timeout, xSemaphoreTake returns immediately. Since semaphore is empty, it returns pdFALSE, so the if block never runs.

3. Final Answer:

   Semaphore is never given before take, so take always fails -> Option C

4. Quick Check:

   Binary semaphore empty at creation, take with zero timeout fails [OK]

Hint: Binary semaphore must be given before take succeeds [OK]

Common Mistakes:

• Assuming semaphore is initially given
• Thinking zero timeout means wait forever
• Confusing function parameters

5. You want to synchronize two tasks so that Task B only runs after Task A signals completion using a binary semaphore. Which sequence correctly implements this?

hard

A. Task A calls xSemaphoreGive() after work; Task B calls xSemaphoreTake() with portMAX_DELAY before work

B. Task B calls xSemaphoreGive() before work; Task A calls xSemaphoreTake() after work

C. Both tasks call xSemaphoreTake() simultaneously; semaphore is given once at start

D. Task A and Task B both call xSemaphoreGive() without taking

Solution

1. Step 1: Understand synchronization with binary semaphore

   Task B must wait for Task A's signal, so Task B should take the semaphore and block until given.

2. Step 2: Match sequence to this logic

   Task A gives the semaphore after finishing work; Task B takes it with portMAX_DELAY to wait indefinitely.

3. Final Answer:

   Task A calls xSemaphoreGive() after work; Task B calls xSemaphoreTake() with portMAX_DELAY before work -> Option A

4. Quick Check:

   Give after work, take before work = sync tasks [OK]

Hint: Give semaphore after work; take before work to sync tasks [OK]

Common Mistakes:

• Reversing give and take roles
• Both tasks giving without taking
• Taking without giving semaphore