分布式系统设计PDF电子书下载

第1章 概论 1

1.1 推动因素 1

1.2 基本计算机组成 2

1.3 分布式系统的定义 4

1.4 我们的模型 7

1.5 互连网络 8

1.6 应用与标准 12

1.7 范围 13

1.8 参考资料来源 15

参考文献 16

习题 18

第2章 分布式程序设计语言 20

2.1 分布式程序设计支持的需求 20

2.2 并行/分布式程序设计语言概述 20

2.3 并行性的表示 21

2.4 进程通信与同步 27

2.5 远程过程调用 34

2.6 健壮性 35

参考文献 38

习题 40

第3章 分布式系统设计的形式方法 43

3.1 模型的介绍 43

3.1.1 状态机模型 43

3.1.2 佩特里网 44

3.2 因果相关事件 49

3.2.1 发生在先关系 49

3.2.2 时空视图 49

3.2.3 交叉视图 50

3.3 全局状态 51

3.3.1 时空视图中的全局状态 51

3.3.2 全局状态：一个形式定义 53

3.3.3 全局状态的 快照 54

3.3.4 一致全局状态的充要条件 55

3.4 逻辑时钟 56

3.4.1 标量逻辑时钟 57

3.4.2 扩展 57

3.4.3 有效实现 59

3.4.4 物理时钟 60

3.5 应用 60

3.5.1 一个全序应用：分布式互斥 60

3.5.2 一个逻辑向量时钟应用：消息的排序 61

3.6 分布式控制算法的分类 62

3.7 分布式算法的复杂性 63

参考文献 63

习题 65

4.1 互斥 67

第4章 互斥和选举算法 67

4.2 非基于权标的解决方案 68

4.2.1 Lamport算法的简单扩展 68

4.2.2 Ricart和Agrawala的第一个算法 69

4.2.3 Maekawa的算法 70

4.3 基于权标的解决方案 71

4.3.1 Ricart和Agrawala的第二个算法 71

4.3.2 一个简单的基于权标环的算法 73

4.3.3 一个基于权标环的容错算法 74

4.3.4 基于权标的使用其他逻辑结构的互斥 75

4.4 选举 76

4.4.1 Chang和Roberts的算法 77

4.4.2 非基于比较的算法 79

4.5 投标 80

4.6 自稳定 84

参考文献 86

习题 89

第5章 死锁的预防、避免和检测 91

5.1 死锁问题 91

5.1.1 死锁发生的条件 91

5.1.2 图论模型 92

5.1.3 处理死锁的策略 93

5.1.4 请求模型 94

5.1.5 资源和进程模型 94

5.1.6 死锁条件 94

5.2 死锁预防 95

5.3 一个死锁预防的例子：分布式数据库系统 96

5.4 死锁避免 98

5.5 一个死锁避免的例子：多机器人的灵活装配单元 100

5.6 死锁检测和恢复 103

5.6.1 集中式方法 103

5.6.3 等级式方法 104

5.6.2 分布式方法 104

5.7 死锁检测和恢复的例子 105

5.7.1 AND模型下的Chandy，Misra和Hass算法 105

5.7.2 AND模型下的Mitchell和Merritt算法 106

5.7.3 OR模型下的Chandy，Misra和Hass算法 106

参考文献 108

习题 109

第6章 分布式路由算法 111

6.1 导论 111

6.1.1 拓扑 112

6.1.2 交换 112

6.1.3 通信类型 113

6.1.4 路由 113

6.1.5 路由函数 114

6.2 一般类型的最短路径路由 114

6.2.2 Ford的分布式算法 115

6.2.1 Dijkstra集中式算法 115

6.2.3 ARPAnet的路由策略 116

6.3 特殊类型网络中的单播 118

6.3.1 双向环 118

6.3.2 网格和圆环 119

6.3.3 超立方 120

6.4 特殊类型网络中的广播 122

6.4.1 环 122

6.4.2 2维网格和圆环 123

6.4.3 超立方 124

6.5 特殊类型网络中的组播 127

6.5.1 一般方法 128

6.5.2 基于路径的方法 128

6.5.3 基于树的方法 129

参考文献 131

习题 133

第7章 自适应、无死锁和容错路由 135

7.1 虚信道和虚网络 135

7.2 完全自适应和无死锁路由 137

7.2.1 虚信道类 137

7.2.2 逃逸信道 138

7.3 部分自适应和无死锁路由 139

7.4 容错单播：一般方法 142

7.5 2维网格和圆环中的容错单播 143

7.5.1 基于局部信息的路由 143

7.5.2 基于有限全局信息的路由 146

7.5.3 基于其他故障模型的路由 147

7.6 超立方中的容错单播 148

7.6.1 基于局部信息的模型 148

7.6.2 基于有限全局信息的模型：安全等级 150

7.6.3 基于扩展安全等级模型的路由：安全向量 151

7.7.1 一般方法 152

