Multithread Binary Semaphore's: Alternating Outputs

Question

1. The goal is to have String of output's consisting of W's, X's ,y's
   and z's.
2. W and X should alternate and W must always be ahead of X. y and z must alternate with y always ahead of z.
3. The total of y's and z's must be less than the number of W's at any given point in the output.

My program so far satisfies the first two points but I'm having trouble with the last one. Also, I very new to semaphore's and want to know if the code I've implemented follows good practices. For example, I had originally set the initial value of my binary semaphores to 0,1,2,3 but changed it to 0,1,0,1 in order to satisfy the second condition.

public class BinarySemaphore extends Semaphore{

    public BinarySemaphore(int initial) {
        value = (initial>0) ? 1 : 0;
    }

    public synchronized void P() throws InterruptedException {
        while (value==0) {
            wait();
        }
        value = 0;
    }

    public synchronized void V() {
        value = 1;
        notify();
    }
}

public class ProcessW extends App implements Runnable{
    public void run() {
        while (true) {
            try {
                Thread.sleep(1 + (int) (Math.random() * 500));
                bsX.P();
            } catch (InterruptedException e1) {
                e1.printStackTrace();
            }
            System.out.print("W");
            bsW.V();
        }
    }
}

public class ProcessX extends App implements Runnable{
    public void run() {
        while (true) {
            try {
                Thread.sleep(1 + (int) (Math.random() * 500));
                bsW.P();
            } catch (InterruptedException e1) {
                e1.printStackTrace();
            }
            System.out.print("X");
            bsX.V();
        }
    }
}

public class ProcessY extends App implements Runnable{
    public void run() {
        while (true) {
            try {
                Thread.sleep(1 + (int) (Math.random() * 800));
                bsZ.P();
            } catch (InterruptedException e1) {
                e1.printStackTrace();
            }
            System.out.print("y");
            bsY.V();
        }
    }
}

public class ProcessZ extends App implements Runnable{
    public void run() {
        while (true) {
            try {
                Thread.sleep(1 + (int) (Math.random() * 800));
                bsY.P();
            } catch (InterruptedException e1) {
                e1.printStackTrace();
            }
            System.out.print("z");
            bsZ.V();
        }
    }
}

public class App {
    protected static final BinarySemaphore bsW = new BinarySemaphore(
            0);
    protected static final BinarySemaphore bsX = new BinarySemaphore(
            1);

    protected static final BinarySemaphore bsY = new BinarySemaphore(
            0);

    protected static final BinarySemaphore bsZ = new BinarySemaphore(
            1);

    public static void main(String[] args) throws Exception {
        Thread W = new Thread(new ProcessW());
        Thread X = new Thread(new ProcessX());
        Thread Y = new Thread(new ProcessY());
        Thread Z = new Thread(new ProcessZ());
        W.start();
        X.start();
        Y.start();
        Z.start();
        Thread.sleep(3000);
        System.out.println("");
        System.exit(0);
    }
}

Here is an example of what my program is currently outputting: WXWyzXWXWXyzyWXWXzyzWXyzWXyzWX

Answer 1

0. Your goal is not defined very well because you didn't write what means are you required to use to achieve the goal. For instance, a program that always prints "WXyzWX" satisfies your question. But I'll assume you specifically want to use four threads each printing its own letter, and you want to use Semaphores for this.

1. Semaphores are used to manage a number of "permissions" between different threads. A thread can semaphore.acquire() a permission and semaphore.release() it after doing its job. If no permissions are available at the moment of calling acquire(), the thread waits until some other thread releases a permission. See documentation for details.

   You can use Semaphores for your purpose, but before that I have to explain what "fairness" means in terms of multithreading. By default, the Semaphore (and all other Java concurrent stuff) is "unfair". This means that when a permission is released, it will be given to any of the threads that are waiting for one, considering the overall performance first. On the other hand, a "fair" Semaphore will always give a newly available permission to the thread that has been waiting for one for the longest time. This practically orders the threads as if in a queue. In general, fair structures work slower, but in our case this fairness is very useful.

   Now to the idea. You can think of your letter ordering in a following way: to write X, a thread needs a permission that will only be available to it after another thread writes W, and then to write W you will need a permission from X thread. So you can use a semaphore for these two threads, with each thread acquiring and releasing a permission from the semaphore before and after printing the letter. And its fairness guarantees that W and X will always be alternating (don't forget that by default semaphores are unfair, you have to specify a flag in its constructor in order to make it fair). You should also make sure which thread acquires the permission first, or else you will get X always ahead of W.

   You can make a similar trick to alternate y and z, but now you have to guarantee your third condition. This is also doable using a semaphore: to write a y or a z, you need a permission that can only be acquired after some W-s were written. I'm going to make you think this one through by yourself. Maybe a nice idea would be to randomly decide whether to release a permission or not, but no details here :)

   I must mention that this is by far not the only way to accomplish your task, and also semaphores may be not the best tool to use in here. (I don't think a specific best one exists though.)

And now some extra comments on your code:

2. What exactly is your purpose of extending the java Semaphore? You never use any of its methods. You can just delete that 'extends' if you want to use this code.

3. To generate a random value from 0 to N, there is a nextInt(N) method in java.util.Random class. It suits your purposes better.

4. InterruptedException is one of the few ones that can be safely ignored most of the times (unless you know what it means and want to use it). I mention it because in case it is thrown, your output is going to be mixed up with letters and exceptions.

5. You simply create a thread, start it and then never access it. In this case, you can simplify your lines to new Thread(new ProcessW()).start() without even creating a variable.

6. P() and V() are terrible names for methods - I can barely understand what they are supposed to do.

7. What is the purpose of your BinarySemaphore fields in App class being protected? Did you mean private?

8. You're stopping all of your threads by calling System.exit(0). This way you cannot make a difference which threads to stop and which not to, as well as being unable to do anything after stopping the threads. A simple solution would be to create a volatile boolean isRunning = true; visible to all threads (do you know what volatile is?), replace while(true) to while(isRunning) and instead of calling System.exit() just do isRunning = false. Or else use the interruption mechanism (again, if you know what it is).