Contention-free synchronization in shared memory multiprocessors

The focus of this research is contention free synchronization in shared memory multiprocessors. We provide new algorithms for the mutual exclusion and readers-writers locks, and concurrent queue implementations for the producer-consumer problem. Busy waiting on global flags is known to cause contention. It is important to eliminate contention to realize the performance and scalability of shared memory multiprocessors. Most of the contention free solutions developed in the past rely on cache coherency or use powerful atomic primitives, e.g., compare & swap. Many industry standard buses support local shared memory but do not support cache coherency. Likewise, a number of processors support swap or fetch & add but do not support the more powerful atomic primitives. New solutions using local shared memory and swap or fetch & add primitives have practical significance in that they have wider applicability. We have developed solutions that meet this criteria. We show that any two processors in a system of N processors may synchronize in a contention free manner using swap or fetch & add and a single synchronization variable. Further, more than one variable may be combined to synchronize more than two processors. We exploit this fact to build data structures to develop new algorithms. We have developed three mutual exclusion locks: an array based lock using fetch & add, another array based solution using swap, and a linked list based solution using swap as the only atomic primitive. Each solution guarantees FIFO behavior and eliminates contention using local shared memory. We have developed two array based readers-writers locks using fetch & add. We have also developed a singly list and three doubly linked list based readers-writers locks using swap. Each algorithm guarantees FIFO behavior. All, except one, use local shared memory to eliminate contention. We have developed a linked list based lock free solution for multiple producers, single consumer using swap as the only atomic primitive. We have also developed array based solutions in which no producer or consumer is required to wait. We have measured the performance of our algorithms in a system without coherent cache. The results verify that our algorithms do eliminate contention due to synchronization in architectures without coherent caches.