Relative performance of preemption-safe locking and non-blocking synchronization on multiprogrammed shared memory multiprocessors

Most multiprocessors are multiprogrammed to achieve accept-able response time. Unfortunately, inopportune preemption may significantly degrade the performance of synchronized parallel ap-plications. To address this problem, researchers have developed two principal strategies for concurrent, atomic update of shared data structures: (1) preemption-safe locking and (2) non-blocking (lock-free) algorithms. Preemption-safe locking requires kernel support. Non-blocking algorithms generally require a universal atomic primitive, and are widely regarded as inefficient. We present a comparison of the two alternative strategies, fo-cusing on four simple but important concurrent data structures— stacks, FIFO queues, priority queues and counters—in micro-benchmarks and real applications on a 12-processor SGI Chal-lenge multiprocessor. Our results indicate that data-structure-specific non-blocking algorithms, which exist for stacks, FIFO queues and counters, can work extremely well: not only do they outperform preemption-safe lock-based algorithms on multipro-grammed machines, they also outperform ordinary locks on ded-icated machines. At the same time, since general-purpose non-blocking techniques do not yet appear to be practical, preemption-safe locks remain the preferred alternative for complex data struc-tures: they outperform conventional locks by significant margins on multiprogrammed systems.