# HW 5 SSE

Ivan Christian

## 1

`getLocation` can be called by both `getImage` and `setLocation` whihc may cause a deadlock problem since multiple threads can call on the lock to try to get it. A possible fix can be seen in the following:

package week5;

import java.util.HashSet;
import java.util.Set;

public class DLExample {
	
}

class Taxi {
    private Point location, destination;
    private final Dispatcher dispatcher;

    public Taxi(Dispatcher dispatcher) {
        this.dispatcher = dispatcher;
    }

	public synchronized Point getLocation() {
        return location;
    }

    public synchronized void setLocation(Point location) {
    	/**
        this.location = location; // Setting location --> locking getLocation
        if (location.equals(destination))
            dispatcher.notifyAvailable(this); // Finished the trip
           **/
    	// FIX
    	
    	boolean reachedDestination;
    	synchronized(this)
    	{
    		this.location = location;
    		reachedDestination = location.equals(destination);
    	}
    	
    	if (reachedDestination)
    	{
    		dispatcher.notifyAvailable(this); // Finished the trip
    	}
    }

    public synchronized Point getDestination() {
        return destination;
    }
}

class Dispatcher {
    private final Set<Taxi> taxis;
    private final Set<Taxi> availableTaxis;

    public Dispatcher() {
        taxis = new HashSet<Taxi>();
        availableTaxis = new HashSet<Taxi>();
    }

    public synchronized void addTaxi(Taxi taxi) {
    	taxis.add(taxi);
        availableTaxis.add(taxi);
    }

    public synchronized void notifyAvailable(Taxi taxi) {
        availableTaxis.add(taxi);
    }

    // public synchronized Image getImage() {
    //     Image image = new Image();
    //     for (Taxi t : taxis)
    //         image.drawMarker(t.getLocation()); // Locking getLocation.
    //     return image;
    // }
        public Image getImage() {
        Set<Taxi> copy;
        
        synchronized (this) 
        { //this keyword refers to the current object in a method or constructor.
            copy = new HashSet<Taxi>(taxis);
        }

        Image image = new Image();
        for (Taxi t : copy) 
            image.drawMarker(t.getLocation());
        return image;
        }

class Image {
    public void drawMarker(Point p) {
    }
}

class Point {
	
}

## 2

The idea for a Dining Philosopher Problem fix is to make sure that only four out of five philosophers can pick up their left fork simultaneously, which guarantees that at least one philosopher will always be able to pick up both forks and eat. This essentially changes the priority of the philosopher to be different from the others and this would ensure that everyone should not be in a deadlock. The following is the proposed fix for the Dining Philosopher Problem.

// the same as the question
class Philosopher extends Thread {
	private final int index;
	private final Fork left;
	private final Fork right;
	
	public Philosopher (int index, Fork left, Fork right) {
		this.index = index;
		this.left = left;
		this.right = right;
	}
	
	public void run() {
		Random randomGenerator = new Random();
		try {
			while (true) {
				Thread.sleep(randomGenerator.nextInt(100)); //not sleeping but thinking
				System.out.println("Phil " + index + " finishes thinking.");
//				left.pickup();				
//				System.out.println("Phil " + index + " picks up left fork.");
//				right.pickup();
//				System.out.println("Phil " + index + " picks up right fork.");
				if (index == 0) {
                    right.pickupBoth(left);
                } else {
                    left.pickupBoth(right);
                }
				Thread.sleep(randomGenerator.nextInt(100)); //eating
				System.out.println("Phil " + index + " finishes eating.");
				left.putdown();
				System.out.println("Phil " + index + " puts down left fork.");
				right.putdown();							
				System.out.println("Phil " + index + " puts down right fork.");
			}
		} catch (InterruptedException e) {
			System.out.println("Don't disturb me while I am sleeping, well, thinking.");
		} 
	}
}

class Fork {
	private final int index;
	private boolean isAvailable = true;
	
	public Fork (int index) {
		this.index = index;
	}
	
	public synchronized void pickup () throws InterruptedException {
		while (!isAvailable) {
			wait();
		}
		
		isAvailable = false;
		notifyAll();
	} // Can be deleted for this instance

	
	public synchronized void putdown() throws InterruptedException {
		while (isAvailable) {
			wait();
		}

		isAvailable = true;
		notifyAll();
	}
	
