[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.5555/645959.676129guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
Article

The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures

Published: 28 October 2002 Publication History

Abstract

We define the Repeat Offender Problem (ROP). Elsewhere, we have presented the first dynamic-sized, lock-free data structures that can free memory to any standard memory allocator--even after thread failures--without requiring special support from the operating system, the memory allocator, or the hardware. These results depend on a solution to the ROP problem. Here we present the first solution to the ROP problem and its correctness proof. Our solution is implementable in most modern shared memory multiprocessors.

References

[1]
J. Anderson and M. Moir. Using local-spin k -exclusion algorithms to improve wait-free object implementations. Distributed Computing , 11:1-20, 1997. A preliminary version appeared in Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing , 1994, pp. 141-150.
[2]
D. Detlefs, C. Flood, A. Garthwaite, P. Martin, N. Shavit, and G. Steele. Even better DCAS-based concurrent deques. In Proceedings of the 14th International Conference on Distributed Computing , pages 59-73, 2000.
[3]
D. Detlefs, P. Martin, M. Moir, and G. Steele. Lock-free reference counting. In Proceedings of the 20th Annual ACM Symposium on Principles of Distributed Computing , pages 190-199, 2001.
[4]
M. Greenwald. Non-Blocking Synchronization and System Design . PhD thesis, Stanford University Technical Report STAN-CS-TR-99-1624, Palo Alto, CA, August 1999.
[5]
T. Harris. A pragmatic implementation of non-blocking linked lists. In Proceedings of the 15th International Symposium on Distributed Computing , 2001. To appear.
[6]
M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Dynamic-sized lock-free data structures. Technical Report TR-2002-110, Sun Microsystems Laboratories, 2002.
[7]
M. Herlihy, V. Luchangco, and M. Moir. The repeat offender problem: A mechanism for supporting lock-free dynamic-sized data structures. Technical Report TR-2002-112, Sun Microsystems Laboratories, 2002.
[8]
L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers , C-28(9):241-248, September 1979.
[9]
N. Lynch and M. Tuttle. An introduction to input/output automata. Technical Report CWI-Quarterly, 2(3), Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands, 1989.
[10]
M. Michael. Safe memory reclamation for dynamic lock-free objects using atomic reads and writes. In Proceedings of the 21st Annual ACM Symposium on the Principles of Distributed Computing , 2002.
[11]
M. Michael and M. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proceedings of the 15th Annual ACM Symposium on the Principles of Distributed Computing , pages 267-276, 1996.
[12]
M. Michael and M. Scott. Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors. Journal of Parallel and Distributed Computing , 51(1):1-26, 1998.
[13]
M. Moir. Practical implementations of non-blocking synchronization primitives. In Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing , pages 219-228, 1997.
[14]
R. Treiber. Systems programming: Coping with parallelism. Technical Report RJ5118, IBM Almaden Research Center, 1986.
[15]
J. Valois. Lock-free linked lists using compare-and-swap. In Proceedings of the 14th Annual ACM Symposium on Principles of Dsitributed Computing , pages 214-22, 1995. See http://www.cs.sunysb.edu/~valois for errata.
[16]
D. Weaver and T. Germond. The SPARC Architecture Manual Version 9 . PTR Prentice Hall, Englewood Cliffs, NJ 07632, USA, 1994.

Cited By

View all
  • (2021)Snapshot-free, transparent, and robust memory reclamation for lock-free data structuresProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454090(987-1002)Online publication date: 19-Jun-2021
  • (2020)Universal wait-free memory reclamationProceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3332466.3374540(130-143)Online publication date: 19-Feb-2020
  • (2018)FASTERProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3196898(275-290)Online publication date: 27-May-2018
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings
DISC '02: Proceedings of the 16th International Conference on Distributed Computing
October 2002
369 pages
ISBN:3540000739

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 28 October 2002

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 03 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2021)Snapshot-free, transparent, and robust memory reclamation for lock-free data structuresProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454090(987-1002)Online publication date: 19-Jun-2021
  • (2020)Universal wait-free memory reclamationProceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3332466.3374540(130-143)Online publication date: 19-Feb-2020
  • (2018)FASTERProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3196898(275-290)Online publication date: 27-May-2018
  • (2016)Fast non-intrusive memory reclamation for highly-concurrent data structuresACM SIGPLAN Notices10.1145/3241624.292669951:11(36-45)Online publication date: 14-Jun-2016
  • (2016)Fast and Robust Memory Reclamation for Concurrent Data StructuresProceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/2935764.2935790(349-359)Online publication date: 11-Jul-2016
  • (2016)Fast non-intrusive memory reclamation for highly-concurrent data structuresProceedings of the 2016 ACM SIGPLAN International Symposium on Memory Management10.1145/2926697.2926699(36-45)Online publication date: 14-Jun-2016
  • (2015)On the Time and Space Complexity of ABA Prevention and DetectionProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767403(193-202)Online publication date: 21-Jul-2015
  • (2014)Language support for lightweight transactionsACM SIGPLAN Notices10.1145/2641638.264165449:4S(64-78)Online publication date: 1-Jul-2014
  • (2014)Making objects writableProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611483(385-395)Online publication date: 15-Jul-2014
  • (2014)StackTrackProceedings of the Ninth European Conference on Computer Systems10.1145/2592798.2592808(1-14)Online publication date: 14-Apr-2014
  • Show More Cited By

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media