Re: Thread Pools (producer / consumer)

Matty wrote:
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?

Are you asking specifically about the shared work buffer issues?
Are you asking for suggestions concerning the design of the pool
of threads so that they do not consistently produce the same answer
for a given path?

Are you concerned about the race conditions encountered when
attempting to determine if a given path already appears in path p?

Please be more specific about your query.

Jim Rogers