分布式互斥算法

㈠ 国外计算机科学教材系列·分布式计算内容简介

国外计算机科学教材系列中的一本重要着作，《分布式计算(第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、节点失效、通信失败等问题。