Electrical computers and digital processing systems: interprogra – Interprogram communication using message – Object oriented message
Reexamination Certificate
2006-02-14
2006-02-14
Bullock, Jr., Lewis A. (Department: 2195)
Electrical computers and digital processing systems: interprogra
Interprogram communication using message
Object oriented message
C719S313000, C719S314000
Reexamination Certificate
active
07000234
ABSTRACT:
A linked-list-based concurrent shared object implementation has been developed that provides non-blocking and linearizable access to the concurrent shared object. In an application of the underlying techniques to a deque, the linked-list-based algorithm allows non-blocking completion of access operations without restricting concurrency in accessing the deque's two ends. The new implementation is based at least in part on a new technique for splitting a pop operation into two steps, marking that a node is about to be deleted, and then deleting it. Once marked, the node logically deleted, and the actual deletion from the list can be deferred. In one realization, actual deletion is performed as part of a next push or pop operation performed at the corresponding end of the deque. An important aspect of the overall technique is synchronization of delete operations when processors detect that there are only marked nodes in the list and attempt to delete one or more of these nodes concurrently from both ends of the deque.
REFERENCES:
patent: 3686641 (1972-08-01), Logan et al.
patent: 3886525 (1975-05-01), Brown et al.
patent: 4847754 (1989-07-01), Obermarck et al.
patent: 5222238 (1993-06-01), Zobre et al.
patent: 5797005 (1998-08-01), Bahls 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
Blumofe, Robert D. et al. “Verification of a Concurrent Deque Implementation.” Jun. 1999.
Shann, Chien-Hua et al. “A practicial nonblocking queue algorithm using compare-and-swap”. IEEE. Jul., 2000.
Prakash, Sundeep et al. “A Nonblocking Algorithm for Shared Queues Using Compare-and-swap.” IEEE. May 1994.
Michael, Maged et al. “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms.” ACM. 1996.
Prakesh, Sundeep et al. “Non-Blocking Algorithms for Concurrent Date Structures.” Jul. 1, 1991.
Valois, John D. “Lock-Free Linked Lists Using Compare-and-Swap.” ACM. 1995.
Turek, John et al. “Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking.” ACM. 1992.
Farook, Mahammad et al. “Managing Long Linked Lists Using Lock Free Techniques.” University of manitoba, Canada.
IBM Technical Disclosure Bulletin. “Conditional Multiple Store Instruction.” Feb. 1, 1980.
Stone, Janice M. “A simple and correct shared-queue algorithm using Compare-and-Swap.” IEEE. 1990.
U.S. Appl. No. 09/551,113, entitled Concurrent Shared Object Implemented Using a Linked List with Amortized Node Allocation, filed Apr. 18, 2000, by inventors(s) Paul A. Martin, David L. Detlefs, Alexander T. Garthwaite, 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. Taubenfeld, 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.
Hagit Attiya and Ophir Rachman. “Atomic Snapshots In O(n log n) Operations,”SIAM Journal on Computing, 27(2):319-340, pp. 1-42, Mar. 1998.
G. Barnes. “A Method For Implementing Lock-Free Shared Data Structures,”Proceedings of the 5th 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 Reseach Lab, 1992.
M.P. Herlihy. “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.
D. E. Knuth. “The Art of Computer Programming: Fundamental Algorithms,” Addison-Wesley, 2nd edtition, 3 pages, 1968.
A. LaMarca. “A performance evaluatio of lock-free synchronization protocols,”Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, pp. 130-140, Aug. 14-17, 1994. Los Angeles, CA.
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.
N. Shavit and Touitou. “Software Transactional Memory,”Distriubted Computing, 10(2):99-116, Feb. 1997.
U.S. Appl. No. 09/207,940, entitled Platform Independent Double Compare and Swap Operation, filed Dec. 9, 1998, by inventor(s) Robert Cartwright Jr. and Ole Agesen.
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 Unversity, 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].
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 Kaufman Publishers, Inc., 1996, pp. 485-495 and 562-572.
Cohoon, James P. and Davidson, Jack W.,C++ Program Design: An Introduction to Programming and Object-Oriented Design, Second Edition, New York, New York, WCB/McGraw-Hill, 1999, pp. 465-502.
Stroustrup, Bjarne, The C++ Programming Language, Third Edition, Reading, Mass., Addison-Wesley, 1997, pp. 461-497.
Chuang, Tyng-Ruey et al., “Real-Ti
Martin Paul A.
Shavit Nir N.
Steele, Jr. Guy L.
Bullock, Jr. Lewis A.
Sun Microsystems Inc.
Zagorin O'Brien Graham
LandOfFree
Maintaining a double-ended queue as a linked-list 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 Maintaining a double-ended queue as a linked-list with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maintaining a double-ended queue as a linked-list with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3695900