死锁在获取多个锁

Question

我有下面的代码（代码是在Java中，但我已经试图减少尽可能多的混乱越好）：

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

} 

这段代码有进入的可能性与以下调用序列的死锁：

Thread1: st1.write() 
Thread1: st1.write() invokes globalRM.request() 
Thread2: st2.write() 
Thread1: globalRM.request() tries to invoke st2.returnResource(), but gets blocked because Thread2 is holding a lock on st2. 
Thread2: st2.write() tries to invoke globalRM.request(), but gets blocked because globalRM's lock is with Thread1 

Thread3: st2.read(), gets blocked. 

我该如何解决这种死锁？我想了一会儿，看到有一种有序的锁方式可以用来获取锁，但我想不出这样的解决方案。问题在于，资源管理器是全局性的，而状态是特定于每个作业的（每个作业都有一个顺序的ID，如果有某种方式可以使用顺序来获取锁，则可用于排序）。

Answer 1

任何死锁的答案是以相同的顺序获取相同的锁。你只需要找出一个方法来做到这一点。

Answer 2

有一些选项来避免这种情况，每个人都有其优点和缺点：

1）使用单一的锁对象所有实例。这种方法实施起来很简单，但是将您限制在一个线程来获得锁定。如果同步块很短并且可扩展性不是一个大问题（例如，桌面应用程序又称为非服务器），则这可能是合理的。其主要卖点是实施简单。

2.）使用有序锁定 - 这意味着无论何时您必须获得两个或更多锁定，请确保它们的获取顺序相同。这样做容易得多，可能需要对代码库进行大量更改。

3.）完全摆脱锁。使用java.util.concurrent（.atomic）类可以实现多线程数据结构而不会阻塞（通常使用compareAndSet-flavor方法）。这当然需要修改代码库，并且需要对结构进行一些重新思考。通常需要重新编写代码库的关键部分。

4.）当你使用不可变的类型和对象时，很多问题会消失。与原子（3.）方法很好地结合来实现可变超级结构（通常实现为拷贝更改）。

为了给出任何建议，您需要知道更多有关锁的保护内容的更多细节。

---编辑---

我需要一个无锁的设置实现，该代码示例说明了它的长处和短处。我没有实现iterator（）作为快照，实现它来抛出ConcurrentModificationException并且支持remove（）会稍微复杂一些，我不需要它。一些引用的实用工具类我没有发布（我认为它完全明显是什么缺少参考作品）。

我希望它至少有一点作为一个起点如何使用AtomicReferences。

/** 
* Helper class that implements a set-like data structure 
* with atomic add/remove capability. 
* 
* Iteration occurs always on a current snapshot, thus 
* the iterator will not support remove, but also never 
* throw ConcurrentModificationException. 
* 
* Iteration and reading the set is cheap, altering the set 
* is 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 the set contains the element. 
    */ 
    @Override 
    public boolean contains(final Object object) { 
     final Object[] array = reference.get(); 
     for (final Object element : array) { 
      if (element.equals(object)) 
       return true; 
     } 
     return false; 
    } 

    /** 
    * Adds an element to the set. Returns true if the element was added. 
    * 
    * If element is NULL or already in the set, no change is made to the 
    * set and false is 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 is already in set 
      for (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 all the given elements to the set. 
    * Semantically this is the same a calling add() repeatedly, 
    * but the whole operation is 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:  for (final Object element : collection) { 
       if (element == null) 
        continue; 
       for (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 an element from the set. Returns true if the element was removed. 
    * 
    * If element is NULL not in the set, no change is made to the set and 
    * false is 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 i = 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 - i - 1); 
      } 
      if (reference.compareAndSet(expect, update)) 
       return true; 
     } 
    } 

    /** 
    * Removes all entries from the set. 
    */ 
    @Override 
    public void clear() { 
     reference.set(Primitives.EMPTY_OBJECT_ARRAY); 
    } 

    /** 
    * Gets an estimation how many elements are in the set. 
    * (its an estimation as it only returns the current size 
    * and that may change at any 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 a new array of a's runtime type, but my 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; 
    } 

}