concurrency-problems

git clone git://git.codymlewis.com/concurrency-problems.git
Log | Files | Refs | README

commit 746a6485f55373e12f7580704a6f3f151ec73986
Author: Cody Lewis <cody@codymlewis.com>
Date:   Fri,  4 Oct 2019 10:59:03 +1000

Added implementation and report

Diffstat:
A.gitignore | 2++
AA2A.java | 26++++++++++++++++++++++++++
AA2B.java | 66++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
AA2C.java | 60++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
ABridge.java | 65+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
AClient.java | 90+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
ACoffeeMachine.java | 157+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
ACustomer.java | 88+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
AFarmer.java | 86+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
AMakefile | 19+++++++++++++++++++
AParlour.java | 117+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
AReport.md | 59+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
AReport.pdf | 0
ASyncTimer.java | 51+++++++++++++++++++++++++++++++++++++++++++++++++++
ATimer.java | 53+++++++++++++++++++++++++++++++++++++++++++++++++++++
15 files changed, 939 insertions(+), 0 deletions(-)

diff --git a/.gitignore b/.gitignore @@ -0,0 +1,2 @@ +Session.vim +*.class diff --git a/A2A.java b/A2A.java @@ -0,0 +1,26 @@ +import java.util.stream.IntStream; + +/** + * A2A - COMP2240A2 + * Main class for part A of this assignment + * + * @author Cody Lewis (c3283349) + * @since 2019-09-10 + */ + +public class A2A { + public static void main(String args[]) { + if (args.length != 2) { + System.err.println("Error: Incorrect arguments supplied."); + System.err.println("Usage: java A2A N=<integer> S=<integer>"); + System.exit(1); + } + Bridge bridge = new Bridge(15); + IntStream.range(1, Integer.parseInt(args[0].substring(args[0].indexOf("=") + 1)) + 1) + .boxed() + .forEach(i -> (new Farmer(String.format("N_Farmer%d", i), bridge, "South")).start()); + IntStream.range(1, Integer.parseInt(args[1].substring(args[1].indexOf("=") + 1)) + 1) + .boxed() + .forEach(i -> (new Farmer(String.format("S_Farmer%d", i), bridge, "North")).start()); + } +} diff --git a/A2B.java b/A2B.java @@ -0,0 +1,66 @@ +import java.util.Collection; +import java.util.LinkedList; +import java.util.Scanner; +import java.io.File; + +/** + * A2B - COMP2240 + * Main class for part B of this assignment + * + * @author Cody Lewis (c3283349) + */ + +public class A2B { + public static void main(String[] args) { + if (args.length < 1) { + System.err.println("Error: Incorrect arguments supplied."); + System.err.println("Usage: java A2B <inputfile>"); + System.exit(1); + } + A2B runner = new A2B(); + try { + runner.run(args[0]); + } catch (Exception e) { + System.err.format("Error: %s", e.getMessage()); + } + } + + /** + * Create a parlour, some customers and run until they all leave + * + * @param filename name of the file contiain the data of each of the customers + */ + public void run(String filename) throws Exception { + System.out.println("Customer\tarrives\tSeats\tLeaves"); + Parlour parlour = new Parlour(); + Collection<Customer> customers = parseFile(filename, parlour); + parlour.start(); + customers.stream().forEach(c -> c.start()); + while (parlour.hasEvents()); + customers.stream().forEach(c -> System.out.println(c.summary())); + parlour.stopTimer(); + } + + /** + * Parse the customer data file + * + * @param filename name of the file contiain the data of each of the customers + * @param parlour Ice cream parlour that the customers will use + * @return Linked list of the customers + */ + private Collection<Customer> parseFile(String filename, Parlour parlour) { + LinkedList<Customer> result = new LinkedList<>(); + try (Scanner fstream = new Scanner(new File(filename))) { + String line; + while (!(line = fstream.nextLine()).equals("END")) { + Scanner sstream = new Scanner(line); + result.add( + new Customer(sstream.nextInt(), sstream.next(), sstream.nextInt(), parlour) + ); + } + } catch (Exception e) { + System.err.format("Error: %s", e.getMessage()); + } + return result; + } +} diff --git a/A2C.java b/A2C.java @@ -0,0 +1,60 @@ +import java.util.Scanner; +import java.util.Collection; +import java.util.LinkedList; +import java.io.File; + +/** + * A2C - COMP2240 + * Main class for part C of this assignment + * + * @author Cody Lewis (c3283349) + */ + +public class A2C { + public static void main(String[] args) { + if (args.length < 1) { + System.err.println("Error: Incorrect arguments supplied."); + System.err.println("Usage: java A2C <inputfile>"); + System.exit(1); + } + A2C runner = new A2C(); + runner.run(args[0]); + } + + /** + * Create a parlour, some customers and run until they all leave + * + * @param filename name of the file contiain the data of each of the customers + */ + public void run(String filename) { + try { + CoffeeMachine coffeeMachine = new CoffeeMachine(); + parseFile(filename, coffeeMachine).stream().forEach(c -> c.start()); + coffeeMachine.startTimer(); + coffeeMachine.run(); + coffeeMachine.stopTimer(); + } catch (Exception e) { + System.err.format("Error: %s", e.getMessage()); + } + } + + /** + * Parse the Client data file + * + * @param filename Name of the Client data file + * @param coffeeMachine CoffeeMachine that the clients will use + * @return Collection containing each of the clients + */ + private Collection<Client> parseFile(String filename, CoffeeMachine coffeeMachine) { + LinkedList<Client> result = new LinkedList<>(); + try (Scanner fstream = new Scanner(new File(filename))) { + int clientCount = fstream.nextInt(); + for (int i = 0; i < clientCount; ++i) { + result.add(new Client(fstream.next(), fstream.nextInt(), coffeeMachine)); + } + } catch (Exception e) { + System.err.format("Error: %s", e.getMessage()); + } + return result; + } +} diff --git a/Bridge.java b/Bridge.java @@ -0,0 +1,65 @@ +import java.util.concurrent.Semaphore; + +/** + * Bridge - COMP2240A2 + * The bridge that all farmers will cross + * + * @author Cody Lewis (c3283349) + * @since 2019-09-10 + */ +public class Bridge { + private int neon; + private int length; + private Semaphore availabilty; + + /** + * Default constructor + */ + public Bridge() { + neon = 0; + length = 0; + availabilty = new Semaphore(1, true); + } + + /** + * Input constructor + * + * @param length Amount of steps needed to cross the bridge + */ + public Bridge(int length) { + this(); + this.length = length; + } + + /** + * Get the length of the bridge + * + * @return Amount of steps needed to cross the bridge + */ + public int getLength() { + return length; + } + + /** + * Have the farmer wait for the bridge to be crossable + * + * @param farmer A Farmer that wants to cross the bridge + */ + public void waitForBridge(Farmer farmer) throws Exception { + availabilty.acquire(); + } + + /** + * Increment the neon sign value and print it + */ + public void incrementNeon() { + System.out.format("NEON = %d\n", ++neon); + } + + /** + * Signal that a farmer has finished crossing the bridge + */ + public void signalBridge() { + availabilty.release(); + } +} diff --git a/Client.java b/Client.java @@ -0,0 +1,90 @@ +/** + * Client - COMP2240A2 + * A Client for a coffee machine + * + * @author Cody Lewis (c3283349) + */ + +public class Client extends Thread implements Comparable<Client> { + private String id; + private int brewTime; + private boolean isHot; + private CoffeeMachine coffeeMachine; + + /** + * Input constructor + * + * @param id ID of the client + * @param brewTime time the client will take to brew a coffee + * @param coffeeMachine CoffeeMachine that the Client will use + */ + public Client(String id, int brewTime, CoffeeMachine coffeeMachine) { + this.id = id; + this.brewTime = brewTime; + isHot = id.contains("H"); + this.coffeeMachine = coffeeMachine; + coffeeMachine.addClient(this); + } + + /** + * Find whether the client wants a hot coffee + * + * @return true if they want a hot coffee else false + */ + public boolean gettingHot() { + return isHot; + } + + /** + * Get the id of the client + * + * @return this Client's id + */ + public String getID() { + return id; + } + + /** + * Get the time that this Client wants to brew for + * + * @return brewing time + */ + public int getBrewTime() { + return brewTime; + } + + /** + * Compare the id of this to another Client + * + * @param other The other Client + * @return id of this compared to the id of other + */ + public int compareTo(Client other) { + return id.compareTo(other.getID()); + } + + /** + * Wait in line, brew a coffee for some time, and leave. + */ + public void run() { + try { + synchronized (this) { + wait(); + } + CoffeeMachine.Tap curTap = coffeeMachine.nextTap(); + synchronized (curTap) { + System.out.format( + "(%d) %s uses dispenser %d (time: %d)\n", + coffeeMachine.getTime(), + id, + curTap.getID(), + brewTime + ); + Thread.sleep(brewTime * SyncTimer.QUANTUM); + coffeeMachine.returnTap(curTap); + } + } catch (Exception e) { + e.printStackTrace(); + } + } +} diff --git a/CoffeeMachine.java b/CoffeeMachine.java @@ -0,0 +1,157 @@ +import java.util.Queue; +import java.util.LinkedList; +import java.util.Stack; +import java.util.PriorityQueue; + +/** + * CoffeeMachine - COMP2240A2 + * A coffee machine + * + * @author Cody Lewis (c3283349) + */ + +public class CoffeeMachine { + + /** + * A dispenser tap in the CoffeeMachine + */ + public class Tap { + private int id; + + /** + * Input constructor + * + * @param id id number of the tap + */ + public Tap(int id) { + this.id = id; + } + + /** + * Get the id number of this tap + * + * @return this tap's id number + */ + public int getID() { + return id; + } + } + + private int numberTaps; + private Stack<Tap> taps; + private SyncTimer timer; + private Queue<Client> line; + private PriorityQueue<Integer> eventTimes; + private boolean servingHot; + private boolean changeHeat; + + /** + * Default constructor + */ + public CoffeeMachine() { + numberTaps = 2; + taps = new Stack<Tap>(); + eventTimes = new PriorityQueue<>(); + timer = new SyncTimer(); + for (int i = 1; i <= numberTaps; ++i) { + taps.push(new Tap(i)); + eventTimes.offer(timer.getTime()); + } + line = new LinkedList<>(); + servingHot = true; + changeHeat = true; + } + + /** + * Start the timer + */ + public void startTimer() { + timer.start(); + } + + /** + * Stop the timer + */ + public void stopTimer() { + timer.kill(); + } + + /** + * Get the current time from the timer + */ + public int getTime() { + return timer.getTime(); + } + + /** + * Add a client to the line + * + * @param client Client to add the the end of the line + */ + public void addClient(Client client) { + line.offer(client); + } + + /** + * Run through serving each of the clients + */ + public synchronized void run() throws Exception { + while (!eventTimes.isEmpty()) { + int sleepTime = eventTimes.poll() - timer.getTime(); + Thread.sleep(sleepTime * SyncTimer.QUANTUM + SyncTimer.EPSILON); + boolean toWait = true; + while (toWait) { + synchronized (taps) { + toWait = taps.isEmpty(); + } + if (toWait) { this.wait(); } + } + Client curClient; + // The line lock ensures that the clients are served in order + synchronized(line) { + curClient = line.peek(); + if (curClient != null) { + synchronized (curClient) { + if (changeHeat) { + servingHot = curClient.gettingHot(); + changeHeat = false; + } + if (servingHot != curClient.gettingHot()) { + wait(); + } + eventTimes.offer(timer.getTime() + curClient.getBrewTime()); + curClient.notify(); + line.poll(); + } + } + } + } + System.out.format("(%d) DONE\n", timer.getTime()); + } + + /** + * Get the next usable tap from the CoffeeMachine + * + * @return The next usable tap + */ + public Tap nextTap() { + synchronized (taps) { + return taps.pop(); + } + } + + /** + * Stop using the tap of the CoffeeMachine + * + * @param tap The Tap to return + */ + public synchronized void returnTap(Tap tap) { + synchronized (taps) { + taps.push(tap); + if (taps.size() == numberTaps) { + changeHeat = true; + } + notify(); + } + } +} diff --git a/Customer.java b/Customer.java @@ -0,0 +1,88 @@ +/** + * Customer - COMP2240 + * An ice cream parlour customer + * + * @author Cody Lewis (c3283349) + */ + +public class Customer extends Thread implements Comparable<Customer> { + private String id; + private int arrivalTime; + private int eatingTime; + private int finishEatingTime; + private Parlour parlour; + private String stats; + + /** + * Input Constructor + * + * @param arrivalTime Time that the customer arrives at the parlour + * @param id id of the customer + * @param eatingTime Amount of time that the customer takes to eat + * @param parlour The ice cream parlour that the customer will eat at + */ + public Customer(int arrivalTime, String id, int eatingTime, Parlour parlour) throws Exception { + this.id = id; + this.arrivalTime = arrivalTime; + this.eatingTime = eatingTime; + this.parlour = parlour; + this.stats = String.format("%s\t\t%d\t", id, arrivalTime); + parlour.addEvent(this); + } + + /** + * Arrive at the parlour + */ + public void arrive() throws Exception { + this.stats += String.format("%d\t", parlour.takeSeat(this)); + } + + /** + * Start eating at the parlour + */ + public void startEating(int time) { + this.stats += String.format("%d\t", time); + } + + /** + * Leave the parlour + */ + public int leave() throws Exception { + return parlour.leave(this); + } + + /** + * Get the summary of what the customer has done + */ + public String summary() { + return stats; + } + + /** + * Get the id of this + * + * @return this Customer's id + */ + public String getID() { return id; } + + /** + * Arrive at the parlour, eat, then leave + */ + public void run() { + try { + Thread.sleep(arrivalTime * Timer.QUANTUM); + arrive(); + Thread.sleep(eatingTime * Timer.QUANTUM); + this.stats += leave(); + } catch (Exception e) { + System.out.format("Error: %s", e.getMessage()); + } + } + + /** + * Compare the id of this customer to another + */ + public int compareTo(Customer other) { + return id.compareTo(other.getID()); + } +} diff --git a/Farmer.java b/Farmer.java @@ -0,0 +1,86 @@ +/** + * Farmer - COMP2240A2 + * A Farmer Thread object + * + * @author Cody Lewis (c3283349) + * @since 2019-10-01 + */ + +public class Farmer extends Thread { + private boolean canCross; + private String id; + private Bridge bridge; + private int distStepped; + private boolean toWait; + private String headingTo; + private boolean blocked; + + /** + * Construct a farmer with the input values + * + * @param id ID of the farmer + * @param bridge the shared bridge for the Farmer to cross + * @param headingTo Where the farmer is heading to + */ + public Farmer(String id, Bridge bridge, String headingTo) { + canCross = false; + toWait = false; + this.id = id; + this.bridge = bridge; + distStepped = 0; + this.headingTo = headingTo; + waiting(); + } + + /** + * Print that the farmer is waiting to cross the bridge + */ + public void waiting() { + System.out.format( + "%s: Waiting for bridge. Going towards %s\n", + id, + headingTo + ); + } + + /** + * Cross the bridge + * + * @param amount Amount of steps to cross the bridge by + */ + public boolean cross(int amount) { + distStepped += amount; + if (distStepped < bridge.getLength()) { + System.out.format( + "%s: Crossing bridge Step %d.\n", id, distStepped + ); + return false; + } else { + distStepped = 0; + headingTo = headingTo == "North" ? "South" : "North"; + System.out.format("%s: Across the bridge.\n", id); + return true; + } + } + + /** + * Main running function for this Thread + */ + public void run() { + try { + while (true) { + waiting(); + bridge.waitForBridge(this); + while (!cross(5)); + bridge.incrementNeon(); + bridge.signalBridge(); + } + } catch (Exception e) { + e.printStackTrace(); + } + } + + public String toString() { + return id; + } +} diff --git a/Makefile b/Makefile @@ -0,0 +1,19 @@ +all: clean A2C + +clean: + $(RM) *.class + +A2A: + javac A2A.java; + java A2A N=2 S=2 + +A2B: + javac A2B.java;\ + java A2B ../Binput.txt + +A2C: + javac A2C.java;\ + java A2C ../Cinput.txt + +report: + pandoc Report.md -s --highlight-style=pygments -o Report.pdf diff --git a/Parlour.java b/Parlour.java @@ -0,0 +1,117 @@ +import java.util.Set; +import java.util.TreeSet; +import java.util.concurrent.Semaphore; + +/** + * Parlour - COMP2240 + * The ice cream parlour, including the line up logic + * + * @author Cody Lewis (c3283349) + */ + +public class Parlour { + private int availableSeats; + private int totalSeats; + private Semaphore seats; + private Semaphore accessTime; + private Semaphore accessCustomers; + private Semaphore wait; + private boolean waitMode; + private Timer timer; + private Set<Customer> customers; + + /** + * Default constructor + */ + public Parlour() { + totalSeats = 4; + availableSeats = totalSeats; + seats = new Semaphore(totalSeats, true); + accessCustomers = new Semaphore(1, true); + accessTime = new Semaphore(1, true); + wait = new Semaphore(0, true); + customers = new TreeSet<>(); + timer = new Timer(); + waitMode = false; + } + + /** + * Start the timer + */ + public void start() { + timer.start(); + } + + /** + * Check whether there are still things to do + * + * @return true if there are still customers that will eat else false + */ + public boolean hasEvents() throws Exception { + accessCustomers.acquire(); + boolean result = customers.isEmpty(); + accessCustomers.release(); + return !result; + } + + /** + * Stop the timer + */ + public void stopTimer() { + timer.kill(); + } + + /** + * Add a thing to do + * + * @param customer The Customer involved in the event + */ + public void addEvent(Customer customer) throws Exception { + accessCustomers.acquire(); + customers.add(customer); + accessCustomers.release(); + } + + /** + * Like young Skywalker, the Customer will take a seat + * + * @param customer Customer to take a seat + * @return Time when the customer will finish eating + */ + public int takeSeat(Customer customer) throws Exception { + if (waitMode) { + wait.acquire(); + } + seats.acquire(); + if (--availableSeats == 0) { + waitMode = true; + } + accessTime.acquire(); + int curTime = timer.getTime(); + accessTime.release(); + return curTime; + } + + /** + * The Customer leaves the Parlour + * + * @param customer Customer that will leave + * @return Time the Customer leaves + */ + public int leave(Customer customer) throws Exception { + accessCustomers.acquire(); + customers.remove(customer); + accessCustomers.release(); + seats.release(); + if (++availableSeats == 4) { + waitMode = false; + for (int i = 0; i < totalSeats; ++i) { + wait.release(); + } + } + accessTime.acquire(); + int curTime = timer.getTime(); + accessTime.release(); + return curTime; + } +} diff --git a/Report.md b/Report.md @@ -0,0 +1,59 @@ +--- +title: Comp2240 - Assignment 2 +author: Cody Lewis [c3283349@uon.edu.au](mailto:c3283349@uon.edu.au) +date: \today +geometry: margin=2cm +linkcolor: blue +--- + +# Sharing the Bridge + +This program was very simple to implement, in that it only required a single +semaphore indicating whether a farmer may cross the bridge. In order to ensure +that the implementation is fair, I had to initialize the semaphore as a hard +semaphore. The result runs very quickly with the output, however, I figure that +may be checked by doing something like piping the output into `less`. + +# Ice-Cream Time + +This program turned out a bit more difficult to implement, especially since I +initially tried to implement it as a discrete time event simulation. The +discrete time event approach turned out to be unsuccessful due to requiring +concurrent access and creating messy interactions. This lead my to use real +time involving sleeps and a timer, I timed in terms of a quantum parameter +which I determined the value of by testing the program at the maximum capacity +on the ES409 lab environment. I was able to be certain of maximum capacity +as the program only needs to be able to handle 4 concurrent threads running at +any given time, hence, I only needed to give sufficient time to handle that. + +A major factor in making this implementation work correctly was the ordering of +locks. I had to use semaphore to lock access to the seats, time, and the line +of customers, these locks ensured mutual exclusion of the operations in +the seat placement algorithm. In order to implement the extra rule for +placement, where no customers will be served when all 4 seats were taken until +all are emptied, I had to add an extra semaphore which locks away the ability +to take a seat. For this to work I had to implement a method of keeping track +of the amount of available seats and locking when there are none, then +unlocking when they are all available. + +# Hot or Iced Coffee? + +In order to implement the algorithm specified, I decided to take what I had +learnt from the previous problem in using a timer, and sleeps. However, this +time, I managed locking through the use of monitors this time as per the +Assignment specifications. In order to give ordering of client arrival, I have +them be placed in a queue, this would be the line for the coffee machine. Then, +I also gave the coffee machine a priority queue of event times, this gets used +by giving the coffee machine a reference where it can determine the amount of +time to sleep before the next event occurs in the system. I found that a +required a secondary parameter for time units in the case of this program, +epsilon, which allows for the distinguishment of multiple simulataneous events +without clashes, or incrementing to the time. + +An important element of getting this program to work correctly was the ordering +of waits and the locks. I found that to ensure the maintainance of the +order of the serving of the clients, I had to lock the queue of clients, then +while that is locked performing the check for notifying the client that the +stop waiting. I decided to have an additional wait contained in the serving of +clients in the case of a mismatch of hot and cold between what is being served +currently and what the client wants. diff --git a/Report.pdf b/Report.pdf Binary files differ. diff --git a/SyncTimer.java b/SyncTimer.java @@ -0,0 +1,51 @@ +/** + * SyncTimer - COMP2240 + * Timer that uses monitors + * + * @author Cody Lewis (c3283349) + */ + +public class SyncTimer extends Thread { + public static final int QUANTUM = 50; + public static final int EPSILON = 1; + private int time; + private boolean alive; + + /** + * Default constructor + */ + public SyncTimer() { + time = 0; + alive = true; + } + + /** + * Get the current time + * + * @return current time in quantum units + */ + public synchronized int getTime() { + return time; + } + + /** + * Kill this timer + */ + public synchronized void kill() { + alive = false; + } + + /** + * Sleep for a quantum then increment the time + */ + public void run() { + try { + while(alive) { + Thread.sleep(QUANTUM); + time++; + } + } catch (Exception e) { + e.printStackTrace(); + } + } +} diff --git a/Timer.java b/Timer.java @@ -0,0 +1,53 @@ +/** + * Timer - COMP2240 + * Keep time in a separate Thread + * + * @author Cody Lewis (c3283349) + */ + +public class Timer extends Thread { + private int time; + private boolean alive; + /** + * Amount of time (ms) for a single unit of sleep + */ + public static final int QUANTUM = 100; + + /** + * Default constructor + */ + public Timer() { + time = 0; + alive = true; + } + + /** + * Get the current time in quantums from this Thread starting + * + * @return time in quantums from this starting + */ + public int getTime() { + return time; + } + + /** + * Kill this timer + */ + public void kill() { + alive = false; + } + + /** + * Sleep for a quantum then iterate the time + */ + public void run() { + try { + while(alive) { + Thread.sleep(Timer.QUANTUM); + time++; + } + } catch (Exception e) { + System.out.format("Error: %s", e.getMessage()); + } + } +}