	public synchronized void pickupBoth(Fork f) throws InterruptedException {
	    while (!isAvailable || !f.isAvailable) {
	        wait();
	    }
	    isAvailable = false;
	    f.isAvailable = false;
	}

	
	public String toString () {
		if (isAvailable) {
			return "Fork " + index + " is available.";			
		}
		else {
			return "Fork " + index + " is NOT available.";						
		}
	}
}

This is not a fair system as by observation, Phil 1 continuously get to eat after some time as seen by the following result.

---------------------------
Phil 2 finishes thinking.
Phil 4 finishes thinking.
Phil 1 finishes thinking.
Phil 0 finishes thinking.
Phil 3 finishes thinking.
Phil 4 finishes eating.
Phil 4 puts down left fork.
Phil 4 puts down right fork.
Phil 2 finishes eating.
Phil 2 puts down left fork.
Phil 2 puts down right fork.
Phil 2 finishes thinking.
Phil 4 finishes thinking.
Phil 2 finishes eating.
Phil 2 puts down left fork.
Phil 2 puts down right fork.
Phil 0 finishes eating.
Phil 0 puts down left fork.
Phil 0 puts down right fork.
Phil 0 finishes thinking.
Phil 2 finishes thinking.
Phil 2 finishes eating.
Phil 2 puts down left fork.
Phil 2 puts down right fork.
Phil 4 finishes eating.
Phil 4 puts down left fork.
Phil 4 puts down right fork.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 4 finishes thinking.
Phil 2 finishes thinking.
Phil 3 finishes eating.
Phil 3 puts down left fork.
Phil 3 puts down right fork.
Phil 2 finishes eating.
Phil 2 puts down left fork.
Phil 2 puts down right fork.
Phil 1 finishes thinking.
Phil 3 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 3 finishes eating.
Phil 3 puts down left fork.
Phil 3 puts down right fork.
Phil 2 finishes thinking.
Phil 2 finishes eating.
Phil 2 puts down left fork.
Phil 2 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 3 finishes thinking.
Phil 3 finishes eating.
Phil 3 puts down left fork.
Phil 3 puts down right fork.
Phil 2 finishes thinking.
Phil 3 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 3 finishes eating.
Phil 3 puts down left fork.
Phil 3 puts down right fork.
Phil 3 finishes thinking.
Phil 1 finishes thinking.
Phil 2 finishes eating.
Phil 2 puts down left fork.
Phil 2 puts down right fork.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 2 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
Phil 1 finishes eating.
Phil 1 puts down left fork.
Phil 1 puts down right fork.
Phil 1 finishes thinking.
...

----------------------

## 3

What are the shared variables?

- saving and investment are shared between multiple threads.

What are the classes which must be made thread-safe?
- BAccount to avoid race condition.

What are the mutable states of the class?
- BAccount.savings, BAccount.investment, Banking.numberOfThreads

What are the requirements of the class?
- The BAccount class must ensure that the balance of saving and investment fields is consistent after concurrent updates by multiple threads.
- The class should prevent negative balances for the saving field.

What is the locking policy of the class?
- Guard BAccount.saving and BAccount.investment variable by having an intrinsic lock using synchronized keyword on both BAccount.deposit() and BAccount.invest() methods.
- Use volatile on BAccount.saving and BAccount.investment too, to ensure that they are always written to the main memory and always updated correctly.

Fix can be seen in the following:

// the same as the question 
class BAccount {
	private int saving;
	private int investment;
	
	public BAccount (int saving, int investment) {
		this.saving = saving;
		this.investment = investment;
	}
	
//	public void deposit (int n) {
//		saving += n;
//	}
//	
//	public void invest (int n) {
//			saving -= n;
//			investment += n;
//	}
	public void deposit(int n) {
        synchronized (this) {
            saving += n;
        }
    }

    public void invest(int n) {
        synchronized (this) {
            if (saving >= n) {
                saving -= n;
                investment += n;
            } else {
                System.out.println("Insufficient balance");
            }
        }
	
	public String toString () {
		return "Saving: SGD " + saving + "; Investment: SGD " + investment;
	}
}