死鎖在獲取多個鎖

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; 
    } 

}