Recursive mutex for nested locking in FreeRTOS - Time & Space Complexity

Time Complexity: Recursive mutex for nested locking

O(n)

Understanding Time Complexity

When using recursive mutexes in FreeRTOS, it's important to understand how the locking operations scale as the number of nested locks increases.

We want to know how the time to lock and unlock changes when a task locks the same mutex multiple times.

Scenario Under Consideration

Analyze the time complexity of the following recursive mutex locking code.

SemaphoreHandle_t xMutex = xSemaphoreCreateRecursiveMutex();

void vTaskFunction() {
    for (int i = 0; i < n; i++) {
        xSemaphoreTakeRecursive(xMutex, portMAX_DELAY);
    }
    // Critical section
    for (int i = 0; i < n; i++) {
        xSemaphoreGiveRecursive(xMutex);
    }
}
    

This code locks the same recursive mutex n times in a row, then unlocks it n times, allowing nested locking.

Identify Repeating Operations

Look at what repeats in the code:

• Primary operation: Calling xSemaphoreTakeRecursive and xSemaphoreGiveRecursive inside loops.
• How many times: Each is called n times, where n is the nesting level.

How Execution Grows With Input

As the nesting level n increases, the number of lock and unlock calls grows linearly.

Input Size (n)	Approx. Operations
10	About 20 calls (10 locks + 10 unlocks)
100	About 200 calls
1000	About 2000 calls

Pattern observation: The total operations grow directly in proportion to n, doubling because of locking and unlocking.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete all nested locks and unlocks grows linearly with the number of times the mutex is locked.

Common Mistake

[X] Wrong: "Recursive mutex locking is constant time no matter how many times it is locked."

[OK] Correct: Each nested lock call still takes time, so locking n times means the total time grows with n. It is not a single instant operation.

Interview Connect

Understanding how recursive mutexes behave helps you reason about task synchronization and performance in embedded systems, a key skill for real-time programming.

Self-Check

"What if we replaced the recursive mutex with a normal mutex that does not support nested locking? How would the time complexity and behavior change?"

Practice

1.

What is the main advantage of using a recursive mutex in FreeRTOS?

easy

A. It increases the priority of the task holding the mutex.

B. It automatically unlocks after a fixed time.

C. It allows the same task to lock the mutex multiple times without deadlock.

D. It can be shared between tasks without any locking.

Solution

1. Step 1: Understand mutex behavior

   Normal mutexes block if the same task tries to lock again, causing deadlock.

2. Step 2: Role of recursive mutex

   Recursive mutexes allow the same task to lock multiple times safely, avoiding deadlock.

3. Final Answer:

   It allows the same task to lock the mutex multiple times without deadlock. -> Option C

4. Quick Check:

   Recursive mutex = multiple locks by same task [OK]

Hint: Recursive mutex lets one task lock repeatedly safely [OK]

Common Mistakes:

• Thinking mutex unlocks automatically
• Confusing recursive mutex with priority inheritance
• Assuming mutex can be shared without locking

2.

Which FreeRTOS function is used to lock a recursive mutex?

SemaphoreHandle_t xMutex = xSemaphoreCreateRecursiveMutex();
// Lock the mutex here

easy

A. xSemaphoreTakeRecursive(xMutex, portMAX_DELAY);

B. xSemaphoreGiveRecursive(xMutex);

C. xSemaphoreTake(xMutex, portMAX_DELAY);

D. xSemaphoreCreateMutex();

Solution

1. Step 1: Identify locking function for recursive mutex

   Recursive mutexes require xSemaphoreTakeRecursive() to lock safely multiple times.

2. Step 2: Match function usage

   xSemaphoreTakeRecursive(xMutex, portMAX_DELAY) locks the recursive mutex properly.

3. Final Answer:

   xSemaphoreTakeRecursive(xMutex, portMAX_DELAY); -> Option A

4. Quick Check:

   Lock recursive mutex = xSemaphoreTakeRecursive() [OK]

Hint: Use xSemaphoreTakeRecursive() to lock recursive mutex [OK]

Common Mistakes:

• Using xSemaphoreTake() instead of recursive version
• Confusing give and take functions
• Trying to create mutex again instead of locking

