Electrical computers and digital processing systems: interprogra – Interprogram communication using message – Object oriented message
Reexamination Certificate
2006-03-21
2006-03-21
Bullock, Jr., Lewis A. (Department: 2195)
Electrical computers and digital processing systems: interprogra
Interprogram communication using message
Object oriented message
C719S312000, C719S314000
Reexamination Certificate
active
07017160
ABSTRACT:
The Hat Trick deque requires only a single DCAS for most pushes and pops. The left and right ends do not interfere with each other until there is one or fewer items in the queue, and then a DCAS adjudicates between competing pops. By choosing a granularity greater than a single node, the user can amortize the costs of adding additional storage over multiple push (and pop) operations that employ the added storage. A suitable removal strategy can provide similar amortization advantages. The technique of leaving spare nodes linked in the structure allows an indefinite number of pushes and pops at a given deque end to proceed without the need to invoke memory allocation or reclamation so long as the difference between the number of pushes and the number of pops remains within given bounds. Both garbage collection dependent and explicit reclamation implementations are described.
REFERENCES:
patent: 3686641 (1972-08-01), Logan et al.
patent: 3886525 (1975-05-01), Brown et al.
patent: 5797005 (1998-08-01), Bahls et al.
patent: 6223335 (2001-04-01), Cartwright, Jr. et al.
patent: 6247064 (2001-06-01), Alferness et al.
patent: 6360219 (2002-03-01), Bretl et al.
patent: 6374339 (2002-04-01), Iivonen
patent: 0 366 585 (1990-05-01), None
patent: 0 466 339 (1992-01-01), None
patent: WO 86 00434 (1986-01-01), None
Josuttis, Nicolai. “C++ Standard Library: A Tutorial and Reference.” Addison Wesley. Aug. 6, 1999.
Chuang et al. “Real-Time Deques, Multihead Turing Machines, and Purely Functional Programming.” ACM. Jun. 1993.
Blumofe, Robert D. et al., “Verification of a Concurrent Deque Implementation”, University of Texas at Austin, Department of Computer Sciences, Technical Report TR99-11, Jun. 1999.
Farook, Mohammad et al., “Managing Long Linked Lists Using Lock Free Techniques”, University of Manitoba, Canada, 1998.
Michael, Maged M. et al., “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms”, University of Rochester, Department of Computer Science, 1996.
Prakash, Sundeep et al., “Non-Blocking Algorithms for Concurrent Data Structures”, University of Florida, Jul. 1, 1991.
Prakash, Sundeep et al., “A Nonblocking Algorithm for Shared Queues Using Compare-and-Swap”, IEEE Transactions on Computers, vol. 43, No. 5, May 1994.
Shann, Chien-Hua et al., “A Practical Nonblocking Queue Algorithm Using Compare-and Swap”, IEEE, Jul. 2000.
Turek, John et al., “Locking Without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking”, ACM, 1992.
Valois, John D., “Lock-Free Linked Lists Using Compare-and-Swap”, ACM, 1995.
IBM Technical Disclosure Bulletin, “Conditional Multiple Store Instruction”, Feb. 1, 1980.
David L. Detlefs et al., “Even Better DCAS-Based Concurrent Deques,” 14th International Conference, Disc 2000. Proceedings (Lecture Notes in Computer Science, vol. 1914), Distributed Computing, Toledo, Spain, Oct. 4-6, 2000, Online, p. 29-73, XP002172096, 2000, Springer-Verlag, Berlin, Germany, ISBN: 3-540-41143-7, [Retrieved from the Internet on Jul. 13, 2001: URL:http://research.sun.com/jtech/subs/00-deque2.ps].
U.S. Appl. No. 09/547,290, entitled Maintaining a Double-Ended Queue as a Linked-List with Sentinel Nodes and Delete Flags with Concurrent Non-Blocking Insert and Remove Operations Using a Double Compare-And-Swap Primitive, filed Apr. 11, 2000, by inventor(s) Nir N. Shavit, Paul A. Martin, and Guy L. Steele Jr.
U.S. Appl. No. 09/551,311, entitled Shared Object Implemented Using a Linked-List Technique that Tolerates Certain Concurrent Opposing-End Removals Using a Distinguishing Pointer Value, filed Apr. 18, 2000, by inventor(s) Guy L. Steele Jr., Alexander T. Garthwaite, Paul A. Martin, and Nir N. Shavit.
U.S. Appl. No. 09/547,288, entitled Maintaining a Double-Ended Queue in a Contiguous Array with Concurrent Non-Blocking Insert and Remove Operations Using a Double Compare-And-Swap Primitive, filed Apr. 11, 2000, by inventor(s) Nir N. Shavit, Ole Agesen, David L. Detlefs, Christine H. Flood, Alexander T. Garthwaite, Paul A. Martin, and Guy L. Steele Jr.
Y. Afek, M. Merritt, G. Taubenfield, and D. Touitou. “Disentangling Multi-Object Operations,”Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing,pp. 111-120, Aug. 1997. Santa Barbara, CA.
N. S. Arora, Blumofe, and C. G. Plaxton. “Thread Scheduling For Multiprogrammed Multiprocessors,”Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures,1998.
H. Attiya and E. Dagan. “Universal Operations: Unary versus Binary,”Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing,11 pages, May 23-26, 1996. Phila. PA.
Hagit Attiya, Nancy Lynch, and Nir Shavit. “Are Wait-Free Algorithms Fast?”Journal of the ACM,41(4):725-763, pp. 223-232, Jul. 1994.
G. Barnes. “A Method For Implementing Lock-Free Shared Data Structures,”Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures,pp. 261-270, Jun. 1993.
B. N. Bershad. “Practical Considerations For Non-Blocking Concurrent Objects,”Proceedings 13th IEEE International Conference on Distributed Computing Systems,pp. 264-273. IEEE Computer Society Press, May 25-28, 1993. Los Alamitos CA.
M. Greenwald. “Non-Blocking Synchronization and System Design,” PhD thesis, Stanford University Technical Report STAN-CS-TR-99-1624, 241 pages, Palo Alto, CA, 8 1999.
M. B. Greenwald and D. R. Cheriton. “The Synergy Between Non-Blocking Synchronization And Operating System Structure,”2nd Symposium on Operating Systems Design and Implementation,pp. 123-136, Oct. 28-31, 1996. Seattle, WA.
M. Herlihy. “A Methodology For Implementing Highly Concurrent Data Objects,”ACM Transactions on Programming Languages and Systems,15(5):745-770, Nov. 1993.
M. Herlihy and J. Moss. “Transactional memory: Architectural Support For Lock-Free Data Structures,”Technical Report CRL 92/07,Digital Equipment Corporation, 12 pages, Cambridge Research Lab, 1992.
M.P. Herlighy. “Wait-Free Synchronization,”ACM Transactions On Programming Languages and Systems,13(1):124-149, Jan. 1991.
M.P. Herlihy and J.M. Wing. “Linearizability: A Correctness Condition For Con-Current Objects,”ACM Transactions On Programming Languages and Systems,12(3):463-492, Jul. 1990.
H. Massalin and C. Pu. “A Lock-Free Multiprocessor OS Kernel,”Technical Report TR CUCS-005-9,pp. 1-19, Columbia University New York, NY, 1991.
H. 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].
Martin C. Rinard, “Effective Fine-Grain Synchronization for Automatically Parallelized Programs Using Optimistic Synchronization Primitives,”ACM Trans. Computer Systems,17(4):337-371, Nov. 1999.
N. Shavit and D. Touitou. “Software Transactional Memory,”Distributed Computing,10(2):99-116, Feb. 1997.
Hagit Attiya and Ophir Rachman, “Atomic Snapshots in0(nlogn) Operations,” Society for Industrial and Applied Mathematics, SIAM Journal on Computing, Apr. 1998, vol. 27, No. 2, pp. 319-340.
Weiss, Mark Allen,Data Structures&Algorithm Analysis in C++,Second Edition, Reading, Mass., Addison-Wesley, 1999, Chapter 3.
Comer, Douglas,Operating System Design: The Xinu Approach,Englewood Cliffs, New Jersey, Prentice-Hall, Inc., 1984, Chapter 3.
Patterson, David A. and Hennessy, John L., Computer Architecture; A Quantitative Approach, Second Edition, San Francisco, California, Morgan
Detlefs David L.
Garthwaite Alexander T.
Martin Paul A.
Moir Mark S.
Steele, Jr. Guy L.
Bullock, Jr. Lewis A.
Sun Microsystems Inc.
Zagorin O'Brien Graham LLP
LandOfFree
Concurrent shared object implemented using a linked-list... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Concurrent shared object implemented using a linked-list..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Concurrent shared object implemented using a linked-list... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3524274