A Distributed Group Mutual Exclusion Algorithm for Soft Real Time Systems

Authors: Abhishek Swaroop, Awadhesh Kumar Singh

Abstract:

The group mutual exclusion (GME) problem is an interesting generalization of the mutual exclusion problem. Several solutions of the GME problem have been proposed for message passing distributed systems. However, none of these solutions is suitable for real time distributed systems. In this paper, we propose a token-based distributed algorithms for the GME problem in soft real time distributed systems. The algorithm uses the concepts of priority queue, dynamic request set and the process state. The algorithm uses first come first serve approach in selecting the next session type between the same priority levels and satisfies the concurrent occupancy property. The algorithm allows all n processors to be inside their CS provided they request for the same session. The performance analysis and correctness proof of the algorithm has also been included in the paper.

Keywords: Concurrency, Group mutual exclusion, Priority, Request set, Token.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062296

References:

[1] Ye-In chang, M.Singhal and M. T. Liu, "A dynamic token based distributed mutual exclusion algorithm", In proc. of 10th annual international phoenix conference on computers and communications, Pages 240 - 246, 1991.
[2] Y.J.Joung, "Asynchronous group mutual exclusion (extended abstract)", In proceedings of the 17the annual ACM symposium on principles of distributed computing (PODC), Pages 51 -60, 1998.
[3] Y.J.Joung, "The Congenial talking philosopher problem in computer networks", distributed computing, Vol. 15, Pages 155-175, 2002.
[4] N.Mittal and P.K.Mohan, "An efficient distributed group mutual exclusion algorithm for non-uniform group access", In proceedings of the international conference on parallel and distributed computing systems, 2005.
[5] P.Kean and M.Moir, "A simple local spin group mutual exclusion algorithm", In proceedings of the 18th annual ACM symposium on principles of distributed computing, pages 23-32, 1999.
[6] Y.Manabe and J.Park, "A quorum based extended group mutual exclusion algorithm without unnecessary blocking", In proceedings of 10th international conference on parallel and distributed systems (ICPADS-04), 2004.
[7] R.Attreya and N.Mittal, "A dynamic group mutual exclusion algorithm using surrogate quorums", In proceedings of the 25th IEEE conference on distributed computing systems (ICDCS-05), 2005.
[8] M.Toyomura, S.Kamei and H.Kakugawa, "A quorum-based distributed algorithm for group mutual exclusion", PDCAT-03 Pages 742-746, 2003.
[9] D.Lin, T.-S.Moh and M.Moh, "Brief announcement: improved asynchronous group mutual exclusion in token passing networks", In proceedings of PODC-05, Pages 275-275, 2005.
[10] G.Ricart and A.K.Agrawala, "An optimal algorithm for mutual exclusion in computer networks", communications of the ACM 24(1), Pages 9-17, 1981.
[11] Q.E.K Mamun, H.Nakazato, "A new token based group mutual exclusion in distributed systems", In the proc. of the Vth international symposium on parallel and distributed computing, 2006.
[12] F.Mueller, "Prioritized token-based mutual exclusion for distributed systems" 9th Symposium on parallel and distributed processing, Pages 791-795, 1998.
[13] A. Housini, M.Trehel, "Distributed mutual exclusion token-permission based by prioritized groups", Proc. of ACS/IEEE international conference, Pages 253-259, 2001.
[14] Y.Chang, "Design of mutual exclusion algorithm for real time distributed systems", Journal of Information science and engineering, Vol.10, Pages 527-548, 1994.
[15] A. Goscinski, "Two algorithms for mutual exclusion fro real time distributed systems", Journal of Parallel and Distributed Computing, Vol. 34(1), Pages 1-13, 1996.
[16] Y.I.Chang, "Comments on two algorithms for mutual exclusion in realtime distributed computer systems", Journal of Parallel and Distributed Computing, Vol. 23, 449-454 (1994).
[17] O.Thiare, M.Gueroui, and M.Naimi, "Distributed group mutual exclusion based on client/servers model", In the proceedings of 7th international conference on parallel and distributed computing, applications and technologies (PDCAT-06), 2006.
[18] M. Singhal, "A heuristically-aided Algorithm for mutual exclusion in distributed systems", IEEE Transactions on Computers, vol. 38, no.5, pp. 651 - 662, 1989.
[19] I. Suzuki, T. Kasmi, "A distributed mutual exclusion algorithm", ACM Transactions on Computer Systems, vol. l3, no. 4, pp. 344 - 349, 1985.
[20] M. Maekawa, "A n algorithm for mutual exclusion in decentralized systems", ACM Transactions on Computer Systems, vol. 3, no. 2, pp. 145 - 159, 1985.
[21] S. Karnar, and N. Chaki, "Modified Raymond-s Algorithm for priority(MRA-P) based mutual exclusion in distributed systems", ICDCIT 2006,LNCS 4317, pp. 325-332, 2006.
[22] Siberschatz, A., Galvin, P. B., Gagne, G. "Operating Systems Concepts", 6th edition, John Wiley & Sons, Inc., 2002.