Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
2007-07-17
2007-07-17
Peyton, Tammara (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S053000, C710S055000, C711S147000, C711S153000, C712S228000
Reexamination Certificate
active
10966748
ABSTRACT:
Multiple non-blocking FIFO queues are concurrently maintained using atomic compare-and-swap (CAS) operations. In accordance with the invention, each queue provides direct access to the nodes stored therein to an application or thread, so that each thread may enqueue and dequeue nodes that it may choose. The prior art merely provided access to the values stored in the node. In order to avoid anomalies, the queue is never allowed to become empty by requiring the presence of at least a dummy node in the queue. The ABA problem is solved by requiring that the next pointer of the tail node in each queue point to a “magic number” unique to the particular queue, such as the pointer to the queue head or the address of the queue head, for example. This obviates any need to maintain a separate count for each node.
REFERENCES:
patent: 5864686 (1999-01-01), Kaiser et al.
patent: 6032207 (2000-02-01), Wilson
patent: 6065019 (2000-05-01), Ault et al.
patent: 6173373 (2001-01-01), Bonola
patent: 6178473 (2001-01-01), Bonola
patent: 6249826 (2001-06-01), Parry et al.
patent: 6314476 (2001-11-01), Ohara
Michael et al., “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms,” Department of Computer Science, University of Rochester, pp. 267-275, ACM, Inc., Philadelphia, PA, 1996.
B. Bershad, et al., “Extensibility, Safety and Performance in the Spin Operating System,”15th ACM Symposium on Operating System Principles, Copper Mountain Resort, Colorado, Dec. 1995, pp. 267-284.
D. Black, et al., “Microkernel Operating System Architecture and Mach,”1st USENIX Workshop on Micro-Kernels and Other Kernel Architectures, Seattle, Apr. 1992, pp. 11-30.
D. Cheriton, et al., “A Caching Model of Operating System Kernel Functionality,”Proceedings of the First Symposium on Operating Systems Design and Implementation, Seattle, 1994, 15 pages.
D. Cheriton, “The V Distributed System”,Communications of the ACM, Mar. 1998, vol. 31, No. 3, pp. 314-333.
R. Draves, et al., “Unifying the User and Kernel Environments,”Microsoft Research Technical Report MSR-TR-97-10, Mar. 1997, 16 pages.
D. Engler, et al., “Exokernel: An Operating System Architecture for Application-Level Resource Management,”15th ACM Symposium on Operating System Principles ACM SIGOPS, Copper Mountain Resort, Colorado, Dec. 1995, pp. 251-266.
B. Ford, et al., “The Flux OSKit: A Substrate for Kernel and Language Research,”Proceedings of the 16th ACM Symposium on Operating Systems Principles, ACM SIGOPS, Saint-Malo, France, Oct. 1997, pp. 38-51.
D. Golub, et al., “UNIX as an application program,”USENIX 1990 Summer Conference, Anaheim, CA, Jun. 1990, pp. 87-95.
J. Helander, “Unix Under Mach: The Lites Server,”Master's Thesis, Helsinki University of Technology, 1994, 71 pages.
D. Hildebrand, “An Architectural Overview of QNX,”1st USENIX Workshop on Micro-kernels and Other Kernel Architectures, Seattle, Apr. 1992, pp. 113-126.
M. Jones, et al., “An Overview of the Rialto Real-Time Architecture,”Proceedings of the Seventh ACM SIGOPS European Workshop, SIGOPS, Sep. 1996, pp. 249-256.
M. Jones, et al., “CPU Reservations and Time Constraints: Efficient, Predictable Scheduling of Independent Activities,”Proceedings of the 16th ACM Symposium on Operating System Principles, ACM SIGOPS, Saint-Malo, France, Oct. 1997, pp. 198-211.
M. Jones, The Microsoft Interactive TV System: An Experience Report, Microsoft Research Technical Report MSR-TR-97-18 [online], Jul. 1997, 24 pages, Retrieved Jan. 26, 2000 from the Internet at http://www.research.microsoft.com/research/os/mbj/papers/mitv/tr-97-18.html.
D. Julin, et al., “Generalized Emulation Services for Mach 3.0 Overview, Experiences and Current Status,”Proceedings of the Usenix Mach Symposium USENIX Association, 1991, pp. 13-26.
D. Lee, et al., “Execution Characteristics of Desktop Applications on Windows NT,”Proceedings of the 25th International Symposium on Computer Architecture,, IEEE, Barcelona, Spain, Jun. 1998, pp. 27-38.
J. Liedtke, “On μ-Kernel Construction,”15th ACM Symposium on Operating System Principles, ACM, Copper Mountain Resort, Colorado, Dec. 1995, pp. 237-250.
J. Mogul, et al., “The Packer Filter: An Efficient Mechanism for User-level Network Code,”11th ACM Symposium on Operating System Principles, ACM, Nov. 1987, 34 pages.
R. Rashid, “From RIG to Accent to Mach: The Evolution of a Network Operating System,”Carnegie-Mellon University Technical Report, Aug. 1987, pp. 1128-1137.
M. Rozier, et al., “CHORUS Distributed Operating System,”Computing Systems, Fall 1998, vol. 1, No. 4, pp. 305-370.
Torborg, Jay, et al., “Talisman: Commodity Realtime 3D Graphics for the PC,”Proceeding of SIGGRAPH96, ACM, Aug. 1996, pp. 353-363.
M. Young, “Exporting a User Interface to Memory Management from a Communication-Oriented Operating System,”Ph.D. Thesis CMU-CS-89-202, Carnegie-Mellon University, Nov. 1989, 206 pages.
Office Action dated, Jun. 24, 2004 from parent application, U.S. Appl. No. 10/429,309.
U.S. Appl. No. 09/282,238, Forin et al., filed Mar. 31, 1999.
U.S. Appl. No. 09/282,227, Forin et al., filed Mar. 31, 1999.
U.S. Appl. No. 09/283,818, Forin et al., filed Mar. 31, 1999.
U.S. Appl. No. 09/282,229, Forin et al., filed Mar. 31, 1999.
U.S. Appl. No. 09/282,656, Forin et al., filed Mar. 31, 1999.
Multi-Access First-In-First-Out Queue Using 370 Compare and Swap; IBM Technical Disclosure Bulletin, Feb. 1, 1993; vol. No. 36; Issue No. 2, page. No. 327-330; IBM Corporation.
Forin Alessandro
Raffman Andrew
Microsoft Corporation
Peyton Tammara
LandOfFree
Non-blocking concurrent queues with direct node access by... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Non-blocking concurrent queues with direct node access by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-blocking concurrent queues with direct node access by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3767444