Print FooBar Alternately

medium concurrency semaphore threads

Problem

Two threads share one FooBar instance. One thread calls foo() n times, the other calls bar() n times. Each call to foo() prints "foo" and each call to bar() prints "bar". Coordinate the threads so the combined output is "foobar" repeated n times — never "barfoo" and never two of the same in a row.

Inputn = 2

Output"foobarfoobar"

foo must always run just before its matching bar, and the next foo must wait until that bar finishes.

n (rounds)

from threading import Semaphore

class FooBar:
    def __init__(self, n):
        self.n = n
        self.fooReady = Semaphore(1)   # foo may go first
        self.barReady = Semaphore(0)   # bar waits

    def foo(self, printFoo):
        for _ in range(self.n):
            self.fooReady.acquire()
            printFoo()
            self.barReady.release()

    def bar(self, printBar):
        for _ in range(self.n):
            self.barReady.acquire()
            printBar()
            self.fooReady.release()

class FooBar {
  constructor(n) {
    this.n = n;
    this.fooReady = Promise.resolve();   // foo may go first
    this.releaseBar = null;
    this.barReady = new Promise(r => (this.releaseBar = r));
  }
  async foo(printFoo) {
    for (let i = 0; i < this.n; i++) {
      await this.fooReady;
      printFoo();
      this.releaseBar();                 // wake bar
      this.barReady = new Promise(r => (this.releaseBar = r));
    }
  }
  async bar(printBar) {
    for (let i = 0; i < this.n; i++) {
      await this.barReady;
      printBar();
    }
  }
}

import java.util.concurrent.Semaphore;

class FooBar {
    private int n;
    private Semaphore fooReady = new Semaphore(1); // foo may go first
    private Semaphore barReady = new Semaphore(0); // bar waits

    public FooBar(int n) { this.n = n; }

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            fooReady.acquire();
            printFoo.run();
            barReady.release();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            barReady.acquire();
            printBar.run();
            fooReady.release();
        }
    }
}

#include <semaphore.h>

class FooBar {
    int n;
    sem_t fooReady, barReady;
public:
    FooBar(int n) : n(n) {
        sem_init(&fooReady, 0, 1);   // foo may go first
        sem_init(&barReady, 0, 0);   // bar waits
    }
    void foo(function<void()> printFoo) {
        for (int i = 0; i < n; i++) {
            sem_wait(&fooReady);
            printFoo();
            sem_post(&barReady);
        }
    }
    void bar(function<void()> printBar) {
        for (int i = 0; i < n; i++) {
            sem_wait(&barReady);
            printBar();
            sem_post(&fooReady);
        }
    }
};

Explanation

Two threads run at the same time, so without coordination they could print in any order. The fix is to make them hand control back and forth using a pair of semaphores that act like permission tokens.

We create fooReady starting at 1 (foo is allowed to go first) and barReady starting at 0 (bar must wait). A semaphore's acquire() blocks until the count is positive then decrements it; release() increments it, possibly waking a waiting thread.

Each round, the foo thread acquire()s fooReady, prints "foo", then release()s barReady — handing the turn to bar. The bar thread, which was blocked on barReady, now wakes, prints "bar", and release()s fooReady so the next foo can proceed. The two are forced to alternate.

Example with n = 2: foo prints "foo" and signals bar; bar prints "bar" and signals foo; this repeats once more, producing exactly "foobarfoobar" — never "barfoo" and never two of the same in a row.

There are 2n hand-offs total, so the work is O(n) with only two fixed semaphores, i.e. O(1) extra space.

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