分布式互斥演算法

㈠ 國外計算機科學教材系列·分布式計算內容簡介

國外計算機科學教材系列中的一本重要著作，《分布式計算(第2版)》深入剖析了分布式計算的核心理論。此書特別關注各種模型之間的共同點和區別，旨在幫助讀者理解分布式計算的內在邏輯。它首先引導讀者步入分布式計算的數學世界，探討了通信、協調、同步和不確定性等基礎問題，以及基本的演算法設計原則和下限技術。

書中詳細探討了一系列關鍵問題，如領導者選舉、互斥、一致性及時鍾同步等，這些都是構建分布式系統時必須面對的核心挑戰。此外，作者還介紹了最新的研究成果，如快速互斥演算法、隊列鎖、分布式共享存儲器模型，以及無等待層級和故障檢測器等技術，這些都在實際應用中發揮著至關重要的作用。

通過《國外計算機科學教材系列?分布式計算(第2版)》，讀者不僅能掌握分布式計算的基礎知識，還能緊跟技術前沿，為構建高效、可靠的分布式系統提供堅實的理論基礎和實踐指導。

㈡ 誰看懂 清華大學 出版的代碼！！有關數據結構的前插法

數據結構與操作系統》——復旦大學2007年碩士研究生入學考試專業課大綱
時間：2006-08-16 被閱讀次數：447

數據結構與操作系統》——復旦大學2007年碩士研究生入學考試專業課大綱

復旦大學2007年入學研究生
《數據結構與操作系統》專業課程考試大綱
第一部分 數據結構
考試題型：簡答題、編程題
參考書目：《數據結構（用面向對象方法C++描述）》殷人昆，清華大學出版社
總分：100分
考試的基本要求
要求考生比較系統地理解數據結構的基本概念和基本理論，掌握各種數據結構的特點和基本方法，著重強調考生要具有綜合運用所學的知識分析問題和解決問題的能力。
對編程語言的要求
數據結構考試中所有的演算法，要求用C或C++語言描述。
一、數組
考試內容
數據；順序表；字元串匹配。
考試要求
1. 理解數組的存儲結構，掌握在順序存儲的情況下，數組元素與存儲單元的對應關系
2. 理解順序表的結構和特點，掌握順序表上基本操作的實現演算法。
3. 掌握字元串比較的基本演算法(包括KMP演算法)。
4. 具有用數組結構解決實際問題的能力。
二、鏈表
考試內容
單鏈表；雙向鏈表；循環鏈表；稀疏矩陣。
考試要求
1. 理解單鏈表、雙向鏈表和循環鏈表三種鏈表形式的存儲結構和特點，掌握其基本操作的實現演算法。
2. 理解稀疏矩陣的存儲結構和特點，掌握稀疏矩陣上基本操作的實現演算法。
3. 具有用鏈表結構解決實際問題(如：用鏈表實現的多項式的運算)的能力。

