Konstantin Milyutin
Konstantin Milyutin

Reputation: 12366

Concurrent game of life using CyclicBarrier

I have a 2D array that represents Game of Life board. N threads work on their own part of the array, creating the next generation.

When all N locks are done with their part, I print the current generation and sleep some time before going to the next generation. It is achieved by using CyclicBarrier.

Although the program works, I think the printing thread might see stale array cells because writes to the array are not synchronized. Internally CyclicBarrier uses lock, so it might trigger happens-before, but I'm not sure about it.

The only solution I see is to lock on Board methods. But I don't want to use locks because each thread has its own dedicated part of the array and it would create unnecessary contention on the lock.

public class GameOfLife {

    private final Worker[] workers;
    private final long duration;
    private final AtomicBoolean done;
    private Board current;

    public GameOfLife(Board initialBoard, long duration) throws InterruptedException {
        initialBoard.print();
        this.current = new Board(initialBoard);
        this.duration = duration;
        this.done = new AtomicBoolean(false);
        int cores = Runtime.getRuntime().availableProcessors();
        this.workers = new Worker[cores];

        CyclicBarrier barrier = new CyclicBarrier(cores, () -> {
            current.print();

            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
                GameOfLife.this.done.set(true);
                return;
            }

            Board oldBoard = current;
            current = new Board(current);

            for (Worker worker : this.workers) {
                worker.setOldBoard(oldBoard);
                worker.setNewBoard(current);
            }
        });

        int partitionSize = (initialBoard.getRows() / cores) + 1;
        for (int core = 0; core < cores; core++) {
            workers[core] = new Worker(barrier, initialBoard, current, done, core * partitionSize, Math.min(initialBoard.getRows(), (core + 1) * partitionSize));
        }
    }

    public void start() {
        for (Worker worker : this.workers) {
            new Thread(worker).start();
        }

        new Timer(true).schedule(new TimerTask() {
            @Override
            public void run() {
                GameOfLife.this.done.set(true);
            }
        }, this.duration);
    }

    public static void main(String[] args) throws InterruptedException {
        boolean[][] initialBoard = new boolean[27][27];
        for (int row = 10; row < 20; row++) {
            initialBoard[row][15] = true;
        }

        GameOfLife e = new GameOfLife(new Board(initialBoard), 40000);
        e.start();
    }
}

class Worker implements Runnable {

    private final CyclicBarrier barrier;
    private final AtomicBoolean done;
    private volatile Board oldBoard;
    private volatile Board newBoard;
    private final int rowStart;
    private final int rowEnd;

    public Worker(CyclicBarrier barrier, Board oldBoard, Board newBoard, AtomicBoolean done, int rowStart, int rowEnd) {
        this.oldBoard = oldBoard;
        this.newBoard = newBoard;
        this.done = done;
        this.rowStart = rowStart;
        this.rowEnd = rowEnd;
        this.barrier = barrier;
    }

    @Override
    public void run() {
        while (!done.get()) {
            for (int row = rowStart; row < rowEnd; row++) {
                for (int col = 0; col < this.oldBoard.getCols(); col++) {
                    int neighbors = this.oldBoard.countNeighbors(row, col);

                    if (this.oldBoard.isAlive(row, col)) {
                        if (neighbors < 2 || neighbors > 3) {
                            this.newBoard.kill(row, col);
                        }
                    } else {
                        if (neighbors == 3) {
                            this.newBoard.create(row, col);
                        }

                    }
                }
            }

            try {
                barrier.await();
            } catch (Exception e) {
                System.out.println(e);
                return;
            }
        }
    }

    public void setOldBoard(Board oldBoard) {
        this.oldBoard = oldBoard;
    }

    public void setNewBoard(Board newBoard) {
        this.newBoard = newBoard;
    }
}

class Board {
    private final boolean[][] board;

    Board(Board another) {
        this(another.board);
    }

    Board(boolean[][] aBoard) {
        this.board = new boolean[aBoard.length][aBoard[0].length];

        for (int row = 0; row < aBoard.length; row++) {
            this.board[row] = Arrays.copyOf(aBoard[row], aBoard[row].length);
        }
    }

    public int countNeighbors(int row, int col) {
        int counter = 0;

        int[][] possibleNeighbors = {{row - 1, col - 1}, {row, col - 1}, {row + 1, col - 1}, {row - 1, col},
                {row + 1, col}, {row - 1, col + 1}, {row, col + 1}, {row + 1, col + 1}};

        for (int[] possibleNeighbor : possibleNeighbors) {
            final int r = possibleNeighbor[0];
            final int c = possibleNeighbor[1];
            if (insideBoard(r, c) && this.board[r][c]) {
                counter++;
            }
        }

        return counter;
    }

    private boolean insideBoard(int row, int col) {
        return row >= 0 && row < this.board.length && col >= 0 && col < this.board[row].length;
    }

    public int getRows() {
        return this.board.length;
    }

    public int getCols() {
        return this.board[0].length;
    }

    public boolean isAlive(int row, int col) {
        return this.board[row][col];
    }

    public void kill(int row, int col) {
        this.board[row][col] = false;
    }

    public void create(int row, int col) {
        this.board[row][col] = true;
    }

    public void print() {
        for (int row = 0; row < this.board.length; row++) {
            for (int col = 0; col < this.board[row].length; col++) {
                System.out.print(this.board[row][col] ? "*" : " ");
            }

            System.out.println();
        }
    }
}

Upvotes: 0

Views: 259

Answers (0)

Related Questions