Value recycling facility for multithreaded computations

Details Value recycling facility for multithreaded computations Value recycling facility for multithreaded computations

2011-03-15

2011-03-15

Krofcheck, Michael C (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Shared memory area

C711S154000, C711S170000, C711SE12010, C711SE12009, C707S813000, C707S820000, C707S999206

Reexamination Certificate

active

07908441

ABSTRACT:
Solutions to a value recycling problem 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 allow non-blocking, shared data structures to be implemented using standard dynamic allocation mechanisms (such as malloc and free). Some exploitations allow non-blocking, indeed even lock-free or wait-free, implementations of dynamic storage allocation for shared data structures. In some exploitations, our techniques provide a way to manage dynamically allocated memory in a non-blocking manner without depending on garbage collection. While exploitations of solutions to the value recycling problem that we propose include management of dynamic storage allocation wherein values managed and recycled tend to include values that encode pointers, they are not limited thereto. Indeed, the techniques are more generally applicable to management of values in a multithreaded computation. For example, value recycling techniques may be exploited, in some cases, apart from dynamic storage allocation, to allow a multithreaded computation to avoid the classic ABA hazard.

REFERENCES:
patent: 4584640 (1986-04-01), MacGregor et al.
patent: 4814971 (1989-03-01), Thatte
patent: 4847754 (1989-07-01), Obermarck et al.
patent: 5081572 (1992-01-01), Arnold
patent: 5222238 (1993-06-01), Zobre et al.
patent: 5224215 (1993-06-01), Disbrow
patent: 5319778 (1994-06-01), Catino
patent: 5742785 (1998-04-01), Stone 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: 6366932 (2002-04-01), Christenson
patent: 6581063 (2003-06-01), Kirkman
patent: 6615216 (2003-09-01), Hu
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/0182465 (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
Michael, M. et al. “Correction of a Memory Management Method for Lock-Free Data Structures,” Dec. 1995, pp. 1-7.
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, Hagit, 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.
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., “Using Local-Spin k-Exclusion Algorithms to Improve Wait-Free Object Implementations,”Distributed Computing, vol. 11, No. 1, pp. 1-20 1997.
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 Implementing Lock-Free Shared Data Structures,”Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures, pp. 261-270, ACM Press, New York, NY 1993.
Herlihy, M., et al., “Transactional Memory: Architectural Support for Lock-Free Data Structures,”Proc. 20th International Symposium in Computer Architecture, pp. 289-300, IEEE Computer Society, Washington, D.C., 1993.
Herlihy, Maurice, “Dynamic-Sized Lockfree Data Structures,” Sun Microsystems Technical Report SMLI TR-2002-112, Jun. 2002.
Herlihy, Maurice et al., “The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized Lock-Free Data Structures,” Sun Microsystems Technical Report SMLI TR-2002-112, Jun. 2002.
Luchangco, Victor et al., “Nonblocking k-compare-single-swap,”Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 314-323, ACM Press, New York, NY, 2003.
Michael, Maged M. et al., “Non-Blocking Algorithms and Preemption Safe Locking on Multiprogrammed Shared Memory Multiprocessors,”Journal of Parallel and Distributed Computing, vol. 51, No. 1, pp. 1-26, May 25, 1998.
Michael, Maged M. et al., “Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes,”Proceedings of the 21st Annual ACM Symposium on the Principles of Distributed Computing, pp. 21-30, ACM Press, New York, NY, 2002.
Moir, Mark et

Affiliated with

Also associated with

Rating

Value recycling facility for multithreaded computations does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Value recycling facility for multithreaded computations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Value recycling facility for multithreaded computations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2769978