在Java中设计一个多线程矩阵

Question

我有一个矩阵，它实现了John Conway的生命模拟器，其中每个单元格代表生命或缺乏生命。

每个生命周期遵循以下规则：

1.任何活着的细胞如果周围活细胞少于两个，则会死亡，就像人口不足一样。

2.任何活着的细胞如果周围有两个或三个活细胞，则会存活到下一代。

3.任何活着的细胞如果周围有三个以上的活细胞，则会死亡，就像过度拥挤一样。

4.任何死亡的细胞如果周围恰好有三个活细胞，则会成为活细胞，就像繁殖一样。

每个单元格都将有一个线程，按照上述规则执行更改。

我已经实现了这些类：

import java.util.Random;

public class LifeMatrix {
    Cell[][] mat;
    public Action currentAction = Action.WAIT_FOR_COMMAND;
    public Action changeAction;

    public enum Action {
        CHECK_NEIGHBORS_STATE,
        CHANGE_LIFE_STATE,
        WAIT_FOR_COMMAND
    }

    // creates a life matrix with all cells alive or dead or random between dead or alive
    public LifeMatrix(int length, int width) {
        mat = new Cell[length][width];

        for (int i = 0; i < length; i++) { // populate the matrix with cells randomly alive or dead
            for (int j = 0; j < width; j++) {
                mat[i][j] = new Cell(this, i, j, (new Random()).nextBoolean());
                mat[i][j].start();
            }

        }
    }

    public boolean isValidMatrixAddress(int x, int y) {
        return x >= 0 && x < mat.length && y >= 0 && y < mat[x].length;
    }

    public int getAliveNeighborsOf(int x, int y) {
        return mat[x][y].getAliveNeighbors();
    }

    public String toString() {
        String res = "";
        for (int i = 0; i < mat.length; i++) { // populate the matrix with cells randomly alive or
                                               // dead
            for (int j = 0; j < mat[i].length; j++) {
                res += (mat[i][j].getAlive() ? "+" : "-") + "  ";
            }
            res += "\n";
        }
        return res;
    }


    public void changeAction(Action a) {
        // TODO Auto-generated method stub
        currentAction=a;
        notifyAll();                 //NOTIFY WHO??
    }
}

---

/**
 * Class Cell represents one cell in a life matrix
 */
public class Cell extends Thread {
    private LifeMatrix ownerLifeMat; // the matrix owner of the cell
    private boolean alive;
    private int xCoordinate, yCoordinate;

    public void run() {
        boolean newAlive;

        while (true) {
            while (! (ownerLifeMat.currentAction==Action.CHECK_NEIGHBORS_STATE)){
                synchronized (this) {//TODO to check if correct


                try {
                    wait();
                } catch (InterruptedException e) {
                    System.out.println("Interrupted while waiting to check neighbors");
                }}
            }
            // now check neighbors
            newAlive = decideNewLifeState();

            // wait for all threads to finish checking their neighbors
            while (! (ownerLifeMat.currentAction == Action.CHANGE_LIFE_STATE)) {
                try {
                    wait();
                } catch (InterruptedException e) {
                    System.out.println("Interrupted while waiting to change life state");
                };
            }

            // all threads finished checking neighbors now change life state
            alive = newAlive;
        }
    }

    // checking the state of neighbors and
    // returns true if next life state will be alive
    // returns false if next life state will be dead
    private boolean decideNewLifeState() {
        if (alive == false && getAliveNeighbors() == 3)
            return true; // birth
        else if (alive
                && (getAliveNeighbors() == 0 || getAliveNeighbors() == 1)
                || getAliveNeighbors() >= 4)
            return false; // death
        else
            return alive; // same state remains

    }

    public Cell(LifeMatrix matLifeOwner, int xCoordinate, int yCoordinate, boolean alive) {
        this.ownerLifeMat = matLifeOwner;
        this.xCoordinate = xCoordinate;
        this.yCoordinate = yCoordinate;
        this.alive = alive;
    }

    // copy constructor
    public Cell(Cell c, LifeMatrix matOwner) {
        this.ownerLifeMat = matOwner;
        this.xCoordinate = c.xCoordinate;
        this.yCoordinate = c.yCoordinate;
        this.alive = c.alive;
    }

