併發訪問組對象

Question

我想開發一個由線程池組成的應用程序，使用工作 - 竊取算法來同時執行任務。

這些任務

• 訪問一組預定義對象;
• 必須「原子地」獲取它在實際運行之前訪問的所有對象的讀/寫權限;
• 完成後（並保證最終完成）釋放它們獲取的對象。

解決此問題的一種可能方法是讓每個線程一次選取一個任務，然後嘗試使用預定義的順序鎖定每個對象。如果至少有一個失敗，則釋放所有鎖，然後繼續執行另一個任務。

然而，這種方法增加了大對象依賴性的任務匱乏的可能性，甚至可能導致活鎖。

是否有另一種獲取一組鎖的同時最大化併發性的方法？ （沒有全局鎖定）或者可能以不再需要的方式更改系統？ 如果是這樣，有什麼好的論文呢？

ps：正如thiton回答，這是「餐飲哲學家」問題的一個普遍版本。我正在尋找非集中式解決方案，特別是在高負載情況下運行良好的算法（添加和刪除任務）。

Answer 1

你的問題叫做Dining Philosophers。你應該在這個關鍵字下找到你需要的任何數量的文獻:-)。

Answer 2

如果某個任務試圖鎖定對象僅在某個時候失敗，則可能是另一個任務將無法鎖定對象，因爲此時第一個任務擁有該對象。

我想我會在最初嘗試獲取鎖時使用全局鎖，也可能在最終釋放它們時使用全局鎖。

當一個簡單的解決方案在實踐中被證明不足時，我會擔心最大併發性。

Answer 3

訂購資源是一種有效的方法。想到的另一個直截了當的方法是引入一個持有關於資源可用性信息的共享仲裁器。任務將通過仲裁器以「獲取（r1，r2，...，rn）」的單個原子步驟鎖定他們需要的所有資源，並通過「release（r1，r2，...，rn）」類似地釋放它們。

如果可以滿足「獲取」請求A，則仲裁器將確保沒有其他任務可以獲取A持有的任何資源，直到A將其釋放回來。

仲裁器可以使用多種策略來滿足傳入的請求：

1. 拒絕請求不能立即滿足 - 任務將不得不重新嘗試。這打開了活鎖和飢餓的大門。
2. 將所有傳入請求保留在一個隊列中，並以頭部請求所需的資源爲FIFO提供服務。
3. 將所有不滿意的請求保留在列表中（不會阻塞他們所需的資源），並在每次釋放一些資源時遍歷它們（可能優先考慮較舊的請求），以查找可以滿足的請求。