java - Deadlock in acquiring multiple locks -

i have following code snippet (the code in java, have tried reduce clutter possible):

class state {     public synchronized read() {    }     public synchronized write(resourcemanager rm) {        rm.request();    }     public synchronized returnresource() {    } }  state st1 = new state(); state st2 = new state(); state st3 = new state();    class resourcemanager {    public syncronized request() {        st2 = findidlestate();        return st2.returnresource();    } }   resourcemanager globalrm = new resourcemanager();   thread1()  {     st1.write(globalrm); }   thread2()  {     st2.write(globalrm);  }  thread3() {     st1.read();  } 

this code snippet has possibility of entering deadlock following sequence of calls:

thread1: st1.write() thread1: st1.write() invokes globalrm.request() thread2: st2.write() thread1: globalrm.request() tries invoke st2.returnresource(), gets blocked because thread2 holding lock on st2. thread2: st2.write() tries invoke globalrm.request(), gets blocked because globalrm's lock thread1  thread3: st2.read(), gets blocked. 

how solve such deadlock? thought while see there sort of ordered locks approach can use acquire locks, cannot think of such solution. problem that, resource manager global, while states specific each job (each job has id sequential can used ordering if there way use order lock acquisition).

there options avoid scenario, each has advantages , drawbacks:

1.) use single lock object all instances. approach simple implement, limits 1 thread aquire lock. can reasonable if synchronized blocks short , scalability not big issue (e.g. desktop application aka non-server). main selling point of simplicity in implementation.

2.) use ordered locking - means whenever have aquire 2 or more locks, ensure order in aquired same. thats easier said done , can require heavy changes code base.

3.) rid of locks completely. java.util.concurrent(.atomic) classes can implement multithreaded data structures without blocking (usually using compareandset-flavor methods). requires changes code base , requires rethinking of structures. reqiures rewrite of critical portions of code base.

4.) many problems disappear when consequently use immutable types , objects. combines atomic (3.) approach implement mutable super-structures (often implemented copy-on-change).

to give recommendation 1 need know lot more details protected locks.

--- edit ---

i needed lock-free set implementation, code sample illustrates strengths , weaknesses. did implement iterator() snapshot, implementing throw concurrentmodificationexception , support remove() little more complicated , had no need it. of referenced utility classes did not post (i think obvious missing referenced pieces do).

i hope @ least little useful starting point how work atomicreferences.

/**  * helper class implements set-like data structure  * atomic add/remove capability.  *   * iteration occurs on current snapshot,  * iterator not support remove, never  * throw concurrentmodificationexception.  *   * iteration , reading set cheap, altering set  * expensive.  */ public final class atomicarrayset<t> extends abstractset<t> {      protected final atomicreference<object[]> reference =         new atomicreference<object[]>(primitives.empty_object_array);      public atomicarrayset() {     }      /**      * checks if set contains element.      */     @override     public boolean contains(final object object) {         final object[] array = reference.get();         (final object element : array) {             if (element.equals(object))                 return true;         }         return false;     }      /**      * adds element set. returns true if element added.      *       * if element null or in set, no change made      * set , false returned.      */     @override     public boolean add(final t element) {         if (element == null)             return false;         while (true) {             final object[] expect = reference.get();             final int length = expect.length;             // determine if element in set             (int i=length-1; i>=0; --i) {                 if (expect[i].equals(element))                     return false;             }             final object[] update = new object[length + 1];             system.arraycopy(expect, 0, update, 0, length);             update[length] = element;             if (reference.compareandset(expect, update))                 return true;         }     }      /**      * adds given elements set.      * semantically same calling add() repeatedly,      * whole operation made atomic.      */     @override     public boolean addall(final collection<? extends t> collection) {         if (collection == null || collection.isempty())             return false;         while (true) {             boolean modified = false;             final object[] expect = reference.get();             int length = expect.length;             object[] temp = new object[collection.size() + length];             system.arraycopy(expect, 0, temp, 0, length); eloop:      (final object element : collection) {                 if (element == null)                     continue;                 (int i=0; i<length; ++i) {                     if (element.equals(temp[i])) {                         modified |= temp[i] != element;                         temp[i] = element;                         continue eloop;                     }                 }                 temp[length++] = element;                 modified = true;             }             // check if content did not change             if (!modified)                 return false;             final object[] update;             if (temp.length == length) {                 update = temp;             } else {                 update = new object[length];                 system.arraycopy(temp, 0, update, 0, length);             }             if (reference.compareandset(expect, update))                 return true;         }     }       /**      * removes element set.  returns true if element removed.      *       * if element null not in set, no change made set ,      * false returned.      */     @override     public boolean remove(final object element) {         if (element == null)             return false;         while (true) {             final object[] expect = reference.get();             final int length = expect.length;             int = length;             while (--i >= 0) {                 if (expect[i].equals(element))                     break;             }             if (i < 0)                 return false;             final object[] update;             if (length == 1) {                 update = primitives.empty_object_array;             } else {                 update = new object[length - 1];                 system.arraycopy(expect, 0, update, 0, i);                 system.arraycopy(expect, i+1, update, i, length - - 1);             }             if (reference.compareandset(expect, update))                 return true;         }     }      /**      * removes entries set.      */     @override     public void clear() {         reference.set(primitives.empty_object_array);     }      /**      * gets estimation how many elements in set.      * (its estimation returns current size      * , may change @ time).      */     @override     public int size() {         return reference.get().length;     }      @override     public boolean isempty() {         return reference.get().length <= 0;     }      @suppresswarnings("unchecked")     @override     public iterator<t> iterator() {         final object[] array = reference.get();         return (iterator<t>) arrayiterator.get(array);     }      @override     public object[] toarray() {         final object[] array = reference.get();         return primitives.clonearray(array);     }      @suppresswarnings("unchecked")     @override     public <u extends object> u[] toarray(final u[] array) {         final object[] content = reference.get();         final int length = content.length;         if (array.length < length) {             // make new array of a's runtime type, contents:             return (u[]) arrays.copyof(content, length, array.getclass());         }             system.arraycopy(content, 0, array, 0, length);         if (array.length > length)             array[length] = null;         return array;     }  }