from threading import Lock
class FizzBuzz:
def __init__(self, n):
self.n = n
self.current = 1
self.lock = [Lock() for _ in range(4)]
for i in range(1, 4):
self.lock[i].acquire()
def fizz(self, printFizz):
while True:
self.lock[0].acquire()
if self.current > self.n:
self.lock[1].release()
break
if self.current % 3 == 0 and self.current % 5 != 0:
printFizz()
self.current += 1
self.lock[1].release()
def buzz(self, printBuzz):
while True:
self.lock[1].acquire()
if self.current > self.n:
self.lock[2].release()
break
if self.current % 5 == 0 and self.current % 3 != 0:
printBuzz()
self.current += 1
self.lock[2].release()
def fizzbuzz(self, printFizzBuzz):
while True:
self.lock[2].acquire()
if self.current > self.n:
self.lock[3].release()
break
if self.current % 15 == 0:
printFizzBuzz()
self.current += 1
self.lock[3].release()
def number(self, printNumber):
while True:
self.lock[3].acquire()
if self.current > self.n:
self.lock[0].release()
break
if self.current % 3 != 0 and self.current % 5 != 0:
printNumber(self.current)
self.current += 1
self.lock[0].release()
#include <functional>
#include <mutex>
#include <condition_variable>
class FizzBuzz {
private:
int n;
int current;
std::mutex mtx;
std::condition_variable cv;
public:
FizzBuzz(int n) {
this->n = n;
current = 1;
}
void fizz(std::function<void()> printFizz) {
while (true) {
std::unique_lock<std::mutex> lock(mtx);
cv.wait(lock, [&]{ return (current > n) || (current % 3 == 0 && current % 5 != 0); });
if (current > n) break;
printFizz();
++current;
cv.notify_all();
}
}
void buzz(std::function<void()> printBuzz) {
while (true) {
std::unique_lock<std::mutex> lock(mtx);
cv.wait(lock, [&]{ return (current > n) || (current % 5 == 0 && current % 3 != 0); });
if (current > n) break;
printBuzz();
++current;
cv.notify_all();
}
}
void fizzbuzz(std::function<void()> printFizzBuzz) {
while (true) {
std::unique_lock<std::mutex> lock(mtx);
cv.wait(lock, [&]{ return (current > n) || (current % 15 == 0); });
if (current > n) break;
printFizzBuzz();
++current;
cv.notify_all();
}
}
void number(std::function<void(int)> printNumber) {
while (true) {
std::unique_lock<std::mutex> lock(mtx);
cv.wait(lock, [&]{ return (current > n) || (current % 3 != 0 && current % 5 != 0); });
if (current > n) break;
printNumber(current);
++current;
cv.notify_all();
}
}
};
import java.util.concurrent.Semaphore;
class FizzBuzz {
private int n;
private int current = 1;
private Semaphore fizz = new Semaphore(0);
private Semaphore buzz = new Semaphore(0);
private Semaphore fizzbuzz = new Semaphore(0);
private Semaphore number = new Semaphore(1);
public FizzBuzz(int n) {
this.n = n;
}
public void fizz(Runnable printFizz) throws InterruptedException {
while (true) {
fizz.acquire();
if (current > n) {
buzz.release();
return;
}
printFizz.run();
current++;
buzz.release();
}
}
public void buzz(Runnable printBuzz) throws InterruptedException {
while (true) {
buzz.acquire();
if (current > n) {
fizzbuzz.release();
return;
}
printBuzz.run();
current++;
fizzbuzz.release();
}
}
public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
while (true) {
fizzbuzz.acquire();
if (current > n) {
number.release();
return;
}
printFizzBuzz.run();
current++;
number.release();
}
}
public void number(IntConsumer printNumber) throws InterruptedException {
while (true) {
number.acquire();
if (current > n) {
fizz.release();
return;
}
if (current % 3 != 0 && current % 5 != 0) {
printNumber.accept(current);
current++;
}
fizz.release();
}
}
}
class FizzBuzz {
constructor(n) {
this.n = n;
this.current = 1;
this.lock = [Promise.resolve(), null, null, null];
this.resolvers = [];
for (let i = 1; i < 4; ++i) {
this.lock[i] = new Promise(resolve => this.resolvers[i] = resolve);
}
this.resolvers[0] = () => {};
}
async fizz(printFizz) {
while (true) {
await this.lock[0];
if (this.current > this.n) {
this.resolvers[1]();
return;
}
if (this.current % 3 === 0 && this.current % 5 !== 0) {
printFizz();
this.current++;
}
this.lock[0] = new Promise(resolve => this.resolvers[0] = resolve);
this.resolvers[1]();
}
}
async buzz(printBuzz) {
while (true) {
await this.lock[1];
if (this.current > this.n) {
this.resolvers[2]();
return;
}
if (this.current % 5 === 0 && this.current % 3 !== 0) {
printBuzz();
this.current++;
}
this.lock[1] = new Promise(resolve => this.resolvers[1] = resolve);
this.resolvers[2]();
}
}
async fizzbuzz(printFizzBuzz) {
while (true) {
await this.lock[2];
if (this.current > this.n) {
this.resolvers[3]();
return;
}
if (this.current % 15 === 0) {
printFizzBuzz();
this.current++;
}
this.lock[2] = new Promise(resolve => this.resolvers[2] = resolve);
this.resolvers[3]();
}
}
async number(printNumber) {
while (true) {
await this.lock[3];
if (this.current > this.n) {
this.resolvers[0]();
return;
}
if (this.current % 3 !== 0 && this.current % 5 !== 0) {
printNumber(this.current);
this.current++;
}
this.lock[3] = new Promise(resolve => this.resolvers[3] = resolve);
this.resolvers[0]();
}
}
}
The "Fizz Buzz Multithreaded" problem is a concurrency challenge based on the classic Fizz Buzz game. Given an integer n, you must print numbers from 1 to n. For each number:
"fizz"."buzz"."fizzbuzz".
However, you must implement this logic using four threads, each responsible for one of the above actions. The threads must work together such that the output order is correct, with each output printed exactly once in sequence from 1 to n.
Key constraints:
n must be handled by exactly one thread.At first glance, the Fizz Buzz logic is simple in a single-threaded context. But with multithreading, the challenge is to ensure that:
Therefore, we need to coordinate the threads so only the correct one prints at each step. This requires synchronization primitives like locks, semaphores, or condition variables to control which thread is allowed to print for a given number.
The key insight is to have a shared counter and use synchronization so that only the thread responsible for the current number is allowed to print. After printing, the counter advances, and the next appropriate thread takes over.
To solve this problem, we use synchronization mechanisms to ensure only the correct thread prints at each step. The general approach is:
current) that represents the number to be processed.
fizz thread: prints "fizz" for numbers divisible by 3 but not 5.buzz thread: prints "buzz" for numbers divisible by 5 but not 3.fizzbuzz thread: prints "fizzbuzz" for numbers divisible by both 3 and 5.number thread: prints the number itself if not divisible by 3 or 5.n.This approach ensures that outputs are in order, no number is missed or printed twice, and threads do not compete for the same number.
Suppose n = 5. The expected output is:
number thread prints 1, increments current to 2.number thread prints 2, increments current to 3.fizz thread prints "fizz", increments current to 4.number thread prints 4, increments current to 5.buzz thread prints "buzz", increments current to 6.Each thread only prints when it is responsible for the current number, and the output is in the correct order.
Brute-force approach: If each thread loops over all numbers and checks if it should print, there would be O(n) iterations per thread, leading to wasted CPU cycles and potential race conditions.
Optimized synchronized approach:
O(n), since each number from 1 to n is processed exactly once, and only one thread prints per number.O(1), aside from synchronization primitives and the shared counter, no extra space is required.Synchronization overhead is minimal and does not affect the overall asymptotic complexity.
The Fizz Buzz Multithreaded problem demonstrates how to coordinate multiple threads to produce ordered output without conflicts. The key is to use synchronization primitives to control which thread is allowed to print at each step, based on shared state. This ensures correctness, order, and efficiency. The solution is elegant because it divides responsibility among threads and uses simple synchronization to achieve a complex coordination task.