A fair starvation-free prioritized mutual exclusion algorithm for distributed systems

• Published in: Journal of parallel and distributed computing 2015-09, Vol.83, p.13-29
• Main Authors: Lejeune, Jonathan, Arantes, Luciana, Sopena, Julien, Sens, Pierre
• Format: Article
• Language: English
• Subjects: Algorithm; Computer Science; Data Structures and Algorithms; Distributed system; Distributed, Parallel, and Cluster Computing; Mutual exclusion; Priority
• ISSN: 0743-7315; 1096-0848
• DOI: 10.1016/j.jpdc.2015.04.002

Several distributed mutual exclusion algorithms define the order in which requests are satisfied based on the priorities assigned to requests. These algorithms are very useful for real-time applications ones or those where priority is associated to a quality of service requirement. However, priority based strategies may result in starvation problems where high priority requests forever prevent low priority ones to be satisfied. To overcome this problem, many priority-based algorithms propose to gradually increase the priority of pending requests. The drawback of such an approach is that it can violate priority-based order of requests leading to priority inversion. Therefore, aiming at minimizing the number of priority violations without introducing starvation, we have added some heuristics in Kanrar–Chaki priority-based token-oriented algorithm in order to slow down the frequency with which priority of pending requests is increased. Performance evaluation results confirm the effectiveness of our approach when compared to both the original Kanrar–Chaki and Chang’s priority-based algorithms. •Our algorithm is based on two mechanisms aiming at postponing priority increment and reducing messages overhead.•Priority increment postponing reduces the amount of priority violations without introducing starvation.•Taking into account request locality allows to reduce the message overhead due to the priority postponement.•Priority increment increases significantly the waiting time of the lowest priorities.•The location of processes on the logical tree topology has an impact over performance.