Lock-free implementation of dynamic-sized shared data structure

Details Lock-free implementation of dynamic-sized shared data structure Lock-free implementation of dynamic-sized shared data structure

2007-08-07

2007-08-07

Rodriguez, Paul (Department: 2123)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C710S056000

Reexamination Certificate

active

10340154

ABSTRACT:
Solutions to a value recycling problem that we define herein facilitate implementations of computer programs that may execute as multithreaded computations in multiprocessor computers, as well as implementations of related shared data structures. Some exploitations of the techniques described herein allow non-blocking, shared data structures to be implemented using standard dynamic allocation mechanisms (such as malloc and free). A variety of solutions to the proposed value recycling problem may be implemented. A class of general solutions to value recycling is described in the context of an illustration we call the Repeat Offender Problem (ROP), including illustrative Application Program Interfaces (APIs) defined in terms of the ROP terminology. Furthermore, specific solutions, implementations and algorithm, including a Pass-The-Buck (PTB) implementation are also described. Solutions to the value recycling problem can be applied in a variety of ways to implement dynamic-sized data structures.

REFERENCES:
patent: 4584640 (1986-04-01), MacGregor et al.
patent: 4847754 (1989-07-01), Obermarck et al.
patent: 5224215 (1993-06-01), Disbrow
patent: 5319778 (1994-06-01), Catino
patent: 5428761 (1995-06-01), Herlihy et al.
patent: 6047295 (2000-04-01), Endicott et al.
patent: 6128710 (2000-10-01), Greenspan et al.
patent: 6144965 (2000-11-01), Olivier
patent: 6178423 (2001-01-01), Douceur et al.
patent: 6360219 (2002-03-01), Bretl et al.
patent: 6360220 (2002-03-01), Forin
patent: 6366932 (2002-04-01), Christenson
patent: 6581063 (2003-06-01), Kirkman
patent: 6615216 (2003-09-01), Hu
patent: 6651146 (2003-11-01), Srinivas et al.
patent: 6826757 (2004-11-01), Steele, Jr. et al.
patent: 6848033 (2005-01-01), Joseph
patent: 2001/0047361 (2001-11-01), Martin et al.
patent: 2003/0140085 (2003-07-01), Moir et al.
patent: 2003/0174572 (2003-09-01), Moir et al.
patent: 2003/0182462 (2003-09-01), Moir et al.
patent: 2004/0015510 (2004-01-01), Moir et al.
patent: 2004/0015642 (2004-01-01), Moir et al.
patent: 2004/0034673 (2004-02-01), Moir et al.
patent: 2004/0153687 (2004-08-01), Moir et al.
patent: 0 366 585 (1990-05-01), None
patent: 0 466 339 (1992-01-01), None
patent: WO 86/00434 (1986-01-01), None
patent: WO 01/53942 (2001-07-01), None
patent: WO 01/53943 (2001-07-01), None
patent: WO 01/80015 (2001-10-01), None
patent: WO 01/82057 (2001-11-01), None
M. P. Herlihy J. E. B. Moss, “Lock-Free Garbage Collection for Multiprocessors” IEEE Transactions on Parallel and Distributed Systems vol. 3, Issue 3 (May 1992) pp. 229-236 ISSN:1045-9219.
Mark Moir,“Practical implementations of non-blocking synchronization primitives” Santa Barbara, California, United States pp. 219-228 1997 ISBN:0-89791-952-1.
Agesen, Ole et al., “DCAS-Based Concurrent Deques”, 12thAnnual ACM Symposium on Parallel Algorithms and Architectures, Jul. 2000, 10 pages.
Arora, Nimar S. et al., “Thread Scheduling for Multiprogrammed Multiprocessors”, 10thAnnual ACM Symposium on Parallel Algorithms and Architectures, Jul. 1998, 12 pages.
Herlihy, Maurice et al., “Transactional Memory: Architectural Support for Lock-Free Data Structures”, Annual International Symposium on Computer Architecture, May 1993, 12 pages.
Michael, Maged M. et al., “Non-Blocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors”, Journal of Parallel and Distributed Computing, 51 (1), pp. 1-26, 1998.
Trieber, R, “Systems Programming: Coping with Parallelism”, IBM Technical Report RJ5118, Apr. 23, 1986, 48 pages.
Valois, John D., “Lock-Free Linked Lists Using Compare-and-Swap”, in Proceedings of the 14thAnnual ACM Symposium on Principles of Distributed Computing, pp. 214-222, 1995.
U.S. Appl. No. 09/837,671, titled “Lock Free Reference Counting” filed Apr. 18, 2001, naming as inventors David L. Detlefs et al.
Herlihy, M.P., et al., “Linearizability: A Correctness Condition For Con-Current Objects,”ACM Transactions On Programming Languages and Systems, 12(3):463-492, Jul. 1990.
Herlihy, M.P., “Wait-Free Synchronization,”ACM Transactions On Programming Languages and Systems, 11(1):124-149, Jan. 1991.
Massalin, H., et al., “A Lock-Free Multiprocessor OS Kernel,” Technical Report TR CUCS-005-9, Columbia University, New York, NY, 1991, 21 pages.
Massalin, Henry, “Synthesis: An Efficient Implementation of Fundamental Operating System Services,” Dissertation submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy in the Graduate School of Arts and Sciences, Columbia University, New York, NY, online, 158 pages, 1992 [retrieved from the Internet on Jul. 13, 2001: URL:ftp://ftp.cs.columbia.edu/reports/reports-1992/cucs-039-92.ps.gz].
Bershad, B. N., “Practical Considerations For Non-Blocking Concurrent Objects,”Proceedings 13th IEEE International Conference on Distributed Computing Systems, pp. 264-273. IEEE Computer Society Press, Washington, D.C., 1993.
Herlihy, M., “A Methodology For Implementing Highly Concurrent Data Objects,”ACM Transactions on Programming Languages and Systems, 15(5):745-770, Nov. 1993.
Attiya, Haglt, et al., “Are Wait-Free Algorithms Fast?”Journal of the ACM, 41(4):725-763, Jul. 1994.
Lamarca, A., “A performance evaluation of lock-free synchronization protocols,”Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, pp. 130-140, ACM Press, New York, NY, 1994.
Michael, Maged M. et al., “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms,” Proceedings of PODC, pp. 267-275, May 1996.
Attiya, H., et al., “Universal Operations: Unary versus Binary,”Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing, pp. 223-232, ACM Press, New York, NY, 1996.
Greenwald, M. B., et al., “The Synergy Between Non-Blocking Synchronization And Operating System Structure,”Proceedings of the 2nd Symposium on Operating Systems Design and Implementation, pp. 123-136, Usenix Association, Berkeley, CA, 1996.
Afek, Y., et al., “Disentangling Multi-Object Operations,”Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, pp. 111-120, Aug. 1997. Santa Barbara, CA.
Attiya, Hagit, et al., “Atomic Snapshots In O(n log n) Operations,”SIAM Journal on Computing, 27(2):319-340, Apr. 1998.
Greenwald, M., “Non-Blocking Synchronization and System Design,” PhD thesis, Stanford University Technical Report STAN-CS-TR-99-1624, Palo Alto, CA, Aug. 1999, 241 pages.
Detlefs, David L., et al., “Even Better DCAS-Based Concurrent Deques,”Lecture Notes in Computer Science, vol. 1914, pp. 59-73, Springer-Verlag, Berlin, Germany, ISBN: 3-540-41143-7, 2000.
U.S. Appl. No. 09/547,288, filed Apr. 11, 2000 and naming as inventor(s) Shavit et al.
U.S. Appl. No. 09/547,290, filed Apr. 11, 2000 and naming as inventor(s) Shavit et al.
U.S. Appl. No. 09/710,218, filed Nov. 10, 2000 and naming as inventor(s) Harris, Timothy.
Afek, Yehuda, “Wait-Free Made Fast,” Proc. 27th Annual ACM Symposium on the Theory of Computing, pp. 538-547, ACM Press, New York, NY 1995.
Afek, Yehuda et al., “Long-Lived Renaming Made Adaptive,” Proceedings of the 18th Annual ACM Symposium on Principles of Distributed Computing, pp. 91-103, ACM Press, New York, NY, 1999.
Agesen, Ole at el., “An Efficient Meta-Lock for Implementing Ubiquitous Synchronization,” ACM SIGPLAN Notices, vol. 34, No. 10, pp. 207-222, Oct. 1999.
Anderson, James H. et al., “Universal Constructions for Large Objects,”IEEE Transactions on Parallel and Distributed Systems, vol. 10 , No. 12, pp. 1317-1332, 1999.
Attiya, Hagit et al., “An Adaptive Collect Algorithm with Applications,”Distributed Computing, vol. 15, No. 2, pp. 87-96, Apr. 2002.
Barnes, G., “A Method for I

Affiliated with

Also associated with

Rating

Lock-free implementation of dynamic-sized shared data structure does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Lock-free implementation of dynamic-sized shared data structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lock-free implementation of dynamic-sized shared data structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3856491