javaconcurrencyatomicatomicreference

Limiting concurrent access to a field


So in a program I'm writing I use a bi-directional breadth first search to search a graph. I do this by running 1 breadth first search in 1 thread, and one in another. Now the search is said to have found the optimal solution when it either an element from the other search is hit, or when the goal is found (which never really happens, but just in case it does for some reason..).

The problem I am running into, is that I need to save this optimal solution to a field, because I need to continue to find all of the solutions, but the field value is getting messed up because both threads hit it at the same time (I think).

Is there a way to block access to the thread who gets there last? I've tried using an AtomicReference and its compareAndSet method but that didn't do the trick. The value still gets messed up....

Btw I'm using java, and for the threads I'm using Callable objects.


Solution

  • Looks like you have a possible Livelock or Race condition that is occuring because of the random order of threads. I'd recommending taking a different approach. (otherwise at some point you will run into NP-Complete).

    The problem I am running into, is that I need to save this optimal solution to a field. because I need to continue to find all of the solutions, but the field value is getting messed up because both threads hit it at the same time (I think).

    There is a way to greatly increase your current technique. You shouldn't need to look at every solution, take a Greedy Approach and use a Paralleled version of Dijkstra's Shortest Path Algorithm.

    Shortest Path (or in your case Optimal Solution)

    Dijkstra's Algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.

    Linear Implementation

    The original algorithm Figure 1. (Source)

    Parallel PDF Algorithm Linear
    (source: iforce.co.nz)

    Java Implementations can be found Here, and Here

    Parallel Implementation

    The parallel algorithm Figure 2. (Source)

    Parallel PDF Algorithm Atomic
    (source: iforce.co.nz)

    Another idea if you are still having problems, might be to use a different concurrent data structure like Map Reduce or Hadoop instead of using Threads to search through a Binary Tree, to fix your search.