Electrical computers and digital processing systems: interprogra – High level application control
Reexamination Certificate
2011-06-14
2011-06-14
Ho, Andy (Department: 2194)
Electrical computers and digital processing systems: interprogra
High level application control
Reexamination Certificate
active
07962923
ABSTRACT:
A method of supporting condition synchronization for a shared data structure so as to provide concurrent access. A protocol is provided between a thread creating a request as part of a remove operation and a thread fulfilling a request as part of an add operation. The protocol provides for the thread making such a request to check the request_value field of the request node and then wait on its own condition variable. A requesting thread sets a requestor_id field of a request node with a value that identifies the thread. A fulfilling thread sets a request_value field of a request node with the address of the data node with the value, and then signals the requesting thread as identified by the requestor_id field. Upon receiving the signal, the requesting thread wakes up and retrieves the value from the data node pointed to it by the request_value field of the request node. If a wait times out, the requesting thread attempts to signal that the wait timed out by performing a CAS operation on the request_value field to modify it from zero to non-zero. If the CAS operation succeeds, the request timed out and the remove operation return failure. If the CAS operation fails, the request was fulfilled since the fulfilling thread set the request_value field with the address of the data node.
REFERENCES:
patent: 5706515 (1998-01-01), Connelly et al.
patent: 6651146 (2003-11-01), Srinivas et al.
patent: 6826757 (2004-11-01), Steele et al.
patent: 7117502 (2006-10-01), Harris
patent: 7293143 (2007-11-01), Shavit et al.
patent: 2007/0169123 (2007-07-01), Hopkins
Nick Parlante, “Linked List Basics”, 2001, Stanford CS Education Library, pp. 1-25.
Maurice P. Herlihy, “A Methodology for Implementing Highly Concurrent Data Objects,” ACM Transactions on Programming Languages and Systems, Oct. 2, 1991.
Maged M. Michael, “High Performance Dynamic Lock-Free Hash-Tables and List-Based Sets,” Poc. 14th Annual ACM Symp. Parallel Algorithms and Architectures, Aug. 2002.
Maged M. Michael, “Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects,” IEEE Transactions on Parallel and Distributed Systems, vol. 15, No. 6, pp. 491-504, Jun. 2004.
Maged M. Michael, “Scalable Lock-Free Dynamic Memory Allocation,” The 2004 ACM SIGPLAN Conference on Programming Language Design and Implementation, Jun. 2004.
Maged M. Michael and Michael L. Scott, “Simple, Fast, and Practical Non-blocking and Blocking Concurrent Queue Algorithms,” Proc. 15th Annual ACM Symp. Principles of Distributed Computing, May 1996.
William N. Scherer III and Michael L. Scott, “Nonblocking Concurrent Data Structures with Condition Synchronization,” 18th Annual Conf. on Distributed Computing, Oct. 2004.
Maged M. Michael, “CAS-Based Lock-Free Algorithm for Shared Deques,” Proc. Ninth Euro-Par Conf. Parallel Processing, Aug. 2003.
Ho Andy
Level 3 Communications LLC
Mudrick Timothy A
LandOfFree
System and method for generating a lock-free dual queue does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for generating a lock-free dual queue, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for generating a lock-free dual queue will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2621589