A prioritized distributed mutual exclusion algorithm balancing priority inversions and response time

Jonathan Lejeune 1 Luciana Arantes 1 Julien Sopena 1 Pierre Sens 1
1 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Résumé : Distributed priority-based mutual exclusion algorithms may present starvation for low priority requests if the shared resource is continuously asked by high priority requests. To address this problem, several existing algorithms dynamically increment the priority of pending low-priority requests. The drawback of this approach is that it may lead to a great number of priority inversions, i.e., a pending request p is satisfied before another one whose priority is higher than p's. One solution to reduce this number, as we have proposed in [7], is to both postpone priority increments and prevent low priorities from increasing too fast. However, in this case, the response time of low priorities may considerably increase. Therefore, in this article, we propose a new algorithm, denoted "Awareness", which aims at reducing the maximum response time whereas the number of priority violations remains low. To this end, a global view of pending requests of the system is necessary. Performance evaluation results confirm that our new algorithm provides a good tradeoff between response time and number of priority inversions.
Type de document :
Communication dans un congrès
ICPP'13 - 42th International Conference on Parallel Processing, Oct 2013, Lyon, France. IEEE Computer Society, pp.290-299, 2013, 〈10.1109/ICPP.2013.38〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00839058
Contributeur : Pierre Sens <>
Soumis le : jeudi 27 juin 2013 - 10:02:42
Dernière modification le : vendredi 31 août 2018 - 09:25:54

Identifiants

Collections

Citation

Jonathan Lejeune, Luciana Arantes, Julien Sopena, Pierre Sens. A prioritized distributed mutual exclusion algorithm balancing priority inversions and response time. ICPP'13 - 42th International Conference on Parallel Processing, Oct 2013, Lyon, France. IEEE Computer Society, pp.290-299, 2013, 〈10.1109/ICPP.2013.38〉. 〈hal-00839058〉

Partager

Métriques

Consultations de la notice

201