Print Zero Even Odd

medium concurrency semaphore threads

Problem

Three threads share one instance. A zero thread only prints 0, an even thread only prints even numbers, and an odd thread only prints odd numbers. They must cooperate so the output is the interleaved series 0102030405… up to n: a 0, then a number, then a 0, then a number, and so on. The threads run concurrently, so you must use synchronization (here, semaphores) to enforce the order regardless of scheduling.

Inputn = 5

Output"0102030405"

A 0 always precedes each value; odd/even values come from their own thread. For n = 2 the output is "0102".

from threading import Semaphore

class ZeroEvenOdd:
    def __init__(self, n):
        self.n = n
        self.gate_zero = Semaphore(1)   # zero starts ready
        self.gate_odd = Semaphore(0)
        self.gate_even = Semaphore(0)

    def zero(self, printNumber):
        for i in range(1, self.n + 1):
            self.gate_zero.acquire()
            printNumber(0)
            (self.gate_odd if i % 2 else self.gate_even).release()

    def even(self, printNumber):
        for i in range(2, self.n + 1, 2):
            self.gate_even.acquire()
            printNumber(i)
            self.gate_zero.release()

    def odd(self, printNumber):
        for i in range(1, self.n + 1, 2):
            self.gate_odd.acquire()
            printNumber(i)
            self.gate_zero.release()

class ZeroEvenOdd {
  constructor(n) {
    this.n = n;
    this.gateZero = lock(1);   // released = ready
    this.gateOdd = lock(0);
    this.gateEven = lock(0);
  }
  async zero(printNumber) {
    for (let i = 1; i <= this.n; i++) {
      await this.gateZero.acquire();
      printNumber(0);
      (i % 2 ? this.gateOdd : this.gateEven).release();
    }
  }
  async even(printNumber) {
    for (let i = 2; i <= this.n; i += 2) {
      await this.gateEven.acquire();
      printNumber(i);
      this.gateZero.release();
    }
  }
  async odd(printNumber) {
    for (let i = 1; i <= this.n; i += 2) {
      await this.gateOdd.acquire();
      printNumber(i);
      this.gateZero.release();
    }
  }
}

import java.util.concurrent.Semaphore;
import java.util.function.IntConsumer;

class ZeroEvenOdd {
    private int n;
    private Semaphore gateZero = new Semaphore(1);
    private Semaphore gateOdd = new Semaphore(0);
    private Semaphore gateEven = new Semaphore(0);

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

    public void zero(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i++) {
            gateZero.acquire();
            printNumber.accept(0);
            (i % 2 == 1 ? gateOdd : gateEven).release();
        }
    }
    public void even(IntConsumer printNumber) throws InterruptedException {
        for (int i = 2; i <= n; i += 2) {
            gateEven.acquire();
            printNumber.accept(i);
            gateZero.release();
        }
    }
    public void odd(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i += 2) {
            gateOdd.acquire();
            printNumber.accept(i);
            gateZero.release();
        }
    }
}

#include <semaphore.h>
#include <functional>

class ZeroEvenOdd {
    int n;
    sem_t gateZero, gateOdd, gateEven;
public:
    ZeroEvenOdd(int n) : n(n) {
        sem_init(&gateZero, 0, 1);
        sem_init(&gateOdd, 0, 0);
        sem_init(&gateEven, 0, 0);
    }
    void zero(function<void(int)> printNumber) {
        for (int i = 1; i <= n; i++) {
            sem_wait(&gateZero);
            printNumber(0);
            sem_post(i % 2 ? &gateOdd : &gateEven);
        }
    }
    void even(function<void(int)> printNumber) {
        for (int i = 2; i <= n; i += 2) {
            sem_wait(&gateEven);
            printNumber(i);
            sem_post(&gateZero);
        }
    }
    void odd(function<void(int)> printNumber) {
        for (int i = 1; i <= n; i += 2) {
            sem_wait(&gateOdd);
            printNumber(i);
            sem_post(&gateZero);
        }
    }
};

Explanation

Three threads must take strict turns to produce 0102030405…: a 0, then a number, then a 0, and so on. We coordinate them with three semaphores, where each acts as a turn token that exactly one thread holds at a time.

gate_zero starts at 1 so the zero thread goes first; gate_odd and gate_even start at 0 so those threads wait. After zero prints a 0, it looks at the loop counter i and releases either the odd or even gate depending on whether i is odd or even, choosing who prints the next number.

The odd and even threads each block on their own gate, print their value when woken, and then release(gate_zero) so the zero thread can emit the next 0. This keeps the strict zero, value, zero, value rhythm.

Example with n = 5: zero prints 0 and (since i=1 is odd) wakes odd, which prints 1 and hands back to zero; zero prints 0 and (i=2) wakes even, which prints 2; continuing gives "0102030405".

Each of the n numbers takes a constant number of hand-offs, so it is O(n) time using three fixed semaphores, O(1) space.

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