Multithreading: why does my program terminate with different results?

Question

I'm doing some research on multithreading and trying to write programs.

I've written a restaurant program, simulating serving multiple customers in parallel:

• a restaurant opens, creates a waiter, a chef, some customers and waits until all customers have eaten their meals
• a customer makes an order, and waits for his boolean 'eaten' to become true, then he notifies the restaurant
• the waiter waits for a client to make an order, and then notifies the chef
• the chef waits for the waiter to notify him about the order, prepares the meal and sets customer's 'eaten' on true

Somehow my program will terminate with roughly different results.

After research I've done, I can see 2 reasons for terminating differently: 1) if my methods are not synchronized (which isn't the case in my program). 2) because we can't influence the way resources for threads are allocated, but this would rather cause some minor differences in the sequence of threads

But my program terminates with big differences, not just small differences in the sequence of threads:

• if there is one customer, it always terminates correctly
• if there are multiple customers, sometimes everything goes correctly and the restaurant closes. but sometimes it gets stuck after the second notification by the waiter, at the moment, when the chef should receive the next order. and it does not terminate, the threads are running, but the chef just does not process the next order.

Could someone give me any tips?

code for chef:

class Chef extends Thread{
    private static int _id=1;
    private int id;
    Order order;

    public Chef(){
        this.id=_id;
        _id++;
        order=null;
        this.start();
    }

    @Override
    public void run() {
        System.out.println("Chef ("+id+") starts to work...");

            synchronized(this){
                while(order==null){
                    try {
                        this.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }

            System.out.println("Chef ("+id+") prepared Order ("+this.order.getId()+")");

            Restaurant.customers.get(this.order.getId()-1).served=true;
            synchronized(Restaurant.customers.get(this.order.getId()-1)){
                Restaurant.customers.get(this.order.getId()-1).notify();
            }
                   order=null;
    }

    public void prepareOrder(Order order){

        this.order=order;
        System.out.println("Chef ("+this.id+") prepares order ("+order.getId()+")");
        synchronized(this){
            this.notify();
        }
    }
}

code for waiter (works correctly, always proceeds incoming orders):

class Waiter extends Thread{

    private static int _id=1;
    private int id;
    Order order;

    public Waiter(){
        this.id=_id;
        _id++;
        order=null;
        this.start();
    }

    @Override
    public void run() {
        System.out.println("Waiter ("+this.id+") starts to work...");

        synchronized(this){
            while(takenOrder==false){
                try {
                    wait();
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
        }
        order=null;

        Restaurant.chefs.get(0).prepareOrder(order);
    }

    public void takeOrder(Order order){

        this.order=order;
        System.out.println("Waiter ("+this.id+") takes order ("+this.order.getId()+")");
        synchronized(this){
            this.notify();
        }
    }
}

whole code

Answer 1

Answer Problem is this

synchronized(this){
...
}

The above code is not Right for two reasons.

1. There is no mutual Exclusion. Each thread has its own monitor/lock. Your lock can be seen by its own thread. Therefore synchronized(this) is redundant.
2. You should never synchronize on Thread instance (bad practice). in your case this is instance of Thread. One more thing don't extends thread, Try to avoid use Runnable instead

How to solve?

class Chef implments Runnable {

  private Object lock;
  Chef(Object lock) {
     this.lock = lock;
  }

  public run() {

      synchronized(lock) {
         // do stuff here
      }
  }

}


class Waiter implments Runnable {

  private Object lock;
  Chef(Object lock) {
     this.lock = lock;
  }

  public run() {

      synchronized(lock) {
         // do stuff here
      }
  }

}


//your main

 public static void main(String []args) {
    Object obj = new Object();
    Thread chef = new Thread(new Chef(obj));
    Thread waiter = new Thread(new Waiter(obj));
    chef.start();
    waiter.start();
 }

The above approach is suggested is a very basic example for mutual exclusion among two threads. But its not a best approach. try Using BlockingQueue its may best fitted for your purpose

i.e instead of sharing mutex obj share the ArrayBlockingQueue instance. It will take care of many things like it will wait if order Queue is empty or customers Queue is full

Answer 2

The question is not really theoretical, clearly there is something not right with the code.

Speculatively, my guess would be that the Chef is not checking for existing orders before waiting to be notified by the Waiter a second time.

Scenario:

1. Customer issues order to Waiter
2. Waiter notifies Chef
3. Chef starts making order
4. Customer issues order to Waiter
5. Waiter notifies Chef
6. Chef finishes first order
7. Chef waits to be notified by Waiter
8. Deadlock.

Answer 3

Monitor locks only work on a single shared instance of an Object. Your chef and waiter are not using the same looks and therefore ain't actually taking with each other

It's actually more of a fluke that the chef gets orders before it blocks indefinitely.

Create a single object (perhaps ORDER_LOCK) which the waiter uses to tell the check that there are orders available.

Waiter would call notify on this lock when it has one or more orders and check would wait on this lock.

Make it public static final so that the two are ensured to use the same instance of the lock

Updated

There's a few things I find weird, but lets not stray...

Your chef is relying on a single state flag called takenOrder. This flag can be modified by a number of threads simultaneously. There is also no way to stop a chef from being given two orders.

ie.

• Waiter(1) takes order(1)
• Waiter(1) takes order(2)
• Chef(1) prepares order(2) ... ??? Wait, what ???

This is known as a race condition. The expected result (order(1)) is being changed before check can processed.

You can actually see this with your ID generation. I was able to make two orders with the same ID

What you really need is some kind of queue system where a custom can not place an order until a waiter is available to take it.

A waiter may be in the (waiter) queue, taking an order and delivering an order.

A chef can in the (chef) queue or preparing an order.

A customer actually doesn't care. They will be making a decision (for an order), waiting for a waiter to place an order, waiting for an order, eating or leaving.

An object can only be in a queue if it is doing nothing. So it leaves the queue to start it's work and returns once it has completed.

There is also no connection between the order and the customer...so how do you know which order belongs to which customer?

Now, depending on what it's you want to achieve, you could create your own blocking queue, something like...

private List<Waiter> waiters;

//...//

public Waiter getNextAvailableWaiter() {

    Waiter waiter = null;

    synchronized (WAITER_QUEUE_LOCK) {

        while (waiters.isEmpty()) {
            WAITER_QUEUE_LOCK.wait();
        }

        waiter = waiters.remove(0);

    }

    return waiter;

}

Or using one of the implementations available in the JDK...see BlockingQueue for more details.

Now, the approach ;)

Personally, none of the entities should have direct to each other. Each should be managed by the restaurant.

For example. When a customer is ready, it should ask for the nextAvailableWaiter. When one becomes available, the customer will give the order to the waiter. The waiter will either get the nextAvailableChef and give the order to them, or even better, place the order in a order queue.

When a chef becomes available, they will get the nextOrder and prepare it. Once prepared, it should placed in a orderReady queue, where the either the waiter that placed it or the next available waiter can deliver it to the customer...