    public boolean getAlive() {
        return alive;
    }

    public void setAlive(boolean alive) {
        this.alive = alive;
    }

    public int getAliveNeighbors() { // returns number of alive neighbors the cell has
        int res = 0;
        if (ownerLifeMat.isValidMatrixAddress(xCoordinate - 1, yCoordinate - 1) && ownerLifeMat.mat[xCoordinate - 1][yCoordinate - 1].alive)
            res++;
        if (ownerLifeMat.isValidMatrixAddress(xCoordinate - 1, yCoordinate) && ownerLifeMat.mat[xCoordinate - 1][yCoordinate].alive)
            res++;
        if (ownerLifeMat.isValidMatrixAddress(xCoordinate - 1, yCoordinate + 1) && ownerLifeMat.mat[xCoordinate - 1][yCoordinate + 1].alive)
            res++;
        if (ownerLifeMat.isValidMatrixAddress(xCoordinate, yCoordinate - 1) && ownerLifeMat.mat[xCoordinate][yCoordinate - 1].alive)
            res++;
        if (ownerLifeMat.isValidMatrixAddress(xCoordinate, yCoordinate + 1) && ownerLifeMat.mat[xCoordinate][yCoordinate + 1].alive)
            res++;
        if (ownerLifeMat.isValidMatrixAddress(xCoordinate + 1, yCoordinate - 1) && ownerLifeMat.mat[xCoordinate + 1][yCoordinate - 1].alive)
            res++;
        if (ownerLifeMat.isValidMatrixAddress(xCoordinate + 1, yCoordinate) && ownerLifeMat.mat[xCoordinate + 1][yCoordinate].alive)
            res++;
        if (ownerLifeMat.isValidMatrixAddress(xCoordinate + 1, yCoordinate + 1) && ownerLifeMat.mat[xCoordinate + 1][yCoordinate + 1].alive)
            res++;
        return res;
    }

}

---

public class LifeGameLaunch {

    public static void main(String[] args) {
        LifeMatrix lifeMat;
        int width, length, populate, usersResponse;
        boolean userWantsNewGame = true;
        while (userWantsNewGame) {
            userWantsNewGame = false; // in order to finish the program if user presses
                                      // "No" and not "Cancel"
            width = Integer.parseInt(JOptionPane.showInputDialog(
                    "Welcome to John Conway's life simulator! \n"
                            + "Please enter WIDTH of the matrix:"));
            length = Integer.parseInt(JOptionPane.showInputDialog(
                    "Welcome to John Conway's life simulator! \n"
                            + "Please enter LENGTH of the matrix:"));


            lifeMat = new LifeMatrix(length, width);

            usersResponse = JOptionPane.showConfirmDialog(null, lifeMat + "\nNext cycle?");
            while (usersResponse == JOptionPane.YES_OPTION) {
                if (usersResponse == JOptionPane.YES_OPTION) {
                    lifeMat.changeAction(Action.CHECK_NEIGHBORS_STATE);
                } 
                else if (usersResponse == JOptionPane.NO_OPTION) {
                    return;
                }
                // TODO leave only yes and cancel options
                usersResponse = JOptionPane.showConfirmDialog(null, lifeMat + "\nNext cycle?");
            }
            if (usersResponse == JOptionPane.CANCEL_OPTION) {
                userWantsNewGame = true;
            }
        }
    }
}

我遇到的问题是如何同步线程： 每个单元格（一个线程）只有在所有线程都检查完邻居后才能改变其生死状态。用户将通过点击按钮调用每个下一个生命周期。

我的逻辑，从run()方法可以理解，是让每个单元格（线程）运行并等待正确的操作状态，该状态在LifeMatrix类中由变量currentAction表示，并继续执行所需的操作。

我遇到的困难是如何向线程传递这些消息，以知道何时等待和何时执行下一个操作？

欢迎提出任何更改程序设计的建议，只要每个单元格都使用单独的线程实现即可！

- Max Segal

---

如果目标是学习如何管理线程，这是一个不错的练习。如果目标是创建一个良好的工作应用程序，那么最好使用单个线程来更新单元格。 - MadConan

