Crossing single lane bridge with pairs of threads (java semaphore)

Viewed 4410

got a task with a different variation of the classic problem. We have a bridge between North and South, n number of objects trying to cross from North, and s number of objects trying to cross from south.(each object runs on its own thread). In this case the object is a Farmer. All the threads start at the same time so the output should vary depending on who gets to the semaphore first.

I understand many variations of this have been asked but I cannot seem to find one too closely related to my problem that I can understand.

I have implemented a perfectly functioning "one at a time" crossing using a single java.util.concurrent.Semaphore on my bridge but am struggling to upgrade it to meet the new criteria for the next question.

The problem is that they must now cross in pairs, and both pairs must be from the same side of the bridge, so 2 can cross from North together or 2 from South together, and not at all if there is only 1 left on that side (needs to loop endlessly trying to cross).

I don't expect you to answer my assignment question for me but any help pointing me in the right direction using java semaphores would be great. My understanding is I have to have my semaphore have a max of 2 (easy enough) and I have to lock the bridge until 2 objects from a certain side are ready to cross (not as easy).

Example output for one at a time crossing on N=3 S=4

Question 2. N_Farmer1: Waiting for bridge. Going towards South N_Farmer2: Waiting for bridge. Going towards South N_Farmer3: Waiting for bridge. Going towards South S_Farmer1: Waiting for bridge. Going towards North S_Farmer2: Waiting for bridge. Going towards North S_Farmer3: Waiting for bridge. Going towards North S_Farmer4: Waiting for bridge. Going towards North N_Farmer1: Crossing bridge Step 5. N_Farmer1: Crossing bridge Step 10. N_Farmer1: Crossing bridge Step 15. N_Farmer1: Across the Bridge. NEON = 1 N_Farmer2: Crossing bridge Step 5. N_Farmer2: Crossing bridge Step 10. N_Farmer2: Crossing bridge Step 15. N_Farmer2: Across the Bridge. NEON = 2 N_Farmer3: Crossing bridge Step 5. N_Farmer3: Crossing bridge Step 10. N_Farmer3: Crossing bridge Step 15. N_Farmer3: Across the Bridge. NEON = 3 S_Farmer2: Crossing bridge Step 5. S_Farmer2: Crossing bridge Step 10. S_Farmer2: Crossing bridge Step 15. S_Farmer2: Across the Bridge. NEON = 4 S_Farmer1: Crossing bridge Step 5. S_Farmer1: Crossing bridge Step 10. S_Farmer1: Crossing bridge Step 15. S_Farmer1: Across the Bridge. NEON = 5 S_Farmer3: Crossing bridge Step 5. S_Farmer3: Crossing bridge Step 10. S_Farmer3: Crossing bridge Step 15. S_Farmer3: Across the Bridge. NEON = 6 S_Farmer4: Crossing bridge Step 5. S_Farmer4: Crossing bridge Step 10. S_Farmer4: Crossing bridge Step 15. S_Farmer4: Across the Bridge. NEON = 7

my code Bridge.java

public class Bridge {
private int crossed;    //Count the number of crossings
private Semaphore bridgeSem;    //semaphore to only allow 1 crossing at a time

//Constructor
public Bridge() {
    crossed=0;
    bridgeSem = new Semaphore(1);   //one bridge resource, mutual exclusivity
}

//Getters
public int getCrossed() {
    return crossed;
}

//Methods
public void cross() { 
    //Semaphore acquire
    try {   
        bridgeSem.acquire();    
        crossed++;              //increment NEON counter
    }
    catch (InterruptedException e) {} 
}

public void exit() {
    //Semaphore release
    bridgeSem.release();

}
}

Farmer.java:

public class Farmer extends Thread{
private String location;    //current location
private String destination; //Opposite location, destination, set in the constructor
private String id;          //name      
private Bridge bridge;      //bridge being used

//constructor
public Farmer(String id, String location, Bridge bridge) {
    this.id=id;
    this.location=location;
    if (location=="North") destination="South"; //Island objects are not necessary for this particular implementation, as our options are merely North or South
    else destination="North";
    this.bridge = bridge;
    System.out.println(id+": Waiting for bridge. Going towards "+destination);  //print initial waiting for bridge

}

//getters
public String getLocation() {
    return location;
}
public String getID() {
    return id;
}

//Do not need setters, none of the instance variables need to change

@Override   //initiatied when the thread.start() method is called
public void run() {

        //***initiate critical section requiring semaphore***
        bridge.cross();

        System.out.println(id+": Crossing bridge Step 5.");
        System.out.println(id+": Crossing bridge Step 10.");
        System.out.println(id+": Crossing bridge Step 15.");

        //Sleep for 200 units ,improves readability (else output is too fast) 
        try {
            Thread.sleep(200);
        } catch (InterruptedException e) {} //No interrupts implemented, so thread shouldn't be interrupted?

        System.out.println(id+": Across the Bridge.");
        System.out.println("NEON = "+bridge.getCrossed());

        bridge.exit();
        //***end critical section***


        //Sleep for 20 units, prevents hogging of semaphore(starvation)
        try {
            Thread.sleep(20);
        } catch (InterruptedException e) {}
}//end run  

}//end class

