Concurrent Update on Multiprogrammed Shared Memory Multiprocessors
Maged M. Michael, Michael Lee Scott · 1996
Most multiprocessors are multiprogrammed in order to achieve acceptable response time and to increase utilization. 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: preemption-safe locking and non-blocking (lock-free) algorithms. Preemption-safe locking requires kernel support. Non-blocking algorithms generally require a universal atomic primitive such as compare and swap or load linked/store conditional. We focus in our study on four simple but important concurrent data structures---stacks, FIFO queues, priority queues and counters---in synthetic kernels and real applications on a 12-processor SGI Challenge multiprocessor. Our results indicate that efficient, data-structure-specific non-blocking algorithms, which exist for stacks, FIFO queues and counters, outperform both preemption-s...