Lecture Notes in Computer Science, 2002, Volume 2387/2002, 44-60, DOI: 10.1007/3-540-45655-4_29

Simple Mutual Exclusion Algorithms Based on Bounded Tickets on the Asynchronous Shared Memory Model

Masataka Takamura and Yoshihide Igarashi

View Related Documents

Abstract

We propose two simple algorithms based on bounded tickets for the mutual exclusion problem. These are modifications of the Bakery algorithm. An unattractive property of the Bakery algorithm is that the shared memory size is unbounded. The first algorithm based on bounded tickets uses one extra process that does not correspond to any user. It is lockout-free and mutual exclusion on the asynchronous single-writer/multi-reader shared memory model. We then modify it to reduce the shared memory size with the cost of another extra process. The maximum waiting time using each of them is bounded by (n − 1)c + O(nl), where n is the number of users, l is an upper bound on the time between two successive atomic steps, and c is an upper bound on the time that any user spends using the resource. The shared memory size needed by the first algorithm and the second algorithm are (n + 1)(1+⌈log(2n+ l)⌉) bits and n(2 + ⌈logn⌉) + 2 bits, respectively.

Fulltext Preview

Image of the first page of the fulltext document