NONBLOCKING ALGORITHMS AND PREEMPTION-SAFE LOCKING ON MULTIPROGRAMMEDSHARED-MEMORY MULTIPROCESSORS

Most multiprocessors are multiprogrammed to achieve acceptable respons e time and to increase their utilization. Unfortunately, inopportune p reemption may significantly degrade the performance of synchronized pa rallel applications. To address this problem, researchers have develop ed two principal strategies for a concurrent, atomic update of shared data structures: (1) preemption-safe locking and (2) nonblocking (lock -free) algorithms. Preemption-safe locking requires kernel support. No nblocking algorithms generally require a universal atomic primitive su ch as compare-and-swap or load-linked/store- conditional and are widel y regarded as inefficient. We evaluate the performance of preemption-s afe lock-based and nonblocking implementations of important data struc tures-queues, stacks, heaps, and counters-including nonblocking and lo ck-based queue algorithms of our own. in microbenchmarks and real appl ications on a 12-processor SGI Challenge multiprocessor. Our results i ndicate that our nonblocking queue consistently outperforms the best k nown alternatives and that data-structure-specific nonblocking algorit hms, which exist for queues, stacks, and counters, can work extremely well. Not only do they outperform preemption-safe lock-based algorithm s on multiprogrammed machines, they also outperform ordinary locks on dedicated machines. At the same time, since general-purpose nonblockin g techniques do not yet appear to be practical, preemption-safe locks remain the preferred alternative for complex data structures: they out perform conventional locks by significant margins on multiprogrammed s ystems. (C) 1998 Academic Press.