Mutex vs binary semaphore difference in FreeRTOS - Performance Comparison

Time Complexity: Mutex vs binary semaphore difference

O(n)

Understanding Time Complexity

When using FreeRTOS synchronization tools like mutexes and binary semaphores, it's important to understand how their operations scale with usage.

We want to see how the time cost changes as tasks try to lock and unlock these objects more often.

Scenario Under Consideration

Analyze the time complexity of task synchronization using a mutex and a binary semaphore.

// Mutex example
xSemaphoreTake(mutex, portMAX_DELAY);
// critical section
xSemaphoreGive(mutex);

// Binary semaphore example
xSemaphoreTake(binarySemaphore, portMAX_DELAY);
// critical section
xSemaphoreGive(binarySemaphore);
    

This code shows tasks taking and giving a mutex or binary semaphore to control access to shared resources.

Identify Repeating Operations

Both mutex and binary semaphore operations repeat every time a task tries to enter or leave the critical section.

• Primary operation: Taking and giving the synchronization object (mutex or binary semaphore).
• How many times: Once per critical section entry and exit, repeated by each task as needed.

How Execution Grows With Input

As more tasks try to access the shared resource, the number of take/give operations grows linearly with the number of attempts.

Number of Task Attempts (n)	Approx. Operations
10	20 (10 take + 10 give)
100	200 (100 take + 100 give)
1000	2000 (1000 take + 1000 give)

Pattern observation: The operations increase directly with the number of task attempts, doubling because each attempt has a take and a give.

Final Time Complexity

Time Complexity: O(n)

This means the time spent on synchronization grows in a straight line as more tasks try to lock and unlock the mutex or semaphore.

Common Mistake

[X] Wrong: "Mutex operations are always slower than binary semaphores because they are more complex."

[OK] Correct: Both have similar time complexity for take/give operations; the difference is in behavior like priority inheritance, not in how operation time grows with usage.

Interview Connect

Understanding how synchronization operations scale helps you write efficient multitasking code and explain your design choices clearly in interviews.

Self-Check

"What if we replaced the mutex with a counting semaphore? How would the time complexity change?"

Practice

1. Which of the following best describes the main difference between a mutex and a binary semaphore in FreeRTOS?

easy

A. Binary semaphores have ownership; mutexes do not.

B. Mutexes have ownership and priority inheritance; binary semaphores do not.

C. Mutexes are used only for signaling; binary semaphores are for exclusive access.

D. There is no difference; both behave exactly the same.

Solution

1. Step 1: Understand ownership concept

   Mutexes have ownership, meaning the task that locks it must unlock it. Binary semaphores do not have ownership.

2. Step 2: Understand priority inheritance

   Mutexes support priority inheritance to avoid priority inversion; binary semaphores do not.

3. Final Answer:

   Mutexes have ownership and priority inheritance; binary semaphores do not. -> Option B

4. Quick Check:

   Ownership + priority inheritance = Mutex [OK]

Hint: Mutex = ownership + priority; binary semaphore = simple flag [OK]

Common Mistakes:

• Thinking binary semaphores have ownership
• Confusing signaling role of binary semaphores
• Assuming mutexes do not support priority inheritance

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

easy

A. xSemaphoreCreateMutex()

B. xQueueCreateMutex()

C. xSemaphoreCreateBinary()

D. xMutexCreateSemaphore()

Solution

1. Step 1: Recall FreeRTOS API for mutex creation

   The function to create a mutex is xSemaphoreCreateMutex().

2. Step 2: Verify other options

   xSemaphoreCreateBinary() creates a binary semaphore, not a mutex. The other options are invalid API calls.

3. Final Answer:

   xSemaphoreCreateMutex() -> Option A

4. Quick Check:

   Mutex creation function = xSemaphoreCreateMutex() [OK]

Hint: Mutex creation always uses xSemaphoreCreateMutex() [OK]

Common Mistakes:

