java - 用成对的线程(java 信号量)穿越单车道桥

Question

得到了一个经典问题的不同变体的任务。我们在南北之间有一座桥，n 个对象试图从北穿过，s 个对象试图从南穿过。(每个对象在自己的线程上运行)。在这种情况下，对象是 Farmer。所有线程同时启动，因此输出应根据谁先到达信号量而有所不同。

我知道有人问过这个问题的很多变体，但我似乎找不到一个与我的问题密切相关以至于我能理解的问题。

我已经在我的桥上使用单个 java.util.concurrent.Semaphore 实现了一个功能完美的“一次一个”交叉，但我正在努力升级它以满足下一个的新标准问题。

问题是他们现在必须成对穿过，而且两对必须来自桥的同一侧，所以 2 个可以一起从北方穿过，或者 2 个可以一起从南方穿过，而不是在all 如果那一侧只剩下 1 个(需要无休止地循环尝试穿过)。

我不希望您为我回答我的作业问题，但任何使用 Java 信号量为我指明正确方向的帮助都会很棒。我的理解是我必须让我的信号灯最多有 2 个(很容易)并且我必须锁定桥直到某一侧的 2 个物体准备好通过(不那么容易)。

一次一个穿越 N=3 S=4 的示例输出

问题 2。
N_Farmer1:WAITING桥接。走向南方
N_Farmer2:WAITING桥接。走向南方
N_Farmer3:WAITING桥接。走向南方
S_Farmer1:WAITING桥接。走向北方
S_Farmer2:WAITING桥接。走向北方
S_Farmer3:WAITING桥接。走向北方
S_Farmer4:WAITING桥接。走向北方
N_Farmer1:过桥第 5 步。
N_Farmer1:第 10 步过桥。
N_Farmer1:第 15 步过桥。
N_Farmer1:过桥。
NEON = 1
N_Farmer2:过桥第 5 步。
N_Farmer2:第 10 步过桥。
N_Farmer2:过桥第 15 步。
N_Farmer2:过桥。
NEON = 2
N_Farmer3:过桥第 5 步。
N_Farmer3:第 10 步过桥。
N_Farmer3:第 15 步过桥。
N_Farmer3:过桥。
NEON = 3
S_Farmer2:第 5 步过桥。
S_Farmer2:第 10 步过桥。
S_Farmer2:第 15 步过桥。
S_Farmer2:过桥。
NEON = 4
S_Farmer1:第 5 步过桥。
S_Farmer1:第 10 步过桥。
S_Farmer1:第 15 步过桥。
S_Farmer1:过桥。
NEON = 5
S_Farmer3:过桥第 5 步。
S_Farmer3:第 10 步过桥。
S_Farmer3:第 15 步过桥。
S_Farmer3:过桥。
NEON = 6
S_Farmer4:第 5 步过桥。
S_Farmer4:第 10 步过桥。
S_Farmer4:过桥步骤 15。
S_Farmer4:过桥。
NEON = 7


我的代码 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();

}
}

农夫.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  

}//下课

主要内容:

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
    }
}

Answer 1

我使用的解决方案:将交叉相关的内容移至 Bridge 文件大部分相关逻辑在 Farmer.java run() 命令中，还有一点在 Bridge.java 中的 Synchronized 函数中(保留相关计数器)。主要文件主要是文件阅读和启动农民。Farmer Threads 本质上是检查 bridge 还没有统计 2 个北方或 2 个南方的农民，如果没有，它会使用同步桥函数 upThis(Farmer f) 计算当前的一个。 Bridge 会记录有多少北方或南方农民准备就绪。在 Farmer run() 中，如果 North 或 South 命中 2，我们将信号量访问适当的一侧(信号量有 2 个资源)，然后我们等到两者都完成(使用同步的 bridge.getExited()==2)，然后退出两者其中，并重置所有计数器。现在计数器已重置，Farmer Thread while 循环可以重试。

可能不是最好的解决方案，Farmer 线程在无限 while 循环中运行，不断地重新检查条件，可能并不理想。但据我所知它是有效的，所以我想我会把它扔给任何有类似问题的人。

将把它标记为已解决和正确的解决方案，直到有人用更好的东西回应。

桥.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();

    }
}

农夫.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

主要.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
        }
    }

}