针对分布式系统的高效死锁检测算法研究

摘要

随着当前信息技术的高速发展，日常学习、工作、生产和生活中的数据呈现出指数型爆炸增长的趋势。而近年来以大容量、多种类、高速度、高价值为主要特征的大数据处理技术日益成为生产系统中不可或缺的重要技术。作为大数据处理技术的重要实现架构，分布式系统的重要性也日渐显现。但是在分布式系统中还存在着不少问题难以完美解决，例如数据一致性，系统的稳定性等问题。但是本文将主要研究分布式系统中的死锁问题。
　　死锁的产生主要是因为系统对于共享资源的分配或者程序推进的顺序不当。在分布式系统中，死锁会导致系统的吞吐量下降，并且无法得到正常的运行结果。同时，发生死锁的进程不再释放已经占有的资源又会降低资源的利用效率。因此，分布式系统中需要有高效处理死锁的模块。
　　为了高效地检测分布式系统中的死锁，本文中提出了一种基于探针消息的死锁检测算法。首先，当分布式系统中发生死锁时，系统中的某些节点会触发死锁检测算法的执行，这类节点被称为发起节点。当发起节点发起死锁检测算法的执行时，它们会向自身的后继节点发送探针消息。然后，非发起节点将自身收到的探针消息又转发给自己的后继节点。在这过程中引入了优先级的概念来区分不同发起节点的算法实例。采用这样的策略传递探针消息可以使系统中所有的节点都能收到探针消息，并参与进死锁的检测过程当中。接着，当非发起节点收到的探针消息的数量等于自身的前驱的数量时，它将向自己所属的死锁检测算法实例的发起节点发送报告消息。最后，发起节点根据接收到的消息中的权值决定消息的发送和接收阶段是否结束。并且，在此阶段结束时，利用收到的报告消息中的依赖信息进行死锁的检测。
　　在现有的死锁检测算法中，依赖信息会在节点之间重复传递。在系统中存在多个算法实例时，这样的重复传递会加重网络通信的负担。而本文中所描述的算法可以减少消息的重复传递。实验结果也证明了这一优势。特别是在拥有多个发起节点的并发执行情况下，本文中所描述的算法能显著的减少消息发送的数量和降低算法执行过程中总的发送的消息的大小。

目录

声明

致谢

摘要

1 绪论

1．1 研究背景与意义

1．1．1 研究背景

1．1．2 研究意义

1．2 研究现状

1．3 本文研究工作和结构

1．4 本章小结

2 相关原理及关键技术

2．1 分布式系统的概念

2．2 死锁的概念

2．2．1 死锁产生的条件

2．2．2 死锁的模型

2．2．3 处理死锁的方法

2．3 分布式死锁问题

2．3．1 分布式死锁的模型

2．3．2 等待图(WFG)的概念

2．4 图论中的相关概念

2．4．1 前驱和后继

2．4．2 入度和出度

2．4．3 生成树

2．4．4 树的直径

2．5 死锁检测算法的分类

2．5．1 集中式的死锁检测算法

2．5．2 分布式的死锁检测算法

2．5．3 分层式的死锁检测算法

2．6 本章小结

3 基于探针消息的死锁检测算法

3．1 算法设计

3．1．1 系统模型

3．1．2 死锁的判断

3．1．3 正确性标准

3．1．4 不同算法实例的区分

3．1．5 虚假边

3．2 算法的实现

3．2．1 算法简介

3．2．2 单个发起节点时算法的形式化描述

3．2．3 多个发起节点的算法

3．3 算法执行过程示例

3．4 本章小结

4．1．1 单个发起节点

4．1．2 多个发起节点

4．2 算法的性能分析

4．2．1 理论分析

4．2．2 实验分析

4．3 本章小结

5 死锁检测算法在MPI上的实现

5．1 原理概述

5．2 详细实现

5．2．1 MPI例程的wrap

5．2．2 对死锁检测程序执行的触发

5．2．3 程序整体执行流程

5．2．4 测试MPI执行结果

5．3 本章小结

6．1 论文总结

6．2 工作展望

参考文献

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集