Accession Number : ADA309541
Title : Concurrent Update on Multiprogrammed Shared Memory Multiprocessors,
Descriptive Note : Technical rept.,
Corporate Author : ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE
Personal Author(s) : Michael, Maged M. ; Scott, Michael L.
PDF Url : ADA309541
Report Date : APR 1996
Pagination or Media Count : 17
Abstract : 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.
Descriptors : *DISTRIBUTED DATA PROCESSING, *CONCURRENT ENGINEERING, *MULTIPROGRAMMING, DATA BASES, ALGORITHMS, OPTIMIZATION, SYSTEMS ENGINEERING, QUEUEING THEORY, DATA MANAGEMENT, COMPUTER COMMUNICATIONS, PERFORMANCE(ENGINEERING), INPUT OUTPUT PROCESSING, PARALLEL PROCESSING, OPERATING SYSTEMS(COMPUTERS), MULTIPROCESSORS, SYSTEMS ANALYSIS, COMPUTER PROGRAM VERIFICATION, EXECUTIVE ROUTINES, STRUCTURED PROGRAMMING.
Subject Categories : Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE