An Improved Token-Based and Starvation Free Distributed Mutual Exclusion Algorithm

Document Type : Original Research (Full Papers)

Authors

1 Department of Computer Engineering, Sanandaj Branch, Islamic Azad University, Sanandaj, Iran

2 Faculty of Computer and Information Technology Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran

Abstract

Distributed mutual exclusion is a fundamental problem of distributed systems that coordinates the access to critical shared resources. It concerns with how the various distributed processes access to the shared resources in a mutually exclusive manner. This paper presents fully distributed improved token based mutual exclusion algorithm for distributed system. In this algorithm, a process which has owing token, could enter to its critical section. The processes communicate to each other in an asynchronous message passing manner. We assume the distributed processes are organized in a wraparound two dimensional array. Also, the communication graph of the network is supposed to be a complete graph. The proposed algorithm uses three types of messages, namely ReqMsg, InfoMsg and RelMsg. Beside token-holding node, there are some nodes, we call them informed-nodes, which can know token-holding node and transmit request message to it directly. The number of messages, which are exchanged per each critical section entrance, is a key parameter to avoid posing additional overhead to the distributed system. In this paper, we obtain to  messages per critical section access where N is the number of nodes in the system. The proposed algorithm outperforms other token based algorithms whilst fairness is kept and the proposed algorithm is starvation free.

Keywords

Journal of Computer & Robotics
Volume 11, Issue 2
Summer and Autumn 2018
Pages 49-58

Files

History

  • Receive Date: 31 January 2017
  • Revise Date: 05 July 2018
  • Accept Date: 27 August 2018

Share

How to cite

Statistics