三、棧和隊列
考試內容
棧；隊列。
考試要求
1. 理解棧的定義和結構特點，掌握其存儲方式(順序存儲與鏈接存儲)和基本操作的實現演算法。
2. 理解隊列的結構和特點，掌握其存儲方式(順序存儲與鏈接存儲)和基本操作的實現演算法。
3. 具有用隊列和棧結構解決實際問題(如：表達式的計算、優先隊列)的能力。
四、遞歸
考試內容
遞歸。
考試要求
1. 理解遞歸的基本概念和實現原理，掌握用遞歸的思想描述問題和書寫演算法的方法。
2. 掌握漢諾塔、迷宮等問題的遞歸解法。
3. 掌握用棧實現遞歸問題的非遞歸解法。
五、樹和森林
考試內容
樹、二叉樹、森林、堆。
考試要求
1. 理解樹的結構，掌握樹的主要概念。
2. 理解各種二叉樹的結構，掌握其特點，具有運用二叉樹解決實際問題的能力。
3. 掌握二叉樹的三種遍歷方法的實現原理和性質，能將二叉樹的遍歷方法應用於求解二叉樹的葉子結點個數、二叉樹計數等問題，掌握遍歷的非遞歸實現方法。
4. 掌握線索化二叉樹的結構和基本操作。
5. 理解堆的原理，掌握基本操作的實現方法。
6. 理解樹和森林的定義和存儲結構，掌握樹和森林的遍歷等方法的實現。
7. 理解霍夫曼編碼的基本原理，掌握基於霍夫曼樹生成霍夫曼編碼的方法。
六、集合和搜索
考試內容
集合；等價類；靜態搜索結構；二叉搜索樹；最優二叉搜索樹；AVL樹。
考試要求
1. 理解集合的基本概念，掌握集合的各種存儲方法。
2. 掌握等價類的生成演算法。
3. 掌握針對有序順序表的折半搜索、斐波那契等搜索方法。
4. 理解AVL樹的定義和特點，掌握AVL樹調整操作的實現原理。
5. 掌握最優二叉樹的構造原理和相關演算法。
七、圖
考試內容
圖；連通分量；最小圖；最短路徑；活動網路。
考試要求
1. 理解和圖相關的各種基本概念，掌握圖的各種存儲方式。
2. 掌握圖兩種搜索方法和連通分量的生成方法。
3. 掌握兩種最小生成樹的生成方法。
4. 掌握各種求最短路徑的方法。
5. 掌握用頂點表示活動和用邊表示活動的兩種網路結構特點和相關操作的實現演算法。
八、排序
考試內容
插入排序；交換排序；選擇排序；歸並排序；基數排序；外排序。
考試要求
理解各種排序方法的實現，掌握各種排序演算法的時間復雜性，各種排序演算法的特性，能夠進行橫向比較。
九、索引結構與散列
考試內容
靜態索引結構；動態索引結構；散列。
考試要求
1. 理解線性索引結構、倒排表、靜態搜索樹的結構和特點。
2. 理解B樹的結構，掌握各種操作的實現演算法。
3. 理解散列的實現原理，掌握各種操作的實現演算法。
第二部分 操作系統
考試內容包括進程、存儲管理、輸入¤輸出和文件系統這四個基本成分的設計原理與實現方法。內容同時涉及分布式操作系統、機群系統和操作系統的安全保障等方面的基礎知識。
要求考生比較系統地理解和掌握操作系統的基本概念、主要功能、主要組成部分、各個主要組成部分的不同實現方法；從資源管理和應用程序與硬體系統介面的觀點掌握操作系統設計的基本思想，掌握現代計算機系統對其各種軟硬資源的管理技術。要求考生具備綜合運用所學的知識分析問題和解決問題的能力。