Main:

public static void main(String[] args) {
    System.out.println("Question 2.");
    int N=3,S=4;    //DEBUG, add file reading later
    Bridge bridge = new Bridge();   //create our bridge
    Farmer[] f = new Farmer[N+S];   //array of Farmers
    //create North farmers
    for (int i=0; i<N; i++) {
        f[i] = new Farmer("N_Farmer"+(i+1),"North",bridge);
    }
    //create South farmers
    for (int i=N; i<S+N; i++) {
        f[i]= new Farmer("S_Farmer"+(i-N+1),"South",bridge);
    }

    //start all farmers
    for (int i=0;i<S+N;i++) {
        f[i].start();   //start Farmer Threads. Farmers can run start, as Farmer extends thread
    }
}
1 Answers

Solution I used: Moved the cross related stuff to the Bridge file Bulk of the relevant logic is in Farmer.java run() command, and a little in Synchronized function in Bridge.java (keeps relevant counters). Main file is mostly just file reading and starting the farmers. Farmer Threads essentially check that bridge has not counted 2 north or 2 south farmers yet, if they have not it counts the current one with a Synchronized bridge function upThis(Farmer f). Bridge keeps a counter of how many North or South farmers are ready. in Farmer run() if North or South hits 2 we give semaphore access to the appropriate side (semaphore has 2 resources), then we wait til both are finished (with a synchronized bridge.getExited()==2) and then exit both of them, and reset all counters. Now that the counters have reset, the Farmer Thread while loops can try again.

Might not be the best solution, Farmer threads run in an infinite while loop, continually rechecking conditions, probably not ideal. But it works as far as I can tell so I thought I'd throw it up for anyone with similar problems.

Will mark this as solved and the correct solution until someone responds with something better.

Bridge.java:

import java.util.concurrent.Semaphore;


public class Bridge {
    private int crossed;    //Count the number of crossings
    private static Semaphore bridgeSem; //semaphore to only allow 1 crossing at a time
    private int northWaiting, southWaiting;
    private int exited;
    //Constructor
    public Bridge() {
        crossed=0;
        bridgeSem = new Semaphore(2);   //one bridge resource, mutual exclusivity
        northWaiting = southWaiting = 0;
        exited = 0;

    }

    //Getters
    public int getCrossed() {
        return crossed;
    }
    //Methods
    public synchronized void upCross() {
        crossed++;
        System.out.println("NEON = "+getCrossed());
    }
    public synchronized void upThis(Farmer f) {
        if (f.getID().startsWith("N")) northWaiting++;
        else southWaiting++;
        f.counted();
        //System.out.println(f.getID()+" is queued to cross");  //DEBUG 
    }
    public synchronized void upExited() {
        exited++;
    }
    public synchronized int getNorth() {
        return northWaiting;
    }
    public synchronized int getSouth() {
        return southWaiting;
    }
    public synchronized int getExited() {
        return exited;
    }
    public synchronized void resetExited() {
        exited=0;
    }
    public synchronized void resetNorth() {
        northWaiting=0;
    }
    public synchronized void resetSouth() {
        southWaiting=0;
    }

    public void cross(Farmer f) { 
        //Semaphore acquire
        try {   
            bridgeSem.acquire();    
            System.out.println(f.getID()+": Crossing bridge Step 5.");
            System.out.println(f.getID()+": Crossing bridge Step 10.");
            System.out.println(f.getID()+": Crossing bridge Step 15.");

            //Sleep for 200 units ,improves readability (else output is too fast) 
            try {
                Thread.sleep(200);
            } catch (InterruptedException e) {} //No interrupts implemented, so thread shouldn't be interrupted?

            System.out.println(f.getID()+": Across the Bridge.");
            upCross();  //increment NEON counter, synchronized to avoid print conflicts
            //Sleep for 200 units ,improves readability (else output is too fast) 
            try {
                Thread.sleep(200);
            } catch (InterruptedException e) {} //No interrupts implemented, so thread shouldn't be interrupted?
        }
        catch (InterruptedException e) {} 
    }

