基本介紹
- 中文名：臨界資源互斥訪問
- 外文名：Access critical resource
- 套用：計算機技術
- 定義：臨界資源訪問以互斥方式實現同步
- 系統：分散式系統
- 算法：完全中心式、局部中心式
分散式互斥的發展歷史,完全中心式算法,局部中心式算法,局部分散式算法,完全分散式算法,分散式互斥的研究成果,理論較充實,算法較豐富,套用廣泛,緊跟時代,
分散式互斥的發展歷史
分散式互斥是隨著分散式系統的出現而出現的，並隨著分散式系統理論發展而發展。因此，和分散式系統的體系結構發展史類似，分散式互斥的發展經歷了如下幾個發展階段：
完全中心式算法
在該類算法中，一個節點被指定為控制(裁決)節點，它控制對所有共享對象的訪問。當任何進程請求對一個臨界資源進行訪問時，就向本地資源控制進程傳送一個請求訊息，該進程接著向控制節點傳送一個請求訊息。當共享對象可用時，將返回一個應答訊息。當進程結束使用資源後，向控制節點傳送一個釋放訊息。這類算法有兩個共同點，其一是只有控制節點能控制資源的分配，其二是所有需要的信息都集中在控制節點中，包括所有資源的實體和位置以及每個資源的分配狀態。
完全中心式算法實現簡單，控制也很方便，但存在以下缺點:如果控制節點崩潰，則互斥機制終止，同時由於所有請求資源的進程都需與控制節點交換訊息，因此，控制節點可能存在通信瓶頸。
局部中心式算法
由於完全中心式算法可能出現的控制節點容錯問題與通信瓶頸問題，人們採取了相應措施以期解決或緩解這些問題給整個系統帶來的影響。因此出現了局部中心式算法。局部中心式算法是將各臨界資源按一定規則分為幾個區域，每個區域包含一定數量的臨界資源和一個中心控制點。任何需要請求某臨界資源的進程都需向該臨界資源所在區域的中心控制節點傳送請求訊息並由該控制節點安排進程訪問臨界資源的次序。該類算法具有多個控制點，各控制點間互不干涉，每一個控制節點故障只影響系統內節點對該控制節點管理區域內的臨界資源訪問，不會對非該區域內資源的訪問造成影響。因此可以緩解完全中心式算法的控制節點容錯問題與通信瓶頸問題。
局部分散式算法
局部中心式算法雖然緩解了其完全中心式算法的控制節點容錯及通信瓶頸問題，但並未使這些問題得到解決。特別是隨著通信技術的發展，節點間的通信頻寬已經能夠較大程度滿足互斥的訊息通信要求，因此使中心式算法的控制節點容錯變得更加重要。因此，人們將局部中心式算法中互不干涉的控制節點改為互相備份的方式。當一個控制節點失效時，其控制的資源將轉向其備份的控制節點，使得互斥能夠繼續進行。該類算法繼續發展，出現了多點共同決策的資源訪問模式，即任何一次的關鍵資源訪問，不再是由唯一的一個控制節點決定，而是由所有控制節點共同決定。因此申請訪問臨界資源的節點不再只是向唯一的資源控制節點傳送請求訊息，而是需要向所有控制節點傳送請求訊息。當所有控制節點都同意申請節點的請求時，申請節點獲得臨界資源訪問機會。因為多點控制使得節點間需要交換的訊息數量增加，同樣可能出現通信瓶頸，因此該類算法是在通信技術發展到一定階段的產物。該類算法在解決控制節點容錯方面具有較好的性質。
完全分散式算法
局部分散式互斥算法雖然使得分散式互斥的控制節點容錯問題得到了一定解決，但其容錯能力不高，並增加了互斥所需的訊息量。因此，Lamport提出了完全分散式互斥的概念，並對分散式系統的訊息排序進行了深入研究。Maekawa對完全分散式算法的對稱性特性作出了如下刻畫。
1、所有節點具有相同的信息量;
2、所有節點只能掌握完整系統的部分情況，且必須基於這一信息作出決定;
3、所有節點對最終決定承擔相同責任;
4、所有節點在對最終決定的影響上付出相同的努力;
5、一個節點的故障從整體上不會導致整個系統的崩潰;
6、不存在系統範圍的共同時鐘來規範時間的定位與排序。
其中第2點是屬於可選項，因為有些分散式互斥算法要求任何節點都要將自己所知道的所有信息通告系統內其他節點，這樣，如果忽略通信延遲，則任何節點都將知道系統的全局信息。當然，由於通信延遲的影響，節點不可能知道全局最新信息，因此，也可以說任何節點只能掌握系統的局部信息。
分散式互斥的研究成果
理論較充實
Lamport給出了全分散式系統中事件的邏輯時鐘排序算法，並給出了相應的全分散式互斥算法，為以後的分散式互斥研究及分散式互斥算法設計提供了理論基礎。Maekawa將有限射影平面理論引入請求集的設計，並得出了分散式互斥算法的訊息複雜度最小為
的結論，為設計分散式互斥算法的性能評估提供了度量標準。
算法較豐富
在Lamport與Maekawa算法的基礎上，人們提出了數十種分散式互斥算法，它們集中解決了競爭分散式互斥算法的請求集生成、減少分散式互斥算法的訊息複雜度、同步延遲、提高分散式互斥算法的容錯能力等問題，給分散式互斥算法的套用提供了豐富的選擇。
套用廣泛
分散式互斥算法由於是對臨界資源的控制，因此，凡是分散式系統中存在對臨界資源的控制問題，都可以用分散式互斥算法解決。因此，分散式互斥算法不僅在分散式計算機系統中得到廣泛套用，在分散式控制，分散式決策等等方面都有非常廣闊的套用前景。
緊跟時代
分散式互斥算法與分散式系統的結構理論發展是分不開的。當市場上或學術界以研究主從式分散式系統為主時，人們就會著重研究主從式的分散式互斥算法。當市場上或學術界以研究對等網路為主時，對等的全分布時分散式互斥算法會成為人們研究的重點。