考試題型：填空與選擇題、解答題、計算題
參考書目：William Stallings. Operating Systems: Internals and Design Principles. Fourth Edition, Prentice Hall. 2001
總分：50分
考試的內容和要求細則
一、操作系統概述
考試內容
1. 計算機基本構成、處理器的內部結構、高速緩沖存儲器CACHE；
2. 操作系統的概念、演變歷程、特性、分類、運行環境、功能
3. 存儲器的層次結構
考試要求
1. 回顧計算機基本原理，了解操作系統所管轄的軟、硬體資源；
2. 了解操作系統的關鍵概念，從整體上把握操作系統的特性與功能等概念；
3. 就存儲器的層次結構展開案例分析。
4. 建立操作系統的資源管理和應用介面的職能概念。
二、進程
考試內容
進程、進程描述及進程狀態轉換
考試要求
掌握進程的本質特徵，明確進程的動態特性，熟悉進程狀態間轉換的原因，建立進程是資源分配單元和一種運行實體的基本理念。
三、線程、對稱多處理SMP和微內核
考試內容
1. 線程的概念，定義線程的必要性和可能性；
2. 線程的功能特性與實現方式；
3. 對稱多處理SMP體系結構；
4. 操作系統的體系結構（微內核與單內核）及其性能分析。
考試要求
1. 理解引入線程作為基本運行實體的必要性和可能性；
2. 掌握線程各種實現方式及其特點；
3. 熟悉SMP體系結構、操作系統的體系結構（微內核與單內核）。
四、並發性
考試內容
1. 並發性問題及相關概念，如臨界區、互斥、信號量和管程等；
2. 進程互斥、同步和通信的各種演算法；
3. 死鎖的概念、死鎖的原因和條件
4. 死鎖的預防、避免和檢測演算法。
考試要求
1. 能夠利用信號量、管程等技術解決互斥合同步問題；
2. 理解死鎖的概念和產生死鎖的充分必要條件；
3. 熟練掌握死鎖的預防、避免和檢測演算法；
4. 了解處理死鎖問題時避免飢餓的方法。
五、存儲器管理
考試內容
1. 分區存儲管理、覆蓋與交換；
2. 頁式管理及段式管理；
3. 段、頁式存儲管理方法及實現技術；
4. 虛存的原理及相關的各種演算法和數據結構。
考試要求
1. 了解存儲管理的功能及存儲管理對多道程序設計的支持；
2. 掌握段、頁式存儲管理方法及實現技術；
3. 重點掌握虛存的原理及相關的各種演算法和數據結構。
六、單處理器調度
考試內容
1. 處理器的三種調度類型；
2. 進程調度的各種演算法及其特點。
考試要求
1. 了解長程、中程和短程三種調度類型；
2. 重點掌握進程調度的各種演算法及其適用環境。
七、多處理器調度和實時調度
考試內容
1. 多處理器對進程調度的影響
2. 多處理器環境下的進程和線程調度演算法；
3. 實時進程的特點；
4. 限期調度和速率單調調度方法。
考試要求
1. 了解調度粒度的概念；
2. 熟悉多處理器環境下進程和線程調度演算法；
3. 了解實時進程的本質，掌握限期調度和速率單調調度方法。
八、設備管理和磁碟調度
考試內容
1. 操作系統中輸入/輸出功能的組織；
2. 中斷處理；
3. 設備驅動程序、設備無關的軟體介面和spooling技術；
4. 緩沖策略；
5. 磁碟調度演算法；
6. 磁碟陣列。
考試要求
1. 了解輸入輸出設備及操作系統中輸入/輸出功能的組織；
2. 掌握中斷處理、設備驅動程序、設備無關的軟體介面和spooling等技術；
3. 重點掌握各種用於提高性能的緩沖策略和磁碟調度演算法；
4. 了解可提高性能和可靠性的各種磁碟陣列配置方式。
九、文件系統
考試內容
1. 文件系統特點與文件組織方式；
2. 文件系統的數據結構；
3. 目錄的基本性質及其實現方法；
4. 磁碟空間的管理。
考試要求
1. 了解文件系統特點與文件組織；
2. 掌握文件系統的基本數據結構；
3. 了解文件、目錄的基本性質及其實現方法；
4. 重點掌握磁碟空間的管理、文件系統的性能及可靠性、文件系統的安全性及保護機制等。
十、分布式系統
考試內容
1. 分布式處理的特點、類型；
2. 多層體系結構、中間件技術；
3. 機群系統；
4. 分布式進程管理相關的操作系統設計問題。
考試要求
1. 了解分布式處理的特點、類型；
2. 掌握多層體系結構、中間件技術和機群系統的基本概念和特點；
3. 重點掌握進程遷移、分布式全局狀態的認定、分布式互斥與死鎖預防等技術。
十一、可信計算機系統
考試內容
1. 計算機系統面臨的安全問題及其應對機制；
2. 可信系統的基本概念。
考試要求
1. 了解計算機系統面臨的安全問題及其應對機制；
2. 掌握計算機安全設計方面的一種綜合性方法——可信系統。

怎麼樣? 值得參考叭?

㈢ 分布式計算的目錄