    public void exit() {
        //Semaphore release
        upExited();
        bridgeSem.release();

    }
}

Farmer.java:

public class Farmer extends Thread{
    private String location;    //current location
    private String destination; //Opposite location, destination, set in the constructor
    private String id;          //name      
    private Bridge bridge;      //bridge being used
    private boolean finished=false;
    private boolean counted = false;

    //constructor
    public Farmer(String id, String location, Bridge bridge) {
        this.id=id;
        this.location=location;
        if (location=="North") destination="South"; //Island objects are not necessary for this particular implementation, as our options are merely North or South
        else destination="North";
        this.bridge = bridge;
        System.out.println(id+": Waiting for bridge. Going towards "+destination);  //print initial waiting for bridge

    }

    //getters
    public String getLocation() {
        return location;
    }
    public String getID() {
        return id;
    }
    public boolean isCounted() {
        return counted;
    }
    //setter
    public void setFinished(boolean finished) {
        this.finished=finished;
    }
    public void counted() {
        counted=true;
    }

    //Overrides the Thread toString() method. Called with Thread.getCurrent().toString()
    @Override   
    public String toString() {
        return id;
    }
    @Override   //initiatied when the Farmer Thread .start() method is called
    public void run() {
        //if ready to cross

        while (!finished) {
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {}

            if (bridge.getNorth() != 2 && bridge.getSouth() != 2 && !counted) { //if neither equal 2 yet and we havent added this to the list
                bridge.upThis(this);    //increments the appropriate north/south counter in a thread safe method, also marks this thread as counted=true
            }
            if (counted && bridge.getNorth()==2 && id.startsWith("N")) {    //if this has been counted, and is a northern farmer and there are 2 northern farmers ready
                bridge.cross(this);
                bridge.exit();
                finished=true;
                if (bridge.getExited()==2) {    //if both successfully crossed reset counts
                    bridge.resetExited();
                    bridge.resetNorth();
                    //System.out.println("Reset exited and North"); //DEBUG
                    //System.out.println("Exit: "+bridge.getExited()+", North: "+bridge.getNorth()+", South: "+bridge.getSouth()); //DEBUG
                }
            }
            else if (counted && bridge.getSouth()==2 && id.startsWith("S")) { //else if this has been counted, and is a southern farmer and there are 2 southern farmers ready
                bridge.cross(this);
                bridge.exit();
                finished=true;
                if (bridge.getExited()==2) {    //if both successfully crossed reset counts
                    bridge.resetExited();
                    bridge.resetSouth();
                    //System.out.println("Reset exited and South"); //DEBUG
                    //System.out.println("Exit: "+bridge.getExited()+", North: "+bridge.getNorth()+", South: "+bridge.getSouth()); //DEBUG
                }
            }

        }
    }//end run  

}//end class

Main.java:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.NoSuchElementException;
import java.util.Scanner;

import packagename.Bridge;
import packagename.Farmer;

public class MainP2 {

    public static void main(String[] args) {
        System.out.println("Question 2.");
        //File reading
        boolean success = false;    //looping file input
        int N=0,S=0;
        String[] input;
        Scanner in = new Scanner(System.in);
        System.out.println("Enter file name eg input.txt: ");
        while (!success) {  //loop until a valid file is given
            try {
                String f = in.nextLine();
                Scanner file = new Scanner(new File(f));    //Throws file not found exception
                try {
                    //split by space
                    input = file.nextLine().split("\\s+");
                    //set number of north and south farmers
                    N = Integer.parseInt(input[0].replaceAll("[^0-9]+",""));    
                    S = Integer.parseInt(input[1].replaceAll("[^0-9]+",""));
                    success = true; //no exception thrown, all went well, break loop
                } catch (NoSuchElementException e) {System.out.println("File was empty or invalid! Please enter a valid file.");}
                file.close();
            } catch (FileNotFoundException e) { System.out.println("File not found! Please enter a valid file.");}
        }
        in.close();
        //end file reading

        Bridge bridge = new Bridge();   //create our bridge
        Farmer[] f = new Farmer[N+S];   //array of Farmers
        //create North farmers
        for (int i=0; i<N; i++) {
            f[i] = new Farmer("N_Farmer"+(i+1),"North",bridge);
        }
        //create South farmers
        for (int i=N; i<S+N; i++) {
            f[i]= new Farmer("S_Farmer"+(i-N+1),"South",bridge);
        }

        //start all farmers
        for (int i=0;i<S+N;i++) {
            f[i].start();   //start Farmer Threads. Farmers can run start, as Farmer extends thread
        }
    }

}
Related