LeetCode-1195. Alternate print string (multi thread)

LeetCode Title Description

Write a program that can output a string representing this number from 1 to n, but:

  • If the number can be divided by three, output "fizz".
  • If the number can be divided by 5, output "buzz".
  • If the number can be divided by 3 and 5 at the same time, output "fizzbuzz".

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

Suppose there is a class:

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
}

Please implement a multi-threaded version of FizzBuzz with four threads. The same FizzBuzz instance will be used by the following four threads:

  • Thread A will call fizz() to determine whether it can be divided by 3. If it can, it will output fizz.
  • Thread B will call buzz() to determine whether it can be divided by 5. If it can, it will output buzz.
  • Thread C will call fizzbuzz() to determine whether it can be divided by 3 and 5 at the same time. If it can, it will output fizzbuzz.
  • Thread D will call number() to implement a number whose output cannot be divisible by either 3 or 5.

Source: LeetCode
Link: https://leetcode-cn.com/problems/fizz-buzz-multithreaded
Copyright belongs to the network. For commercial reprint, please contact the official authorization. For non-commercial reprint, please indicate the source.

Title Solution

The overall thinking is as follows:
Concurrent execution of 4 threads

① . the thread printing the number controls the execution of the other 3 threads. After the execution of the method printing the number of digital thread, the corresponding thread is waked up by judging the number division. But here we consider whether there is such a situation. The number method wakes up the fizz method. After the fizz method is executed, it can directly execute the buzz method. If we use the number method to transition, there will be redundant operations. (refer to Solution1)
② . each thread judges the integer division to wake up the corresponding thread. (it is more complicated to judge when releasing all permits when the program is finally considered to be stopped)
③ . use a single semaphore + for loop polling to judge. If the conditions are met, execute it. If the conditions are not met, release the permission and let other methods judge. (refer to Solution2, implementation considerations - if a method takes a long time, performance issues)

Solution1.Semaphore + integer variable

class FizzBuzz {
    private int n;

    Semaphore fizzSem = new Semaphore(0);
    Semaphore buzzSem = new Semaphore(0);
    Semaphore fizzBuzzSem = new Semaphore(0);
    Semaphore numSem = new Semaphore(1);

    private int i;

    public FizzBuzz(int n) {
        //Starting from 1
        this.i = 1;
        this.n = n;
    }

    // printFizz.run() outputs "fizz".
    public void fizz(Runnable printFizz) throws InterruptedException {
        while (true) {
            fizzSem.acquire();
            if (i > n) {
                break;
            }
            printFizz.run();
            i++;
            numSem.release();
        }
    }

    // printBuzz.run() outputs "buzz".
    public void buzz(Runnable printBuzz) throws InterruptedException {
        while (true) {
            buzzSem.acquire();
            if (i > n) {
                break;
            }
            printBuzz.run();
            i++;
            numSem.release();
        }
    }

    // printFizzBuzz.run() outputs "fizzbuzz".
    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        while (true) {
            fizzBuzzSem.acquire();
            if (i > n) {
                break;
            }
            printFizzBuzz.run();
            i++;
            numSem.release();
        }
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void number(IntConsumer printNumber) throws InterruptedException {
        ///It's mainly because the others are waiting after the execution here, so it will time out. At this time, just release all of them.
        while (i <= n) {
            numSem.acquire();
            if (i % 3 == 0 && i % 5 == 0) {
                fizzBuzzSem.release();
            } else if (i % 3 == 0) {
                fizzSem.release();
            } else if (i % 5 == 0) {
                buzzSem.release();
            } else {
                if (i <= n) {
                    printNumber.accept(i);
                }
                i++;
                numSem.release();
            }
        }
        release(); // Final release permit
    }

    private void release() {
        fizzBuzzSem.release();
        buzzSem.release();
        fizzSem.release();
    }
}

Solution2.Semaphore + for round robin judgment

class FizzBuzz {
    private Semaphore semaphore = new Semaphore(1);
    private int curNum = 1;
    private int n;

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

    // printFizz.run() outputs "fizz".
    public void fizz(Runnable printFizz) throws InterruptedException {
        for (; ; ) {
            this.semaphore.acquire(1);
            try {
                if (this.curNum > n) {
                    return;
                }

                if ((this.curNum % 3 == 0) && (this.curNum % 5 != 0)) {
                    printFizz.run();
                    this.curNum++;
                }
            } finally {
                // Release the permit anyway.
                this.semaphore.release(1);
            }
        }
    }

    // printBuzz.run() outputs "buzz".
    public void buzz(Runnable printBuzz) throws InterruptedException {
        for (; ; ) {
            this.semaphore.acquire(1);
            try {
                if (this.curNum > n) {
                    return;
                }

                if ((this.curNum % 3 != 0) && (this.curNum % 5 == 0)) {
                    printBuzz.run();
                    this.curNum++;
                }
            } finally {
                this.semaphore.release(1);
            }
        }
    }

    // printFizzBuzz.run() outputs "fizzbuzz".
    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        for (; ; ) {
            this.semaphore.acquire(1);
            try {
                if (this.curNum > n) {
                    return;
                }

                if ((this.curNum % 3 == 0) && (this.curNum % 5 == 0)) {
                    printFizzBuzz.run();
                    this.curNum++;
                }
            } finally {
                this.semaphore.release(1);
            }
        }
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void number(IntConsumer printNumber) throws InterruptedException {
        for (; ; ) {
            this.semaphore.acquire(1);

            try {
                if (this.curNum > n) {
                    return;
                }

                if ((this.curNum % 3 != 0) && (this.curNum % 5 != 0)) {
                    printNumber.accept(this.curNum);
                    this.curNum++;
                }
            } finally {
                this.semaphore.release(1);
            }
        }
    }
}

Reference resources

250 original articles published, 55 praised, 380000 visitors+
His message board follow

Tags: Java Programming network

Posted on Wed, 05 Feb 2020 21:37:20 -0800 by Mackey18