Stephen M. Blackburn, Perry Cheng, et al.
SIGMETRICS/Performance 2004
This paper presents a scalable solution to the group mutual exclusion problem, with applications to linearizable stacks and queues, and related problems. Our solution allows entry and exit from the mutually exclusive regions in O (tr + τ) time, where tr is the maximum time spent in a critical region by a user, and τ is the maximum time taken by any instruction, including a fetch-and-add instruction. This bound holds regardless of the number of users. We describe how stacks and queues can be implemented using two regions, one for pushing (enqueueing) and one for popping (dequeueing). These implementations are particularly simple, are linearizable, and support access in time proportional to a fetch-and-add operation. In addition, we present experimental results comparing room synchronizations with the Keane-Moir algorithm for group mutual exclusion.
Stephen M. Blackburn, Perry Cheng, et al.
SIGMETRICS/Performance 2004
Erik Altman, Joshua S. Auerbach, et al.
FPT 2013
David F. Bacon, Perry Cheng, et al.
ACM SIGPLAN Notices
David F. Bacon, Perry Cheng, et al.
LCTES 2003