Semaphore for ISR-to-task signaling in FreeRTOS - Time & Space Complexity

Time Complexity: Semaphore for ISR-to-task signaling

O(n)

Understanding Time Complexity

When using a semaphore to signal from an interrupt to a task in FreeRTOS, it is important to understand how the time taken grows as the system runs.

We want to know how the number of operations changes as more signals happen.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void ISR_Handler(void) {
    BaseType_t xHigherPriorityTaskWoken = pdFALSE;
    xSemaphoreGiveFromISR(xSemaphore, &xHigherPriorityTaskWoken);
    portYIELD_FROM_ISR(xHigherPriorityTaskWoken);
}

void Task(void *pvParameters) {
    for(;;) {
        if(xSemaphoreTake(xSemaphore, portMAX_DELAY) == pdTRUE) {
            // Process event
        }
    }
}
    

This code shows an interrupt giving a semaphore to unblock a task waiting on it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The task repeatedly waits on the semaphore in a loop.
• How many times: The loop runs indefinitely, waiting for each semaphore signal from the ISR.

How Execution Grows With Input

Each time the ISR signals, the task wakes and processes one event. The number of operations grows directly with the number of signals.

Input Size (n)	Approx. Operations
10	10 semaphore takes and event processes
100	100 semaphore takes and event processes
1000	1000 semaphore takes and event processes

Pattern observation: The work grows linearly with the number of ISR signals.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows in direct proportion to how many times the ISR signals the semaphore.

Common Mistake

[X] Wrong: "The semaphore take inside the task loop runs in constant time regardless of how many signals happen."

[OK] Correct: Each semaphore take corresponds to one signal, so more signals mean more takes and more processing, increasing total operations.

Interview Connect

Understanding how signaling between interrupts and tasks scales helps you design responsive and efficient real-time systems.

Self-Check

"What if the task processed multiple events per semaphore take? How would the time complexity change?"

Practice

1. What is the main purpose of using a semaphore in FreeRTOS for ISR-to-task signaling?

easy

A. To disable interrupts during task execution

B. To create a new task inside an ISR

C. To safely notify a task from an interrupt service routine (ISR)

D. To allocate memory dynamically in an ISR

Solution

1. Step 1: Understand semaphore role in FreeRTOS

   Semaphores are synchronization tools used to signal between tasks or between ISRs and tasks.

2. Step 2: Identify ISR-to-task signaling purpose

   In FreeRTOS, semaphores let an ISR notify a task safely without blocking or complex synchronization.

3. Final Answer:

   To safely notify a task from an interrupt service routine (ISR) -> Option C

4. Quick Check:

   Semaphore signals task from ISR = A [OK]

Hint: Semaphores signal tasks from ISRs safely [OK]

Common Mistakes:

• Thinking semaphores create tasks
• Confusing semaphores with disabling interrupts
• Using semaphores for memory allocation

2. Which FreeRTOS function is used inside an ISR to give a semaphore to a task?

easy

A. xSemaphoreGiveFromISR()

B. xSemaphoreTakeFromISR()

C. xSemaphoreCreateFromISR()

D. xSemaphoreGive()

Solution

1. Step 1: Recall ISR-safe semaphore functions

   FreeRTOS provides special functions for ISR context to avoid blocking and ensure safety.

2. Step 2: Identify the correct ISR semaphore give function

   The function to give a semaphore from an ISR is xSemaphoreGiveFromISR().

3. Final Answer:

   xSemaphoreGiveFromISR() -> Option A

4. Quick Check:

   Give semaphore from ISR = xSemaphoreGiveFromISR() [OK]

Hint: ISR uses xSemaphoreGiveFromISR() to signal tasks [OK]

Common Mistakes:

• Using xSemaphoreGive() inside ISR (not safe)
• Confusing take and give functions
• Assuming xSemaphoreCreateFromISR() exists

3. Given the code snippet below, what will be the output printed by the task?

SemaphoreHandle_t xSemaphore;

void ISR_Handler() {
    BaseType_t xHigherPriorityTaskWoken = pdFALSE;
    xSemaphoreGiveFromISR(xSemaphore, &xHigherPriorityTaskWoken);
}

void TaskFunction(void *pvParameters) {
    if (xSemaphoreTake(xSemaphore, portMAX_DELAY) == pdTRUE) {
        printf("Semaphore received\n");
    }
}

medium

A. Semaphore received twice

B. No output

C. Runtime error

D. Semaphore received

Solution

1. Step 1: Analyze ISR giving semaphore

   The ISR calls xSemaphoreGiveFromISR() which releases the semaphore.

2. Step 2: Analyze task waiting on semaphore

   The task waits indefinitely with xSemaphoreTake() and prints "Semaphore received" when it gets the semaphore.

3. Final Answer:

   Semaphore received -> Option D

4. Quick Check:

   Task prints after semaphore take = C [OK]

Hint: Task prints after successful semaphore take [OK]

Common Mistakes:

• Thinking semaphore is given twice
• Assuming no output if ISR runs
• Expecting runtime error without initialization

4. Identify the error in the following ISR code snippet for giving a semaphore:

void ISR_Handler() {
    xSemaphoreGive(xSemaphore);
}

medium

A. xSemaphoreGive() cannot be called from an ISR

B. Semaphore must be taken before giving

C. ISR must not use semaphores

D. xSemaphoreGive() requires a pointer argument

Solution

1. Step 1: Check function suitability for ISR

   xSemaphoreGive() is not safe to call inside an ISR because it may block or cause race conditions.

2. Step 2: Identify correct ISR function

   Use xSemaphoreGiveFromISR() inside ISRs to safely give semaphores.

3. Final Answer:

   xSemaphoreGive() cannot be called from an ISR -> Option A

4. Quick Check:

   Use xSemaphoreGiveFromISR() in ISR, not xSemaphoreGive() [OK]

Hint: Use xSemaphoreGiveFromISR() inside ISR, not xSemaphoreGive() [OK]

Common Mistakes:

• Calling xSemaphoreGive() inside ISR
• Ignoring ISR context restrictions
• Assuming semaphore must be taken before giving

5. You want a task to respond immediately when a hardware interrupt occurs. Which sequence correctly uses a semaphore for ISR-to-task signaling in FreeRTOS?

hard

A. Create counting semaphore; task calls xSemaphoreGive(); ISR calls xSemaphoreTakeFromISR()

B. Create binary semaphore; ISR calls xSemaphoreGiveFromISR(); task calls xSemaphoreTake() with portMAX_DELAY

C. Create mutex; ISR calls xSemaphoreGive(); task calls xSemaphoreTake() with zero timeout

D. Create binary semaphore; task calls xSemaphoreGiveFromISR(); ISR calls xSemaphoreTake()

Solution

1. Step 1: Identify correct semaphore type and usage

   Binary semaphore is suitable for signaling events from ISR to task.

2. Step 2: Confirm correct function calls and order

   ISR must call xSemaphoreGiveFromISR() to signal; task waits with xSemaphoreTake() blocking indefinitely (portMAX_DELAY) until signaled.

3. Final Answer:

   Create binary semaphore; ISR calls xSemaphoreGiveFromISR(); task calls xSemaphoreTake() with portMAX_DELAY -> Option B

4. Quick Check:

   Binary semaphore + ISR give + task take = A [OK]

Hint: ISR gives semaphore, task takes with infinite wait [OK]

Common Mistakes:

• Using mutex instead of semaphore
• Calling give in task and take in ISR
• Using zero timeout causing missed signals