A Distributed Group Mutual Exclusion Algorithm for Soft Real Time Systems

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.

Authors:

• Abhishek Swaroop
• Awadhesh Kumar Singh

Keywords:

• Concurrency
• Group mutual exclusion
• Priority
• Request set
• Token.

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.