Research Of Distributed Mutual Exclusion Algorithm

With the development of network technology, distributed system has been widely researched and used. Mutual exclusion is an important problem in distributed system It guarantees concurrent processes access critical resources correctly. As the network bandwidth of distributed system is limited and the number of critical resources is fixed, so it has great significance to design some distributed mutual exclusion algorithms that is network light-loaded and has a highly usage rate of critical resources.Based on the realization strategy of mutual exclusion, distributed mutual exclusion algorithm can be categorized into two types: token-based algorithm and permission-based algorithm. This paper introduces some typical distributed mutual exclusion algorithms and then analyzes each one's merits and drawbacks. Token algorithm is simple and can be used in ring network and mobile network. But in this algorithm, so many messages need to be sent for one access of critical resources; the synchronize delay is also very high. This paper presents a new token-based mutual exclusion algorithm. By using token requesting strategy, the new algorithm reduces the number of messages need to be sent. It also introduces a token direct sending strategy to reduce the sync delay. Among permission-base algorithms, the article describes Maekawa algorithm in detail. Maekawa algorithm is the first algorithm that proposes the concept of quorum, with which the mutex area can be reduced from global system to local area. So the message complexity of Maekawa drops significantly. However, Maekawa algorithm is complicated and has a high sync delay. This paper has some improvement for the shortcomings of Maekawa algorithm. The improved algorithm combines Maekawa quorum and token strategy sets, the token holding node sends token directly to the requesting node after receiving the request so the sync delay is reduced. Finally, the simulation results of these two algorithms show that the proposed algorithms mark improvement compared with other similar algorithms.