Thread Pool (Producer / Consumer)

[matt_kennelly]

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);

}
}