Vultr DocsLatest Content

Print in Order

Updated on 20 June, 2025
Print in Order header image

Problem Statement

In the given scenario, we have a class named Foo with three methods: first(), second(), and third(). These methods need to be executed in a specific sequence (first(), then second(), finally third()) from within three individual threads labeled A, B, and C. Each thread is responsible for one specific method call. The challenge lies in ensuring that the execution of these methods is ordered correctly regardless of the threads' initiation sequence in the environment, which is inherently nondeterministic. In other words, even if thread B (which calls second()) starts execution before thread A (which calls first()), the output should still enforce the order as "firstsecondthird" due to the logical sequence required by the problem.

Examples

Example 1

Input:

nums = [1,2,3]

Output:

"firstsecondthird"

Explanation:

There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

Example 2

Input:

nums = [1,3,2]

Output:

"firstsecondthird"

Explanation:

The input [1,3,2] means thread A calls first(), thread B calls third(), and thread C calls second(). "firstsecondthird" is the correct output.

Constraints

  • nums is a permutation of [1, 2, 3].

Approach and Intuition

The key to solving this concurrency problem is to ensure that certain conditions are met before threads can proceed with their execution. Here’s the step-by-step approach to achieve this:

  1. Using Synchronization Tools:

    • We utilize synchronization mechanisms like locks, events, or semaphores which enable us to enforce constraints on the order of execution.

  2. Guarantees Through States:

    • Implement states where the state of each method (first, second, third) is dependent on the completion of its predecessor. For instance, second() should only execute if first() has completed.

  3. Apply Condition Variables or Semaphores:

    • Use two semaphores or condition variables. The first semaphore initializes at 0 and is released after first() finishes. It acts as a trigger for second() to start. Similarly, the second semaphore is released once second() completes, allowing third() to proceed.

  4. Thread Joining (Alternative Approach):

    • Although not always advisable due to potential wait times, making thread B wait for thread A and thread C wait for thread B to complete (thread joining) can be another approach.

  5. Checking Execution through Examples:

    • In Example 1, with inputs as nums = [1,2,3], threads are fired in the order they are supposed to logically execute, that is, A then B then C. This straightforward case directly matches the logical sequence.
    • In Example 2, the input nums = [1,3,2] suggests threads initiate out-of-order (A, C, B). However, the use of synchronization tools as explained will rectify this and ensure the output remains "firstsecondthird".

This challenge fundamentally builds on concurrent programming aspects, where synchronization is critical to maintaining the integrity and order of operations in multi-threaded environments.

Solutions

  • C++
  • Java
cpp 
#include <semaphore.h>

class FooBar {

protected:
    sem_t job1Done;
    sem_t job2Done;

public:

    FooBar() {
        sem_init(&job1Done, 0, 0);
        sem_init(&job2Done, 0, 0);
    }

    void firstJob(function<void()> printFirst) {
        printFirst();
        sem_post(&job1Done);
    }

    void secondJob(function<void()> printSecond) {
        sem_wait(&job1Done);
        printSecond();
        sem_post(&job2Done);
    }

    void thirdJob(function<void()> printThird) {
        sem_wait(&job2Done);
        printThird();
    }
};

The given C++ code defines a class FooBar that ensures three jobs are executed in a specific sequence using semaphores. This is a typical synchronization problem in concurrent programming. Here's a breakdown of how the implementation works:

  • Initialization: Semaphores job1Done and job2Done are initialized in the constructor of the FooBar class. Both semaphores start at 0, indicating that no jobs have been completed at the initialization stage.

  • Job Execution:

    • firstJob function:
      • Executes printFirst, a function passed as an argument to firstJob.
      • Signals the completion of the first job by incrementing the semaphore job1Done using sem_post.
    • secondJob function:
      • Waits for the job1Done semaphore using sem_wait, ensuring that the first job has been completed before proceeding.
      • Executes printSecond after the first job is completed.
      • Signals the completion of the second job by incrementing the semaphore job2Done.
    • thirdJob function:
      • Waits for the job2Done semaphore, ensuring that the second job has been completed.
      • Executes printThird after the second job is completed.

This structured synchronization via semaphores is critical in scenarios involving dependent tasks in multithreaded environments, ensuring tasks are performed in the correct order despite potential race conditions.

java 
class SequenceController {

  private AtomicInteger taskOneComplete = new AtomicInteger(0);
  private AtomicInteger taskTwoComplete = new AtomicInteger(0);

  public SequenceController() {}

  public void first(Runnable printFirst) throws InterruptedException {
    printFirst.run();
    taskOneComplete.incrementAndGet();
  }

  public void second(Runnable printSecond) throws InterruptedException {
    while (taskOneComplete.get() != 1) {
      // Ensure first task is complete
    }
    printSecond.run();
    taskTwoComplete.incrementAndGet();
  }

  public void third(Runnable printThird) throws InterruptedException {
    while (taskTwoComplete.get() != 1) {
      // Ensure second task is complete
    }
    printThird.run();
  }
}

The Java solution provided manages the execution of tasks in a specific sequence using a class named SequenceController. This class effectively coordinates three tasks to be executed in the order first, second, and third despite potential concurrent execution attempts. Here's how the implementation achieves this:

  • The class utilizes AtomicInteger variables (taskOneComplete and taskTwoComplete) to monitor the completion status of the first two tasks. These are thread-safe variables ideal for counting and status flagging in a multi-threading environment.

  • Inside the first method, the corresponding task is executed by calling printFirst.run(). Post execution, it increments taskOneComplete to signal that the first task has concluded.

  • The second method actively waits (busy waiting) until the first task is fully complete, signified by taskOneComplete being set to 1. Once this condition is satisfied, it proceeds to run printSecond.run() and subsequently increments taskTwoComplete.

  • Similarly, the third method pauses execution until the second task completes, checked by continuously monitoring taskTwoComplete until it equals 1. Then, it executes printThird.run().

By utilizing atomic operations and busy waiting, this implementation ensures that the three tasks execute strictly in the specified sequence without using advanced synchronization features like locks or condition variables. This solution provides an effective mechanism to control the execution order that is critical in certain concurrent programming scenarios.

Comments

No comments yet.