《雲數據管理：挑戰與機遇》2.1.3　互斥和仲裁集

本節書摘來自華章出版社《雲數據管理》一書中的第2章，第1節，作者迪衛艾肯特·阿格拉沃爾，更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看

互斥和仲裁集

互斥是並發進程訪問共享資源時涉及的一個基本概念。互斥是操作係統中的一個重要操作，後來也被擴展到數據庫中。互斥可以按照如下方式進行定義：給定一個進程集合和一個單獨的資源，開發一種協議，該協議可以確保在同一時間，一個資源隻能被一個進程進行排他性訪問。針對集中式係統和分布式係統都已經提出了多種解決方案。針對分布式互斥問題的一種簡單的集中式解決方案可以設計如下：指定一個進程為協調者，當進程需要訪問資源時，發送一個請求消息給協調者。協調者維護一個等待請求隊列。當協調者接收一個請求消息時，檢查該隊列是否為空，如果隊列為空，協調者就為請求客戶端發送一個回複消息，請求客戶端就可以訪問共享資源。否則，請求消息就被添加到等待請求隊列中。進程在共享資源上執行完成以後，向協調者發送一個釋放消息。接收到釋放消息以後，協調者從隊列中移除請求，然後為其他等待的請求檢查隊列。該協議已經被Lamport[1978]擴展成分布式協議，很多其他研究人員對該協議進行了優化。

該基本協議的普遍應用需要係統中所有進程的參與。為了克服障礙，Gifford提出了仲裁集的概念。比較重要的發現是任意兩個請求都應該有一個共同的進程來充當仲裁者。假定進程pi(pj)從集合qi(qj)中請求許可，其中qi和qi是仲裁集，也可以是係統中所有進程的子集。qi和qj的交集不能為空。例如，包括係統中大部分進程的集合就可以構成一個仲裁集。使用仲裁集，而非係統中的所有進程，基本協議仍然有效，但是有可能出現死鎖[Maekawa, 1985]。圖2-4a展示了一個包含7個進程的係統，任意一個大於等於4的集合和另外一個大於等於4的集合一定相交，即對於任意兩個仲裁集， 每一個仲裁集都包含大部分站點，它們的交集一定是非空的。

在數據庫中，仲裁集的概念可以理解成基本的讀、寫操作，讀操作不需要互斥。然而，多個讀操作雖然可以並發執行，但是，針對數據的寫操作仍需要互斥訪問。因此，設計了兩種仲裁集：讀仲裁集和寫仲裁集，其中，兩個寫仲裁集之間的交集不能為空，一個讀仲裁集和一個寫仲裁集之間的交集也不能為空，針對兩個讀仲裁集的交集沒有強製性要求。圖2-4b展示了一個包含6個進程的係統，寫仲裁集是大小為4的任意集合，讀仲裁集是大小為3的任意集合。需要注意的是，任意讀仲裁集和寫仲裁集必須相交，任意兩個寫仲裁集也必須相交。但是，讀仲裁集之間不一定相交，因此，多個讀操作可以並行執行。

　

a）互斥仲裁集                                                          b）讀寫仲裁集