Thread Pool (Producer / Consumer)

Discussion in 'Java' started by matt_kennelly@hotmail.com, Apr 22, 2006.

  1. Guest

    Hi There,

    I have a sequential solution to the knight's tour program below and I'm
    trying to adapt it so it works using a producer / consumer approach. I
    need to implement the following spec.

    The program should be organised around a pool of producer/consumer
    worker threads, each retrieving work items from a shared work buffer.
    Each work item in the buffer is a partial knight's tour. Workers
    repeatedly remove a path p from the buffer. They then compute all the
    paths (up to 8 of them) that are 1 position longer than path p, and
    such that the added position does not already occur in p. If a new path
    is complete (i.e. visits all positions) and closed it is placed in a
    shared output buffer. If it is complete but not closed it is discarded.
    If it is not complete then it is put back in the work buffer. The work
    buffer initially contains a single path consisting of just (0,0). The
    work buffer should be designed as an unbounded stack (i.e. lifo).
    Processes will be delayed if they try to remove from an empty buffer.
    The buffer should be protected using locks and condition variables. You
    must code he buffer, without using any concurrent data structures from
    the Java library. The output buffer should be lockfree; there is no bar
    here on using useful classes in the Java library.

    Any suggestions (or solutions) on the best way to approach this?

    Thanks,

    Matty

    import java.util.*;

    class Position {

    static final int numRows = 3; // number of rows on board
    static final int numCols = 10; // number of columns on board

    static final Position startPosition = new Position(0,0); // start
    position
    static final Position end1 = new Position(1,2); // possible end
    positions
    static final Position end2 = new Position(2,1); // other possible end
    position

    private int row; // row number, o<=row<numRows
    private int col; // column number, o<=col<numCols


    Position(int row0,int col0) {
    row = row0; col = col0;
    }

    public boolean equals(Object obj) { // compare with another position
    if (obj==null) return false;
    Position p = (Position) obj;
    return (p.row==row && p.col==col);
    }

    Position[] knightMoves() { //list of knight's possible moves from
    here
    Position[] temp = new Position[8];
    int count = 0; // temp[0..count-1] holds results
    int[] xStep = {2, 2, -2, -2, 1, 1, -1, -1}; // potential moves are
    (row+yStep[k],col+xStep[k]) for each index k
    int[] yStep = {1, -1, 1, -1, 2, -2, 2, -2};
    for (int k=0; k<xStep.length; k++) { // check that each potential
    move stays on board
    int x = row+yStep[k];
    int y = col+xStep[k];
    if (0<= x && x<numCols && 0<=y && y<numRows) {
    temp[count] = new Position(x,y); count++;
    }
    }
    Position[] result = new Position[count];
    for (int k=0; k<count; k++)
    result[k] = temp[k];
    return result;
    }

    void putPosition() { // print position
    System.out.print("("+row+","+col+")");
    }
    }

    class Path { // non-empty path of Position's

    private Position start; // one end position in path (other is (0,0))
    private Path next; // path following start node (may be null)
    private int pathLength; // length of path

    Path(Position start0, Path next0) {
    start = start0; next = next0;
    if (next==null)
    pathLength = 1;
    else
    pathLength = 1 + next.pathLength;
    }

    boolean contains(Position p) { // does p occur in this path?
    if (start.equals(p)) return true;
    else if (next==null) return false;
    else return next.contains(p);
    }


    Position[] pathMoves() { // new positions to extend path
    return start.knightMoves();
    }

    boolean pathComplete() { // does the path cover the entire board?
    int tourLength = Position.numRows*Position.numCols;
    return pathLength == tourLength;
    }

    boolean pathClosed() { // is the path (assumed complete) closed?
    return start.equals(Position.end1) || start.equals(Position.end2);
    }

    void putPath() { // print path
    start.putPosition();
    if (next!=null) {
    System.out.print(":");
    next.putPath();
    }
    }

    }

    class KnightsTourSequential {

    static void knightsTours(Path path, LinkedList<Path> tour) {
    // Append knights tours that begin with 'path' to 'tour'
    // Assume path not complete, and does not contain any position more
    than once
    Position[] moves = path.pathMoves();
    for (Position pos : moves) {
    if (!path.contains(pos)) {
    Path newPath = new Path(pos, path);
    if (newPath.pathComplete()) {
    if (newPath.pathClosed())
    tour.add(newPath);
    }
    else
    knightsTours(newPath,tour);
    }
    }
    }

    public static void main(String[] args) {
    LinkedList<Path> tour = new LinkedList<Path>();
    knightsTours(new Path(Position.startPosition, null), tour);
    int numTours = tour.size();
    while (!tour.isEmpty()) {
    Path p = tour.poll();
    p.putPath();
    System.out.println();
    }
    String boardSize = "" + Position.numRows + "X" + Position.numCols + "
    Board:";
    System.out.println(boardSize + " Number of tours = " + numTours);

    }
    }
     
    , Apr 22, 2006
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Mark McKay
    Replies:
    0
    Views:
    453
    Mark McKay
    Dec 9, 2003
  2. Buck Turgidson

    Simple Producer/Consumer Thread Question

    Buck Turgidson, Feb 17, 2004, in forum: Java
    Replies:
    5
    Views:
    545
    Tony Dahlman
    Feb 21, 2004
  3. Usenet Poster!!!
    Replies:
    4
    Views:
    1,870
    Eric Sosman
    Sep 30, 2004
  4. Jeff
    Replies:
    4
    Views:
    684
    xarax
    Oct 22, 2004
  5. Replies:
    3
    Views:
    1,510
Loading...

Share This Page