Counting semaphore for resource pools in FreeRTOS - Time & Space Complexity

Time Complexity: Counting semaphore for resource pools

O(1)

Understanding Time Complexity

We want to understand how the time to take or give a counting semaphore changes as the number of waiting tasks grows.

How does the system handle waiting and releasing resources when many tasks compete?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Create a counting semaphore with max count 5
SemaphoreHandle_t xSemaphore = xSemaphoreCreateCounting(5, 5);

// Task tries to take a resource
if (xSemaphoreTake(xSemaphore, portMAX_DELAY) == pdTRUE) {
    // Use the resource
    // ...
    // Release the resource
    xSemaphoreGive(xSemaphore);
}
    

This code manages access to a pool of 5 identical resources using a counting semaphore.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Taking and giving the semaphore to access resources.
• How many times: Constant time per take/give; no loops that scale with queue length. Internally manages queue with O(1) enqueue/dequeue.

How Execution Grows With Input

As the number of tasks waiting grows, the time to take or give remains constant.

Input Size (n)	Approx. Operations
10	About 5-10 queue operations
100	About 5-10 queue operations
1000	About 5-10 queue operations

Pattern observation: The work per operation remains constant regardless of the number of waiting tasks.

Final Time Complexity

Time Complexity: O(1)

This means the time to manage the semaphore and waiting tasks per operation remains constant, independent of the number of tasks waiting.

Common Mistake

[X] Wrong: "Taking or giving a counting semaphore takes longer as more tasks wait because it scans the queue."

[OK] Correct: FreeRTOS uses doubly-linked lists for efficient O(1) enqueue (tail) and dequeue (head) operations. Each give wakes only one task.

Interview Connect

Understanding how resource management scales helps you design systems that stay responsive even when many tasks compete for limited resources.

Self-Check

"What if the semaphore was binary instead of counting? How would the time complexity change when many tasks wait?"

Practice

1. What is the main purpose of a counting semaphore in FreeRTOS when managing resource pools?

easy

A. To track the number of available identical resources

B. To create tasks with different priorities

C. To store data between tasks

D. To handle interrupts directly

Solution

1. Step 1: Understand counting semaphore role

   A counting semaphore keeps track of how many identical resources are free or in use.

2. Step 2: Compare with other options

   Creating tasks, storing data, or handling interrupts are not roles of counting semaphores.

3. Final Answer:

   To track the number of available identical resources -> Option A

4. Quick Check:

   Counting semaphore = resource count tracker [OK]

Hint: Counting semaphore counts free resources, not tasks or data [OK]

Common Mistakes:

• Confusing counting semaphore with binary semaphore
• Thinking it creates or manages tasks
• Assuming it stores data

2. Which of the following is the correct way to create a counting semaphore with a maximum count of 5 and an initial count of 3 in FreeRTOS?

easy

A. xSemaphoreCreateCounting(3, 5);

B. xSemaphoreCreateCounting(5, 3);

C. xSemaphoreCreateCounting(5);

D. xSemaphoreCreateCounting(3);

Solution

1. Step 1: Recall function parameters

   The function xSemaphoreCreateCounting takes max count first, then initial count.

2. Step 2: Match parameters to options

   xSemaphoreCreateCounting(5, 3); uses (5, 3) which means max count 5 and initial count 3, correct order.

3. Final Answer:

   xSemaphoreCreateCounting(5, 3); -> Option B

4. Quick Check:

   Max count first, initial count second [OK]

Hint: Remember max count is first parameter, initial count second [OK]

Common Mistakes:

• Swapping max and initial count parameters
• Using only one parameter
• Confusing with binary semaphore creation

3. Given the following code snippet, what will be the value of the semaphore count after both tasks successfully take the semaphore once?

SemaphoreHandle_t sem = xSemaphoreCreateCounting(3, 3);
xSemaphoreTake(sem, 0);
xSemaphoreTake(sem, 0);

medium

A. 3

B. 0

C. 2

D. 1

Solution

1. Step 1: Understand initial semaphore count

   The semaphore starts with count 3 (max and initial both 3).

2. Step 2: Subtract count for each take

   Each xSemaphoreTake reduces count by 1 if successful. Two takes reduce count by 2.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   3 - 2 takes = 1 [OK]

Hint: Each take reduces count by one if successful [OK]

Common Mistakes:

• Assuming count stays the same after take
• Confusing take with give operation
• Thinking count can go below zero

4. Identify the error in this code snippet that uses a counting semaphore for a resource pool:

SemaphoreHandle_t sem = xSemaphoreCreateCounting(2, 2);
xSemaphoreGive(sem);

medium

A. xSemaphoreGive should be called before creation

B. xSemaphoreCreateCounting parameters are reversed

C. Calling xSemaphoreGive when semaphore count is at max causes overflow

D. No error, code is correct

Solution

1. Step 1: Check initial semaphore count

   The semaphore is created with max count 2 and initial count 2, so it's full.

2. Step 2: Analyze xSemaphoreGive call

   Giving semaphore when count is already max causes overflow error or undefined behavior.

3. Final Answer:

   Calling xSemaphoreGive when semaphore count is at max causes overflow -> Option C

4. Quick Check:

   Giving at max count causes overflow [OK]

Hint: Don't give semaphore if count is already at max [OK]

Common Mistakes:

• Ignoring semaphore max count limits
• Swapping max and initial counts
• Calling give before creating semaphore

5. You have a resource pool of 4 identical devices. You want to create a counting semaphore to manage access. Initially, 2 devices are free. Which code snippet correctly creates and initializes the semaphore for this scenario?

hard

A. SemaphoreHandle_t sem = xSemaphoreCreateCounting(4, 2);

B. SemaphoreHandle_t sem = xSemaphoreCreateCounting(2, 2);

C. SemaphoreHandle_t sem = xSemaphoreCreateCounting(4, 4);

D. SemaphoreHandle_t sem = xSemaphoreCreateCounting(2, 4);

Solution

1. Step 1: Identify max and initial counts

   Max count is total devices (4), initial count is free devices (2).

2. Step 2: Match parameters to function call

   Correct call is xSemaphoreCreateCounting(4, 2) with max 4 and initial 2.

3. Final Answer:

   SemaphoreHandle_t sem = xSemaphoreCreateCounting(4, 2); -> Option A

4. Quick Check:

   Max = total devices, initial = free devices [OK]

Hint: Max count = total resources, initial count = free resources [OK]

Common Mistakes:

• Swapping max and initial counts
• Setting initial count higher than max
• Using max count less than total resources