Print in Order

easy concurrency synchronization locks

Problem

The same instance of a class is given to three different threads. Thread A calls first(), thread B calls second(), and thread C calls third(). Design a mechanism so that second() always runs after first() finishes and third() always runs after second() finishes, regardless of the order in which the threads are scheduled.

Inputnums = [1, 2, 3]

Output"firstsecondthird"

nums describes the order the threads are scheduled (here C, A, B for example). Whatever the schedule, the printed output is always "firstsecondthird".

thread schedule (permutation of 1,2,3)

from threading import Lock

class Foo:
    def __init__(self):
        self.gate2 = Lock(); self.gate2.acquire()
        self.gate3 = Lock(); self.gate3.acquire()

    def first(self, printFirst):
        printFirst()
        self.gate2.release()

    def second(self, printSecond):
        self.gate2.acquire()
        printSecond()
        self.gate3.release()

    def third(self, printThird):
        self.gate3.acquire()
        printThird()

class Foo {
  constructor() {
    this.r2 = null; this.r3 = null;
    this.g2 = new Promise(r => this.r2 = r);
    this.g3 = new Promise(r => this.r3 = r);
  }
  async first(printFirst) {
    printFirst();
    this.r2();
  }
  async second(printSecond) {
    await this.g2;
    printSecond();
    this.r3();
  }
  async third(printThird) {
    await this.g3;
    printThird();
  }
}

import java.util.concurrent.Semaphore;

class Foo {
    private Semaphore gate2 = new Semaphore(0);
    private Semaphore gate3 = new Semaphore(0);

    public void first(Runnable printFirst) throws InterruptedException {
        printFirst.run();
        gate2.release();
    }
    public void second(Runnable printSecond) throws InterruptedException {
        gate2.acquire();
        printSecond.run();
        gate3.release();
    }
    public void third(Runnable printThird) throws InterruptedException {
        gate3.acquire();
        printThird.run();
    }
}

#include <semaphore.h>

class Foo {
    sem_t gate2, gate3;
public:
    Foo() { sem_init(&gate2, 0, 0); sem_init(&gate3, 0, 0); }
    void first(function<void()> printFirst) {
        printFirst();
        sem_post(&gate2);
    }
    void second(function<void()> printSecond) {
        sem_wait(&gate2);
        printSecond();
        sem_post(&gate3);
    }
    void third(function<void()> printThird) {
        sem_wait(&gate3);
        printThird();
    }
};

Explanation

The three methods can be called by their threads in any order, so we need a way to make later steps wait for earlier ones. The idea is two locked "gates" that only open once the previous step has finished.

In the constructor we create gate2 and gate3 and immediately acquire (lock) both, so they start closed. A thread that tries to acquire a closed lock will block until someone releases it.

first() has no gate to wait on, so it prints right away and then release()s gate2. second() begins by acquiring gate2 — which only succeeds after first opened it — then prints and releases gate3. third() waits on gate3, then prints. This chains the order regardless of scheduling.

Example: even if the OS runs the threads as third, first, second, third blocks on the closed gate3 and second blocks on gate2. Only first can run; it opens gate2, letting second run, which opens gate3, letting third run. The output is always "firstsecondthird".

Each method does a constant amount of work, so it is O(1) time and uses just two locks, O(1) space.

Time: O(1) Space: O(1)