第1章引言
1．1分布式系統
1．2分布式計算理論
1．3內容概要
1．4理論和實踐的關系
本章注釋
第一部分
第2章消息傳遞系統中的基本演算法
2．1消息傳遞系統的形式化模型
2．2生成樹上的廣播和斂播
2．3洪泛演算法及構造生成樹
2．4構造指定根的深度—優先搜索生成樹
2．5構造不指定根的深度—優先搜索生成樹
練習
本章注釋
第3章環中領導者選舉演算法
3．1領導者選舉問題
3．2匿名環
3．3非同步環
練習
本章注釋
第4章共享存儲器中的互斥
第5章容錯一致性
第6章因果關系和時間
第7章模擬的形式化模型
第8章廣播與多播
第9章分布式共享存儲器
第10章讀/寫對象的容錯模擬
第11章模擬同步
第12章改進演算法的容錯性
第13章容錯的時鍾同步
第14章隨機化
第15章任意對象的無等待模擬
第16章非同步系統中的可解問題
參考文獻
……

㈣ 分布式存儲中，怎樣使用paxos演算法保證數據的一致性

在分布式系統中，我們經常遇到多數據副本保持一致的問題，在我們所能找到的資料中該問題講的很籠統，模模糊糊的，把多個問題或分類糅合在一起，難以理解。在思考和翻閱資料後，通俗地把一致性的問題可分解為2個問題：
1、任何一次修改保證數據一致性。
2、多次數據修改的一致性。
在弱一致性的演算法，不要求每次修改的內容在修改後多副本的內容是一致的，對問題1的解決比較寬松，更多解決問題2，該類演算法追求每次修改的高度並發性，減少多副本之間修改的關聯性，以獲得更好的並發性能。例如最終一致性，無所謂每次用戶修改後的多副本的一致性及格過，只要求在單調的時間方向上，數據最終保持一致，如此獲得了修改極大的並發性能。
在強一致性的演算法中，強調單次修改後結果的一致，需要保證了對問題1和問題2要求的實現，犧牲了並發性能。本文是討論對解決問題1實現演算法，這些演算法往往在強一致性要求的應用中使用。
解決問題1的方法，通常有兩階段提交演算法、採用分布式鎖服務和採用樂觀鎖原理實現的同步方式,下面分別介紹這幾種演算法的實現原理。

兩階段提交演算法

在兩階段提交協議中，系統一般包含兩類機器（或節點）：一類為協調者（coordinator），通常一個系統中只有一個；另一類為事務參與者（participants，cohorts或workers），一般包含多個，在數據存儲系統中可以理解為數據副本的個數。兩階段提交協議由兩個階段組成，在正常的執行下，這兩個階段的執行過程如下所述：
階段1：請求階段（commit-request phase，或稱表決階段，voting phase）。
在請求階段，協調者將通知事務參與者准備提交或取消事務，然後進入表決過程。在表決過程中，參與者將告知協調者自己的決策：同意（事務參與者本地作業執行成功）或取消（本地作業執行故障）。
階段2：提交階段（commit phase）。
在該階段，協調者將基於第一個階段的投票結果進行決策：提交或取消。當且僅當所有的參與者同意提交事務協調者才通知所有的參與者提交事務，否則協調者將通知所有的參與者取消事務。參與者在接收到協調者發來的消息後將執行響應的操作。
舉個例子：A組織B、C和D三個人去爬長城：如果所有人都同意去爬長城，那麼活動將舉行；如果有一人不同意去爬長城，那麼活動將取消。用2PC演算法解決該問題的過程如下：
首先A將成為該活動的協調者，B、C和D將成為該活動的參與者。
階段1：A發郵件給B、C和D，提出下周三去爬山，問是否同意。那麼此時A需要等待B、C和D的郵件。B、C和D分別查看自己的日程安排表。B、C發現自己在當日沒有活動安排，則發郵件告訴A它們同意下周三去爬長城。由於某種原因，D白天沒有查看郵件。那麼此時A、B和C均需要等待。到晚上的時候，D發現了A的郵件，然後查看日程安排，發現周三當天已經有別的安排，那麼D回復A說活動取消吧。
階段2：此時A收到了所有活動參與者的郵件，並且A發現D下周三不能去爬山。那麼A將發郵件通知B、C和D，下周三爬長城活動取消。此時B、C回復A「太可惜了」，D回復A「不好意思」。至此該事務終止。
兩階段提交演算法在分布式系統結合，可實現單用戶對文件（對象）多個副本的修改，多副本數據的同步。其結合的原理如下：
1、客戶端（協調者）向所有的數據副本的存儲主機（參與者）發送：修改具體的文件名、偏移量、數據和長度信息，請求修改數據，該消息是1階段的請求消息。
2、存儲主機接收到請求後，備份修改前的數據以備回滾，修改文件數據後，向客戶端回應修改成功的消息。 如果存儲主機由於某些原因（磁碟損壞、空間不足等）不能修改數據，回應修改失敗的消息。
3、客戶端接收發送出去的每一個消息回應，如果存儲主機全部回應都修改成功，向每存儲主機發送確認修改的提交消息；如果存在存儲主機回應修改失敗，或者超時未回應，客戶端向所有存儲主機發送取消修改的提交消息。該消息是2階段的提交消息。
4、存儲主機接收到客戶端的提交消息，如果是確認修改，則直接回應該提交OK消息；如果是取消修改，則將修改數據還原為修改前，然後回應取消修改OK的消息。
5、 客戶端接收全部存儲主機的回應，整個操作成功。
在該過程中可能存在通信失敗，例如網路中斷、主機宕機等諸多的原因，對於未在演算法中定義的其它異常，都認為是提交失敗，都需要回滾，這是該演算法基於確定的通信回復實現的，在參與者的確定回復（無論是回復失敗還是回復成功）之上執行邏輯處理，符合確定性的條件當然能夠獲得確定性的結果哲學原理。

