Scalable and lock-free first-in-first-out queue implementation

Details Scalable and lock-free first-in-first-out queue implementation Scalable and lock-free first-in-first-out queue implementation

2004-10-15

2010-11-16

Hafiz, Tariq (Department: 2182)

Electrical computers and digital data processing systems: input/

Input/output data processing

Input/output data buffering

C710S020000, C710S021000, C710S029000, C710S033000, C710S035000, C710S036000, C711S147000, C719S311000, C719S312000, C719S313000, C719S314000

Reexamination Certificate

active

07836228

ABSTRACT:
A scalable first-in-first-out queue implementation adjusts to load on a host system. The scalable FIFO queue implementation is lock-free and linearizable, and scales to large numbers of threads. The FIFO queue implementation includes a central queue and an elimination structure for eliminating enqueue-dequeue operation pairs. The elimination mechanism tracks enqueue operations and/or dequeue operations and eliminates without synchronizing on the FIFO queue implementation.

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: 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: 6651146 (2003-11-01), Srinivas et al.
patent: 6826757 (2004-11-01), Steele, Jr. et al.
patent: 7243354 (2007-07-01), Chhabra et al.
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: 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/0034743 (2004-02-01), Wolrich et al.
patent: 2004/0153687 (2004-08-01), Moir et al.
patent: 2004/0240444 (2004-12-01), Matthews et al.
patent: 2005/0240924 (2005-10-01), Jones et al.
patent: 2007/0165043 (2007-07-01), Fouladi 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
patent: WO 03/060705 (2003-07-01), None
patent: WO 03/060715 (2003-07-01), None
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.
U.S. Appl. No. 10/653,828, filed Sep. 3, 2003 and naming as inventor(s) Martin et al.
U.S. Appl. No. 10/669,948, filed Sep. 24, 2003 and naming as inventor(s) Dice et al.
U.S. Appl. No. 10/670,495, filed Sep. 24, 2003 and naming as inventor(s) Shavit et al.
U.S. Appl. No. 10/894,828, filed Jul. 20, 2004 and naming as inventor(s) Moir et al.
U.S. Appl. No. 10/894,829, filed Jul. 20, 2004 and naming as inventor(s) Moir et al.
U.S. Appl. No. 10/915,502, filed Aug. 10, 2004 and naming as inventor(s) Moir, Mark.
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, 2007: 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.
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.
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.
Farook, Mohammad et al., “Managing Long Linked Lists Using Lock Free Techniques” inHigh Performance Computing Systems and Applications, Chapter 37(pp. 407-422), Kluwer Academic Publishers, Oct. 1998.
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 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.
Herlihy, Maurice et al., “Obstruction-Free Synchronization: Double-Ended Queues as an Example,”Proceedings of the 23rd International Conference on Distributed Computing, p. 522, IEEE Computer Society, Washington, D.C., 2003.
Laden-Mozes, E., et al., “An Optimistic Approach to Lock-free FIFO Queues,”Lecture Notes in Computer Science, vol. 3274, pp. 117-131, Springer-Verlag Berlin Heidelberg 2004.
Martin, Paul et al., “DCAS-Based Concurrent Deques Supporting Bulk Allocation,” Sun Microsystems, Inc. Technical Report SMI TR-2002-111, Oct. 2002.
Michael, M., “Scalable Lock-Free Dynamic Memory Allocation,”Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, pp. 35-46, ACM Press, New York, NY, 2004.
Shann, Chien-Hua et al., “A Practical Nonblocking Queue Algorithm Using Compare-and Swap,”Proceedings of the Seventh International Conference on Parallel and Distributed Systemsp. 470, IEEE Computer Society, Washington, D.C., 2000.
Goetz, Brian, “A First Look at JSR 166: Concurrency Utilities,” Mar. 1, 2004. [URL:http://today.java.net/lpt/a/76].
Dolev, Danny and Shavit, Nir, “Bounded Concurrent Time-Stamping,” SIAM J. Comput., Apr. 1997, No. 2:418-455, vol. 26.
Goodman, James R. et al., “Efficient Synchronization Primitives for Large-Scale Cache-Coherent Multiprocessors,” Proceedings Of The Third International Conference on Architectural Support for Programming Languages and Operating Systems, Apr. 3-6, 1989, pp. 64-75, ACM Press.
Gottleib, Allan, et al., “Basic Techniques For The Efficient Coordination Of Very Large Numbers Of Cooperating Sequential Processors,” AC

Affiliated with

Also associated with

Rating

Scalable and lock-free first-in-first-out queue implementation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Scalable and lock-free first-in-first-out queue implementation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalable and lock-free first-in-first-out queue implementation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4216365