10
\$\begingroup\$

Recently, I submitted a project that simulates a barbershop-style problem; the task was to create a Hotel that contained guests, front-desk employees, and bellhops. Each of these were to be implemented with their respective Semaphores, with mutual exclusion being kept to a minimum if possible.

My code works as expected, but perhaps I could have used fewer semaphores.

package test;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
import java.util.concurrent.Semaphore;

public class Hotel implements Runnable{ 
    /* Constants */
    public static final int NUMGUESTS = 25;
    public static final int NUMEMPLOYEES = 2;
    public static final int NUMBELLHOP = 2;
    /**************************************/

    /* Semaphores */
    public static Semaphore custReady;
    public static Semaphore custReqHelp;
    public static Semaphore employee;
    public static Semaphore leaveEmployee;
    public static Semaphore bellHop;
    public static Semaphore bagsDelivered;
    public static Semaphore givenRoom;
    public static Semaphore bagsDropped;
    public static Semaphore mutex1;
    public static Semaphore mutex2;
    public static Semaphore mutex3;
    public static Semaphore finished[];
    public static Semaphore inRoom[];
    /**************************************/

    /* Variables */
    public static int       empHelped[];
    public static int       hopHelped[];
    public static int       guestJoins;
    public static Queue<Guest> guestQueue;
    public static Queue<Guest> bagQueue;
    public Thread hotel;
    /**************************************/

    /* Instantiate all semaphores, arrays, and queues that are required */
    public Hotel() {
        custReady     = new Semaphore(0, true);
        custReqHelp   = new Semaphore(0, true);
        leaveEmployee = new Semaphore(0, true);
        bagsDelivered = new Semaphore(0, true);
        bagsDropped   = new Semaphore(0, true);
        mutex1        = new Semaphore(1, true);
        mutex2        = new Semaphore(1, true);
        mutex3        = new Semaphore(1, true);
        givenRoom     = new Semaphore(0, true);
        employee      = new Semaphore(NUMEMPLOYEES, true);
        bellHop       = new Semaphore(NUMBELLHOP, true);
        finished      = new Semaphore[NUMGUESTS];
        inRoom        = new Semaphore[NUMGUESTS];
        guestQueue    = new LinkedList<Guest>();
        bagQueue      = new LinkedList<Guest>(); 

        empHelped     = new int [NUMGUESTS];
        hopHelped     = new int [NUMGUESTS];
        guestJoins    = 0;

        for (int i = 0; i < NUMGUESTS; i++) {
            finished[i]  = new Semaphore(0, true);
            inRoom[i]    = new Semaphore(0, true);
            empHelped[i] = 0;
            hopHelped[i] = 0;
        }

        hotel = new Thread();
    }

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

        /* Create 2 front-desk employees */
        for (int i = 0; i < NUMEMPLOYEES; i++) {
            new Employee(i, hotel);
        }

        /* Create 2 bellhops */
        for (int i = 0; i < NUMBELLHOP; i++) {
            new BellHop(i, hotel);
        }

        /* Create 25 guests */
        for (int i = 0; i < NUMGUESTS; i++) {
            new Guest(i, hotel);
        }

        /* Keep program running while there are guests who are not in rooms */
        while(Hotel.guestJoins < NUMGUESTS) {
            System.out.print("");
        }

        /* Exit successfully */
        System.out.println("Simulation ends");
        System.exit(0);
    }

    public static void joinedGuests() {++Hotel.guestJoins;}

    @Override
    public void run() {}
}

class Guest implements Runnable{
    /* Constants */
    public static final int MAXBAGS = 5;
    public static final int MINBAGS = 0;
    /**************************************/

    /* Variables */
    public Hotel  hotel;
    public int    guestNum;
    public int    numBags;
    public int    roomNum;
    public static int joins = 0;
    public Thread guest;
    /**************************************/

    /* Initializes all of the required variables for the Guest instance */
    public Guest(int num, Hotel hotel) {
        Random random = new Random();
        this.hotel = hotel;
        guestNum = num;
        numBags  = random.nextInt(MAXBAGS - MINBAGS + 1);

        System.out.println("Guest "  + guestNum + " created");
        guest = new Thread(this);
        guest.start();
    }

