Research Of Efficient Deadlock Detection Algorithm In Distributed System

With the rapid development of current information technology,data that produced in daily learning,woring,producing,and living show a trend of explosive growth.In recent years,the big data processing technology which is characterized as large-capacity,multi-category,high-speed,high-value has become an indispensable and important technology for production system.As an important implementation architecture for big data processing technology,the importance of distributed systems is becoming increasingly apparent.However,there are still many problems that are difficult to be resolved perfectly in the distributed system,such as data consistency,system stability etc.But this paper will focus on the deadlock problem in distributed systems.The generation of deadlock is mainly due to the allocation of shared resources or improper progress of the programs.In a distributed system,deadlocks can cause the decrease of the system throughput capacity and the failure of getting correct results.At the same time,processes which are deadlocked won't release resources than they have already occupied,which will lead to poor utilization.Therefore,it is necessary for the distributed systems to detect deadlocks properly as soon as possible.In order to detect and solve the deadlock in distributed system,this paper proposes a probing based deadlock detection algorithm.Firstly,when a deadlock occurs in a distributed system,one or more nodes in the system are triggered to execute deadlock detection algorithms,which are called initiators.When the initiator initiates the execution of the deadlock detection algorithm,it sends probe messages to its own successor nodes.Then,the non-initiators forward the probe message to its own successor nodes.In this process,the concept of priority is introduced to distinguish different algorithm instances that are initiated by different initiator.Using this strategy to pass the probe messages can make all the nodes in the system receive one probe message at least,and participate in the deadlock detection process.Then,when the number of probe messages received by the non-initiators is equal to the number of their own predecessors,they will send a report message to the initiator of the deadlock detection algorithm instance respectively.Finally,the initiator terminates the probing phase by checking the weight it received in the messages.At the end of this phase,the deadlock detection is performed on the dependent information carried in the report messages.In the existing deadlock detection algorithms,the request conditions are sent between processes repeatedly.When multiple instances of the algorithm exist in the system,it increases network load.The algorithms described in this paper can reduce the repetitive transmission of messages.The experimental results also prove this advantage.In particular,in the case of concurrent execution with multiple initiators,the proposed algorithm can significantly reduce the number of transmitted messages and the total size of messages that are sent in the execution of the algorithm.