Is there a way to stabilize direct communication between threads in java?

We have a system in which each thread (there can be dozens of them) works as an individual agent. It has its own inner variables and objects, and it monitors other threads' object开发者_JAVA百科s as well as its own) in order to make decisions. Unfortunately the system is deadlocking quite often.

Going through java tutorial (http://download.oracle.com/javase/tutorial/essential/concurrency/index.html) and through other topics here at stackoverflow, I managed to avoid some of these deadlocks by synchronizing the methods and using a monitor, as in:

Producer->monitor->Consumer.

However, not all communication between threads can be modeled like this. As I've mentioned before, at a given time one thread must have access to the objects (variables, lists, etc) of the other threads. The way it's being done now is that each thread has a list with pointers to every other thread, forming a network. By looping through this list, one thread can read all the information it needs from all the others. Even though there is no writing involved (there shouldn't be any problems with data corruption), it still deadlocks.

My question is: is there an already known way for dealing with this sort of problem? A standard pattern such as the monitor solution? Please let me know if the question needs more explanation and I'll edit the post.

Thank you in advance!

-Edit----

After getting these answers I studied more about java.concurrency and also the actor model. At the moment the problem seems to be fixed by using a reentrant lock:

http://download.oracle.com/javase/tutorial/essential/concurrency/newlocks.html

Since it can back out from an attempt to acquire the locks, it doesn't seem to have the problem of waiting forever for the them. I also started implementing an alternate version following the actor model since it seems to be an interesting solution to this case.

My main mistakes were:

-Blindly trusting synchronize

-When in the tutorial they say "the lock is on the object" what they actually mean is the whole object running the thread (in my case), not the object I would like to access.

Thank you all for the help!

Look at higher-level concurrency constructs such as the java.util.concurrent package and the Akka framework/library. Synchronizing and locking manually is a guaranteed way to fail with threads in Java.

I would recommend to apply Actor model here (kind of share nothing parallelism model).

Using this model means that all your thread don't interrupt each other explicitely and you don't need to do any synchronization at all.

Instead of making synchronization you'll use messages. When one Actor (thread) needs to get info about another Actor, it just asynchronously send a correspondent message to that Actor.

Each Actor can also respond to messages of certain types. So, when a new message comes, Actor analyses it and sends a response (or does any other activity). The key point here is that processing of incoming messages is being done synchronously (i.e. it's the only point where you need the simplest way of synchronization - just mark the method which processes messages with synchronized modifier).

When one thread needs to synchronize with many other threads in a manner that a deadlock may occur, greedily acquire all your resources, and in the case that you can't acquire a single resource out of the set, release all resources and try again.

It's an algorithm based on the dining philosophers problem.

One important thing to remember is, that you have to aquire all locks in a consistent order across all your threads, in order to avoid the following situation:

Thread 1     Thread 2
acquire A    acquire B
acquire B    acquire A

One way to do it would be to have only objects used as locks, which can be ordered.

class Lock {
    static final AtomicLong counter = new AtomicLong()
    final long id = counter.incrementAndGet();
}

which must be used like

if (lock1.id < lock2.id) {
    synchronized (lock1) {
        synchronized (lock2) {
            ...
        }
    }
} else {
    synchronized (lock2) {
        synchronized (lock1) {
            ...
        }
    }
}

Obviously, this becomes tedious soon, in particular, the more locks are involved. Using explicit ReentrantLocks might help, as it more easily allows all that stuff to be factored out into a generic “grab multiple locks method“.

Another strategy, which might be applicable for your problem, would be "hand-over-hand" locking. Consider

class Node {
    final ReentrantLock lock = new ReentrantLock();
    Node previous;
    Node next;
}

with a traversal operation like

Node start = ...;
Node successor;
start.lock.lock();
try {
    successor = start.next;
    successor.lock.lock();
} finally {
    start.lock.unlock();
}
// Here, we own the lock on start's next sibling. We could continue
// with this scheme, traversing the entire graph, at any time holding
// at most two locks: the node we come from and the node we want to 
// go to.

The above scheme still requires, that the locks are acquired in a consistent order across all threads. This means, that you can only every traverse the graph either in "forward" direction (i.e., following the thread of next pointers) or "backward" direction (going via previous). As soon as you start using both at random, things become prone to deadlocks again. This is potentially true also, if you make arbitrary changes to the graph structure, changing the positions of nodes.

How about actor model? Shortly speaking, in actor-based programming all threads work as independent actors (or, as you said, agents). Communication is done via messages. Each actor has its own message queue and processes these messages one by one. This model is implemented in a Scala programming language, and one of its frameworks - Akka - may be used from Java.

What I do is use ExecutorServices for each Thread Pool. When you want another thread to do work, you pass it copies (or immutable data) of all the information it will need. This way you have state which is local to a thread or thread pool and you have information which is passed to another thread. i.e. you never pass mutable state to another thread. This avoid the need to ever lock another threads data.