How to use semaphores correctly

Question

I've been posed a problem along the lines of Santa's workshop where numerous things have to happen before presents can be delivered. One such requirement is that eleven elves successfully manufacture 100 presents. My main class looks like this:

public class Main {

    public volatile int toyList = 100;

    public int getToyList() {
        return toyList;
    }

    public void setToyList(int toyList) {
        this.toyList = toyList;
    }

    public static void main(String[] args){
        Main main = new Main();

        ...

        Elf elfOne = new Elf("Jim", main);
        Elf elfTwo = new Elf("John", main);
        Elf elfThree = new Elf("Eamonn", main);
        Elf elfFour = new Elf("Eoin", main);
        Elf elfFive = new Elf("Ronan", main);
        Elf elfSix = new Elf("Seamus", main);
        Elf elfSeven = new Elf("Rebecca", main);
        Elf elfEight = new Elf("Orla", main);
        Elf elfNine = new Elf("Tina", main);
        Elf elfTen = new Elf("Filly", main);
        Elf elfEleven = new Elf("Jess", main);


        ...

        elfOne.start();
        elfTwo.start();
        elfThree.start();
        elfFour.start();
        elfFive.start();
        elfSix.start();
        elfSeven.start();
        elfEight.start();
        elfNine.start();
        elfTen.start();
        elfEleven.start();

    }

and my Elf class looks like this:

public class Elf extends Thread{

    Semaphore semaphore = new Semaphore(11);
    Random rng = new Random();
    String name;
    Main main;

    public Elf(String name, Main main){
        this.name = name;
        this.main = main;
    }

    public void run(){
        while(true){
                try {
                    semaphore.acquire();
                    makeToy();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    semaphore.release();
                }
        }
    }

    private void makeToy() throws InterruptedException{
        if (main.getToyList() != 0){
            if(rng.nextInt(99) <= 4){ //5% chance to fail
                System.out.println(name + " failed in making a toy!");
            }else{
                main.setToyList(main.getToyList() - 1);
                System.out.println(name + " created a toy! Toys remaining: " + main.getToyList());
            }
        } else {
            wakeSanta();
        }
    }

    private void wakeSanta() throws InterruptedException {

    }

}

A sample output I get is:

...
Eamonn created a toy! Toys remaining: 6
Jim created a toy! Toys remaining: 7
Eoin created a toy! Toys remaining: 8
Jess created a toy! Toys remaining: 9
Filly created a toy! Toys remaining: 0

The output I'd like to get is that it counts down sequentially with a random Elf from 100 to 0. Is it something as simple as my semaphore acquisition being in the wrong place or am I misunderstanding semaphores altogether?

Kulu Limpa · Accepted Answer

Yes, your semaphore is not used correctly. A semaphore instance can grant a number of permissions.

A thread can acquire() a permission - block until a permission is available and then decrease the number of available permissions.
A thread can release() a permission - increase the number of available permissions.

In your code, each thread has its own semaphore with 11 permissions. Firstly, being a means of synchronization, semaphores usually only make sense if they are shared by multiple threads. Secondly, if you want to make a resource (in your case toyList) fully mutially exclusive, the semaphore should only provide a single permission.

Think of it this way: In order to make toys, the elves need to use a machine. Now your scenario requires that only one elve can make a toy at the same time, which is equivalent to the workshop only having one toy-manufactoring machine. So - in code - you need to create the equivalent of a single machine: A single Semaphore-instance with only one permission. Okay, so let us put the Semaphore in the Main-class:

public class Main {

    Semaphore semaphore = new Semaphore(1);
    // the rest of Main is kept the same
}

Now the elves need to get access to the toy-manufactoring machine, so instead of semaphore.acquire(), we use main.semaphore.aquire(). But if the machine is occupied when calling run() and never released, the first elf to start working won't ever let any other elf have the machine. So Santa put down some rules on how the machine is to be used:

The machine must not be occupied unless an elf attempts to make a toy
The machine must be freed once an elf (successfully or not) finished making a toy

So the code of run() and makeToy() changes as follows:

public void run(){
    while(true){ // sidenote: I would rearrange the nesting: Wrap the while-loop in the try-catch
        try {
            makeToy();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

private void makeToy() throws InterruptedException{
    main.semaphore.acquire();
    if (main.getToyList() != 0){
        if(rng.nextInt(99) <= 4){ //5% chance to fail
            System.out.println(name + " failed in making a toy!");
        }else{
            main.setToyList(main.getToyList() - 1);
            System.out.println(name + " created a toy! Toys remaining: " + main.getToyList());
        }
    } else {
        wakeSanta();
    }
    main.semaphore.release();
}

In case you are wondering about when to use a semaphore with multiple permissions, here an example:

Assume you have a resource that is read often and occasionally written. Because reading does not change the value (i.e., mutate the state), it is safe to have multiple threads read the value concurrently. Say we have n threads and a semaphore with n permissions. A thread must now acquire a single permission to read - meaning that all threads can read at the same time, but it must acquire all n permissions to be allowed to write - meaning while one thread is writing, no other thread can access the resource (neither to read nor to write).

Personally, I think of acquiring and releasing a semaphore with a single permission as a synchronized-block. However, note the important difference that user Ralf pointed out in a comment: A semaphore can be released by any thread regardless of which thread has actually acquired the permission. Semaphores are more expressive - with the downside that it is easier to use them wrong.

How to use semaphores correctly

Answers (2)

Related Questions