Previous [1] [2] [3] [4] [5] [6] [7] [8] [9]


Journal of Information Science and Engineering, Vol.19 No.3, pp.415-432 (May 2003)

Group Mutual Exclusion in Tree Networks*

Joffroy Beauquier, Sebastien Cantarell, Ajoy K. Datta**
and Franck Petit+
LRI/CNRS, Universite de Paris-Sud, France
**School of Computer Science
University of Nevada Las Vegas, U.S.A.
+LaRIA, Universite de Picardie Jules Verne, France

The group mutual exclusion (GME) problem deals with sharing a set of (m) mutually exclusive resources among all (n) processes of a network. Processes are allowed to be in a critical section simultaneously provided they request the same resource. We present three group mutual exclusion solutions for tree networks. All three solutions do not use process identifiers and use bounded size messages. They achieve the best context-switch complexity, which is O(min(n, m)). The first solution uses a fixed root of the tree and uses 0 to O(n) messages per critical section entry. This solution supports an unbounded degree of concurrency, thus providing the maximum resource utilization. The second solution also uses a fixed root, but uses a reduced number of messages for the critical section entry. It generates an average of O(log n) messages per critical section entry and also allows an unbounded degree of concurrency. We remove the restriction of using a fixed root in the third solution in addition to maintaining all other desirable properties of the second solution.

Keywords: group mutual exclusion, mutual exclusion, priority-based, resource allocation, readers/writers problem

Full Text () Retrieve PDF document (200305_02.pdf)

Received May 15, 2002; accepted July 25, 2002.
Communicated by Biing-Feng Wang, Stephan Olariu and Gen-Huey Chen.
*A preliminary version of the paper was presented at the 2002 International Conference on Parallel and Distributed Systems, Chungli, Taiwan.