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

Most multiprocessors are multiprogrammed to achieve acceptable response time. Unfortunately, inopportune preemption may significantly degrade the performance of synchronized parallel applications. 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, focusing 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 Challenge 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 multiprogrammed machines, they also outperform ordinary locks on dedicated machines. At the same time, since general-purpose nonblocking techniques do not yet appear to be practical, preemption-safe locks remain the preferred alternative for complex data structures: they outperform conventional locks by significant margins on multiprogrammed systems.