Petri Net Model for Ricart and Agrawala’s Mutual Exclusion Algorithm

Abstract

Issues involved in mutual exclusion and background of mutual exclusion are discussed. A Ricart and Agrawala mutual exclusion algorithm is investigated. Simulation model of the system based on Petri Nets is described. Simulation results are presented and evaluated.

Keywords

• Mutual exclusion,Petri nets,simulation

References

1. Baier, C.; Daum, M.; Engel, B.; Härtig, H.; Klein, J.; Klüppelholz, S.; ... & Völp, M. (2015). Locks: Picking key methods for a scalable quantitative analysis, Journal of Computer and System Sciences, Vol. 81, No. 1, 258-287.
2. Dijkstra, E. W. (1965). Solution of a problem in concurrent programming control, Communications of the ACM, Vol. 8, No. 9, 569.
3. Khanna, A.; Singh, A. K.; Swaroop, A. (2014). A leader-based k-local mutual exclusion algorithm using token for MANETs. Journal of Information Science And Engineering, Vol. 30, 1303-1319.
4. Knuth, D. E. (1966). Addition comments on a problem in concurrent programming control, Communications of the ACM, Vol. 9, No. 5, 321-322.
5. Kostin, A.; Ilushechkina, L. (2005). Winsim: a tool for performance evaluation of parallel and distributed systems, Proceedings of the International Conference on Advances in Information Systems, 312-321.
6. Lamport, L. (1974). A new solution of Dijkstra's concurrent programming problem, Communications of the ACM, Vol. 17, No. 8, 453-455.
7. Lamport, L. (1977). Concurrent reading and writing, Communications of the ACM, Vol. 20, No. 11, 806-811.
8. Lamport, L. (1987). A fast mutual exclusion algorithm, ACM Transactions on Computer Systems, Vol. 5, No. 1, 1-11.

9. Mellor-Crummey, J. M.; Scott, M. L. (1991). Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems, Vol. 9, No. 1, 21-65.
10. Murata, T. (1989). Petri nets: Properties, analysis and applications. Proceedings of the IEEE, Vol. 77, No. 4, 541-580.
11. Peterson, G. L. (1981). Myths about the mutual exclusion problem, Information Processing Letters, Vol. 12, No. 3, 115-116.
12. Ricart, G., & Agrawala, A. K. (1981). An optimal algorithm for mutual exclusion in computer networks. Communications of the ACM, 24(1), 9-17.
13. Wang, J.; Wang, Z. (2014). Mutual Exclusion Algorithms in the Shared Queue Model, Proceedings of the International Conference on Distributed Computing and Networking, 29-43.
14. Wong, M., Ayguadé, E., Gottschlich, J., Luchangco, V., de Supinski, B. R., & Bihari, B. (2014). Towards Transactional Memory for OpenMP, Proceedings of the 10th International Workshop on OpenMP, 130-145.