Rendezvous (sync) pattern in FreeRTOS - Time & Space Complexity

Time Complexity: Rendezvous (sync) pattern

O(n)

Understanding Time Complexity

When tasks wait for each other to reach a point before continuing, it affects how long the program runs.

We want to see how the waiting time grows as more tasks synchronize.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Two tasks synchronize using a binary semaphore
SemaphoreHandle_t syncSemaphore;

void TaskA(void *params) {
    // Do some work
    xSemaphoreGive(syncSemaphore); // Signal TaskB
    xSemaphoreTake(syncSemaphore, portMAX_DELAY); // Wait for TaskB
}

void TaskB(void *params) {
    xSemaphoreTake(syncSemaphore, portMAX_DELAY); // Wait for TaskA
    // Do some work
    xSemaphoreGive(syncSemaphore); // Signal TaskA
}
    

This code shows two tasks using a semaphore to wait for each other before continuing.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Each task waits once on the semaphore before proceeding.
• How many times: The synchronization happens once per rendezvous point in each task.

How Execution Grows With Input

As the number of tasks or rendezvous points increases, the waiting time grows linearly because each task must wait for others.

Input Size (n)	Approx. Operations
2 tasks	2 waits and 2 signals
10 tasks	10 waits and 10 signals
100 tasks	100 waits and 100 signals

Pattern observation: The number of synchronization operations grows directly with the number of tasks.

Final Time Complexity

Time Complexity: O(n)

This means the waiting and signaling steps increase in a straight line as more tasks synchronize.

Common Mistake

[X] Wrong: "Adding more tasks won't affect the waiting time much because they run in parallel."

[OK] Correct: Even if tasks run at the same time, each must wait for others at the rendezvous point, so waiting grows with more tasks.

Interview Connect

Understanding how tasks wait for each other helps you design programs that run smoothly without unnecessary delays.

Self-Check

"What if we replaced the binary semaphore with a counting semaphore for multiple tasks? How would the time complexity change?"

Practice

1. What is the main purpose of the Rendezvous (sync) pattern in FreeRTOS?

easy

A. To synchronize two tasks so they wait for each other before proceeding

B. To create multiple independent tasks running without coordination

C. To prioritize one task over another permanently

D. To allocate memory dynamically for tasks

Solution

1. Step 1: Understand the Rendezvous pattern concept

   The Rendezvous pattern is designed to synchronize two tasks so that each waits for the other to reach a certain point before continuing.

2. Step 2: Identify the purpose in FreeRTOS context

   In FreeRTOS, this synchronization is often done using semaphores to signal readiness and wait for the other task.

3. Final Answer:

   To synchronize two tasks so they wait for each other before proceeding -> Option A

4. Quick Check:

   Rendezvous = Synchronize tasks [OK]

Hint: Rendezvous means tasks meet and wait for each other [OK]

Common Mistakes:

• Thinking it creates independent tasks without coordination
• Confusing with task prioritization
• Assuming it manages memory allocation

2. Which FreeRTOS primitive is typically used to implement the Rendezvous pattern?

easy

A. Mutex

B. Queue

C. Semaphore

D. Event Group

Solution

1. Step 1: Recall synchronization primitives in FreeRTOS

   FreeRTOS provides mutexes, semaphores, queues, and event groups for task synchronization and communication.

2. Step 2: Identify which primitive signals readiness and waits

   The Rendezvous pattern requires signaling and waiting between two tasks, which is best done using semaphores.

3. Final Answer:

   Semaphore -> Option C

4. Quick Check:

   Rendezvous uses semaphores [OK]

Hint: Semaphores signal and wait between tasks [OK]

Common Mistakes:

• Choosing mutex which is for mutual exclusion, not sync
• Confusing queues with direct signaling
• Using event groups which are for multiple event flags

3. Consider two tasks using binary semaphores for Rendezvous. Task A signals semaphore S1 and waits on S2. Task B signals S2 and waits on S1. What happens if Task A runs first and signals S1 before Task B waits on it?

medium

A. Both tasks will run without blocking

B. Task B will block indefinitely waiting on S1

C. Task A will block indefinitely waiting on S2

D. Task B will unblock immediately when it waits on S1

Solution

1. Step 1: Understand semaphore signaling and waiting

   If Task A signals semaphore S1 before Task B waits on it, the semaphore count becomes available.

2. Step 2: Analyze Task B's wait on S1

   When Task B waits on S1, it finds the semaphore already signaled and unblocks immediately without waiting.

3. Final Answer:

   Task B will unblock immediately when it waits on S1 -> Option D

4. Quick Check:

   Signaled semaphore unblocks waiting task immediately [OK]

Hint: Semaphore signals persist until taken by waiting task [OK]

Common Mistakes:

• Assuming tasks must wait even if semaphore is signaled
• Thinking Task A blocks waiting on S2 first
• Believing both tasks run without blocking always

4. Given this snippet for Rendezvous synchronization, what is the error?

void TaskA(void *pvParameters) {
  xSemaphoreGive(SemA);
  xSemaphoreTake(SemB, portMAX_DELAY);
  // Continue...
}

void TaskB(void *pvParameters) {
  xSemaphoreTake(SemA, portMAX_DELAY);
  xSemaphoreGive(SemB);
  // Continue...
}

medium

A. Tasks should not use semaphores for synchronization

B. Semaphores SemA and SemB are not created before use

C. xSemaphoreGive should be called after xSemaphoreTake in TaskA

D. portMAX_DELAY is invalid for xSemaphoreTake

Solution

1. Step 1: Check semaphore initialization

   Before using semaphores, they must be created with xSemaphoreCreateBinary or similar functions.

2. Step 2: Identify missing creation

   The code snippet does not show creation of SemA and SemB, which will cause runtime errors or undefined behavior.

3. Final Answer:

   Semaphores SemA and SemB are not created before use -> Option B

4. Quick Check:

   Semaphores must be created before giving or taking [OK]

Hint: Always create semaphores before using them [OK]

Common Mistakes:

• Thinking order of give/take is wrong here
• Believing semaphores are not for synchronization
• Misunderstanding portMAX_DELAY usage

5. You want two tasks to synchronize at multiple points using the Rendezvous pattern. Which approach ensures no deadlock if one task signals twice before the other waits?

hard

A. Use counting semaphores instead of binary semaphores

B. Use mutexes to lock and unlock tasks

C. Use queues to send messages instead of semaphores

D. Use event groups with a single bit flag

Solution

1. Step 1: Understand semaphore types and their behavior

   Binary semaphores can only hold one signal at a time, so signaling twice before waiting can cause lost signals and deadlock.

2. Step 2: Identify solution to handle multiple signals

   Counting semaphores can hold multiple signals, allowing tasks to signal multiple times without losing signals, preventing deadlock.

3. Final Answer:

   Use counting semaphores instead of binary semaphores -> Option A

4. Quick Check:

   Counting semaphores handle multiple signals safely [OK]

Hint: Counting semaphores count signals, preventing lost sync [OK]

Common Mistakes:

• Using mutexes which do not count signals
• Using queues which add complexity
• Using event groups with single bits only