Local-spin Abortable Mutual Exclusion

Abortable mutual exclusion is a variant of mutual exclusion, in which processes are allowed to abort in the trying protocol. Scott presented the first local-spin abortable mutual exclusion algorithms. They are based on a queue and perform O(1) remote memory accesses (RMAs) when no processes abort. However, they use unbounded space and a process can perform an unbounded number of RMAs, in the worst case, to enter the critical section. The only other local-spin abortable mutual exclusion algorithm is by Jayanti. It has bounded space and RMA complexity, but a process always performs \Theta(log N) RMAs to enter the critical section, where N is the number of processes. In this thesis, three new, bounded space, abortable mutual exclusion algorithms are presented. We give the first local-spin abortable mutual exclusion algorithm that uses only registers. It has \Theta(log N) RMA complexity, even if no processes abort. We also present the first local-spin abortable mutual exclusion algorithm using more general primitives which has bounded space and in which each process performs O(1) RMAs to enter the critical section when no processes abort. However, this algorithm is local-spin only for a certain type of cache-coherent model. Finally, we present an abortable mutual exclusion algorithm which is local-spin in any cache-coherent model and in which each process performs O(1) RMAs to enter the critical section when no processes abort. We develop a new reference counting method to bound the space used in this algorithm.Ph