7.7 容错广播 152

7.7.2 使用全局信息的广播 153

7.7.3 使用安全等级进行广播 153

7.8 容错组播 155

7.8.1 一般方法 155

7.8.2 基于路径的路由 155

7.8.3 使用安全等级在超立方中进行组播 157

参考文献 159

习题 163

第8章 分布式系统的可靠性 166

8.1 基本模型 166

8.2 容错系统设计的构件模块 167

8.2.1 稳定存储器 167

8.2.2 故障-停止处理器 168

8.2.3 原子操作 169

8.3 节点故障的处理 169

8.3.1 向后式恢复 169

8.3.2 前卷式恢复 170

8.4.1 检查点的存储 172

8.4 向后恢复中的问题 172

8.4.2 检查点方法 173

8.5 处理拜占庭式故障 176

8.5.1 同步系统中的一致协议 176

8.5.2 对一个发送者的一致 177

8.5.3 对多个发送者的一致 179

8.5.4 不同模型下的一致 180

8.5.5 对验证消息的一致 181

8.6 处理通信故障 182

8.7 处理软件故障 185

参考文献 186

习题 191

第9章 静态负载分配 192

9.1 负载分配的分类 192

9.2 静态负载分配 193

9.2.1 处理器互连 194

9.2.2 任务划分 195

9.2.3 任务分配 196

9.3 不同调度模型概述 196

9.4 基于任务优先图的任务调度 197

习题 200

9.5 案例学习：两种最优调度算法 200

9.6 基于任务相互关系图的任务调度 201

9.7 案例学习：域划分 203

9.8 使用其他模型和目标的调度 205

9.8.1 网络流量技术：有不同处理器能力的任务相互关系图 206

9.8.2 速率单调优先调度和期限驱动调度：带实时限制的定期任务 209

9.8.3 通过任务复制实现故障安全调度：树结构的任务优先图 211

参考文献 217

第10章 动态负载分配 222

10.1 动态负载分配 222

10.1.1 动态负载分配的组成要素 223

10.2 负载平衡设计决策 224

10.2.1 静态算法对动态算法 224

10.1.2 动态负载分配算法 224

10.2.2 多样化信息策略 225

10.2.3 集中控制算法和分散控制算法 225

10.2.7 操作系统和独立任务启动策略 226

10.2.6 进程分类 226

10.2.8 开环控制和闭环控制 226

10.2.9 使用硬件和使用软件 226

10.2.5 资源复制 226

10.2.4 移植启动策略 226

10.3 移植策略：发送者启动和接收者启动 227

10.4 负载平衡使用的参数 229

10.4.1 系统大小 229

10.4.2 系统负载 229

10.4.3 系统交通强度 229

10.4.4 移植阈值 230

10.4.5 任务大小 230

10.4.6 管理成本 230

10.4.7 响应时间 230

10.4.8 负载平衡视界 230

10.4.9 资源要求 230

10.5 其他相关因素 231

10.5.1 编码文件和数据文件 231

10.5.2 系统稳定性 231

10.5.3 系统体系结构 231

10.6 负载平衡算法实例 231

10.6.2 最近邻居算法：扩散 232

10.6.3 最近邻居算法：梯度 232

10.6.1 直接算法 232

10.6.4 最近邻居算法：维交换 233

10.7 案例学习：超立方体多计算机上的负载平衡 237

10.8 未来的研究方向 238

参考文献 239

习题 242

11.1 基本概念 243

11.2 可串行性理论 243

第11章 分布式数据管理 243

11.3 并发控制 246

11.3.1 基于锁的并发控制 246

11.3.2 基于时戳的并发控制 247

11.3.3 乐观的并发控制 248

11.4 复制和一致性管理 248

11.4.1 主站点方法 249

11.4.2 活动复制 249

11.4.3 选举协议 250

11.4.4 网络划分的乐观方法：版本号向量 251

11.4.5 网络分割的悲观方法：动态选举 253

11.5 分布式可靠性协议 255

参考文献 259

习题 260

第12章 分布式系统的应用 263

12.1 分布式操作系统 263

12.1.1 服务器结构 264

12.1.2 八种服务类型 264

12.1.3 基于微内核的系统 265

12.2 分布式文件系统 265

12.2.2 文件共享语义 266

12.2.3 文件系统合并 266

12.2.1 文件存取模型 266

12.2.5 命名和名字服务 267

12.2.6 加密 267

12.2.4 保护 267

12.2.7 缓存 268

12.3 分布式共享存储器 269

12.3.1 存储器相关性问题 270

12.3.2 Stumm和Zhou的分类 270

12.3.3 Li和Hudak的分类 271

12.4 分布式数据库系统 273

12.5 异构型处理 275

12.6 分布式系统的未来研究方向 276

参考文献 277

习题 281

附录 DCDL中的通用符号列表 282

索引 283

9.9 未来的研究方向 2196