Restaurant Management
Imagine there is a restaurant with three tables. Table A serves seafood, table B serves steak, and table C serves pasta. Each table can fit four people. Everyone must choose the table they want to eat at, and stand in its line. Each customer has an idea of which table they want to eat at, and may have a backup choice in case it is too busy. When the customer enters the restaurant through one of its two doors (which fit one person at a time) they look at the lines for the tables they want. If their first choice has a long line (7 or more) they will choose their second choice (if they have one) if it is not also long. Otherwise, they will always choose their first choice. Once their table is chosen, the customers stand in line for that table getting one of the four seats when it is their turn. After the customer sits at the table, they will call the waiter. The waiter will go to the table to take the order, go to the kitchen to deliver the order, and after some time will bring the order back to the table. The customers at the table will then eat, leave the table, pay, and then leave the restaurant.
You should program a single application in c,c++, java, or python. The program will simulate the restaurant using threads for the waiters and customers. If you program in c or c++, use pthreads and POSIX semaphores. If your program in java uses the Thread and Semaphore classes. If you use python, use the threading module, and threading. Semaphore for synchronization.
You should set up the simulation and then launch 3 waiter threads followed by 40 customer threads. At creation, each thread will be given an id that uniquely distinguishes it from other threads of the same type (waiter or customer). You will need some shared variables to exchange information and synchronization. In particular, several semaphores must be used to synchronize the behavior of the threads.
Both the waiter and the customer will have times it will wait. The wait time is given as a range. You should randomly select a time within the range when you reach that step.
The Waiter
1. The waiter chooses a table. Only one waiter can wait at each table.
2. The waiter waits for a customer from his table to call him.
3. Once called, the waiter goes to the customer, and informs the customer he is ready to take the order
4. The waiter gets the customer’s id (represents getting the order)
5. The waiter goes to the kitchen. Only one waiter can use the kitchen at a time. He will spend 100 to 500 milliseconds in the kitchen to deliver the order.
6. The waiter waits outside the kitchen for the order to be ready (this will be between 300 milliseconds to 1 second)
7. The waiter will go to the kitchen to get the order. He will spend 100 to 500 milliseconds in the kitchen.
8. The waiter will bring the customer the order
9. The waiter will wait for the next customer
10. When the last customer leaves the restaurant, the waiter will clean the table, and leave the restaurant.
The Customer
1. The customer chooses a table to eat at
2. The customer may choose a backup table to eat at (randomly decide this)
3. The customer enters the restaurant through one of the two doors. Each door allows one customer to enter at a time.
4. The customer looks at the lines for the chosen tables.
• A line is long if there are 7 or more customers in it. You will need to keep a shared counter.
• If the first choice’s line is long, but the second choice’s line is not, then the customer will go to the second choice table
• Otherwise, the customer will go to the first choice table
• If there is no second choice, the customer will always go to the first choice table
5. Once the table is chosen, the customer will stand in the corresponding line to wait for an empty seat
6. There are four seats. Whenever a seat is empty the next customer in line leaves the line to sit down.
• The seats will start empty. So, the first four customers in line will not need to wait.
7. When the customer sits down, it will call the waiter for this table, and wait.
8. When the waiter comes to take the order, the customer will give the waiter its id (representing giving the order), and wait for the order
9. When the waiter brings the order, the customer will eat the food. This will take 200 milliseconds to 1 second.
10. Afterwards the customer will leave the table. This means the seat has now become empty.
11. The customer will then pay the bill. Only one customer can pay at a time.
12. The customer leaves the restaurant. The client thread will then exit.
Output
Every thread should print out what it is doing as it does it. Each step listed in the above subsections needs a line printed. Each line should contain what type of thread it is (waiter or customer) and its id (within its type). If the action is an interaction with the other type of thread it should also print out that information. As an example, when the waiter takes the customer’s order, your program may print out something like:
Waiter 0 takes Customer 7’s order.
When the customer gives its order to the waiter your program may print out something like:
Customer 7 gives the order to Waiter 0.
The order of the message is only restricted by the order the actions must take place in, given in the previous two subsections. Due to the nature of threads, without using a synchronization mechanism like semaphores, we cannot control the order in which these actions will happen. So, the waiter should not take an order before going to the table, but it is ok if waiter 2 takes customer 30’s order before waiter 0 takes customer 7’s.
Solution:
Main:
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Semaphore;
public class Main {
private static final int NUM_CUSTOMERS = 40;
// Semaphore to protect the number of customers who exited the restaurant
private static Semaphore customerExitSemaphore = new Semaphore(1);
private static int numCustomerExits = 0;
// Semaphore that forced this main class to wait until last customer exits restaurant
private static Semaphore lastCustomerExitSemaphore = new Semaphore(0);
// Add +1 to exit
public static void signalCustomerExit() {
try {
customerExitSemaphore.acquire();
numCustomerExits++;
if (numCustomerExits >= NUM_CUSTOMERS) {
// Signal that the last customer has exited
lastCustomerExitSemaphore.release();
}
customerExitSemaphore.release();
} catch (Exception e) {
e.printStackTrace(System.out);
}
}
// Initialize the threads and start them
public static void main(String[] args) throws Exception {
// There will be 3 tables
List
tables = new ArrayList<>();
tables.add(new Table("A"));
tables.add(new Table("B"));
tables.add(new Table("C"));
// There will be 1 kitchen shared by all waiters
Kitchen kitchen = new Kitchen();
// There will be 3 waiters
List waiters = new ArrayList<>();
waiters.add(new Waiter(1, kitchen));
waiters.add(new Waiter(2, kitchen));
waiters.add(new Waiter(3, kitchen));
// There will be 1 waiter assigned for each table
tables.get(0).setWaiter(waiters.get(0));
tables.get(1).setWaiter(waiters.get(1));
tables.get(2).setWaiter(waiters.get(2));
waiters.get(0).setTable(tables.get(0));
waiters.get(1).setTable(tables.get(1));
waiters.get(2).setTable(tables.get(2));
// There will be 2 doors only in the restaurant for entry of customers
List doors = new ArrayList<>();
doors.add(new Door(1));
doors.add(new Door(2));
// There will be 1 cashier for payment of customers
Cashier cashier = new Cashier();
// There will be 40 customers
List customers = new ArrayList<>();
for (int i = 1; i <= NUM_CUSTOMERS; i++) {
customers.add(new Customer(i, tables, doors, cashier));
}
// Start all waiter and customer threads
for (Waiter waiter : waiters) {
waiter.start();
}
for (Customer customer : customers) {
customer.start();
}
// Wait for the last customer
lastCustomerExitSemaphore.acquire();
// Signal all waiters to to stop waiting
for (Waiter waiter : waiters) {
waiter.signalOrder();
}
}
}
Customer:
import java.util.List;
import java.util.Random;
import java.util.concurrent.Semaphore;
public class Customer extends Thread {
private int customerId;
private List
tables;
private List doors;
private Cashier cashier;
private Semaphore semaphore;
private boolean served;
// Initialize the customer
public Customer(int customerId, List tables, List doors, Cashier cashier) {
this.customerId = customerId;
this.tables = tables;
this.doors = doors;
this.cashier = cashier;
served = false;
// This will make customer wait to be served
semaphore = new Semaphore(0);
}
// Return a string representation
@Override
public String toString() {
return "Customer " + customerId;
}
// Check if customer has been served
public boolean isServed() {
return served;
}
// Mark customer as served
public void setServed(boolean served) {
this.served = served;
}
// Signal the customer to stop waiting
public void signal() {
semaphore.release();
}
// Start customer, choose the best table, wait to get served
// and then pay afterwards
@Override
public void run() {
try {
Random random = new Random();
// Customer enters one of the doors
Door chosenDoor = doors.get(random.nextInt(doors.size()));
chosenDoor.enter(this);
// Look for the best table
Table chosenTable = tables.get(random.nextInt(tables.size()));
System.out.println(this + " initially chooses " + chosenTable);
if (chosenTable.getQueueSize() > 7) {
// If line is long, look for another table that is shorter
for (Table table : tables) {
if (table != chosenTable && table.getQueueSize() < chosenTable.getQueueSize()) {
chosenTable = table;
}
}
System.out.println(this + " chooses " + chosenTable + " as backup because initial table has long queue");
}
// Go to the chosen table, and wait to be served
chosenTable.addCustomer(this);
semaphore.acquire();
// Once food arrives starts eating
System.out.println(this + " is now eating");
Thread.sleep(random.nextInt(1000) + 200);
System.out.println(this + " is finished eating");
// Done eating, then leave the table
chosenTable.removeSeatedCustomer(this);
// Pay for the bill
cashier.acceptPayment(this);
// Customer leaves the restaurant
System.out.println(this + " leaves restaurant");
Main.signalCustomerExit();
} catch (Exception e) {
e.printStackTrace(System.out);
}
}
}
Table:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.Semaphore;
public class Table {
private String name;
// Waiter that will service this table
private Waiter waiter;
// Semaphore to protect the seats and queue
private Semaphore semaphore;
private List
Waiter:
import java.util.Random;
import java.util.concurrent.Semaphore;
public class Waiter extends Thread {
private int waiterId;
private Semaphore semaphore;
private Table table;
private Kitchen kitchen;
// Initialize the waiter
public Waiter(int waiterId, Kitchen kitchen) {
this.waiterId = waiterId;
this.kitchen = kitchen;
semaphore = new Semaphore(0);
}
// Initiaize the waiter's table
public void setTable(Table table) {
this.table = table;
}
// Signal is recieved from a customer that sat on
// the table it is servicing. This means waiter
// has to move and get an order
public void signalOrder() {
semaphore.release();
}
// Entry point of the waiter to execute independently
@Override
public void run() {
try {
while (true) {
// Wait for a customer from the table it is assigned
semaphore.acquire();
// Service the next customer from the table
Customer customer = table.serveNextCustomer();
// If there are no customer to serve next, then stop now
if (customer == null) {
break;
}
// Use the kitchen
System.out.println(this + " is now serving " + customer);
kitchen.use(this);
// Wait for the food outside the kitchen to get the order
System.out.println(this + " is waiting outside kitchen for order to be ready...");
Random random = new Random();
Thread.sleep(random.nextInt(1000) + 300);
// Go back to the kitchen to grab food
System.out.println(this + " will now go back to kitchen to get customer's order.");
kitchen.use(this);
customer.setServed(true);
System.out.println(this + " has served " + customer);
customer.signal();
// Process next customer...
}
System.out.println(this + " left the restaurant");
} catch (Exception e) {
e.printStackTrace(System.out);
}
}
// Return a string represenation of a waiter
@Override
public String toString() {
return "Waiter " + waiterId;
}
}
Kitchen:
import java.util.Random;
import java.util.concurrent.Semaphore;
// Place where waiters will prepare food. Only one waiter at a time
// can use this kitchen
public class Kitchen {
private Semaphore semaphore;
private Random random;
// Initialize the kitchen
public Kitchen() {
semaphore = new Semaphore(1);
random = new Random();
}
// Waiter will use this kitchen, if it is being used by another
// waiter then it will wait.
public void use(Waiter waiter) {
try {
semaphore.acquire();
System.out.println(waiter + " is now using the kitchen");
Thread.sleep(random.nextInt(500) + 100);
System.out.println(waiter + " is finished using the kitchen");
semaphore.release();
} catch (Exception e) {
e.printStackTrace(System.out);
}
}
}
Cashier:
import java.util.concurrent.Semaphore;
public class Cashier {
private Semaphore semaphore;
// Initialize the cashier
public Cashier() {
semaphore = new Semaphore(1);
}
// Accept customer's payment
public void acceptPayment(Customer customer) {
try {
semaphore.acquire();
System.out.println(customer + " paid the bill");
semaphore.release();
} catch (Exception e) {
e.printStackTrace(System.out);
}
}
}
Door:
import java.util.concurrent.Semaphore;
public class Door {
private int doorId;
private Semaphore semaphore;
// Initialize the door
public Door(int doorId) {
this.doorId = doorId;
semaphore = new Semaphore(1);
}
// 1 customer at a time to enter a door
public void enter(Customer customer) {
try {
semaphore.acquire();
System.out.println(customer + " entered using " + this);
semaphore.release();
} catch(Exception e) {
e.printStackTrace(System.out);
}
}
// Return a string representation of a door
@Override
public String toString() {
return "Door " + doorId;
}
}