multithreading Archives - Huahua's Tech Road

Write a program that outputs the string representation of numbers from 1 to n, however:

If the number is divisible by 3, output “fizz”.
If the number is divisible by 5, output “buzz”.
If the number is divisible by both 3 and 5, output “fizzbuzz”.

For example, for n = 15, we output: 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz.

Suppose you are given the following code:

class FizzBuzz {
  public FizzBuzz(int n) { ... }               // constructor
  public void fizz(printFizz) { ... }          // only output "fizz"
  public void buzz(printBuzz) { ... }          // only output "buzz"
  public void fizzbuzz(printFizzBuzz) { ... }  // only output "fizzbuzz"
  public void number(printNumber) { ... }      // only output the numbers
}

Implement a multithreaded version of FizzBuzz with four threads. The same instance of FizzBuzz will be passed to four different threads:

Thread A will call fizz() to check for divisibility of 3 and outputs fizz.
Thread B will call buzz() to check for divisibility of 5 and outputs buzz.
Thread C will call fizzbuzz() to check for divisibility of 3 and 5 and outputs fizzbuzz.
Thread D will call number() which should only output the numbers.

Solution:

4 Semaphores

C++

// Author: Huahua

class Semaphore {

public:

Semaphore (int count = 0): count_(count) {}

inline void notify() {

unique_lock<std::mutex> lock(mtx_);

count_++;

cv_.notify_one();

}

inline void wait() {

unique_lock<std::mutex> lock(mtx_);

while (count_ == 0) cv_.wait(lock);

count_--;

}

private:

mutex mtx_;

condition_variable cv_;

int count_;

};

class FizzBuzz {

private:

int n;

Semaphore sn;

Semaphore s3;

Semaphore s5;

Semaphore s15;

public:

FizzBuzz(int n): n(n), sn(1), s3(0), s5(0), s15(0) {}

void fizz(function<void()> printFizz) {

for (int i = 3; i <= n; i += 3) {

if (i % 5 == 0) continue;

s3.wait();

printFizz();

sn.notify();

}

void buzz(function<void()> printBuzz) {

for (int i = 5; i <= n; i += 5) {

if (i % 3 == 0) continue;

s5.wait();

printBuzz();

sn.notify();

}

void fizzbuzz(function<void()> printFizzBuzz) {

for (int i = 15; i <= n; i += 15) {

s15.wait();

printFizzBuzz();

sn.notify();

}

void number(function<void(int)> printNumber) {

for (int i = 1; i <= n; ++i)

if (i % 15 == 0) { s15.notify(); sn.wait(); }

else if (i % 5 == 0) { s5.notify(); sn.wait(); }

else if (i % 3 == 0) { s3.notify(); sn.wait(); }

else { printNumber(i); }

}

};

Input: [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.

Solution 1: Mutex

C++

// Author: Huahua, 128 ms / 8.2 MB

class Foo {

public:

Foo() {

first_.lock();

second_.lock();

}

void first(function<void()> printFirst) {

// printFirst() outputs "first". Do not change or remove this line.

printFirst();

first_.unlock();

}

void second(function<void()> printSecond) {

first_.lock();

// printSecond() outputs "second". Do not change or remove this line.

printSecond();

first_.unlock();

second_.unlock();

}

void third(function<void()> printThird) {

second_.lock();

// printThird() outputs "third". Do not change or remove this line.

printThird();

second_.unlock();

}

private:

std::mutex first_;

std::mutex second_;

};

Solution 2: Busy waiting

C++

// Author: Huahua, 176 ms / 9.2 MB

#include <unistd.h>

class Foo {

public:

Foo() {}

void first(function<void()> printFirst) {

// printFirst() outputs "first". Do not change or remove this line.

printFirst();

state_ = 1;

}

void second(function<void()> printSecond) {

while (state_ != 1) usleep(1);

// printSecond() outputs "second". Do not change or remove this line.

printSecond();

state_ = 2;

}

void third(function<void()> printThird) {

while (state_ != 2) usleep(1);

// printThird() outputs "third". Do not change or remove this line.

printThird();

state_ = 3;

}

private:

int state_ = 0;

};

Posts tagged as “multithreading”

花花酱 LeetCode 1195. Fizz Buzz Multithreaded

C++

花花酱 LeetCode 1114. Print in Order

Solution 1: Mutex

C++

Solution 2: Busy waiting

C++