分布式鎖服務

分布式鎖是對數據被外界修改持保守態度，在整個數據處理過程中將數據處於鎖定狀態，在用戶修改數據的同時，其它用戶不允許修改。
採用分布式鎖服務實現數據一致性，是在操作目標之前先獲取操作許可，然後再執行操作，如果其他用戶同時嘗試操作該目標將被阻止，直到前一個用戶釋放許可後，其他用戶才能夠操作目標。分析這個過程，如果只有一個用戶操作目標，沒有多個用戶並發沖突，也申請了操作許可，造成了由於申請操作許可所帶來的資源使用消耗，浪費網路通信和增加了延時。
採用分布式鎖實現多副本內容修改的一致性問題， 選擇控制內容顆粒度實現申請鎖服務。例如我們要保證一個文件的多個副本修改一致， 可以對整個文件修改設置一把鎖，修改時申請鎖，修改這個文件的多個副本，確保多個副本修改的一致，修改完成後釋放鎖；也可以對文件分段，或者是文件中的單個位元組設置鎖， 實現更細顆粒度的鎖操作，減少沖突。
常用的鎖實現演算法有Lamport bakery algorithm （俗稱麵包店演算法）， 還有Paxos演算法。下面對其原理做簡單概述。

Lamport麵包店演算法

是解決多個線程並發訪問一個共享的單用戶資源的互斥問題的演算法。 由Leslie Lamport（英語：Leslie Lamport）發明。
Lamport把這個並發控制演算法可以非常直觀地類比為顧客去麵包店采購。麵包店只能接待一位顧客的采購。已知有n位顧客要進入麵包店采購，安排他們按照次序在前台登記一個簽到號碼。該簽到號碼逐次加1。根據簽到號碼的由小到大的順序依次入店購貨。完成購買的顧客在前台把其簽到號碼歸0. 如果完成購買的顧客要再次進店購買，就必須重新排隊。
這個類比中的顧客就相當於線程，而入店購貨就是進入臨界區獨占訪問該共享資源。由於計算機實現的特點，存在兩個線程獲得相同的簽到號碼的情況，這是因為兩個線程幾乎同時申請排隊的簽到號碼，讀取已經發出去的簽到號碼情況，這兩個線程讀到的數據是完全一樣的，然後各自在讀到的數據上找到最大值，再加1作為自己的排隊簽到號碼。為此，該演算法規定如果兩個線程的排隊簽到號碼相等，則線程id號較小的具有優先權。
把該演算法原理與分布式系統相結合，即可實現分步鎖。

