Concurrent Update on Multiprogrammed Shared Memory Multiprocessors

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-safe and ordinary locks by 20--40% in real applications and 40--55% in synthetic kernels on both multiprogrammed and dedicated systems (general-purpose non-blocking techniques do not yet appear to be practical). At the same time, preemption-safe locks outperform conventional locks by significant margins on multiprogrammed systems. The clear conclusion is that data-structure-specific non-blocking algorithms should be used whenever possible. For data structures for which such algorithms are not known, operating systems for multiprogrammed parallel machines should provide preemption-safe locks