• Using xSemaphoreCreateBinary() for mutex
• Confusing queue creation functions with mutex
• Inventing non-existent API functions

3. Consider the following FreeRTOS code snippet:

SemaphoreHandle_t xMutex = xSemaphoreCreateMutex();
if (xSemaphoreTake(xMutex, 0) == pdTRUE) {
    // Critical section
    xSemaphoreGive(xMutex);
    printf("Mutex taken and released\n");
} else {
    printf("Failed to take mutex\n");
}

What will be the output when this code runs?

medium

A. Mutex taken and released

B. Failed to take mutex

C. Compilation error

D. No output

Solution

1. Step 1: Analyze mutex creation and take

   The mutex is created successfully. The call to xSemaphoreTake with zero block time tries to take the mutex immediately. Since it is free, it succeeds.

2. Step 2: Check critical section and release

   The mutex is given back with xSemaphoreGive, and the message "Mutex taken and released" is printed.

3. Final Answer:

   Mutex taken and released -> Option A

4. Quick Check:

   Mutex free at start, take succeeds, prints message [OK]

Hint: Mutex initially free, immediate take succeeds [OK]

Common Mistakes:

• Assuming take fails with zero block time
• Confusing mutex with binary semaphore behavior
• Expecting compilation errors from correct API usage

4. Identify the error in the following FreeRTOS code using a binary semaphore:

SemaphoreHandle_t xBinarySemaphore = xSemaphoreCreateBinary();
xSemaphoreGive(xBinarySemaphore);
if (xSemaphoreTake(xBinarySemaphore, portMAX_DELAY) == pdTRUE) {
    // Critical section
    xSemaphoreGive(xBinarySemaphore);
    xSemaphoreGive(xBinarySemaphore);
}

medium

A. Semaphore handle is not initialized.

B. Taking the semaphore with portMAX_DELAY is invalid.

C. Binary semaphore must be created with xSemaphoreCreateMutex().

D. Giving the semaphore twice causes incorrect behavior.

Solution

1. Step 1: Understand binary semaphore usage

   Binary semaphores act like flags with max count 1. Giving twice without taking in between can cause logic errors.

2. Step 2: Analyze the code's semaphore give calls

   The code gives the semaphore twice without an intervening take, which can lead to unexpected behavior or overflow.

3. Final Answer:

   Giving the semaphore twice causes incorrect behavior. -> Option D

4. Quick Check:

   Binary semaphore max count = 1, double give is wrong [OK]

Hint: Binary semaphore max count 1, don't give twice without take [OK]

Common Mistakes:

• Thinking portMAX_DELAY is invalid
• Confusing binary semaphore with mutex creation
• Ignoring semaphore initialization

5. You have two tasks: Task A (high priority) and Task B (low priority). Both need exclusive access to a shared resource. Which synchronization method should you use to avoid priority inversion and why? A) Use a mutex because it supports priority inheritance. B) Use a binary semaphore because it is simpler. C) Use a counting semaphore to allow multiple accesses. D) Use no synchronization to improve performance.

hard

A. Use a counting semaphore to allow multiple accesses.

B. Use a binary semaphore because it is simpler.

C. Use a mutex because it supports priority inheritance.

D. Use no synchronization to improve performance.

Solution

1. Step 1: Identify need for exclusive access with priority handling

   Both tasks need exclusive access, so synchronization is required. Priority inversion can occur if a low priority task holds the resource.

2. Step 2: Choose synchronization with priority inheritance

   Mutexes provide priority inheritance, temporarily boosting the low priority task's priority to avoid blocking the high priority task.

3. Final Answer:

   Use a mutex because it supports priority inheritance. -> Option C

4. Quick Check:

   Priority inversion avoidance = mutex [OK]

Hint: Use mutex for priority inheritance and exclusive access [OK]

Common Mistakes:

• Choosing binary semaphore ignoring priority inversion
• Using counting semaphore for exclusive access
• Skipping synchronization to save time