Paxos演算法

該演算法比較熱門，參見WIKI，http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
Paxos演算法解決的問題是一個分布式系統如何就某個值(決議)達成一致。一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「一致性演算法」以保證每個節點看到的指令一致。一個通用的一致性演算法可以應用在許多場景中，是分布式計算中的重要問題。節點通信存在兩種模型：共享內存(Shared memory)和消息傳遞(Messages passing)。Paxos演算法就是一種基於消息傳遞模型的一致性演算法。BigTable使用一個分布式數據鎖服務Chubby，而Chubby使用Paxos演算法來保證備份的一致性。

採用樂觀鎖原理實現的同步

我們舉個例子說明該演算法的實現原理。如一個金融系統，當某個操作員讀取用戶的數據，並在讀出的用戶數據的基礎上進行修改時（如更改用戶帳戶余額），如果採用前面的分布式鎖服務機制，也就意味著整個操作過程中（從操作員讀出數據、開始修改直至提交修改結果的全過程，甚至還包括操作員中途去煮咖啡的時間），資料庫記錄始終處於加鎖狀態，可以想見，如果面對幾百上千個並發，這樣的情況將導致怎樣的後果。
樂觀鎖機制在一定程度上解決了這個問題。樂觀鎖，大多是基於數據版本（ Version）記錄機制實現。何謂數據版本？即為數據增加一個版本標識，在基於資料庫表的版本解決方案中，一般是通過為資料庫表增加一個 「version」 欄位來實現。讀取出數據時，將此版本號一同讀出，之後更新時，對此版本號加一。此時，將提交數據的版本數據與資料庫表對應記錄的當前版本信息進行比對，如果提交的數據版本號大於資料庫表當前版本號，則予以更新，否則認為是過期數據。
對於上面修改用戶帳戶信息的例子而言，假設資料庫中帳戶信息表中有一個 version 欄位，當前值為 1 ；而當前帳戶余額欄位（ balance ）為 $100 。
操作員 A 此時將其讀出（version=1 ），並從其帳戶余額中扣除 $50（$100-$50 ）。
在操作員 A 操作的過程中，操作員B也讀入此用戶信息（ version=1 ），並從其帳戶余額中扣除 $20 （ $100-$20 ）。
操作員 A 完成了修改工作，將數據版本號加一（ version=2 ），連同帳戶扣除後余額（ balance=$50 ），提交至資料庫更新，此時由於提交數據版本大於資料庫記錄當前版本，數據被更新，資料庫記錄 version 更新為 2 。
操作員 B 完成了操作，也將版本號加一（ version=2 ）試圖向資料庫提交數據（ balance=$80 ），但此時比對資料庫記錄版本時發現，操作員 B 提交的數據版本號為 2 ，資料庫記錄當前版本也為 2 ，不滿足 「 提交版本必須大於記錄當前版本才能執行更新 「 的樂觀鎖策略，因此，操作員 B 的提交被駁回。這樣，就避免了操作員 B 用基於 version=1 的舊數據修改的結果覆蓋操作員A 的操作結果的可能。
樂觀鎖機制與分布式系統相結合上， 我整理了偽代碼如下：
obj 操作的目標
vlaue 修改的值
atom_update_ver 每個目標上的版本，每次修改該值遞增
set( obj, value)
{
//從每個節點上取出修改前的對象版本
get original_ver = obj.atom_update_ver from each node;
//將值賦到每個節點的obj目標
set obj = value from each node;
//條件修改每個節點的obj版本，目標版本加一
//比較和修改操作是原子操作
result = (set obj.atom_update_ver = original_ver + 1
where original_ver + 1 > obj.atom_update_ver
for each node);
if(result == ok)
return set_ok;
else
return set(obj, value);//不成功遞歸修改

該演算法未考慮節點下線、失效等問題，在後續我將分析採用樂觀鎖原理實現一致性演算法，解決問題2、節點失效、通信失敗等問題。