这确实是一个用于练习线程同步的大学练习题...任何粗略的指导都可以...我该如何让所有线程等待，直到LifeMatrix对象中的currentAction变量发生改变？ - Max Segal

Answer 1

我会使用两个 Phaser 来解决这个问题。

您可以使用一个 Phaser 控制周期，使用另一个 Phaser 同步单元格，当它们确定是否存活时。

public class Cell extends Thread {
    private LifeMatrix ownerLifeMat; // the matrix owner of the cell
    private boolean alive;
    private int xCoordinate, yCoordinate;

    // Phaser that controls the cycles
    private Phaser cyclePhaser;

    // Phaser for cell synchronisation
    private Phaser cellPhaser;

    public Cell(LifeMatrix matLifeOwner, Phaser cyclePhaser, Phaser cellPhaser,
            int xCoordinate, int yCoordinate, boolean alive) {
        this.ownerLifeMat = matLifeOwner;
        this.cyclePhaser = cyclePhaser;
        this.cellPhaser = cellPhaser;
        this.xCoordinate = xCoordinate;
        this.yCoordinate = yCoordinate;
        this.alive = alive;

        // Register with the phasers
        this.cyclePhaser.register();
        this.cellPhaser.register();
    }

    public void run() {
        boolean newAlive;

        while (true) {
            // Await the next cycle
            cyclePhaser.arriveAndAwaitAdvance();

            // now check neighbors
            newAlive = decideNewLifeState();

            // Wait until all cells have checked their state
            cellPhaser.arriveAndAwaitAdvance();

            // all threads finished checking neighbors now change life state
            alive = newAlive;
        }
    }

    // Other methods redacted
}

你可以通过让主线程在cyclePhaser上注册并通过arrive来控制周期，以便开始下一个周期。

- Raniz

---

只是好奇，似乎在这种情况下使用“屏障”会更简单（实际上我们只需要一个 Phaser/Barrier），为什么要选择 Phaser（和 2 个 Phasers）作为解决方案呢？ - Adrian Shum

使用数字2的原因是主线程需要在进入下一个周期时到达，但在单元格检查状态时没有必要这样做。使用Phaser而不是CyclicBarrier的原因是我更喜欢它（静态参与者数量与（取消）注册相比），并且它具有arrive方法，该方法不等待其他线程。 Phaser更加灵活，我认为CyclicBarrier几乎已经过时了。 - Raniz

Answer 2

使用CyclicBarrier应该很容易理解：

(更新为使用2个障碍，并利用内部类使单元格看起来更短更清洁)

伪代码：

public class LifeMatrix {
    private CyclicBarrier cycleBarrier;
    private CyclicBarrier cellUpdateBarrier;
    //.....

    public LifeMatrix(int length, int width) {
        cycleBarrier = new CyclicBarrier(length * width + 1);
        cellUpdateBarrier = new CyclicBarrier(length * width);

        // follow logic of old constructor
    }

    public void changeAction(Action a) {
        //....
        cycleBarrier.await()
    }

    // inner class for cell
    public class Cell implements Runnable {
        // ....

        @Override
        public void run() {
             while (...) {
                 cycleBarrier.await();  // wait until start of cycle
                 boolean isAlive = decideNewLifeState();
                 cellUpdateBarrier.await();  // wait until everyone completed
                 this.alive = isAlive;
             }
        }
    }
}

- Adrian Shum

---

这将使单元格连续运行，不会暂停等待用户启动下一个周期。 - Raniz

好发现 :P 我在编写时忘记了这一点。但是可以通过更改为 CyclicBarrier barrier = new CyclicBarrier(noOfCells + 1); 并且当用户启动每个周期时，执行 barrier.await(); barrier.await(); 来轻松完成。(或者如果 OP 想要的话，将其分成2个屏障，在这方面更清晰) - Adrian Shum

是的，这就是我在我的答案中使用两个“Phaser”的原因——我不喜欢双重调用await()。在这种情况下它可以正常工作，但如果单元格执行某些需要更长时间的高级操作，主线程会在等待单元格时被锁定——在真实的应用程序中这意味着UI将会被冻结。 - Raniz

好的，我可以更新我的答案，使用2个屏障 :) 这应该解决问题。 - Adrian Shum