An Improved Token-Based and Starvation Free Distributed Mutual Exclusion Algorithm
Publish place: Journal of Computer and Robotics، Vol: 11، Issue: 2
Publish Year: 1397
نوع سند: مقاله ژورنالی
زبان: English
View: 539
This Paper With 10 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_JCR-11-2_006
تاریخ نمایه سازی: 7 مرداد 1398
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:
Authors
Om-Kolsoom Shahryari
Department of Computer Engineering, Sanandaj Branch, Islamic Azad University, Sanandaj, Iran
Ali Broumandnia
Faculty of Computer and Information Technology Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran