Electrical computers and digital processing systems: interprogra – Interprogram communication using message – Object oriented message
Reexamination Certificate
2006-10-03
2006-10-03
Thomson, William (Department: 2194)
Electrical computers and digital processing systems: interprogra
Interprogram communication using message
Object oriented message
C710S200000, C707S793000
Reexamination Certificate
active
07117502
ABSTRACT:
A simple and therefore highly usable non-blocking implementations of linked-lists can be provided using read, write, and CAS operations. Several realizations of linked-list based data-structures are described, which are non-blocking, linearizable, and exhibit disjoint-access for most operations. In other words, the realizations are non-blocking and linearizable while maintaining the property that operations on disjoint parts of the list do not interact, effectively lowering contention and increasing concurrency. We implement three exemplary data structures: sets, multi-sets, and ordered-sets. The exemplary implementations support insert, remove, and find operations, with natural semantics. An ordered-set implementation supports an additional removeGE operation.
REFERENCES:
patent: 4584640 (1986-04-01), MacGregor et al.
patent: 5081572 (1992-01-01), Arnold
patent: 5765175 (1998-06-01), Needham et al.
patent: 5924098 (1999-07-01), Kluge
patent: 6360220 (2002-03-01), Forin
patent: 6581063 (2003-06-01), Kirkman
patent: 6651146 (2003-11-01), Srinivas 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
Valois, “Lock-Free Linked Using Compare-and-Swap,” in Proceedings of the Fourteenth ACM Symposium on Principles o Distributed Computing, Aug. 1995, pp. 214-222.
Ole Agesen et. al, “DCAS-Based Concurrent Deques,” Jul. 2000, p. 137-146.
Henery Massalin et. al, “A Lock-Free Multiprocessor OS Kernel,” Jun. 1991, Department of Computer Science Columbia University, Technical Report No. 10027.
Prasad Jayanti and Srdjan Petrovic, “Efficient and Practical Constructions of LL/SC Variables,” ACM, Jul. 13-16, 2003, p. 285-294.
Arora, Blumofe and Plaxton,Thread Scheduling for Multiprogrammed Multiprocessors, inProceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures(1998) pp. 119-129.
Greenwald and Cheriton,The Synergy Between Non-Blocking Synchronizatio and Operating System Structure, Dept. of Computer Science, Univ. of Rochester, NY (1998), 14 pp.
Greenwald,Non-Blocking Synchronization and System Design, PhD thesis, Stanford University Technical Report STAN-CS-TR-99-1624, Palo Alto, CA, (1999) pp. 1-24.
LaMarca,A Performance Evaluation of Lock-Free Synchronization ProtocolsinProceedings of the 13th Annual ACM Symposium on Principles of Distributed ComputingLos Angeles, CA, (Aug. 14-17, 1994), pp. 130-140.
Massalin and Pu,A Lock-free Multiprocessor OS Kernel, Tech. Rep. TRCUCS-005-9, Columbia University, New York, NY, (1991) 21 pp.
Michael and Scott,Correction of a Memory Management Method for Lock-Free Data Structures, TR599, Dept. of Computer Science, Univ. of Rochester, NY (Dec. 1995) pp. 1-7.
Michael and Scott,Non-Blocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors, Dept. of Computer Science, Univ. of Rochester, NY (1998) pp. 1-24.
Michael and Scott,Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithmsin15th ACM Symposium on Principles of Distributed Computing(May 1996) 9 pp.
Valois,Lock-Free Linked Lists Using Compare-and-Swap, inProceedings of the Fourteenth ACM Symposium on Principles of Distributed Computing, Ottawa, Canada (Aug. 1995) pp. 214-222.
Ole Agesen et al., “DCAS-Based Concurrent Deques,” Proceedings of the Twelfth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA2000), Bar Arbor, Maine, online, Jul. 9-12, 2000, pp. 137-146 XP002172095, Association for Computing Machinery, ACM, New York, NY, [retrieved from the Internet on Jul. 13, 2001: URL:http://research.sun.com/jtech/subs/00-dequel.ps>].
Henry Massalin, “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, 1992; pp. 1-149 XP002172093 [retrieved from the Internet on Jul. 13, 2001: URL:ftp://ftp.cs.columbia.edu/reports/reports-1992/cucs-039-92.ps.gz].
David L. Detlefs et al., “Even Better DCAS-Based Concurrent Deques,” Distributed Computing, 14th International Conference, Oct. 4, 2000, pp. 59-73, XP002172096.
Afek, Yehuda, et al., “Atomic snapshots of shared memory.” InJournal of ACM, vol. 40, No. 4, pp. 873-890 Sep. 1993.
Afek, Yehuda, et al., “Wait-free made fast.” InProceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, Las Vegas, Nevada, United States, May 29-Jun. 1, 1995, pp. 538-547, ACM Press, New York, NY.
Afek, Yehuda, et al., “Disentangling multi-object operations.” InProceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, Santa Barbara, California, United States, Aug. 21-24, 1997, pp. 111-120, ACM Press, New York, NY.
Agesen, Ole, et al., “An efficient meta-lock for implementing ubiquitous synchronization.” InProceedings of the 14th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, Denver, Colorado, United States, Nov. 1-5, 1999, pp. 207-222, ACM Press, New York, NY.
Attiya, Hagit and Dagan, Eyal, “Universal operations: unary versus binary.” InProceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, Philadelphia, Pennsylvania, United States, May 23-26, 1996, pp. 223-232, ACM Press, New York, NY.
Attiya, Hafit and Rachman, Ophir, “Atomic snapshots in O(n log n) operations.” InProceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing, Ithaca, New York, United States, Aug. 15-18, 1993, pp. 29-40, ACM Press, New York, NY.
Bacon, David F., et al., “Thin locks: featherweight synchronization for Java.” InProceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, Montreal, Quebec, Canada, Jun. 17-19, 1998, pp. 258-268, ACM Press, New York, NY.
Barnes, Greg, “A method for implementing lock-free shared-data structures.” InProceedings of the Fifth Annual ACM Symposium on Parallel Algorithms and Architectures, Velen, Germany, Jun. 30-Jul. 2, 1993, pp. 261-270, ACM Press, New York, NY.
Detlefs, David, “Garbage Collection and Run-time Typing as a C++ Library.” InProceedings of the 1992 USENIX C++ Conference, pp. 37-56, Portland, Oregon, Aug. 1992.
Ben-Ari, Mordechai, “On-the-Fly Garbage Collection: New Algorithms Inspired by Program Proofs,”Lectures Notes in Computer Science, vol. 140, pp. 14-22, Springer-Verlag, Berlin, Heidelberg, Germany, 1982.
Ben-Ari, Mordechai, “Algorithms for On-the-Fly Garbage Collection,”ACM Transactions on Programming Languages and Systems, vol. 6, No. 3, pp. 333-344, Jul. 1984.
Bershad, B. N., “Practical Considerations for Non-Blocking Concurrent Objects,” InProceedings of the 13th IEEE International Conference on Distributed Computing Systems, Los Alamitos, California, United States, May 25-28, 1993, pp. 264-273, IEEE Computer Society Press.
Blumofe, Robert D. et al., “Verification of a Concurrent Deque Implementation,” Technical Report TR99-11, University of Texas at Austin, Department of Computer Sciences, pp. 1-20, Jun. 1999.
Brown, Jeremy Hanford, “Memory Management on a Massively Parallel Capability Architecture,” Thesis Proposal, MIT Artificial Intelligence Laboratory, pp. 1-68, Dec. 3, 1999, retrieved from URL: ai.mit.edu/projects/aries/Documents/jhbrown—thesis—proposal.pdf>.
Chuang, Tyng-Ruey et al., “Real-Time Deques, Multihead Turing Machines, and Purely Functional Programming,” InProceedings of the Conference on Functional Programming Languages and Computer Architecture, Copenhagen, Denmark, Jun. 9-11, 1993, pp. 289-298, ACM Press, New York, NY.
Detlefs, David, “Garbage Collection and Run-time Typing as a C++ Library,” InProceedings of the 1992 Useni
Thomson William
Zagorin O'Brien Graham LLP
Zhen Li
LandOfFree
Linked-list implementation of a data structure with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Linked-list implementation of a data structure with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linked-list implementation of a data structure with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3689917