N. Mittal and P.K. Mohan (USA)
message-passing system, resource management, group mu tual exclusion, token-based algorithm, non-uniform group access
In the group mutual exclusion problem, each critical sec tion has a type or a group associated with it. Processes requesting critical sections of the same type may execute their critical sections concurrently. However, processes re questing critical sections of different types must execute their critical sections in a mutually exclusive manner. Most algorithms for group mutual exclusion that have been proposed so far implicitly assume that all groups are equally likely to be requested. In this paper, we propose an efficient algorithm for solving the problem when a rel atively small number of groups are requested more fre quently than others. Our algorithm has a message com plexity of 2n − 1 per request for critical section, where n is the number of processes in the system. It has low syn chronization delay of t and low waiting time of 2t, where t denotes the maximum message delay. The maximum con currency of our algorithm is n, which implies that if all processes have requested critical sections of the same type, then all of them may execute their critical sections con currently. Finally, the amortized message overhead of our algorithm is O(1). Our experimental results indicate that our algorithm outperforms the existing algorithms by as much as 50% in some cases.
Important Links:
Go Back
