The DOI matches its Crossref record.
Nonblocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors
Open accessAbstract
Most multiprocessors are multiprogrammed to achieve acceptable response time and to increase their utilization. Unfortunately, inopportune preemption may significantly degrade the performance of synchronized parallel applications. To address this problem, researchers have developed two principal strategies for a concurrent, atomic update of shared data structures: (1) preemption-safe locking and (2) nonblocking (lock-free) algorithms . Preemption-safe locking requires kernel support. Nonblocking algorithms generally require a universal atomic primitive such as compare-and-swap or load-linked/store-conditional and are widely regarded as inefficient. We evaluate the performance of preemption-safe lock-based and nonblocking implementations of important data structures—queues, stacks, heaps, and counters—including nonblocking and lock-based queue algorithms of our own, in microbenchmarks and real applications on a 12-processor SGI Challenge multiprocessor. Our results indicate that our nonblocking queue consistently outperforms the best known alternatives and that data-structure-specific nonblocking algorithms, which exist for queues, stacks, 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Hazard pointers: safe memory reclamation for lock-free objects
Michael, M. M. (2004) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2004.8 · Cited by 508
Self-citationKV-Cache: A Scalable High-Performance Web-Object Cache for Manycore
Waddington, D., Colmenares, J., Kuang, J., & Song, F. (2013) · 2013 IEEE/ACM 6th International Conference on Utility and Cloud Computing · doi:10.1109/ucc.2013.34 · Cited by 11
Metadata
- Authors
- Michael, M. M., & Scott, M. L.
- Venue
- Journal of Parallel and Distributed Computing
- Publisher
- Elsevier BV
- Published
- 1998-05
- Volume
- 51
- Issue
- 1
- Pages
- 1-26
- ISSN
- 0743-7315 (ISSN-L)
- OpenAlex
- W1993301893
- Cited by
- 211
- References
- 0
- FWCI
- 3.24
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Nonblocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors. https://app.cochat.ai/papers/10.1006/jpdc.1998.1446
- The paper
- Michael, M. M., & Scott, M. L. (1998). Nonblocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors. Journal of Parallel and Distributed Computing. https://doi.org/10.1006/jpdc.1998.1446
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.