    /* Runs the thread for the given instance of guest */
    @Override
    public void run() {
        try {
            System.out.println("Guest " + guestNum + " enters the hotel with " + numBags + " bags");

            /* Critical section to add guest to queue for help from employee */
            Hotel.mutex1.acquire();
            Hotel.guestQueue.add(this);
            Hotel.mutex1.release();

            /* Wait for an available employee, then get a unique room from employee */
            Hotel.employee.acquire();
            Hotel.custReady.release();
            Hotel.finished[guestNum].acquire();
            Hotel.givenRoom.acquire();
            System.out.println("Guest " + guestNum + " receives room key for room " + roomNum + " from employee " + Hotel.empHelped[guestNum]);

            /* Indicate that guest is walking away from the front-desk employee */
            Hotel.leaveEmployee.release();


            /* Guests with more than 2 bags require a bellhop */
            if (numBags > 2) {
                /* Guest indicates that they need help with bags and waits for a bellhop */
                Hotel.bellHop.acquire();
                System.out.println("Guest " + guestNum + " requests help with bags");
                Hotel.bagQueue.add(this);
                Hotel.custReqHelp.release();

                /* Guest goes to their assigned room */
                Hotel.bagsDropped.acquire();
                System.out.println("Guest " + guestNum + " enters room " + roomNum);
                Hotel.inRoom[guestNum].release();

                /* Wait for the bellhop to bring bags before going to bed */
                Hotel.bagsDelivered.acquire();
                System.out.println("Guest " + guestNum + " receives bags from bellhop " + Hotel.hopHelped[guestNum]);

            }
            /* Guest had less than 2 bags and immediately goes to room and then retires */
            else {
                Hotel.inRoom[guestNum].release();
                System.out.println("Guest " + guestNum + " enters room " + roomNum);
            }

            /* Guest goes to bed */
            System.out.println("Guest " + guestNum + " retires for the evening");
        }
        catch(Exception e) {
            e.printStackTrace();
        }
        finally {
            /* Attempt to join the thread */
            try {
                Hotel.joinedGuests();
                System.out.println("Guest " + guestNum + " joined");
                guest.join();       
            } 
            catch (InterruptedException e) {e.printStackTrace();}
        }
    }
}

class Employee implements Runnable{
    /* Variables */
    public static int ROOMNUM = -1;
    public int employeeNum;
    public Thread employee;
    /**************************************/

    /* Initializes all of the required variables for the Employee instance */
    public Employee(int num, Hotel hotel) {
        employeeNum = num;
        System.out.println("Employee "  + employeeNum + " created");
        Thread employee = new Thread(this);
        employee.start();
    }

    /* Runs the thread for the given instance of employee */
    @Override
    public void run() {
        try {
            while(true) {
                /* Wait until a customer is ready to be serviced */
                Hotel.custReady.acquire();

                /* Enter critical section to give unique room to unique customer */
                Hotel.mutex2.acquireUninterruptibly();
                Guest guest = Hotel.guestQueue.remove();
                ROOMNUM++;
                guest.roomNum = ROOMNUM;    
                Hotel.mutex2.release();

                /* Let the guest know who helped them and that they are assigned a room */
                Hotel.empHelped[guest.guestNum] = employeeNum;
                Hotel.givenRoom.release();
                System.out.println("Front desk employee " + employeeNum + " registers guest " + guest.guestNum + " and assigns room " + guest.roomNum);

                Hotel.finished[guest.guestNum].release();
                Hotel.leaveEmployee.acquire();
                Hotel.employee.release();
            }
        }
        catch(Exception e) {e.printStackTrace();}
        finally {}
    }
}

class BellHop implements Runnable{

    public Thread bellhop;
    public int bellHopNum;

    /* Initializes all of the required variables for the BellHop instance */
    public BellHop(int num, Hotel hotel) {
        bellHopNum = num;
        System.out.println("Bellhop "  + bellHopNum + " created");
        Thread bellhop = new Thread(this);
        bellhop.start();
    }

    /* Runs the thread for the given instance of bellHop */
    @Override
    public void run() {
        try {
            while (true) {
                /* Wait for a customer to reuqest help with bags, then assign
                 * a unique bellhop to assist them */
                Hotel.custReqHelp.acquire();
                Hotel.mutex3.acquireUninterruptibly();
                Guest guest = Hotel.bagQueue.remove();

                /* Let the guest know what bellhop is helping them with their bags &*/
                Hotel.hopHelped[guest.guestNum] = bellHopNum;
                Hotel.mutex3.release();

                /* Indicate to the guest that the bags have been delivered */
                System.out.println("Bellhop " + bellHopNum + " receives bags from guest " + guest.guestNum);
                Hotel.bagsDropped.release();

                /* Wait for the guest to enter their room before delivering
                 * their bags, then release the bellhop resource */
                Hotel.inRoom[guest.guestNum].acquire();
                System.out.println("Bellhop " + bellHopNum + " delivers bags to guest " + guest.guestNum);
                Hotel.bagsDelivered.release();
                Hotel.bellHop.release();
            }
        }
        catch(Exception e) {e.printStackTrace();}
        finally {}
    }
}
\$\endgroup\$
  • \$\begingroup\$ Just to double-check, when you say: "Each of these were to be implemented with their respective Semaphores", you mean it was a requirement to use semaphores for all concurrency control rather than concurrent collections? \$\endgroup\$ – Ben Aaronson Nov 2 '15 at 14:54
  • 1
    \$\begingroup\$ @BenAaronson yes, we were supposed to figure out what semaphore would be required and create them, we were not allowed to use any built-in concurrency from the Java Collections Library. \$\endgroup\$ – Evan Bechtol Nov 2 '15 at 15:40
5
\$\begingroup\$

You implemented your pieces as Runnable, which is a good first step.

public Guest(int num, Hotel hotel) {
    Random random = new Random();
    this.hotel = hotel;
    guestNum = num;
    numBags  = random.nextInt(MAXBAGS - MINBAGS + 1);

    System.out.println("Guest "  + guestNum + " created");
    guest = new Thread(this);
    guest.start();
}

First - boiler plate code should look like boiler plate code. In the constructor, when you are initializing state from constructor arguments, the name of the variable being set should match the name of the argument, unless there is some compelling reason to do otherwise. So the variable should be named num or guestNum in both places.

Second - that variable should be named guestId -- it's a unique identifier for the guest; num should represent a count of something.

Third - random numbers are hard to test; leave yourself a back door if you can. For instance:

for (int i = 0; i < NUMGUESTS; i++) {
    Random random = new Random();
    int numBags  = random.nextInt(MAXBAGS - MINBAGS + 1);
    new Guest(i, numBags, hotel);
}

Now, in your implementation, MAXBAGS and MINBAGS are scoped to Guest, so maybe those details shouldn't leak out. Consider then a static member function in Guest.

public static int getBagCount(Random random) {
    return random.nextInt(MAXBAGS-MINBAGS + 1)
}

Alternatively, you might implement a Factory to generate bag counts

class LuggageFactory {
    private final int maxBags;
    private final int minBags;

    // ...
    public int getBagCount(Random random) {
        return random.nextInt(maxBags - minBags + 1);
    }
}

Having a single class to test may make it easier to discover the bug when Guest.MINBAGS is not zero.

    guest = new Thread(this);
    guest.start();

This is a bad idea at two levels. First, you shouldn't be doing this kind of work in the constructor. You'd be much better off to put it in the outer loop. Second, unless you have a really compelling reason to do otherwise, you should be submitting the Runnable to an instance of an ExecutorService.

ExecutorService executor = // ...

for (int i = 0; i < NUMGUESTS; i++) {
    Random random = new Random();
    int numBags  = random.nextInt(MAXBAGS - MINBAGS + 1);
    executor.submit(new Guest(i, numBags, hotel));
}

Don't use static member variables where you can use instance member variables instead. You are passing a hotel to each of the actors in your system, so that already gives you a container to track everything. The hint that you should really be doing this is the fact that you were initializing all of the static members in an instance constructor

public Hotel() {
    // These should be members of this Hotel instance, not static
    custReady     = new Semaphore(0, true);
    custReqHelp   = new Semaphore(0, true);
    // ...

Also, you should avoid having one object reach into the internals of another.

        Hotel.mutex1.acquire();
        Hotel.guestQueue.add(this);
        Hotel.mutex1.release();

So this is telling us that there should be a method on hotel to note the arrival of Guests. Something like...

class Hotel  {
    public void add(Guest guest) {
        this.mutex1.acquire();
        this.guestQueue.add(guest);
        this.mutex1.release();
    }

All of the logic for coordinating the Semaphore for the hotel should be encapsulated within methods of the hotel itself.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the great advice and suggestions! I'm working on implementing them now \$\endgroup\$ – Evan Bechtol Nov 3 '15 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.