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

发布时间：2018-03-18 16:42

本文选题：死锁检测　切入点：等待图　出处：《北京交通大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着当前信息技术的高速发展,日常学习、工作、生产和生活中的数据呈现出指数型爆炸增长的趋势。而近年来以大容量、多种类、高速度、高价值为主要特征的大数据处理技术日益成为生产系统中不可或缺的重要技术。作为大数据处理技术的重要实现架构,分布式系统的重要性也日渐显现。但是在分布式系统中还存在着不少问题难以完美解决,例如数据一致性,系统的稳定性等问题。但是本文将主要研究分布式系统中的死锁问题。死锁的产生主要是因为系统对于共享资源的分配或者程序推进的顺序不当。在分布式系统中,死锁会导致系统的吞吐量下降,并且无法得到正常的运行结果。同时,发生死锁的进程不再释放已经占有的资源又会降低资源的利用效率。因此,分布式系统中需要有高效处理死锁的模块。为了高效地检测分布式系统中的死锁,本文中提出了一种基于探针消息的死锁检测算法。首先,当分布式系统中发生死锁时,系统中的某些节点会触发死锁检测算法的执行,这类节点被称为发起节点。当发起节点发起死锁检测算法的执行时,它们会向自身的后继节点发送探针消息。然后,非发起节点将自身收到的探针消息又转发给自己的后继节点。在这过程中引入了优先级的概念来区分不同发起节点的算法实例。采用这样的策略传递探针消息可以使系统中所有的节点都能收到探针消息,并参与进死锁的检测过程当中。接着,当非发起节点收到的探针消息的数量等于自身的前驱的数量时,它将向自己所属的死锁检测算法实例的发起节点发送报告消息。最后,发起节点根据接收到的消息中的权值决定消息的发送和接收阶段是否结束。并且,在此阶段结束时,利用收到的报告消息中的依赖信息进行死锁的检测。在现有的死锁检测算法中,依赖信息会在节点之间重复传递。在系统中存在多个算法实例时,这样的重复传递会加重网络通信的负担。而本文中所描述的算法可以减少消息的重复传递。实验结果也证明了这一优势。特别是在拥有多个发起节点的并发执行情况下,本文中所描述的算法能显著的减少消息发送的数量和降低算法执行过程中总的发送的消息的大小。
[Abstract]:With the rapid development of information technology, the data in daily study, work, production and daily life are increasing exponentially. And in recent years, with large capacity, many kinds and high speed, Big data's processing technology, which is characterized by high value, has increasingly become an indispensable and important technology in the production system. The importance of distributed systems is becoming more and more important. However, there are still many problems in distributed systems that are difficult to solve perfectly, such as data consistency. However, this paper will focus on the deadlock problem in distributed systems. The deadlock is mainly caused by the improper allocation of shared resources or the improper sequence of program advancement. Deadlocks can cause system throughput to decline and fail to get normal results. At the same time, the process that occurs deadlocks will no longer release the resources already occupied and will reduce the efficiency of the resources. In order to detect deadlock efficiently in distributed system, a deadlock detection algorithm based on probe message is proposed. Some nodes in the system trigger the execution of the deadlock detection algorithm, which is called the initiating node. When the initiating node initiates the implementation of the deadlock detection algorithm, they send a probe message to their successors. The non-initiating node forwards the probe message it receives to its successor node. In the process, the concept of priority is introduced to distinguish the algorithm instance of different initiating node. Using this policy, the probe message can be transmitted. So that all nodes in the system can receive probe messages, Then, when the number of probe messages received by the non-initiator node is equal to the number of its own precursors, it will send a report message to the initiating node of the deadlock detection algorithm to which it belongs. Finally, when the number of probe messages received by the non-initiator node is equal to the number of its precursors, it will send a report message to the initiating node of its own deadlock detection algorithm. The initiating node determines whether the sending and receiving stages of the message end based on the weights in the received message. And, at the end of this phase, In the existing deadlock detection algorithms, the dependency information is repeatedly passed between nodes. When there are many instances of algorithms in the system, the deadlock is detected by using the dependency information in the received report message. The algorithm described in this paper can reduce the repeated transmission of messages. The experimental results also prove this advantage, especially in the case of concurrent execution with multiple initiating nodes. The algorithm described in this paper can significantly reduce the number of messages sent and the total size of messages sent during the execution of the algorithm.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP338.8

【参考文献】