3.

What will be the output of the following FreeRTOS code snippet?

SemaphoreHandle_t xMutex = xSemaphoreCreateRecursiveMutex();

void Task(void *params) {
    xSemaphoreTakeRecursive(xMutex, portMAX_DELAY);
    xSemaphoreTakeRecursive(xMutex, portMAX_DELAY);
    xSemaphoreGiveRecursive(xMutex);
    xSemaphoreGiveRecursive(xMutex);
    if (xSemaphoreGiveRecursive(xMutex) == pdFALSE) {
        printf("Mutex fully released\n");
    } else {
        printf("Mutex still locked\n");
    }
}

medium

A. Mutex fully released

B. Mutex still locked

C. Compilation error

D. Deadlock occurs

Solution

1. Step 1: Count lock and unlock calls

   The mutex is locked twice and unlocked twice, so it is fully released after two gives.

2. Step 2: Analyze extra unlock call

   The third give returns pdFALSE because mutex is already fully released, triggering "Mutex fully released" print.

3. Final Answer:

   Mutex fully released -> Option A

4. Quick Check:

   Extra unlock returns false = fully released [OK]

Hint: Unlock same times as lock to fully release mutex [OK]

Common Mistakes:

• Assuming extra unlock succeeds
• Ignoring return value of xSemaphoreGiveRecursive()
• Thinking deadlock occurs on unlock

4.

Identify the error in this FreeRTOS recursive mutex usage:

SemaphoreHandle_t xMutex = xSemaphoreCreateRecursiveMutex();

void Task(void *params) {
    xSemaphoreTakeRecursive(xMutex, portMAX_DELAY);
    // Some code
    xSemaphoreGive(xMutex);
}

medium

A. Not locking the mutex before unlocking.

B. Using xSemaphoreGive() instead of xSemaphoreGiveRecursive() to unlock.

C. Creating mutex inside the task instead of globally.

D. Using portMAX_DELAY as timeout.

Solution

1. Step 1: Check unlock function for recursive mutex

   Recursive mutexes must be unlocked with xSemaphoreGiveRecursive(), not xSemaphoreGive().

2. Step 2: Identify mismatch in lock/unlock

   Using xSemaphoreGive() causes undefined behavior or errors because it is for normal mutexes.

3. Final Answer:

   Using xSemaphoreGive() instead of xSemaphoreGiveRecursive() to unlock. -> Option B

4. Quick Check:

   Unlock recursive mutex = xSemaphoreGiveRecursive() [OK]

Hint: Unlock recursive mutex with xSemaphoreGiveRecursive() only [OK]

Common Mistakes:

• Mixing normal and recursive mutex functions
• Ignoring correct unlock function
• Assuming portMAX_DELAY causes error here

5.

You have a recursive mutex locked three times by the same task. What must you do to avoid deadlock when unlocking?

// Pseudocode
xSemaphoreTakeRecursive(xMutex, portMAX_DELAY);
xSemaphoreTakeRecursive(xMutex, portMAX_DELAY);
xSemaphoreTakeRecursive(xMutex, portMAX_DELAY);
// ... critical section ...
// Unlock here

hard

A. Call xSemaphoreTakeRecursive() again to balance locks.

B. Call xSemaphoreGiveRecursive() once to release the mutex fully.

C. Call xSemaphoreGive() three times to release the mutex.

D. Call xSemaphoreGiveRecursive() exactly three times before releasing the mutex.

Solution

1. Step 1: Understand recursive mutex lock count

   Each lock increments a count; unlocking must decrement the same number of times.

2. Step 2: Proper unlock calls

   To fully release, call xSemaphoreGiveRecursive() three times matching the three locks.

3. Final Answer:

   Call xSemaphoreGiveRecursive() exactly three times before releasing the mutex. -> Option D

4. Quick Check:

   Unlock count = lock count to avoid deadlock [OK]

Hint: Unlock recursive mutex as many times as locked [OK]

Common Mistakes:

• Unlocking fewer times causing deadlock
• Using xSemaphoreGive() instead of recursive version
• Trying to unlock more times than locked